趙 陽，白 凡

(江南計算技術(shù)研究所，江蘇 無錫 214083)

基于FP-tree的支持度計數(shù)優(yōu)化策略

趙 陽，白 凡

(江南計算技術(shù)研究所，江蘇 無錫 214083)

關(guān)聯(lián)規(guī)則挖掘過程中，頻繁項集的挖掘是最關(guān)鍵的步驟。最大頻繁項集是最常用的頻繁項集簡化表示?；贔P-tree的最大頻繁項集挖掘算法多數(shù)都需要自底向上地搜索FP-tree來計算項集的支持度。而已有的支持度計算方法在計算當(dāng)前項集的支持度時沒有考慮已完成的支持度計算過程所獲得的信息，因而造成了不必要的開銷。針對該問題，提出了基于FP-tree的支持度計數(shù)優(yōu)化策略(Support Count Optimization Method on FP-tree,SCOM)，在付出很小的額外空間代價的條件下，充分利用已完成的支持度計數(shù)過程中獲取的路徑對項集的支持信息和項集之間的關(guān)系進(jìn)行搜索剪枝，并設(shè)計實驗將該策略應(yīng)用到DMFIA算法上。實驗結(jié)果表明，應(yīng)用該策略的最大頻繁項集挖掘算法DMFIA獲得了較大的性能提升。SCOM對基于FP-tree的支持度計數(shù)進(jìn)行優(yōu)化，因此能夠應(yīng)用到所有利用FP-tree進(jìn)行支持度計數(shù)的算法之中。

關(guān)聯(lián)規(guī)則挖掘；FP-tree；最大頻繁項集；支持度計數(shù)；搜索剪枝

0 引 言

關(guān)聯(lián)規(guī)則的概念是由Agrawal等提出的[1-2],反映了大量數(shù)據(jù)中項目集之間有趣的關(guān)聯(lián)或相關(guān)關(guān)系。頻繁項集挖掘是關(guān)聯(lián)規(guī)則挖掘中最關(guān)鍵的一步。實踐中，由事務(wù)數(shù)據(jù)集產(chǎn)生的頻繁項集的數(shù)量可能非常大，因此，從中識別出可以推導(dǎo)出其他所有頻繁項集的、較小的、具有代表性的項集是有用的。由于最大頻繁項目集中已經(jīng)隱含了所有頻繁項目集,所以可把發(fā)現(xiàn)頻繁項目集的問題轉(zhuǎn)化為發(fā)現(xiàn)最大頻繁項目集的問題。另外,某些數(shù)據(jù)挖掘應(yīng)用僅需發(fā)現(xiàn)最大頻繁項目集,而不必發(fā)現(xiàn)所有的頻繁項目集,因而發(fā)現(xiàn)最大頻繁項目集對數(shù)據(jù)挖掘具有重大意義[3]。

頻繁模式樹(Frequent Patten tree,FP-tree)是由Han等提出的對于事務(wù)數(shù)據(jù)集的一種壓縮存儲方式[4]。基于FP-tree的算法可以避免Apriori系列算法需要多次讀取事務(wù)數(shù)據(jù)集而造成的額外開銷。目前，基于FP-tree的最大頻繁項集挖掘算法主要有FP-Max[5]，DMFIA[3]，IDMFIA[6]，F(xiàn)PMFI[7]，BDRFIA[8]，等等。FP-Max與FP-growth類似，通過遞歸構(gòu)建FP-tree的方式挖掘頻繁項集，用超級檢驗的方法保證最終結(jié)果是最大頻繁項集。DMFIA是一種自頂向下的最大頻繁項集挖掘算法，與FP-Max相比，其無需遞歸生成FP-tree，對于最大頻繁項集維度較大的數(shù)據(jù)效果較好；IDMFIA是在DMFIA基礎(chǔ)上提出的雙向搜索算法，充分利用了低維項集信息進(jìn)行剪枝，擴(kuò)大了算法的適用數(shù)據(jù)范圍；FPMFIA使用基于投影的方法減少了超集檢測的時間；BDRFI則改進(jìn)FP-tree為DFP-tree(Digital Frequent Patten tree，數(shù)字頻繁模式樹)，運(yùn)用多種預(yù)測剪枝策略，快速降低候選項集維度，減少了超級檢測的時間。調(diào)研中還發(fā)現(xiàn)各文獻(xiàn)對于“自頂向下”和“自底向上”的項集空間搜索的定義較為混亂[9-11]，因此文中的“自頂向下”的項集空間搜索特指從高維項集到低維項集的搜索。

