【導(dǎo)讀】關(guān)聯(lián)規(guī)則在數(shù)據(jù)挖掘是一個重要的研究內(nèi)容。而產(chǎn)生頻繁集則是產(chǎn)生關(guān)聯(lián)規(guī)則的第一。在大多數(shù)以前的實現(xiàn)中，人們普遍采用了類似于Apriori[2]的算法。很大的缺點，就是使用了不斷產(chǎn)生候選集并加以測試的方式來得到頻繁集。集的代價是很大的。本文分析并且實現(xiàn)了在論文[1]中提出的FP-growth算法。FP-growth算法的優(yōu)點是節(jié)。省時間和空間，對大規(guī)模數(shù)據(jù)采用分治的辦法以避免規(guī)模巨大難以接受。FP-tree是一個數(shù)據(jù)庫里跟產(chǎn)生頻繁集有關(guān)的信息的壓縮表示。通過了一系列的從低到高的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)它，并進(jìn)而實現(xiàn)整個算法。平臺，編程工具是VisualC++，許多地方還用到了C++的標(biāo)準(zhǔn)模板庫。聯(lián)規(guī)則找尋的第一步就是要找到相應(yīng)的頻繁集.現(xiàn)了FP-growth算法,并將它作為一個使用數(shù)據(jù)挖掘工具,ARMiner的一部分.第3部分討論關(guān)聯(lián)規(guī)則的一些問題.模式、規(guī)律和約束等看作知識?；?，決策支持和過程控制等，還可以用于數(shù)據(jù)自身的維護(hù)。語言表達(dá)所發(fā)現(xiàn)的結(jié)果。笑片”大話西游”,該網(wǎng)站會提醒你,

　　

