Apriori算法实现
时间: 2023-09-15 13:17:56 浏览: 51
Apriori算法是一种挖掘频繁项集的常用算法,它基于先验性质,通过逐层剪枝来减少搜索空间,从而提高挖掘效率。
下面是一个简单的Apriori算法实现:
1. 初始化数据集D,设置最小支持度min_support和最小置信度min_confidence。
2. 生成频繁1项集C1:遍历数据集D,统计每个项的支持度,筛选出支持度不小于min_support的项。
3. 生成频繁1项集L1:将C1中的项按照支持度排序,筛选出前k个支持度最高的项,作为频繁1项集L1。
4. 生成候选项集Ck:根据频繁(k-1)项集Lk-1生成候选项集Ck,具体方法为:将Lk-1中的每个项与自身合并,去重得到Ck。
5. 筛选频繁项集Lk:遍历数据集D,统计Ck中每个候选项集的支持度,筛选出支持度不小于min_support的项作为频繁项集Lk。
6. 重复步骤4和5,直到没有更多的频繁项集产生。
7. 生成关联规则:对于每个频繁项集Lk,根据其子集生成关联规则,具体方法为:对于Lk中的每个项集S,将其划分为两个子集A和B,计算其置信度,筛选出置信度不小于min_confidence的关联规则。
下面是一个简单的Python实现:
```python
def generate_C1(data_set):
C1 = []
for transaction in data_set:
for item in transaction:
if not [item] in C1:
C1.append([item])
C1.sort()
return list(map(frozenset, C1))
def scan_D(D, Ck, min_support):
ss_cnt = {}
for tid in D:
for can in Ck:
if can.issubset(tid):
if not can in ss_cnt:
ss_cnt[can] = 1
else:
ss_cnt[can] += 1
num_items = float(len(D))
ret_list = []
support_data = {}
for key in ss_cnt:
support = ss_cnt[key] / num_items
if support >= min_support:
ret_list.append(key)
support_data[key] = support
return ret_list, support_data
def apriori_gen(Lk, k):
ret_list = []
len_Lk = len(Lk)
for i in range(len_Lk):
for j in range(i + 1, len_Lk):
L1 = list(Lk[i])[:k - 2]
L2 = list(Lk[j])[:k - 2]
L1.sort()
L2.sort()
if L1 == L2:
ret_list.append(Lk[i] | Lk[j])
return ret_list
def apriori(data_set, min_support=0.5):
C1 = generate_C1(data_set)
D = list(map(set, data_set))
L1, support_data = scan_D(D, C1, min_support)
L = [L1]
k = 2
while len(L[k - 2]) > 0:
Ck = apriori_gen(L[k - 2], k)
Lk, supK = scan_D(D, Ck, min_support)
support_data.update(supK)
L.append(Lk)
k += 1
return L, support_data
def generate_rules(L, support_data, min_confidence=0.7):
big_rule_list = []
for i in range(1, len(L)):
for freq_set in L[i]:
H1 = [frozenset([item]) for item in freq_set]
if i > 1:
rules_from_conseq(freq_set, H1, support_data, big_rule_list, min_confidence)
else:
calc_conf(freq_set, H1, support_data, big_rule_list, min_confidence)
return big_rule_list
def calc_conf(freq_set, H, support_data, brl, min_confidence=0.7):
prunedH = []
for conseq in H:
conf = support_data[freq_set] / support_data[freq_set - conseq]
if conf >= min_confidence:
print(freq_set - conseq, "-->", conseq, "conf:", conf)
brl.append((freq_set - conseq, conseq, conf))
prunedH.append(conseq)
return prunedH
def rules_from_conseq(freq_set, H, support_data, brl, min_confidence=0.7):
m = len(H[0])
if len(freq_set) > (m + 1):
Hmp1 = apriori_gen(H, m + 1)
Hmp1 = calc_conf(freq_set, Hmp1, support_data, brl, min_confidence)
if len(Hmp1) > 1:
rules_from_conseq(freq_set, Hmp1, support_data, brl, min_confidence)
```
这个实现只是一个简单的示例,具体应用时需要根据数据集的特点进行优化。