上述基于FP-tree的最大頻繁項集挖掘算法中多數(shù)都需要通過遍歷FP-tree或其子樹來計算項集的支持?jǐn)?shù)，以避免多次掃描數(shù)據(jù)庫或遞歸生成條件FP-tree。但是在項集支持度計數(shù)的過程中，沒有充分利用在計算之前的項集支持度時所獲得的信息，因而造成了不必要的檢索開銷。針對該問題，提出了基于FP-tree的支持度計數(shù)優(yōu)化策略(Support Count Optimization Method on FP-tree,SCOM)。根據(jù)集合的性質(zhì)，在搜索FP-tree計算項集的支持度時，記錄路徑對項集的支持信息，以達(dá)到減少搜索路徑數(shù)的目的；并以DMFIA算法為例，應(yīng)用該策略對算法進(jìn)行改進(jìn)，并設(shè)計實驗進(jìn)行驗證。

1 相關(guān)知識

1.1相關(guān)定義和性質(zhì)

設(shè)I={i1,i2,…,im}是由m個項組成的集合，D是由一組事務(wù)組成的事務(wù)數(shù)據(jù)集且D中事務(wù)都由I中的項組成。給定項集X?I,X在D中的支持?jǐn)?shù)是指D中包含X的事務(wù)數(shù)，X在D中的支持度是指X的支持?jǐn)?shù)占D中所有事務(wù)數(shù)的百分比。

定義1：對于項集X?I,若X在D中的支持度sX大于等于給定的最小支持度s,則稱項集X為事務(wù)數(shù)據(jù)集D在最小支持度s下的頻繁項集；反之，則稱項集X為事務(wù)數(shù)據(jù)集D在最小支持度s下的非頻繁項集。

定義2：對于項集X?I,給定最小支持度s,若X的所有超集都是非頻繁項集，則稱項集X為事務(wù)數(shù)據(jù)集D在最小支持度s下的最大頻繁項集。

設(shè)R={n1,n2,…,nm}為由事務(wù)數(shù)據(jù)集D生成的FP-tree中的一條路徑，所有項集和路徑都是按照支持度降序排列的。

性質(zhì)1：對于項集X,若X?R,則?Y?X,Y?R且?R'?R,X?R'；若X?R,則?Y?X,Y?R且?R'?R,X?R'。

證明：根據(jù)集合的性質(zhì)容易得證。

對于項集X,Y?X且Y的最后一項為ei，R'為R的以ei結(jié)尾的前綴子路徑。

性質(zhì)2：若X?R,則必有Y?R'；若Y?R',則必有X?R。

證明：若X?R,由于所有項集和路徑都是按照支持度降序排列的，則對于X的以ei為結(jié)尾的前綴子集X',必有X'?R'，而Y?X'，故Y?R',同理可證若Y?R',則必有X?R,證畢。

1.2FP-tree與DMFIA

FP-tree是一種輸入數(shù)據(jù)的壓縮表示法，它通過逐個讀入事務(wù)，并把每個事物映射到FP-tree中的一條路徑來構(gòu)造。由于不同的事物可能會有若干個相同的項，因此它們的路徑可能部分重疊。路徑相互重疊越多，使用FP樹結(jié)構(gòu)獲得的壓縮效果越好。如果FP-tree足夠小，能夠存放在內(nèi)存之中，就可以直接從這個內(nèi)存中的結(jié)構(gòu)提取頻繁項集，而不必重復(fù)掃描存放在硬盤上的數(shù)據(jù)。

在FP-tree中，每個節(jié)點由4個域組成[12]:節(jié)點名稱item-name、節(jié)點計數(shù)item-count、節(jié)點鏈item-link(用于指向樹中具有相同item-name的下一個節(jié)點)，及父節(jié)點指針item-parent。同時為方便樹的遍歷，F(xiàn)P-tree還包含一個頻繁項頭表Htable，它由兩個域組成:項目名稱item-name和指向FP-tree中具有相同item-name的首節(jié)點指針head of node-link。

為了獲得較好的壓縮效果，通常需要將事務(wù)中的項按照支持度降序排列，盡管這樣得到的FP-tree并不一定是最小的[13]。通過兩次掃描數(shù)據(jù)集來構(gòu)造FP-tree：

