基于有序FP-tree的最大頻繁項集挖掘算法

李少華，呂志旺，車德勇，周　寧

(1.東北電力大學能源與動力工程學院，吉林 吉林 132012；2.東北電力大學信息工程學院，吉林 吉林 132012)

基于有序FP-tree的最大頻繁項集挖掘算法

李少華1，呂志旺2，車德勇1，周寧2

(1.東北電力大學能源與動力工程學院，吉林 吉林 132012；2.東北電力大學信息工程學院，吉林 吉林 132012)

[摘要]通過分析有序FP-tree與MFI之間的關聯關系，提出一種高效的MFI挖掘算法(MMFI)，使其在挖掘過程中不但避免了條件頻繁模式樹的構建，也省略了超集檢測的過程.提出了兩種預剪枝策略，該策略能夠有效地縮短算法執行的時間復雜度.結合理論分析和實驗數據發現MMFI算法比傳統算法快速、合理.

[關鍵詞]數據挖掘；FP-tree；最大頻繁項集；關聯規則

0引言

R.Agrawal和R.Srikant[1]提出了為布爾型關聯規則挖掘頻繁項集的Apriori算法.隨后J.Han[2]將所要挖掘的事務數據庫DB轉化為FP-tree 結構，并設計了FP-Growth算法.FP-Growth和Apriori都是用于發現事務數據庫中的全部頻繁項，造成了算法的執行過程耗時較長.因此提出將挖掘頻繁項集的問題轉化為挖掘MFI.一方面是由于MFI集合中包括了所有的頻繁項；另一方面由于MFI的數量遠遠低于頻繁項的數量.然而，目前對于MFI的挖掘過程普遍存在以下問題：(1)需要遞歸構建條件模式樹，增加了算法的時間復雜度；(2)算法對每次求出的頻繁項需要檢測其是否為MFI(超集檢測).在項集數量較大、事務條數較多的情況下，以上2個問題的耗時會占整個挖掘過程的絕大部分時間，因此降低了算法的執行效率.

本文通過對文獻[3]提出的有序FP-tree的結構進行了改進，總結并分析出了該樹型結構的相關性質.提出了一種新的MFI挖掘算法——MMFI (mining maximal frequent itemset)算法.有序FP-tree作為對傳統FP-tree結構的一種改進，使得MMFI算法在挖掘MFI的過程中既能夠避免超集檢測，也無須建立條件模式樹.

1相關知識

1.1FP-tree結構

FP-tree是J.Han[2]等人提出的一種樹型結構，用于存儲事物數據庫中滿足最小支持度的頻繁項集，且該樹型結構仍保留各項集間的關聯關系.項集在該樹型結構體現為任意節點到根節點的節點集合，同時在各節點中存儲對應項集的支持度數.

為便于對樹的遍歷需創建頭表，頭表用于存儲頻繁項和支持度計數，將樹中相同的頻繁項用指針鏈從左到右依次鏈接在一起，其中鏈頭指針存儲在頭表中.下面給出了構建FP-tree的例子，表1列出了事務數據庫以及滿足min_sup2的頻繁項，圖1為事務數據庫DB對應的FP-tree.

圖1　事務數據庫DB對應的FP-tree

TID事務數據庫頻繁項1a,c,fc,a2c,gc3a,c,ec,a,e4c,d,kc,d5a,c,d,oc,d,a6a,e,pa,e7c,d,e,hc,d,e8b,c,d,e,nc,d,e,b9d,e,td,e10a,b,d,md,a,b11a,c,d,qc,d,a

1.2MFI挖掘算法的現狀

當前已經比較成熟的MFI挖掘算法主要有MaxMiner[4]、DMFIA[5]、MAFIA[6]和FP-Max[7]等.由Bayardo等人提出的MaxMiner算法運用“look-ahead”的超集剪枝策略，在一定程度上有效地壓縮了算法的搜索空間，但是在生成無用候選項集和多次遍歷數據庫的過程中影響了算法的執行效率；Burdick等提出的MAFIA算法結合縱向位圖與動態重排序技術進行空間剪枝，算法性能較好，但也需要多次掃描事務數據庫；宋余慶等人通過對MaxMiner算法進行了改進，提出DMFIA算法，只需掃描數據庫2次且沒有產生條件模式基，但是也會產生大量的頻繁項集候選項.

