一種基于fp-tree的Apriori算法改進研究

倪政君，夏哲雷

(中國計量大學(xué) 信息工程學(xué)院，浙江 杭州 310018)

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中一個重要的研究領(lǐng)域,本質(zhì)上是對頻繁項集的挖掘，主要研究從事務(wù)數(shù)據(jù)庫、關(guān)系型數(shù)據(jù)庫或數(shù)據(jù)倉庫等海量數(shù)據(jù)的項集之間，發(fā)現(xiàn)有價值的頻繁出現(xiàn)的模式關(guān)聯(lián)和相關(guān)性.關(guān)聯(lián)規(guī)則挖掘最早僅限于事務(wù)數(shù)據(jù)庫的布爾型關(guān)聯(lián)規(guī)則，現(xiàn)已被廣泛使用于關(guān)系型數(shù)據(jù)庫中，因此，積極對挖掘關(guān)聯(lián)規(guī)則挖掘進行研究具有重要的意義[1].

關(guān)聯(lián)規(guī)則挖掘算法大致可以分為兩類：一種是Apriori類算法，如基于壓縮矩陣的NCM_Apriori算法[2]、基于Hash的DHP算法[3]等等，這些算法都是在經(jīng)典的Apriori算法[4]上進行改進，算法步驟相對簡單并且易于實現(xiàn)；但是這些算法都需要重復(fù)掃描數(shù)據(jù)庫用來統(tǒng)計候選項集支持?jǐn)?shù)，在數(shù)據(jù)庫數(shù)據(jù)量較大時，這些算法的挖掘速度較低.另一類算法是基于樹形結(jié)構(gòu)的關(guān)聯(lián)規(guī)則算法，如基于fp-tree的FP-Growth算法[5]、基于cofi-tree的COFI-Tree算法[6]、基于cfp-tree的CT-PRO算法[7].該類算法采用樹形結(jié)構(gòu)對數(shù)據(jù)進行壓縮，并對子樹進行挖掘，挖掘時沒有候選項集的生成，減少了掃描數(shù)據(jù)的量，算法的挖掘速度得到提升；但是，該類算法在子樹挖掘時可能會遞歸生成大量的子樹，當(dāng)在遞歸生成子樹上耗費太多時間時，會使得算法的挖掘速度受到限制.

一些研究人員結(jié)合兩類算法的優(yōu)點，將fp-tree樹形結(jié)構(gòu)移植到Apriori算法當(dāng)中，提出了基于fp-tree的改進Apriori算法[8-9].這類改進算法先采用fp-tree對數(shù)據(jù)進行壓縮，僅僅需要掃描數(shù)據(jù)庫一次或者兩次，然后把生成的fp-tree劃分成若干子數(shù)據(jù)集分區(qū)，再將子數(shù)據(jù)集分區(qū)結(jié)合Apriori算法的候選項集生成機制進行挖掘.此類算法大幅減少了候選項集支持?jǐn)?shù)統(tǒng)計的掃描數(shù)據(jù)量，算法的挖掘速度得到提高.文獻[8]結(jié)合fp-tree將fp-tree進行壓縮，并從最不頻繁項元開始劃分生成子樹，單獨地在每一顆子樹上采用候選項集生成機制進行挖掘.該算法避免了遞歸生成大量子樹，并且減少了數(shù)據(jù)掃描量，挖掘速度得到提升.文獻[9]用fp-tree的首元對數(shù)據(jù)庫進行分庫，用分庫代替原數(shù)據(jù)庫進行候選項集支持?jǐn)?shù)的統(tǒng)計，從而減少了Apriori算法掃描數(shù)據(jù)庫的次數(shù)，提高了算法的挖掘速度.但是，基于fp-tree的Apriori算法減少的掃描數(shù)據(jù)量不夠徹底，在支持?jǐn)?shù)統(tǒng)計過程中仍然要掃描較多的分區(qū)數(shù)據(jù)，需要較多時間，算法的挖掘速度不夠理想.

為了提高基于fp-tree的Apriori算法的挖掘速度，本文提出了一種改進的基于fp-tree的Apriori算法.本文的改進算法從減少掃描數(shù)據(jù)的量的角度出發(fā)，通過尾元分區(qū)、動態(tài)刪除冗余數(shù)據(jù)、快速統(tǒng)計支持?jǐn)?shù)等措施改進，進一步提高了挖掘速度.

1　Apriori算法和fp-tree結(jié)構(gòu)