(1)第一次掃描數(shù)據(jù)集，確定每個項的支持度計數(shù)，丟棄非頻繁項；按照支持度降序構(gòu)建頻繁項頭表Headers，創(chuàng)建FP-tree的根節(jié)點，標(biāo)記為“null”；

(2)第二次掃描數(shù)據(jù)集，對于每個事務(wù)Trans，根據(jù)項的支持度降序排列。令當(dāng)前節(jié)點為根節(jié)點，順序遍歷Trans中的項，若當(dāng)前節(jié)點包含與該項同名的子節(jié)點，則該子節(jié)點計數(shù)加1，當(dāng)前節(jié)點變?yōu)樵撟庸?jié)點；否則，創(chuàng)建當(dāng)前節(jié)點的新的子節(jié)點，item-name=當(dāng)前項的名稱，item-count=1，item-parent指向當(dāng)前節(jié)點，Headers中同名鏈表的尾節(jié)點的item-link指向該子節(jié)點。直到遍歷完數(shù)據(jù)集中所有的事務(wù)，F(xiàn)P-tree構(gòu)建完成。

文獻(xiàn)[9]提出了FP-tree的一種改進(jìn)—數(shù)字頻繁模式樹(DFP-tree)，用頻繁項降序排列后的序號代替名稱，有利于提高超集檢測的效率。

DMFIA采用FP-tree的存儲結(jié)構(gòu)和自頂向下的搜索策略。它采用雙重循環(huán)的方式挖掘最大頻繁項集，外層循環(huán)是在MFCS非空狀態(tài)下進(jìn)行，內(nèi)層循環(huán)以自底向上的方式進(jìn)行處理，若MFCS中項集的支持度大于等于最小支持度閾值，則將該項集加入到最大頻繁項集(Maximum Frequent Sets，MFS)中;對非頻繁項集，通過循環(huán)每次刪除該項集中的一個項來產(chǎn)生新的候選項集，對于新的候選項集需要判斷在MFS和MFCS中是否存在超集，若不存在則將其加入MFCS中，否則將其刪除。

2 SCOM

2.1主要思想

SCOM策略的主要思想是：在搜索FP-tree計算候選項集的支持度時，記錄各個相關(guān)路徑的支持狀態(tài)；當(dāng)通過該項集生成新的候選項集時，根據(jù)性質(zhì)1、2將舊的項集的路徑支持信息傳遞給新的候選項集，這樣在計算新的候選項集的支持度時就可以剪除不必要的路徑與候選項集的匹配。SCOM策略理論上適用于所有的DMFIA同類算法。

2.2算法步驟

為了讓SCOM策略能夠較好地發(fā)揮優(yōu)勢，需要為FP-tree的每一個節(jié)點增加一個域item_num，用來記錄該節(jié)點在Headers中同名鏈表的序號，也就是在計算以該項結(jié)尾的候選項集的支持度時檢索的路徑序號；為每一個候選項集X增加一個二進(jìn)制向量標(biāo)記(binary vector)用以表示路徑對X的支持情況，記為X.bv。X.bv(i)表示X.bv的第i位，X.bv(i)=0表示路徑i不支持X,X.bv(i)=1表示路徑i支持X。

DMFIA同類算法計算最大頻繁項集的過程大致可分為如下幾個步驟：

(1)初始化候選項集集合；

(2)選取部分候選項集，計算支持度；

(3)將最大頻繁項集加入到結(jié)果集；

(4)通過非最大頻繁項集候選項集生成新的候選項集，通過“超級檢測”等策略篩選后，代替步驟(2)中候選項集加入到候選項集集合；

(5)重復(fù)步驟(2)～(4)直到候選項集集合為空。

SCOM策略主要體現(xiàn)在支持度計算(步驟(2))和新的候選項集生成(步驟(4))之中。支持度計算過程如下：

ProcedureComputeCount(FP-tree,Headers,m)

/*Headers為頻繁項頭表，m為待計算的最后一項為i的候選項集*/

begin

搜索項目頭表Htable的項目名稱域item-name,假設(shè)Htable[q1].item-name=i;

根據(jù)Htable[q1].head找到FP-tree中節(jié)點名稱為i的節(jié)點n1,n2,…,nh;

根據(jù)n1,n2,…,nh及其前綴節(jié)點的父節(jié)點指針域，找到包含i的所有路徑P1,P2,…,Ph;

for(j=1;j≤h;j++) do begin

ifm.bv的第j位為1 then//項集空間搜索方向為“自頂向下”時