基于FP-tree的FP-Max算法需多次遞歸建立條件模式樹，當挖掘對象為稠密型數據時會產生大量的冗余遞歸過程，耗費大量存儲空間.近年來，國內學者對FP-Max和DMFIA算法進行了改進，提出了BDRFI[8]和NCFP-Max[9]等算法.BDRFI算法通過建立數字頻繁模式樹以提高超集檢驗效率，同時采用自下而上的搜索策略，但算法也會生成大量的候選項集.NCFP-Max算法雖然能夠避免超集檢測，但是在避免遞歸生成條件模式樹的過程中需對所有路徑求其交集，耗時較長.

綜上所述，目前的MFI挖掘算法普遍存在以下問題：(1)多次遍歷數據庫；(2)遞歸建立條件模式樹；(3)超集檢測.

2MMFI算法

MMFI算法是通過沿有序FP-tree頭表中的節點鏈對樹中的節點進行遍歷以挖掘事務數據庫DB中隱藏的MFI.在挖掘的過程中既不用遞歸的構建條件頻繁模式樹，也避免了將求出的項集進行超集監測的過程.

2.1有序FP-tree

MMFI算法依據MFI的任何真子集都不是利用MFI的基本性質對有序FP-tree進行挖掘，使得在算法執行過程中僅生成MFI.為實現MMFI算法需要建立有序FP-tree，其具體的構建過程已經被提出[3].

圖2表示由表1中滿足min_sup2的項構成的有序FP-tree.同時在該樹型結構頭表中添加了一個num域，用于記錄各頻繁項位于FP-tree中的層次(最左側節點).

圖2　有序FP-tree

2.2有序FP-tree的性質

設Ipi表示從任意非根節點pi到根節點的所有節點組成的集合，則有序FP-tree具有2種性質.

性質1設pi和pj為有序FP-tree對應頭表中2個頻繁項且pi在pj的下方，那么Ipi可能為Ipj的超集，但一定不是Ipj的子集.

證明在頭表中所有頻繁項從上到下依據支持度按遞減順序排列，若pi和pj同時出現在有序FP-tree的一個分支上，且在頭表中pi位于pj下方，則pi必為pj的子孫節點，因此性質1成立.證畢.

性質2設為有序FP-tree頭表中的項，若有序FP-tree中有模式(其中i≤n)，那么該頻繁模式一定處于有序FP-tree最左側分枝.

證明設〈p1，p2，…，pi〉是有序FP-tree中的一個MFI，根據文獻[3]中有序FP-tree的構建過程可知，節點p1一定是樹根的最左側孩子，同理節點p2一定是節點p1的最左側孩子，如此進行下去，節點pi必是節點pi-1的最左側孩子，因此〈p1，p2，…，pi〉一定是FP-tree的最左邊的分枝.證畢.

結合上文對有序FP-tree性質的分析，以pi為后綴的MFI必然是下面情形之一：

(1)Ipi可能是最大頻繁項集；

(2)pi右側的兄弟節點中存在pj且滿足Ipj?Ipi，則Ipj可能是MFI；

(3)在兄弟鏈表中存在節點pi，pj，…，pk，且Ipi，Ipj，…，Ipk互不包含，則Ipi，Ipj，…，Ipk的最大化交集為MFI.

2.3預剪枝策略

基于有序FP-tree的MMFI算法的基本思想采用自下而上依次處理頭表中各個節點所指節點鏈，同一層節點鏈沿FP-tree從左到右的順序進行遍歷.為提高算法的挖掘效率，結合有序FP-tree的性質，采取預剪枝策略.

(1)當頭表中任意節點p的num域的值等于該節點在頭表中的層次且為p.count≥min_sup時，算法終止.

