摘  要： 為解決AprioriTid算法對(duì)大數(shù)據(jù)執(zhí)行效率不高的問(wèn)題，根據(jù)Hadoop平臺(tái)的MapReduce模型,，分析了AprioriTid算法的并行化方法,，給出了并行化的主要步驟和Map、Reduce函數(shù)的描述,。與串行的AprioriTid算法相比,，并行算法利用了多個(gè)節(jié)點(diǎn)的計(jì)算能力，縮短了從大數(shù)據(jù)集中挖掘關(guān)聯(lián)規(guī)則的時(shí)間,。對(duì)并行算法的性能進(jìn)行了測(cè)試,，實(shí)驗(yàn)結(jié)果表明，并行AprioriTid算法具有較高的執(zhí)行效率和較好的可擴(kuò)展性,。

　　關(guān)鍵詞： AprioriTid算法,；MapReduce；Hadoop,；關(guān)聯(lián)規(guī)則

0 引言

　　AprioriTid算法[1]是AGRAWAL R等人提出的關(guān)聯(lián)規(guī)則挖掘算法,，該算法在迭代計(jì)算頻繁k-項(xiàng)集的過(guò)程中使用Ck代替事務(wù)數(shù)據(jù)庫(kù)，通過(guò)逐步縮小Ck的規(guī)模來(lái)減少I/O讀取時(shí)間,，進(jìn)而提高算法的執(zhí)行效率[2],。但是,，AprioriTid算法的時(shí)間復(fù)雜度較高,，對(duì)大數(shù)據(jù)而言，該算法在單機(jī)環(huán)境下的執(zhí)行時(shí)間太長(zhǎng),，難以取得較高的執(zhí)行效率,。云計(jì)算是解決這個(gè)問(wèn)題的可行方法，由于云計(jì)算平臺(tái)具有強(qiáng)大的計(jì)算能力,，突破了單機(jī)計(jì)算能力的限制,，為用戶高效處理大數(shù)據(jù)提供了支持。MapReduce[3]是云計(jì)算環(huán)境下被廣泛采用的并行編程模型,。本文根據(jù)Hadoop平臺(tái)[4]的MapReduce模型,，給出了一種AprioriTid算法的并行化實(shí)現(xiàn)方法。并行算法利用計(jì)算機(jī)集群的多個(gè)節(jié)點(diǎn)并行計(jì)算候選項(xiàng)集的支持度,，解決了單機(jī)環(huán)境下AprioriTid算法對(duì)大數(shù)據(jù)執(zhí)行時(shí)間過(guò)長(zhǎng)的問(wèn)題,，提高了挖掘關(guān)聯(lián)規(guī)則的效率。

1 相關(guān)知識(shí)

　　1.1 AprioriTid算法分析

　　AprioriTid算法是在Apriori算法[1]的基礎(chǔ)上改進(jìn)而來(lái)的關(guān)聯(lián)規(guī)則挖掘算法,，參考文獻(xiàn)[1]給出了該算法的描述和實(shí)例分析,。AprioriTid算法計(jì)算頻繁-1項(xiàng)集和生成候選k-項(xiàng)集的方法與Apriori算法是相同的，但是在發(fā)現(xiàn)頻繁k-項(xiàng)集的過(guò)程中采用了Ck代替事務(wù)數(shù)據(jù)庫(kù)D,。對(duì)于所有的候選k-項(xiàng)集Ck,，數(shù)據(jù)庫(kù)D中的一個(gè)事務(wù)t在Ck中對(duì)應(yīng)的記錄表示為：<t.TID,，{c∈Ck|c contained in t}。例如：k=2,，C2={{1 3},，{1 4}，{1 5},，{3 4},，{3 5}，{4 5}},，D的一個(gè)事務(wù)t=<100,，{1 2 3 4}>，則t在中C2對(duì)應(yīng)的記錄表示為<100,，{{1 3},，{1 4}，{3 4}}>,。

　　AprioriTid算法計(jì)算頻繁k-項(xiàng)集（k≥2）的時(shí)間復(fù)雜度為O（|Ck|×|Ck-1|×|t|）,，其中，|t|是Ck-1的記錄包含的候選（k-1）-項(xiàng)集的平均個(gè)數(shù),。在一般情況下,，當(dāng)k的取值較小時(shí)，Ck-1的規(guī)模會(huì)大于事務(wù)數(shù)據(jù)庫(kù)的規(guī)模,，算法的時(shí)間復(fù)雜度較高,。可見(jiàn),，在單機(jī)環(huán)境下應(yīng)用AprioriTid算法對(duì)大數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則難以取得較高的執(zhí)行效率,。在并行條件下，利用多臺(tái)計(jì)算機(jī)的處理能力能很好地解決運(yùn)行效率低下的問(wèn)題[5],。如果將Ck-1分解成p個(gè)子數(shù)據(jù)集,，由p個(gè)節(jié)點(diǎn)對(duì)子數(shù)據(jù)集并行計(jì)算頻繁k-項(xiàng)集，則在單個(gè)節(jié)點(diǎn)上的時(shí)間復(fù)雜度為O（|Ck|×|Ck-1|×|t|/p）,，這就提高了算法的執(zhí)行效率,，這也是本文實(shí)現(xiàn)AprioriTid算法并行化的基本思想。