m支持?jǐn)?shù)增加ndj.node-count，continue;//性質(zhì)1

/*

ifm.bv的第j位為0 then//項集空間搜索方向為“自底向上”時

continue;//性質(zhì)2

*/

if路徑Pj包含m,then//

m的支持?jǐn)?shù)增加ndj.node-count;

m.bv的第j位置1

end

end

對每個非最大頻繁項集候選項集m,設(shè)M'是由m生成的新的候選項集，則應(yīng)用SCOM策略的算法如下：

begin

for allm'∈M'do begin

ifm'與m的最后一項相同，then

m'.bv=m.bv;

else

ComputeBV(FP-tree,m,m');//由性質(zhì)2根據(jù)路徑的包含關(guān)系計算路徑支持信息

end

end

ProcedureComputeBV(FP-tree,Headers,m,m')

/*由性質(zhì)2根據(jù)已計算過路徑支持信息的m計算新的候選項集m'的路徑支持信息，I(0)表示全0的二進(jìn)制向量，|m.bv|表示m.bv的長度*/

/*針對“自頂向下”的項集空間搜索*/

begin

m'.bv=I(0);

fori=0 to |m.bv| do begin

ifm.bv(i)=0 then continue;

由Headers找到item_name=m末項名稱的第i個節(jié)點Ni;

ifNi存在item_name=m'末項名稱的祖先節(jié)點Nj,Nj.item_num=jthen

m'.bv(j)=1;

end

/*針對“自底向上”的項集空間搜索*/

begin

m'.bv=I(1);

fori=0 to |m.bv| do begin

ifm.bv(i)=1 then continue;

由Headers找到item_name=m末項名稱的第i個節(jié)點Ni；

ifNi存在item_name=m'末項名稱的子孫節(jié)點Nj,Nj.item_num=jthen

m'.bv(j)=0

end

2.3算法實例

舉例說明該策略的優(yōu)化過程。圖1為一棵數(shù)字頻繁模式樹。

圖1 數(shù)字頻繁模式樹

設(shè)X={2,3,5}為已經(jīng)計算過支持度的候選項集，則X.bv=(1,0)；Y1={2,5}，Y2={2,3}為“自頂向下”的項集空間搜索算法生成的新候選項集，Y3={2,3,5,6}為根據(jù)自底向上搜索算法生成的新候選項集，根據(jù)SCOM策略能夠快速得出Y1.bv=X.bv=(1,0)，由ComputeBV得Y2.bv=(1,0)，Y3.bv=(1,0,1)，則在計算Y1、Y2的支持度時，只需搜索item_name=6的第二條路徑，在計算Y3的支持度時，只需搜索第一條路徑與第三條路徑。

3 實驗結(jié)果

為了驗證SCOM策略的實際優(yōu)化效果，在8 G RAM，Intel Core i5-2430 M CPU 2.40 GHz，Windows7操作系統(tǒng)上用Java實現(xiàn)了DMFIA原算法和應(yīng)用了SCOM策略的DMFIA算法SCOM-DMFIA。實驗采用的測試數(shù)據(jù)集為mushroom，包含有8 124條記錄，記錄平均長度為23，共有115個蘑菇屬性。圖2為在不同最小支持度下(分為5%，10%，15%，20%，25%五檔)兩種算法的執(zhí)行時間對比結(jié)果。

圖2 mushroom數(shù)據(jù)集上兩種算法的執(zhí)行時間對比

從圖2可以看出，應(yīng)用了SCOM策略的DMFIA算法的整體運(yùn)行時間明顯少于原算法。為了進(jìn)一步說明SCOM策略通過優(yōu)化支持度計數(shù)進(jìn)而提高最大頻繁項集挖掘算法整體性能的過程，實驗中還監(jiān)測了兩種算法用于支持度計數(shù)的時間開銷，如圖3所示。

圖3 mushroom數(shù)據(jù)集上兩種算法用于支持度計數(shù)的時間對比

從圖3中可以看出，SCOM明顯降低了DMFIA算法用于支持度計數(shù)的時間。

以上實驗結(jié)果說明，SCOM策略的確能在基于FP-tree的支持度計數(shù)過程中減少搜索路徑，降低時間開銷，進(jìn)而提高整個最大頻繁項集挖掘算法的效率。

4 結(jié)束語

文中提出的基于FP-tree的支持度計數(shù)優(yōu)化策略—SCOM，通過記錄支持度計算過程中路徑對項集的支持情況，依據(jù)相關(guān)性質(zhì)在支持度計算中搜索FP-tree時避免不必要的搜索路徑，以達(dá)到搜索優(yōu)化的目的。實驗結(jié)果表明，該策略有效提高了最大頻繁項集挖掘算法DMFIA的運(yùn)行效率，并且可以推廣應(yīng)用到DMFIA的同類算法中。下一步的工作中將進(jìn)一步探究SCOM在其他種類頻繁項集挖掘算法中的適用性。

[1] Agrawal R， Imielinski T，Swami A． Mining association rules between sets of items in large database[C]//Proceedings of 1993 ACM SIGMOD conference on management of data．New York:ACM，1993:207-216．

[2] Han J, Kamber M. Data mining:concepts and techniques[M].Beijing:High Education Press,2001.

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

[4] Han J，Pei J，Yin Y．Mining frequent patterns without candidate generation[C]//Proceedings of the 2000 ACM-SIGMOD international conference on management of data．New York:ACM，2000:1-12．

[5] Grahne G，Zhu J．High performance mining of maximal frequent itemset[EB/OL]．[2014-07-06]．http://www．docin．com/p-773109811．html．[6] 吉根林，楊 明，宋余慶，等．最大頻繁項目集的快速更新[J]．計算機(jī)學(xué)報，2005，28(1):128-135．

[7] 顏躍進(jìn)，李舟軍，陳火旺．基于FP-Tree有效挖掘最大頻繁項集[J]．軟件學(xué)報，2005，16(2)：215-222．

[8] 錢雪忠，惠 亮．關(guān)聯(lián)規(guī)則中基于降維的最大頻繁模式挖掘算法[J]．計算機(jī)應(yīng)用，2011，31(5):1339-1343．

[9] 顏躍進(jìn),李舟軍,陳火旺.一種挖掘最大頻繁項集的深度優(yōu)先算法[J].計算機(jī)研究與發(fā)展,2005,42(3):462-467.

[10] 陳 晨,鞠時光.基于改進(jìn)FP-tree的最大頻繁項集挖掘算法[J].計算機(jī)工程與設(shè)計,2008,29(24):6236-6239.

[11] 王黎明,趙 輝.基于FP樹的全局最大頻繁項集挖掘算法[J].計算機(jī)研究與發(fā)展,2007,44(3):445-451.

[12] 付冬梅，王志強(qiáng)．基于FP-tree和約束概念格的關(guān)聯(lián)規(guī)則挖掘算法及應(yīng)用研究[J]．計算機(jī)應(yīng)用研究，2014，31(4):1013-1015．

[13] Tan Pangning．?dāng)?shù)據(jù)挖掘?qū)д摚河⑽腫M].北京：人民郵電出版社，2006.

