關(guān)聯(lián)規(guī)則算法Apriori的學(xué)習(xí)與實(shí)現(xiàn)

1、關(guān)聯(lián)規(guī)則算法Apriori的學(xué)習(xí)與實(shí)現(xiàn) (2011-07-18 11:28:52)首先我們來(lái)看，什么是規(guī)則？規(guī)則形如”如果那么(IfThen)”,前者為條件，后者為結(jié)果。關(guān)聯(lián)規(guī)則挖掘用于尋找給定數(shù)據(jù)集中項(xiàng)之間的有趣的關(guān)聯(lián)或相關(guān)關(guān)系。關(guān)聯(lián)規(guī)則揭示了數(shù)據(jù)項(xiàng)間的未知的依賴關(guān)系，根據(jù)所挖掘的關(guān)聯(lián)關(guān)系，可以從一個(gè)數(shù)據(jù)對(duì)象的信息來(lái)推斷另一個(gè)數(shù)據(jù)對(duì)象的信息。例如購(gòu)物籃分析。牛奶 面包 支持度：3%，置信度：40%支持度3%意味3%顧客同時(shí)購(gòu)買(mǎi)牛奶和面包。置信度40%意味購(gòu)買(mǎi)牛奶的顧客40%也購(gòu)買(mǎi)面包。規(guī)則的支持度和置信度是兩個(gè)規(guī)則興趣度度量，它們分別反映發(fā)現(xiàn)規(guī)則的有用性和確定性。關(guān)聯(lián)規(guī)則是有趣的，如果它滿足

2、最小支持度閾值和最小置信度閾值。這些閾值可以由用戶或領(lǐng)域?qū)＜以O(shè)定。我們先來(lái)認(rèn)識(shí)幾個(gè)相關(guān)的定義：定義1： 支持度（support）支持度s是事務(wù)數(shù)據(jù)庫(kù)D中包含A U B的事務(wù)百分比，它是概率P（A U B），即support（A B）=P（A U B），它描述了A和B這兩個(gè)物品集的并集在所有的事務(wù)中出現(xiàn)的概率。定義2： 置信度（confidence）可信度為事務(wù)數(shù)據(jù)庫(kù)D中包含A的事務(wù)中同時(shí)也包含B的百分比，它是概率P（B|A），即confidence（A B）=P（B|A）。定義3： 頻繁項(xiàng)目集支持度不小于用戶給定的最小支持度閾值（minsup）的項(xiàng)集稱為頻繁項(xiàng)目集（簡(jiǎn)稱頻集），或者大項(xiàng)目集。所

3、有的頻繁1-項(xiàng)集記為L(zhǎng)1。假設(shè)有如下表的購(gòu)買(mǎi)記錄。顧客項(xiàng)目1orange juice, coke2milk, orange juice, window cleaner3orange juice, detergent4orange juice, detergent, coke5window cleaner將上表整理一下，得到如下的一個(gè)2維表OrangeWin ClMilkCokeDetergentOrange41122WinCl12100Milk11100Coke20021Detergent10002上表中橫欄和縱欄的數(shù)字表示同時(shí)購(gòu)買(mǎi)這兩種商品的交易條數(shù)。如購(gòu)買(mǎi)有Orange的交易數(shù)為4，而同時(shí)

4、購(gòu)買(mǎi)Orange和Coke的交易數(shù)為2。置信度表示了這條規(guī)則有多大程度上值得可信。設(shè)條件的項(xiàng)的集合為A,結(jié)果的集合為B。置信度計(jì)算在A中，同時(shí)也含有B的概率。即Confidence(A=B)=P(B|A)。例如計(jì)算如果Orange則Coke的置信度。由于在含有Orange的4條交易中，僅有2條交易含有Coke.其置信度為0.5。支持度計(jì)算在所有的交易集中，既有A又有B的概率。例如在5條記錄中，既有Orange又有Coke的記錄有2條。則此條規(guī)則的支持度為2/5=0.4。現(xiàn)在這條規(guī)則可表述為，如果一個(gè)顧客購(gòu)買(mǎi)了Orange,則有50%的可能購(gòu)買(mǎi)Coke。而這樣的情況（即買(mǎi)了Orange會(huì)再買(mǎi)Co

