王 青， 譚 良,2， 楊顯華

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

?

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

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

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

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

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

0 引言

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

1 相關(guān)工作

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

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

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

2.1 Apriori算法簡介

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

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

輸出：K-項(xiàng)頻繁集LK；

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

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

3) 對K>2的每個(gè)候選集CK，重復(fù)2)，最終得出最大頻繁項(xiàng)集LK.

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

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

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

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

2) 對各個(gè)1-item進(jìn)行計(jì)數(shù)，記錄頻數(shù)最大的iitem并去除產(chǎn)生1項(xiàng)候選集C1.

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

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

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

7) 如果nnum_Li

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

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

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

表1 K-項(xiàng)集與二進(jìn)制對應(yīng)關(guān)系Tab.1 The correspondence between K-item and binary

對于步驟5)～9)，把傳統(tǒng)算法抽象成循環(huán)迭代算法，每次搜索項(xiàng)集候選項(xiàng)集確定，迭代次數(shù)確定并小于K，它不僅減少了運(yùn)行復(fù)雜度，且可以把每次搜索任務(wù)分?jǐn)偟蕉鄠€(gè)處理器上同時(shí)運(yùn)行，便于并行化計(jì)算.

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

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

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

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

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

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

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

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

6) 設(shè)置關(guān)聯(lián)規(guī)則標(biāo)準(zhǔn)的閾值最小支持度mmin_sup.

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

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

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

10) 結(jié)合頻繁項(xiàng)集時(shí)序性規(guī)則挖掘趨勢進(jìn)行filter(-，-)產(chǎn)生有趣頻繁項(xiàng)集.

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

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

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

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

輸出：K-項(xiàng)頻繁集；K-項(xiàng)頻繁集輸出路徑K-outpath.

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

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

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

4)K=1.

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

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

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

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

3 實(shí)驗(yàn)和結(jié)果分析

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

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

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

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

圖2 不同算法的運(yùn)行時(shí)間Fig.2 The running time of different algorithms

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

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

4 小結(jié)

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

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

[2] 毛宇星, 陳彤兵, 施伯樂. 一種高效的多層和概化關(guān)聯(lián)規(guī)則挖掘方法[J]. 軟件學(xué)報(bào),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] 陳玉哲,趙明華,李軍,等.基于移動(dòng)agent和數(shù)據(jù)挖掘標(biāo)準(zhǔn)的分布式數(shù)據(jù)挖掘系統(tǒng)[J].鄭州大學(xué)學(xué)報(bào)(理學(xué)版),2011,43(1):90-94.

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

[6] 劉木林, 朱慶華. 基于Hadoop的關(guān)聯(lián)規(guī)則挖掘算法研究：以Apriori算法為例[J]. 計(jì)算機(jī)技術(shù)與發(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.

(責(zé)任編輯：孔 薇)

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

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

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

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

TP301.6

A

1671-6841(2016)04-0060-05

10.13705/j.issn.1671-6841.2016667