顧 鵬

（南京理工大學(xué)計算機工程與科學(xué)學(xué)院 南京 210094）

1 引言

隨著大數(shù)據(jù)時代的到來，關(guān)聯(lián)規(guī)則挖掘日益受到人們的重視，且在銀行、保險、電商、零售等行業(yè)的應(yīng)用也越來越廣泛。作為關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法，Apriori算法受到了廣泛的關(guān)注和研究。同時，利用Apriori算法挖掘頻繁模式也是構(gòu)建商務(wù)智能系統(tǒng)前期數(shù)據(jù)預(yù)處理和特征提取的重要技術(shù)手段之一。經(jīng)典的Apriori算法需要多次掃描事務(wù)數(shù)據(jù)庫，候選-N項集通過頻繁-N-1項集的連接產(chǎn)生，生成大量候選集，進行了大量的無用計算，尤其在項目數(shù)較多的情況下，這種情況更加明顯。

針對Apriori算法的性能瓶頸問題，人們開展大量的研究對Apriori算法進行改進，以提高其效率。較有名的是FP-Growth算法［17］，該算法采用樹和鏈表的混合結(jié)構(gòu)，只需掃描兩次事務(wù)數(shù)據(jù)庫，且無需產(chǎn)生候選項集，但算法的局限性體現(xiàn)在頻繁的構(gòu)造條件模式基，對于大規(guī)模數(shù)據(jù)集來講，F(xiàn)P-Growth算法所構(gòu)建的FP-Tree會非常龐大，可能無法存儲于內(nèi)存之中。

FP-Growth算法之所以高效，是因為采用特殊的數(shù)據(jù)結(jié)構(gòu)將事務(wù)數(shù)據(jù)庫壓縮存儲到內(nèi)存中，避免了重復(fù)掃描事務(wù)數(shù)據(jù)庫帶來的性能瓶頸。學(xué)者們也采用了其他的數(shù)據(jù)結(jié)構(gòu)來對事務(wù)數(shù)據(jù)庫進行壓縮存儲，并在此特殊的數(shù)據(jù)結(jié)構(gòu)上挖掘頻繁項集。文獻［3］提出用十字鏈表來壓縮存儲數(shù)據(jù)結(jié)構(gòu)，文獻［7］首先將事務(wù)數(shù)據(jù)庫轉(zhuǎn)化為關(guān)系矩陣，并使用正交鏈表對該矩陣進行存儲，從而可以通過對鏈表節(jié)點集合進行操作實現(xiàn)頻繁項目集的挖掘。文獻［8～9］同樣采用特殊的方法壓縮事務(wù)數(shù)據(jù)庫，并通過各自特殊的方法挖掘頻繁項集。圖作為經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，也被許多學(xué)者用到頻繁項集的挖掘中。文獻［6］將事務(wù)數(shù)據(jù)庫壓縮為一個有向圖進行存儲，有向圖頂點為項，邊為事務(wù)編號集合，通過對該圖的遍歷來搜索頻繁項集，與之不同是，文獻［1］采用以事務(wù)為頂點，項為邊的無向圖來存儲事務(wù)數(shù)據(jù)庫，在挖掘頻繁-K項集時，混合Apriori算法和基于圖的頻繁項集挖掘算法，在K較小時用Apriori算法，在K較大時用圖挖掘算法。文獻［4］分別用布爾矩陣（生成矩陣）和圖兩種結(jié)構(gòu)來進行頻繁項集挖掘。文獻［2］采用PPC-Tree和N-list的數(shù)據(jù)結(jié)構(gòu)，對項進行pre-order和post-order編碼，極大壓縮了事務(wù)數(shù)據(jù)庫，提高了算法的效率，文獻［15］混合利用Apriori算法和FP-Growth算法來挖掘頻繁項集。也有利用特殊的方法挖掘頻繁項集，以改進Apriori算法的效率，文獻［14］根據(jù)事務(wù)數(shù)據(jù)庫中事務(wù)的長度進行倒序排列，從最長的事務(wù)開始，求頻繁項集。