1.1　Apriori算法

Apriori算法為布爾關(guān)聯(lián)規(guī)則挖掘頻繁項集的原創(chuàng)性算法，使用一種稱為逐層搜索的迭代思想，其中k項集用于探索k+1項集.Apriori算法主要包含以下3個步驟[10]：

候選項集生成：隨機取兩個頻繁k項集，把當(dāng)中的各個項按照順序排列，如p={ti1，ti2，…，tik}，q={tj1，tj2，…，tjk}，滿足ti1=tj1，ti2=tj2，…，tik-1=tjk-1，且tik≠tjk時，連接p、q生成候選k+1項候選項集為{ti1，ti2，…，tik，tjk}.

候選項集剪枝：剪枝則是利用了頻繁項集的反單調(diào)性，設(shè)有候選k+1項候選項集包含任意非頻繁項或項集，則可直接判定其非頻繁項集，否則需要對數(shù)據(jù)庫遍歷進行支持?jǐn)?shù)統(tǒng)計，進一步驗證其是否頻繁.

支持?jǐn)?shù)統(tǒng)計：掃描數(shù)據(jù)集，累加k+1項候選項集在數(shù)據(jù)集中出現(xiàn)的次數(shù).最后根據(jù)給定的最小支持?jǐn)?shù)閥值生成k+1項頻繁項集.在支持?jǐn)?shù)計算判定頻繁項集過程中存在一個定理：

定理1如果數(shù)據(jù)庫中某條事務(wù)的長度為k，那么這條事務(wù)就不可能包含任何項數(shù)大于k的頻繁項集

推論1若某條事務(wù)的長度小于k+1，則在k+1項候選項集的支持?jǐn)?shù)統(tǒng)計中可以忽略此條事務(wù)數(shù)據(jù)

在Apriori算法的支持?jǐn)?shù)計數(shù)步驟，因其需要掃描一遍完整的原數(shù)據(jù)集來統(tǒng)計支持?jǐn)?shù)，在數(shù)據(jù)庫事務(wù)數(shù)量較多的情況下，算法的挖掘速度會下降.

1.2　fp-tree結(jié)構(gòu)

fp-tree結(jié)構(gòu)是對數(shù)據(jù)進行壓縮的一種樹形數(shù)據(jù)結(jié)構(gòu)，最早出現(xiàn)在FP-growth算法中.fp-tree中每個節(jié)點對應(yīng)一個項元，每個節(jié)點由4個域組成：項元標(biāo)識item-name，經(jīng)過該節(jié)點的支持?jǐn)?shù)count，項元鏈node-link以及父節(jié)點指針parent.另外，為了方便對樹進行操作，還有一個頭表HeaderTable，頭表中的記錄有2個域：項元標(biāo)識item-name、項元鏈鏈頭node-head，其中node-head指向fp-tree中首次創(chuàng)建某一項元的節(jié)點.fp-tree中實線是父節(jié)點指針，虛線是項元鏈.fp-tree相關(guān)概念及結(jié)構(gòu)細(xì)節(jié)詳見文獻[11].圖1顯示了fp-tree在表1樣例數(shù)據(jù)集上的結(jié)構(gòu).

表1　樣例數(shù)據(jù)集

圖1　fp-tree結(jié)構(gòu)Figure 1　fp-tree Structure

2　改進算法

2.1　算法的改進思想

為了提高基于fp-tree的Apriori算法的挖掘速度，從進一步縮減掃描數(shù)據(jù)量的改進方向進行研究，本文通過以下幾個方法進行改進和優(yōu)化：其一，改變算法的分區(qū)方法，使用尾元分區(qū)的方式進行分區(qū)，可以得到數(shù)據(jù)量更小的子數(shù)據(jù)集.第二，依據(jù)Apriori算法的性質(zhì)，動態(tài)刪減子數(shù)據(jù)集中小于當(dāng)前迭代維度數(shù)的冗余數(shù)據(jù)，數(shù)據(jù)動態(tài)縮減使得子數(shù)據(jù)集的數(shù)據(jù)進一步得到縮減.最后，通過掃描子數(shù)據(jù)集進行快速統(tǒng)計，迅速統(tǒng)計候選項集的支持?jǐn)?shù)，并判斷此候選項集是否是頻繁項集，從而快速挖掘.具體的改進方法如下：