　　1.2 Hadoop平臺(tái)的MapReduce模型

　　MapReduce模型的基本思想是將處理的問(wèn)題分解為映射和歸約操作,，由用戶實(shí)現(xiàn)的Map和Reduce函數(shù)完成大規(guī)模的并行化計(jì)算[6],。開(kāi)源的云計(jì)算平臺(tái)Hadoop實(shí)現(xiàn)了MapReduce模型，MapReduce任務(wù)在Hadoop平臺(tái)上的執(zhí)行流程如圖1所示,。數(shù)據(jù)文件被切分成多個(gè)數(shù)據(jù)分片存儲(chǔ)在Hadoop分布式文件系統(tǒng)HDFS中,，在input階段，MapReduce支持庫(kù)將數(shù)據(jù)分片的記錄解析為<key,，value>對(duì)輸入Map函數(shù),，Map函數(shù)對(duì)數(shù)據(jù)分片進(jìn)行處理,，產(chǎn)生一組新的<key，value>對(duì)中間結(jié)果,。在shuffle階段,，相同key的value值被合并為values集合，以<key,，values>對(duì)傳遞給Reduce函數(shù),。Reduce函數(shù)對(duì)<key，values>集合作進(jìn)一步處理,，將最終結(jié)果輸出到HDFS中,。

　　在實(shí)際的應(yīng)用中，不同的數(shù)據(jù)文件通常采用不同的記錄格式,，為了將記錄解析成合適的<key,，value>對(duì)，Hadoop平臺(tái)為用戶提供了TextInputFormat,、KeyValueTextInputFormat等類,，使用這些類可以指定輸入Map函數(shù)的key和value。在Hadoop的MapReduce模型中,，執(zhí)行Map函數(shù)的各個(gè)節(jié)點(diǎn)分別處理不同的數(shù)據(jù)分片,，如果所有節(jié)點(diǎn)都能夠讀取相同的文件，就需要借助Hadoop的分布式緩存機(jī)制[7],。在主程序中將待分發(fā)到所有節(jié)點(diǎn)的文件設(shè)置為分布式緩存文件,，各個(gè)節(jié)點(diǎn)便可以同時(shí)讀取這些文件。

2 AprioriTid算法的MapReduce并行化

　　2.1 AprioriTid算法的并行化方法

　　AprioriTid算法的執(zhí)行過(guò)程包括兩個(gè)階段：首先從事務(wù)數(shù)據(jù)庫(kù)中找出所有頻繁1-項(xiàng)集L1,，然后采用迭代方法計(jì)算所有頻繁k-項(xiàng)集Lk,，每次迭代計(jì)算的輸入數(shù)據(jù)是Lk-1和Ck-1,，輸出結(jié)果是Lk和Ck,。按照Hadoop的MapReduce模型，結(jié)合分布式緩存機(jī)制,，這兩個(gè)階段都能實(shí)現(xiàn)并行化,，方法如下：

　　（1）將事務(wù)數(shù)據(jù)庫(kù)切分成多個(gè)數(shù)據(jù)分片,，多個(gè)節(jié)點(diǎn)并行對(duì)數(shù)據(jù)分片統(tǒng)計(jì)各個(gè)項(xiàng)的支持度計(jì)數(shù),，從而實(shí)現(xiàn)了L1的并行計(jì)算。

　?。?）將Lk-1設(shè)置為分布式緩存文件,，Map函數(shù)讀取Lk-1，通過(guò)執(zhí)行Ck=apriori-gen（Lk-1）生成所有候選k-項(xiàng)集Ck,，將Ck存放在節(jié)點(diǎn)的內(nèi)存中,。將Ck-1切分成多個(gè)數(shù)據(jù)分片,，多個(gè)節(jié)點(diǎn)根據(jù)Ck對(duì)Ck-1的分片并行統(tǒng)計(jì)候選k-項(xiàng)集的支持度計(jì)數(shù)生成Ck，從而實(shí)現(xiàn)了Lk和Ck的并行計(jì)算,。

　　2.2 AprioriTid算法并行化的主要步驟

