關聯規則中經典的Apriori算法研究

摘 要：本文主要介紹了關聯規則中的Apriori算法。通過對該算法的研究，挖掘數據之間的聯動關系。

關鍵詞：關聯；Apriori

Apriori算法使用了逐層查尋的方式，一遍一遍的掃描事務數據庫，得到各層頻繁K項集，并利用當層得到的K項集，生成候選的（K+1）項集，直到不能再生成頻繁K項集為止。關聯挖掘問題被分成如下2個問題：⑴尋找所有的這樣的項的集合，它們的支持度不小于用戶指定的最小支持度閾值，這樣的集合稱為頻繁項集。⑵利用頻繁項集產生規則。一般的想法是，如果B1，B2，B3和B1，B2是頻繁項集，那么通過計算置信度，conf=P（B1B2B3）/P（B1B2）來確定{B1，B2，B3}這個規則是否成立，當它不小于最小置信度閾值時，規則成立。為了避免需要算出所有項集的支持度，Apriori引入了候選項集概念，并將候選項集記為Ck。這里需要介紹關聯規則兩條重要的性質，如下：（1）頻繁項集的所有非空子集也必須是頻繁的。 （2）非頻繁項集的所有超集一定是非頻繁的。

例如，如果項集{ B1，B2}是非頻繁的，即數據庫中同時包含的B1，B2的事務的個數小于min_sup，那么數據庫中同時包含B1，B2，B3的事務的個數肯定是小于min_sup的，即{B1，B2，B3}一定是非頻繁的。而Apriori算法只運用了性質（1），通過已經找到的頻繁項集去構造更大的頻繁項集，就是候選項集Ck，它是有可能成為頻繁k項集的項集的集合。使用Lk-1生成Lk的詳細過程如下：（1）連接步驟：通過Lk-1∞Lk-1來生成Ck：如果Lk-1中兩個頻繁項集L1和L2的前（k-2）個項相同，但L1的第（k-1）項排在L2的第（k-1）項的前面，那么將它們合在一起可以形成一個k項集。（2）修剪步驟：A.如果Ck中一個候選k項集的某個（k-1）子項集不在Lk-1中，則將該候選項集從Ck中刪除。B.對仍在Ck中的沒被刪除的候選k項集，掃描數據庫來計算它們的支持度計數，生成Lk，Lk中包含了Ck中支持度不小于min_sup的所有項集，它們都是k項頻繁項集。

1 算法的偽碼實現

算法的偽碼表示如下：

輸入： D：事務數據庫；

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

輸出：L：所有頻繁項集。

方法：

（1） L1={frequent 1-itemsets}；

for（k=2；Lk-1≠，k++）

{ Ck=apriori-gen（Lk-1）； for each transaction t∈D

{Ct=subset（Ck，t）；

for each candidate c∈Ct

c.count++；}

Lk={c∈Ck|c.count≥min_sup}}

return L=kLk

（2） procedure apriori-gen（Lk-1：frequent （k-1）-itemsets）

for each itemset L1∈Lk-1

for each itemset L2∈Lk-1

if （L1[1]^L2[1]）= （L1[2]^L2[2]）=^…^ （L1[k-1]

{

c=L1∞L2；

if has_infrequent_subset（c，Lk-1）then

delete c； else

add c to Ck；

} return Ck；

（3） procedure has_infrequent_subset（c，Lk-1）

for each （k-1）-subset s of c

if sLk-1

return TRUE；

return FALSE；

2 算法的實例

假設數據庫中有10個事務，數據庫如下：

表2.2 原始數據庫

事務TID 項集

TID1 B1，B2，B3

TID2 B2，B3，B5

TID3 B3，B4

TID4 B1，B2，B3

TID5 B1，B3

TID6 B2，B5

TID7 B1，B2

TID8 B2，B3

TID9 B2，B4

TID10 B1，B3，B5

（1）第一次執行，找出項集中所有的項構成候選1項集C1，并對每個項統計出現的次數。如果規定的最小支持度計數min_sup=2（2為絕對支持度），則找出候選1項集中大于min_sup的項，然后構成頻繁一項集L1。

（2）第二次執行是為了求的2項集L2，這里需要對L1進行自身連接產生C2。設n=|L1|表示的是L1中項的個數，那么C2產生的2項集的個數則是n（n-1）/2，如果項集太多的話，那么如此多的項集對時間效率和空間容量是個巨大的考驗。而本例的項集較小，連接步之后，

再進行剪枝步，由于1項集都是頻繁的，所以不用剪枝，都進入C2中。

（3）將各個項集的支持度計數與最小支持度計數閾值進行比較，刪除小于min_sup的項集，結果就是L2，即頻繁2項集。然后對L2進行自連接，連接完成后進行剪枝，這里需

要根據Apriori算法的性質來刪除部分項集，然后產生候選項集C3。根據性質，頻繁項集的各個子集都是頻繁的，刪除C3中不頻繁的項集{B1，B2，B5}，{B1，B3， B5}。這樣在后面的掃描過程中就不需要計算它們的支持度了。

（4）得到候選項集C3后，再在原始數據庫中掃描一次，計算各個項集的支持度，然后

把小于min_sup的項集刪除，得到頻繁3項集L3。

（5）因為L3中只有一個項集，無法再產生4項集了，因此算法結束，把前面的頻繁項集綜合起來，構成了全部的頻繁項集。這樣，運用Apriori算法就求得了所有的頻繁項集。

作者簡介

朱建斌（1980-），江西南昌人，本科.研究方向：電工電子。