基于Spark的Apriori并行算法優(yōu)化實現(xiàn)

王 青， 譚 良,2， 楊顯華

(1.四川師范大學 計算機科學學院 四川 成都 610101； 2.中國科學院 計算技術研究所 北京 100190；3.四川省計算機研究院 四川 成都 610041)

?

基于Spark的Apriori并行算法優(yōu)化實現(xiàn)

王 青1， 譚 良1,2， 楊顯華3

(1.四川師范大學 計算機科學學院 四川 成都 610101； 2.中國科學院 計算技術研究所 北京 100190；3.四川省計算機研究院 四川 成都 610041)

針對傳統(tǒng)Apriori算法處理速度和計算資源的瓶頸，以及Hadoop平臺上Map-Reduce計算框架不能處理節(jié)點失效、不能友好支持迭代計算以及不能基于內存計算等問題，提出了Spark下并行關聯(lián)規(guī)則優(yōu)化算法.該算法只需兩次掃描事務數(shù)據(jù)庫，并充分利用Spark內存計算的RDD存儲項集.與傳統(tǒng)Apriori算法相比，該算法掃描事務數(shù)據(jù)庫的次數(shù)大大降低；與Hadoop下Apriori算法相比，該算法不僅簡化計算，支持迭代，而且通過在內存中緩存中間結果減少I/O花銷.實驗結果表明，該算法可以提高關聯(lián)規(guī)則算法在大數(shù)據(jù)規(guī)模下的挖掘效率.

Spark； 并行化； 數(shù)據(jù)挖掘； 關聯(lián)規(guī)則； Apriori

0 引言

關聯(lián)規(guī)則挖掘是用來描述事物之間的聯(lián)系和挖掘事物之間的相關性，它是在數(shù)據(jù)庫中搜索兩個項目之間存在的顯示或者隱式關系，有助于管理和決策.Apriori算法是最為經典的關聯(lián)規(guī)則挖掘算法，該算法的核心是生成最大項目集，通過迭代方式逐層搜索頻繁項集，直至沒有更大項目集生成，但每次搜索都需要完整地掃描一次數(shù)據(jù)庫，這種傳統(tǒng)串行方式效率非常低.隨著云計算技術的發(fā)展，Hadoop在分布式集群環(huán)境下對離線批處理作業(yè)表現(xiàn)出優(yōu)勢，但由于其處理數(shù)據(jù)必須先存儲后運算，不能同時進行并行化操作，影響數(shù)據(jù)處理的實時性.而Spark擁有Map-Reduce框架所有的優(yōu)點，且所有計算結果都可以保存在內存中，它的快速數(shù)據(jù)處理能力可以有效減輕海量數(shù)據(jù)下發(fā)現(xiàn)挖掘任務的壓力，提高迭代運算的效率.基于Spark下的并行Apriori算法可以解決傳統(tǒng)關聯(lián)規(guī)則算法遇到的難題、單一并行化計算模式的瓶頸以及Hadoop平臺不能很好支持迭代計算的缺陷.因此，本文結合Spark計算平臺，提出了基于Spark的Apriori并行優(yōu)化算法，提高了關聯(lián)規(guī)則算法在大數(shù)據(jù)規(guī)模下的挖掘效率.

1 相關工作

為了提高Apriori算法的性能，文獻[1]在最大項集和閉項集的基礎上，提出了元項集挖掘算法，減少頻繁項集結果的冗余；文獻[2]構建了基于領域知識的項相關性模型，簡約劃分數(shù)據(jù)庫并映射至一種壓縮樹形結構中，縮小事務規(guī)模；文獻[3]利用緩存數(shù)據(jù)庫提高Apriori算法的效率.這些算法在事務集小且事務維度不高的情況下，能發(fā)揮較好的作用.但隨著事務集越來越大、事務維度越來越高，上述算法性能明顯降低.