SupportCountOptimizationMethodBasedonFP-tree

ZHAO Yang，BAI Fan

(Jiangnan Institute of Computer Technology，Wuxi 214083，China)

In the association rules mining,mining frequent itemsets is the most critical step.Maximum frequent itemsets is the most common simplified representation of frequent itemsets.Maximum frequent itemsets mining algorithms based on FP-tree are most needed to search the FP-tree bottom-up to count the support of the itemsets,but they have not considered the information obtained by completed support counting while counting the current itemset,resulting in unnecessary overhead.To solve it,Support Count Optimization Method on FP-tree,called SCOM for short,is proposed.With a small additional space cost,it can make full use of the information that whether a path supports a itemset and the relation between the itemsets to prune the search.Experimental results show that the maximum frequent itemsets mining algorithm applied obtains a performance boost with SCOM which optimizes the support count based on FP-tree,so it can be applied to all algorithms that use FP-tree to count support.

association rules mining;FP-tree;maximum frequent itemsets;support count;search prune

TP311

A

1673-629X(2017)10-0030-04

2016-11-14

2017-03-16 < class="emphasis_bold">網(wǎng)絡(luò)出版時間

時間：2017-07-11

國家科技重點專項“核高基”(2015ZX01040-201)

趙 陽(1991-)，男，碩士研究生，研究方向為數(shù)據(jù)挖掘、文本分析及可視化；導(dǎo)師：劉鎮(zhèn)江，高級工程師，研究方向為數(shù)據(jù)挖掘、信息處理、數(shù)據(jù)可視化。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170711.1457.090.html

10.3969/j.issn.1673-629X.2017.10.007