5、ke）會(huì)有40%的可能發(fā)生。再來(lái)考慮下述情況。項(xiàng)支持度A0.45B0.42C0.4A and B0.25A and C0.2B and C0.15A,B，and C0.05可得到下述規(guī)則規(guī)則置信度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%上述的三條規(guī)則，哪一條規(guī)則有用呢？對(duì)于規(guī)則If B and C then A，同時(shí)購(gòu)買(mǎi)B和C的人中，有33.33%會(huì)購(gòu)買(mǎi)A。而單項(xiàng)A的支持度有0.45，也就是說(shuō)在所有交易中，會(huì)有45%的人

6、購(gòu)買(mǎi)A.看來(lái)使用這條規(guī)則來(lái)進(jìn)行推薦，還不如不推薦，隨機(jī)對(duì)顧客進(jìn)薦好了。為此引入另外一個(gè)量，即提升度(Lift)，以度量此規(guī)則是否可用。描述的是相對(duì)于不用規(guī)則，使用規(guī)則可以提高多少。有用的規(guī)則的提升度大于1。計(jì)算方式為L(zhǎng)ift(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。也就是說(shuō)對(duì)買(mǎi)了A的人進(jìn)行推薦B,購(gòu)買(mǎi)概率是隨機(jī)推薦B的1

7、.32倍。如何產(chǎn)生規(guī)則呢。可以分兩步走。首先找出頻繁集(frequent itemset)。所謂頻繁集指滿足最小支持度或置信度的集合。其次從頻繁集中找出強(qiáng)規(guī)則(strong rules)。強(qiáng)規(guī)則指既滿足最小支持度又滿足最小置信度的規(guī)則。我們來(lái)看如何產(chǎn)生頻繁集。這其中有一個(gè)定理。即頻繁集的子集也一定是頻繁集。比如，如果A,B,C是一個(gè)3項(xiàng)的頻繁集，則其子集A,B,B,C,A,C也一定是2項(xiàng)的頻繁集。為方便，可以把含有k項(xiàng)的集合稱之為k-itemsets.下面以迭代的方式找出頻繁集。首先找出1-itemsets的頻繁集，然后使用這個(gè)1-itemsets，進(jìn)行組合，找出2-itemsets的頻繁集。

8、如此下去，直到不再滿足最小支持度或置信度的條件為止。這其中重要的兩步驟分別是連接(join)和剪枝(prune).即從(k-1)-itemsets中的項(xiàng)進(jìn)行組合，產(chǎn)生備選集(Candidate itemsets)。再?gòu)膫溥x集中，將不符合最小支持度或置信度的項(xiàng)刪去。例如Frequent 2-itemsetsCandidate 3-itemsetsFrqquent 3-itemsetsI1,I2=I1,I2,I4=I1,I2,I4I1,I4I2,I3,I4I2,I3I2,I4下面我們?cè)賮?lái)看一個(gè)詳細(xì)的例子。設(shè)最小支持度為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對(duì)C2進(jìn)行掃描，計(jì)算支持度。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對(duì)于頻繁集中的每一項(xiàng)k-itemset,可以產(chǎn)生非空子集，對(duì)每一個(gè)子集，可以得到滿足最小置信度的規(guī)則了。例如考慮I1,I2,I5。其子集有I1,I2, I1,I5, I2,I5, I1, I2, I5?？梢援a(chǎn)生規(guī)則，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%)。也不是每個(gè)數(shù)據(jù)集都有產(chǎn)生強(qiáng)規(guī)則。例如Thinkpad notebook 和Canon printer一起可能很難產(chǎn)生有效規(guī)則。因?yàn)榍『靡黄鹳I(mǎi)這兩個(gè)牌子的產(chǎn)品的顧客太少。但不妨將Thinkpad notebook放到Notebook這一層次上考慮，而Canon printer放到printer這一去層次上考慮。這樣的話，一起買(mǎi)notebook和printer的顧客就較多了。也即Multilevel association rules。自1994年由Agrawal等人提出的關(guān)聯(lián)規(guī)則挖掘Apriori的算法從其產(chǎn)生到現(xiàn)在，對(duì)關(guān)聯(lián)規(guī)則挖掘方面的研究有著很大的影響。Aprior