尾元分區(qū)：通過候選項集的尾元搜索fp-tree，將原數(shù)據(jù)集劃分生成若干子數(shù)據(jù)集，從而達到縮減數(shù)據(jù)量的目的.生成的每一個子數(shù)據(jù)集在內(nèi)存中僅有一份，生成后無須再度生成.尾元分區(qū)的具體過程如下：

圖2tk對應(yīng)的fp-tree分枝
Figure 2Corresponding fp-tree Branch

若候選項集中存在某尾部項元tk，則tk的子數(shù)據(jù)集生成過程如下：找到項元tk在頭表HeaderTable中的項元鏈鏈頭node-head，通過node-head找到在fp-tree中項元標(biāo)識item-name為tk的第一個節(jié)點tk1.假設(shè)節(jié)點tk1所在fp-tree前綴分枝的普遍形式如圖2所示，則通過遍歷分枝可以得到分枝上所有節(jié)點的信息，獲取分枝上每個節(jié)點的item-name匯總成向量表示形式，得到分枝向量的一般表示形式為

k=[t1t2…tk].

(1)

可得tk1分枝向量為k1，并記錄tk1節(jié)點的支持?jǐn)?shù)count為S1.通過tk1節(jié)點的項元鏈node-link找到下一個位置的tk節(jié)點tk2，并以同樣的方式生成tk2節(jié)點所在分枝的向量k2，并記錄支持?jǐn)?shù)為S2.根據(jù)當(dāng)前節(jié)點的node-link遍歷下一個節(jié)點，直至到最后一個節(jié)點tki，可得分枝向量ki，支持?jǐn)?shù)Si，至此停止遍歷.將所有的分枝向量匯總，可得到此項元tk的子數(shù)據(jù)集為

Mk={k1,k2,…,ki}.

(2)

對應(yīng)的支持?jǐn)?shù)數(shù)據(jù)集為

Sk={S1,S2,…,Si}.

(3)

其中Sk數(shù)據(jù)集記錄了子數(shù)據(jù)集中的每一條分枝對應(yīng)的支持?jǐn)?shù)，用于下文的快速支持?jǐn)?shù)統(tǒng)計.

通過尾元分區(qū)，將具有相同尾元的頻繁項集所要掃描的數(shù)據(jù)歸為同一子數(shù)據(jù)集，從而避免了對無關(guān)數(shù)據(jù)的掃描，在含有大量頻繁項集的情況下，數(shù)據(jù)得到縮減的量較多，算法挖掘速度提升也較多.

數(shù)據(jù)動態(tài)縮減：候選項集的迭代生成是從低維向高維進行遞推.根據(jù)定理1和推論1可知，當(dāng)事務(wù)數(shù)小于迭代的維度數(shù)時，可知在此事務(wù)中肯定不包含當(dāng)前維度數(shù)的頻繁項集.那么，在支持?jǐn)?shù)統(tǒng)計中可以忽略此事務(wù)，將此事務(wù)從子數(shù)據(jù)集刪除，從而達到縮減掃描數(shù)據(jù)量的目的.子數(shù)據(jù)集數(shù)據(jù)動態(tài)縮減的描述如下：

在子數(shù)據(jù)集已經(jīng)生成的基礎(chǔ)上，若要統(tǒng)計某候選項集Ck=[t1t2…tk]的支持?jǐn)?shù)，則選取Ck最尾部的項元tk，找到tk所對應(yīng)的子數(shù)據(jù)集，如式(2)子數(shù)據(jù)集Mk.其中，若當(dāng)前迭代的維度為j，則刪除Mk中事務(wù)數(shù)小于j的事務(wù)，得到數(shù)據(jù)量更小的新Mk.

數(shù)據(jù)動態(tài)縮減的改進方法是在上一層經(jīng)過縮減的子數(shù)據(jù)集的基礎(chǔ)上進行縮減，在當(dāng)?shù)木S度數(shù)越高時，可以刪減的冗余數(shù)據(jù)也越多，從而對算法的挖掘速度的提升越明顯.

快速統(tǒng)計支持?jǐn)?shù)：遍歷新Mk，將其中每一個分枝的向量與Ck進行比較，若ki包含Ck，則認(rèn)為此分枝包含候選項集Ck，累加式(3)支持?jǐn)?shù)數(shù)據(jù)集Sk中對應(yīng)此分枝的支持?jǐn)?shù)，若有整數(shù)n個分枝包含候選項集Ck，則最終候選項集Ck的支持?jǐn)?shù)有

(4)

若S大于最小支持?jǐn)?shù)，則候選項集Ck是頻繁項集.

