趙學(xué)健 孫知信 袁 源

?

基于預(yù)判篩選的高效關(guān)聯(lián)規(guī)則挖掘算法

趙學(xué)健*①②③孫知信①②袁 源③

①(南京郵電大學(xué)物聯(lián)網(wǎng)學(xué)院 南京 210003),②(南京郵電大學(xué)江蘇省通信與網(wǎng)絡(luò)技術(shù)工程研究中心 南京 210003),③(江蘇省郵電規(guī)劃設(shè)計院有限責(zé)任公司 南京 210006)

關(guān)聯(lián)規(guī)則分析作為數(shù)據(jù)挖掘的主要手段之一，在發(fā)現(xiàn)海量事務(wù)數(shù)據(jù)中隱含的有價值信息方面具有重要的作用。該文針對Apriori 算法的固有缺陷，提出了AWP (Apriori With Prejudging) 算法。該算法在Apriori 算法連接、剪枝的基礎(chǔ)上，添加了預(yù)判篩選的步驟，使用先驗概率對候選頻繁項集集合進(jìn)行縮減優(yōu)化，并且引入阻尼因子和補(bǔ)償因子對預(yù)判篩選產(chǎn)生的誤差進(jìn)行修正，簡化了挖掘頻繁項集的操作過程。實驗證明AWP算法能夠有效減少掃描數(shù)據(jù)庫的次數(shù)，降低算法的運(yùn)行時間。

數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；事務(wù)數(shù)據(jù)庫；預(yù)判篩選；Apriori

1 引言

在大數(shù)據(jù)技術(shù)發(fā)展如火如荼的今天，人們逐漸意識到數(shù)據(jù)即是財富，尤其是對商業(yè)數(shù)據(jù)的分析更具有巨大的實用價值。關(guān)聯(lián)規(guī)則分析作為數(shù)據(jù)挖掘的主要手段之一，是數(shù)據(jù)挖掘技術(shù)中不可或缺的一個重要組成部分，主要用于發(fā)現(xiàn)大型事務(wù)數(shù)據(jù)庫中隱含的有價值的令人感興趣的聯(lián)系及規(guī)則[1,2]。因此，對關(guān)聯(lián)規(guī)則算法的研究具有非常重要的意義。

早在1993年，IBM的計算機(jī)科學(xué)家Agrawal等人在顧客交易數(shù)據(jù)庫中發(fā)現(xiàn)了顧客在購買商品時的購買規(guī)律，提出了事務(wù)之間的相關(guān)性模式，即最初的關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則通常是一種不復(fù)雜但實用性卻很高的規(guī)則。通過關(guān)聯(lián)規(guī)則分析，我們可以將事務(wù)項集與項集之間的關(guān)系挖掘出來。關(guān)聯(lián)規(guī)則分析最典型的應(yīng)用是購物籃數(shù)據(jù)分析，比如經(jīng)典的{啤酒}→{尿布}規(guī)則。除了可以應(yīng)用于購物籃數(shù)據(jù)之外，關(guān)聯(lián)規(guī)則分析在其它領(lǐng)域的應(yīng)用也十分廣泛，如電子商務(wù)個性化推薦，金融服務(wù)，廣告策劃，生物信息學(xué)及科學(xué)數(shù)據(jù)分析等。比如說在電子商務(wù)個性化推薦中，關(guān)聯(lián)規(guī)則可以幫助電子商務(wù)網(wǎng)站向具有相似消費(fèi)行為的顧客進(jìn)行一些他們可能感興趣的商品推薦，這樣有助于電子商務(wù)網(wǎng)站提升用戶體驗，增加盈利等。