(2)對于樹中任意非根節點p，其tag域初始值為T；定義p.tag=T表示Ip可能為MFI，p.tag=f表示Ip肯定不是MFI.如果Ip為MFI，那么Ip的任何子集都不可能是MFI，因此可將Ip中所有節點的tag域標記為f.當遍歷的節點滿足p.tag=f時可以直接跳過，從而避免超集檢測的過程.

2.4MMFI算法及流程

結合本文提出的有序FP-tree的性質以及最大頻繁項可能出現的情況，從頭表最底端節點指針域所指節點鏈開始挖掘.

(1)如果support(p)≥min_sup則Ip是MFI，將Ip存入MFS(最大頻繁項集集合)后分2種情況分別處理：

(A)如果節點p是節點鏈的首節點且所在頭表的層次等于num域的值，則Ip為剩余所有項的最大頻繁項(由性質2可知)，算法結束并輸出MFS；

(b)否則將該節點的所有祖先節點標記為不可挖掘，并沿鏈表向右側搜索Ip的子集，并標記為不可挖掘.

(2)若support(p)

(A)若在節點鏈右側有pj滿足Ipj為Ip的子集，則執行Ipj.count=Ip.count+Ipj.count.

(b)若節點鏈右側有pj且Ipj不是Ip的子集；令Ipk=IpIpj，如果Ipk非空，按照有序FP-tree的構造規則將Ipk添加到兄弟鏈表中.其count域的值為Ipk.count=Ip.count+Ipj.count.

結合以上分析，MMFI算法偽代碼執行過程具體如下：

(1)輸入：事務數據庫DB和min_sup

(2)輸出：MFS

