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

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

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

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

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

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

[關鍵詞]數(shù)據(jù)挖掘；FP-tree；最大頻繁項集；關聯(lián)規(guī)則

0引言

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

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

1相關知識

1.1FP-tree結構

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

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

圖1　事務數(shù)據(jù)庫DB對應的FP-tree

TID事務數(shù)據(jù)庫頻繁項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挖掘算法的現(xiàn)狀

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

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

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

2MMFI算法

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

2.1有序FP-tree

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

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

圖2　有序FP-tree

2.2有序FP-tree的性質

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

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

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

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

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

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

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

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

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

2.3預剪枝策略

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

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

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

2.4MMFI算法及流程

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

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

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

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

(2)若support(p)

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

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

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

(1)輸入：事務數(shù)據(jù)庫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路徑上所有節(jié)點tag域為F;

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

(12)if(Ipj?Ip){

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

(14)Ip添加到MFS;}

}

else{//Ip不是MFI

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

(16)if(Ipj?Ip){

(17)令Ip所有節(jié)點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的節(jié)點){

(23)if(Ipi?Ip)

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

(25)p=p→next;}

}

}

}.

2.5MMFI算法實例

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

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

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

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

3算法性能分析

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

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

圖3　mushroom數(shù)據(jù)集

圖4　chess數(shù)據(jù)集

4結束語

頻繁項集的獲取是發(fā)現(xiàn)事務間關聯(lián)規(guī)則的前提和關鍵，將挖掘頻繁項集轉化為挖掘MFI能夠降低算法的時間復雜度.相對于傳統(tǒng)基于FP-tree的挖掘算法，MMFI算法不但避免了遞歸建立條件頻繁模式樹和超集檢測的步驟，所提出的預剪枝策略也提高了算法執(zhí)行的效率.同時，MMFI算法需要在同一層節(jié)點鏈上進行多次循環(huán)遍歷，在一定程度上增加了算法的復雜程度，這也是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]錢雪忠，惠亮.關聯(lián)規(guī)則中基于降維的最大頻繁模式挖掘算法[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

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

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

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

[文獻標志碼]A

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