基于Apriori算法的降低數(shù)據(jù)庫掃描記錄數(shù)的挖掘算法研究

安穎 馬桂真

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

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

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

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

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

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

1.1 經(jīng)典Apriori算法

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

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

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

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

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

2 Apriori算法改進(jìn)

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

2.1 BTA算法思想

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

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

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

BTA 算法基本步驟為：

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

(項(xiàng)集Item_set，支持度計(jì)數(shù)support，事務(wù)標(biāo)識(shí)符集Tid_set)

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

（3）Lk-1進(jìn)行自連接，生成Ck，其中Ck的事務(wù)標(biāo)識(shí)符集等于生成它的兩個(gè)Lk-1的事務(wù)標(biāo)識(shí)符集的交集。計(jì)算Ck中項(xiàng)集所對(duì)應(yīng)的事務(wù)標(biāo)識(shí)符集中的Tid 個(gè)數(shù)，就得到了Ck中每一個(gè)項(xiàng)集的計(jì)數(shù)。

2.2 BTA算法描述

下面是BTA 算法的描述：

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

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

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

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

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

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

Lk= Ck.Item_set；/選出頻繁項(xiàng)集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//連接頻繁項(xiàng)集Lk-1，得到一個(gè)候選項(xiàng)集C

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

Delete cand；

Else

{cand.Tid_set=li.Tid_set ∩lj.Tid_set；//計(jì)算該項(xiàng)集的事務(wù)標(biāo)識(shí)集的交集

cand.support=length(cand.Tid_set) ；//計(jì)算該項(xiàng)集的支持度計(jì)數(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)

//判斷候選項(xiàng)集的子集是否為頻繁項(xiàng)集

For each(k-1)_subset s of cand

If s ! ∈ Lk-1 then

Return true；

Return flase；

2.3 實(shí)驗(yàn)驗(yàn)證BTA算法與Apriori算法的性能

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

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

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

3 結(jié)論

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