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]算法,，通過(guò)編碼和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)集過(guò)多時(shí)效果也不是很理想；RATHEE S等人提出了一個(gè)通過(guò)一代代消除候選項(xiàng)從而改進(jìn)數(shù)據(jù)集性能的R-Apriori算法^[5],，相較于YAFIM算法,，R-Apriori更加具有優(yōu)越性；Gui Feng在分析了FP-Growth算法的基礎(chǔ)上,，提出了DPBM算法^[6],，通過(guò)引入全球修剪技術(shù)極大減少候選項(xiàng)目集。

1 Apriori算法

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

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

    (2)由頻繁項(xiàng)集產(chǎn)生候選項(xiàng)集的過(guò)程中都需要進(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é)提到的問(wèn)題(1),，改進(jìn)策略是數(shù)據(jù)以特定的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)從而減少掃描數(shù)據(jù)庫(kù)次數(shù),，本文用圖1的存儲(chǔ)結(jié)構(gòu)。

    通過(guò)使用此種數(shù)據(jù)結(jié)構(gòu),，可以避免重復(fù)掃描數(shù)據(jù)庫(kù),，大大降低了時(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ù)倉(cāng)庫(kù),，數(shù)據(jù)倉(cāng)庫(kù)會(huì)有很多人使用，有些人可能使用同樣的作業(yè),，而執(zhí)行同樣操作,，在Hadoop中就需要重復(fù)的計(jì)算，而在Spark中,，如果發(fā)現(xiàn)曾經(jīng)有人完成了同樣的數(shù)據(jù),、同樣的計(jì)算，另外有人要和數(shù)據(jù)倉(cāng)庫(kù)進(jìn)行交互時(shí),，直接復(fù)用工作集的結(jié)果即可,，可以極大地提高運(yùn)算速率。Spark相比Hadoop的MapReduce的優(yōu)勢(shì)在于,，基于MapReduce的計(jì)算引擎通常會(huì)將中間結(jié)果輸出到磁盤中,，進(jìn)行存儲(chǔ)和容錯(cuò)。Spark將執(zhí)行模型抽象為有向無(wú)環(huán)圖執(zhí)行計(jì)劃DAG,，無(wú)須將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)境搭建過(guò)程：

    ①本地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管理頁(yè)面，使用用戶名和密碼都為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ù)庫(kù)進(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ù)庫(kù)設(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ù)庫(kù)設(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ù)一致的情況小,，通過(guò)改變節(jié)點(diǎn)數(shù)來(lái)測(cè)試加速比，實(shí)驗(yàn)結(jié)果如圖11,、圖12,。加速比無(wú)法呈線性的主要原因是集群間的通信時(shí)間消耗。

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

4 結(jié)語(yǔ)

    本文在介紹關(guān)聯(lián)規(guī)則的概念以及分析Apriori算法的基礎(chǔ)上,，發(fā)現(xiàn)Apriori算法存在數(shù)據(jù)量巨大時(shí)計(jì)算周期大、修剪操作計(jì)算復(fù)雜度高,、產(chǎn)生大量不必要的候選項(xiàng)集等問(wèn)題,，為解決這些問(wèn)題，對(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）