摘 要：本文主要介紹了關(guān)聯(lián)規(guī)則中的Apriori算法。通過(guò)對(duì)該算法的研究，挖掘數(shù)據(jù)之間的聯(lián)動(dòng)關(guān)系。

關(guān)鍵詞：關(guān)聯(lián)；Apriori

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

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

1 算法的偽碼實(shí)現(xiàn)

算法的偽碼表示如下：

輸入： D：事務(wù)數(shù)據(jù)庫(kù)；

min_sup：最小支持度計(jì)數(shù)閾值。

輸出：L：所有頻繁項(xiàng)集。

方法：

（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 算法的實(shí)例

假設(shè)數(shù)據(jù)庫(kù)中有10個(gè)事務(wù)，數(shù)據(jù)庫(kù)如下：

表2.2 原始數(shù)據(jù)庫(kù)

事務(wù)TID 項(xiàng)集

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）第一次執(zhí)行，找出項(xiàng)集中所有的項(xiàng)構(gòu)成候選1項(xiàng)集C1，并對(duì)每個(gè)項(xiàng)統(tǒng)計(jì)出現(xiàn)的次數(shù)。如果規(guī)定的最小支持度計(jì)數(shù)min_sup=2（2為絕對(duì)支持度），則找出候選1項(xiàng)集中大于min_sup的項(xiàng)，然后構(gòu)成頻繁一項(xiàng)集L1。

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

再進(jìn)行剪枝步，由于1項(xiàng)集都是頻繁的，所以不用剪枝，都進(jìn)入C2中。

（3）將各個(gè)項(xiàng)集的支持度計(jì)數(shù)與最小支持度計(jì)數(shù)閾值進(jìn)行比較，刪除小于min_sup的項(xiàng)集，結(jié)果就是L2，即頻繁2項(xiàng)集。然后對(duì)L2進(jìn)行自連接，連接完成后進(jìn)行剪枝，這里需

要根據(jù)Apriori算法的性質(zhì)來(lái)刪除部分項(xiàng)集，然后產(chǎn)生候選項(xiàng)集C3。根據(jù)性質(zhì)，頻繁項(xiàng)集的各個(gè)子集都是頻繁的，刪除C3中不頻繁的項(xiàng)集{B1，B2，B5}，{B1，B3， B5}。這樣在后面的掃描過(guò)程中就不需要計(jì)算它們的支持度了。

（4）得到候選項(xiàng)集C3后，再在原始數(shù)據(jù)庫(kù)中掃描一次，計(jì)算各個(gè)項(xiàng)集的支持度，然后

把小于min_sup的項(xiàng)集刪除，得到頻繁3項(xiàng)集L3。

（5）因?yàn)長(zhǎng)3中只有一個(gè)項(xiàng)集，無(wú)法再產(chǎn)生4項(xiàng)集了，因此算法結(jié)束，把前面的頻繁項(xiàng)集綜合起來(lái)，構(gòu)成了全部的頻繁項(xiàng)集。這樣，運(yùn)用Apriori算法就求得了所有的頻繁項(xiàng)集。

作者簡(jiǎn)介

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