一種改進(jìn)的Apriori算法的研究

王平

摘要：本文對關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘經(jīng)典算法Apriori算法需要重復(fù)掃描數(shù)據(jù)庫的不足提出了一種新算法。該算法在連接兩個頻繁（k-1）-項集時，對其事務(wù)標(biāo)識符進(jìn)行交計算，得到新的候選k-項集。避免了對數(shù)據(jù)庫的頻繁掃描，大大提高了算法效率。

關(guān)鍵詞：Apriori 關(guān)聯(lián)規(guī)則 數(shù)據(jù)挖掘

中圖分類號：TP311.13 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2014）12-0132-02

1 Apriori算法簡介

在已經(jīng)提出的所有關(guān)聯(lián)規(guī)則的算法中，最經(jīng)典的算法是Agrawal和Srikant的Apriori算法（1993）[1]。Apriori算法的具體執(zhí)行步驟如下：

先產(chǎn)生頻繁1-項集L1。首先掃描數(shù)據(jù)庫，識別所有單個項（1-項集），記為C1。統(tǒng)計數(shù)據(jù)庫中有多少個事務(wù)包含該項，這些事務(wù)的計數(shù)叫做1-項集的支持度。刪除支持度低于用戶所規(guī)定的最小支持度的1-項集，得到頻繁1-項集，記為L1。

對于k=2，3，…，產(chǎn)生過程按如下方法由頻繁（k-1）-項集得到頻繁k-項集。在頻繁（k-1）-項集列表上進(jìn)行（k-1）-項集對的連接運算，創(chuàng)建候選k-項集列表。當(dāng)且僅當(dāng)兩個項集的前（k-2）項相同，一對（k-1）-項集被連接在一起。如果條件滿足，則該對能連接成一個k-項集，它包括前（k-2）個公共項和兩個非公共項，兩個非公項分別來自兩個（k-1）-項的成員。

根據(jù)Apriori的性質(zhì)，一個項集是頻繁的，則它的所有非空子集都必須頻繁的。換句話說，如果一個項集不是頻繁的，則它的所有超集都不可能是頻繁的。

推廣到一般情況，在Lk-1中通過與自身項集的連接得到候選k-項集。為壓縮Ck，結(jié)合Apriori性質(zhì)，若一個候選k-項集Ck的（k-1）項子集不在Lk中，則該候選也不可能是頻繁的，從而將其從Ck中刪除。選擇不小于最小支持度的候選項集，得到Lk。重復(fù)以上過程，直到不再有候選（或頻繁）項集為止。

2 Apriori算法缺陷分析

（1）對于每次生成的候選項集Ck的每一個候選項集，都必須掃描數(shù)據(jù)庫進(jìn)行其支持度計數(shù)。掃描過程需要數(shù)據(jù)頻繁地進(jìn)出，因此算法效率很低。

（2）產(chǎn)生了大量的候選項集，候選2-項集尤為多。Ck是Lk的超集，呈指數(shù)級增長。

3 Apriori算法的改進(jìn)

針對Apriori算法的兩個致命的缺陷，國內(nèi)外專家學(xué)者提出以Apriori算法為基礎(chǔ)的一些改進(jìn)算法。Savasere等[2]提出了基于數(shù)據(jù)分割的算法，將數(shù)據(jù)庫中的事務(wù)劃分成多個互不相交的塊，在不同的塊上產(chǎn)生局部頻繁項集，通過對原數(shù)據(jù)庫的兩次掃描完成頻繁項集的挖掘。Brin等[3]提出了基于動態(tài)項集計數(shù)的DIC算法，其與Apriori算法的區(qū)別在于，將事務(wù)數(shù)據(jù)庫劃分成多個區(qū)段，在搜索數(shù)據(jù)庫時，利用各區(qū)段的特性，動態(tài)產(chǎn)生候選集的同時也能計算出其支持度。

對各種算法進(jìn)行了分析與研究，發(fā)現(xiàn)影響算法效率的主要缺陷是頻繁地掃描數(shù)據(jù)庫，為減少掃描次數(shù)而提出了一種新的算法。算法步驟如下：

