基于預判篩選的高效關聯規則挖掘算法

趙學健 孫知信 袁 源

?

基于預判篩選的高效關聯規則挖掘算法

趙學健*①②③孫知信①②袁 源③

①(南京郵電大學物聯網學院 南京 210003),②(南京郵電大學江蘇省通信與網絡技術工程研究中心 南京 210003),③(江蘇省郵電規劃設計院有限責任公司 南京 210006)

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

數據挖掘；關聯規則；事務數據庫；預判篩選；Apriori

1 引言

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

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

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

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

2 AWP算法

2.1 理論基礎

證明 因為

故

則有

證畢

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

2.2 算法描述

AWP算法為實現關聯規則的挖掘，同樣包含兩個步驟：(1)找出所有的頻繁項集；(2)由頻繁項集產生強規則。

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

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

步驟6 重復執行上述步驟2~步驟5，直到不能發現更大的頻繁項目集為止；

AWP算法由頻繁項集產生強規則的過程與Apriori算法類似。若最終AWP算法獲得的頻繁項目集為，則可產生關聯規則,為頻繁項目集集合中任意成員的非空子集，為的補集，即,且，其中為頻繁項目集集合包含的成員數目。比如說若集合是頻繁項目集集合的成員，則可產生如下關聯規則：,,,,，。

3 實驗分析

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

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

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

事務數虛警率(%) =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 補償因子-漏檢率分析表()

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

事務數漏檢率(%) =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

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

圖1 算法運行時間隨事務數變化曲線

圖2 掃描數據庫次數隨事務數變化曲線

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

圖3 算法運行時間隨最小支持度變化曲線

4 結論

[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]. 電子與信息學報, 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] 葛琳, 季新生, 江濤. 基于關聯規則的網絡信息內容安全事件發現及其Map-Reduce實現[J]. 電子與信息學報, 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；網絡出版：2016-04-14

趙學健 zhaoxj@njupt.edu.cn

國家自然科學基金(61373135, 61401225, 61502252, 61201160)，江蘇省基礎研究計劃(自然科學基金)(BK20140883, BK20140894, BK20131377)，中國博士后科學基金(2015M581844)， 江蘇省博士后科研資助計劃項目(1501125B)，南京郵電大學校級科研基金(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)

趙學健： 男，1982年生，副教授，研究方向為數據挖掘、無線傳感器網絡.

孫知信： 男，1964年生，教授，研究方向為大數據、物聯網.

袁 源： 女，1976年生，教授級工程師，研究方向為大數據、電信網絡.