孫兵率

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

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

DOIDOI：10.11907/rjdk.151007

中圖分類號：TP312

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

0引言

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

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

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

1相關概念

1.1頻繁項集

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

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

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

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

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

1.2MapReduce

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

2頻繁項集算法

2.1Apriori算法

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

2.2FPGrowth算法

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

（1）如果事務數據庫D的規(guī)模達到海量級別，FPTree算法將所有事務數據庫中的頻繁項壓縮至內存中的一棵頻繁模式樹，樹的高度或寬度可能達到內存無法接受的規(guī)模。因此，這個過程可能會失敗。

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

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

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

> 分散存儲

> 并行計算

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

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

3.1Job_Counting任務分析

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

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

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

3.2Job_Generating任務分析

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

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

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

3.3Job_Aggregating任務分析

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

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

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

4實驗結果與分析

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

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

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

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

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

5結語

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

參考文獻參考文獻：

[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.

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