一種基于MapReduce的頻繁項集挖掘算法

孫兵率

摘要摘要：隨著大數(shù)據(jù)時代的到來，針對Apriori算法和FPGrowth算法在挖掘海量規(guī)模數(shù)據(jù)頻繁項集時，存在內(nèi)存不足、計算效率低等問題，提出一種Aggregating_FP算法。該算法結(jié)合MapReduce并行計算框架與FPGrowth算法，實現(xiàn)頻繁項集的并行挖掘，對每個項進行規(guī)約合并處理，僅輸出包含該項的前K個頻繁項集，提高了海量數(shù)據(jù)決策價值的有效性。在Hadoop分布式計算平臺上對多組規(guī)模不同的數(shù)據(jù)集進行測試。實驗結(jié)果表明，該算法適合大規(guī)模數(shù)據(jù)的分析和處理，具有較好的可擴展性。

關鍵詞關鍵詞：頻繁項集；MapReduce；Hadoop；可擴展性

DOIDOI：10.11907/rjdk.151007

中圖分類號：TP312

文獻標識碼：A文章編號文章編號：16727800（2015）004007503

0引言

隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)庫的容量越來越大，已經(jīng)達到PB，甚至EP水平，傳統(tǒng)的數(shù)據(jù)分析方法和技術不能完全滿足數(shù)據(jù)處理需要。為能快速得到隱藏在海量數(shù)據(jù)背后的具有決策價值的知識，需要結(jié)合當前數(shù)據(jù)技術開拓新的數(shù)據(jù)挖掘方法。

MapReduce[1]是Google提出的利用集群來處理大規(guī)模數(shù)據(jù)集的并行計算框架，Hadoop[2]是Apache基金會開發(fā)的一個分布式系統(tǒng)架構(gòu)，其開源實現(xiàn)了MapReduce。Hadoop通過組織一定規(guī)模集群，構(gòu)建分布式平臺對大規(guī)模數(shù)據(jù)進行計算和存儲，已經(jīng)成為目前主流的云計算技術平臺。國內(nèi)外諸多學者在Hadoop平臺上基于MapReduce對數(shù)據(jù)挖掘算法進行了研究[35]。

頻繁項集挖掘是關聯(lián)規(guī)則分析的關鍵步驟，針對Apriori算法和FPGrowth算法在挖掘海量規(guī)模數(shù)據(jù)頻繁項集時的性能瓶頸，本文提出一種Aggregating_FP算法，該算法運用了MapReduce并行計算框架與FPGrowth算法“分而治之”的思想。

1相關概念

1.1頻繁項集

假設I={i1，i2，…，in}是項（Item）的集合，給定一個事務數(shù)據(jù)庫D={T1，T2，…}，其中每個事務（Transaction）Ti是I的非空集合，即TiI，每一個事務都與一個唯一的標識符TID相對應。項的集合稱為項集（Itemset），事務T是項的集合，并且TI，設A、B分別是I中的一個項集。

定義1：規(guī)則A→B在數(shù)據(jù)庫D中具有支持度S，表示S是D中事務，同時包含AB的百分比，它是概率P（AB），即：

S（A→B）=P（AB）=ABD（1）

其中，|D|表示事務數(shù)據(jù)庫D的個數(shù)，|AB|表示A、B兩個項集同時發(fā)生的事務個數(shù)。

定義2：項的集合稱為項集（Itemset），包含k個項的項集稱為k項集。如果項集滿足最小支持度，則它稱之為頻繁項集（Frequent Itemset）。

1.2MapReduce

MapReduce采用“分而治之”的思想，將一個大的計算任務分解為多個較小的子任務，子任務的計算過程相互獨立，分發(fā)到集群中各節(jié)點分別執(zhí)行，再將各節(jié)點的執(zhí)行結(jié)果進行匯總，得到最終結(jié)果。MapReduce計算過程分為兩個階段：Map（映射）和Reduce（規(guī)約），Map負責執(zhí)行分解后的子任務，得到一系列中間結(jié)果；Reduce負責將這些中間結(jié)果進行匯總規(guī)約。圖1描述了MR的運行機制。

2頻繁項集算法

2.1Apriori算法

Apriori算法是目前頻繁項集挖掘算法中最為經(jīng)典的算法，Apriori算法通過逐層迭代的方式挖掘頻繁項集，面對海量數(shù)據(jù)，存在性能瓶頸：①事務數(shù)據(jù)庫掃描次數(shù)過多，I/O負載過大；②可能產(chǎn)生數(shù)量龐大的候選項集。

