安穎 馬桂真

（北京聯(lián)合大學旅游學院 北京市 100101）

在數(shù)據(jù)挖掘的知識模式中，關聯(lián)規(guī)則用于表示數(shù)據(jù)庫中一組對象之間某種關聯(lián)關系的規(guī)則。關聯(lián)規(guī)則的挖掘就是要找出支持度大于等于指定的最小支持度閥值這樣的一些規(guī)則，挖掘過程分兩步完成：

步驟一：找出所有支持度大于事先給定的最小支持度的頻繁項集；

步驟二：從找出的頻繁項集中產(chǎn)生強關聯(lián)規(guī)則，即產(chǎn)生那些支持度大于等于預先給定的最小支持度的關聯(lián)規(guī)則。

關聯(lián)規(guī)則挖掘的特點是數(shù)據(jù)量龐大，所以算法的總體性能主要取決于第一步，因此高效率地找出所有頻繁項目集是衡量關聯(lián)規(guī)則挖掘算法性能的重要指標。在傳統(tǒng)的算法中，往往通過多次掃描數(shù)據(jù)庫來實現(xiàn)，算法的主要時間將花費在掃描數(shù)據(jù)庫和I/O 操作上，因此算法運行效率較低，也是各種改進算法需要解決的核心問題。

1 經(jīng)典關聯(lián)規(guī)則算法

1.1 經(jīng)典Apriori算法

關聯(lián)規(guī)則挖掘的經(jīng)典算法是Agrawal 等人在1994年提出的Apriori 算法。隨后，圍繞著如何提高這個算法的性能問題，研究人員進行了大量的改進工作。

Apriori 算法發(fā)現(xiàn)關聯(lián)規(guī)則的過程首先要找出所有支持度大于等于預先給定的最小支持度閥值的所有屬性的組合，稱為頻繁項集，記為Lk，這一步是算法性能高低的關鍵步驟。然后利用頻繁項集產(chǎn)生滿足最小支持度閥值的所有規(guī)則。為了找到Lk，Apriori 算法使用一種稱為逐層搜索的迭代方法，即首先通過Lk-1 與自己連接產(chǎn)生候選K-項集，記為Ck，然后通過剪枝，剔除Ck 中非頻繁項集，得到Lk。

1.2 影響Apriori算法性能的主要問題

基于頻繁項集的Apriori 算法采用了逐層搜索的迭代的方法，即利用候選項集和頻繁項集得到全部頻繁項集，并通過對候選項集的剪枝，大幅度降低了候選項集的大小，得到了預期的結果。然而，Apriori 算法在性能上仍存在著一些問題：

該算法需要重復掃描數(shù)據(jù)庫來計算侯選項集的支持度計數(shù)，從而嚴重影響了算法的運行效率。

2 Apriori算法改進

針對Apriori 算法瓶頸問題，本文提出了一種改進算法，即通過減少數(shù)據(jù)庫掃描次數(shù)的方法提高Apriori 算法的效率。

2.1 BTA算法思想

圖1：兩種算法在不同支持度閥值下的時間開銷

在經(jīng)典的Apriori 算法中，計算侯選項集的支持度計數(shù)是通過重復掃描數(shù)據(jù)庫來實現(xiàn)的。為了改善這個問題，提高算法性能，本文提出一種基于事務標號集的關聯(lián)規(guī)則算法BTA(Based on Tid_set Apriori)。

BTA 算法只在第一次掃描數(shù)據(jù)庫得到頻繁項集各項的事務標識號后，就無需再對數(shù)據(jù)庫進行掃描，由頻繁n 項集在生成候選n+1項集時，對相關項的Tid 集進行交運算，生成新的Tid 集，通過Tid 集中包含的事務數(shù)計算候選集中相關項的支持度。將大于支持度閥值的記錄組成頻繁n+1 項集，如此反復，直到產(chǎn)出最終所需要的頻繁項集為止。區(qū)別于經(jīng)典的Apriori 算法，BTA 算法只需要在產(chǎn)生侯選1-項集時掃描一次數(shù)據(jù)庫，計算剩余的侯選項集支持度計數(shù)時只統(tǒng)計相應Tid 集合元素的個數(shù)即可。這樣就不用重復掃描數(shù)據(jù)庫，降低了訪問數(shù)據(jù)庫的I/O 操作時間，提高了Apriori 算法的效率。

BTA 算法基本步驟為：

（1）首先，逐個掃描事務數(shù)據(jù)庫，產(chǎn)生1-項候選集合Cl，在掃描每個事務時，除了對每個項計數(shù)外，還要記錄包含該項的事務標識符Tid。這樣掃描完一遍數(shù)據(jù)庫后，我們得到的候選集Cl中，每個項集都包含一個相應的事務標識符列表。Cl的結構如下：

