周國軍，梁燕紅，唐 微（玉林師范學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院，廣西 玉林 537000）

AprioriTid 算法的MapReduce并行化實現(xiàn)*

周國軍，梁燕紅，唐 微
（玉林師范學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院，廣西 玉林 537000）

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

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

0 引言

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

1 相關(guān)知識

1.1 AprioriTid算法分析

AprioriTid算法是在 Apriori算法［1］的基礎(chǔ)上改進而來的關(guān)聯(lián)規(guī)則挖掘算法，參考文獻［1］給出了該算法的描述和實例分析。AprioriTid算法計算頻繁-1項集和生成候選k-項集的方法與 Apriori算法是相同的，但是在發(fā)現(xiàn)頻繁k-項集的過程中采用了Ck代替事務(wù)數(shù)據(jù)庫D。對于所有的候選 k-項集Ck，數(shù)據(jù)庫 D中的一個事務(wù)t在 Ck中對應(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的一個事務(wù)t=＜100，｛1 2 3 4｝＞，則t在中C2對應(yīng)的記錄表示為＜100，｛｛1 3｝，｛1 4｝，｛3 4｝｝＞。

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

1.2 Hadoop平臺的MapReduce模型

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

圖1 MapReduce任務(wù)的執(zhí)行流程

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

2 AprioriTid算法的MapReduce并行化

2.1 AprioriTid算法的并行化方法

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

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

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

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

（1）在主程序中設(shè)置Job1的輸入路徑為DPath，輸出路徑為LPath1。

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

（4）在主程序中將 Lk-1設(shè)置為分布式緩存文件，設(shè)置 Jobk的輸入路徑為 CPathk-1，輸出路徑為 LPathk。

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

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

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

3 實驗與結(jié)果分析

使用6臺配置相同的計算機和一臺100 M交換機搭建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個數(shù)據(jù)集 ：chess、mushroom、pumsb_star、kosarak、retail和accidents，由于這些數(shù)據(jù)集的事務(wù)沒有TID，通過編寫程序給事務(wù)添加了從0開始順序編號的TID。

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

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

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

3.2 算法的可擴展性測試

使用1個節(jié)點對DB規(guī)模的數(shù)據(jù)執(zhí)行算法的時間表示為 t1×DB，使用m個節(jié)點對 m×DB規(guī)模的數(shù)據(jù)執(zhí)行算法的時間表示為 tm×m×DB，則算法的可擴展性［8］定義為：scaleup（DB，m）=t1×DB/tm×m×DB。

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

圖2 并行AprioriTid算法的執(zhí)行時間

圖3 并行AprioriTid算法的可擴展性

4 結(jié)論

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

［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］.計算機工程與設(shè)計，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］.微型機與應(yīng)用，2014，33（1）：67-70.

［6］亢麗蕓，王效岳，白如江.MapReduce原理及其主要實現(xiàn)平臺分析［J］.現(xiàn)代圖書情報技術(shù)，2012（2）：60-67.［7］CHUCK L.Hadoop實戰(zhàn)［M］.韓冀中，譯.北京：人民郵電出版社，2011.

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

Parallel im plementation of AprioriTid algorithm w ith MapReduce

Zhou Guojun，Liang Yanhong，Tang Wei
（School of Mathematics and Information Science，Yulin Normal University，Yulin 537000，China）

To solve the problem which execution efficiency is not high when AprioriTid algorithm is applied for big data，according to MapReduce model of Hadoop platform，a parallelization method of AprioriTid algorithm is analyzed，and main steps of the method and description of Map and Reduce functions are given.Compared with serial AprioriTid algorithm，parallel AprioriTid uses computing power of many nodes to mine association rules，which shortens the execution time.The performance of parallel AprioriTid algorithm is tested，the experimental results show that the parallel algorithm has high execution efficiency and good scalability.

AprioriTid algorithm；MapReduce；Hadoop；association rules

TP311.1

A

1674-7720（2015）24-0022-03

周國軍，梁燕紅，唐微.AprioriTid算法的MapReduce并行化實現(xiàn)［J］.微型機與應(yīng)用，2015，34（24）：22-24，27.

2015-08-22）

周國軍（1975-），男，碩士，講師，主要研究方向：數(shù)據(jù)挖掘、云計算。

梁燕紅（1981-），女，碩士，講師，主要研究方向：數(shù)據(jù)挖掘。

唐微（1980-），女，碩士，講師，主要研究方向：信息管理。

廣西高?？茖W(xué)技術(shù)研究立項項目（LX2014300）