2.2FPGrowth算法

FPGrowth算法采用“分而治之”的思想，首先將數(shù)據(jù)庫的事務集壓縮到一棵FPTree，然后對這顆FPTree進行遞歸挖掘，逐步得到頻繁項集。但FPTree的大小受高度和寬度的雙重影響，難免會存在以下缺陷：

（1）如果事務數(shù)據(jù)庫D的規(guī)模達到海量級別，F(xiàn)PTree算法將所有事務數(shù)據(jù)庫中的頻繁項壓縮至內(nèi)存中的一棵頻繁模式樹，樹的高度或?qū)挾瓤赡苓_到內(nèi)存無法接受的規(guī)模。因此，這個過程可能會失敗。

（2）FPGrowth算法挖掘頻繁項集過程中，每一次遞歸計算都會生成一顆新的條件頻繁模式樹，每一次遍歷條件頻繁模式樹的時間消耗占據(jù)了該算法時間復雜度的主要部分，當面對海量規(guī)模的數(shù)據(jù)集，該算法的處理能力在空間維度和時間維度上都將會達到極限。

3改進的頻繁項集并行挖掘算法

FPGrowth算法的設計初衷是采用“分而治之”的策略，這與MapReduce并行計算框架的核心思想是不謀而合的。結(jié)合MapReduce計算框架，對FPGrowth算法的構(gòu)造樹、挖掘樹等過程進行并行化改進，不失為解決海量數(shù)據(jù)性能瓶頸的一種途徑。為提高輸出頻繁項集數(shù)據(jù)的有效性，挖掘出所有的頻繁項集后，不直接輸出，而作進一步改進。改進如下：分別對包含某一項item的所有頻繁項集進行規(guī)約合并，篩選出關聯(lián)度最高的前K個頻繁項集進行組合輸出。整個改進處理過程，稱之為Aggregating_FP算法。該算法從兩個方面實現(xiàn)FP_Growth算法的并行改進：

> 分散存儲

> 并行計算

Aggregating_FP算法需要利用3個MapReduce任務來完成頻繁項集的挖掘，即先后啟動3個Job任務，分別定義為：Job_Counting，Job_Generating和Job_Aggregating。算法流程如圖2所示。其中，Job_Counting的主要任務是并行統(tǒng)計事務數(shù)據(jù)庫中所有項的支持度；Job_Generating的主要任務是根據(jù)事務集的分組情況，構(gòu)建各節(jié)點的本地FP_Tree，挖掘各組包含的頻繁項集；Job_Aggregating的主要任務是歸并各組挖掘結(jié)果，輸出最后的頻繁項集。

3個MapReduce任務在Aggregating_FP算法中分別發(fā)揮不同的作用，而每個Job任務均需要通過設計Map函數(shù)和Reduce函數(shù)來實現(xiàn)，具體設計過程如下：

3.1Job_Counting任務分析

Job_Counting通過設計Map函數(shù)和Reduce函數(shù)，統(tǒng)計整個事務數(shù)據(jù)庫中所有項的支持度。

完成Map函數(shù)的所有輸入后，MapReduce框架會先合并具有相同key'的value'（可能是{1，1，…，1}），成為一個集合S（key'），然后將鍵值對作為輸入傳至Reduce函數(shù)。

Reduce函數(shù)統(tǒng)計計算不同節(jié)點傳遞過來的S（key'），輸出sum（S（key'）），即為項Skey'的支持度計數(shù)。結(jié)果命名為FList。

3.2Job_Generating任務分析

為達到可行的并行計算，各節(jié)點構(gòu)造的本地FPTree規(guī)模不能太大。先將FList中的項劃分為Q組，分別給此Q組項集賦予一個獨立的groupID，組成一個GList。

Map函數(shù)的主要任務是根據(jù)GList分組情況將本地事務數(shù)據(jù)集生成相互獨立的Q個事務組。Map函數(shù)輸入格式，對每一條事務Ti，輸出鍵值對。

Reduce函數(shù)的主要任務是對分配給本節(jié)點的組號為groupID的所有事務集進行頻繁項集挖掘。與傳統(tǒng)算法FPGrowth不同，遞歸過程中不需要遍歷整個表頭，只需遍歷GList中與組號groupID對應的項。為了更好地適應海量數(shù)據(jù)的頻繁項集挖掘，在遞歸創(chuàng)建模式子樹中，發(fā)現(xiàn)符合條件的模式組合后并不直接輸出，僅輸出前K個具有較高關聯(lián)度的頻繁項集。Reduce最終輸出格式定義為：，其中v是頻繁項集，supp（v）為其關聯(lián)度。

