一種新的改進(jìn)Apriori算法*

楊金鳳，劉 鋒

(安徽大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，安徽 合肥 230039)

數(shù)據(jù)挖掘DM(Data Mining)出現(xiàn)于 20世紀(jì)80年代后期，是在數(shù)據(jù)庫技術(shù)的基礎(chǔ)上，結(jié)合人工智能、機器學(xué)習(xí)、統(tǒng)計學(xué)、神經(jīng)網(wǎng)絡(luò)等多種學(xué)科技術(shù)產(chǎn)生的具有很強生命力的新研究領(lǐng)域。其中關(guān)聯(lián)規(guī)則挖掘研究[1-2]是一項重要的內(nèi)容，目的是發(fā)現(xiàn)大規(guī)模數(shù)據(jù)集中項集之間有趣的關(guān)聯(lián)關(guān)系或模式。

頻繁項集的挖掘是關(guān)聯(lián)規(guī)則挖掘的核心，如何高效地從海量數(shù)據(jù)庫中找出頻繁出現(xiàn)的項集是世界范圍內(nèi)的熱門研究課題。

1 相關(guān)概念[1]

設(shè) I={I1，I2，…，Im}是項的集合，稱為項集，包含 k 個項的項集稱為k項集。D是數(shù)據(jù)庫事務(wù)的集合，數(shù)據(jù)庫中的每個事務(wù)T是項的集合，T?I，TID是事務(wù) T的標(biāo)識符。設(shè)A是一個項集，事務(wù)T包含A，當(dāng)且僅當(dāng)A?T，一個包含k個項的事務(wù)T可以產(chǎn)生2k個非空的子項集。

規(guī)則A?B的支持度s是D中同時包含A和B的事務(wù)占總事務(wù)的百分比。規(guī)則A?B的支持度c是D中同時包含A和B的事務(wù)占包含A的事務(wù)的百分比。項集的出現(xiàn)頻率是包含項集的事務(wù)數(shù)，稱為項集的支持度計數(shù)。項集的支持度計數(shù)除以總的事務(wù)數(shù)就是相對支持度計數(shù)，如果項集I的相對支持度計數(shù)不小于預(yù)定義的最小支持度閾值，則稱此項集是頻繁項集，否則是不頻繁項集。

2 Apriori算法和優(yōu)化

2.1 經(jīng)典的Apriori算法[2-6]

Apriori是一種逐層搜索的迭代方法，即用k項頻繁項集探索(k+1)項頻繁項集。首先，掃描數(shù)據(jù)庫找出頻繁1項集的集合，該集合為L1。用L1找頻繁2項集的集合L2，用L2找 L3，如此下去直到不能再找到頻繁項集。找每個Lk需要1次數(shù)據(jù)庫全掃描。

為了提高頻繁項集逐層產(chǎn)生的效率，一種稱作Apriori的重要性質(zhì)用于壓縮搜索空間。Apriori性質(zhì)為頻繁項集的所有非空子集也必須是頻繁的。

Apriori算法是由連接步和剪枝步組成。(1)連接步：為找Lk，通過將Lk-1與自身連接產(chǎn)生候選k項集的集合。該候選項集合為 Ck。(2)剪枝步：Ck是 Lk的超集，即Ck的成員可能是頻繁的；也可能是不頻繁的。掃描數(shù)據(jù)庫確定Ck中每個候選項集的計數(shù)，從而確定Lk(即根據(jù)定義，計數(shù)值不小于最小支持度計數(shù)的所有候選項集是頻繁的，從而屬于Lk)。然而Ck可能很大，因此所涉及的計算量就很大。為壓縮Ck，可以使用Apriori性質(zhì)。任何非頻繁的(k-1)項集都不是頻繁k項集的子集。因此，如果候選 k項集的(k-1)項子集不在Lk-1中，則該候選項集也不可能是頻繁的，從而可以從Ck中刪除。

