文章目次
一、问题形貌
某个商场的事务数据库D如表1所示,包罗9个事务,即|D|=9。假设最小支持度min_sup=2,请使用Apriori算法找到D中的频仍项集,并输出所有的关联规则(实验编程语言不限)。
二、实验思路
1、数据格式
(1)想要得到类似于下图的表格输出,则需用到DataFrame,使用DataFrame则Lk、Ck集确定为字典的格式。
(2)由于DataFram是把字典的键作为列标签,若要让频仍项集一列、支持度计数一列,则需要举行转置。
- print(pd.DataFrame(C, index=['支持度计数']).T)
复制代码 (3)字典是无序的,Apriori算法需要字典是有序的,所以在盘算每一项出现的次数之前,先把key按顺序分列好放入字典中。
以C1的处理处罚为例:
- # C1 C={} Lkey = [] for values in data['商品ID的列表']: Lkey.extend(["{"+item+"}" for item in values if item not in Lkey]) Lkey.sort()# 整理键的顺序 for i in Lkey: C[i]=0 for values in data['商品ID的列表']: for item in values: C["{"+item+"}"]+=1"""——————C1—————— 支持度计数{I1} 6{I2} 7{I3} 6{I4} 2{I5} 2"""
复制代码 (4)字典不是不支持列表吗?如果要生成如下图的效果怎么用字典实现?
强制范例转换,把列表转成字符串。同时增加对额外字符“{”、"}"的处理处罚。
- # 对额外字符的处理处罚-删去for key in L.keys(): key = key.replace('{','') key = key.replace('}','') Lstr.append(key) Lkey.append(key.split(',')) # 对额外字符的处理处罚-增加Lkey_new.sort()# 整理键的顺序for i in Lkey_new: C["{"+i+"}"]=0
复制代码 2、频仍项集
(1)毗连步—产生候选式Ck
敲重点:
1)以聚集 L 1 = L_1= L1={{I1,I2},{I1,I3},{I1,I5},{I2,I3},{I2,I4},{I2,I5}}为例(下标从1开始数)
i) L L L是聚集{{I1,I2},{I1,I3},{I1,I5},{I2,I3},{I2,I4},{I2,I5}}
ii) l i l_i li是聚集L中的项集,如 l 1 = l_1= l1={I1,I2}、 l 2 = l_2= l2={I2,I5}
iii) l i [ j ] l_i[j] li[j]表现 l i l_i li的第 j j j项,如 l 1 [ 1 ] = l_1[1]= l1[1]=I1, l 4 [ 2 ] = l_4[2]= l4[2]=I3
iiii)前 k − 2 k-2 k−2个项相同等价于除了最后一个项以外别的项都相同。
如{I1,I2},{I1,I3},第一项相同,最后一项差别,归并为{I1,I2,I3}
如{I1,I2},{I2,I3},第一项差别,不举行归并,若归并则会与前面的项重复,这条规则是为了不产生重复项。
2)项按字典序排序,即{I1,I2}需放在{I1,I3}的前面,这步在二、1、数据格式中先容过了。
- # 产生候选Cdef Apriori_gen(Lkey,Lstr): # Lkey-字典L的key-列表/Lstr-字典L的key-字符串 # 毗连步 C={} Lkey_new = [] for i in range(len(Lkey)-1): j=i flag = 0 for j in range(i+1,len(Lkey)): # 查抄Lkey[i]和Lkey[j]是否除最后一项外前面的几项都相同 for x in range(len(Lkey[i])): if x==len(Lkey[i])-1: if Lkey[i][x]==Lkey[j][x]: print("ERROR:出现重复的频仍项") print(Lkey[i]) print(Lkey[j]) exit(0) else: # 找到归并项集,参加 temp=Lstr[i]+','+str(Lkey[j][x]) # 若子集都是频仍项集,则参加到新的键表中 if not Has_infrequent_subset(temp,Lkey): Lkey_new.append(temp) # 若前k-2项出现差别,退出循环 elif Lkey[i][x]!=Lkey[j][x]: flag=1 break if flag==1: break # 整理键的顺序 Lkey_new.sort() for i in Lkey_new: C["{"+i+"}"]=0 return C
复制代码 (2)剪枝步—产生频仍项集Lk
1)把有非频仍子集的候选集剔除
- # 判断是否存在非频仍项集def Has_infrequent_subset(candi_set,Lkey): # candi_set-候选集、L_k-1的频仍集 candi_set = candi_set.split(',') for x in candi_set: subset = candi_set[:] subset.remove(x) if subset not in Lkey: return True return False# 若子集都是频仍项集,则参加到新的键表中if not Has_infrequent_subset(temp,Lkey): Lkey_new.append(temp)
复制代码 2)把小于最小支持度的频仍项集删除,即把大于便是最小支持度的频仍项集参加到L中
- L = {}for key, values in C.items(): if values >= min_sup: L[key] = values
复制代码 (3)输出效果
- ——————Data—————— 商品ID的列表0 [I1, I2, I5]1 [I2, I4]2 [I2, I3]3 [I1, I2, I4]4 [I1, I3]5 [I2, I3]6 [I1, I3]7 [I1, I2, I3, I5]8 [I1, I2, I3]——————C1—————— 支持度计数{I1} 6{I2} 7{I3} 6{I4} 2{I5} 2——————L1—————— 支持度计数{I1} 6{I2} 7{I3} 6{I4} 2{I5} 2——————C2—————— 支持度计数{I1,I2} 4{I1,I3} 4{I1,I4} 1{I1,I5} 2{I2,I3} 4{I2,I4} 2{I2,I5} 2{I3,I4} 0{I3,I5} 1{I4,I5} 0——————L2—————— 支持度计数{I1,I2} 4{I1,I3} 4{I1,I5} 2{I2,I3} 4{I2,I4} 2{I2,I5} 2——————C3—————— 支持度计数{I1,I2,I3} 2{I1,I2,I5} 2——————L3—————— 支持度计数{I1,I2,I3} 2{I1,I2,I5} 2
复制代码 3、关联规则
(1)盘算方法
敲重点:
1)频仍项集 l l l是聚集 T T T的子集,这里的聚集 T T T即为上一步的效果 L L L。
2)如求解 A = > B A=>B A=>B的置信度,则先求数据库中 A ∪ B A\cup B A∪B的数目,再求数据库中 A A A的数目,做除法,效果为 A = > B A=>B A=>B的置信度。若大于最小置信度阈值则输出关联规则。
- # 产生非空子集并盘算关联度def Non_subset(Lkey,D,min_conf): # Lkey-频仍项集的聚集、D-数据库、min_conf-最小置信度 conf={} for l in Lkey: non_subset = [] # 获取频仍项集l的所有非空子集 for i in range(len(l)): for j in combinations(l, i + 1): non_subset.append(j) # 对非空子集举行格式处理处罚 non_subset_new = [] for i in non_subset: temp = [] for j in i: temp.append(j) non_subset_new.append(temp) # 产生关联规则/盘算关联度 for i in range(len(non_subset_new)-1): for j in range(i+1,len(non_subset_new)): A = non_subset_new[i] B = non_subset_new[j] AB = list(set(A).union(set(B))) # 取并集 # 存在相同元素 if len(AB)!=len(A)+len(B): continue # 盘算数目 A_cnt = Cul_itemcnt(D,A) B_cnt = Cul_itemcnt(D,B) AB_cnt = Cul_itemcnt(D,AB) if len(A) == 1: Astr = A[0] else: Astr = Conf_deal(A) if len(B) == 1: Bstr = B[0] else: Bstr = Conf_deal(B) # 与最小置信度阈值比力 if AB_cnt/A_cnt>=min_conf: s = Astr+"=>"+Bstr s = s.replace("'","") conf[s] = AB_cnt/A_cnt if AB_cnt/B_cnt>=min_conf: s = Bstr+"=>"+Astr s = s.replace("'","") conf[s] = AB_cnt/B_cnt return conf
复制代码 (2)输出效果
假定最小置信度阈值为0
- 置信度I1=>I2 0.666667I2=>I1 0.571429I1=>I3 0.666667I3=>I1 0.666667I1=>{I2, I3} 0.333333{I2, I3}=>I1 0.500000I2=>I3 0.571429I3=>I2 0.666667I2=>{I1, I3} 0.285714{I1, I3}=>I2 0.500000I3=>{I1, I2} 0.333333{I1, I2}=>I3 0.500000I1=>I5 0.333333I5=>I1 1.000000I1=>{I2, I5} 0.333333{I2, I5}=>I1 1.000000I2=>I5 0.285714I5=>I2 1.000000I2=>{I1, I5} 0.285714{I1, I5}=>I2 1.000000I5=>{I1, I2} 1.000000{I1, I2}=>I5 0.500000
复制代码 三、完整代码
Apriori算法求解关联规则完整代码
来源:https://blog.csdn.net/weixin_44012551/article/details/111980815
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作! |