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

1、关联规则算法Apriori的学习与实现 (2011-07-18 11:28:52)首先我们来看，什么是规则？规则形如”如果那么(IfThen)”,前者为条件，后者为结果。关联规则挖掘用于寻找给定数据集中项之间的有趣的关联或相关关系。关联规则揭示了数据项间的未知的依赖关系，根据所挖掘的关联关系，可以从一个数据对象的信息来推断另一个数据对象的信息。例如购物篮分析。牛奶 面包 支持度：3%，置信度：40%支持度3%意味3%顾客同时购买牛奶和面包。置信度40%意味购买牛奶的顾客40%也购买面包。规则的支持度和置信度是两个规则兴趣度度量，它们分别反映发现规则的有用性和确定性。关联规则是有趣的，如果它满足

2、最小支持度阈值和最小置信度阈值。这些阈值可以由用户或领域专家设定。我们先来认识几个相关的定义：定义1： 支持度（support）支持度s是事务数据库D中包含A U B的事务百分比，它是概率P（A U B），即support（A B）=P（A U B），它描述了A和B这两个物品集的并集在所有的事务中出现的概率。定义2： 置信度（confidence）可信度为事务数据库D中包含A的事务中同时也包含B的百分比，它是概率P（B|A），即confidence（A B）=P（B|A）。定义3： 频繁项目集支持度不小于用户给定的最小支持度阈值（minsup）的项集称为频繁项目集（简称频集），或者大项目集。所

3、有的频繁1-项集记为L1。假设有如下表的购买记录。顾客项目1orange juice, coke2milk, orange juice, window cleaner3orange juice, detergent4orange juice, detergent, coke5window cleaner将上表整理一下，得到如下的一个2维表OrangeWin ClMilkCokeDetergentOrange41122WinCl12100Milk11100Coke20021Detergent10002上表中横栏和纵栏的数字表示同时购买这两种商品的交易条数。如购买有Orange的交易数为4，而同时

4、购买Orange和Coke的交易数为2。置信度表示了这条规则有多大程度上值得可信。设条件的项的集合为A,结果的集合为B。置信度计算在A中，同时也含有B的概率。即Confidence(A=B)=P(B|A)。例如计算如果Orange则Coke的置信度。由于在含有Orange的4条交易中，仅有2条交易含有Coke.其置信度为0.5。支持度计算在所有的交易集中，既有A又有B的概率。例如在5条记录中，既有Orange又有Coke的记录有2条。则此条规则的支持度为2/5=0.4。现在这条规则可表述为，如果一个顾客购买了Orange,则有50%的可能购买Coke。而这样的情况（即买了Orange会再买Co

5、ke）会有40%的可能发生。再来考虑下述情况。项支持度A0.45B0.42C0.4A and B0.25A and C0.2B and C0.15A,B，and C0.05可得到下述规则规则置信度If B and C then A0.05/0.15*100%=33.33%If A and C then B0.05/0.20*100%=25%If A and B then C0.05/0.25*100%=20%上述的三条规则，哪一条规则有用呢？对于规则If B and C then A，同时购买B和C的人中，有33.33%会购买A。而单项A的支持度有0.45，也就是说在所有交易中，会有45%的人

