摘要：頻繁模式樹的提出，提高了挖掘效率，是關(guān)聯(lián)規(guī)則挖掘史上的一個歷程碑。頻繁模式增長算法在創(chuàng)建頻繁模式樹時，重復(fù)比較新結(jié)點與已經(jīng)插入結(jié)點，以便確定新插入點的位置，造成了性能上的浪費。針對此問題，本文提出一種解決方法，即在創(chuàng)建FP-tree之前，將每一事務(wù)轉(zhuǎn)換成相應(yīng)的實數(shù)，以便在通過項頭表尋找結(jié)點鏈時可以快速定位。然后再對這些由實數(shù)組成的對應(yīng)數(shù)據(jù)庫進行排序，得到一個新的數(shù)據(jù)庫。在新的數(shù)據(jù)庫基礎(chǔ)上快速生成頻繁模式樹，這樣就避免了大量的重復(fù)的工作，提高了創(chuàng)建FP-tree的效率。理論分析表明，修改后的算法的性能明顯優(yōu)于原算法。
　　關(guān)鍵詞：數(shù)據(jù)挖掘；頻繁項集挖掘；頻繁模式增長算法；有序頻繁模式增長算法；
　　中圖分類號：TP311.1
　　1引言
　　頻繁模式的挖掘[1]在關(guān)聯(lián)規(guī)則[2]、相關(guān)分析、序列模式、因果律、顯露模式等許多重要數(shù)據(jù)挖掘任務(wù)中承擔著重要的角色。長期以來，挖掘頻繁模式主要采用Apriori[3,4]算法及其改進形式。然而Apriori及其改進算法仍然會產(chǎn)生大量候選項集，并需要反復(fù)頻繁的掃描數(shù)據(jù)庫，這嚴重影響了算法的效率。J.Han等人提出了新的結(jié)構(gòu)FP-tree和相應(yīng)的模式增長算法FP-growth[5]，該算法采用分治的策略，無須產(chǎn)生候選項集，F(xiàn)P-growth算法是一種本質(zhì)上不同于Apriori的挖掘頻繁項集的有效算法。但它的大部分時間都花費在FP-tree及條件FP-tree的構(gòu)造與遍歷上，如果能提高這方面的效率將對提高算法的效率有較大的幫助。基于這樣的分析，我們提出了對FP-growth算法的改進措施。在原數(shù)據(jù)庫D的基礎(chǔ)上建立新的數(shù)據(jù)庫D*。以便創(chuàng)建有序FP-tree，使得樹中的每一個結(jié)點的子結(jié)點按照項的序號從小到大排列。這樣，加入新結(jié)點時需要比較的結(jié)點數(shù)大大降低了，從而縮短構(gòu)造一棵樹的時間。此外，還采取了其它的優(yōu)化措施，如將item-no按照item-name的次序排成一個列表，在將item-name轉(zhuǎn)換為item-no時，通過列表可直接找到對應(yīng)的項。
　　2問題描述
　　2．1頻繁項集[6]
　　設(shè)I={i1,i2,…,in}是n個不同項目（Item）的集合，如果對一個集合，且k=|X|,則X稱為K項集，或者簡單地稱為一個項集（Itemset）。記D為事務(wù)T的集合，。對于給定事務(wù)數(shù)據(jù)庫D，定義X的支持度為D中包含X的事務(wù)個數(shù)，記為sup(X)。用戶可自定義一個小于|D|的最小支持度記為s.
　　定義1頻繁項集：給定事務(wù)數(shù)據(jù)庫D和支持度s，對于項集，若sup(X)≥s,則稱X為D中的頻繁項集。
　　性質(zhì)1一個長度為k的項集不是頻繁的，則它的長度為（k+1）的超模式不可能是頻繁的。
　　2.2FP-tree和FP-growth算法
　　頻繁模式樹即FP-tree中，每個結(jié)點由3個域組成：項名item、結(jié)點支持度計數(shù)sup-count及結(jié)點鏈node-link。為方便遍歷，創(chuàng)建一個項頭表Headertable，它由2個域組成:項名item和結(jié)點鏈頭headofnode-link，其中結(jié)點鏈頭指向FP-tree中與之名稱相同的第一結(jié)點。
　　FP-growth算法主要是FP-tree的構(gòu)造過程，需要掃描兩次數(shù)據(jù)庫：
　　(1)第一次掃描數(shù)據(jù)庫D，產(chǎn)生所有頻繁1-項集及其支持度計數(shù)，按其支持度降序排列插人到項頭表。
　　(2)創(chuàng)建FP-treeT的根結(jié)點，用“null”標記，對D中每個事務(wù)做如下處理:①按項頭表中的次序排列第一次掃描得到的頻繁項集，設(shè)排列后的結(jié)果為[p|P]，其中p是第1個項目，而p是剩余項目的列表;②調(diào)用insert_tree[p|P]，如果T有子女N使得N.item=p，則N的計數(shù)增加1，否則創(chuàng)建一個新結(jié)點N，將其名稱item設(shè)置為p，將sup_count設(shè)置為1，鏈接到它的父結(jié)點，并通過結(jié)點鏈node-link鏈接到具有相同項名的結(jié)點，如果P非空，遞歸調(diào)用insert_tree([P|N])。
　　3有序頻繁模式樹
　　3．1有序FP-tree的定義與構(gòu)造
　　有序FP-tree是在傳統(tǒng)FP-tree的基礎(chǔ)上通過改進獲得的。
　　定義2有序頻繁模式樹(OFP-tree)是一種樹結(jié)構(gòu)，定義如下：
　　(1)它由以下三個部分組成：一個標記為“null"的樹根，一棵以項前綴子樹集作為樹根的孩子所組成的樹，以及一個頻繁項頭表。
　　(2)項前綴子樹中的每個結(jié)點由6個域組成:item-no,count,parent-link,child-link,last-link和node-link。其中，item-no記錄該結(jié)點所代表的項在項頭表中的序號，count記錄從根結(jié)點到該結(jié)點的路徑上所代表的項集在所有數(shù)據(jù)庫事務(wù)中出現(xiàn)的次數(shù)，parent-link是指向父結(jié)點的指針，child-link是指向第一個子結(jié)點的指針，last-link是指向最后插入的孩子結(jié)點，而node-link則連接到FP-tree中與該結(jié)點具有相同item-no的下一個結(jié)點，如果沒有下一結(jié)點，則為null。具有相同父結(jié)點的結(jié)點按照item-no從小到大的次序排列。
　　(3)頻繁項頭表中的每個項由兩個域組成：item-no(結(jié)點所代表的項名)和node-link的頭指針(指向FP-tree中具有item-name對應(yīng)item-no的第一個結(jié)點)。項頭表中的項按照其出現(xiàn)頻度的降序排列。
　　OFP-tree與FP-tree不同之處主要在于：(1)FP-tree中的結(jié)點保存的是item-name，而OFP-tree中的結(jié)點保存的是item-no，在輸出模式時才將item-no換成item-name。(2)FP-tree中的結(jié)點是無序的，而OFP-tree中的結(jié)點是按照item-no從小到大的次序排列的。
　　3．2算法實例
　　例1設(shè)事務(wù)數(shù)據(jù)庫中的事務(wù)如表1所示，最小支持度閾值為3。
　　
　　表1一個事務(wù)數(shù)據(jù)庫示例