隨著云計算技術和大數(shù)據(jù)分析處理技術的興起，為了提高挖掘效率，Apriori算法優(yōu)化主要圍繞并行化進行研究[4]，包括MPI并行化以及基于Hadoop平臺的并行化研究.文獻[5-6]把云計算技術的兩個重要步驟Map和Reduce，分別引入到Apriori算法的連接和剪枝步驟中，并對優(yōu)化算法進行Map-Reduce模型并行化，達到了Apriori算法并行化的目的.但Apriori算法需要多次迭代才能發(fā)現(xiàn)頻繁項集，當采用Hadoop并行化的Apriori算法時，需要為每次迭代產生一個新的Map-Reduce去讀取HDFS上的中間結果，產生額外負載.文獻[7]提出了將Apriori 基于Spark 進行并行化實現(xiàn)的YAFIM算法，解決了基于Hadoop并行化存在的編程模式問題，性能明顯提高，但YAFIM算法也存在經典Apriori算法本身的一些問題.文獻[8]提出了Spark 平臺上并行化的R-Apriori算法，但R-Apriori算法僅通過優(yōu)化YAFIM算法的第二次迭代過程提高YAFIM的效率，仍然存在額外的I/O負載.因此，進行基于Spark的Apriori算法并行化優(yōu)化具有研究意義.

2 基于Spark的Apriori算法優(yōu)化(SP-Apriori)

2.1 Apriori算法簡介

Apriori算法的主要思想是通過迭代的方法逐層搜索，用(K-1)項集去搜索大于最小支持度的K項集，直到沒有滿足條件的(K+1)項集生成.對于事物A、B，規(guī)則是否有效是由支持度ssupport(A→B)=P(A∪B)決定.Apriori算法具體步驟如下：

輸入：數(shù)據(jù)集Datasets；最小支持度閾值mmin_support.

輸出：K-項頻繁集LK；

1) 首次掃描Datasets生成候選集C1，通過逐層掃描統(tǒng)計候選集中每個項集X的支持度ssupport，刪除X.ssupport

2) 頻繁集L1再進行自身連接生成候選集C2，再次通過逐層掃描Datasets，刪除X.ssupport

3) 對K>2的每個候選集CK，重復2)，最終得出最大頻繁項集LK.

可以看出，算法效率非常低下，主要存在以下問題：① 資源消耗大.算法每次搜索都需要完整掃描一次數(shù)據(jù)庫，挖掘海量數(shù)據(jù)時，CPU時間和內存消耗問題更加突出；② 規(guī)則挖掘模型較復雜.單一方式搜索候選集，挖掘海量數(shù)據(jù)時，候選集數(shù)量巨大，產生候選集模型無法適應大數(shù)據(jù)環(huán)境.

2.2 基于Spark的Apriori算法優(yōu)化過程

2.2.1 Apriori算法的改進 對Apriori算法進行了如下改進：在挖掘過程中,利用頻數(shù)表示支持度，易于比較并減少頻繁計算支持度概率；利用組合策略得到總的規(guī)則類別，便于獲得各項集kkey；利用此算法的兩個重要性質(① 若X是頻繁項集，則X的所有子集是頻繁項集；② 若X是非頻繁項集，則X的所有超集都是非頻繁項集)去掉多余項集kkey來壓縮搜索空間.改進Apriori算法的步驟描述如下：

1) 掃描事物數(shù)據(jù)庫得到所有1-item項集K個，以及事物總數(shù)nnums.

2) 對各個1-item進行計數(shù)，記錄頻數(shù)最大的iitem并去除產生1項候選集C1.

3) 根據(jù)業(yè)務需求和經驗設置關聯(lián)規(guī)則閾值：mmin_support(最小支持度)，即最小支持頻數(shù)為mmin_sup=nnums*mmin_support.

4) 令i=1，i作為搜索第i項集的迭代控制變量，滿足i

6) 所有候選集Ci頻數(shù)nnum_Li滿足規(guī)則(nnum_Li>mmin_sup)=>1項頻繁項集Li.

7) 如果nnum_Li

8) 去掉頻繁集Li中頻數(shù)最小的i-item，產生有趣第i項頻繁集Fi，令Li=Fi.

9) 對Li進行趨勢(平穩(wěn)、下降、上升、隨機)分析=>Li，更新項集并存儲，i++.

10) 逐次迭代5)～9)直到產生K項候選集CK，如果存在K+1項候選集，則繼續(xù)迭代執(zhí)行，如果不存在，則最終得到有趣K項頻繁集LK，產生關聯(lián)規(guī)則.

表1 K-項集與二進制對應關系Tab.1 The correspondence between K-item and binary

對于步驟5)～9)，把傳統(tǒng)算法抽象成循環(huán)迭代算法，每次搜索項集候選項集確定，迭代次數(shù)確定并小于K，它不僅減少了運行復雜度，且可以把每次搜索任務分攤到多個處理器上同時運行，便于并行化計算.