經(jīng)典的Apriori算法在產(chǎn)生候選項集上，由Lk-1自連接產(chǎn)生Ck，然后再利用Apriori性質(zhì)對Ck進(jìn)行刪減。設(shè)l1和 l2是 Lk-1中的項集。 記號 li[j]表示 li中的第 j項(例如，l1[k-2]表示l1的倒數(shù)第 2項)。Apriori假定事務(wù)或項集中的項按字典次序排序。執(zhí)行Lk-1的自連接，如果它們的前(k-2)個項相同的話，則可以連接。例如，(l1[1]=l2[1])∧(l1[2]=l2[2])∧… ∧(l1[k-2]=l2[k-2])∧(l1[k-1]＜l2[k-1])，那么 l1和 l2是可以連接的，否則是不可以連接的，連接結(jié)果項集是 l1[1]，l1[2]，…，l1[k-1]，l2[k-2]。 然后再利用 Apriori性質(zhì)進(jìn)行判斷項集 l1[1]，l1[2]，…，l1[k-1]，l2[k-2]是否可能是頻繁的，這樣需要先產(chǎn)生項集l1[1]，l1[2]， … ，l1[k-1]，l2[k-2]的(k-1)個 (k-1)項子集 ，然后依次比較(k-1)個子集是否在Lk-1中，如果出現(xiàn)不在，則刪減項集 l1[1]，l1[2]， … ，l1[k-1]，l2[k-2]； 如果都在，再對數(shù)據(jù)庫掃描，進(jìn)行計數(shù)。

2.2 對Apriori算法的改進(jìn)

通過上面的分析發(fā)現(xiàn)，為了生成Ck，在連接步驟需要大量的比較，而且由連接產(chǎn)生的項集即使后來由Apriori性質(zhì)確定了它不是候選項集，但在確定之前仍然需要對它生成子項集，并對子項集進(jìn)行確定是否都在Lk-1中。這些步驟浪費了大量的時間，如果可以保證由連接步生成的項集都是候選項集的話，那么可以省掉不必要的連接比較和剪枝步驟。下面介紹改進(jìn)后的算法。

首先對Lk-1中的每項進(jìn)行掃描，記下項集{l1[1]}，{l1[1]，l1[2]}，…，{l1[1]，l1[2]，…，l1[k-2]}，{l2[1]}，{l2[1]，l2[2]}，…，{l2[1]，l2[2]，…，l2[k-2]}，{l3[1]}，…。 設(shè) 1 個 k項集 li={li[1]，li[2]， … ，li[k-1]，li[k]}， 由 Apriori 性質(zhì)知道，如果 li屬于 Ck，那么以下的(k-1)個(k-1)項集就必須都出現(xiàn)在 Lk-1中，所以{li[1]}至少要出現(xiàn)(k-2)次，{li[1]，li[2]}至少要出現(xiàn) (k-3)次 ， 依次類推 {li[1]，li[2]，…，li[k-1]}至少要出現(xiàn) 1次。設(shè)掃描得到的{li[1]}出現(xiàn)次數(shù)為 a，如果 a＜(k-2)，則可以將 Lk-1中所有以 li[1]開頭的(k-1)項集全部刪除，如果a≥(k-2)，那么比較掃描得到的{li[1]，li[2]}出現(xiàn)次數(shù) b 與(k-3)的大小，若 b＜(k-3)，則刪除 Lk-1中所有以{li[1]，li[2]}開頭的項集，如果b≥(k-3)，則繼續(xù)比較下一項。通過簡單的數(shù)字比較，可以大量地從Lk-1中刪除項集，這樣可以大大地減少不必要的連接。連接生成的k項集，也只需要比較1次就可以確定是否屬于Ck，其算法如下：

輸入：D(事物數(shù)據(jù)庫)；

min_sup:最小支持度計數(shù)閾值。

輸出：L(D中的頻繁項集)。

(1)掃描數(shù)據(jù)庫D，生成頻繁1項集L1；

(2)由頻繁1項集生成頻繁2項集L2；

(3)for(i=1；li∈Lk；i++)。

(4)累加{li[1]}、{li[1]，li[2]}、…、{li[1]，li[2]， …，li[k-1]}的出現(xiàn)次數(shù)；

