一種改進(jìn)的AprioriTid算法*

張偉科

(沈陽理工大學(xué) 理學(xué)院， 沈陽 110159)

一種改進(jìn)的AprioriTid算法*

張偉科

(沈陽理工大學(xué) 理學(xué)院， 沈陽 110159)

針對經(jīng)典Apriori算法多次掃描數(shù)據(jù)庫產(chǎn)生I/O負(fù)載影響運行效率等問題，在對Apriori算法的原理及其相關(guān)改進(jìn)算法研究的基礎(chǔ)上，提出了一種基于壓縮集的改進(jìn)Apriori算法，即AprioriTid_M算法.通過有效的裁剪方法減少無效項集的產(chǎn)生，減少候選項集的數(shù)量，從而提高算法的效率.仿真實驗表明，在支持度相同但數(shù)據(jù)量不同，以及數(shù)據(jù)量相同但支持度不同這兩種條件下，AprioriTid_M算法在性能上和運算時間上都比Apriori算法有很大程度的改善.

Apriori算法； AprioriTid算法； AprioriTid_M算法； 關(guān)聯(lián)規(guī)則； 置信度； 項集； 支持度； 性能

數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則中相當(dāng)經(jīng)典的算法就是Apriori算法，該算法具有反單調(diào)性的特點.Apriori算法首先生成候選項集判斷是否為頻繁項集[1]，所生成的頻繁項集的任一子集均是頻繁的，含有非頻繁項集的任意子集的項集一定是非頻繁的.運用迭代的思想，首先發(fā)現(xiàn)頻繁1項集，由頻繁k-1項集生成k候選項集，逐層掃描數(shù)據(jù)庫后從候選k項集中篩選出頻繁k項集，直到最終剩下的候選項集為空時算法結(jié)束[2].

1　Apriori算法核心思想

Apriori算法生成頻繁項集的算法描述如下.

輸入：數(shù)據(jù)集D，設(shè)置最小支持度min_sup的閾值.

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

L1=find_frequent_1-itemset(D)；

for(k=2；Lk-1≠φ；k++){

Ck=apriori_gen(Lk-1)；

//產(chǎn)生候選項集

for all transactiont∈D{

Ct=subset(Ck，t)；

//識別t包含的所有候項集

for all candidatesc∈Ct{

c.count++；

//支持度計算增值

}

}

//提取頻繁k項集

}

returnL=∪kLk；

procedure apriori_gen(Lk-1)

for eachitemsetl1∈Lk-1

for eachitemsetl2∈Lk-1

if(l1[1]=l2[1])∧…∧(l1[k-2]=l2[k-2])∧(l1[k-1]

c=join(l1，l2)；

//連接：產(chǎn)生候選項集

if has_infrequent_subset(c，Lk-1)then

deletec

//剪枝：移除非頻繁的候選項集

else

addctoCk

}

returnCk

procedure has_infrequent_subset(c，Lk-1)

//使用先驗知識判斷候選項集是否頻繁

for each(k-1)-subsetsofc

ifs?Lk-1then

return TRUE；

return FALSE

算法的具體步驟如下.

1) 單遍掃描數(shù)據(jù)集，得到每個項的支持度以及所有頻繁1項集的集合L1.

2) 通過調(diào)用apriori_gen[3]函數(shù)對前一次掃描得到的頻繁k-1項集再次掃描，依據(jù)每項的支持度使判斷閾值得到新的候選k項集.apriori_gen函數(shù)由頻繁k-1項集生成候選k項集，經(jīng)過連接和剪枝，其兩個步驟如下所示.

② 剪枝.由has_infrequent_subset函數(shù)完成[5]，判定候選項集中的k項集是否含有k-1非頻繁項集，若含有k-1項集是非頻繁的，則要將該候選項集刪除以此完成剪枝.圖1為Apriori算法挖掘事物數(shù)據(jù)的關(guān)聯(lián)規(guī)則流程圖.

圖1　關(guān)聯(lián)規(guī)則流程圖

雖然Apriori算法能夠?qū)崿F(xiàn)對數(shù)據(jù)項的關(guān)聯(lián)規(guī)則挖掘，但是隨著數(shù)據(jù)庫存儲量的增加和對算法的迭代應(yīng)用及研究，表明Apriori算法主要有兩方面運行性能瓶頸[6].

