随着大数据概念的火热，啤酒和尿布的故事家喻户晓。我们如何发现经常购买啤酒的人也购买尿布的规律？数据挖掘中挖掘频繁项集和关联规则的Apriori算法可以告诉我们。本文首先介绍了Apriori算法，然后进一步介绍了相关的基本概念，然后详细介绍了Apriori算法的具体策略和步骤，最后给出了Python实现代码。1.Apriori算法简介Apriori算法是一种经典的数据挖掘算法，用于挖掘频繁项集和关联规则。Apriori在拉丁语中的意思是“从前”。在定义问题时，通常会使用先验知识或假设，这称为“先验”。Apriori算法的名称是基于该算法利用了频繁项集的先验性质，即频繁项集的所有非空子集也一定是频繁的。Apriori算法使用称为逐层搜索的迭代方法，其中使用k项集来探索(k+1)项集。首先通过扫描数据库，累加每一项的个数，收集满足最小支持度的项，找出频繁1-项集的集合。该集合表示为L1。然后，用L1找出频繁2项集的集合L2，用L2找出L3，以此类推，直到找不到更多的频繁k项集。需要对数据库进行全面扫描才能找出Lk。Apriori算法利用频繁项集的先验特性来压缩搜索空间。2.基本概念item和itemset：令itemset={item1,item_2,…,item_m}为所有item的集合，其中item_k(k=1,2,…,m)成为一个item。项的集合称为项集，包含k个项的项集称为k-项集。交易和交易集：交易T是一个项目集，是项目集的一个子集，每笔交易关联一个唯一的标识符Tid。不同的交易共同构成一个交易集D，它构成了关联规则发现的交易数据库。关联规则：关联规则是A=>B形式的蕴涵，其中A和B都是项集的子集并且都不是空集，并且A与B相交是空的。支持度：关联规则的支持度定义如下：其中P(A∪B)表示交易包含集合A和B的并集（即包含A和B中的每一项）的概率。注意与P(AorB)的区别，P(AorB)表示一笔交易包含A或B的概率。Confidence：关联规则的置信度定义如下：Itemsetoccurrencefrequency（supportcount）：包含一个itemset的事务的数量，简称frequency，supportcount，或itemset的count。频繁项集（frequentitemset）：如果项集I的相对支持度满足预先定义的最小支持度阈值（即I的出现频率大于对应的最小出现频率（支持度计数）阈值），则I为频繁项集。强关联规则：满足最小支持度和最小置信度的关联规则，即待挖掘的关联规则。3.实现步骤关联规则的挖掘一般分为两步：找出所有频繁项集从频繁项集生成强关联规则3.1挖掘频繁项集3.1.1相关定义-1)项集自连接Lk-1生成候选k个项集CkApriori算法假设项集中的项按字典顺序排序。如果Lk-1中的某些两个元素（项集）itemset1和itemset2的前（k-2）项相同，则称itemset1和itemset2是可连接的。所以连接itemset1和itemset2生成的结果itemset是{itemset1[1],itemset1[2],...,itemset1[k-1],itemset2[k-1]}。连接步骤包含在下面代码中的create_Ck函数中。由于修剪策略的先验性质：任何非频繁(k-1)项集都不是频繁k项集的子集。因此，如果一个候选k-项集Ck的(k-1)项子集不在Lk-1中，则该候选不可能是频繁的，因此可以将其从Ck中删除，得到压缩后的Ck。下面代码中的is_apriori函数用于判断是否满足先验性质，create_Ck函数中包含剪枝步骤，即如果不满足先验性质，则进行剪枝。删除策略是基于压缩后的Ck，扫描所有事务，对Ck中的每一项进行计数，然后删除不满足最小支持度的项，从而得到频繁的k-项集。删除策略包含在下面代码中的generate_Lk_by_Ck函数中。3.1.2步骤每个项目都是候选1-项目集C1的成员。该算法扫描所有交易，获取每个项目，并生成C1（见下面代码中的create_C1函数）。然后计算每个项目。然后根据最小支持度从C1中删除不满足的项，从而得到频繁1-项集L1。对L1自连接生成的集合执行剪枝策略，生成候选2项集的集合C2，然后扫描所有事务并对C2中的每一项进行计数。同样根据最小支持度从C2中删除不满足的项，从而得到频繁2-项集L2。对L2自连接生成的集合执行剪枝策略生成候选3项集的集合C3，然后扫描所有事务并对C3的每一项进行计数。同理，根据最小支持度从C3中删除不满足的项，得到频繁3-项集L3。以此类推，对Lk-1自连接生成的集合执行剪枝策略生成候选k-项集Ck，然后扫描所有事务并对Ck中的每一项进行计数。然后根据最小支持度从Ck中删除不满足的项，从而得到频繁的k-项集。3.2从频繁项集生成关联规则一旦找到频繁项集，就可以直接从中生成强关联规则。生成步骤如下：对每个频繁项集项集，生成项集的所有非空子集（这些非空子集必须是频繁项集）；对于项目集的每个非空子集s，if则输出s=>(l-s)，其中min_conf是最小置信度阈值。4.示例和Python实现代码下图是《数据挖掘：概念与技术》（第三版）中挖掘频繁项集的示例说明。本文根据本样本数据编写Python代码实现Apriori算法。代码中需要注意以下两点：由于Apriori算法假设项集中的项是按字典顺序排序的，而集合本身是无序的，所以需要时我们需要对集合和列表进行转换；因为我们需要用字典（support_data）来记录一个itemset的支持度，所以需要用itemset作为key，而变量set不能作为字典的key。因此，应适时将项集转化为固定集frozenset。"""#Python2.7#Filename:apriori.py#Author:llhthinker#Email:hangliu56[AT]gmail[DOT]com#Blog:http://www.cnblogs.com/llhthinker/p/6719779.html#日期：2017-04-16"""defload_data_set():"""Loadasampledataset(FromDataMining:ConceptsandTechniques,3thEdition)返回：Adataset:Alistoftransactions.Eachtransactioncontainsseveralitems."""data_set=[['l1','l2','l5'],['l2','l4'],['l2','l3'],['l1','l2','l4'],['l1','l3'],['l2','l3'],['l1','l3'],['l1','l2','l3','l5'],['l1','l2','l3']]returndata_setdefcreate_C1(data_set):"""Createfrequentcandidate1-itemsetC1byscaningdataset.Args:data_set:Alistoftransactions.Eachtransactioncontainsseveralitems.Returns:C1:Asetwhichcontainsallfrequentcandidate1-itemsets"""C1=set()fortindata_set:foritemint:item_set=frozenset([item])C1.add(item_set)returnC1defis_apriori(Ck_item,Lksub1):"""判断是否频繁候选k-itemsetsatisfyAprioriproperty.Args:Ck_item:afrequentcandidatek-itemsetinCkwhichcontainsallfrequentcandidatek-itemsets.Lksub1:Lk-1,asetwhichcontainsallfrequentcandidate(k-1)-itemsets.Returns:True:satisfyingAprioriproperty.False:NotsatisfyingAprioriproperty."""foriteminCk_item:sub_Ck=Ck_item-frozenset([item])ifsub_CknotinLksub1:returnFalsereturnTruedefcreate_Ck(Lksub1,k):"""CreateCk,asetwhichcontainsallallfrequentcandidatek-itemsetsbyLk-1'sownconnectionoperation.Args:Lksub1:Lk-1,asetwhichcontainsallfrequentcandidate(k-1)-itemsets.k:theitemnumberofafrequentitemset.Return:Ck:asetwhichcontainsallallfrequentcandidatek-itemsets."""Ck=set()len_Lksub1=len(Lksub1)list_Lksub1=list(Lksub1)foriinrange(len_Lksub1):forjinrange(1,len_Lksub1):l1=list(list_Lksub1[i])l2=list(list_Lksub1[j])l1.sort()l2.sort()ifl1[0:k-2]==l2[0:k-2]:Ck_item=list_Lksub1[i]|list_Lksub1[j]#pruningifis_apriori(Ck_item,Lksub1):Ck.add(Ck_item)returnCkdefgenerate_Lk_by_Ck(data_set,Ck,min_support,support_data):"""GenerateLkbyexecutingadeletepolicyfromCk.Args:data_set:Alistoftransactions.Eachtransactioncontainsseveralitems.Ck:Asetwhichcontainsallallfrequentcandidatek-itemsets.min_support:Theminimumsupport.support_data:Adictionary.Thekeyisfrequentitemsetandthevalueissupport.Returns:Lk:Asetwhichcontainsallallfrequentk-itemsets."""Lk=set()item_count={}fortindata_set:foriteminCk:ifitem.issubset(t):ifitemnotinititem_count:item_count[item]=1else:item_count[item]+=1t_num=float(len(data_set))foriteminitem_count:if(item_count[item]/t_num)>=min_support:Lk.add(item)support_data[item]=item_count[item]/t_numreturnLkdefgenerate_L(data_set,k,min_support):"""Generateallfrequentitemsets.Args:data_set:Alistoftransactions.Eachtransactioncontainsseveralitems.k:所有频率项集的最大项数.min_support:Theminimumsupport.Returns:L:ThelistofLk.support_data:Adictionary.Thekeyisfrequentitemsetandthevalueissupport."""support_data={}C1=create_C1(data_set)L1=generate_Lk_by_Ck(data_set,C1,min_support,support_data)Lksub1=L1.copy()L=[]L.append(Lksub1)foriinrange(2,k+1):Ci=create_Ck(Lksub1,i)Li=generate_Lk_by_Ck(data_set,Ci,min_support,support_data)Lksub1=Li.copy()L.append(Lksub1)returnL,support_datadefgenerate_big_rules(L,support_data,min_conf):"""Generatebigrulesfromfrequentitemsets.Args:L:ThelistofLk.support_data:Adictionary.Thekeyisfrequentitemsetandthevalueissupport.min_conf:Minimalconfidence.Returns:big_rule_list:Alistwhichcontainsallbigrules.Eachbigruleisrepresentedasa3-tuple."""big_rule_list=[]sub_set_list=[]foriinset_range(0,foriinLrange):包含所有bigrules的Alist[i]:forsub_setinsub_set_list:ifsub_set.issubset(freq_set):conf=support_data[freq_set]/support_data[freq_set-sub_set]big_rule=(freq_set-sub_set,sub_set,conf)ifconf>=min_confandbig_rulenotinbig_rule_list:#printfreq_set-sub_set,"=>",sub_set,"conf:",confbig_rule_list.append(big_rule)sub_set_list.append(freq_set)returnbig_rule_listif__name__=="__main__":"""测试"""data_set=load_data_set()L,support_data=generate_L(data_set,k=3,min_support=0.2)big_rules_list=generate_big_rules(L,support_data,min_conf=0.7)forLkinL:print"="*50print"frequent"+str(len(list(Lk)[0]))+"-itemsets\t\tsupport"print"="*50forfreq_setinLk:printfreq_set,support_data[freq_set]printprint"BigRules"foriteminbig_rules_list:printitem[0],"=>",item[1],"conf:",item[2]代码运行结果截图如下：