2.2.2 基于Spark的Apriori算法并行化設計 Spark引入彈性分布式數(shù)據(jù)集RDD數(shù)據(jù)模型，并整合了內存計算基元，支持節(jié)點集群將數(shù)據(jù)集緩存在內存中，縮短了訪問延遲.除了能夠提供交互式查詢外，還可以優(yōu)化迭代工作負載，當需要反復操作的次數(shù)越多、讀取的數(shù)據(jù)量越大時，相對于Hadoop，Spark在性能方面更適用于需要多次操作特定數(shù)據(jù)集的應用場合.Spark是Map-Reduce的擴展，它提供兩類操作：transformation(得到新的RDD)和action(得到結果)多種API，不再需要使用Hadoop唯一DataShuffle模式，編寫程序更具靈活性，使上層應用開發(fā)效率提升數(shù)倍.Spark大數(shù)據(jù)編程模型如圖1所示.

圖1 Spark大數(shù)據(jù)編程模型
Fig.1 Big data programming model of Spark

結合Spark特性，基于“分而治之”的思想，本文算法的并行化設計是把事物數(shù)據(jù)庫均衡分發(fā)給多個子節(jié)點，以局部查找頻繁項集、剪枝代替全局操作，避免全局查找出現(xiàn)內存無法容納的問題，并且可以實時實現(xiàn)數(shù)據(jù)集計數(shù)、過濾支持度低的項集以及排序等，實現(xiàn)對整個挖掘頻繁項集和生成規(guī)則以及評價規(guī)則等各個處理過程的并行化.并行化設計步驟如下：

1) Master利用Spark提供的算子ttextFile()掃描存儲在HDFS上的事務數(shù)據(jù)庫，即為一個RDD.

2) Worker利用CCount(rrdd,nnum)操作求1項集的集合L1和候選1項集C1.

3) RDD被平分成n個數(shù)據(jù)塊，且這些數(shù)據(jù)塊被分配到m個worker節(jié)點進行處理.

4) 根據(jù)worker節(jié)點上1-項Item, 采用優(yōu)化算法步驟7)的方式生成所有局部K-項集Part_LK.

5) 通過函數(shù)f(iiter)=>iiter.ffilter(_>=MMax_ L1)對wworker中的所有數(shù)據(jù)進行過濾.

6) 設置關聯(lián)規(guī)則標準的閾值最小支持度mmin_sup.

7) 根據(jù)Part_LK生成局部支持度頻數(shù)，利用局部剪枝性質，刪除局部支持度頻數(shù)小于局部支持度閾值的項.

8) 利用mmap(wworker，CK)、rreduceByKey(wworker，CK)、ffilter(wworker，CK>mmin_sup)組合操作進行每一輪局部剪枝操作.

9) 針對剪枝觸發(fā)提交job進行fforeachRDD(iiter.步驟8)=>aadd(wworker，CK)=>PPart_ LK局部連接，然后uunion(worker，PPart_ LK)=>CK進行全局連接.

10) 結合頻繁項集時序性規(guī)則挖掘趨勢進行filter(-，-)產生有趣頻繁項集.

11) 全局ffilter(CK>mmin_sup)觸發(fā)SparkContext產生有趣規(guī)則LK.

以上ttextFile，CCount，ffilter，mmap，rreduceByKey算子都是Spark為用戶編程提供的接口API，其中f(iiter)函數(shù)是自定義迭代函數(shù)，去除小于支持度的項集.

2.2.3 基于Spark的Apriori算法的實現(xiàn) 迭代式Apriori算法并行化實現(xiàn)的核心是迭代調用transformation和action操作，每次迭代中利用上一次迭代結果來進行求解，算法并行化實現(xiàn)步驟如下：

輸入：數(shù)據(jù)源路徑iinpath；最小支持度閾值mmin_sup.

輸出：K-項頻繁集；K-項頻繁集輸出路徑K-outpath.

1) 獲取總事務集iitems=AApriori(iinpath)//構造函數(shù)，對數(shù)據(jù)源進行預處理.

2) 獲取總事務數(shù)nnums=ggetNums(iitems)//計算1項集總類別數(shù).

3) 獲取1到K-項集K-items集，去掉mmaxCount(iitems)的1項集合//計算得到最大1項集.