3.3Job_Aggregating任務分析

Job_Aggregating的任務是讀取Job_Generating中所有Reduce函數(shù)實例輸出，對于每一個項aj，輸出與其相關的K個關聯(lián)度最高的頻繁項集。

Map函數(shù)輸入格式，對于每一項ai∈v，輸出。

MapReduce框架匯總合并key"相同的鍵值對，傳遞給Reduce函數(shù)，輸入格式形如，其中S（aj）是所有含項aj的頻繁項集集合，Reducer函數(shù)從集合S（aj）中篩選出支持度最高的前K個頻繁項集并輸出。

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

試驗環(huán)境：服務器安裝vSphere虛擬化軟件，創(chuàng)建10個虛擬機，安裝Hadoop1.2.1，搭建Hadoop集群，包括1個NameNode，9個DataNode。其中，服務器參數(shù)配置：64bit X86處理器，32G內(nèi)存，1T硬盤空間。

本試驗數(shù)據(jù)集源自http：//fimi.ua.ac.be/data/，該數(shù)據(jù)集由比利時某超市零售店提供，認為每條記錄表示一個顧客的一次購物行為，一次購物行為表示一個事務，而每個事務對應的項表示顧客一次購買的商品。

本實驗用Hadoop MapReduce實現(xiàn)Aggregating_FP算法，并在不同數(shù)目節(jié)點的集群中對3個不同規(guī)模的數(shù)據(jù)集進行頻繁項集挖掘，實驗過程中，支持度閾值取為200，F(xiàn)List分為100組，令參數(shù)K=50，3個數(shù)據(jù)集T1，T2、T3分別包含的記錄數(shù)據(jù)為88 163條、420 815條和2 104 075條。

當Hadoop集群中節(jié)點數(shù)為1，3，5，7，9時，測試T1，T2，T33個數(shù)據(jù)集在集群中Aggregating_FP算法的并行計算執(zhí)行時間，結(jié)果如圖3所示?？梢钥闯?，當數(shù)據(jù)規(guī)模較大時，隨著集群節(jié)點數(shù)目的增加，集群的并行計算效率有很大提升，說明并行Aggregating_FP算法適于大規(guī)模數(shù)據(jù)的頻繁項集挖掘。

統(tǒng)計數(shù)據(jù)集T1，T2，T3分別在1，3，9個節(jié)點的集群中執(zhí)行時間。結(jié)果顯示，隨著數(shù)據(jù)集規(guī)模的增大，通過增加集群節(jié)點，算法的執(zhí)行時間呈平穩(wěn)的平滑曲線，集群計算能力具有很好的可擴展性。

5結(jié)語

本文探討了Apriori算法和FPGrowth算法在對海量規(guī)模數(shù)據(jù)進行頻繁項集挖掘時的性能瓶頸，提出了一種Aggregating_FP算法，并基于Hadoop平臺對頻繁項集的并行挖掘過程進行了研究和實現(xiàn)。試驗結(jié)果表明，該并行算法具有很好的可擴展性，通過對頻繁項集結(jié)果的進一步處理，提高了海量數(shù)據(jù)決策價值的有效性。

參考文獻參考文獻：

[1]DEAN J， GHEMAWAT S.MapReduce： simplified data processing on large clusters[J].Communications Of The ACM，2008，51（1）：107113.

[2]APACHE HADOOP.Hadoop[EB/OL].http：//hadoop.apache.org.

[3]虞倩倩，戴月明，李晶晶.基于MapReduce的ACOKmeans并行聚類算法[J].計算機工程與應用，2013，49（16）：117120，136.

[4]曾青華，袁家斌，張云洲.基于Hadoop的貝葉斯過濾Mapreduce模型[J].計算機工程.2013，39（11）：5760，64.

[5]ZHUOBO RONG.Complex statistical analysis of big data：implementation and application of apriori and FPGrowth algorithm based on MapReduce[C].Proceedings of 2013 4th IEEE International Conference on Software Engineering and Service Science （ICSESS）， Beijing， IEEE， 2013：968972.

責任編輯（責任編輯：陳福時）