0 引言

    Apriori算法是關聯規(guī)則(Association rule mining)中最為經典的，隨著互聯網的發(fā)展，已經漸漸不能滿足需求。Google在2004年提出了MapReduce框架，然后基于MapReduce的Hadoop應運而生。LI N等提出了一個并行頻繁項集挖掘算法（PApriori）^[1]，其中Map操作計算候選項集，Reduce操作統計頻繁項集，但其需要反復執(zhí)行Map操作和Reduce操作；Guo Jian等人提出了一種CMR-Apriori^[2]算法，通過編碼和MapReduce對算法進行處理，但是Hadoop需要將中間結果保存到HDFS，也不支持迭代操作。UC Berkeley AMP實驗室提出了一種Spark計算框架，Spark是一個基于內存的并行計算框架，它可以大大提高實時數據處理，確保集群的高容錯性和在大數據環(huán)境下高可伸縮性^[3]。Qiu Hongjian等提出了一種基于Spark RDD框架的頻繁項集挖掘(YAFIM)算法^[4]，實驗表明Spark的性能遠遠高于MapReduce框架，但對于候選項集過多時效果也不是很理想；RATHEE S等人提出了一個通過一代代消除候選項從而改進數據集性能的R-Apriori算法^[5]，相較于YAFIM算法，R-Apriori更加具有優(yōu)越性；Gui Feng在分析了FP-Growth算法的基礎上，提出了DPBM算法^[6]，通過引入全球修剪技術極大減少候選項目集。

1 Apriori算法

    Apriori算法使用了一個簡單的數據結構，執(zhí)行過程是明確的，但當事務的維度大、最小支持很小時，執(zhí)行效率將下降。Apriori算法問題總結如下：

    (1)每次生成高維項集時需要掃描事務數據庫，當事務數據庫巨大時，會導致I/O的負擔重，計算周期大和算法效率低。

    (2)由頻繁項集產生候選項集的過程中都需要進行連接和剪枝操作，時間復雜度很高，算法的效率低。

    (3)算法會產生大量候選項集，直接導致計算包含大量冗余，使算法效率較低。

2 基于Spark框架的改進Apriori算法

2.1 Apriori算法改進

    對于上節(jié)提到的問題(1)，改進策略是數據以特定的數據結構存儲從而減少掃描數據庫次數，本文用圖1的存儲結構。

    通過使用此種數據結構，可以避免重復掃描數據庫，大大降低了時間復雜度。當統計候選集的支持度時，只需要將支持度作為Key值，然后將相應下標元素的數組做“與”操作，最后統計非零的數量即為候選集的支持度。

2.2 Spark+IApriori算法

    Spark本身是一個計算框架，要計算數據時，一般是從外部文件系統讀取數據， Spark本身擅長內存迭代，尤其是基于工作集的內存迭代，會非常高效。如果有分布式大數據倉庫，數據倉庫會有很多人使用，有些人可能使用同樣的作業(yè)，而執(zhí)行同樣操作，在Hadoop中就需要重復的計算，而在Spark中，如果發(fā)現曾經有人完成了同樣的數據、同樣的計算，另外有人要和數據倉庫進行交互時，直接復用工作集的結果即可，可以極大地提高運算速率。Spark相比Hadoop的MapReduce的優(yōu)勢在于，基于MapReduce的計算引擎通常會將中間結果輸出到磁盤中，進行存儲和容錯。Spark將執(zhí)行模型抽象為有向無環(huán)圖執(zhí)行計劃DAG，無須將stage中間結果輸出到HDFS中。同時，Spark在數據格式、內存布局、執(zhí)行策略以及任何調度開銷上都有很好的優(yōu)勢。

    在上節(jié)的基礎上，將改進算法IApriori與基于內存的大數據并行計算處理框架Apache Spark相結合，提出了一種基于Spark并行計算處理框架的Apriori改進算法(Spark+IAprior)，算法流程圖如圖2。算法主要分為兩步：(1)產生本地頻繁項集；(2)產生全局頻繁項集。

3 實驗

3.1 環(huán)境搭建

    由于Spark的服務部署比較繁瑣，需要手工編輯配置非常多的文件以及下載依賴包等，本實驗采用cloudera manager以GUI的方式管理CDH集群，提供向導式的安裝步驟。

    (1)實驗環(huán)境：

    處理器：Intel（R）Pentium（R）CPU 3.20 GHz；

    安裝內存RAM：16 GB；

    系統類型：64位操作系統；

    (2)環(huán)境搭建過程：

    ①本地Yum軟件源安裝Cloudera Manager 5：首先需要關閉關閉防火墻、selinux，修改/etc/selinux/config文件，然后安裝Apache httpd web服務器，下載CM資源包cm5.0.2-centos6.tar.gz，同時發(fā)布CM資源文件，移動解壓后的cm文件夾到Web目錄，并設置權限，安裝postgresql，修改客戶端配置，使其可以找到資源文件，下載CM5安裝文件cloudera-manager-installer.bin，安裝CM5，給cloudera-manager-installer.bin 添加可執(zhí)行權限， 登錄CM管理頁面，使用用戶名和密碼都為admin登錄 http://localhost:7180/界面，如圖3。

    ②CDH5上安裝Hive、HBase、Impala、Spark等服務：下載RPM-GPG-KEY-cloudera(這是對rpm包進行校驗的文件)，所有的服務器上安裝CentOS-6.5-x86_64，并關閉防火墻、selinux、保持時間一致。保持所有的root用戶密碼一致。一個 Hadoop集群中的節(jié)點最少為3臺，本測試環(huán)境的節(jié)點為5臺保存到Web服務器的/var/www/html/redhat/cdh目錄，cm.worker.com上安裝PostgreSQL，圖4～圖6為Hive、HBase、Impala、Spark的安裝和配置圖。