本文提出的改進算法通過以上思路和方法進行改進，提高了算法挖掘速度，尤其是對含有大量高維度數(shù)頻繁項集的數(shù)據(jù)集，掃描數(shù)據(jù)的量會得到大幅縮減，算法挖掘速度可以得到明顯提升.

2.2　算法描述

在Apriori候選項集生成機制上，算法主要增加了使用fp-tree的步驟：通過尾元劃分?jǐn)?shù)據(jù)，并在生成和使用子數(shù)據(jù)集的過程中只選取大于等于當(dāng)前迭代維度數(shù)的事務(wù)，即動態(tài)縮減數(shù)據(jù)，最后通過候選項集和子數(shù)據(jù)集的比較進行支持?jǐn)?shù)快速統(tǒng)計，判斷是否是頻繁項集.

使用fp-tree的偽代碼如下：

輸入：候選項集Ck、fp-tree、最小支持?jǐn)?shù)min_support

輸出：頻繁項集Lk

1)begin

2)for each candidate candiItem∈Ck

3)support=0

//將候選項集轉(zhuǎn)換成向量

4)canMatrix:=candiItem trans to matrix and sort

//獲得尾元進行分區(qū)，得到子數(shù)據(jù)集

5)oneItem=canMatrix[max]

//得到fp-tree的第一個節(jié)點

6)currNode=HeaderTable[oneItem]

//遍歷所有節(jié)點

7)while currNode.hasNext

8)currNode=currNode.next

//將當(dāng)前節(jié)點的fp-tree分枝轉(zhuǎn)換成向量

9)tempMatrix:=Get prefix and trans to matrix

//數(shù)據(jù)動態(tài)縮減，剔除小于當(dāng)前維度數(shù)的事務(wù)

10)if tempMatrix.size>=candiItem.size

11)add tempMatrix to Matrix[oneItem]

12)end if

//快速統(tǒng)計支持?jǐn)?shù)

//若分枝包含候選項集則累加支持?jǐn)?shù)

13)if canMatrix∩tempMatrix equals canMatrix

14)support+=currNode.support

15)end if

16)end while

//判斷是否是頻繁項集

17)if support>min_support

18)add candiItem to Lk

19)end if

20)cache the Matrix

21)end for

22)end

3　實驗分析

實驗是在CPU為I5 4590，8 G內(nèi)存的硬件環(huán)境下，操作系統(tǒng)為Windows，編程語言為Java，編輯工具為Eclipse的軟件環(huán)境下完成實驗數(shù)據(jù)的獲取和測量，并使用Matlab展示實驗圖表.實驗使用經(jīng)典的關(guān)聯(lián)規(guī)則算法數(shù)據(jù)集T10I4D100K和Accidents，均是從FIMI存儲庫(http://fimi.ua.ac.be/data/)下載.本文分別在這兩種數(shù)據(jù)集上進行對比試驗，每組試驗的參數(shù)都是不變的，都是通過改變最小支持度從而記錄算法的運行時間，算法運行的時間越小代表算法的挖掘速度越快.

實驗一圖3的實驗采用了T10I4D100K數(shù)據(jù)集，該數(shù)據(jù)集是個數(shù)據(jù)量為100 000的人工數(shù)據(jù)集，在最小支持度大于5%，頻繁項集較少，此時，改進算法得到的提升不高.在最小支持度小于5%時，會出現(xiàn)大量的頻繁項集，由于本文尾元分區(qū)的改進方法減少了統(tǒng)計頻繁項集支持?jǐn)?shù)所需掃描數(shù)據(jù)的量，從而對于這些大量的頻繁項集進行掃描時間也會相應(yīng)地減少，尤其當(dāng)最小支持度為4%時.本文改進算法的運行時間較文獻[8]縮短了61.7%，較文獻[9]縮短了72.6%.可見對于含有大量頻繁項集的數(shù)據(jù)集，本文改進算法挖掘的速度較高.

實驗二圖4的實驗采用了Accidents數(shù)據(jù)集，該數(shù)據(jù)集的平均事務(wù)長度和頻繁項集的長度都會較長，說明在逐層迭代過程中會對維度數(shù)較高的候選項集進行支持?jǐn)?shù)統(tǒng)計；而根據(jù)本文改進算法動態(tài)縮減數(shù)據(jù)的改進方法，對維度數(shù)越高的頻繁項集進行支持?jǐn)?shù)統(tǒng)計，那么減少的掃描數(shù)據(jù)的量也越多，從而縮減的運行時間也越多，算法的挖掘速度也越快.從圖4的實驗結(jié)果上可知，在最小支持度為60%時，本文改進算法的運行時間較文獻[9]縮短了76%，較文獻[8]縮短了70%.