關(guān)聯(lián)規(guī)則分析算法較多，其中最經(jīng)典實用性最好的是Apriori算法及其改進(jìn)算法。Apriori算法是由文獻(xiàn)[6]于1994 年提出的第1個關(guān)聯(lián)規(guī)則算法，應(yīng)用廣泛，該算法通過重復(fù)循環(huán)執(zhí)行連接、剪枝生成頻繁項目集，從而建立關(guān)聯(lián)規(guī)則?；贏priori算法，文獻(xiàn)[7]提出了Apriori-TFP算法，該算法在關(guān)聯(lián)規(guī)則挖掘過程中，將原始數(shù)據(jù)進(jìn)行預(yù)處理并存儲在局部支持樹中，最后生成關(guān)聯(lián)規(guī)則。該算法通過有效的預(yù)處理，降低了關(guān)聯(lián)規(guī)則挖掘的時間，但是需要掃描數(shù)據(jù)庫的次數(shù)仍然較多。文獻(xiàn)[8]提出了GP-Apriori算法，GP-Apriori算法采用圖形處理器(Graphical Processing Unit, GPU)進(jìn)行并行化的支持度計數(shù)，并將垂直交易列存儲為線性有序陣列。GPU通過遍歷該有序陣列，并執(zhí)行按位交叉實現(xiàn)支持度計算，并將結(jié)果復(fù)制回內(nèi)存。與傳統(tǒng)CPU上運(yùn)行的Apriori算法相比，GP-Apriori算法由于采用了先進(jìn)的GPU提高了運(yùn)行速率，但是復(fù)雜性反而有所增長。文獻(xiàn)[9]提出了Apriori的改進(jìn)算法(Apriori Mend Algorithm)。該算法使用哈希函數(shù)生成項目集，用戶必須指定最小支持度以刪除不需要的項集。該算法具有比傳統(tǒng)Apriori算法更好的效率，但是執(zhí)行時間有所增加。文獻(xiàn)[10]基于MapReduce框架實現(xiàn)了Apriori算法的并行化。該算法在處理海量數(shù)據(jù)集時具有良好的可擴(kuò)展性和效率，但是該算法需要強(qiáng)大的計算和存儲能力支撐，通常運(yùn)行在集群環(huán)境中。文獻(xiàn)[11]嘗試將Apriori算法應(yīng)用于多維數(shù)據(jù)分析，探討了在多維數(shù)據(jù)中建立關(guān)聯(lián)規(guī)則更加具體有效的方法。文獻(xiàn)[12]對Apriori算法進(jìn)行了改進(jìn)，引入了事務(wù)尺寸和事務(wù)規(guī)模的概念以消除非重要項目的影響。文獻(xiàn)[13]提出了一種基于矩陣的Apriori算法，該算法通過矩陣有效地表示數(shù)據(jù)庫的各種操作，并用基于矩陣的AND操作得到最大的頻繁項目集。算法雖然大大減少了掃描數(shù)據(jù)庫的次數(shù)，但是空間復(fù)雜度較高。文獻(xiàn)[14]對Apriori算法進(jìn)行了改進(jìn)，提出了M-Apriori算法，該算法在尋找頻繁項目集的過程中，對包含項集的事務(wù)集合進(jìn)行記錄，在驗證項集是否頻繁時，不再掃描整個數(shù)據(jù)庫，而是僅需掃描數(shù)據(jù)庫中部分事務(wù)，從而提高時間效率。文獻(xiàn)[15]提出了一種Map-Reduce框架下的分布式冪集Apriori算法。實驗結(jié)果表明，該算法并行運(yùn)算能力強(qiáng)，在低虛警率和漏檢率的情況下，具有較好的檢測率。文獻(xiàn)[16]提出一種基于Apriori的改進(jìn)算法，通過減少候選2項集的剪枝操作從而提高效率，但實驗結(jié)果表明算法性能提升非常有限。

上述基于Apriori的改進(jìn)算法大多繼承了Apriori算法需要大量掃描數(shù)據(jù)庫和占用大量內(nèi)存的缺點[17]。本文針對經(jīng)典 Apriori 算法的固有缺陷，提出了AWP(Apriori With Prejudging) 算法，該算法在Apriori算法連接、剪枝的基礎(chǔ)上，添加了預(yù)判篩選的步驟，通過使用先驗概率對候選頻繁項集集合進(jìn)行縮減優(yōu)化，并且引入阻尼因子和補(bǔ)償因子對預(yù)判篩選產(chǎn)生的誤差進(jìn)行修正，以減少掃描數(shù)據(jù)庫的次數(shù)，降低算法的運(yùn)算時間，提高算法的運(yùn)算效率。

2 AWP算法

2.1 理論基礎(chǔ)

證明 因為

故

則有

證畢

AWP算法嘗試在連接、剪枝步驟后，通過計算先驗概率的方法對候選頻繁項集集合中的項目集進(jìn)行縮減優(yōu)化，而不是直接通過掃描數(shù)據(jù)庫進(jìn)行判斷，從而減少掃描數(shù)據(jù)庫的次數(shù)，降低算法運(yùn)行時間，提高算法運(yùn)算效率。由定理1可知，若直接采用獨(dú)立事件概率公式對的概率進(jìn)行計算，在預(yù)判篩選過程中難免出現(xiàn)虛警(把非頻繁項目集視為頻繁項目集)和漏檢(把頻繁項目集視為非頻繁項目集)的情況。因此，AWP算法引入阻尼因子和補(bǔ)償因子對預(yù)判篩選產(chǎn)生的虛警率和漏檢率進(jìn)行控制。若阻尼因子和補(bǔ)償因子嚴(yán)格根據(jù)定理1進(jìn)行設(shè)置，可保證虛警率和漏檢率均為0，但是算法性能會受到嚴(yán)重影響。為追求更佳的算法性能，并且保證一定的虛警率和漏檢率的前提下，算法將采用實驗驗證的方法對阻尼因子和補(bǔ)償因子進(jìn)行了設(shè)置。