(5)將只含 li[1]項的項集出現(xiàn)次數(shù) a與(k-1)比較大小，如果a小于(k-1)，則刪除 Lk中的所有以 li[1]項開頭的項集，從li+1[1]項的項集出現(xiàn)次數(shù)開始比較；如果a大于(k-1)，再比較以{li[1]，li[2]}開頭的項集出現(xiàn)次數(shù) b與(k-2)的大小。如果 b小于(k-2)，則刪除 Lk中的所有以{li[1]，li[2]}開頭的項集，并將只含 li[1]項的項集出現(xiàn)次數(shù)賦值為(a-b)，再對(a-b)與(k-1)進(jìn)行比較；如果 b大于(k-2)，再對以{li[1]，li[2]，li[3]}開頭的項集出現(xiàn)次數(shù)c與(k-3)的大小進(jìn)行比較。依次類推，刪除后Lk項集為 Lk′。

(6)用 Lk′中的項集自連接生成 C′k+1；

(7)for(i=1；li∈C′k+1；i++)

if({li[2]，li[3]，…，li[k]}∈Lk)

li是候選項集，放入 Ck+1中；

(8)掃描數(shù)據(jù)庫，對Ck+1中項集進(jìn)行計數(shù)，如果大于min_sup，就是頻繁項集，放入Lk+1中。

3 實例說明

通過由頻繁3項集生成4項候選集的例子，說明是如何通過改進(jìn)的算法在連接前對頻繁3項集進(jìn)行刪減的。 設(shè) L3={{I1，I2，I3}，{I1，I2，I6}，{I2，I3，I4}，{I2，I3，I5}，{I2，I4，I5}，{I3，I4，I5}，{I3，I5，I6}，{I4，I5，I6}}。 掃描 L3，得到相關(guān)的計數(shù)。表1所示為刪減L3中項集的過程。

經(jīng)過刪減得 Lk′={{I2，I3，I4}，{I2，I3，I5}}，Lk′自連接只生成 1 個 4 項集{I2，I3，I4，I5}。 {I3，I4，I5}∈L3，所以 ，得到候選項集 C4={I2，I3，I4，I5}。 通過驗證，結(jié)果是正確的。

如果采用經(jīng)典的Apriori算法，先連接生成2個4項集{I1，I2，I3，I6}，{I2，I3，I4，I5}， 再進(jìn)行剪枝 ， 最壞情況下 ，需要掃描8個子項集是否在L3中，才能確定，{I1，I2，I3，I6}，{I2，I3，I4，I5}是否為候選項集 ， 最好的情況下也需要掃描2個子集。而采用新的算法，只連接生成1個4項集，再進(jìn)行剪枝步，只需要掃描 1個子項集{I3，I4，I5}是否在 L3中。

本文運用新的算法，從另一個先刪減再連接的新視角來生成頻繁項集，可以減少大量的無用連接，進(jìn)而也減少了剪枝步需要判斷是否為候選項集的數(shù)量，在時間上提高了效率。但是對Apriori算法改進(jìn)的并不徹底，依然需要大量的數(shù)據(jù)庫掃描，在未來的研究工作中著力解決多次掃描數(shù)據(jù)庫的問題。

[1]HAN Jia Wei，KAMBER M.數(shù)據(jù)挖掘概念與技術(shù)[M].范明，孟小峰，譯.北京：機械工業(yè)出版社，2007.

[2]楊明，孫志揮，宋余慶.快速更新全局頻繁項目集 [J].軟件學(xué)報 ，2004，15(8)：1189-1196.

[3]郭健美，宋順林，李世松.基于 Apriori算法的改進(jìn)算法 [J].計算機工程與設(shè)計，2008，29(11)：2814-2815.

[4]馮興杰，周諄.Apriori算法的改進(jìn)[J].計算機工程，2005，31(21)：172-173.

[5]朱其祥，徐勇，張林.基于改進(jìn) Apriori算法的關(guān)聯(lián)規(guī)則挖掘研究[J].計算機技術(shù)與發(fā)展，2006，16(7)：102-104.

[6]MING Cheng Tseng， WEN Yang Lin， RONG Jeng.Dynamic mining of multi-supported association rules with classification ontology[J].網(wǎng)際網(wǎng)路技術(shù)學(xué)刊， 2006，7(14)：399-406.

表1 刪減L3中的項集