1) 反復(fù)多次掃描事物的數(shù)據(jù)庫，增加了I/O的負(fù)載.Apriori算法每次進(jìn)行k循環(huán)都要完整地掃描數(shù)據(jù)庫，判定候選項集Ck中的每一個元素是否能夠成為項集Lk.例如，一個最大頻繁項集中有15個項，就需要至少掃描事物數(shù)據(jù)庫15遍才能完成任務(wù).對于海量數(shù)據(jù)挖掘來說，I/O負(fù)載量非常大.

2) 海量數(shù)據(jù)會產(chǎn)生異常龐大的候選項集.項集Lk-1候選項集Ck是呈指數(shù)增長的，數(shù)量龐大.例如，104個頻繁1項集會產(chǎn)生大約107個元素的候選2項集[7].龐大的候選項集浪費了存儲空間，同時降低了運行效率，因此，算法的運行性能方面需加以優(yōu)化.

2　改進(jìn)的Apriori算法

2.1AprioriTid算法

AprioriTid算法主要是通過減少掃描事物數(shù)據(jù)量來實現(xiàn)性能優(yōu)化.一個事物中如果不包含k階大項集，則一定不含有k+1階的大項集.因此，忽略大項集事務(wù)后，可減少后續(xù)循環(huán)掃描事物的次數(shù)，并且不會影響到候選項集的支持度.

AprioriTid算法的過程描述如下：

L1={large 1-itemsets}；

//計算1階大項集

for(k=2；Lk-1≠φ；k=k+1)；

Ck=apriori_gen(Lk-1)；

//構(gòu)造候選項集

//t包含的候選項集

for allC∈CtdoC.sup=C.sup+1；end for

end if

//構(gòu)造k階候選項集的Tid表

end for

//計算k階大項集

end for

L=∪kLk

2.2AprioriTid_M算法

AprioriTid算法只在計算1項集的支持度時對數(shù)據(jù)庫D進(jìn)行了掃描，減少了運行時間，但是過于龐大的候選項集還是會影響運行時間，因此，本文提出一種基于壓縮集的AprioriTid_M改進(jìn)算法.根據(jù)原理，頻繁項集的所有非空子集一定是頻繁項集[9]，可得頻繁k項集的所有k-1項集一定也是頻繁的，以此為基礎(chǔ)進(jìn)一步地優(yōu)化Tid表.

性質(zhì)1如果頻繁k項集可以產(chǎn)生頻繁k+1項集，那么頻繁k項集中的項集個數(shù)一定大于k.

證明由一切頻繁項集的非空子集一定是頻繁的，推出Lk+1任何項集的k+1個不同k項子集一定在頻繁k項集中，證明完畢.

性質(zhì)2若Mk是數(shù)據(jù)庫D中的頻繁k項集[10]，那么Mk中包含的任何一項在全部k-1項集Mk-1里出現(xiàn)的次數(shù)一定大于等于k-1次.

證明假設(shè)Nk={x1，x2，x3，…，xk}，xi∈Lk，頻繁項集Nk∈Lk，xi∈I，i=1，2，…，k，其中，I={I1，I2，…，Im}是數(shù)據(jù)項的集合，則Nk中任何一個含有k-1個項的子集也一定是頻繁項集，且它們都屬于Lk-1.設(shè)Nk-1，i=Nk-{xi}，則推出xi∈Nk-{xj}，j≠i，j=1，2，…，k，即xi一定在其他的k-1項集集合中，因此，頻繁k項集Lk中任意的xi項在Lk-1里面至少出現(xiàn)k-1次，證明完畢.

L1={頻繁1項集}；

for(k=2；Lk-1≠φ；k++)do begin；

//產(chǎn)生全部的頻繁項集

Lk-1=A_prune(Ck-1)；

for每一個項目T1∈t.set-itemsets；

for每一個項目T2∈t.set-itemsets；

for所有候選c∈Ctdo；