（1）掃描所有事務(wù)，對每個項計數(shù)，產(chǎn)生候選項集C1。C1不只是數(shù)據(jù)項集和計數(shù)的集合，而同時為產(chǎn)生的每個候選項集添加一個屬性：事務(wù)標(biāo)識符。將小于最小支持度計數(shù)的候選項刪除，得到頻繁1-項集L1。

（2）Lk-1自身進(jìn)行連接操作，生成k-項集Ck。此過程需生成Ck的事務(wù)標(biāo)識符，即把兩個滿足連接條件的Lk-1標(biāo)識符進(jìn)行求交計算。再統(tǒng)計Ck各項集中事務(wù)標(biāo)識符的計數(shù)，即Ck各項集的計數(shù)（如表1）。

具體執(zhí)行過程：

（1）掃描數(shù)據(jù)庫，產(chǎn)生候選集C1，如表2所示。

（2）由C1確定頻繁項集L1（如表3）。

（3）對L1進(jìn)行連接，生成C2。每生成一個新的候選項集，通過計算兩個項的事務(wù)標(biāo)識符的交，然后統(tǒng)計新的事務(wù)標(biāo)識個數(shù)，并與最小支持度進(jìn)行比較，如果新的事務(wù)標(biāo)識符的計數(shù)小于最小支持度，則將該項從C2中刪除。

{A，B}.LIST=A.list∩B.list={S1，S4，S8，S9}≥min_sup

{A，C}.LIST=A.list∩C.list={S5，S7，S8，S9}≥min_sup

{A，D}.LIST=A.list∩D.list={S4}≤min_sup（刪除）

{A，E}.LIST=A.list∩E.list={S1，S8}≥min_sup

{B，C}.LIST=B.list∩C.list={S3，S6，S8，S9}≥min_sup

{B，D}.LIST=B.list∩D.list={S2，S4}≥min_sup

{B，E}.LIST=B.list∩E.list={S1，S8}≥min_sup

{C，D}.LIST=C.list∩D.list=≤min_sup（刪除）

{C，E}.LIST=C.list∩E.list={S8}≥min_sup

{D，E}.LIST=D.list∩E.list=≤min_sup（刪除）

通過以上計算得出帶有事務(wù)標(biāo)識符屬性的候選項集C2，如表4所示。

（4）根據(jù)上表生成頻繁2-項集L2，如表5所示。

（5）重復(fù)步驟3，生成C3。

根據(jù)其Apriori性質(zhì)可得，{A，C，E}，{B，C，D}，{B，C，E}，{B，D，E}均被剪枝。

只剩項集{A，B，C}.list={S8，S9}

{A，B，E}.list={S1，S8}

由此結(jié)果生成候選項集C3，如表6所示。

（6）生成頻繁項集L3，如表7所示。

（7）生成C4。

{A，B，C，E}.list={S8}≤min_sup，因此L4=。

至此不再產(chǎn)生新的候選項集，算法終止，找到了全部的頻繁項集。

從以上可以看出，Apriori改進(jìn)算法相比未改進(jìn)的Apriori算法的優(yōu)勢在于：在整個數(shù)據(jù)挖掘過程只對數(shù)據(jù)庫掃描一次。改進(jìn)算法只在第一步產(chǎn)生1-候選項集C1時需要對數(shù)據(jù)庫掃描一次，以便獲取當(dāng)前所有項集的事務(wù)標(biāo)識符。之后不需要掃描事務(wù)數(shù)據(jù)庫去確定每個項集的支持度，只需統(tǒng)計Ck中事務(wù)標(biāo)識符的個數(shù)。新算法在時間上具有明顯優(yōu)勢，尤其數(shù)據(jù)量比較龐大時，這種優(yōu)勢更加顯著。

參考文獻(xiàn)

[1]（印度）K.P.Soman Shyam Diwakar.數(shù)據(jù)挖掘基礎(chǔ)教程[M].范明，牛常勇譯.北京：機械工業(yè)出版社，2012.120-129.

[2]Savasere A，Omiecinski E，Navathe S.An efficient algorithm for mining association rules inlarge databases[C].Morgan Kaufmann Publisher，1995.432-443.

[3]Brin S，Motwani R，Ullman J D，et al. Dynamic itemset counting and implication rules for market basket data[C].ACM Publisher Press 1997.255-264.endprint