董 輝 (亳州職業(yè)技術(shù)學(xué)院信息工程系，安徽 亳州 236800)

基于單向增長鏈表的關(guān)聯(lián)規(guī)則挖掘算法研究

董 輝 (亳州職業(yè)技術(shù)學(xué)院信息工程系，安徽 亳州 236800)

分析研究關(guān)聯(lián)規(guī)則挖掘經(jīng)典算法Apriori和FP-Growth算法，發(fā)現(xiàn)其不足之處在于構(gòu)建和遍歷各自數(shù)據(jù)結(jié)構(gòu)的時間長、內(nèi)存消耗巨大，降低了算法在時間和空間方面的效率。針對2種算法的缺陷，提出了LK-Growth算法，該算法不再構(gòu)建FP-Tree，而是構(gòu)建單向線性鏈表組結(jié)構(gòu)，能有效地縮短發(fā)現(xiàn)頻繁模式的時間和節(jié)省內(nèi)存空間開支。研究結(jié)果表明，LK-Growth算法的實用性強(qiáng)且挖掘效率更高。

數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；線性增長鏈表；LK-Growth算法

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘眾多知識類型中一種典型代表，也是數(shù)據(jù)挖掘中最活躍的研究領(lǐng)域之一，其首要任務(wù)就是發(fā)現(xiàn)頻繁項目集。長期以來，人們對關(guān)聯(lián)規(guī)則頻繁項目集的挖掘主要采用Apriori算法和FP-Growth算法或者它們的有關(guān)改進(jìn)算法。但是，無論是Apriori算法還是FP-Growth算法，都要多次掃描事務(wù)數(shù)據(jù)庫，I/O負(fù)載大，導(dǎo)致算法的時間開銷增大；在空間需求上，Apriori算法要產(chǎn)生大量的候選頻繁項目集、FP-Growth算法構(gòu)造結(jié)構(gòu)復(fù)雜的FP-Tree樹，對內(nèi)存開銷要求都很高[1]。針對上述情況，筆者提出基于單項線性鏈表的關(guān)聯(lián)規(guī)則挖掘優(yōu)化算法，該算法構(gòu)建多個單向鏈表結(jié)構(gòu)做成鏈表組，通過該結(jié)構(gòu)的遍歷發(fā)現(xiàn)所有的頻繁模式，在挖掘效率上比Apriori和FP-Growth算法都要高。

1 優(yōu)化算法設(shè)計

1.1優(yōu)化算法的思路

從對關(guān)聯(lián)規(guī)則挖掘的2種經(jīng)典算法的分析可知，要想提高挖掘效率，可從2方面考慮[2]：第1方面是優(yōu)化重構(gòu)算法操作對象的數(shù)據(jù)結(jié)構(gòu)；第2方面是在不改變操作對象的數(shù)據(jù)結(jié)構(gòu)情況下，改變對其執(zhí)行方式，提高操作速度，發(fā)現(xiàn)頻繁項集。筆者從第1方面著手，構(gòu)建單向鏈表組數(shù)據(jù)結(jié)構(gòu)，提出優(yōu)化的LK-Growth算法，挖掘出所有的頻繁模式，從而提高挖掘效率。

1.2算法設(shè)計

LK-Growth算法設(shè)計過程為輸入：事務(wù)數(shù)據(jù)庫D，最小支持度閥值 min_sup；輸出：頻繁模式完全集。具體實現(xiàn)步驟如下[3-4]：①首次掃描事務(wù)數(shù)據(jù)庫D生成1-頻繁項集和各項支持度計數(shù)值，把支持度計數(shù)滿足最小支持度閥值的各項及支持度計數(shù)按支持度計數(shù)降序存至項頭表HT(Header Table)中；②第2次掃描數(shù)據(jù)庫D，對第1個事務(wù) 掃描，保留出現(xiàn)在HT表的頻繁項，各項節(jié)點按支持度計數(shù)降序排列，存入到名為SingleLink單鏈表內(nèi)；③構(gòu)造以項頭表中節(jié)點為頭節(jié)點的單鏈表組，偽代碼如下：

Procedure HTL_List

(1)For (i=2；i≥j；i++) //j是SingleLink鏈表中的節(jié)點數(shù)

(2)Do begin

(3) For (m=i；m≥2；m--)

(4)Do begin

(5)Insert_link(SL，Mj-1)； //Mj為SingleLink

//鏈表第j個節(jié)點,SL為HT表中以Mj為頭節(jié)點的單向鏈表

(6)End

(7)End

在構(gòu)造單鏈表過程中調(diào)用Insert_link( )函數(shù)作用是把節(jié)點插入到LT單鏈表中，其偽代碼如下：

Function insert_link(LT，λ)

(1)If( LT中存在 ) Then

(2)λ.Sup_count=λ. Sup_count +1； //λ節(jié)點支持度計數(shù)加1

(3)Else

(4)IF (按HT表的排序，LT中存在δ節(jié)點排在λ前) Then

(5)λ節(jié)點鏈接在δ之后，λ.Sup_count=λ. Sup_count +1；

(6)Else

(7)節(jié)點鏈接到LT的尾端，λ.Sup_count=λ.Sup_count +1；

④依照上述步驟依次掃描數(shù)據(jù)庫D的每個事務(wù)，每次掃描要重構(gòu)SingleLink單鏈表，再按步驟②、③對余下的頻繁項作類似處理，直到全部事務(wù)掃描完止，把各事務(wù)的所有數(shù)據(jù)項都插入到相應(yīng)的以項頭表中節(jié)點為頭節(jié)點的單鏈表內(nèi)。至此，可以得到以HT表中各節(jié)點為頭指針的各單鏈表組成的相鄰的鏈表組，通過遍歷該鄰接鏈表組，即可發(fā)現(xiàn)滿足最小支持度閥值的所有頻繁模式。