4)K=1.

5)ooutpath=ggetFirstFreq(iinpath,K,nnums,mmin_sup)//從iinpath獲得所有1項集L1，并將產生的L1=>C2輸出到新的K-outpath中.

6) while(1){K-outpath=ggetKFreq(iinpath,ooutpath,nnums,mmin_sup) //通過數(shù)據(jù)源iinpath以及L1獲得2-K項集L2-LK結果集 如果K-outpath為空，則退出 否則：K=K+1； 比對K-items集，去掉小于mmin_sup項集；ooutpath=K-outpath//作為下一次剪枝依據(jù) }.

7) 各計算節(jié)點將頻繁模式CK增加趨勢：CK=CK->ttrend(C1,C2,…,CK) =>LK.

8) 通過uunion(K-outpath,mmin_sup)匯集到mmaster節(jié)點，得出全局關聯(lián)規(guī)則集合. //子節(jié)點得到關聯(lián)規(guī)則結果=>全局關聯(lián)規(guī)則結果.

3 實驗和結果分析

3.1 實驗環(huán)境

采用兩臺PC電腦，其中1臺為mmaster節(jié)點，同時也作為wworker節(jié)點，另外1臺為wworker節(jié)點，共4個節(jié)點，通過交換機組成一個局域網.所用軟件為Intellij+Hadoop+Spark，分別實現(xiàn)了傳統(tǒng)Apriori算法，Hadoop Map-Reduce模式下Apriori改進算法(Mp-Apriori算法)，Spark RDD模式下Apriori算法(S-Apriori算法)，Spark RDD模式下Apriori改進算法(SP-Apriori算法).本實驗數(shù)據(jù)由IBM數(shù)據(jù)生成器生成，由于實驗硬件條件限制，數(shù)據(jù)量大小為1.12 G，事務平均長度為42 MB，共100個iitem項集，包括約100萬條事務數(shù)據(jù)記錄.

3.2 實驗結果

對3.1節(jié)數(shù)據(jù)進行隨機采樣，在支持度 0.75下統(tǒng)計運行時間，采用子節(jié)點運行內存的50%來緩存RDD,在此基礎上開展兩組實驗.實驗一：采用傳統(tǒng)Apriori算法以及保持4個節(jié)點不變的集群環(huán)境下的并行化Mp-Apriori算法、S-Apriori算法和SP-Apriori算法，在挖掘數(shù)據(jù)集大小不同的情況下，計算各個算法的運行時間，結果如圖2所示.實驗二：采用100萬條數(shù)據(jù)集，增加一臺機器，新增兩個wworker節(jié)點，改變集群節(jié)點數(shù)目,測量節(jié)點可擴展性，分別測量節(jié)點數(shù)為 1， 2， 4， 6 時的SP-Apriori算法進行規(guī)則挖掘的執(zhí)行時間,結果如圖3所示.

圖2 不同算法的運行時間Fig.2 The running time of different algorithms

圖3 不同節(jié)點數(shù)的運行時間Fig.3 The running time of different workers

由圖2可知，并行化算法比傳統(tǒng)串行Apriori算法的效率更高，隨著數(shù)據(jù)量的增加，并行化算法時間開銷平穩(wěn)增加，而傳統(tǒng)串行Apriori算法時間開銷成倍增加，說明相對于傳統(tǒng)串行方式，并行化更適合大數(shù)據(jù)環(huán)境；當事務數(shù)據(jù)量不大時，基于Spark和Hadoop的算法運行時間差距不大，但隨著事務數(shù)據(jù)量的增加，基于內存計算的SP-Apriori算法直接從內存中讀取迭代時所需中間結果，大大減少了Hadoop計算時所需I/O讀取時間，Spark的優(yōu)勢越來越明顯，改進的算法效果最好.由圖3可知，隨著數(shù)據(jù)節(jié)點數(shù)增多，算法執(zhí)行時間不斷縮短.數(shù)據(jù)節(jié)點也是影響算法效率的一個重要因素.因此，本文提出的優(yōu)化對算法的性能有一定提高，同時隨著節(jié)點數(shù)的增加、各節(jié)點內存容量變大以及對數(shù)據(jù)源進行預處理，算法的執(zhí)行時間在理論上將大幅度減少.

4 小結

