一種改進的AprioriTid算法*

張偉科

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

一種改進的AprioriTid算法*

張偉科

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

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

Apriori算法； AprioriTid算法； AprioriTid_M算法； 關聯規則； 置信度； 項集； 支持度； 性能

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

1　Apriori算法核心思想

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

輸入：數據集D，設置最小支持度min_sup的閾值.

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

L1=find_frequent_1-itemset(D)；

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

Ck=apriori_gen(Lk-1)；

//產生候選項集

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)；

//連接：產生候選項集

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) 單遍掃描數據集，得到每個項的支持度以及所有頻繁1項集的集合L1.

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

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

圖1　關聯規則流程圖

雖然Apriori算法能夠實現對數據項的關聯規則挖掘，但是隨著數據庫存儲量的增加和對算法的迭代應用及研究，表明Apriori算法主要有兩方面運行性能瓶頸[6].

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

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

2　改進的Apriori算法

2.1AprioriTid算法

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

AprioriTid算法的過程描述如下：

L1={large 1-itemsets}；

//計算1階大項集

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

Ck=apriori_gen(Lk-1)；

//構造候選項集

//t包含的候選項集

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

end if

//構造k階候選項集的Tid表

end for

//計算k階大項集

end for

L=∪kLk

2.2AprioriTid_M算法

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

性質1如果頻繁k項集可以產生頻繁k+1項集，那么頻繁k項集中的項集個數一定大于k.

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

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

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

L1={頻繁1項集}；

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

//產生全部的頻繁項集

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　改進的AprioriTid_M算法示例

3　算法性能比較

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

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

圖3　支持度不同時產生頻繁項集所需的時間

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

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

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

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

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

4　結　論

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

[1]張春燕，孟志青，袁沛.文本挖掘的時態文本關聯規則算法研究 [J].計算機科學，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]于孝美，陳貞翔，彭立志.基于決策樹的網絡流量分類方法 [J].濟南大學學報(自然科學版)，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]焉曉貞，謝紅，王桐.一種基于相關分析的多元回歸數據估計方法 [J].沈陽工業大學學報，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]翟云，楊炳儒，曲武，等.基于新型集成分類器的非平衡數據分類關鍵問題研究 [J].系統工程與電子技術，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]向程冠，熊世桓，王東.基于關聯規則的社交網絡好友推薦算法 [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].計算機工程與應用，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]胡維華，馮偉.基于分解事務矩陣的關聯規則挖掘算法 [J].計算機應用，2014，34(增刊2)：113-116.

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

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

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.

遼寧省科學技術計劃項目(2012217005)； 遼寧省科學事業公益研究基金資助項目(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在中國知網優先數字出版. 網絡出版地址： http：∥www.cnki.net/kcms/detail/21.1189.T.20160422.1541.006.html