(項集Item_set，支持度計數(shù)support，事務標識符集Tid_set)

（2）從Cl中刪除不滿足最小支持度計數(shù)的項集，得到Ll。

（3）Lk-1進行自連接，生成Ck，其中Ck的事務標識符集等于生成它的兩個Lk-1的事務標識符集的交集。計算Ck中項集所對應的事務標識符集中的Tid 個數(shù)，就得到了Ck中每一個項集的計數(shù)。

2.2 BTA算法描述

下面是BTA 算法的描述：

輸入：事務數(shù)據(jù)庫D；最小支持度閥值minsup。

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

Cl=create_candidaet_1(D) ；//創(chuàng)建1-項侯選集

Ll={cand∈Clcand.support)>= minsup}；//選出1-項頻繁集

For (K=2；Lk-1<>φ；k++)

｛apriori_generate (Lk-1，minsup)；// 調用apriori_generate 生成候選集Ck

Lk= Ck.Item_set；/選出頻繁項集Lk

｝

Answer：L=∪kLk；/合并所有的Lk

Procedure apriori_generate (Lk-1: frequence _item;minsup:int)

//產(chǎn)生最小支持度為minsup 的候選集Ck

{for each Item_set li∈Lk-1

for each Item_set lj∈Lk-1

if (li[1]= lj[1]∧li[2]=lj[2]∧……∧li[k-2]= lj[k-2]∧li[k-1]< lj[k-1]) then

{cand= li∪lj//連接頻繁項集Lk-1，得到一個候選項集C

If has_inftequence_subset(cand, Lk-1) then // 利 用Apriori 性質剪枝

Delete cand；

Else

{cand.Tid_set=li.Tid_set ∩lj.Tid_set；//計算該項集的事務標識集的交集

cand.support=length(cand.Tid_set) ；//計算該項集的支持度計數(shù)if cand.support

delete cand；

else

add cand to Ck

}

}

Return Ck；

}

Procedure has_infrequence_subset(cand:candidate_k_itemset；Lk-1:frequence(k-1)_itemset)

//判斷候選項集的子集是否為頻繁項集

For each(k-1)_subset s of cand

If s ! ∈ Lk-1 then

Return true；

Return flase；

2.3 實驗驗證BTA算法與Apriori算法的性能

通過上述算法描述可以看出，BTA 算法只有在第一步生成侯選1-項集Cl的時候掃描了一遍數(shù)據(jù)庫，從而獲得了每個項集的Tid 列表；計算其他侯選項集支持度計數(shù)時，只需統(tǒng)計侯選項集中相應事務標識符列表中的Tid 個數(shù)即可。假設侯選項集Cl的數(shù)目為|Cl|，數(shù)據(jù)庫中的記錄數(shù)為n，每條記錄的平均容量為v，則計算侯選集C1 所需的時間為O(|Cl|nv)，由于只掃描一遍數(shù)據(jù)庫，因此BTA 算法總時間開銷為O(|Cl|nv)(此處忽略內存運行時間)。與Apriori 經(jīng)典算法的總時間開銷O(∑k|Ck|nv)相比，BTA 算法大大節(jié)省了時間開銷。

為了便于比較，我們利用模擬實驗數(shù)據(jù)集測試兩種算法的運行時間。實驗環(huán)境：計算機硬件配置是Intel Core CPU 2.5GHZ/4GB/100GB，操作系統(tǒng)是Windows7，在VC++6.0 編程環(huán)境中分別實現(xiàn)Apriori 和BTA 算法。

實驗數(shù)據(jù)集為：Mushroom，含8124 個事務，該數(shù)據(jù)庫由蘑菇的顏色、氣味、形狀、生長環(huán)境、……、類別等23 個屬性組成。每種屬性有2～12 個枚舉值，共128 個不同項。數(shù)據(jù)集取自UCI Machine Learning Repositoty。在不同的支持度閥值下，兩種算法執(zhí)行時間如圖1 所示。

3 結論

綜上所述，針對不同的支持度，BTA 算法的執(zhí)行效率要比Apriori 算法高。而且BTA 算法的執(zhí)行效率優(yōu)勢在支持度較小時更加明顯，其原因是隨著支持度的減小，候選項目集逐漸增多，Apriori 算法進行數(shù)據(jù)庫掃描計算支持度所需時間迅速增加。而BTA 算法只需掃描一次數(shù)據(jù)庫，通過事務標識符集的交集計算支持度，算法運行時間得到很大的縮減。