2 應(yīng)用案例

2.1構(gòu)建事務(wù)數(shù)據(jù)庫

設(shè)事務(wù)數(shù)據(jù)庫D(見圖1)，設(shè)最小支持度計數(shù)為3。根據(jù)最小支持度計數(shù)為3，對事務(wù)數(shù)據(jù)庫D的數(shù)據(jù)項進(jìn)行排序，結(jié)果如圖2所示。

圖1 事務(wù)數(shù)據(jù)庫D

圖2 處理后的事務(wù)數(shù)據(jù)庫D

2.2LK-Growth算法應(yīng)用

首次掃描事務(wù)數(shù)據(jù)庫D，得到1-頻繁項集：L={(a：5)，(b：4)，(c：3)，(d：3) }(支持度計數(shù)相同者按字典排序，e、f、j、k、o、p、s的支持度計數(shù)為1小于2，故舍去)，并把1-頻繁項集按支持度計數(shù)降序存入項頭表HT中。

圖3 第1個事務(wù)的SingleLink鏈表

圖4 節(jié)點單鏈表結(jié)構(gòu)

第2次掃描事務(wù)數(shù)據(jù)庫D，對T100事務(wù)的掃描只保留HT中出現(xiàn)的頻繁項，且按支持度計數(shù)降序排列得到：a、b、c，依次存入SingleLink單鏈表中，此時SingleLink鏈表節(jié)點個數(shù)j=3，其第2的節(jié)點為b，把b的父節(jié)點(即a)插入到HT表中以b為頭節(jié)點的單向鏈表中，計數(shù)值置為1。同理，對余下節(jié)點進(jìn)行上述操作，對T100事務(wù)掃描操作結(jié)束后，SingleLink單鏈表如圖3所示，各節(jié)點單鏈表結(jié)構(gòu)如圖4所示。

按照上述操作，對余下事務(wù)進(jìn)行掃描操作，每次重構(gòu)SingleLink鏈表，并把每個節(jié)點信息按如下規(guī)則插入到相應(yīng)的單鏈表位置上：若鏈表內(nèi)無該節(jié)點，則創(chuàng)建之，并計數(shù)值置1；若鏈表內(nèi)存在該節(jié)點，無需再創(chuàng)建，計數(shù)值加1即可。按照上述方法，直至全部事務(wù)掃描完畢，最后生成以項頭表HT中各節(jié)點為頭結(jié)點的多個單鏈表構(gòu)成的鏈表組，結(jié)果如圖5所示。

遍歷圖5，在滿足支持度計數(shù)大于3的條件下，以項頭表HT中各節(jié)點為基本結(jié)點，分別對各單鏈表中各節(jié)點組合，可得頻繁模式集(見圖6)。

圖5 各事務(wù)所有節(jié)點構(gòu)成的鏈表組

圖6 滿足最小支持度閥值的所有頻繁模式

2.3算法性能試驗分析

圖7 算法運行對比圖

通過試驗對FP_Growth算法和LK_Growth算法的性能進(jìn)行分析比較。試驗測試環(huán)境如下：Intel Core i3 CPU；4G內(nèi)存；320G SATA硬盤；Win7 OS；C#編程環(huán)境。試驗中采用的數(shù)據(jù)庫為中國生物谷中藥方劑數(shù)據(jù)庫，數(shù)據(jù)庫事務(wù)量(即方劑數(shù))為84449，測試結(jié)果如圖7所示。

由圖7可知，在相同支持度計數(shù)的情況下，要處理的事務(wù)量是相同的，但是LK_Growth算法所花費的時間明顯要小于FP_Growth算法所耗費的時間，LK_Growth算法的效率要高于FP_Growth算法的效率，且隨著支持度計數(shù)的減小和事務(wù)量的增大，LK_Growth效率優(yōu)勢越明顯，總體效率比FP_Growth要高50%以上。

3 結(jié) 語

分析了關(guān)聯(lián)規(guī)則中的Apriori和FP_Growth算法，針對其不足，提出了LK_Growth優(yōu)化算法。由于在優(yōu)化算法中無需生成頻繁模式基和條件模式樹，而是把事務(wù)的所有節(jié)點數(shù)據(jù)項直接存入到以HT表中各節(jié)點為頭指針的相鄰的單鏈表組中，因此減小了空間消耗，避免了內(nèi)存壓力，同時也僅需掃描事務(wù)數(shù)據(jù)庫2次，且這種存儲結(jié)構(gòu)本身就直接蘊涵了全部頻繁項目集，通過遍歷操作，可以很容易地挖掘出所有的頻繁項模式，挖掘效率有了顯著的提高。試驗結(jié)果表明，改進(jìn)后的算法速度快，而且挖掘的數(shù)據(jù)庫事務(wù)量越大，其優(yōu)越性越能得以體現(xiàn)，從而為關(guān)聯(lián)規(guī)則挖掘提供了新途徑。

[1]朱 明.數(shù)據(jù)挖掘[M].合肥：中國科學(xué)技術(shù)大學(xué)出版社，2008.

[2]楊云，羅艷霞.FP-Growth 算法的改進(jìn)[J].陜西科技大學(xué)學(xué)報，2010，31 (7):1506-1508.

[3]石杰.大規(guī)模數(shù)據(jù)庫關(guān)聯(lián)規(guī)則挖掘算法研究[D].濟(jì)南：山東師范大學(xué)，2003.

[4]潘福錚.數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則[J].湖北大學(xué)學(xué)報(自然科學(xué)版)，2002，24(4):25-29.

[編輯] 李啟棟

10.3969/j.issn.1673-1409.2012.01.035

TP391.1

A

1673-1409(2012)01-N110-03