if((T1[1]=T2[1])∧(T1[2]=T2[2])∧…∧(T1[k-2]=T2[k-2])∧(T1[k-1]

{c=T1；

addctoCt；

c.count++}；

end；

Answer=UkLk

圖2　改進(jìn)的AprioriTid_M算法示例

3　算法性能比較

為了驗證改進(jìn)后的AprioriTid_M算法的性能，分別采用AprioriTid算法和改進(jìn)的AprioriTid_M算法對相同的數(shù)據(jù)進(jìn)行挖掘，測試出在不同的支持度下兩種算法執(zhí)行所需要的時間，和不同的數(shù)據(jù)規(guī)模下兩種算法運行所需要的時間.操作系統(tǒng)采用Windows XP Professional，利用SQL 2005對實驗數(shù)據(jù)進(jìn)行預(yù)處理.

圖3為設(shè)置不同支持度時，數(shù)據(jù)集量為1 000條時，使用AprioriTid算法和AprioriTid_M算法生成頻繁項集所消耗的時間對比圖.當(dāng)數(shù)據(jù)量相同時，AprioriTid產(chǎn)生頻繁項集的時間隨著支持度的增加變化幅度比較大，性能不夠穩(wěn)定.改進(jìn)的AprioriTid_M算法對于相同的數(shù)據(jù)進(jìn)行運算時，時間變化幅度相對較小，且運算時間明顯少于沒有改進(jìn)時所使用的時間，說明AprioriTid_M算法在計算時間和性能上比AprioriTid算法有很大程度的提高.

圖3　支持度不同時產(chǎn)生頻繁項集所需的時間

圖4為分別選取事務(wù)數(shù)據(jù)量為2 000、3 000、4 000、5 000、6 000和7 000，支持度為0.5時兩種算法運行所消耗的時間對比圖.由圖4可以看出，兩種算法在數(shù)據(jù)量增加時，消耗的時間越來越多.但是在處理等量數(shù)據(jù)時，AprioriTid_M算法運行的時間明顯小于改進(jìn)前的算法消耗時間，且當(dāng)數(shù)據(jù)量增加時，運行時間的增值幅度是趨于平穩(wěn)的，而AprioriTid算法隨事務(wù)總量增加時，消耗時間增長幅度比較大，性能不夠穩(wěn)定.

圖4　支持度為0.5時兩種算法的運行時間

圖5為支持度為0.7時兩種算法的運行時間.由圖5可知，當(dāng)支持度為0.7時，改進(jìn)后的AprioriTid_M算法用時較少，且隨著事務(wù)量的增長，運行時間平穩(wěn)增長，而AprioriTid算法運行時間隨事務(wù)量增加而急劇增長，性能不如改進(jìn)后的算法穩(wěn)定.

圖5　支持度為0.7時兩種算法的運行時間

綜上可知，改進(jìn)后的AprioriTid_M算法在性能上和運行效率上有所提高，穩(wěn)定性比較好.

4　結(jié)　論

本文研究了經(jīng)典Apriori算法的核心思想，分析了該算法性能上的缺點和不足，在此基礎(chǔ)上研究了AprioriTid算法，并提出一種基于事務(wù)集壓縮的AprioriTid_M算法.通過對這兩種算法在等量事務(wù)數(shù)據(jù)、不同支持度下的運行時間比較和某一設(shè)定支持度下不同事務(wù)數(shù)據(jù)量的運行時間比較分析，證明了AprioriTid_M算法在性能和效率上均高于AprioriTid算法.

[1]張春燕，孟志青，袁沛.文本挖掘的時態(tài)文本關(guān)聯(lián)規(guī)則算法研究 [J].計算機科學(xué)，2013，40(6)：219-224.

(ZHANG Chun-yan，MENG Zhi-qing，YUAN Pei.Mining algorithm for temporal text association rules in text mining [J].Computer Science，2013，40(6)：219-224.)

[2]Silverstri C，Orlando S.Approximate mining of frequent patterns on streams [J].Intelligent Data Analysis，2007，11(1)：49-73.

[3]于孝美，陳貞翔，彭立志.基于決策樹的網(wǎng)絡(luò)流量分類方法 [J].濟(jì)南大學(xué)學(xué)報(自然科學(xué)版)，2012，26(3)：291-295.

(YU Xiao-mei，CHEN Zhen-xiang，PENG Li-zhi.Traffic classification based on decision tree [J].Journal of University of Jinan(Science and Technology)，2012，26(3)：291-295.)

[4]Tsang S，Kao B，Kevin Y Y，et al.Decision trees for uncertain data [J].IEEE Transations on Knowledge and Date Engineering，2011，23(1)：64-78.

[5]Kohavi R，Provost F.Applications of data mining to electronic commerce [J].Data Mining and Knowldege Discovery，2011，5(1)：5-10.

[6]焉曉貞，謝紅，王桐.一種基于相關(guān)分析的多元回歸數(shù)據(jù)估計方法 [J].沈陽工業(yè)大學(xué)學(xué)報，2013，35(2)：212-217.

(YAN Xiao-zhen，XIE Hong，WANG Tong.Data evaluation method using multiple regression based on correlation analysis [J].Journal of Shenyang University of Technology，2013，35(2)：212-217.)

[7]翟云，楊炳儒，曲武，等.基于新型集成分類器的非平衡數(shù)據(jù)分類關(guān)鍵問題研究 [J].系統(tǒng)工程與電子技術(shù)，2011，33(1)：196-201.

(ZHAI Yun，YANG Bing-ru，QU Wu，et al.Study on source of classification in imbalanced datasets based on new ensemble classifier [J].Systems Engineering and Electronics，2011，33(1)：196-201.)

[8]向程冠，熊世桓，王東.基于關(guān)聯(lián)規(guī)則的社交網(wǎng)絡(luò)好友推薦算法 [J].中國科技論文，2014，9(1)：87-91.

(XIANG Cheng-guan，XIONG Shi-huan，WANG Dong.Social network friends recommendation algorithm based on association rules [J].China Sciencepaper，2014，9(1)：87-91.)

[9]章志剛，吉根林.一種基于FP-Growth的頻繁項目集并行挖掘算法 [J].計算機工程與應(yīng)用，2014，50(2)：103-106.

(ZHANG Zhi-gang，JI Gen-lin.Parallel algorithm for mining frequent item sets based on FP-Growth [J].Computer Engineering and Applications，2014，50(2)：103-106.)

[10]胡維華，馮偉.基于分解事務(wù)矩陣的關(guān)聯(lián)規(guī)則挖掘算法 [J].計算機應(yīng)用，2014，34(增刊2)：113-116.

(HU Wei-hua，F(xiàn)ENG Wei.Improved Apriori algorithm based on decomposed transaction matrix [J].Journal of Computer Applications，2014，34(Sup2)：113-116.)

(責(zé)任編輯：鐘媛英文審校：尹淑英)

An improved AprioriTid algorithm

ZHANG Wei-ke

(School of Science, Shenyang Ligong University, Shenyang 110159, China)

In order to solve the problem that the I/O load generated in the repeated scanning database for the classic Apriori algorithm will affect the running efficiency, an improved AprioriTid algorithm based on the compression set, namely the AprioriTid_M algorithm, was proposed on the basis of the research on the principle of Apriori algorithm and its related improved algorithms. Through the effective pruning methods, the generation of invalid item sets was reduced, and the number of candidate item sets was decreased. Therefore, the efficiency of the algorithm was improved. The results of simulation experiments show that under such conditions as the same support degree but different data amount or the same data amount but different support degree, the performance and running time of AprioriTid_M algorithm get greatly improved compared with those of Apriori algorithm.

Apriori algorithm; AprioriTid algorithm; AprioriTid_M algorithm; association rule; confidence degree; item set; support degree; performance

2015-12-03.

遼寧省科學(xué)技術(shù)計劃項目(2012217005)； 遼寧省科學(xué)事業(yè)公益研究基金資助項目(2012004002).

張偉科(1965-)，男，河北秦皇島人，講師，碩士，主要從事計算機視覺、智能檢測與控制等方面的研究.

10.7688/j.issn.1000-1646.2016.03.14

TP 311

A

1000-1646(2016)03-0314-05

*本文已于2016-04-22 15∶41在中國知網(wǎng)優(yōu)先數(shù)字出版. 網(wǎng)絡(luò)出版地址： http：∥www.cnki.net/kcms/detail/21.1189.T.20160422.1541.006.html