基于Spark的Apriori算法的改進

牛海玲，魯慧民，劉振杰

(長春工業大學計算機科學與工程學院，吉林 長春 130012)

?

基于Spark的Apriori算法的改進

牛海玲，魯慧民，劉振杰

(長春工業大學計算機科學與工程學院，吉林 長春 130012)

[摘要]基于Spark大數據框架，將傳統Apriori算法進行并行化處理，提出了一種改進的并行化AMRDD算法，使Apriori算法能夠適用于大數據關聯規則的挖掘.該算法利用Spark基于內存計算的抽象對象存儲頻繁項集，通過引入矩陣概念減少掃描事務數據庫的次數，應用局部剪枝和全局剪枝方法縮減生成候選頻繁項集的數量.通過搭建Spark平臺實現該算法，并與傳統Apriori算法和基于Hadoop的Apriori算法進行性能上的比較. 結果表明，該算法能夠較大程度地提高大數據關聯規則挖掘的效率.

[關鍵詞]Apriori；Spark；矩陣；局部剪枝；全局剪枝

0引言

隨著大數據時代的到來，云計算技術的興起，如何從海量數據中高效地提取知識是目前急需解決的問題.同時，人們越來越關注數據挖掘技術在大數據環境下的應用，很多學者在該領域進行了改進研究，如數據分類、聚類方面等[1-2].關聯規則挖掘作為數據挖掘的一個重要組成部分，在數據挖掘中扮演重要角色，作為關聯規則中的經典算法Aprioi的地位更是舉足輕重.然而傳統的串行算法已經不能滿足大數據時代的要求，因此新型的挖掘模式成為人們新的選擇.

近年來，隨著Hadoop和Spark等云計算平臺的開源化，采用云計算并行編程框架，將傳統的數據挖掘算法進行分布式并行化處理，提高大數據挖掘的效率，已成為數據挖掘領域的一個熱點.本文將經典的Apriori關聯規則挖掘算法基于Spark框架進行改進，提出了一種分布式并行化AMRDD算法，使之能夠適用于大數據關聯規則的挖掘.同時，算法采用矩陣向量結構減少掃描數據庫的次數，應用局部剪枝和全局剪枝策略減少候選項集的數目，從而提高大數據環境下Apriori算法關聯規則挖掘的效率.

針對Apriori算法需多次掃描數據庫和可能產生大量頻繁項集的缺點，人們提出了很多改進算法.包括基于概念格的頻繁項集挖掘算法、基于頻繁模式樹的分布關聯規則挖掘算法及在Apriori算法基礎上進行改進的算法.[3-5]

文獻[6]基于Hadoop平臺提出一種MapReduceApriori，該算法針對Apriori的一些缺陷和Hadoop在大集群中表現出的優勢，用HDFS來存儲數據，以MapReduce方式實現并行處理，用于海量數據中發現頻繁項集，處理效率明顯比傳統算法高，且表現出很好的加速比；文獻[7]提出AprioriMMR算法，引入了矩陣的概念，通過矩陣與運算計算項目集的支持度，結合MapReduce計算框架，改進和優化了頻繁項集的產生，在海量數據挖掘中大大提高了效率，不足之處是求解局部頻繁項集的過程無剪枝操作，生成的候選項集數目過大；文獻[8]基于MapReduce框架提出一種有效的關聯規則算法ScadiBino，該算法首先將數據離散化處理轉換為二進制，其次通過N個mappers和一個reducer過程，直接得到關聯規則，而不是尋找頻繁項集，有效地降低了執行時間.本文提出了一種改進的并行化AMRDD算法，使Apriori算法能夠適用于大數據關聯規則的挖掘.

1基于Spark的Apriori算法改進

Spark是一個通用的大規模數據快速處理引擎，主要提供基于內存計算的抽象對象RDD，允許用戶將數據加載至內存后重復地使用.Spark編程模型參考MapReduce，不同的是Spark基于內存的計算特點在某些應用的實驗性能上超過MapReduce 100多倍.Spark平臺完全由Scala語言編寫，Scala是一種融合了面向對象和函數式的編程語言，它專門為分布式而設計，精簡且具有并發的威力.

RDD的基本操作[9]包括轉換(Transformation)和動作(Action).可通過Scala集合或Hadoop數據集構造一個新的RDD，或通過已有的RDD產生新的RDD，例如map，filter，groupBy，reduceBy.Action是通過RDD計算得到一個或者一組值，例如count，collect和save.Spark中的所有轉換都是惰性的，不會直接計算結果，只是記住應用到基礎數據集(例如一個文件)上的這些轉換動作.只有當發生一個要求返回結果給Driver的動作時，這些轉換才會真正運行，這個設計讓Spark更加有效地運行.