6、购买A.看来使用这条规则来进行推荐，还不如不推荐，随机对顾客进荐好了。为此引入另外一个量，即提升度(Lift)，以度量此规则是否可用。描述的是相对于不用规则，使用规则可以提高多少。有用的规则的提升度大于1。计算方式为Lift(A=B)=Confidence(A=B)/Support(B)=Support(A=B)/(Support(A)*Support(B)。在上例中，Lift(If B and C The A)=0.05/(0.15*0.45)=0.74。而Lift(If A then B)=0.25/(0.45*0.42)=1.32。也就是说对买了A的人进行推荐B,购买概率是随机推荐B的1

7、.32倍。如何产生规则呢。可以分两步走。首先找出频繁集(frequent itemset)。所谓频繁集指满足最小支持度或置信度的集合。其次从频繁集中找出强规则(strong rules)。强规则指既满足最小支持度又满足最小置信度的规则。我们来看如何产生频繁集。这其中有一个定理。即频繁集的子集也一定是频繁集。比如，如果A,B,C是一个3项的频繁集，则其子集A,B,B,C,A,C也一定是2项的频繁集。为方便，可以把含有k项的集合称之为k-itemsets.下面以迭代的方式找出频繁集。首先找出1-itemsets的频繁集，然后使用这个1-itemsets，进行组合，找出2-itemsets的频繁集。

8、如此下去，直到不再满足最小支持度或置信度的条件为止。这其中重要的两步骤分别是连接(join)和剪枝(prune).即从(k-1)-itemsets中的项进行组合，产生备选集(Candidate itemsets)。再从备选集中，将不符合最小支持度或置信度的项删去。例如Frequent 2-itemsetsCandidate 3-itemsetsFrqquent 3-itemsetsI1,I2=I1,I2,I4=I1,I2,I4I1,I4I2,I3,I4I2,I3I2,I4下面我们再来看一个详细的例子。设最小支持度为2，以Ck表示k-itemsets备选集,以Lk表示k-itemsets频繁集。

9、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

10、=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。可以产生规则，I1,I2=I5 (50%), I1,I5=I2 (100%), I2,I5=I1 (100%),I1=I2,I5 (33%), I2=I1,I5 (29%), I5=

11、I1,I2 (100%)。也不是每个数据集都有产生强规则。例如Thinkpad notebook 和Canon printer一起可能很难产生有效规则。因为恰好一起买这两个牌子的产品的顾客太少。但不妨将Thinkpad notebook放到Notebook这一层次上考虑，而Canon printer放到printer这一去层次上考虑。这样的话，一起买notebook和printer的顾客就较多了。也即Multilevel association rules。自1994年由Agrawal等人提出的关联规则挖掘Apriori的算法从其产生到现在，对关联规则挖掘方面的研究有着很大的影响。Aprior

12、i 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。算法基于这样的事实：算法使用频繁项集性质的先验知识。Apriori 使用一种称作逐层搜索的迭代方法，k-项集用于探索（k+1）-项集。首先，找出频繁1-项集的集合。该集合记作L1。L1用于找频繁2-项集的集合L2，而L2用于找L3，如此下去，直到不能找到频繁k-项集。找每个Lk需要一次数据库扫描。为提高频繁项集逐层产生的效率，一种称作Apriori 性质的重要性质用于压缩搜索空间。为了提高频繁项目集逐层产生的效率，Apriori算法利用了两个重要的性质用于压缩搜索空间：（l）若X是频繁项集，则x的所有子集都是频繁项集。（2）若x是非频繁项

13、集，则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） for each transaction t D /scan D for count5） Ct = subset（Ck，t）； /get subsets of t that are candidates6） for each candid

14、ate c Ct7） c.count+；8） 9） Lk=c Ck | c.count min_sup10） 11） return L = kLk；现举例说明：如表1所示为事务数据库D，设最小支持度为20%，挖掘频繁项集的具体过程如表所示。表1事务数据库D图所示为Apriori算法挖掘频繁集的过程，其中最小支持度为20%。图1Apriori算法的执行流程第一步，经过算法的第一次迭代，对事务数据库进行一次扫描，计算出D中所包含的每个项目出现的次数，生成候选1-项集的集合C1。第二步，根据设定的最小支持度，从C1中确定频繁1-项集L1。第三步，由L1产生候选2-项集C2，然后扫描事务数据库对C2中

15、的项集进行计数。第四步，根据最小支持度，从候选集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个。正如本例所示，利用A

16、priori性质，我们只需要检查4个候选2-项集的支持度。Apriori算法在2项集这个层次上剪枝率达33.3%。随着候选集的长度逐渐增大，可能的组合数目也急剧增大，因此Apriori算法的剪枝效率也越来越高。（2）尽管Apriori能对大量候选集剪枝，但是在大型的事务数据库中，仍然可能有大量的候选集需要处理，并且这种操作相当耗时。例如，如果事务数据库包含106个项目，并且只有1%（即104）的项目是频繁的，Apriori需要产生超过107个候选2-项集，扫描数据库计算它们的支持度，生成L2以产生候选3-项集。（3）反复地扫描数据库、计算候选集的支持度，再生成新的长度加1的候选集，Aprior

17、i算法是冗长乏味的，尤其是当存在长模式的时候。Apriori是一种产生候选集，然后检测其支持度的算法。为挖掘频集X =x1，x2，x100 . Apriori需要扫描数据库100次。针对Apriori算法存在的缺点，人们对Apriori算法进行了多方面的改进，希望能够找出一个高效、可靠的挖掘频繁项集的算法。这些算法大多是以 Apriori 为核心，或是其变体，或是其扩展。如增量更新算法、并行算法等下面是使用Java语言实现的Apriori算法，实现了AprioriAlgorithm 类，包含了频繁项集的挖掘过程和频繁关联规则的挖掘过程。另外，有一个辅助类ProperSubsetCombinat

18、ion用于计算一个频繁项集的真子集，采用组合原理，基于数值编码原理实现的组合求解集合的真子集。算法实现（一）核心类Apriori算法的核心实现类为AprioriAlgorithm，实现的Java代码如下所示：package org.shirdrn.datamining.association;import java.util.HashMap;import java.util.HashSet;import java.util.Iterator;import java.util.Map;import java.util.Set;import java.util.TreeMap;public cla

19、ss AprioriAlgorithm private MapInteger, Set txDatabase; / 事务数据库private Float minSup; / 最小支持度private Float minConf; / 最小置信度private Integer txDatabaseCount; / 事务数据库中的事务数private MapInteger, SetSet freqItemSet; / 频繁项集集合private MapSet, SetSet assiciationRules; / 频繁关联规则集合public AprioriAlgorithm(MapInteger

20、, Set txDatabase,Float minSup,Float minConf) this.txDatabase = txDatabase;this.minSup = minSup;this.minConf = minConf;this.txDatabaseCount = this.txDatabase.size();freqItemSet = new TreeMapInteger, SetSet();assiciationRules = new HashMapSet, SetSet();public MapSet, Float getFreq1ItemSet() MapSet, Fl

21、oat freq1ItemSetMap = new HashMapSet, Float();MapSet, Integer candFreq1ItemSet = this.getCandFreq1ItemSet();IteratorMap.EntrySet, Integer it = candFreq1ItemSet.entrySet().iterator();while(it.hasNext() Map.EntrySet, Integer entry = it.next();/ 计算支持度Float supported = new Float(entry.getValue().toStrin

22、g()/new Float(txDatabaseCount);if(supported=minSup) freq1ItemSetMap.put(entry.getKey(), supported);return freq1ItemSetMap;public MapSet, Integer getCandFreq1ItemSet() MapSet, Integer candFreq1ItemSetMap = new HashMapSet, Integer();IteratorMap.EntryInteger, Set it = txDatabase.entrySet().iterator();/

23、 统计支持数，生成候选频繁1-项集while(it.hasNext() Map.EntryInteger, Set entry = it.next();Set itemSet = entry.getValue();for(String item : itemSet) Set key = new HashSet();key.add(item.trim();if(!candFreq1ItemSetMap.containsKey(key) Integer value = 1;candFreq1ItemSetMap.put(key, value);else Integer value = 1+cand

24、Freq1ItemSetMap.get(key);candFreq1ItemSetMap.put(key, value);return candFreq1ItemSetMap;public SetSet aprioriGen(int m, SetSet freqMItemSet) SetSet candFreqKItemSet = new HashSetSet();IteratorSet it = freqMItemSet.iterator();Set originalItemSet = null;while(it.hasNext() originalItemSet = it.next();I

25、teratorSet itr = this.getIterator(originalItemSet, freqMItemSet);while(itr.hasNext() Set identicalSet = new HashSet(); / 两个项集相同元素的集合(集合的交运算)identicalSet.addAll(originalItemSet);Set set = itr.next();identicalSet.retainAll(set); / identicalSet中剩下的元素是identicalSet与set集合中公有的元素if(identicalSet.size() = m-1

26、) / (k-1)-项集中k-2个相同Set differentSet = new HashSet(); / 两个项集不同元素的集合(集合的差运算)differentSet.addAll(originalItemSet);differentSet.removeAll(set); / 因为有k-2个相同，则differentSet中一定剩下一个元素，即differentSet大小为1differentSet.addAll(set); / 构造候选k-项集的一个元素(set大小为k-1,differentSet大小为k)candFreqKItemSet.add(differentSet); / 加

27、入候选k-项集集合return candFreqKItemSet;private IteratorSet getIterator(Set itemSet, SetSet freqKItemSet) IteratorSet it = freqKItemSet.iterator();while(it.hasNext() if(itemSet.equals(it.next() break;return it;public MapSet, Float getFreqKItemSet(int k, SetSet freqMItemSet) MapSet, Integer candFreqKItemSet

28、Map = new HashMapSet, Integer();/ 调用aprioriGen方法，得到候选频繁k-项集SetSet candFreqKItemSet = this.aprioriGen(k-1, freqMItemSet);/ 扫描事务数据库IteratorMap.EntryInteger, Set it = txDatabase.entrySet().iterator();/ 统计支持数while(it.hasNext() Map.EntryInteger, Set entry = it.next();IteratorSet kit = candFreqKItemSet.it

29、erator();while(kit.hasNext() Set kSet = kit.next();Set set = new HashSet();set.addAll(kSet);set.removeAll(entry.getValue(); / 候选频繁k-项集与事务数据库中元素做差元算if(set.isEmpty() / 如果拷贝set为空，支持数加1if(candFreqKItemSetMap.get(kSet) = null) Integer value = 1;candFreqKItemSetMap.put(kSet, value);else Integer value = 1+

30、candFreqKItemSetMap.get(kSet);candFreqKItemSetMap.put(kSet, value);/ 计算支持度，生成频繁k-项集，并返回return support(candFreqKItemSetMap);public MapSet, Float support(MapSet, Integer candFreqKItemSetMap) MapSet, Float freqKItemSetMap = new HashMapSet, Float();IteratorMap.EntrySet, Integer it = candFreqKItemSetMap.

31、entrySet().iterator();while(it.hasNext() Map.EntrySet, Integer entry = it.next();/ 计算支持度Float supportRate = new Float(entry.getValue().toString()/new Float(txDatabaseCount);if(supportRateminSup) / 如果不满足最小支持度，删除it.remove();else freqKItemSetMap.put(entry.getKey(), supportRate);return freqKItemSetMap;p

32、ublic void mineFreqItemSet() / 计算频繁1-项集SetSet freqKItemSet = this.getFreq1ItemSet().keySet();freqItemSet.put(1, freqKItemSet);/ 计算频繁k-项集(k1)int k = 2;while(true) MapSet, Float freqKItemSetMap = this.getFreqKItemSet(k, freqKItemSet);if(!freqKItemSetMap.isEmpty() this.freqItemSet.put(k, freqKItemSetMa

33、p.keySet();freqKItemSet = freqKItemSetMap.keySet();else break;k+;public void mineAssociationRules() freqItemSet.remove(1); / 删除频繁1-项集IteratorMap.EntryInteger, SetSet it = freqItemSet.entrySet().iterator();while(it.hasNext() Map.EntryInteger, SetSet entry = it.next();for(Set itemSet : entry.getValue(

34、) / 对每个频繁项集进行关联规则的挖掘mine(itemSet);public void mine(Set itemSet) int n = itemSet.size()/2; / 根据集合的对称性，只需要得到一半的真子集for(int i=1; i=n; i+) / 得到频繁项集元素itemSet的作为条件的真子集集合SetSet properSubset = ProperSubsetCombination.getProperSubset(i, itemSet);/ 对条件的真子集集合中的每个条件项集，获取到对应的结论项集，从而进一步挖掘频繁关联规则for(Set conditionSet

35、 : properSubset) Set conclusionSet = new HashSet();conclusionSet.addAll(itemSet);conclusionSet.removeAll(conditionSet); / 删除条件中存在的频繁项confide(conditionSet, conclusionSet); / 调用计算置信度的方法，并且挖掘出频繁关联规则public void confide(Set conditionSet, Set conclusionSet) / 扫描事务数据库IteratorMap.EntryInteger, Set it = txDa

36、tabase.entrySet().iterator();/ 统计关联规则支持计数int conditionToConclusionCnt= 0; / 关联规则(条件项集推出结论项集)计数int conclusionToConditionCnt= 0; / 关联规则(结论项集推出条件项集)计数int supCnt = 0; / 关联规则支持计数while(it.hasNext() Map.EntryInteger, Set entry = it.next();Set txSet = entry.getValue();Set set1 = new HashSet();Set set2 = new

37、 HashSet();set1.addAll(conditionSet);set1.removeAll(txSet); / 集合差运算：set-txSetif(set1.isEmpty() / 如果set为空，说明事务数据库中包含条件频繁项conditionSet/ 计数conditionToConclusionCnt+;set2.addAll(conclusionSet);set2.removeAll(txSet); / 集合差运算：set-txSetif(set2.isEmpty() / 如果set为空，说明事务数据库中包含结论频繁项conclusionSet/ 计数conclusionT

38、oConditionCnt+;if(set1.isEmpty() & set2.isEmpty() supCnt+;/ 计算置信度Float conditionToConclusionConf = new Float(supCnt)/new Float(conditionToConclusionCnt);if(conditionToConclusionConf=minConf) if(assiciationRules.get(conditionSet) = null) / 如果不存在以该条件频繁项集为条件的关联规则SetSet conclusionSetSet = new HashSetSet

39、();conclusionSetSet.add(conclusionSet);assiciationRules.put(conditionSet, conclusionSetSet);else assiciationRules.get(conditionSet).add(conclusionSet);Float conclusionToConditionConf = new Float(supCnt)/new Float(conclusionToConditionCnt);if(conclusionToConditionConf=minConf) if(assiciationRules.get

40、(conclusionSet) = null) / 如果不存在以该结论频繁项集为条件的关联规则SetSet conclusionSetSet = new HashSetSet();conclusionSetSet.add(conditionSet);assiciationRules.put(conclusionSet, conclusionSetSet);else assiciationRules.get(conclusionSet).add(conditionSet);public MapInteger, SetSet getFreqItemSet() return freqItemSet;

41、public MapSet, SetSet getAssiciationRules() return assiciationRules;（二）辅助类ProperSubsetCombination类是一个辅助类，在挖掘频繁关联规则的过程中，用于生成一个频繁项集元素的非空真子集，实现代码如下：package org.shirdrn.datamining.association;import java.util.BitSet;import java.util.HashSet;import java.util.Set;public class ProperSubsetCombination priva

42、te static String array;private static BitSet startBitSet; / 比特集合起始状态private static BitSet endBitSet; / 比特集合终止状态，用来控制循环private static SetSet properSubset; / 真子集集合public static SetSet getProperSubset(int n, Set itemSet) String array = new StringitemSet.size();ProperSubsetCombination.array = itemSet.to

43、Array(array);properSubset = new HashSetSet();startBitSet = new BitSet();endBitSet = new BitSet();/ 初始化startBitSet，左侧占满1for (int i=0; i=array.length-n; i-) endBitSet.set(i, true);/ 根据起始startBitSet，将一个组合加入到真子集集合中get(startBitSet);while(!startBitSet.equals(endBitSet) int zeroCount = 0; / 统计遇到10后，左边0的个数i

44、nt oneCount = 0; / 统计遇到10后，左边1的个数int pos = 0; / 记录当前遇到10的索引位置/ 遍历startBitSet来确定10出现的位置for (int i=0; i1 & counter0) pos-;endIndex = pos;for (int i=0; i0) endIndex = pos;get(startBitSet);return properSubset;private static void get(BitSet bitSet) Set set = new HashSet();for(int i=0; iarray.length; i+)

45、if(bitSet.get(i) set.add(arrayi);properSubset.add(set);测试用例对上述Apriori算法的实现进行了简单的测试，测试用例如下所示：package org.shirdrn.datamining.association;import java.util.HashMap;import java.util.Map;import java.util.Set;import java.util.TreeSet;import org.shirdrn.datamining.association.AprioriAlgorithm;import junit.f

46、ramework.TestCase;public class TestAprioriAlgorithm extends TestCase private AprioriAlgorithm apriori;private MapInteger, Set txDatabase;private Float minSup = new Float(0.50);private Float minConf = new Float(0.70);Overrideprotected void setUp() throws Exception create(); / 构造事务数据库apriori = new AprioriAlgorithm(txDatabase, minSup, minConf);public void create() txDatabase = new HashMapInteger, Set();Set set1 = new TreeSet();set1.add(A);set1.add(B);set1.add(C);set1.add(E);txDatabase.put