关联规则算法Apriori的学习与实现

1关联规则算法Apriori的学习与实现(2011-07-1811:28:52)首先我们来看，什么是规则？规则形如”如果…那么…(If…Then…)”,前者为条件，后者为结果。关联规则挖掘用于寻找给定数据集中项之间的有趣的关联或相关关系。关联规则揭示了数据项间的未知的依赖关系，根据所挖掘的关联关系，可以从一个数据对象的信息来推断另一个数据对象的信息。例如购物篮分析。牛奶⇒面包[支持度：3%，置信度：40%]支持度3%意味3%顾客同时购买牛奶和面包。置信度40%意味购买牛奶的顾客40%也购买面包。规则的支持度和置信度是两个规则兴趣度度量，它们分别反映发现规则的有用性和确定性。关联规则是有趣的，如果它满足最小支持度阈值和最小置信度阈值。这些阈值可以由用户或领域专家设定。我们先来认识几个相关的定义：定义1：支持度（support）支持度s是事务数据库D中包含AUB的事务百分比，它是概率P（AUB），即support（AB）=P（AUB），它描述了A和B这两个物品集的并集在所有的事务中出现的概率。定义2：置信度（confidence）可信度为事务数据库D中包含A的事务中同时也包含B的百分比，它是概率P（B|A），即confidence（AB）=P（B|A）。定义3：频繁项目集支持度不小于用户给定的最小支持度阈值（minsup）的项集称为频繁项目集（简称频集），或者大项目集。所有的频繁1-项集记为L1。假设有如下表的购买记录。顾客项目1orangejuice,coke2milk,orangejuice,windowcleaner3orangejuice,detergent4orangejuice,detergent,coke5windowcleaner将上表整理一下，得到如下的一个2维表OrangeWinClMilkCokeDetergentOrange41122WinCl12100Milk11100Coke20021Detergent10002上表中横栏和纵栏的数字表示同时购买这两种商品的交易条数。如购买有Orange的交易数为4，而同时购买Orange和Coke的交易数为2。置信度表示了这条规则有多大程度上值得可信。设条件的项的集合为A,结果的集合为B。置信度计算在A中，同时也含有B的概率。即Confidence(A==B)=P(B|A)。例如计算如果2Orange则Coke的置信度。由于在含有Orange的4条交易中，仅有2条交易含有Coke.其置信度为0.5。支持度计算在所有的交易集中，既有A又有B的概率。例如在5条记录中，既有Orange又有Coke的记录有2条。则此条规则的支持度为2/5=0.4。现在这条规则可表述为，如果一个顾客购买了Orange,则有50%的可能购买Coke。而这样的情况（即买了Orange会再买Coke）会有40%的可能发生。再来考虑下述情况。项支持度A0.45B0.42C0.4AandB0.25AandC0.2BandC0.15A,B，andC0.05可得到下述规则规则置信度IfBandCthenA0.05/0.15*100%=33.33%IfAandCthenB0.05/0.20*100%=25%IfAandBthenC0.05/0.25*100%=20%上述的三条规则，哪一条规则有用呢？对于规则IfBandCthenA，同时购买B和C的人中，有33.33%会购买A。而单项A的支持度有0.45，也就是说在所有交易中，会有45%的人购买A.看来使用这条规则来进行推荐，还不如不推荐，随机对顾客进荐好了。为此引入另外一个量，即提升度(Lift)，以度量此规则是否可用。描述的是相对于不用规则，使用规则可以提高多少。有用的规则的提升度大于1。计算方式为Lift(A==B)=Confidence(A==B)/Support(B)=Support(A==B)/(Support(A)*Support(B))。在上例中，Lift(IfBandCTheA)=0.05/(0.15*0.45)=0.74。而Lift(IfAthenB)=0.25/(0.45*0.42)=1.32。也就是说对买了A的人进行推荐B,购买概率是随机推荐B的1.32倍。如何产生规则呢。可以分两步走。首先找出频繁集(frequentitemset)。所谓频繁集指满足最小支持度或置信度的集合。其次从频繁集中找出强规则(strongrules)。强规则指既满足最小支持度又满足最小置信度的规则。我们来看如何产生频繁集。这其中有一个定理。即频繁集的子集也一定是频繁集。比如，如果{A,B,C}是一个3项的频繁集，则其子集{A,B},{B,C},{A,C}也一定是2项的频繁集。为方便，可以把含有k项的集合称之为k-itemsets.下面以迭代的方式找出频繁集。首先找出1-itemsets的频繁集，然后使用这个1-itemsets，进行组合，找出2-itemsets的频繁集。如此下去，直到不再满足最小支持度或置信度的条件为3止。这其中重要的两步骤分别是连接(join)和剪枝(prune).即从(k-1)-itemsets中的项进行组合，产生备选集(Candidateitemsets)。再从备选集中，将不符合最小支持度或置信度的项删去。例如Frequent2-itemsetsCandidate3-itemsetsFrqquent3-itemsetsI1,I2==I1,I2,I4==I1,I2,I4I1,I4I2,I3,I4I2,I3I2,I4下面我们再来看一个详细的例子。设最小支持度为2，以Ck表示k-itemsets备选集,以Lk表示k-itemsets频繁集。IDItemsItemsetSup.countItemsetItemset100I1,I2,I5I16I1I1,I2200I2,I4==C1:I27==L1:I2==C2I1,I3300I2,I3I36I3I1,I4400I1,I2,I4I42I4I1,I5500I1,I3I52I5I2,I3600I2,I3I2,I4700I1,I3I2,I5800I1,I2,I3,I5I3,I4900I1,I2,I3I3,I5I4,I5对C2进行扫描，计算支持度。ItemsetSup.countItemsetItemsetSup.countItemsetI1,I24==L2:I1,I2==C3I1,I2,I32==L3:I1,I2,I3I1,I34I1,I3I1,I2,I52I1,I2,I5I1,I41I1,I5I1,I52I2,I3I2,I34I2,I4I2,I42I2,I5I2,I52I3,I40I3,I51I4,I50对于频繁集中的每一项k-itemset,可以产生非空子集，对每一个子集，可以得到满足最小置信度的规则了。例如考虑{I1,I2,I5}。其子集有{I1,I2},{I1,I5},{I2,I5},{I1},{I2},{I5}。可以4产生规则，{I1,I2}{I5}(50%),{I1,I5}{I2}(100%),{I2,I5}{I1}(100%),{I1}{I2,I5}(33%),{I2}{I1,I5}(29%),{I5}{I1,I2}(100%)。也不是每个数据集都有产生强规则。例如Thinkpadnotebook和Canonprinter一起可能很难产生有效规则。因为恰好一起买这两个牌子的产品的顾客太少。但不妨将Thinkpadnotebook放到Notebook这一层次上考虑，而Canonprinter放到printer这一去层次上考虑。这样的话，一起买notebook和printer的顾客就较多了。也即Multilevelassociationrules。自1994年由Agrawal等人提出的关联规则挖掘Apriori的算法从其产生到现在，对关联规则挖掘方面的研究有着很大的影响。Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。算法基于这样的事实：算法使用频繁项集性质的先验知识。Apriori使用一种称作逐层搜索的迭代方法，k-项集用于探索（k+1）-项集。首先，找出频繁1-项集的集合。该集合记作L1。L1用于找频繁2-项集的集合L2，而L2用于找L3，如此下去，直到不能找到频繁k-项集。找每个Lk需要一次数据库扫描。为提高频繁项集逐层产生的效率，一种称作Apriori性质的重要性质用于压缩搜索空间。为了提高频繁项目集逐层产生的效率，Apriori算法利用了两个重要的性质用于压缩搜索空间：（l）若X是频繁项集，则x的所有子集都是频繁项集。（2）若x是非频繁项集，则X的所有超集都是非频繁项集。算法：Apriori算法，使用逐层迭代找出频繁项集。输入：事务数据库D；最小支持度阈值min_sup。输出：D中的频繁项集L。1）L1=find_frequent_1_itemsets（D）；2）for（k=2；Lk-1≠；k++）{3）Ck=aproiri_gen（Lk-1，min_sup）；4）foreachtransactiontD{//scanDforcount5）Ct=subset（Ck，t）；//getsubsetsoftthatarecandidates6）foreachcandidatecCt7）c.count++；8）}9）Lk={cCk|c.count≥min_sup}10）}11）returnL=∪kLk；现举例说明：如表1所示为事务数据库D，设最小支持度为20%，挖掘频繁项集的具体过程如表１所示。表1事务数据库D图１所示为Apriori算法挖掘频繁集的过程，其中最小支持度为20%。图1Apriori算法的执行流程5第一步，经过算法的第一次迭代，对事务数据库进行一次扫描，计算出D中所包含的每个项目出现的次数，生成候选1-项集的集合C1。第二步，根据设定的最小支持度，从C1中确定频繁1-项集L1。第三步，由L1产生候选2-项集C2，然后扫描事务数据库对C2中的项集进行计数。第四步，根据最小支持度，从候选集C2中确定频繁集L2。第五步，由频繁2-项集L2生成候选3-项集C3，生成的候选3-项集的集合C3={{1，2，3}，{1，3，5}，{2，3，5}}，根据Apriori的性质剪枝：所有的频繁项集的子集都是频繁的，项集{1，2，3}的子集{1，2}不包含在频繁2-项集L2中，故删除{1，2，3}。项集{1，3，5}的子集{1，5}也不包含在频繁2-项集L2中，故删除{1，3，5}，项集{2，3，5}的所有子集都是L2的元素，故保留。Apriori算法的效率分析：（1）Apriori性质能显著减少候选集的数目。事务数据库TDB总共有4个项目，因此可能的2-项集有=6个。正如本例所示，利用Apriori性质，我们只需要检查4个候选2-项集的支持度。Apriori算法在2项集这个层次上剪枝率达33.3%。随着候选集的长度逐渐增大，可能的组合数目也急剧增大，因此Apriori算法的剪枝效率也越来越高。（2）尽管Apriori能对大量候选集剪枝，但是在大型的事务数据库中，仍然可能有大量的候选集需要处理，并且这种操作相当耗时。例如，如果事务数据库包含106个项目，并且只有1%（即104）的项目是频繁的，Apriori需要产生超过107个候选2-项集，扫描数据库计算它们的支持度，生成L2以产生候选3-项集。（3）反复地扫描数据库、计算候选集的支持度，再生成新的长度加1的候选集，Apriori算法是冗长乏味的，尤其是当存在长模式的时候。Apriori是一种产生候选集，然后检测其支持度的算法。为挖掘频集X={x1，x2…，x100}.Apriori需要扫描数据库100次。针对Apriori算法存在的缺点，人们对Apriori算法进行了多方面的改进，希望能够找出一个高效、可靠的挖掘频繁项集的算法。这些算法大多是以Apriori为核心，或是其变体，或是其扩展。如增量更新算法、并行算法等下面是使用Java语言实现的Apriori算法，实现