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

基于單向增長(zhǎng)鏈表的關(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)的時(shí)間長(zhǎng)、內(nèi)存消耗巨大，降低了算法在時(shí)間和空間方面的效率。針對(duì)2種算法的缺陷，提出了LK-Growth算法，該算法不再構(gòu)建FP-Tree，而是構(gòu)建單向線性鏈表組結(jié)構(gòu)，能有效地縮短發(fā)現(xiàn)頻繁模式的時(shí)間和節(jié)省內(nèi)存空間開支。研究結(jié)果表明，LK-Growth算法的實(shí)用性強(qiáng)且挖掘效率更高。

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

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

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

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

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

1.2算法設(shè)計(jì)

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

Procedure HTL_List

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

(2)Do begin

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

(4)Do begin

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

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

(6)End

(7)End

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

Function insert_link(LT，λ)

(1)If( LT中存在 ) Then

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

(3)Else

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

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

(6)Else

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

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

2 應(yīng)用案例

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3算法性能試驗(yàn)分析

圖7 算法運(yùn)行對(duì)比圖

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

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

3 結(jié) 語(yǔ)

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

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

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

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

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

[編輯] 李啟棟

10.3969/j.issn.1673-1409.2012.01.035

TP391.1

A

1673-1409(2012)01-N110-03