12、i 算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法。算法基于這樣的事實(shí)：算法使用頻繁項(xiàng)集性質(zhì)的先驗(yàn)知識(shí)。Apriori 使用一種稱作逐層搜索的迭代方法，k-項(xiàng)集用于探索（k+1）-項(xiàng)集。首先，找出頻繁1-項(xiàng)集的集合。該集合記作L1。L1用于找頻繁2-項(xiàng)集的集合L2，而L2用于找L3，如此下去，直到不能找到頻繁k-項(xiàng)集。找每個(gè)Lk需要一次數(shù)據(jù)庫(kù)掃描。為提高頻繁項(xiàng)集逐層產(chǎn)生的效率，一種稱作Apriori 性質(zhì)的重要性質(zhì)用于壓縮搜索空間。為了提高頻繁項(xiàng)目集逐層產(chǎn)生的效率，Apriori算法利用了兩個(gè)重要的性質(zhì)用于壓縮搜索空間：（l）若X是頻繁項(xiàng)集，則x的所有子集都是頻繁項(xiàng)集。（2）若x是非頻繁項(xiàng)

13、集，則X的所有超集都是非頻繁項(xiàng)集。算法： Apriori算法，使用逐層迭代找出頻繁項(xiàng)集。輸入：事務(wù)數(shù)據(jù)庫(kù)D；最小支持度閾值min_sup。輸出：D 中的頻繁項(xiàng)集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；現(xiàn)舉例說(shuō)明：如表1所示為事務(wù)數(shù)據(jù)庫(kù)D，設(shè)最小支持度為20%，挖掘頻繁項(xiàng)集的具體過(guò)程如表所示。表1事務(wù)數(shù)據(jù)庫(kù)D圖所示為Apriori算法挖掘頻繁集的過(guò)程，其中最小支持度為20%。圖1Apriori算法的執(zhí)行流程第一步，經(jīng)過(guò)算法的第一次迭代，對(duì)事務(wù)數(shù)據(jù)庫(kù)進(jìn)行一次掃描，計(jì)算出D中所包含的每個(gè)項(xiàng)目出現(xiàn)的次數(shù)，生成候選1-項(xiàng)集的集合C1。第二步，根據(jù)設(shè)定的最小支持度，從C1中確定頻繁1-項(xiàng)集L1。第三步，由L1產(chǎn)生候選2-項(xiàng)集C2，然后掃描事務(wù)數(shù)據(jù)庫(kù)對(duì)C2中

15、的項(xiàng)集進(jìn)行計(jì)數(shù)。第四步，根據(jù)最小支持度，從候選集C2中確定頻繁集L2。第五步，由頻繁2-項(xiàng)集L2生成候選3-項(xiàng)集C3，生成的候選3-項(xiàng)集的集合C3=1，2，3，1，3，5，2，3，5，根據(jù)Apriori的性質(zhì)剪枝：所有的頻繁項(xiàng)集的子集都是頻繁的，項(xiàng)集1，2，3的子集1，2不包含在頻繁2-項(xiàng)集L2中，故刪除1，2，3。項(xiàng)集1，3，5的子集1，5也不包含在頻繁2-項(xiàng)集L2中，故刪除1，3，5，項(xiàng)集2，3，5的所有子集都是L2的元素，故保留。Apriori算法的效率分析：（1）Apriori性質(zhì)能顯著減少候選集的數(shù)目。事務(wù)數(shù)據(jù)庫(kù)TDB總共有4個(gè)項(xiàng)目，因此可能的2-項(xiàng)集有 =6個(gè)。正如本例所示，利用A

16、priori性質(zhì)，我們只需要檢查4個(gè)候選2-項(xiàng)集的支持度。Apriori算法在2項(xiàng)集這個(gè)層次上剪枝率達(dá)33.3%。隨著候選集的長(zhǎng)度逐漸增大，可能的組合數(shù)目也急劇增大，因此Apriori算法的剪枝效率也越來(lái)越高。（2）盡管Apriori能對(duì)大量候選集剪枝，但是在大型的事務(wù)數(shù)據(jù)庫(kù)中，仍然可能有大量的候選集需要處理，并且這種操作相當(dāng)耗時(shí)。例如，如果事務(wù)數(shù)據(jù)庫(kù)包含106個(gè)項(xiàng)目，并且只有1%（即104）的項(xiàng)目是頻繁的，Apriori需要產(chǎn)生超過(guò)107個(gè)候選2-項(xiàng)集，掃描數(shù)據(jù)庫(kù)計(jì)算它們的支持度，生成L2以產(chǎn)生候選3-項(xiàng)集。（3）反復(fù)地掃描數(shù)據(jù)庫(kù)、計(jì)算候選集的支持度，再生成新的長(zhǎng)度加1的候選集，Aprior