上述對Apriori算法的改進，均不同程度的提高了挖掘頻繁項集的效率，但算法采用的數(shù)據(jù)結(jié)構(gòu)過于復(fù)雜，對事物數(shù)據(jù)庫的壓縮有限，對項集的支持度計數(shù)仍是采用循環(huán)或搜索統(tǒng)計的方法。本文在總結(jié)現(xiàn)有研究的基礎(chǔ)上提出了一種基于鏈表的改進的Apriori算法。該算法首先掃描事務(wù)數(shù)據(jù)庫計算頻繁-1項集并采用鏈表進行壓縮存儲，然后在頻繁-N項集（N≥1）的基礎(chǔ)上利用高效的位運算對鏈表進行合并操作生成頻繁N+1項集，并對頻繁N+1項集（N≥1）的產(chǎn)生過程進行了優(yōu)化，提高了Apriori算法的效率。

2 IABL（An improved Apriori algo?rithm based on linked list）算法

2.1 算法描述

IABL算法首先掃描事務(wù)數(shù)據(jù)庫計算頻繁-1項集，并采用鏈表以垂直數(shù)據(jù)結(jié)構(gòu)的形式將頻繁-1項集存儲在內(nèi)存中，然后對頻繁-1項集鏈表中的節(jié)點進行兩兩合并生成頻繁-2項集鏈表。為節(jié)約內(nèi)存，保存頻繁-1項集的Itemi和其支持度計數(shù)后，刪除頻繁-1項集鏈表，然后按相同的方法生成頻繁-N項集（N≥2），直到新生成的頻繁-N項集鏈表長度小于N，算法結(jié)束。具體步驟如下。

步驟1：加載數(shù)據(jù)，生成頻繁-1項集L1。掃描事務(wù)數(shù)據(jù)庫D，統(tǒng)計每個項目的支持度計數(shù)，獲得L1并采用如圖1所示的鏈表結(jié)構(gòu)進行存儲。該鏈表包含兩種節(jié)點，Item節(jié)點和Tid節(jié)點。其中Item節(jié)點組成ILink鏈表，包含三個域，next指向下一個Item節(jié)點，如無則為Null，TLink域指向由Tid節(jié)點組成的鏈表，ID域存儲該Item節(jié)點包含項目的ID號；Tid節(jié)點中包含兩個域，rno存儲該項集在事務(wù)數(shù)據(jù)庫中出現(xiàn)的行序號，另一個為指向下一個Tid節(jié)點的next域，若無則為Null。TLink鏈表的長度，即所包含Tid節(jié)點的個數(shù)，為該項集的支持度計數(shù)。

步驟2：根據(jù)步驟1中生成的ILink鏈表，對IL?ink鏈表中的Item節(jié)點進行兩兩合并，生成新的Item節(jié)點，如果該節(jié)點的支持度計數(shù)滿足最小支持度計數(shù)，則將該節(jié)點添加到新的ILink中，否則丟棄。新的ILink中的所有節(jié)點均為頻繁-2項集。在節(jié)點合并時，一個節(jié)點只與其之后的節(jié)點合并，具體合并時，對于待合并的兩個節(jié)點Item1和Item2，合并生成一個新的Item節(jié)點NewItem，NewI?tem.ID=Item1.ID∪ Item2.ID，NewItem.TLink=Item1.TLink∩Item2.TLink。然后刪除頻繁-1項集的IL?ink鏈表，保存頻繁2項集的ILink中各個Item節(jié)點的ID和支持度計數(shù)信息得到L2。

步驟3：重復(fù)步驟2直到ILink的長度小于N為止。但在Item節(jié)點的兩兩合并過程中，需要增加以下判斷以減少不必要的計算。

1）判斷新生成的ID是否屬于N項集令║ID║為ID所表示的項集中所包含的項目的個數(shù)，如果║ID║≠N，進行下兩個節(jié)點的合并，否則進行下一步。