　　為了便于描述,，設(shè)定事務(wù)數(shù)據(jù)庫(kù)D、Ck,、頻繁k-項(xiàng)集Lk在HDFS中的目錄分別為DPath,、CPathk、LPathk,。在并行算法的執(zhí)行過(guò)程中,，需要多個(gè)MapReduce作業(yè)（Job）才能完成，第k個(gè)Job用Jobk表示,，算法并行化的主要步驟描述如下,。

　　（1）在主程序中設(shè)置Job1的輸入路徑為DPath,，輸出路徑為L(zhǎng)Path1,。

　　（2）Map函數(shù)讀取D的數(shù)據(jù)分片,，將事務(wù)t的所有項(xiàng)ij分解出來(lái),，輸出<ij，1>鍵/值對(duì),。Reduce函數(shù)統(tǒng)計(jì)項(xiàng)ij的支持度計(jì)數(shù)count,，將滿足最小支持度閾值minsup的項(xiàng)ij及其支持度計(jì)數(shù)輸出到LPath1目錄的文件中。Map,、Reduce函數(shù)描述如下：

　　map（key=TID,，value=t）{

　　for each項(xiàng)ij of t

　　emit（<ij，1>）,；

　　}

　　reduce（key=ij,，values={1，1,，…}）{

　　count=|values|,；  //|values|是集合中1的個(gè)數(shù)

　　if （count≥minsup）emit （<ij，count>）,；

　　}

　?。?）k=2，C1=D,。

　?。?）在主程序中將Lk-1設(shè)置為分布式緩存文件，設(shè)置Jobk的輸入路徑為CPathk-1,，輸出路徑為L(zhǎng)Pathk,。

　?。?）在Map函數(shù)中定義setup、map和cleanup方法,。setup方法讀取Lk-1,，執(zhí)行Ck=apriori-gen（Lk-1），初始化Ck,。map方法讀取Ck-1的分片,，對(duì)于分片的每一個(gè)記錄t，根據(jù)Ck計(jì)算t包含的候選k-項(xiàng)集集合Ct,，將Ct添加到Ck中,，并將Ct的每一個(gè)候選k-項(xiàng)集c以<c，l>鍵/值對(duì)傳遞給Reduce函數(shù),。cleanup方法將Ck保存到CPathk目錄的一個(gè)文件中,。Reduce函數(shù)統(tǒng)計(jì)候選k-項(xiàng)集的支持度計(jì)數(shù)，將滿足最小支持度閾值的頻繁k-項(xiàng)集及其支持度計(jì)數(shù)輸出到LPathk目錄的文件中,。

　　Map函數(shù)描述如下：

　　setup（）{

　　從LPathk-1目錄讀取Lk-1,；

　　Ck=apriori-gen（Lk-1）；

　　Ck=,；

　　}