圖3　T10I4D100K上運行時間對比Figure 3　Running time comparisonon T10I4D100K

圖4　Accidents上運行時間對比Figure 4　Running time comparison on Accidents

綜合實驗分析可知，當(dāng)數(shù)據(jù)集在一定最小支持度區(qū)間內(nèi)出現(xiàn)大量頻繁項集和頻繁項集維度數(shù)較高時，本文改進算法的挖掘速度要快于文獻[9]算法和文獻[8]算法.可見，本文提出的改進的基于fp-tree的Apriori算法的挖掘速度得到提升.

4　結(jié)　語

本文提出改進的基于fp-tree的Apriori算法，從縮減掃描數(shù)據(jù)量的角度出發(fā)，采用改變分區(qū)方式、縮減冗余數(shù)據(jù)量和快速支持?jǐn)?shù)掃描等措施提升算法挖掘速度，通過實驗驗證了改進算法的挖掘速度得到提高.

【參考文獻】

[1]崔貫勛,李梁,王柯柯.關(guān)聯(lián)規(guī)則挖掘中Apriori算法的研究與改進[J].計算機應(yīng)用,2010,30(11)：2952-2955.

CUI G X, LI L, WANG K K.Research and improvement on apriori algorithm of association rule mining[J].JournalofComputerApplications, 2010,30(11)：2952-2955.

[2]羅丹,李陶深.一種基于壓縮矩陣的Apriori算法改進研究[J].計算機科學(xué),2013,40(12)：75-80.

LUO D, LI T S.Research on improved apriori algorithm based on compressed matrix[J].ComputerScience, 2013,40(12)：75-80.

[3]PARK J S, CHEN M S, YU P S.An effective hash-based algorithms for mining association rules[C]//Proceedingsofthe1995ACMSIGMODInternationalConferenceonManagementofData. California：ACM Press,1995：175-186.

[4]AGRAWAL R, SRIKAN R. Fast algorithms for mining association rules in lager databases[C]//ProceedingsoftheTwentiethInternationalConferenceonVeryLargeDatabases.Santiago：IEEE,1994：487-499.

[5]JIA W H, JIAN P, YIN Y W, et al.Mining frequent patterns without candidate generation：A frequent patterns tree approach[J].DataMiningandKnowledgeDiscovery, 2004,8(1):53-87.

[6]肖繼海,崔曉紅,陳俊杰.基于cofi-tree的N-最有興趣項目集挖掘算法[J].計算機技術(shù)與發(fā)展,2012,35(2)：99-102.

XIAO J H, CUI X H, CHEN J J.Mining n-most interesting itemsets algorithm based on cofi-tree[J].ComputerTechnologyandDevelopment,2012,22(3)：99-102.

[7]YUDHOG S, RAJ P G. CT-PRO：A bottom-up non frequent itemset mining algorithm using compressed fp-Tree data structure[C]//ProceedingsoftheIEEEICDMWorkshoponFrequentItemsetMiningImplementations. Brighton：IEEE, 2004：212-223.

[8]吳倩,羅健旭.壓縮FP-Tree的改進搜索算法[J].計算機工程與設(shè)計,2015,36(7)：1771-1777.

WU Q, LUO J X. Improved search algorithm based on compressed fp-tree[J].ComputerEngineeringandDesign, 2015,36(7)：1771-1777.

[9]張寧.基于fp-tree的Apriori算法的改進[J].信息通信,2015,2：94-95.

ZHANG N. Improvement of apriori algorithm based on fp-tree[J].Information&Communications, 2015,2：1771-1777.

[10]錢光超,賈瑞玉,張然.Apriori算法的一種優(yōu)化方法[J].計算機工程,2008,34(23)：196-198.

QIAN G C, JIA R Y, ZHANG R.One optimized method of apriori algorithm[J].ComputerEngineering, 2008,34(23)：196-198.

[11]趙強利,蔣艷凰,徐明.基于fp-tree的快速選擇性集成算法[J].軟件學(xué)報,2011,22(4)：709-721.

ZHAO Q L, JIANG Y H, XU M.Fast ensemble pruning algorithm based on fp-tree[J].Journalofsoftware, 2011,22(4)：709-721.