Apriori算法及java實現(xiàn)

1、1 Apriori 介紹Apriori算法使用頻繁項集的先驗知識，使用一種稱作逐層搜索的迭代方法，k項集用于探索（k+1）項集。首先，通過掃描事務（交易）記錄，找出所有的頻繁1項集，該集合記做Li,然后利用Li找頻繁2項集的集合L2，L2找L3,如此下去，直到不能再找到任何頻繁 k項集。最后再在所有的頻繁集中找出強規(guī)則，即產(chǎn)生用戶感興趣的關(guān)聯(lián)規(guī)則。其中，Apriori算法具有這樣一條 性質(zhì)：任一頻繁項集的所有非空子集也必須是頻繁的。 因為假如P（l）<最小支持度閾值，當有元素A添加到I中時，結(jié)果項集（A n I）不可能比I出現(xiàn)次數(shù)更多。因此 A nI也不是頻繁的。2連接步和剪枝步在上述的

2、關(guān)聯(lián)規(guī)則挖掘過程的兩個步驟中，第一步往往是總體性能的瓶頸。Apriori算法采用連接步和剪枝步兩種方式來找出所有的頻繁項集。1）連接步為找出Lk （所有的頻繁k項集的集合），通過將Lk-i （所有的頻繁k-1項集的集合）與自身連接產(chǎn)生候選k項集的集合。候選集合記作Ck。設(shè)li和12是Lk-i中的成員。記1酉表示h中的第j項。假設(shè)Apriori算法對事務或項集中的項按字典次序排序，即對于（k-i）項集li,lii<l i2< Vik-i。將 Lk-i 與自身連接，如果（1ii=1 2i）&&（ 1 i2=122）&& &&（lik-2=

3、l 2k-2）&&（l ik-i<l 2k-i），那認為li和b是可連接。連接li和l2產(chǎn)生的結(jié)果是 lii,li2,，lik-i,l 2k-i。2）剪枝步Ck是Lk的超集，也就是說，Ck的成員可能是也可能不是頻繁的。通過掃描所有的事 務（交易），確定Ck中每個候選的計數(shù)，判斷是否小于最小支持度計數(shù)，如果不是，則認為該候選是頻繁的。為了壓縮Ck,可以利用Apriori性質(zhì)：任一頻繁項集的所有非空子集也必 須是頻繁的，反之，如果某個候選的非空子集不是頻繁的，那么該候選肯定不是頻繁的，從 而可以將其從Ck中刪除。（Tip :為什么要壓縮 Ck呢？因為實際情況下事務記錄往往是保

4、存在外存儲上，比如數(shù)據(jù)庫或者其他格式的文件上，在每次計算候選計數(shù)時都需要將候選與所有事務進行比對，眾所周知，訪問外存的效率往往都比較低，因此Apriori力口入了所謂的剪枝步，事先對候選集進行過濾，以減少訪問外存的次數(shù)。）3 Apriori算法實例交易ID商品ID列表TiOOIi , I2 , I5T200I2, I4T300I2, I3T400Ii , I2 , I4T500Ii , I3T600I2 , I3T700Ii , I3T800Ii , I2 , I3 , I5T900上圖為某商場的交易記錄，共有9個事務,11 , 12 ,13利用Apriori算法尋找所有的頻繁項集的過程如下：