3.2 實驗結果

    實驗數據選自網站http://fimi.ua.ac.be/data/，Frequent Itemset Mining Dataset Repository，主要選取其中的T10I4D100K以及Accidents這兩個數據庫進行測試。

    算法有效性測試：在保證數據集的支持度和節(jié)點數一致的前提下，將Spark+IApriori算法分別與基于MapReduce框架下Apriori算法（MapReduce+Apriori）與基于Spark框架下的Apriori算法（Spark+Apriori）進行對比，同時尋找數據集拷貝數和算法運行時間的關系。本文根據不同數據庫設置了不同的支持度，集群采用了5個節(jié)點，其中一個作為Master節(jié)點，其余4個作為Slave節(jié)點，實驗對比結果如圖7、圖8。從圖7、圖8可以看出，隨著數據拷貝數的增大，也就是隨著數據量不斷增大，MapReduce+Apriori算法的運行時間幾乎直線上升，數據量越大，其處理速度急速下降。這是因為基于MapReduce 計算框架的Hadoop需要將中間結果保存到HDFS，并且MapReduce是分步對數據進行處理的，從圖7、圖8中可以很明顯地看出，Spark框架下的算法運行速度優(yōu)于Hadoop計算框架，這是因為Spark會在內存中接近“實時”的時間完成所有數據分析，Spark的批處理速度比MapReduce快近10倍。同時從圖7、圖8也可以看出，基于Spark框架下，改進Apriori算法的運行效率也高于Apriori算法，證明Spark+IApriori算法是有效的。

    為了消除單一實驗中偶然誤差的影響，本文主要從下面兩個方面對Spark+IApriori算法進行評估性能：

    （1）集群的可伸縮性：在數據集的支持度和數據量一定的前提下，尋找數據集節(jié)點與算法運行時間的關系；為了測試集群的可伸縮性，本文同樣根據不同數據庫設置了不同的支持度，圖9、圖10反映了不同數據集節(jié)點與算法運行時間的關系。對于不同數據集，其算法運行時間以及下降趨勢也是不同的，這是因為對于不同的數據集，數據的橫縱向維度、局部頻繁項集大小以及設置的最小支持度minsup都會有差異。

    （2）集群的加速比：算法在單節(jié)點和多節(jié)點上運行時間的比值：

其中，t₁表示算法在單節(jié)點上的運行時間，t_i表示作業(yè)在n個節(jié)點下的運行時間。

    在本實驗中，為了測試Spark+IApriori算法的加速比，在保持實驗其他參數一致的情況小，通過改變節(jié)點數來測試加速比，實驗結果如圖11、圖12。加速比無法呈線性的主要原因是集群間的通信時間消耗。

    綜上所述，Spark+IApriori算法優(yōu)于基于MapReduce框架下Hadoop平臺的Apriori算法；同時在Spark 平臺下，Spark+IApriori算法在數據伸縮性和加速比方面都優(yōu)于Spark框架下的Apriori算法。

4 結語

    本文在介紹關聯規(guī)則的概念以及分析Apriori算法的基礎上，發(fā)現Apriori算法存在數據量巨大時計算周期大、修剪操作計算復雜度高、產生大量不必要的候選項集等問題，為解決這些問題，對算法在數據結構以及剪枝操作進行了改進，然后結合Spark計算框架，提出了Spark+IApriori算法。實驗驗證了Spark+IApriori算法的有效性以及在集群伸縮性和加速比方面的優(yōu)勢。

參考文獻

[1] LI N，ZENG L，HE Q.Parallel implementation of Apriori algorithm based on MapReduce[C].2012 13th ACM International Conference on Software Engineering, Artificial Intelligence，Networking and Parallel & Distributed Computing，IEEE Computer Society.Kyoto，Japan，2012：236-241. 

[2] Guo  Jian.Research on improved Apriori algorithm based on coding and MapReduce[C].2013 10th Web Information System and Application Conference(WISA 2013)，IEEE Computer Society.Yangzhou，Jiangsu，China，2013：294-299.

[3] Gao Yanjie.Data processing with Spark technology，application and performance optimization[M].China Machine Press，2014.

[4] Qiu Hongjian，Gu Rong，Yuan Chunfeng.YAFIM：A parallel frequent item set mining algorithm with Spark[C].2014 IEEE 28th International Parallel & Distributed Processing Symposium Workshops，IEEE Computer Society.Phoenix，AZ，United states，2014：1664-1671.

[5] RATHEE S，KAUL M，KASHYAP A.R-apriori：An efficient Apriori based algorithm on Spark[C].PIKM 2015-Proceedings of the 8th Ph.D.Workshop in Information and Knowledge Management.Melbourne，VIC，Australia，2015：27-34.

[6] GUI F，MA Y，ZHANG F，et al.A distributed frequent item set mining algorithm based on Spark[C].Proceedings of the 2015 IEEE 19th International Conference on Computer Supported Cooperative Work in Design.Calabria，Italy，2015：271-275.

作者信息:

葉  璐，董增壽

（太原科技大學 電子信息工程學院，山西 太原030024）