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

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

基于有序FP-tree的最大頻繁項(xiàng)集挖掘算法

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

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

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

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

0引言

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

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

1相關(guān)知識(shí)

1.1FP-tree結(jié)構(gòu)

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

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

圖1　事務(wù)數(shù)據(jù)庫(kù)DB對(duì)應(yīng)的FP-tree

TID事務(wù)數(shù)據(jù)庫(kù)頻繁項(xiàng)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)狀

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

基于FP-tree的FP-Max算法需多次遞歸建立條件模式樹，當(dāng)挖掘?qū)ο鬄槌砻苄蛿?shù)據(jù)時(shí)會(huì)產(chǎn)生大量的冗余遞歸過程，耗費(fèi)大量存儲(chǔ)空間.近年來，國(guó)內(nèi)學(xué)者對(duì)FP-Max和DMFIA算法進(jìn)行了改進(jìn)，提出了BDRFI[8]和NCFP-Max[9]等算法.BDRFI算法通過建立數(shù)字頻繁模式樹以提高超集檢驗(yàn)效率，同時(shí)采用自下而上的搜索策略，但算法也會(huì)生成大量的候選項(xiàng)集.NCFP-Max算法雖然能夠避免超集檢測(cè)，但是在避免遞歸生成條件模式樹的過程中需對(duì)所有路徑求其交集，耗時(shí)較長(zhǎng).

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

2MMFI算法

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

2.1有序FP-tree

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

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

圖2　有序FP-tree

2.2有序FP-tree的性質(zhì)

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

性質(zhì)1設(shè)pi和pj為有序FP-tree對(duì)應(yīng)頭表中2個(gè)頻繁項(xiàng)且pi在pj的下方，那么Ipi可能為Ipj的超集，但一定不是Ipj的子集.

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

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

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

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

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

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

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

2.3預(yù)剪枝策略

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

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

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

2.4MMFI算法及流程

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

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

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

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

(2)若support(p)

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

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

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

(1)輸入：事務(wù)數(shù)據(jù)庫(kù)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;算法結(jié)束;}

else{

(7)while(p≠null){

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

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

(10){Ip路徑上所有節(jié)點(diǎn)tag域?yàn)镕;

(11)while(節(jié)點(diǎn)鏈右側(cè)tag=T的節(jié)點(diǎn))

(12)if(Ipj?Ip){

(13)令I(lǐng)pj所有節(jié)點(diǎn)tag=F;

(14)Ip添加到MFS;}

}

else{//Ip不是MFI

(15)搜索節(jié)點(diǎn)鏈右側(cè)tag=T的節(jié)點(diǎn);

(16)if(Ipj?Ip){

(17)令I(lǐng)p所有節(jié)點(diǎn)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(向右側(cè)搜索tag=T的節(jié)點(diǎn)){

(23)if(Ipi?Ip)

(24)將pi及其祖先節(jié)點(diǎn)tag標(biāo)記為F;

(25)p=p→next;}

}

}

}.

2.5MMFI算法實(shí)例

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

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

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

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

3算法性能分析

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

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

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

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

4結(jié)束語(yǔ)

頻繁項(xiàng)集的獲取是發(fā)現(xiàn)事務(wù)間關(guān)聯(lián)規(guī)則的前提和關(guān)鍵，將挖掘頻繁項(xiàng)集轉(zhuǎn)化為挖掘MFI能夠降低算法的時(shí)間復(fù)雜度.相對(duì)于傳統(tǒng)基于FP-tree的挖掘算法，MMFI算法不但避免了遞歸建立條件頻繁模式樹和超集檢測(cè)的步驟，所提出的預(yù)剪枝策略也提高了算法執(zhí)行的效率.同時(shí)，MMFI算法需要在同一層節(jié)點(diǎn)鏈上進(jìn)行多次循環(huán)遍歷，在一定程度上增加了算法的復(fù)雜程度，這也是MMFI算法需要進(jìn)一步解決的問題.

[參考文獻(xiàn)]

[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]陳晨，鞠時(shí)光.基于改進(jìn)FP-tree的最大頻繁項(xiàng)集挖掘算法[J].計(jì)算機(jī)工程與設(shè)計(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的最大頻繁項(xiàng)目集挖掘及更新算法[J].軟件學(xué)報(bào)，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]錢雪忠，惠亮.關(guān)聯(lián)規(guī)則中基于降維的最大頻繁模式挖掘算法[J].計(jì)算機(jī)應(yīng)用，2011，31(5):1339-1343.

[9]趙志剛，王芳.基于OWSFP-Tree的最大頻繁項(xiàng)目集挖掘算法[J].計(jì)算機(jī)工程與設(shè)計(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.

(責(zé)任編輯：石紹慶)

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

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

[收稿日期]2015-08-11

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

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

[中圖分類號(hào)]TP 311[學(xué)科代碼]

[文獻(xiàn)標(biāo)志碼]A

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