2）根據(jù)新生成的ID在ILink中查找是否已存在具有相同ID的節(jié)點，如果存在，則進行下兩個節(jié)點的合并，否則進行下一步。

3）判斷ID所表示的項集的所有長度為N-1的子集是否為頻繁集，如是則進行下一步，進行下兩個Item節(jié)點的合并。

2.2 算法分析

接下來采用表1所示樣本事務(wù)數(shù)據(jù)庫，對本文所提出的算法進行具體的描述，并對算法性能進行簡要的分析。設(shè)最小支持度計數(shù)為2。

表1 樣本事務(wù)數(shù)據(jù)庫

1）根據(jù)IABL算法步驟1，掃描事務(wù)數(shù)據(jù)庫，計算頻繁-1項集L1，構(gòu)建L1的ILink鏈表，L1=｛B，C，D，A，E｝，其支持度計數(shù)分別為：5，4，4，3，3。結(jié)果如圖2所示。

圖2 L1的ILink

2）按步驟2，對1）生成的ILink中各Item節(jié)點進行兩兩合并，由滿足條件（支持度計數(shù)不小于最小支持度）的新生成的Item節(jié)點構(gòu)成L2的ILink，其結(jié)果如圖3所示。根據(jù)L2的ILink結(jié)果，可得到L2=｛BC，BD，BA，BE，CA，CD，CE，DA｝，其支持度計數(shù)分別為4，3，3，3，3，2，2，2。

圖3 L2的ILink

3）按步驟3，對步驟2中生成的ILink進行兩兩節(jié)點的合并，結(jié)果如圖4所示。根據(jù)L3的ILink，L3=｛BCD，BCA，BCE，BDA，CDA｝，其支持度計數(shù)均為2。同樣地，可得到L4的ILink，其結(jié)果如圖5所示?？傻玫絃4=｛BCDA｝，其支持度計數(shù)為：2。因此時IL?ink中Item節(jié)點的個數(shù)少于4個，算法結(jié)束。

圖4 L3的ILink

根據(jù)上述采用表1的樣本事務(wù)數(shù)據(jù)庫對算法的具體描述可以看出：

圖5 L4的ILink

1）本算法采用鏈表結(jié)構(gòu)對事務(wù)數(shù)據(jù)庫進行一次掃描后存儲到內(nèi)存中，避免了多次掃描事務(wù)數(shù)據(jù)庫帶來的頻繁I/O操作，解決了Apriori算法的性能瓶頸問題，同時本算法采用的用嵌套鏈表存儲事務(wù)數(shù)據(jù)庫的方法，客觀上對事務(wù)數(shù)據(jù)庫信息進行了壓縮，數(shù)據(jù)量越大越稀疏壓縮效果越明顯。

2）在頻繁項集的迭代生成過程中，LN的生成，包括項集支持度計數(shù)的計算只與LN-1相關(guān)，方便計算的同時整體上減少了內(nèi)存開銷。

3）算法采用鏈表結(jié)構(gòu)存儲事務(wù)數(shù)據(jù)庫信息，在生成頻繁項集的過程中只進行兩個Item節(jié)點的合并操作，方法簡單，實現(xiàn)容易，但克服了經(jīng)典Apriori算法的瓶頸，提高了頻繁項集挖掘的效率。

為了提高算法的運行效率，可將高效的位運算運用到兩個Item節(jié)點的合并過程中，包括其ID域和Tid鏈表的合并（實際上是兩個Tid鏈表求交集），具體方法如下：

1）ID域的合并。首先對L1中的所有項進行編碼，用與L1中項的個數(shù)相同長度的二進制位對L1中的每個項進行編碼。如在上面的示例中，L1=｛B，C，A，E｝，則我們可以用4位二進制位來對L1中的每個項進行編碼，具體為：B=1000，C=0100，A=0010，E=0001，在ID域的合并過程中則直接對其編碼進行或運算，如B∪ C=1000|0100=1100。

2）Tid鏈表的合并。類似地，如對于圖3中Item節(jié)點B的Tid域可以表示為：11111，C的Tid域可表示為：11101，對節(jié)點B和C的Tid域進行合并操作，計算11111&11101即可。支持度計數(shù)的計算只需求11101中“1”的個數(shù)即可。