1.1基于Spark的Apriori算法基本思想

在Hadoop上實現基于矩陣的Apriori算法思想[7]，引入矩陣概念，只需2次掃描數據集D，結合Spark技術框架，并運用局部剪枝性質和全局剪枝性質改進頻繁項集產生的過程，提高關聯規則挖掘的效率.事務數據集及頻繁項集的存儲基于Hadoop的HDFS文件系統.矩陣的行為事務的集合，矩陣的列為項的集合，向量矩陣存儲變量為0和1，可以減少數據存儲空間，減少掃描次數，根據向量的操作規則，只需在矩陣中使用“與”操作即可快速產生項集的支持度.根據Spark內部運行機制，整個Spark編程框架均是基于對RDD的操作，算法命名為AMRDD.具體算法描述為：

(1) 掃描事務數據庫，求頻繁1項集的集合L1.

(2) 存儲在HDFS上的事務數據庫即為一個RDD，RDD被平分成n個數據塊，并且這些數據塊被分配到m個work節點進行處理.

(3) 構造局部矩陣.設Di為事務數據庫中的某一個數據塊(1≤i≤n)，假定L1的個數為H，Di中事務數目為J，則用L1和Di構造H×(J+2)矩陣Gi，其中第1列為L1中的項，最后一列為L1中對應項的支持度計數，Gi中的其余各列為Di中的事務T，若T中存在對應于L1中的項，則相應位置1，否則置0.矩陣向量的具體轉換如圖1所示.

TIDItemsT0I0,I3,I5T1I3,I4T2I0,I2,I3T3I0,I1,I2,I5T4I1,I4T5I0,I2,I3,I6T6I2,I3,I5T7I1,I2,I4T8I0,I2,I6劃塊→T0I0,I3,I5T1I3,I4T2I0,I2,I3T3I0,I1,I2,I5T4I1,I4T5I0,I2,I3,I6T6I2,I3,I5T7I1,I2,I4T8I0,I2,I6根據L1構建矩陣→I01012I10011I21113?è????÷÷G1I00011I11012I20011?è????÷÷G2I00011I11113I21000?è????÷÷G3

圖1矩陣向量的轉換

(4) 用Gi生成候選項集的局部支持度.含有k個項目的候選項集即為Gi中第1列對應k個項目的集合，因此只需對Gi中對應的k行進行“與”操作即可計算含有k個項目的候選項集的局部支持度.在求k候選項集時，只需對最后一列大于k的行進行“與”操作即可，可以大大減少候選項集的數量.利用局部剪枝性質，刪除局部支持度小于局部支持度閾值的項.

(5) 利用ReduceByKey操作，求得候選項集的全局支持度.如果全局支持度大于支持度閾值的項直接加入頻繁項集集合L；如果全局支持度小于支持度閾值的項利用全局剪枝性質，再次掃描數據庫，最終求得頻繁項集的集合L.

1.2AMRDD算法描述

輸入：數據集D(以數據塊的形式存儲在Hadoop的分布式文件系統中)，最小支持度閾值min_sup；

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

(1)求L1

instans = sc.textfile(D)

L1= instans.map(_，1).reduceByKey(_ + _).filter(_ > min_sup)

(2)構造局部矩陣

Matrix G =?；//初始化H×(J+2)矩陣

foreach(1 inL1)

foreach(tinDi)

if(1 int)

G.add(1) //若L1中的項l在事務t中，則相應位置1

else

G.add(0) //否則，相應位置0

(3)求局部候選項集

