请选择 进入手机版 | 继续访问电脑版

【Python】Apriori算法求解关联规则

[复制链接]
唐少琼 发表于 2021-1-3 12:22:03 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
文章目次



一、问题形貌

某个商场的事务数据库D如表1所示,包罗9个事务,即|D|=9。假设最小支持度min_sup=2,请使用Apriori算法找到D中的频仍项集,并输出所有的关联规则(实验编程语言不限)。

二、实验思路

1、数据格式

(1)想要得到类似于下图的表格输出,则需用到DataFrame,使用DataFrame则Lk、Ck集确定为字典的格式。

(2)由于DataFram是把字典的键作为列标签,若要让频仍项集一列、支持度计数一列,则需要举行转置。
  1. print(pd.DataFrame(C, index=['支持度计数']).T)
复制代码
(3)字典是无序的,Apriori算法需要字典是有序的,所以在盘算每一项出现的次数之前,先把key按顺序分列好放入字典中。
以C1的处理处罚为例:
  1. # 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)字典不是不支持列表吗?如果要生成如下图的效果怎么用字典实现?

强制范例转换,把列表转成字符串。同时增加对额外字符“{”、"}"的处理处罚。
  1. # 对额外字符的处理处罚-删去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、数据格式中先容过了。
  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)把有非频仍子集的候选集剔除
  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中
  1. L = {}for key, values in C.items():        if values >= min_sup:                L[key] = values
复制代码
(3)输出效果

  1. ——————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的置信度。若大于最小置信度阈值则输出关联规则。
  1. # 产生非空子集并盘算关联度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
  1.                置信度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
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )