文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.2017.06.032
中文引用格式： 葉璐，董增壽. 基于Spark的改進關聯規則算法研究[J].電子技術應用，2017，43(6)：126-129.
英文引用格式： Ye Lu，Dong Zengshou. An improved algorithm of association rules based on the Spark[J].Application of Electronic Technique，2017，43(6)：126-129.
0 引言
Apriori算法是關聯規則(Association rule mining)中最為經典的，隨著互聯網的發展，已經漸漸不能滿足需求。Google在2004年提出了MapReduce框架，然后基于MapReduce的Hadoop應運而生。LI N等提出了一個并行頻繁項集挖掘算法（PApriori）[1]，其中Map操作計算候選項集，Reduce操作統計頻繁項集，但其需要反復執行Map操作和Reduce操作；Guo Jian等人提出了一種CMR-Apriori[2]算法，通過編碼和MapReduce對算法進行處理，但是Hadoop需要將中間結果保存到HDFS，也不支持迭代操作。UC Berkeley AMP實驗室提出了一種Spark計算框架，Spark是一個基于內存的并行計算框架，它可以大大提高實時數據處理，確保集群的高容錯性和在大數據環境下高可伸縮性[3]。Qiu Hongjian等提出了一種基于Spark RDD框架的頻繁項集挖掘(YAFIM)算法[4]，實驗表明Spark的性能遠遠高于MapReduce框架，但對于候選項集過多時效果也不是很理想；RATHEE S等人提出了一個通過一代代消除候選項從而改進數據集性能的R-Apriori算法[5]，相較于YAFIM算法，R-Apriori更加具有優越性；Gui Feng在分析了FP-Growth算法的基礎上，提出了DPBM算法[6]，通過引入全球修剪技術極大減少候選項目集。
1 Apriori算法
Apriori算法使用了一個簡單的數據結構，執行過程是明確的，但當事務的維度大、最小支持很小時，執行效率將下降。Apriori算法問題總結如下：
(1)每次生成高維項集時需要掃描事務數據庫，當事務數據庫巨大時，會導致I/O的負擔重，計算周期大和算法效率低。
(2)由頻繁項集產生候選項集的過程中都需要進行連接和剪枝操作，時間復雜度很高，算法的效率低。
(3)算法會產生大量候選項集，直接導致計算包含大量冗余，使算法效率較低。
2 基于Spark框架的改進Apriori算法
2.1 Apriori算法改進
對于上節提到的問題(1)，改進策略是數據以特定的數據結構存儲從而減少掃描數據庫次數，本文用圖1的存儲結構。
通過使用此種數據結構，可以避免重復掃描數據庫，大大降低了時間復雜度。當統計候選集的支持度時，只需要將支持度作為Key值，然后將相應下標元素的數組做“與”操作，最后統計非零的數量即為候選集的支持度。
2.2 Spark+IApriori算法
Spark本身是一個計算框架，要計算數據時，一般是從外部文件系統讀取數據， Spark本身擅長內存迭代，尤其是基于工作集的內存迭代，會非常高效。如果有分布式大數據倉庫，數據倉庫會有很多人使用，有些人可能使用同樣的作業，而執行同樣操作，在Hadoop中就需要重復的計算，而在Spark中，如果發現曾經有人完成了同樣的數據、同樣的計算，另外有人要和數據倉庫進行交互時，直接復用工作集的結果即可，可以極大地提高運算速率。Spark相比Hadoop的MapReduce的優勢在于，基于MapReduce的計算引擎通常會將中間結果輸出到磁盤中，進行存儲和容錯。Spark將執行模型抽象為有向無環圖執行計劃DAG，無須將stage中間結果輸出到HDFS中。同時，Spark在數據格式、內存布局、執行策略以及任何調度開銷上都有很好的優勢。
在上節的基礎上，將改進算法IApriori與基于內存的大數據并行計算處理框架Apache Spark相結合，提出了一種基于Spark并行計算處理框架的Apriori改進算法(Spark+IAprior)，算法流程圖如圖2。算法主要分為兩步：(1)產生本地頻繁項集；(2)產生全局頻繁項集。
3 實驗
3.1 環境搭建
由于Spark的服務部署比較繁瑣，需要手工編輯配置非常多的文件以及下載依賴包等，本實驗采用cloudera manager以GUI的方式管理CDH集群，提供向導式的安裝步驟。
(1)實驗環境：
處理器：Intel（R）Pentium（R）CPU 3.20 GHz；
安裝內存RAM：16 GB；
系統類型：64位操作系統；
(2)環境搭建過程：
①本地Yum軟件源安裝Cloudera Manager 5：首先需要關閉關閉防火墻、selinux，修改/etc/selinux/config文件，然后安裝Apache httpd web服務器，下載CM資源包cm5.0.2-centos6.tar.gz，同時發布CM資源文件，移動解壓后的cm文件夾到Web目錄，并設置權限，安裝postgresql，修改客戶端配置，使其可以找到資源文件，下載CM5安裝文件cloudera-manager-installer.bin，安裝CM5，給cloudera-manager-installer.bin 添加可執行權限， 登錄CM管理頁面，使用用戶名和密碼都為admin登錄 http://localhost:7180/界面，如圖3。
②CDH5上安裝Hive、HBase、Impala、Spark等服務：下載RPM-GPG-KEY-cloudera(這是對rpm包進行校驗的文件)，所有的服務器上安裝CentOS-6.5-x86_64，并關閉防火墻、selinux、保持時間一致。保持所有的root用戶密碼一致。一個 Hadoop集群中的節點最少為3臺，本測試環境的節點為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這兩個數據庫進行測試。
算法有效性測試：在保證數據集的支持度和節點數一致的前提下，將Spark+IApriori算法分別與基于MapReduce框架下Apriori算法（MapReduce+Apriori）與基于Spark框架下的Apriori算法（Spark+Apriori）進行對比，同時尋找數據集拷貝數和算法運行時間的關系。本文根據不同數據庫設置了不同的支持度，集群采用了5個節點，其中一個作為Master節點，其余4個作為Slave節點，實驗對比結果如圖7、圖8。從圖7、圖8可以看出，隨著數據拷貝數的增大，也就是隨著數據量不斷增大，MapReduce+Apriori算法的運行時間幾乎直線上升，數據量越大，其處理速度急速下降。這是因為基于MapReduce 計算框架的Hadoop需要將中間結果保存到HDFS，并且MapReduce是分步對數據進行處理的，從圖7、圖8中可以很明顯地看出，Spark框架下的算法運行速度優于Hadoop計算框架，這是因為Spark會在內存中接近“實時”的時間完成所有數據分析，Spark的批處理速度比MapReduce快近10倍。同時從圖7、圖8也可以看出，基于Spark框架下，改進Apriori算法的運行效率也高于Apriori算法，證明Spark+IApriori算法是有效的。
為了消除單一實驗中偶然誤差的影響，本文主要從下面兩個方面對Spark+IApriori算法進行評估性能：
（1）集群的可伸縮性：在數據集的支持度和數據量一定的前提下，尋找數據集節點與算法運行時間的關系；為了測試集群的可伸縮性，本文同樣根據不同數據庫設置了不同的支持度，圖9、圖10反映了不同數據集節點與算法運行時間的關系。對于不同數據集，其算法運行時間以及下降趨勢也是不同的，這是因為對于不同的數據集，數據的橫縱向維度、局部頻繁項集大小以及設置的最小支持度minsup都會有差異。
（2）集群的加速比：算法在單節點和多節點上運行時間的比值：
其中，t1表示算法在單節點上的運行時間，ti表示作業在n個節點下的運行時間。
在本實驗中，為了測試Spark+IApriori算法的加速比，在保持實驗其他參數一致的情況小，通過改變節點數來測試加速比，實驗結果如圖11、圖12。加速比無法呈線性的主要原因是集群間的通信時間消耗。
綜上所述，Spark+IApriori算法優于基于MapReduce框架下Hadoop平臺的Apriori算法；同時在Spark 平臺下，Spark+IApriori算法在數據伸縮性和加速比方面都優于Spark框架下的Apriori算法。
4 結語
本文在介紹關聯規則的概念以及分析Apriori算法的基礎上，發現Apriori算法存在數據量巨大時計算周期大、修剪操作計算復雜度高、產生大量不必要的候選項集等問題，為解決這些問題，對算法在數據結構以及剪枝操作進行了改進，然后結合Spark計算框架，提出了Spark+IApriori算法。實驗驗證了Spark+IApriori算法的有效性以及在集群伸縮性和加速比方面的優勢。
參考文獻
[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）