5、ttw tf T 6 2 z 裊 _*./ _»./ «ElQQI4d6r宅1ft巾支特憧橫術(shù)pfi14L14$WE)4MB41體2402,142皿尉20砂1aL2ig4pijj斗2422創(chuàng)師有的壹持俺計義左曲疋承-+ULE.B；OLB43)2I(I*冏3詳細介紹下候選3項集的集合C3的產(chǎn)生過程：從連接步，首先C3=I1,I2,I3 ,11,12,15，11,13,15，12,13,14，12,13,15，12,14,15（ C3 是由 L2 與自身連接產(chǎn)生）。根據(jù) Apriori性質(zhì)，頻繁項集的所有子集也必須頻繁的，可以確定有4個候選集11,13,15，12,13,14，

6、12,13,15，12,14,15不可能時頻繁的，因為它們存在子集不屬于頻繁集，因此將它們從C3中刪除。注意，由于 Apriori算法使用逐層搜索技術(shù)，給定候選k項集后，只需檢查它們的（k-1）個子集是否頻繁。3. Apriori偽代碼算法：Apriori輸入：D -事務數(shù)據(jù)庫；min_sup -最小支持度計數(shù)閾值輸出：L - D中的頻繁項集方法:L1=find_frequent_1-itemsets(D); / 找出所有頻繁 1 項集For(k=2;L k-1 !=null;k+)Ck=apriori_gen(L k-i); / 產(chǎn)生候選，并剪枝For each事務t in D /掃描D進行

7、候選計數(shù)Ct =subset(Ck,t); / 得到 t 的子集For each候選c屬于Ctc.co un t+;Lk=c 屬于 Ck | c.count>=min_supRetur n L=所有的頻繁集；Procedure apriori_gen (Lk-1:frequent(k-1)-itemsets)For each 項集 11 屬于 Lk-1For each項集b屬于lf(l 11=l 21)&&( l 12=l 22)&& && (l 1k-2=l 2k-2)&&(l 1k-1<l 2k-1) thenc=

8、l1連接l2 連接步：產(chǎn)生候選if has_infrequent_subset(c,L k-1) thendelete c; /剪枝步：刪除非頻繁候選else add c to Ck；Retur n C k；Procedure has_infrequent_sub(c:candidate k-itemset; L k-1:frequent(k-1)-itemsets)For each(k-1)-subset s of cIf s 不屬于 Lk-1 thenRetur n true;Return false;4. 由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則Co nfide nce(A->B)=P(B|A)=s

9、upport_cou nt(AB)/support_cou nt(A)關(guān)聯(lián)規(guī)則產(chǎn)生步驟如下：1) 對于每個頻繁項集I，產(chǎn)生其所有非空真子集；2) 對于每個非空真子集 s,如果 support_count(l)/support_count(s)>=min_conf，則輸 出s->(l-s)，其中，min_conf是最小置信度閾值。例如，在上述例子中，針對頻繁集I1，I2 ,15?？梢援a(chǎn)生哪些關(guān)聯(lián)規(guī)則？該頻繁集的非空真子集有I1，I2，I1，I5，I2，I5，I1 ，I2和I5，對應置信度如下:I1&& 12->15con fide nce=2/4=50%I1&a

10、mp;& 15->12con fide nce=2/2=100%I2&& 15->11con fide nce=2/2=100%I1 ->I2&& 15con fide nce=2/6=33%I2 ->I1 &&I5con fide nce=2/7=29%I5 ->I1 &&I2co nfide nce=2/2=100%如果 min_conf=70%,則強規(guī)則有 I1&& 15->12 ，I2&& 15->11 ，I5 ->I1 &&a

11、mp; 12。5. Apriori Java 代碼package com.apriori;import java.util.ArrayList;import java.util.Collections;import java.util.HashMap;import java.util.List;import java.util.Map;import java.util.Set;public class Apriori private final static int SUPPORT = 2; / 支持度閾值private final static double CONFIDENCE = 0.7

12、; / 置信度閾值private final static String ITEM_SPLIT="" /項之間的分隔符private final static String CON="->" /項之間的分隔符private final static List<String> transList=new ArrayList<String>(); /所有交易static/初始化交易記錄transList.add("1;2;5;");transList.add("2;4;");transLi

13、st.add("2;3;");transList.add("1;2;4;");transList.add("1;3;");transList.add("2;3;");transList.add("1;3;");transList.add("1;2;3;5;");transList.add("1;2;3;");public Map<String,lnteger> getFC()Map<String,lnteger> frequentC