2.2 算法描述

AWP算法為實現(xiàn)關(guān)聯(lián)規(guī)則的挖掘，同樣包含兩個步驟：(1)找出所有的頻繁項集；(2)由頻繁項集產(chǎn)生強(qiáng)規(guī)則。

為了解決Apriori算法存在的技術(shù)問題，精簡候選項目集中的元素，簡化算法挖掘頻繁項集以及規(guī)則的操作過程，減少掃描數(shù)據(jù)庫的次數(shù)，AWP算法根據(jù)定理1在Apriori算法連接、剪枝步驟后添加了預(yù)判篩選環(huán)節(jié)，算法找出所有頻繁項集的過程如下：

步驟3 利用Apriori性質(zhì)[5](任一頻繁項集的所有非空子集也必須是頻繁的，如果某個候選的非空子集不是頻繁的，那么該候選肯定不是頻繁的)對候選項集集合進(jìn)行剪枝。剪枝過程如下：對候選項集集合的成員,的所有非空子集的支持度進(jìn)行判斷，若該成員存在支持度小于預(yù)設(shè)的最小支持度的非空子集，根據(jù)Apriori性質(zhì)可判定該成員不是頻繁項目集，將其從中刪除；反之，將該成員保留在候選項集集合中；

步驟6 重復(fù)執(zhí)行上述步驟2~步驟5，直到不能發(fā)現(xiàn)更大的頻繁項目集為止；

AWP算法由頻繁項集產(chǎn)生強(qiáng)規(guī)則的過程與Apriori算法類似。若最終AWP算法獲得的頻繁項目集為，則可產(chǎn)生關(guān)聯(lián)規(guī)則,為頻繁項目集集合中任意成員的非空子集，為的補(bǔ)集，即,且，其中為頻繁項目集集合包含的成員數(shù)目。比如說若集合是頻繁項目集集合的成員，則可產(chǎn)生如下關(guān)聯(lián)規(guī)則：,,,,，。

3 實驗分析

本文采用8組事務(wù)數(shù)據(jù)庫對AWP算法的性能進(jìn)行了分析，8組數(shù)據(jù)庫分別包含5×102, 1×103，2×103, 5×103, 8×103, 1×104, 2×104, 4×104個事務(wù)。由于AWP算法增加了預(yù)判篩選的步驟，該步驟通過獨(dú)立事件概率公式計算候選項集集合中成員,的先驗概率，以減少掃描數(shù)據(jù)庫的次數(shù)，這容易導(dǎo)致虛警和漏檢的情況發(fā)生。為此，AWP算法在預(yù)判篩選步驟中引入了阻尼因子和補(bǔ)償因子兩個參數(shù)，通過合理設(shè)置阻尼因子和補(bǔ)償因子可有效降低虛警率和漏檢率。根據(jù)虛警率和漏檢率的概念可知，所謂虛警是指本不是頻繁項目集卻納入到頻繁項目集的范疇；所謂漏檢是指本應(yīng)是頻繁項目集卻沒有納入到頻繁項目集的范疇。在現(xiàn)實情況中，為了盡可能地挖掘出所有的強(qiáng)關(guān)聯(lián)規(guī)則，對算法的漏檢率要求應(yīng)該更加嚴(yán)格。因此，本文中要求算法的虛警率低于5%，而漏檢率低于2%。在分析AWP算法性能之前，首先通過實驗對阻尼因子和補(bǔ)償因子的取值進(jìn)行分析。

表1 阻尼因子-虛警率分析表()

表1 阻尼因子-虛警率分析表()

事務(wù)數(shù)虛警率(%) =0.5=0.4=0.3=0.2=0.1 5×1023.934.575.216.858.76 5×1033.594.245.016.268.13 1×1043.223.884.315.446.59 2×1042.743.313.674.915.63 4×1041.562.653.113.754.76

表2 補(bǔ)償因子-漏檢率分析表()

表2 補(bǔ)償因子-漏檢率分析表()