17、i算法是冗長(zhǎng)乏味的，尤其是當(dāng)存在長(zhǎng)模式的時(shí)候。Apriori是一種產(chǎn)生候選集，然后檢測(cè)其支持度的算法。為挖掘頻集X =x1，x2，x100 . Apriori需要掃描數(shù)據(jù)庫(kù)100次。針對(duì)Apriori算法存在的缺點(diǎn)，人們對(duì)Apriori算法進(jìn)行了多方面的改進(jìn)，希望能夠找出一個(gè)高效、可靠的挖掘頻繁項(xiàng)集的算法。這些算法大多是以 Apriori 為核心，或是其變體，或是其擴(kuò)展。如增量更新算法、并行算法等下面是使用Java語(yǔ)言實(shí)現(xiàn)的Apriori算法，實(shí)現(xiàn)了AprioriAlgorithm 類，包含了頻繁項(xiàng)集的挖掘過(guò)程和頻繁關(guān)聯(lián)規(guī)則的挖掘過(guò)程。另外，有一個(gè)輔助類ProperSubsetCombinat

18、ion用于計(jì)算一個(gè)頻繁項(xiàng)集的真子集，采用組合原理，基于數(shù)值編碼原理實(shí)現(xiàn)的組合求解集合的真子集。算法實(shí)現(xiàn)（一）核心類Apriori算法的核心實(shí)現(xiàn)類為AprioriAlgorithm，實(shí)現(xiàn)的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; / 事務(wù)數(shù)據(jù)庫(kù)private Float minSup; / 最小支持度private Float minConf; / 最小置信度private Integer txDatabaseCount; / 事務(wù)數(shù)據(jù)庫(kù)中的事務(wù)數(shù)private MapInteger, SetSet freqItemSet; / 頻繁項(xiàng)集集合private MapSet, SetSet assiciationRules; / 頻繁關(guān)聯(lián)規(guī)則集合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();/ 計(jì)算支持度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、 統(tǒng)計(jì)支持?jǐn)?shù)，生成候選頻繁1-項(xiàng)集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(); / 兩個(gè)項(xiàng)集相同元素的集合(集合的交運(yùn)算)identicalSet.addAll(originalItemSet);Set set = itr.next();identicalSet.retainAll(set); / identicalSet中剩下的元素是identicalSet與set集合中公有的元素if(identicalSet.size() = m-1

26、) / (k-1)-項(xiàng)集中k-2個(gè)相同Set differentSet = new HashSet(); / 兩個(gè)項(xiàng)集不同元素的集合(集合的差運(yùn)算)differentSet.addAll(originalItemSet);differentSet.removeAll(set); / 因?yàn)橛衚-2個(gè)相同，則differentSet中一定剩下一個(gè)元素，即differentSet大小為1differentSet.addAll(set); / 構(gòu)造候選k-項(xiàng)集的一個(gè)元素(set大小為k-1,differentSet大小為k)candFreqKItemSet.add(differentSet); / 加

27、入候選k-項(xiàng)集集合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();/ 調(diào)用aprioriGen方法，得到候選頻繁k-項(xiàng)集SetSet candFreqKItemSet = this.aprioriGen(k-1, freqMItemSet);/ 掃描事務(wù)數(shù)據(jù)庫(kù)IteratorMap.EntryInteger, Set it = txDatabase.entrySet().iterator();/ 統(tǒng)計(jì)支持?jǐn)?shù)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-項(xiàng)集與事務(wù)數(shù)據(jù)庫(kù)中元素做差元算if(set.isEmpty() / 如果拷貝set為空，支持?jǐn)?shù)加1if(candFreqKItemSetMap.get(kSet) = null) Integer value = 1;candFreqKItemSetMap.put(kSet, value);else Integer value = 1+