14、ollectionMap=new HashMap<String,lnteger>();所有的頻繁集frequentCollectionMap.putAII(getltem1FC();Map<String,Integer> itemkFcMap=new HashMap<String,Integer>();itemkFcMap.putAII(getltem 1FC();while(itemkFcMap!=null&&itemkFcMap.size()!=O)Map<String,Integer> candidateCollection

15、=getCandidateCollection(itemkFcMap);Set<String> ccKeySet=candidateCollection.keySet();/對候選集項進行累加計數(shù)for(String trans:transList)for(String candidate:ccKeySet)boolean flag=true;用來判斷交易中是否出現(xiàn)該候選項，如果出現(xiàn)，計數(shù)加 1String candidateltems=candidate.split(ITEM_SPLIT);for(String candidateltem:candidateltems)if(tr

16、ans.indexOf(candidateltem+ITEM_SPLIT)=-1)flag=false;break;if(flag)Integer count=candidateCollection.get(candidate);candidateCollection.put(candidate, count+1);/從候選集中找到符合支持度的頻繁集項itemkFcMap.clear();for(String candidate:ccKeySet)Integer count=candidateCollection.get(candidate);if(count>=SUPPORT)item

17、kFcMap.put(candidate, count);/合并所有頻繁集frequentCollectionMap.putAII(itemkFcMap);return frequentCollectionMap;private Map<String,Integer> getCandidateCollection(Map<String,lnteger> itemkFcMap)Map<String,Integer> candidateCollection=new HashMap<String,lnteger>();Set<String>

18、 itemkSet 1=itemkFcMap.keySet();Set<String> itemkSet2=itemkFcMap.keySet();for(String itemk1:itemkSet1)for(String itemk2:itemkSet2)/進行連接String tmp1=itemk1.split(ITEM_SPLIT);String tmp2=itemk2.split(ITEM_SPLI T);String c=""if(tmp1.length=1)if(pareTo(tmp20)<0) c=tmp10+ITEM_S

19、PLIT+tmp20+ITEM_SPLIT;elseboolean flag=true;for(int i=O;i<tmp1.length-1;i+)if(!tmp1i.equals(tmp2i)flag=false;break;if(flag&&(pareTo(tmp2tmp2.length-1)<0) c=itemk1+tmp2tmp2.length-1+ITEM_SP LIT;/進行剪枝boolean hasInfrequentSubSet = false;if (!c.equals("") Str

20、ing tmpC = c.split(ITEM_SPLIT);for (int i = 0; i < tmpC .l ength; i+) String subC =""for (int j = 0; j < tmpC .l ength; j+) if (i != j) subC = subC+tmpCj+ITEM_SP LIT;if (itemkFcMap.get(subC) = null) hasInfrequentSubSet = true; break;elsehaslnfrequentSubSet=true;if(!haslnfrequentSubSe

21、t)candidateCollection.put(c, 0);return candidatecollection;private Map<String,lnteger> getltem1FC()Map<String,lnteger> sltem1FcMap=new HashMap<String,lnteger>();Map<String,Integer> rltem1FcMap=new HashMap<String,lnteger>(); 頻繁 1 項集for(String trans:transList)String items

22、=trans.split(ITEM_SPLIT);for(String item:items)Integer count=sltem1FcMap.get(item+ITEM_SPLIT); if(count=null) sltem1FcMap.put(item+ITEM_SPLIT, 1);elsesltem1FcMap.put(item+ITEM_SPLIT, count+1);Set<String> keySet=sltem1FcMap.keySet(); for(String key:keySet)Integer count=sltem1FcMap.get(key); if(

23、count>=SUPPORT) rltem1FcMap.put(key, count);return rItem1FcMap;public Map<String,Double> getRelationRules(Map<String,Integer> frequentCollectionMap)Map<String,Double> relationRules=new HashMap<String,Double>();Set<String> keySet=frequentCollectionMap.keySet();for (St

24、ring key : keySet) double countAII=frequentCollectionMap.get(key);String keyItems = key.split(ITEM_SPLIT);if(keyltems .l ength>1)List<String> source=new ArrayList<String>();Collections.addAII(source, keyItems);List<List<String>> result=new ArrayList<List<String>&g

25、t;(); buildSubSet(source,result); 獲得 source 的所有非空子集 for(List<String> itemList:result)if(itemList.size()<source.size() 只處理真子集List<String> otherList=new ArrayList<String>();for(String sourceltem:source)if(!itemList.contains(sourceltem)otherList.add(sourceltem);String reasonStr=&qu

26、ot;" 前置String resultStr="" 結(jié)果for(String item:itemList)reasonStr=reasonSt 葉item+ITEM_SPLIT;for(String item:otherList)resultStr=resultStr+item+ITEM_SPLIT;double countReason=frequentCollectionMap.get(reasonStr);double itemConfidence=countAII/countReason; 計算置信度if(itemConfidence>=CONFID

27、ENCE)String ruIe=reasonSt 葉CON+resultStr;relationRules.put(rule, itemConfidence);return relationRules;private void buildSubSet(List<String> sourceSet, List<List<String>> result) /僅有一個元素時，遞歸終止。此時非空子集僅為其自身，所以直接添加到result中if (sourceSet.size() = 1) List<String> set = new ArrayList

28、<String>();set.add(sourceSet.get(O);result.add(set); else if (sourceSet.size() > 1) /當有n個元素時，遞歸求出前n-1個子集，在于result中buildSubSet(sourceSet.subList(O, sourceSet.size() - 1), result);int size = result.size();/求出此時result的長度，用于后面的追加第n個元素時計數(shù)/把第n個元素加入到集合中List<String> single = new ArrayList<String>()