(3)for(p=tb_pos;tb_pos≥0;tab_pos--){

(4)p=tb[tb_pos].node_link

(5)if(p.count>min_sup&&tb[tb_pos].num==tb_pos)

(6){輸出MFS;算法結束;}

else{

(7)while(p≠null){

(8)if(p.tag==T){//Ip可能是MFI

(9)if(p.count≥min_sup)//Ip是MFI

(10){Ip路徑上所有節點tag域為F;

(11)while(節點鏈右側tag=T的節點)

(12)if(Ipj?Ip){

(13)令Ipj所有節點tag=F;

(14)Ip添加到MFS;}

}

else{//Ip不是MFI

(15)搜索節點鏈右側tag=T的節點;

(16)if(Ipj?Ip){

(17)令Ip所有節點tag=F;

(18)pj.count+=p.count;}

else

(19){Ipk=Ip∩Ipj;

(20)Ipk.count=Ip.count+Ipj.count;

(21)將Ipk添加到兄弟鏈表中;}

}

}

else{//Ip及其子集都不是MFI

(22)while(向右側搜索tag=T的節點){

(23)if(Ipi?Ip)

(24)將pi及其祖先節點tag標記為F;

(25)p=p→next;}

}

}

}.

2.5MMFI算法實例

MMFI算法的挖掘過程(見圖3)：首先沿項頭表b節點所指節點鏈開始遍歷，由于{c，d，e，b:1}和{d，A，b:1}均不滿足最小支持度且互不包含，取其最大化交集{d，b:2}滿足支持數，因此以b為后綴的MFI為{d，b:2}.

當沿節點e所指節點鏈遍歷時，項集{c，d，e:2}滿足最小支持數，又由于{A，e:1}是{c，A，e:1}的子集故轉移支持數生成{A，e:2}，因此以e為后綴的MFI為{c，d，e:2}、{A，e，:2}.

當沿節點A所指節點鏈遍歷時，由于鏈表num域的值等于節點A在頭表中的層次且該節點滿足最小支持數，故以A為后綴的MFI為{c，d，A:2}，算法結束.

綜上圖3所隱藏的最大頻繁項集集合MFS={{d，b:2}，{c，d，e:2}，{A，e:2}，{c，d，A:2}}.

3算法性能分析

為驗證MMFI算法的可行性，通過實驗數據將其與FP-max算法進行對比分析.實驗測試環境：CPU為T4200 2.0 GHz，操作系統為Win7，內存為2 GB的PC機.通過Java語言實現了FP-max 和MMFI算法，實驗對象為由文獻[10]提供的國際象棋數據(chess.dat)和蘑菇數據(mushroom.dat)2個密集型數據集.

圖3和4分別表示2種算法在mushroom(含有8 124個事務)和chess.dat(含有3 196個事務)數據集上采用不同支持度時的性能對比結果.實驗表明，在挖掘MFI時MMFI的挖掘效率優于FP-max算法.

圖3　mushroom數據集

圖4　chess數據集

4結束語

頻繁項集的獲取是發現事務間關聯規則的前提和關鍵，將挖掘頻繁項集轉化為挖掘MFI能夠降低算法的時間復雜度.相對于傳統基于FP-tree的挖掘算法，MMFI算法不但避免了遞歸建立條件頻繁模式樹和超集檢測的步驟，所提出的預剪枝策略也提高了算法執行的效率.同時，MMFI算法需要在同一層節點鏈上進行多次循環遍歷，在一定程度上增加了算法的復雜程度，這也是MMFI算法需要進一步解決的問題.

[參考文獻]

[1]AGRAWAL R，IMIELINSKI T，SWAMI A.Mining association rules between sets of items in large databases[C]// Proceedings of the ACM SIGMOD inter-national conference management of date，Washington：ACM，1993:207-216.

[2]HAN J，PEI J.Mining frequent patterns without candidate generation[C]// Proceeding of the ACM SIGMOD International Conference on Management of Data，Dallas：ACM，2000，29:1-12.

[3]陳晨，鞠時光.基于改進FP-tree的最大頻繁項集挖掘算法[J].計算機工程與設計，2008，24：6236-6239.

[4]BAYARDO J，ROBERTO J.Efficiently mining long patterns from databases[C]// Proceeding of 1998 ACM SIG-MOD International Conference on Management of Data，New York：ACM，1998:85-93.

[5]宋余慶，朱玉全，孫志揮，等.基于FP-Tree的最大頻繁項目集挖掘及更新算法[J].軟件學報，2003(9):1586-1592.

[6]BURDICK D，CALIMLIM M.MAFIA：a maximal frequent itemset algorithm[J].IEEE Transactions on Knowledge and Data Engineering，2005(11)：1490-1504.

[7]GRAHNE G，ZHU J.High performance mining of maximal frequent itemsets[EB/OL].(2014-07-06)[2015-07-20].http://www.docin.com/p-773109811.html.

[8]錢雪忠，惠亮.關聯規則中基于降維的最大頻繁模式挖掘算法[J].計算機應用，2011，31(5):1339-1343.

[9]趙志剛，王芳.基于OWSFP-Tree的最大頻繁項目集挖掘算法[J].計算機工程與設計，2013，34(5):1687-1690.

[10]BART GOETHALS.Frequent itemset mining implementations repository [DB/OL].(2004-09-03)[2015-07-20].http://fimi.ua.ac.be.

(責任編輯：石紹慶)

Algorithm for mining maximal frequent itemset based on ordered FP-tree

LI Shao-hua1，Lü Zhi-wang2，CHE De-yong1，ZHOU Ning2

(1.Institute for Energy and Power Engineering，Northeast Dianli University，Jilin 132012，China；2.Institute for Information Engineering，Northeast Dianli University，Jilin 132012，China)

Abstract:A new algorithm MMFI (mining maximalfrequent itemset)for efficiently mining maximal frequent itemset is proposed through analyzing the relationship of the ordered FP-tree and MFI.In the algorithm neither constructing conditional frequent pattern tree nor superset checking is needed.Also proposed two pre-pruning strategies can effectively reduce the time of the algorithm executed.It is proved by theoretical analysis and experimental comparison that the algorithm is fast and reasonable.

Keywords:data mining；FP-tree；maximal frequent itemsets；association rules

[文章編號]1000-1832(2016)02-0065-05

[收稿日期]2015-08-11

[基金項目]吉林省科技發展計劃項目(20140307022GX).

[作者簡介]李少華(1957—)，男，教授，博士研究生導師，主要從事數據挖掘、信息融合，數字電站系統等研究.

[中圖分類號]TP 311[學科代碼]

[文獻標志碼]A

[DOI]10.16163/j.cnki.22-1123/n.2016.02.015