一種新的改進Apriori算法*

楊金鳳，劉 鋒

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

數據挖掘DM(Data Mining)出現于 20世紀80年代后期，是在數據庫技術的基礎上，結合人工智能、機器學習、統計學、神經網絡等多種學科技術產生的具有很強生命力的新研究領域。其中關聯規則挖掘研究[1-2]是一項重要的內容，目的是發現大規模數據集中項集之間有趣的關聯關系或模式。

頻繁項集的挖掘是關聯規則挖掘的核心，如何高效地從海量數據庫中找出頻繁出現的項集是世界范圍內的熱門研究課題。

1 相關概念[1]

設 I={I1，I2，…，Im}是項的集合，稱為項集，包含 k 個項的項集稱為k項集。D是數據庫事務的集合，數據庫中的每個事務T是項的集合，T?I，TID是事務 T的標識符。設A是一個項集，事務T包含A，當且僅當A?T，一個包含k個項的事務T可以產生2k個非空的子項集。

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

2 Apriori算法和優化

2.1 經典的Apriori算法[2-6]

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

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

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

經典的Apriori算法在產生候選項集上，由Lk-1自連接產生Ck，然后再利用Apriori性質對Ck進行刪減。設l1和 l2是 Lk-1中的項集。 記號 li[j]表示 li中的第 j項(例如，l1[k-2]表示l1的倒數第 2項)。Apriori假定事務或項集中的項按字典次序排序。執行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是可以連接的，否則是不可以連接的，連接結果項集是 l1[1]，l1[2]，…，l1[k-1]，l2[k-2]。 然后再利用 Apriori性質進行判斷項集 l1[1]，l1[2]，…，l1[k-1]，l2[k-2]是否可能是頻繁的，這樣需要先產生項集l1[1]，l1[2]， … ，l1[k-1]，l2[k-2]的(k-1)個 (k-1)項子集 ，然后依次比較(k-1)個子集是否在Lk-1中，如果出現不在，則刪減項集 l1[1]，l1[2]， … ，l1[k-1]，l2[k-2]； 如果都在，再對數據庫掃描，進行計數。

2.2 對Apriori算法的改進

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

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

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

min_sup:最小支持度計數閾值。

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

(1)掃描數據庫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]}的出現次數；

(5)將只含 li[1]項的項集出現次數 a與(k-1)比較大小，如果a小于(k-1)，則刪除 Lk中的所有以 li[1]項開頭的項集，從li+1[1]項的項集出現次數開始比較；如果a大于(k-1)，再比較以{li[1]，li[2]}開頭的項集出現次數 b與(k-2)的大小。如果 b小于(k-2)，則刪除 Lk中的所有以{li[1]，li[2]}開頭的項集，并將只含 li[1]項的項集出現次數賦值為(a-b)，再對(a-b)與(k-1)進行比較；如果 b大于(k-2)，再對以{li[1]，li[2]，li[3]}開頭的項集出現次數c與(k-3)的大小進行比較。依次類推，刪除后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)掃描數據庫，對Ck+1中項集進行計數，如果大于min_sup，就是頻繁項集，放入Lk+1中。

3 實例說明

通過由頻繁3項集生成4項候選集的例子，說明是如何通過改進的算法在連接前對頻繁3項集進行刪減的。 設 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，得到相關的計數。表1所示為刪減L3中項集的過程。

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

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

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

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

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

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

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

[5]朱其祥，徐勇，張林.基于改進 Apriori算法的關聯規則挖掘研究[J].計算機技術與發展，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].網際網路技術學刊， 2006，7(14)：399-406.

表1 刪減L3中的項集