【正文】 (也就是支持度小于最小支持度的項 )都被排在最后面 ,最后通過語句 while(tit!=dbitend()amp。amp。titcount) tit++。 if(tit!=dbitend())dbiterase(tit,dbitend())。 把它們?nèi)縿h除掉 . (f8) Node* SetupFP(FreqSet* pSet,Table* pTable,DB* pDB)。 這是 Algorithm1(...)中最關(guān)鍵的一個函數(shù) .它通過上面幾步建立頻繁項集合 pSet,頭表pTable,每個交易都已經(jīng)排序好的數(shù)據(jù)庫 pDB 得到一棵 FPtree. 該函數(shù)的主要清單如下 : for(dit=pDBbegin()。dit!=pDBend()。dit++){//對數(shù)據(jù)庫中每個交易 node=root。 for(tit=ditbegin()。tit!=ditend()。tit++){對某個交易中的每個項 Node* temp。 temp=find_node(nodepChildrenbegin(),nodepChildrenend(),titname)。 if(temp==NULL){ //如果子節(jié)點中沒有要找的項則創(chuàng)建一個 Node* temp2=(Node*)new Node。 temp2name=titname。 temp2count=titcount。 nodepChildrenpush_back(temp2)。 一個不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實現(xiàn) １７ temp2pParent=node。 node=temp2。 }else{ tempcount+=titcount。//否 則 ,增加該項的支持度 node=temp。 continue。 } fit=pSetfind(nodename)。 tait=*((Table_Iter*)fit)。//通過頻繁項集合 pSet 中項的 lpvoid 域 //找到相應(yīng)頭表表項 nodenode_link=taithead_link。//更新頭表表項中的 node_link taithead_link=node。 } } 關(guān)于該函數(shù)的情況 ,請看程序清單 中的注釋。 在算法的描述中只規(guī)定了根節(jié)點的標(biāo)記為 ”null”,并沒有要求它和其它的節(jié)點一樣具有count 和 node_link 域 .為了不用給根節(jié)點另外建立一個類 ,就簡單使用了一般節(jié)點的類 Node.把其中的 count 設(shè)為 0,node_link 設(shè)為 null. Node* find_node(NVector_Iter f,NVector_Iter l,CString name)在子節(jié)點的集合中查找是否含有 name 的子節(jié)點 ,并返回之 ,若無 ,則返回 ,其原因已經(jīng)在數(shù)據(jù)結(jié)構(gòu)部分 的 ”NodeVector和 Node”中說明了 . (f9) void Algorithm2(Node* tree,Table* pTable,DB *pDB,Trans set){ if(tree==NULL)return。 Node* tree2=tree。 if(HasNoBranch(tree)){//如果 tree 沒有分支 Trans set2。 while(true){//把 tree 的唯一路徑上面的所有節(jié)點都放入 set2 中 if(treename!=) (Item(treename,treecount))。 if(treepChildrenempty())break。 tree=*treepChildrenbegin()。 } Generate1(set2,pDB,set)。//產(chǎn)生頻繁集 }else{ Table_Iter tit。 for(tit=pTableend()。tit!=pTablebegin()。){//從尾到頭遍歷每一個頭表表項 DB* db。 tit。 int count。 db=Generate2(tithead_link,count)。//tit Table* table。 Node* node。 if(!dbempty()) 一個不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實現(xiàn) １８ Algorithm1(db,node,table)。 delete db。 Trans set2(set)。 (Item(titname,count))。 Algorithm2(node,table,pDB,set2)。 } } delete tree2。 delete pTable。 } 函數(shù) (f9)基本對應(yīng)于算法描述中的算法二 .它接受一棵由 (f4) 產(chǎn)生的 FPtree,node,相應(yīng)頭表 pTable,一個存放找到的頻繁集的數(shù)據(jù)庫結(jié)構(gòu) pDB,和存放中間模式的 pSet. Trans 類和 DB 類本來是用來存放交易和交易數(shù)據(jù)庫的 ,這里又用它來存放頻繁集和頻繁集數(shù)據(jù)庫 .頻繁集和交易的數(shù)據(jù)結(jié)構(gòu)在算法描述的時候是不太一樣的 . 交易和頻繁集都需要記錄項 .但是交易需要對每個項都記錄相應(yīng)的支持度 ,一個頻繁集卻只需要一個支持度 .為了方便對它們采用了相同的數(shù)據(jù)結(jié)構(gòu) .但是頻繁集中每個項的支持度都是相同的 . 在該函數(shù) 中使用了函數(shù) (f10)(f). (f10) bool HasNoBranch(Node* tree){ NVector_Iter nit。 while(tree){ if(treepChildrenempty())return true。//若 tree 節(jié)點沒有子節(jié)點 ,返回 true nit=treepChildrenbegin()。//nit 為 tree 的第一個子節(jié)點 nit++。//得到第二個子節(jié)點 if(nit!=treepChildrenend())//若第二個子節(jié)點存在 return false。//返回 false tree=(*nit)。//節(jié)點向下移動 } return true。 } 這個函數(shù)判斷以 tree 為根節(jié)點的樹是否只有一條路徑 . 具體的執(zhí)行方式參見源代碼中的注釋 . (f11) void Generate1(Transamp。 set2,DB* pDB,Transamp。 set) { int size=()。 unsigned int maxsize=pow(2,size)。 bitint bit。 int count。 if(()){//如果 set2 為空 if(())return。//如果 set 也為空 ,返回 count=()count。//否則這里產(chǎn)生的頻繁集的支持度為 set 的支持度 }else{如果 set2 不為空 一個不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實現(xiàn) １９ Trans_Iter tit=()。 tit。 count=titcount。//頻繁集的支持度是 set2 中最小的 ,即最后一個 } for(。bitmaxsize。bit++){//產(chǎn)生頻繁集 { Trans trans。 int i=0。 Trans_Iter tit。 for(i=0,tit=()。tit!=()。tit++,i++){ if(bit[i]) (Item(titname,count))。 } for(tit=()。tit!=()。tit++) (Item(titname,count))。 if(!()) pDBpush_back(trans)。 } } } 該函數(shù)的作用是將每一個 set2中項的組合與 set合并 ,其結(jié)果即為一個頻繁集 ,然后將產(chǎn)生的頻繁集放入 pDB 中 . bitint 是我自己定義的一個類 .它跟產(chǎn)生一個集合的所有組合有關(guān) . bitint 實際上是一個無符號長整數(shù) ,但我們可以根據(jù)其中的成員函數(shù)得到這個無符號長整數(shù)的每一個比特位為 0 還是為 0 每次加 1,遞增到 pow(2,n)1,選出那些比特位為 1 所代表的元素就得到了有 n 個元素的集合的所有組合 . (f12) DB* Generate2(Node* node,intamp。 retcount){ DB* pDB=(DB*)new DB。 retcount=0。 while(node){ Trans trans。 Node* node2=nodepParent。 int count=nodecount。 while(node2name!=){ (Item(node2name,count))。 node2=node2pParent。 } retcount+=count。 pDBpush_back(trans)。 node=nodenode_link。 } return pDB。 一個不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實現(xiàn) ２０ } 該函數(shù)的作用是根據(jù)從頭表表項的 node_link 指針中得到的節(jié)點產(chǎn)生一個條件模式庫(conditional pattern base). 它的工作方式很簡單 .先從第一個節(jié)點向上尋找 ,把該節(jié)點的祖先節(jié)點 (除了根節(jié)點以外 )都放到一個交易對象里面 ,然后把這個交易放到函數(shù)開 頭生成的數(shù)據(jù)庫對象 pDB 里面 .接著通過 node_link 轉(zhuǎn)到下一個節(jié)點 ,進(jìn)行相同的處理 ,直到 node_link 指向空值 . 我掌握了數(shù)據(jù)挖掘的基本知識后 ,就開始針對論文 [1]中所提出的算法進(jìn)行程序設(shè)計 .這個算法主要是跟關(guān)聯(lián)規(guī)則有關(guān)系 ,所以注意力比較集中在跟關(guān)聯(lián)規(guī)則有關(guān)的問題上 ,閱讀了一些專門闡述關(guān)聯(lián)規(guī)則的論文如 [2],[5]等 .在設(shè)計程序的時候 ,為了使數(shù)據(jù)結(jié)構(gòu)的使用達(dá)到最大的優(yōu)化 ,還閱讀了許多 STL 的源代碼 . 關(guān)于程序 ,應(yīng)該說比較完整了 ,剩下的步驟就是把它集成到 ARMiner 里面去了 . 在這段時間 里 ,通過程序的編寫和論文的寫作掌握了數(shù)據(jù)挖掘的基本知識，對關(guān)聯(lián)規(guī)則有了比較多的認(rèn)識 ,對頻繁集產(chǎn)生的各個算法有了比較深入的探討 .對我的編程能力和自我學(xué)習(xí)的能力也是一個考驗 . 最后 ,我要感謝在這段時間內(nèi)對我的工作進(jìn)行指導(dǎo)的朱揚勇教授 .他在本學(xué)期開設(shè)的一門數(shù)據(jù)庫的課程使我對原來對數(shù)據(jù)庫系統(tǒng)抽象的認(rèn)識更加深刻和感性了 ,對數(shù)據(jù)倉庫和數(shù)據(jù)挖掘的講解使我來說是全新的 ,有吸引力的 . 我要感謝朱建秋 ,蔡偉杰 ,張曉輝三位研究生 .他們在我工作的每一個過程都及時的提出建議和給予指導(dǎo) . 還有他們?nèi)唤⒌囊粋€傳播數(shù)據(jù)挖掘 知識的論壇 ,知道了什么是數(shù)據(jù)挖掘 ,在寫論文的過程中又不斷從那里得到不可或缺的幫助 . 參考文獻(xiàn) ： [1] Jiawei Han,Jian Pei,and Yiwen Frequent Patterns without Candidate Generation [2] Rakesh Agrawal,Ramakrjshnan Srjkant. Fast Algorithms for Mining Association of the 20th VLDB Conference. [3] 朱揚勇 ,周欣 ,施伯樂 . 規(guī)則型數(shù)據(jù)采掘工具集 AMINER. 20xx , 高技術(shù)通訊 . [4] 數(shù)據(jù)挖掘入門 . 朱揚勇 . [5] 一個基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)采掘工具的設(shè)計和實現(xiàn) . 朱建秋 , 周皓峰 , 朱揚勇 , 施伯樂