30、candFreqKItemSetMap.get(kSet);candFreqKItemSetMap.put(kSet, value);/ 計(jì)算支持度，生成頻繁k-項(xiàng)集，并返回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();/ 計(jì)算支持度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() / 計(jì)算頻繁1-項(xiàng)集SetSet freqKItemSet = this.getFreq1ItemSet().keySet();freqItemSet.put(1, freqKItemSet);/ 計(jì)算頻繁k-項(xiàng)集(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-項(xiàng)集IteratorMap.EntryInteger, SetSet it = freqItemSet.entrySet().iterator();while(it.hasNext() Map.EntryInteger, SetSet entry = it.next();for(Set itemSet : entry.getValue(

34、) / 對(duì)每個(gè)頻繁項(xiàng)集進(jìn)行關(guān)聯(lián)規(guī)則的挖掘mine(itemSet);public void mine(Set itemSet) int n = itemSet.size()/2; / 根據(jù)集合的對(duì)稱性，只需要得到一半的真子集for(int i=1; i=n; i+) / 得到頻繁項(xiàng)集元素itemSet的作為條件的真子集集合SetSet properSubset = ProperSubsetCombination.getProperSubset(i, itemSet);/ 對(duì)條件的真子集集合中的每個(gè)條件項(xiàng)集，獲取到對(duì)應(yīng)的結(jié)論項(xiàng)集，從而進(jìn)一步挖掘頻繁關(guān)聯(lián)規(guī)則for(Set conditionSet

35、 : properSubset) Set conclusionSet = new HashSet();conclusionSet.addAll(itemSet);conclusionSet.removeAll(conditionSet); / 刪除條件中存在的頻繁項(xiàng)confide(conditionSet, conclusionSet); / 調(diào)用計(jì)算置信度的方法，并且挖掘出頻繁關(guān)聯(lián)規(guī)則public void confide(Set conditionSet, Set conclusionSet) / 掃描事務(wù)數(shù)據(jù)庫(kù)IteratorMap.EntryInteger, Set it = txDa

36、tabase.entrySet().iterator();/ 統(tǒng)計(jì)關(guān)聯(lián)規(guī)則支持計(jì)數(shù)int conditionToConclusionCnt= 0; / 關(guān)聯(lián)規(guī)則(條件項(xiàng)集推出結(jié)論項(xiàng)集)計(jì)數(shù)int conclusionToConditionCnt= 0; / 關(guān)聯(lián)規(guī)則(結(jié)論項(xiàng)集推出條件項(xiàng)集)計(jì)數(shù)int supCnt = 0; / 關(guān)聯(lián)規(guī)則支持計(jì)數(shù)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); / 集合差運(yùn)算：set-txSetif(set1.isEmpty() / 如果set為空，說(shuō)明事務(wù)數(shù)據(jù)庫(kù)中包含條件頻繁項(xiàng)conditionSet/ 計(jì)數(shù)conditionToConclusionCnt+;set2.addAll(conclusionSet);set2.removeAll(txSet); / 集合差運(yùn)算：set-txSetif(set2.isEmpty() / 如果set為空，說(shuō)明事務(wù)數(shù)據(jù)庫(kù)中包含結(jié)論頻繁項(xiàng)conclusionSet/ 計(jì)數(shù)conclusionT

38、oConditionCnt+;if(set1.isEmpty() & set2.isEmpty() supCnt+;/ 計(jì)算置信度Float conditionToConclusionConf = new Float(supCnt)/new Float(conditionToConclusionCnt);if(conditionToConclusionConf=minConf) if(assiciationRules.get(conditionSet) = null) / 如果不存在以該條件頻繁項(xiàng)集為條件的關(guān)聯(lián)規(guī)則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) / 如果不存在以該結(jié)論頻繁項(xiàng)集為條件的關(guān)聯(lián)規(guī)則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類是一個(gè)輔助類，在挖掘頻繁關(guān)聯(lián)規(guī)則的過(guò)程中，用于生成一個(gè)頻繁項(xiàng)集元素的非空真子集，實(shí)現(xiàn)代碼如下：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; / 比特集合起始狀態(tài)private static BitSet endBitSet; / 比特集合終止?fàn)顟B(tài)，用來(lái)控制循環(huán)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，左側(cè)占滿1for (int i=0; i=array.length-n; i-) endBitSet.set(i, true);/ 根據(jù)起始startBitSet，將一個(gè)組合加入到真子集集合中g(shù)et(startBitSet);while(!startBitSet.equals(endBitSet) int zeroCount = 0; / 統(tǒng)計(jì)遇到10后，左邊0的個(gè)數(shù)i

44、nt oneCount = 0; / 統(tǒng)計(jì)遇到10后，左邊1的個(gè)數(shù)int pos = 0; / 記錄當(dāng)前遇到10的索引位置/ 遍歷startBitSet來(lái)確定10出現(xiàn)的位置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);測(cè)試用例對(duì)上述Apriori算法的實(shí)現(xiàn)進(jìn)行了簡(jiǎn)單的測(cè)試，測(cè)試用例如下所示：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(); / 構(gòu)造事務(wù)數(shù)據(jù)庫(kù)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