3）需要注意的是，如果L1中的項的個數(shù)較多，或者事務(wù)數(shù)據(jù)庫中事務(wù)的數(shù)目較多時，可以采用鏈表等方式來處理。如事務(wù)數(shù)較多，可將事務(wù)劃分為若干塊，每塊設(shè)置編號，在塊內(nèi)依然用二進制串表示，以便可以用高效的位運算來進行兩個Item節(jié)點的合并。

3 實驗分析

為對IABL算法的性能進行驗證，采用Java編程語言將該算法與FP-Growth算法的性能進行了實驗對比分析。實驗環(huán)境為華碩X556UB筆記本電腦一臺，配置如下：CPU Intel（R）Core（TM）i7-6500 2.5GHz；8G內(nèi)存；64位windows 10操作系統(tǒng)，數(shù)據(jù)集共6組，詳情如表2所示。

表2 實驗數(shù)據(jù)集詳細(xì)信息表

表2中T40I10D100K.dat、T10I4D100K.dat兩個數(shù)據(jù)集為采用IBM Quest Market-Basket Synthetic Data Generator生成的數(shù)據(jù)集，其余的數(shù)據(jù)集為真實數(shù)據(jù)集。在上述實驗條件下，分別用實現(xiàn)的兩種算法在6組數(shù)據(jù)上進行了實驗，具體實驗結(jié)果如圖6～圖11所示。通過實驗結(jié)果數(shù)據(jù)綜合分析，可以得出如下結(jié)論。

1）總體上，IABL算法性能明顯高于FP-Growth算法。從所示各圖可以看出，對于相同的數(shù)據(jù)集，在相同的最小支持度時，IABL算法的執(zhí)行時間明顯低于FP-Growth算法的運行時間。

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

圖7 pumsb數(shù)據(jù)集

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

圖9 kosarak數(shù)據(jù)集

圖10 T40I10D100K數(shù)據(jù)集

圖11 T10I4D100K數(shù)據(jù)集

2）對同一數(shù)據(jù)集，隨著最小支持度的降低，IABL算法和FP-Growth算法在同一最小支持度下的運行時間差距更大。如圖6所示，當(dāng)最小支持度為95%時，IABL算法與FP-Growth算法各自運行時間所表示的點在圖上幾乎重合，但當(dāng)最小支持度降低到90%時，我們可以清楚地從圖上看到差距，而當(dāng)最小支持度降低到85%時，這種差距更明顯。對同一數(shù)據(jù)集而言，最小支持度越小，所得到的頻繁-1項集也就越多，意味著有更多的項參與到之后的頻繁-2項集以及頻繁-N項集的計算中，計算的復(fù)雜度也會相應(yīng)的增加。這也說明IABL算法在查找頻繁項集的計算中效率要高于FP-Growth算法。

3）IABL算法在低密度數(shù)據(jù)集上的性能表現(xiàn)相較于FP-Growth算法優(yōu)勢更加突出。如圖6～圖11所示三個數(shù)據(jù)集，其特點就是數(shù)據(jù)密度低，數(shù)據(jù)量大。如kosarak.dat數(shù)據(jù)集，項目總數(shù)為41270，而平均事務(wù)長度只有8，事務(wù)總數(shù)卻達到990000。根據(jù)算法的實現(xiàn)原理，以圖4～6所示的兩種算法在T10I4D100K數(shù)據(jù)集上運行結(jié)果對比為例，對其原因進行分析。

當(dāng)最小支持度為10%時，數(shù)據(jù)集中滿足最小支持度的項的個數(shù)為0，算法運行時間的差距較小，產(chǎn)生差距的原因在于對數(shù)據(jù)的讀取和計算頻繁-1項集上。