for(1

for(0=

count=0

for(m

while(count

if(G[m][maxL-1]

break

else

count += 1

}

local_sup_count = [use“AND” operation on ‘kcolumn items’ of G]；

Ck.add()

}

}

}

(4)計算全局支持度，得到頻繁項集L

對全局支持度小于最小支持度的項應用全局剪枝策略，遍歷事務數據庫進行剪枝

gCk=Ck.reduceByKey(_ + _).filter(_.2 < min_sup)

L= instans.map(_，gCk).reduceBykey(_ + _).filter(_ > min_sup) //全局支持度大于最小支持度的項直接加到頻繁項集集合

L+=Ck.reduceByKey(_ + _).filter(_.2 > min_sup).add(kitems，sup_count)

returnL

2實驗結果

實驗環境為3臺CPU Intel Core4、主頻2.3 GHz、4 G內存，操作系統為CentOS6.5臺式機，其中1臺為master節點，同時也作為worker節點，另外2臺為worker節點，通過交換機組成一個局域網.所用軟件為JDK1.7、Hadoop2.4.0、Scala2.10.4、Spark1.1.0和IntelliJ13.6.實驗數據采用IBM數據庫生成器隨機生成數據.

2.1算法有效性驗證

采用圖1中的事務數據，對AMRDD算法有效性進行驗證，事務數據庫D有9條交易記錄D={T0，T1，T2，T3，T4，T5，T6，T7，T8}，I為項目集合，且I={I0，I1，I2，I3，I4，I5，I6}.假定數據被分成3個數據塊D1={T0，T1，T2}，D2={T3，T4，T5}，D3={T6，T7，T8}，最小支持度閾值為4.傳統Apriori算法和AMRDD算法挖掘這3塊數據文件進行算法有效性驗證.

AMRDD算法生成頻繁1項集L1.以T0為例，產生鍵值對〈I0，1〉，〈I3，1〉，〈I5，1〉.同樣，其他交易記錄也將產生相應鍵值對.合并相同的key，可得到L1：{〈I0，5〉〈I2，6〉〈I3，5〉}.

構造局部矩陣.根據L1，通過掃描數據塊將每條交易記錄轉化為一個列向量v.若一條交易記錄中的項在L1中，則相應位值為“1”，否則為“0”.表1展示了3個數據塊的列向量表示.

表1　數據塊D1，D2和D3的列向量表示

以D1為例計算局部支持度local_sup.由表1可看出，I2的count計數為1<4/3，因此求候選項集進行“與”運算時忽略此行，候選項集為{I0I3}，則{I0I3}的局部支持度local_sup=1×1+1×0+1×1=2；用同樣方法可計算D2，則{I0，I2}局部支持度分別為2，而D3由于count均小于4/3，因此沒有生成候選項集，最后計算全局支持度.將候選項集局部支持度相加，得到{I0，I2}，{I0，I3}的全局支持度都為2，均小于最小支持度閾值，故運用全局剪枝策略再次掃描事務數據集，得到頻繁項集L1：{〈I0，5〉〈I2，6〉〈I3，5〉}，L2：{〈I0I2，4〉}，符合要求的關聯數據是I0和I2.傳統Apriori算法生成的頻繁項集L1：{I0I2I5}，L2：{I0I2，4}，符合要求的關聯數據是I0和I2.從最終結果可以看出，AMRDD算法與傳統Apriori算法挖掘出的頻繁項集和關聯規則結果及數量是一致的，證明了AMRDD算法沒有丟失相關挖掘數據，算法改進后是有效的.

2.2算法支持度實驗

對Apriori算法支持度設定不同也會影響算法的執行效率和產生的規則條數，若設定支持度太高，挖掘出的知識量可能有限，若支持度設定太低，將使算法運算復雜，也會產生一些無用冗余的規則.對傳統Apriori算法和改進的AMRDD算法在設定不同支持度情況下挖掘的關聯規則條數進行實驗，結果如表2所示.

由表2可以看出，當sup=0.07和sup=0.08時產生的規則數一樣多，但是sup=0.08時明顯比sup=0.07時產生的頻繁項集數目少，由此可見選擇合適的支持度既可以產生適當的規則數，也可以縮短算法的運行時間，從而提高了效率.

表2　不同支持度算法輸出結果

2.3算法數據分塊實驗

數據集的大小對算法的運行效率有一定影響，劃分的數據塊過大，每個運算節點的計算量和負載則加大，影響算法效率，若劃分的數據塊小，數據集分塊多，則運算節點間通信壓力變大，也同樣會影響算法的運算效率，所以實驗將數據集分成1，2，3，4，5，6，7，8，9塊數據進行挖掘，實驗效果如圖2所示.由圖2可看出，隨著數據分塊數增多，程序運行時間不斷下降，數據塊為4的時候，運行時間最短，之后隨著數據分塊數增加運行時間也不斷增加.因此，數據分塊是影響算法效率的一個因素.

2.4不同數據量下算法運行時間實驗

實驗分別實現了單機的Apriori算法、Hadoop平臺上的MRApriori算法和Spark平臺上的AMRDD算法.在不同大小的數據集上，不同算法的運行時間比較見圖3.

圖2　不同數據分塊下運行時間比較

圖3　不同算法運行時間比較

由圖3可看出，當數據量小于百萬條時，基于Spark和Hadoop的算法與傳統Apriori算法所用的時間相差不多，隨著數據量增加，時間差逐漸增大.這是因為當數據量逐漸增大時，基于Spark平臺和Hadoop平臺數據處理時間比例上升，通信開銷所占比例逐漸縮小，甚至可以忽略.當數據量繼續增大時，AMRDD算法比MRApriori算法有明顯的優勢，產生這種現象的原因是Spark可以將計算的中間結果cache存到內存中，省去了MapReduce大量的磁盤I/O操作.

3總結

本文在傳統Apriori算法的基礎上提出了AMRDD算法，該算法引入矩陣概念，應用了局部剪枝策略和全局剪枝策略從而大大減少了生成候選項集的數量，并充分利用Spark的并行化優點，迭代計算基于內存，比Hadoop更快.實驗結果表明，傳統Apriori算法不適合處理大數據，基于Spark的算法明顯優于基于Hadoop的算法.將傳統的數據挖掘算法移植到Spark平臺上來處理大數據將會是未來的一個趨勢.

[參考文獻]

[1]李鋒剛，梁鈺. 基于LDA-wSVM模型的文本分類研究[J]. 計算機應用研究，2015，32(1)：21-25.

[2]宋天勇，趙輝，李萬龍，等. 引入自檢策略的進化K-means算法[J]. 東北師大學報(自然科學版)，2014，46(3)：59-63.

[3]柴玉梅，張卓，王黎明. 基于頻繁概念直乘分布的全局閉頻繁項集挖掘算法[J]. 計算機學報，2012，35(5)：990-1001.

[4]馮勇，尹潔娜，徐紅艷. 基于垂直頻繁模式樹帶有負載均衡的分布關聯規則挖掘算法[J]. 計算機應用，2014，34(2)：396-400.

[5]CHANCHAL YADAV，SHULIANG WANG，MANOJ KUMAR. An approach to improve Apriori algorithm based on association rule mining[C]//2013 Fourth International Conference on Computing，Communications and Networking Technologies (ICCCNT)，USA：IEEE，2013:1-9.

[6]楊新月. 云計算環境下關聯規則算法的研究[D]. 成都:電子科技大學，2011.

[7]毛衛俊. 基于云平臺的并行關聯規則挖掘算法研究[D]. 上海:華東理工大學，2014.

[8]MOHAMMADHOSSEIN BARKHORDARI，MAHDI NIAMANESH. ScadiBino an effective MapReduce-based association rule miming method[C]//ICEC’14：Proceedings of the Sixteenth International Conference on Electronic Commerce，Philadelphia：ICEC，2014:1-8.

[9]MATEI ZAHARIA，MOSHARAF CHOWDHURY，TATHAGATA DAS，et al. Resilient distributed datasets：a fault-tolerant abstraction for in-memory cluster computing[C]// Presented as part of the 9thUSENIX Symposium on Networked Systems Design and Implementation，USA：Matei University of California，2012：25-27.

(責任編輯：石紹慶)

The improvement and research of Apriori algorithm based on Spark

NIU Hai-ling，LU Hui-min，LIU Zhen-jie

(School of Computer Science and Engineering，Changchun University of Technology，Changchun 130012，China)

Abstract:The AMRDD algorithm is proposed on the basis of the traditional Apriori algorithm，which is a distributed association rules algorithm based on Spark. To reduce the times of scanning the database，the matrix is introduced，and the number of candidate frequent itemsets is reduced by using local pruning strategy and global pruning strategy. The algorithm is realized on Spark platform，and compare with the traditional Apriori algorithm and the Apriori algorithm based on Hadoop. The experimental results show that AMRDD algorithm performs effectively on big data for mining frequent itemsets.

Keywords:Apriori；Spark；matrix；local pruning strategy；global pruning strategy

[中圖分類號]TP 391[學科代碼]520·20

[文獻標志碼]A

[作者簡介]牛海玲(1985—)，女，碩士研究生； 通訊作者：魯慧民(1972—)，女，博士后，副教授，主要從事智能信息處理、大數據研究.

[基金項目]國家自然科學基金資助項目(61472049)；吉林省自然科學基金資助項目(20130101055JC)；吉林省科技發展計劃項目(20150204005GX)；長春市重大科技攻關計劃項目(14KG082).

[收稿日期]2015-05-08

[文章編號]1000-1832(2016)01-0084-06

[DOI]10.16163/j.cnki.22-1123/n.2016.01.018