基于Apriori算法的降低數據庫掃描記錄數的挖掘算法研究

安穎 馬桂真

（北京聯合大學旅游學院 北京市 100101）

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

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

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

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

1 經典關聯規則算法

1.1 經典Apriori算法

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

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

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

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

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

2 Apriori算法改進

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

2.1 BTA算法思想

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

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

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

BTA 算法基本步驟為：

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

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

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

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

2.2 BTA算法描述

下面是BTA 算法的描述：

輸入：事務數據庫D；最小支持度閥值minsup。

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

Cl=create_candidaet_1(D) ；//創建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)

//產生最小支持度為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) ；//計算該項集的支持度計數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的時候掃描了一遍數據庫，從而獲得了每個項集的Tid 列表；計算其他侯選項集支持度計數時，只需統計侯選項集中相應事務標識符列表中的Tid 個數即可。假設侯選項集Cl的數目為|Cl|，數據庫中的記錄數為n，每條記錄的平均容量為v，則計算侯選集C1 所需的時間為O(|Cl|nv)，由于只掃描一遍數據庫，因此BTA 算法總時間開銷為O(|Cl|nv)(此處忽略內存運行時間)。與Apriori 經典算法的總時間開銷O(∑k|Ck|nv)相比，BTA 算法大大節省了時間開銷。

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

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

3 結論

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