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

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