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

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