　　表2通過排序后得到的新數(shù)據(jù)庫D*
　　
　　
　　圖1事務(wù)數(shù)據(jù)庫D*對應(yīng)的OFP樹
　　
　　算法1：OFP-tree的建立
　　輸入：一個事務(wù)數(shù)據(jù)庫D及最小支持度閾值minsup
　　輸出：建立后的排序頻繁模式樹OFP-tree
　　方法：執(zhí)行以下步驟
　　（1） 掃描事務(wù)數(shù)據(jù)庫D一遍，獲得頻繁1-項集及其支持度信息，將頻繁1-項集按照支持度降序排列，記為L。
　　（2） 第二遍掃描D，將trans中的每個頻繁項按L中順序排列，并將項名用L中的序號替換，不存在的項用0來補位。
　　（3） 將替換好的所有事務(wù)按實數(shù)大小排序，得到一個新的數(shù)據(jù)庫D*。
　　（4） 創(chuàng)建SFP-tree的根結(jié)點T，記為“null”，對于D*中的每個trans執(zhí)行如下操作：
　　○1設(shè)排列后的結(jié)果為［p|P］,其中p是第一個項目,而P是剩余項目列表;
　　○2調(diào)用insert_tree([p|P],T),如果T沒有子結(jié)點，則N.item-no=p,N.count=1,N的父結(jié)點鏈指向T;否則,將p與T的最右子結(jié)點進行比較，如果N.item-no=p，則N的計數(shù)加1，否則，創(chuàng)建一個新結(jié)點N，使N.item-no=p,N.count=1，將T的last-link指向N，N的父結(jié)點鏈指向T。
　　○3如果新加入了結(jié)點N，則將N插入到項頭表中第p個元素的相同結(jié)點鏈表的末尾.
　　○4如果P非空，則遞歸調(diào)用insert-tree(P,N)。
　　需要指出的是：在OFP-tree中，由于相同父結(jié)點的子結(jié)點是有序的，在加入新結(jié)點時只需要比較最右子結(jié)點的item-no，而FP-tree則需要比較所有結(jié)點。所以，OFP-tree加入一個新結(jié)點的時間大大降低。而且，item-no就是該項在項頭表中的位置，不需要進行查找。
　　算法2：OFP-growth
　　輸入：建成的OFP-tree及minsup
　　輸出：調(diào)用OFP-growth(OFP-tree,null)
　　方法：調(diào)用OFP-growth(OFP-tree,null)
　　ProcedureOPF-growth(T,a)
　　{
　　(1) if樹T包含單一路徑P
　　(2) then對路徑P中的任一項集組合β，輸出項集βα(轉(zhuǎn)換為item-name)，項集支持度取β中結(jié)點的最小支持度
　　(3) else{
　　(4) for(i=n;i>=0;i--)//n為項頭表的長度減1
　　(5) {β=且sup(β)=sup(i);
　　(6) 構(gòu)造β的條件FP-treeTβ;
　　(7) ifTβ≠φthencallSFP-growth(Tβ,β);
　　(8) }}}
　　從以上算法可以看出，在插入一個新的結(jié)點時，不需要再從項頭表的第一項開始比較，將相同項名的結(jié)點鏈相連，只需要根據(jù)序號就可以很快的找到所要鏈接的結(jié)點位置。同時在新數(shù)據(jù)庫的基礎(chǔ)上，可以不必逐個比較該父結(jié)點的各子結(jié)點是否與要插入的結(jié)點相同，只需比較最后插入的結(jié)點即可。這樣就大大減少了頻繁模式樹的創(chuàng)建時間。在這兩方面，該算法較原算法有了一定的提高。
　　4結(jié)論
　　通過對頻繁模式增長算法的詳細了解，可以看出該算法具有以往算法所不具備的優(yōu)點，但是它也同樣存在一些缺陷。比如在FP－growth算法中，絕大部分時間主要是消耗在FP－tree及條件FP－tree的構(gòu)造與遍歷上，雖然本文對創(chuàng)建樹的算法進行了一些改進，但是仍然存在很大的改進空間。
　　參考文獻
　　[1]劉喜蘋.基于Fp-growth算法的關(guān)聯(lián)規(guī)則挖掘算法研究與應(yīng)用[D].湖南:湖南大學(xué),2006:1
　　[3]安穎.基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法研究[D].北京:北京工業(yè)大學(xué),2009:18
　　[4]范明,孟小峰.數(shù)據(jù)挖掘概念與技術(shù)[M].北京:機械工業(yè)出版社,2007.3:155~156.
　　[6]胡可云,田鳳占,黃厚寬.數(shù)據(jù)挖掘理論與應(yīng)用[M].北京:清華大學(xué)出版社；北京交通大學(xué)出版社,2008.4:115~120.