事務(wù)數(shù)漏檢率(%) =0.25=0.20=0.15=0.10=0.05 5×1020.861.342.894.528.51 5×1030.731.151.922.875.38 1×1040.550.820.971.944.63 2×1040.390.660.841.373.25 4×1040.170.490.670.981.46

在確定了算法的阻尼因子和補(bǔ)償因子分別如式(4)和式(5)所示后，第2組實驗對算法的運(yùn)行時間隨事務(wù)數(shù)的變化情況進(jìn)行了分析。在最小支持度設(shè)置為0.04時，算法運(yùn)行時間隨事務(wù)數(shù)變化曲線如圖1所示。由于數(shù)據(jù)庫包含的事務(wù)數(shù)變化較大，因此圖1橫坐標(biāo)采用了對數(shù)坐標(biāo)軸，縱坐標(biāo)依然為普通坐標(biāo)軸。由圖1可以看出，隨著數(shù)據(jù)庫中事務(wù)數(shù)的增多，Apriori算法、M-Apriori算法和AWP算法的運(yùn)行時間均逐漸增大。但是，AWP算法相對于Apriori算法和M-Apriori算法來說，運(yùn)行時間得到了大幅縮短。當(dāng)事務(wù)數(shù)據(jù)庫包含4×104條記錄時，AWP算法的運(yùn)行時間為34.48 s，比Apriori算法和M-Apriori分別降低48.9%和17.1%。

圖1 算法運(yùn)行時間隨事務(wù)數(shù)變化曲線

圖2 掃描數(shù)據(jù)庫次數(shù)隨事務(wù)數(shù)變化曲線

最后一組實驗，針對事務(wù)數(shù)為104的數(shù)據(jù)庫，分析了算法運(yùn)行時間隨最小支持度的變化情況，如圖3所示。由圖可以看出，3種算法的運(yùn)行時間均隨最小支持度的增大而減小。這是因為當(dāng)最小支持度增大時，候選項目集集合中的成員逐漸減少，因此掃描數(shù)據(jù)庫進(jìn)行比較的次數(shù)減少，運(yùn)行時間自然降低。在最小支持度相同的情況下，AWP算法比Apriori算法和M-Apriori算法降低了運(yùn)行時間，并且當(dāng)最小支持度越小的時候，效果愈發(fā)明顯。

圖3 算法運(yùn)行時間隨最小支持度變化曲線

4 結(jié)論

[1] SINGLA S and MALIK A. Survey on various improved Apriori algorithms[J]., 2014, 3(11): 8528-8531. doi: 10.17148/ijarcce.2014.31139.

[2] MINAL G I and SURYAVANSHI N Y. Association rule mining using improved Apriori algorithm[J]., 2015, 112(4): 37-42.

[3] RAJESWARI K. Improved Apriori algorithmA comparative study using different objective measures[J].2015, 6(3): 3185-3191.

[4] ACHAR A, LAXMAN S, and SASTRY P S. A unified view of the Apriori-based algorithms for frequent episode discovery[J].&2012, 31(2): 223-250. doi: 10.1007/s10115-011-0408-2.

[5] 李鵬, 于曉洋, 孫渤禹. 基于用戶群組行為分析的視頻推薦方法研究[J]. 電子與信息學(xué)報, 2014, 36(6): 1484-1491. doi: 10.3724/SP.J.1146.2013.01225.

LI Peng, YU Xiaoyang, and SUN Boyu. Video recommendation method based on group user behavior analysis[J].&, 2014, 36(6): 1484-1491. doi: 10.3724/SP.J.1146.2013.01225.

[6] AGRAWAL R and SRIKANT R. Fast algorithms for mining association rules[C]. VLDB’94 Proceedings of the 20th International Conference on Very Large Data Bases, San Francisco, CA, USA, 1994: 487- 499.

[7] YANG Z, TANG W, SHINTEMIROV A,Association rule mining-based dissolved gas analysis for fault diagnosis of power transformers[J].,,:, 2009, 39(6): 597-610. doi: 10.1109/TSMCC.2009.2021989.

[8] ZHANG F, ZHANG Y, and BAKOS J D. Gpapriori: Gpu-accelerated frequent itemset mining[C]. 2011 IEEE International Conference on Cluster Computing, Austin, TX, USA, 2011: 590-594. doi: 10.1109/CLUSTER.2011.61.

[9] ANGELINE M D and JAMES S P. Association rule generation using Apriori mend algorithm for student’s placement[J].2012, 2(1): 78-86.