結合Spark計算平臺，實現(xiàn)了一種基于Spark的并行Apriori優(yōu)化算法，提高了處理海量數(shù)據(jù)的效率，適用于生產環(huán)境中對實時性要求較高的應用.由于沒有事先對數(shù)據(jù)集進行預處理，無效數(shù)據(jù)過多，使得內存利用率降低；沒有改變數(shù)據(jù)的存儲結構，在實驗過程中發(fā)現(xiàn)仍然有數(shù)據(jù)集本身數(shù)十倍甚至上百倍大小的中間結果需要保存在內存中.在接下來的研究中，將對算法的預處理和改變事務存儲結構進行深入研究，并對并行過程進行嚴謹證明和理論推導，同時也會探討Spark平臺對實際應用場景的適用性，以期獲得理想效果.

[1] 宋威, 李晉宏, 徐章艷, 等. 一種新的頻繁項集精簡表示方法及其挖掘算法的研究[J]. 計算機研究與發(fā)展, 2010, 47(2): 277-285.

[2] 毛宇星, 陳彤兵, 施伯樂. 一種高效的多層和概化關聯(lián)規(guī)則挖掘方法[J]. 軟件學報,2011,22(12):2965-2980.

[3] ASTHANA P, SINGH D. Improving efficiency of Apriori algorithm using cache database[J]. International journal of computer applications, 2013, 75(13):15-20.

[4] 陳玉哲,趙明華,李軍,等.基于移動agent和數(shù)據(jù)挖掘標準的分布式數(shù)據(jù)挖掘系統(tǒng)[J].鄭州大學學報(理學版),2011,43(1):90-94.

[5] 伊瑤瑤, 茅蘇. Hadoop下的關聯(lián)規(guī)則分析研究[J]. 計算機技術與發(fā)展,2015,25(9):84-88.

[6] 劉木林, 朱慶華. 基于Hadoop的關聯(lián)規(guī)則挖掘算法研究：以Apriori算法為例[J]. 計算機技術與發(fā)展,2016,26(7):1-11.

[7] QIU H, GU R, YUAN C, et al. YAFIM: a parallel frequent itemset mining algorithm with Spark[C]// IEEE International on Parallel & Distributed Processing Symposium Workshops (IPDPSW). Phoenix, 2014: 1664-1671.

[8] YANG S, XU G, WANG Z, et al. The parallel improved Apriori algorithm research based on Spark[C]//9th International Conference on Frontier of Computer Science and Technology. Dalian, 2015:354-359.

(責任編輯：孔 薇)

Optimization of Apriori Parallel Algorithm Based on Spark

WANG Qing1， TAN Liang1,2， YANG Xianhua3

(1.CollegeofComputerScience,SichuanNormalUniversity,Chengdu610101,China; 2.InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing100190,China; 3.SichuanInstituteofComputerSciences,Chengdu610041,China)

In view of the bottleneck of traditional Apriori algorithm in processing speed and computing resources， and that Map-Reduce on Hadoop could not handle node failures, friendly support iterative calculation, and calculate based on memory issues ,a parallel association rule optimization algorithm based on Spark was proposed． The optimization algorithm only needed to scan the transaction database twice and it took advantage of Spark’s RDD storage structure. By comparing with the traditional Apriori and Apriori based on Hadoop, analysis showed that Apriori based on Spark more greatly reduced the number of scan database than that of traditional Apriori, and it used less I/O overhead than Apriori based on Hadoop, because it supported storing temporary results in memory and iterative calculation. Experimental results showed that Apriori based on Spark performed effectively on big data for mining association rules.

Spark; parallel processing; data mining; association rule; Apriori

2016-07-23

國家自然科學基金資助項目(61373162);四川省科技支撐項目(2014GZ007)．

王青(1992—)，女，湖南衡陽人，碩士研究生，主要從事大數(shù)據(jù)處理與分析、數(shù)據(jù)挖掘以及機器學習研究；通訊作者：譚良(1972—)，男，四川成都人，教授，主要從事可信計算、網絡安全以及云計算和大數(shù)據(jù)處理研究，E-mail: tanliang2008cn@126.com．

王青，譚良，楊顯華.基于Spark的Apriori并行算法優(yōu)化實現(xiàn)[J].鄭州大學學報(理學版)，2016,48(4)：60-64.

TP301.6

A

1671-6841(2016)04-0060-05

10.13705/j.issn.1671-6841.2016667