孫兵率

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

關(guān)鍵詞關(guān)鍵詞：頻繁項(xiàng)集；MapReduce；Hadoop；可擴(kuò)展性

DOIDOI：10.11907/rjdk.151007

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2015）004007503

0引言

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

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

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

1相關(guān)概念

1.1頻繁項(xiàng)集

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

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

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

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

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

1.2MapReduce

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

2頻繁項(xiàng)集算法

2.1Apriori算法

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

2.2FPGrowth算法

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

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

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

3改進(jìn)的頻繁項(xiàng)集并行挖掘算法

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

> 分散存儲(chǔ)

> 并行計(jì)算

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

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

3.1Job_Counting任務(wù)分析

Job_Counting通過(guò)設(shè)計(jì)Map函數(shù)和Reduce函數(shù)，統(tǒng)計(jì)整個(gè)事務(wù)數(shù)據(jù)庫(kù)中所有項(xiàng)的支持度。

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

Reduce函數(shù)統(tǒng)計(jì)計(jì)算不同節(jié)點(diǎn)傳遞過(guò)來(lái)的S（key'），輸出sum（S（key'）），即為項(xiàng)Skey'的支持度計(jì)數(shù)。結(jié)果命名為FList。

3.2Job_Generating任務(wù)分析

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

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

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

3.3Job_Aggregating任務(wù)分析

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

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

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

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

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

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

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

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

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

5結(jié)語(yǔ)

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

參考文獻(xiàn)參考文獻(xiàn)：

[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].計(jì)算機(jī)工程與應(yīng)用，2013，49（16）：117120，136.

[4]曾青華，袁家斌，張?jiān)浦?基于Hadoop的貝葉斯過(guò)濾Mapreduce模型[J].計(jì)算機(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.

責(zé)任編輯（責(zé)任編輯：陳福時(shí)）