數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘?qū)嶒?yàn)報(bào)告

數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘課程APRIORI算法學(xué)習(xí)一簡(jiǎn)介Apriori算法是一種挖掘關(guān)聯(lián)規(guī)則的頻繁項(xiàng)集算法，其核心思想是通過(guò)候選集生成和情節(jié)的向下封閉檢測(cè)兩個(gè)階段來(lái)挖掘頻繁項(xiàng)集。而且算法已經(jīng)被廣泛的應(yīng)用到商業(yè)、網(wǎng)絡(luò)安全等各個(gè)領(lǐng)域。它是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法。其核心是基于兩階段頻集思想的遞推算法。該關(guān)聯(lián)規(guī)則在分類(lèi)上屬于單維、單層、布爾關(guān)聯(lián)規(guī)則。在這里，所有支持度大于最小支持度的項(xiàng)集稱(chēng)為頻繁項(xiàng)集，簡(jiǎn)稱(chēng)頻集[1]。二基本思想該算法的基本思想是：首先找出所有的頻集，這些項(xiàng)集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持度一樣。然后由頻集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，這些規(guī)則必須滿(mǎn)足最小支持度和最小可信度。然后使用第1步找到的頻集產(chǎn)生期望的規(guī)則，產(chǎn)生只包含集合的項(xiàng)的所有規(guī)則，其中每一條規(guī)則的右部只有一項(xiàng)，這里采用的是中規(guī)則的定義。一旦這些規(guī)則被生成，那么只有那些大于用戶(hù)給定的最小可信度的規(guī)則才被留下來(lái)。為了生成所有頻集，使用了遞歸的方法。挖掘步驟：(1)依據(jù)支持度[2]找出所有頻繁項(xiàng)集(頻度)。(2)依據(jù)置信度[3]產(chǎn)生關(guān)聯(lián)規(guī)則(強(qiáng)度)。三核心流程Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法。是基于這樣的事實(shí)：算法使用頻繁項(xiàng)集性質(zhì)的先驗(yàn)知識(shí)。Apriori使用一種稱(chēng)作逐層搜索的迭代方法，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ù)掃描。這個(gè)算法的思路，簡(jiǎn)單的說(shuō)就是如果集合I不是頻繁項(xiàng)集，那么所有包含集合I的更大的集合也不可能是頻繁項(xiàng)集。算法原始數(shù)據(jù)如下：TIDListofitem_ID’sT100T200T300T400T500T600T700T800T900I1,I2,I5I2,I4I2,I3I1,I2,I4I1,I3I2,I3I1,I3I1,I2,I3,I5I1,I2,I3算法的基本過(guò)程如下圖：首先掃描所有事務(wù)，得到1-項(xiàng)集C1，根據(jù)支持度要求濾去不滿(mǎn)足條件項(xiàng)集，得到頻繁1-項(xiàng)集。下面進(jìn)行遞歸運(yùn)算：已知頻繁k-項(xiàng)集(頻繁1-項(xiàng)集已知)，根據(jù)頻繁k-項(xiàng)集中的項(xiàng)，連接得到所有可能的K+1_項(xiàng)，并進(jìn)行剪枝（如果該k+1_項(xiàng)集的所有k項(xiàng)子集不都能滿(mǎn)足支持度條件，那么該k+1_項(xiàng)集被剪掉），得到項(xiàng)集，然后濾去該項(xiàng)集中不滿(mǎn)足支持度條件的項(xiàng)得到頻繁k+1-項(xiàng)集。如果得到的項(xiàng)集為空，則算法結(jié)束。連接的方法：假設(shè)項(xiàng)集中的所有項(xiàng)都是按照相同的順序排列的，那么如果和中的前k-1項(xiàng)都是完全相同的，而第k項(xiàng)不同，則和是可連接的。比如中的{I1,I2}和{I1,I3}就是可連接的，連接之后得到{I1,I2,I3}，但是{I1,I2}和{I2,I3}是不可連接的，否則將導(dǎo)致項(xiàng)集中出現(xiàn)重復(fù)項(xiàng)。關(guān)于剪枝再舉例說(shuō)明一下，如在由生成的過(guò)程中，列舉得到的3_項(xiàng)集包括{I1,I2,I3},{I1,I3,I5},{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}，但是由于{I3,I4}和{I4,I5}沒(méi)有出現(xiàn)在中，所以{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}被剪枝掉了。簡(jiǎn)單的講:發(fā)現(xiàn)頻繁項(xiàng)集，過(guò)程為（1）掃描（2）計(jì)數(shù)（3）比較（4）產(chǎn)生頻繁項(xiàng)集（5）連接、剪枝，產(chǎn)生候選項(xiàng)集。重復(fù)步驟（1）~（5）直到不能發(fā)現(xiàn)更大的頻集。2、產(chǎn)生關(guān)聯(lián)規(guī)則，過(guò)程為:根據(jù)前面提到的置信度的定義，關(guān)聯(lián)規(guī)則的產(chǎn)生如下：（1）對(duì)于每個(gè)頻繁項(xiàng)集L，產(chǎn)生L的所有非空子集；（2）對(duì)于L的每個(gè)非空子集S，如果P（L）/P（S）≧min_conf則輸出規(guī)則“SàL-S”注：L-S表示在項(xiàng)集L中除去S子集的項(xiàng)集偽代碼偽代碼描述：//找出頻繁1項(xiàng)集L1=find_frequent_1-itemsets(D);For(k=2;Lk-1!=null;k++){//產(chǎn)生候選，并剪枝Ck=apriori_gen(Lk-1);//掃描D進(jìn)行候選計(jì)數(shù)Foreach事務(wù)tinD{Ct=subset(Ck,t);//得到t的子集Foreach候選c屬于Ctc.count++;} //返回候選項(xiàng)集中不小于最小支持度的項(xiàng)集Lk={c屬于Ck|c.count>=min_sup}}ReturnL=所有的頻繁集；第一步：連接（join）Procedureapriori_gen(Lk-1:frequent(k-1)-itemsets)Foreach項(xiàng)集l1屬于Lk-1Foreach項(xiàng)集l2屬于Lk-1If((l1[1]=l2[1])&&(l1[2]=l2[2])&&……&&(l1[k-2]=l2[k-2])&&(l1[k-1]<l2[k-1]))then{c=l1連接l2//連接步：產(chǎn)生候選 //若k-1項(xiàng)集中已經(jīng)存在子集c則進(jìn)行剪枝ifhas_infrequent_subset(c,Lk-1)thendeletec;//剪枝步：刪除非頻繁候選elseaddctoCk;}ReturnCk;第二步：剪枝（prune） Procedurehas_infrequent_sub(c:candidatek-itemset;Lk-1:frequent(k-1)-itemsets)Foreach(k-1)-subsetsofcIfs不屬于Lk-1thenReturntrue;Returnfalse;四具體實(shí)例及代碼實(shí)現(xiàn)交易ID商品ID列表T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3T600I2，I3T700I1，I3T800I1，I2，I3，I5T900I1，I2，I3上圖為某商場(chǎng)的交易記錄，共有9個(gè)事務(wù)，利用Apriori算法尋找所有的頻繁項(xiàng)集的過(guò)程如下:詳細(xì)介紹下候選3項(xiàng)集的集合C3的產(chǎn)生過(guò)程：從連接步，首先C3={{I1,I2,I3}，{I1,I2,I5}，{I1,I3,I5}，{I2,I3,I4}，{I2,I3,I5}，{I2,I4,I5}}（C3是由L2與自身連接產(chǎn)生）。根據(jù)Apriori性質(zhì)，頻繁項(xiàng)集的所有子集也必須頻繁的，可以確定有4個(gè)候選集{I1,I3,I5}，{I2,I3,I4}，{I2,I3,I5}，{I2,I4,I5}}不可能時(shí)頻繁的，因?yàn)樗鼈兇嬖谧蛹粚儆陬l繁集，因此將它們從C3中刪除。注意，由于Apriori算法使用逐層搜索技術(shù)，給定候選k項(xiàng)集后，只需檢查它們的（k-1）個(gè)子集是否頻繁。偽代碼：L1=find_frequent_1-itemsets(D);//找出所有頻繁1項(xiàng)集For(k=2;Lk-1!=null;k++){Ck=apriori_gen(Lk-1);//產(chǎn)生候選，并剪枝Foreach事務(wù)tinD{//掃描D進(jìn)行候選計(jì)數(shù)Ct=subset(Ck,t);//得到t的子集Foreach候選c屬于Ctc.count++;}Lk={c屬于Ck|c.count>=min_sup}}ReturnL=所有的頻繁集；Procedureapriori_gen(Lk-1:frequent(k-1)-itemsets)Foreach項(xiàng)集l1屬于Lk-1Foreach項(xiàng)集l2屬于Lk-1If((l1[1]=l2[1])&&(l1[2]=l2[2])&&……..&&(l1[k-2]=l2[k-2])&&(l1[k-1]<l2[k-1]))then{c=l1連接l2//連接步：產(chǎn)生候選ifhas_infrequent_subset(c,Lk-1)thendeletec;//剪枝步：刪除非頻繁候選elseaddctoCk;}ReturnCk;Procedurehas_infrequent_sub(c:candidatek-itemset;Lk-1:frequent(k-1)-itemsets)Foreach(k-1)-subsetsofcIfs不屬于Lk-1thenReturntrue;Returnfalse;Java代碼packagecom.apriori;importjava.util.ArrayList;importjava.util.Collections;importjava.util.HashMap;importjava.util.List;importjava.util.Map;importjava.util.Set;publicclassApriori{privatefinalstaticintSUPPORT=2;//支持度閾值privatefinalstaticdoubleCONFIDENCE=0.7;//置信度閾值privatefinalstaticStringITEM_SPLIT=";";//項(xiàng)之間的分隔符privatefinalstaticStringCON="->";//項(xiàng)之間的分隔符privatefinalstaticList<String>transList=newArrayList<String>();//所有交易static{//初始化交易記錄transList.add("1;2;5;");transList.add("2;4;");transList.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;");}publicMap<String,Integer>getFC(){Map<String,Integer>frequentCollectionMap=newHashMap<String,Integer>();//所有的頻繁集frequentCollectionMap.putAll(getItem1FC());Map<String,Integer>itemkFcMap=newHashMap<String,Integer>();itemkFcMap.putAll(getItem1FC());while(itemkFcMap!=null&&itemkFcMap.size()!=0){Map<String,Integer>candidateCollection=getCandidateCollection(itemkFcMap);Set<String>ccKeySet=candidateCollection.keySet();//對(duì)候選集項(xiàng)進(jìn)行累加計(jì)數(shù)for(Stringtrans:transList){for(Stringcandidate:ccKeySet){booleanflag=true;//用來(lái)判斷交易中是否出現(xiàn)該候選項(xiàng)，如果出現(xiàn)，計(jì)數(shù)加1String[]candidateItems=candidate.split(ITEM_SPLIT);for(StringcandidateItem:candidateItems){if(trans.indexOf(candidateItem+ITEM_SPLIT)==-1){flag=false;break;}}if(flag){Integercount=candidateCollection.get(candidate);candidateCollection.put(candidate,count+1);}}}//從候選集中找到符合支持度的頻繁集項(xiàng)itemkFcMap.clear();for(Stringcandidate:ccKeySet){Integercount=candidateCollection.get(candidate);if(count>=SUPPORT){itemkFcMap.put(candidate,count);}}//合并所有頻繁集frequentCollectionMap.putAll(itemkFcMap);}returnfrequentCollectionMap;}privateMap<String,Integer>getCandidateCollection(Map<String,Integer>itemkFcMap){Map<String,Integer>candidateCollection=newHashMap<String,Integer>();Set<String>itemkSet1=itemkFcMap.keySet();Set<String>itemkSet2=itemkFcMap.keySet();for(Stringitemk1:itemkSet1){for(Stringitemk2:itemkSet2){//進(jìn)行連接String[]tmp1=itemk1.split(ITEM_SPLIT);String[]tmp2=itemk2.split(ITEM_SPLIT);Stringc="";if(tmp1.length==1){if(tmp1[0].compareTo(tmp2[0])<0){c=tmp1[0]+ITEM_SPLIT+tmp2[0]+ITEM_SPLIT;}}else{booleanflag=true;for(inti=0;i<tmp1.length-1;i++){if(!tmp1[i].equals(tmp2[i])){flag=false;break;}}if(flag&&(tmp1[tmp1.length-1].compareTo(tmp2[tmp2.length-1])<0)){c=itemk1+tmp2[tmp2.length-1]+ITEM_SPLIT;}}//進(jìn)行剪枝booleanhasInfrequentSubSet=false;if(!c.equals("")){String[]tmpC=c.split(ITEM_SPLIT);for(inti=0;i<tmpC.length;i++){StringsubC="";for(intj=0;j<tmpC.length;j++){if(i!=j){subC=subC+tmpC[j]+ITEM_SPLIT;}}if(itemkFcMap.get(subC)==null){hasInfrequentSubSet=true;break;}}}else{hasInfrequentSubSet=true;}if(!hasInfrequentSubSet){candidateCollection.put(c,0);}}}returncandidateCollection;}privateMap<String,Integer>getItem1FC(){Map<String,Integer>sItem1FcMap=newHashMap<String,Integer>();Map<String,Integer>rItem1FcMap=newHashMap<String,Integer>();//頻繁1項(xiàng)集for(Stringtrans:transList){String[]items=trans.split(ITEM_SPLIT);for(Stringitem:items){Integercount=sItem1FcMap.get(item+ITEM_SPLIT);if(count==null){sItem1FcMap.put(item+ITEM_SPLIT,1);}else{sItem1FcMap.put(item+ITEM_SPLIT,count+1);}}}Set<String>keySet=sItem1FcMap.keySet();for(Stringkey:keySet){Integercount=sItem1FcMap.get(key);if(count>=SUPPORT){rItem1FcMap.put(key,count);}}returnrItem1FcMap;}publicMap<String,Double>getRelationRules(Map<String,Integer>frequentCollectionMap){Map<String,Double>relationRules=newHashMap<String,Double>();Set<String>keySet=frequentCollectionMap.keySet();for(Stringkey:keySet){doublecountAll=frequentCollectionMap.get(key);String[]keyItems=key.split(ITEM_SPLIT);if(keyItems.length>1){List<String>source=newArrayList<String>();Collections.addAll(source,keyItems);List<List<String>>result=newArrayList<List<String>>();buildSubSet(source,result);//獲得source的所有非空子集for(List<String>itemList:result){if(itemList.size()<source.size()){//只處理真子集List<String>otherList=newArrayList<String>();for(StringsourceItem:source){if(!itemList.contains(sourceItem)){otherList.add(sourceItem);}}StringreasonStr="";//前置StringresultStr="";//結(jié)果for(Stringitem:itemList){reasonStr=reasonStr+item+ITEM_SPLIT;}for(Stringitem:otherList){resultStr=resultStr+item+ITEM_SPLIT;}doublecountReason=frequentCollectionMap.get(reasonStr);doubleitemConfidence=countAll/countReason;//計(jì)算置信度if(itemConfidence>=CONFIDENCE){Stringrule=reasonStr+CON+resultStr;relationRules.put(rule,itemConfidence);}}}}}returnrelationRules;}privatevoidbuildSubSet(List<String>sourceSet,List<List<String>>result){//僅有一個(gè)元素時(shí)，遞歸終止。此時(shí)非空子集僅為其自身，所以直接添加到result中if(sourceSet.size()==1){List<String>set=newArrayList<String>();set.add(sourceSet.get(0));result.add(set);}elseif(sourceSet.size()>1){//當(dāng)有n個(gè)元素時(shí)，遞歸求出前n-1個(gè)子集，在于result中buildSubSet(sourceSet.subList(0,sourceSet.size()-1),result);intsize=result.size();//求出此時(shí)result的長(zhǎng)度，用于后面的追加第n個(gè)元素時(shí)計(jì)數(shù)//把第n個(gè)元素加入到集合中List<String>single=newArrayList<String>();single.add(sourceSet.get(sourceSet.size()-1));result.add(single);//在保留前面的n-1子集的情況下，把第n個(gè)元素分別加到前n個(gè)子集中，并把新的集加入到result中;//為保留原有n-1的子集，所以需要先對(duì)其進(jìn)行復(fù)制List<String>clone;for(inti=0;i<size;i++){clone=newArrayList<String>();for(Stringstr:result.get(i)){clone.add(str);}clone.add(sourceSet.get(sourceSet.size()-1));result.add(clone);}}}publicstaticvoidmain(String[]args){Aprioriapriori=newApriori();Map<String,Integer>frequentCollectionMap=apriori.getFC();System.out.println("----------------頻繁集"+"----------------");Set<String>fcKeySet=frequentCollectionMap.keySet();for(StringfcKey:fcKeySet){System.out.println(fcKey+":"+frequentCollectionMap.get(fcKey));}Map<String,Double>relationRulesMap=apriori.getRelationRules(frequentCollectionMap);System.out.println("----------------關(guān)聯(lián)規(guī)則"+"----------------");Set<String>rrKeySet=relationRulesMap.keySet();for(StringrrKey:rrKeySet){System.out.println(rrKey+":"+relationRulesMap.get(rrKey));}}}五缺點(diǎn)海量數(shù)據(jù)下，Apriori算法的時(shí)空復(fù)雜度都不容忽視。空間復(fù)雜度：如果數(shù)量達(dá)到的量級(jí)，那么中的候選項(xiàng)將達(dá)到的量級(jí)。由頻繁k-1項(xiàng)集進(jìn)行自連接生成的候選頻繁