當(dāng)最小支持度降為4%時，頻繁-1項集的數(shù)目為26，而頻繁-2項集的數(shù)目為0。FP-Growth算法的運行過程為：根據(jù)得到的頻繁-1項集開始第二次掃描事務(wù)數(shù)據(jù)庫構(gòu)建FP-Tree［4］，然后根據(jù)構(gòu)建的FP-Tree調(diào)用FP-growth（Tree，α）挖掘出所有頻繁項集。IABL算法的運行過程為：掃描事務(wù)數(shù)據(jù)庫得到頻繁-1項集并構(gòu)建ILink鏈表，然后對TidLink鏈表采用位運算的形式進行兩兩合并，并計算其支持度計數(shù)，確定頻繁-2項集，頻繁-2項集為空，算法結(jié)束。由于FP-Growth算法需要掃描兩次事務(wù)數(shù)據(jù)庫，而IABL算法只需掃描一次事務(wù)數(shù)據(jù)庫，同時構(gòu)建FP-Tree和之后的挖掘頻繁模式也比IABL算法計算更復(fù)雜，效率更低。實驗結(jié)果也很好地驗證了這點，在最小支持度為4%時，在T10I4D100K數(shù)據(jù)集上，F(xiàn)P-Growth算法的運行時間為1968ms，而在同等的條件下，IABL算法的運行時間為422ms，是FP-Growth算法的21.44%。

當(dāng)最小支持度為1%時，頻繁-1項集的數(shù)目是375，頻繁-2項集的數(shù)目為9，頻繁-3項集的數(shù)目為1。為了挖掘出所有滿足最小支持度的頻繁項集，F(xiàn)P-Growth算法需要對查找出的375個頻繁項構(gòu)建龐大的FP-Tree，并在此基礎(chǔ)上展開對樹的搜索查找出所有的頻繁項集，這將是繁重的工作，必將耗費大量時間。而IABL算法基于查找出的375個頻繁項構(gòu)建的ILink鏈表，一方面對數(shù)據(jù)進行了充分的壓縮，另一方面采用位運算迭代計算頻繁-2項集和頻繁-3項集，計算量相對較小，位運算的速度也比搜索操作的速度更快，從而整個算法的執(zhí)行效率也就更高。實驗結(jié)果顯示，在最小支持度為1%時，在T10I4D100K數(shù)據(jù)集上，F(xiàn)P-Growth算法的執(zhí)行時間為37546ms，IABL算法的執(zhí)行時間為4947ms，是FP-Growth算法的13.18%。

4）綜合圖6～11及上述1）～3）的分析，相對于FP-Growth算法而言，由于采用特殊的ILink鏈表結(jié)構(gòu)對預(yù)先計算出的頻繁-1項集進行了壓縮存儲，整個算法在挖掘頻繁項集的過程中只需掃描一遍事務(wù)數(shù)據(jù)庫，采用高效的位運算挖掘頻繁-N項集以及計算其相應(yīng)的支持度計數(shù)，IABL算法性能明顯優(yōu)于FP-Growth算法，在數(shù)據(jù)密度低的數(shù)據(jù)集上這種優(yōu)勢更加明顯，其效率也更高。

4 結(jié)語

本文在研究總結(jié)現(xiàn)有關(guān)聯(lián)規(guī)則挖掘算法的基礎(chǔ)上，提出并實現(xiàn)了一種基于鏈表的改進Apriori算法，該算法使用嵌套鏈表對事務(wù)數(shù)據(jù)庫和前一頻繁項集LN-1進行存儲，并對經(jīng)典Apriori算法的連接、剪枝和驗證過程基于嵌套鏈表的存儲結(jié)構(gòu)進行了優(yōu)化，并采用多個數(shù)據(jù)集對本文所提出的算法與經(jīng)典的FP-Growth算法的運行結(jié)果進行對比分析，證明了本文提出的算法的可行性與正確性。通過實驗的對比分析，本文所提出的算法具有更好的性能。雖然算法能處理較大量的數(shù)據(jù)集，但內(nèi)存空間畢竟有限，在今后的研究中將基于分布式和并行計算對算法進行改進，以適應(yīng)更廣泛的應(yīng)用需求。