　　map（key=TID,，value=t）{

　　Ct=；//初始化Ct

　　Ct={c∈Ck|（c-c[k]）∈t.set-of-itemsets∧（c-c[k-1]）∈t.set-of-itemsets},；

　　if（Ct≠）{

　　Ck+=<TID,，Ct>；

　　for each 候選k-項(xiàng)集c∈Ct

　　emit（<c,，1>）,；

　　}

　　cleanup（）{

　　將Ck作為一個(gè)文件保存到CPathk目錄；

　　}

　　Reduce函數(shù)描述如下：

　　reduce（key=c,，values={1,，1，…}）{

　　count=|values|,；

　　if（count≥minsup）emit（<c,，count>）,；

　　}

　?。?）如果Lk=，則算法結(jié)束,；否則,，k=k+1，轉(zhuǎn)向執(zhí)行步驟（4）,。

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

　　使用6臺(tái)配置相同的計(jì)算機(jī)和一臺(tái)100 M交換機(jī)搭建Hadoop集群,，操作系統(tǒng)是Ubuntu Linux 12.04,，安裝的軟件是Hadoop 1.2.1、JDK 1.7.0_51,。從Frequent Itemset Mining Dataset Repository網(wǎng)站（http：//fimi.ua.ac.be/data/）下載了6個(gè)數(shù)據(jù)集：chess,、mushroom、pumsb_star,、kosarak,、retail和accidents，由于這些數(shù)據(jù)集的事務(wù)沒(méi)有TID,，通過(guò)編寫(xiě)程序給事務(wù)添加了從0開(kāi)始順序編號(hào)的TID,。

　　3.1算法的執(zhí)行時(shí)間測(cè)試

　　使用Java實(shí)現(xiàn)了AprioriTid的串行算法和并行算法，使用4個(gè)數(shù)據(jù)集測(cè)試算法的執(zhí)行時(shí)間,。由于數(shù)據(jù)集的稠密程度不同,，對(duì)這些數(shù)據(jù)集設(shè)置了不同的最小支持度，retail,、kosarak,、pumsb_star、chess的最小支持度閾值分別設(shè)置為0.3%,、0.8%,、45%、75%,。

　　在單機(jī)環(huán)境下,，串行算法對(duì)retail、kosarak,、pumsb_star,、chess的執(zhí)行時(shí)間分別為1 879 s、721 s,、906 s,、3 265 s。在Hadoop平臺(tái)上,，并行AprioriTid算法的執(zhí)行時(shí)間如圖2所示,。當(dāng)節(jié)點(diǎn)數(shù)為2時(shí)，并行算法對(duì)4個(gè)數(shù)據(jù)集的執(zhí)行時(shí)間都小于串行算法的執(zhí)行時(shí)間,，隨著節(jié)點(diǎn)數(shù)的增加,，并行算法的執(zhí)行時(shí)間不斷減少。由此可見(jiàn),，并行AprioriTid算法能取得較高的執(zhí)行效率,。

　　3.2 算法的可擴(kuò)展性測(cè)試

　　使用1個(gè)節(jié)點(diǎn)對(duì)DB規(guī)模的數(shù)據(jù)執(zhí)行算法的時(shí)間表示為t1×DB，使用m個(gè)節(jié)點(diǎn)對(duì)m×DB規(guī)模的數(shù)據(jù)執(zhí)行算法的時(shí)間表示為tm×m×DB，則算法的可擴(kuò)展性[8]定義為：scaleup（DB,，m）=t1×DB/tm×m×DB,。

　　對(duì)數(shù)據(jù)集mushroom和accidents測(cè)試并行AprioriTid算法的可擴(kuò)展性。mushroom,、accidents的最小支持度閾值分別設(shè)置為25%,、70%，當(dāng)使用m個(gè)節(jié)點(diǎn)時(shí),，將數(shù)據(jù)集復(fù)制m份上傳到HDFS,，實(shí)驗(yàn)結(jié)果如圖3所示。從實(shí)驗(yàn)結(jié)果可以看出,，對(duì)于兩個(gè)數(shù)據(jù)集,，并行AprioriTid算法都取得了較好的可擴(kuò)展性。

　　4 結(jié)論

　　AprioriTid算法是一種時(shí)間復(fù)雜度較高的關(guān)聯(lián)規(guī)則挖掘算法,，在單機(jī)環(huán)境下對(duì)大數(shù)據(jù)的執(zhí)行效率不高,。針對(duì)這個(gè)問(wèn)題，本文給出了一種AprioriTid算法的MapReduce并行化方法,，該方法利用多個(gè)節(jié)點(diǎn)對(duì)數(shù)據(jù)分片并行計(jì)算候選項(xiàng)集的支持度,，縮短了發(fā)現(xiàn)頻繁項(xiàng)集的時(shí)間。使用多個(gè)數(shù)據(jù)集測(cè)試了算法的性能,，實(shí)驗(yàn)結(jié)果表明,，并行AprioriTid算法具有較高的執(zhí)行效率，適合云計(jì)算環(huán)境下對(duì)大數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則,。

　　參考文獻(xiàn)

　　[1] AGRAWAL R,， SRIKANT R. Fast algorithms for mining association rules[C]. Proceedings of the 20th International Conference on Very Large Data Bases. Santiago，Chile,， 1994： 487-499.

　　[2] 向程冠,，姜季春，陳梅,，等.AprioriTid算法的改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì),，2009，30（15）：3581-3583.

　　[3] DEAN J,， GHEMAWAT S. MapReduce： simplified data processing on large clusters[J]. Communications of the ACM,， 2008，51（1）：107-113.

　　[4] The apache software foundation. Hadoop[EB/OL]. （2015-07-08） [2015-08-16]. http：//hadoop.apache.org/.

　　[5] 廖寶魁,，孫雋楓.基于MapReduce的增量數(shù)據(jù)挖掘研究[J].微型機(jī)與應(yīng)用,，2014，33（1）：67-70.

　　[6] 亢麗蕓,，王效岳,，白如江.MapReduce原理及其主要實(shí)現(xiàn)平臺(tái)分析[J].現(xiàn)代圖書(shū)情報(bào)技術(shù),，2012（2）：60-67.

　　[7] CHUCK L. Hadoop實(shí)戰(zhàn)[M].韓冀中,，譯.北京：人民郵電出版社,，2011.

　　[8] 楊勇，王偉.一種基于MapReduce的并行FP-growth算法[J].重慶郵電大學(xué)學(xué)報(bào)（自然科學(xué)版）,，2013,，25（5）：651-657.