0 引言

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

1 Apriori算法

    Apriori算法使用了一個(gè)簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，執(zhí)行過程是明確的，但當(dāng)事務(wù)的維度大、最小支持很小時(shí)，執(zhí)行效率將下降。Apriori算法問題總結(jié)如下：

    (1)每次生成高維項(xiàng)集時(shí)需要掃描事務(wù)數(shù)據(jù)庫，當(dāng)事務(wù)數(shù)據(jù)庫巨大時(shí)，會(huì)導(dǎo)致I/O的負(fù)擔(dān)重，計(jì)算周期大和算法效率低。

    (2)由頻繁項(xiàng)集產(chǎn)生候選項(xiàng)集的過程中都需要進(jìn)行連接和剪枝操作，時(shí)間復(fù)雜度很高，算法的效率低。

    (3)算法會(huì)產(chǎn)生大量候選項(xiàng)集，直接導(dǎo)致計(jì)算包含大量冗余，使算法效率較低。

2 基于Spark框架的改進(jìn)Apriori算法

2.1 Apriori算法改進(jìn)

    對(duì)于上節(jié)提到的問題(1)，改進(jìn)策略是數(shù)據(jù)以特定的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)從而減少掃描數(shù)據(jù)庫次數(shù)，本文用圖1的存儲(chǔ)結(jié)構(gòu)。

    通過使用此種數(shù)據(jù)結(jié)構(gòu)，可以避免重復(fù)掃描數(shù)據(jù)庫，大大降低了時(shí)間復(fù)雜度。當(dāng)統(tǒng)計(jì)候選集的支持度時(shí)，只需要將支持度作為Key值，然后將相應(yīng)下標(biāo)元素的數(shù)組做“與”操作，最后統(tǒng)計(jì)非零的數(shù)量即為候選集的支持度。

2.2 Spark+IApriori算法

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

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

3 實(shí)驗(yàn)

3.1 環(huán)境搭建

    由于Spark的服務(wù)部署比較繁瑣，需要手工編輯配置非常多的文件以及下載依賴包等，本實(shí)驗(yàn)采用cloudera manager以GUI的方式管理CDH集群，提供向?qū)降陌惭b步驟。

    (1)實(shí)驗(yàn)環(huán)境：

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

    安裝內(nèi)存RAM：16 GB；

    系統(tǒng)類型：64位操作系統(tǒng)；

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

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

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

3.2 實(shí)驗(yàn)結(jié)果

    實(shí)驗(yàn)數(shù)據(jù)選自網(wǎng)站http://fimi.ua.ac.be/data/，F(xiàn)requent Itemset Mining Dataset Repository，主要選取其中的T10I4D100K以及Accidents這兩個(gè)數(shù)據(jù)庫進(jìn)行測(cè)試。

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

    為了消除單一實(shí)驗(yàn)中偶然誤差的影響，本文主要從下面兩個(gè)方面對(duì)Spark+IApriori算法進(jìn)行評(píng)估性能：

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

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

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

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

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

4 結(jié)語

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

參考文獻(xiàn)

[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.

作者信息:

葉  璐，董增壽

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