[10] LI N, ZENG L, HE Q,Parallel implementation of Apriori algorithm based on MapReduce[C]. 13th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel Distributed Computing (SNPD), Kyoto, Japan, 2012: 236-241. doi: 10.1109/ SNPD. 2012.31.

[11] SULIANTA F, LIONG TH, and ATASTINA I. Mining food industry’s multidimensional data to produce association rules using Apriori algorithm as a basis of business strategy[C]. 2013 International Conference of Information and Communication Technology (ICoICT), Bandung, Indonisia, 2013: 176-181. doi: 10.1109/ICoICT.2013.6574569.

[12] ABAYA S A. Association rule mining based on Apriori algorithm in minimizing candidate generation[J].&, 2012, 3(7): 1-4.

[13] WANG Feng and LI Yonghua. An improved Apriori algorithm based on the matrix[C]. Proceedings of 2008 International Seminar on Future BioMedical Information Engineering, Wuhan, China, 2008: 152-155. doi: 10.1109/ FBIE.2008.80.

[14] MAOLEGI M A and ARKOK B. An improved Apriori algorithm for association rules[J]., 2014, 3(1): 21-29. doi: 10.5121/ijnlc.2014.3103.

[15] 葛琳, 季新生, 江濤. 基于關(guān)聯(lián)規(guī)則的網(wǎng)絡(luò)信息內(nèi)容安全事件發(fā)現(xiàn)及其Map-Reduce實現(xiàn)[J]. 電子與信息學(xué)報, 2014, 36(8): 1831-1837. doi: 10.3724/SP.J.1146.2013.01272.

GE Lin, JI Xinsheng, and JIANG Tao. Discovery of network information content security incidents based on association rules and its implementation in Map-Reduce[J].&, 2014, 36(8): 1831-1837. doi: 10.3724/SP.J.1146.2013.01272.

[16] TANK D M. Improved Apriori algorithm for mining association rules[J]., 2014, 6(7): 15-23. doi: 10.5815/ijitcs.2014.07.03.

[17] RAO S and GUPTA R. Implementing improved algorithm over Apriori data mining association rule algorithm[J]., 2012, 34(3): 489-493.

An Efficient Association Rule Mining Algorithm Based on Prejudging and Screening

ZHAO Xuejian①②③SUN Zhixin①②YUAN Yuan③

①(,,210003,),②(,,210003,),③(&.,210006,)

Association rule analysis, as one of the significant means of data mining, plays an important role in discovering the implicit knowledge in massive transaction data. To overcome the inherent defects of the classic Apriori algorithm, this paper proposes Apriori With Prejudging (AWP) algorithm. AWP algorithm adds a pre-judging procedure on the basis of the self-join and pruning progress in Apriori algorithm. It reduces and optimizes the-frequent item sets using prior probability. In addition, the damping factor and compensating factor are introduced to revise the deviation caused by pre-judging. AWP algorithm simplifies the operation process of mining frequent item sets. Experimental results show that the improvement measures can effectively reduce the number of scanning databases and reduce the running time of the algorithm.

Data mining; Association rules; Transaction database; Prejudging; Apriori

TP391

A

1009-5896(2016)07-1654-06

10.11999/JEIT151107

2015-09-29；改回日期：2016-02-26；網(wǎng)絡(luò)出版：2016-04-14

趙學(xué)健 zhaoxj@njupt.edu.cn

國家自然科學(xué)基金(61373135, 61401225, 61502252, 61201160)，江蘇省基礎(chǔ)研究計劃(自然科學(xué)基金)(BK20140883, BK20140894, BK20131377)，中國博士后科學(xué)基金(2015M581844)， 江蘇省博士后科研資助計劃項目(1501125B)，南京郵電大學(xué)校級科研基金(NY214101, NY215147)

The National Natural Science Foundation of China (61373135, 61401225, 61502252, 61201160), Natural Science Foundation of Jiangsu Province of China (BK20140883, BK20140894, BK20131377), China Postdoctoral Science Foundation Funded Project (2015M581844), Jiangsu Planned Projects for Postdoctoral Research Funds (1501125B), NUPTSF (NY214101, NY215147)

趙學(xué)?。?男，1982年生，副教授，研究方向為數(shù)據(jù)挖掘、無線傳感器網(wǎng)絡(luò).

孫知信： 男，1964年生，教授，研究方向為大數(shù)據(jù)、物聯(lián)網(wǎng).

袁 源： 女，1976年生，教授級工程師，研究方向為大數(shù)據(jù)、電信網(wǎng)絡(luò).