Fp—Growth算法在MapReduce框架下的實(shí)現(xiàn)

舒遠(yuǎn)仲+戴海輝+吳小玲

摘 要：Fp-Growth算法是頻繁模式挖掘的經(jīng)典算法，已在許多領(lǐng)域得到了良好應(yīng)用。傳統(tǒng)Fp-Growth算法是基于內(nèi)存的，而計(jì)算機(jī)內(nèi)存卻無法裝載入大數(shù)據(jù)，故傳統(tǒng)Fp-Growth算法并不能有效地處理大數(shù)據(jù)。提出一種新的基于MapReduce并行計(jì)算框架的Fp-Growth實(shí)現(xiàn)，使Fp-Growth算法在多臺(tái)計(jì)算機(jī)上并行計(jì)算，從而實(shí)現(xiàn)大數(shù)據(jù)的有效處理。實(shí)驗(yàn)結(jié)果表明，該算法具有很好的擴(kuò)展性，頻繁模式挖掘效率隨著用于計(jì)算的主機(jī)的增加而平穩(wěn)提升。

關(guān)鍵詞：大數(shù)據(jù)；Fp-Growth算法；MapReduce；數(shù)據(jù)挖掘

DOIDOI：10.11907/rjdk.171258

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

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)文章編號(hào)：1672-7800（2017）008-0025-04

0 引言

近年來，數(shù)據(jù)呈爆炸式增長(zhǎng)，用于大數(shù)據(jù)的計(jì)算框架和基于大數(shù)據(jù)的各類算法成為研究熱點(diǎn)。MapReduce是一種由Google提出的用于分布式并行數(shù)據(jù)處理的編程模型，它采用“分而治之”的思想，把對(duì)數(shù)據(jù)的處理分解為Map與Reduce兩個(gè)核心階段。在MapReduce中高度封裝了Map和Reduce兩個(gè)函數(shù)接口，工程師只需實(shí)現(xiàn)這兩個(gè)接口就可實(shí)現(xiàn)大部分的并行數(shù)據(jù)處理工作[1-2]。MapReduce任務(wù)中的數(shù)據(jù)往往較多，會(huì)被分為多個(gè)分片，通常包含多個(gè)Map進(jìn)程，它們可以并行地運(yùn)行在不同的計(jì)算機(jī)上，極大提升了數(shù)據(jù)處理速度。在Map中，用戶的輸入被映射為一組組鍵值（Key-Value）對(duì)，這些鍵值對(duì)經(jīng)過Shffule過程后，形成一組或多組有序的鍵值對(duì)，排列好的鍵值對(duì)將作為Reduce的輸入值。Reduce階段，數(shù)據(jù)將會(huì)被合并和歸納總結(jié)并輸出。

Fp-Growth算法是數(shù)據(jù)挖掘中頻繁模式挖掘的經(jīng)典算法。目前，國(guó)內(nèi)外已有學(xué)者對(duì)Fp-Growth算法進(jìn)行并行化改造。楊勇等[3]對(duì)Fp-Growth算法中FP-tree的結(jié)構(gòu)及挖掘過程進(jìn)行了改進(jìn)，他們?cè)诜治鯢P-tree單路徑與多路徑的不同挖掘方法后，提出了一種新的剪枝策略，從而在挖掘過程中縮減部分分支的迭代次數(shù)，最后運(yùn)用MapReduce編程模型，對(duì)改進(jìn)的Fp-Growth算法進(jìn)行并行化。章志剛等[4]在MapReduce編程模型的基礎(chǔ)上提出了一種基于Fp-Growth的頻繁模式并行挖掘算法。該算法中，在每個(gè)計(jì)算節(jié)點(diǎn)上首先構(gòu)造局部頻繁模式樹，并對(duì)它進(jìn)行挖掘得到局部頻繁項(xiàng)目集，然后合并所有局部頻繁項(xiàng)目集從而得到全局頻繁項(xiàng)集，但此時(shí)得到的結(jié)果并不完備，因此對(duì)合并后未達(dá)到最小支持度閾值的項(xiàng)目集，重新計(jì)算其支持?jǐn)?shù)。Wei X等[5]提出了一種基于MapReduce的并行Fp-Growth挖掘策略，使最小支持度閾值和原始數(shù)據(jù)庫變化時(shí)有效挖掘出頻繁項(xiàng)。Riondato M等[6]提出了一種新的挖掘頻繁項(xiàng)集的隨機(jī)并行技術(shù)PARMA。PARMA中隨機(jī)創(chuàng)建多個(gè)小的運(yùn)算數(shù)據(jù)挖掘算法的并行樣本，每個(gè)樣本包含小規(guī)模的事務(wù)數(shù)據(jù)集，而后從每個(gè)樣本中匯總篩選出頻繁項(xiàng)集，最終得到所有頻繁集的一個(gè)近似解。

1 MapReduce編程模型

MapReduce中，每個(gè)Reduce的過程輸入都是按鍵排序。將Map的輸出進(jìn)行排序、合并后作為Reduce的輸入過程稱為Shuffle。如圖1所示，在Map端，輸入分片經(jīng)過Map方法處理后產(chǎn)生的輸出沒有簡(jiǎn)單將它寫入磁盤，而是存儲(chǔ)到一個(gè)內(nèi)存中的環(huán)形緩沖區(qū)中（默認(rèn)大小為100M），一旦緩沖區(qū)的內(nèi)容大小達(dá)到閾值（默認(rèn)為緩沖區(qū)大小的80%），緩沖區(qū)中的數(shù)據(jù)便開始溢出到磁盤中。在溢出的過程中，Map繼續(xù)往該緩沖區(qū)中寫入數(shù)據(jù)，如果該緩沖區(qū)被填滿，Map將會(huì)被阻塞直至當(dāng)前溢出寫磁盤過程完成。在溢出過程中，線程根據(jù)數(shù)據(jù)鍵值對(duì)應(yīng)的Reducer將數(shù)據(jù)分成相應(yīng)的分區(qū)，在每個(gè)分區(qū)中，后臺(tái)線程對(duì)分區(qū)中的數(shù)據(jù)進(jìn)行內(nèi)排序。每次環(huán)形緩沖區(qū)達(dá)到閾值時(shí)，都會(huì)生成一個(gè)新的溢出文件。因此默認(rèn)情況下，當(dāng)分片大于80M時(shí)，溢出工作完成后，會(huì)有幾個(gè)已分區(qū)且已排序的溢出文件。在Map任務(wù)完成前，這些溢出文件經(jīng)過一次或多次（默認(rèn)情況下一次最多合并10個(gè)文件流）合并最終得到一個(gè)已分區(qū)且排序的輸出文件。

在Reduce端，Reduce任務(wù)從所有的Map任務(wù)中選擇自己對(duì)應(yīng)的分區(qū)復(fù)制其中的數(shù)據(jù)。默認(rèn)情況下，Reduce有5個(gè)線程來并行地取得Map的輸出。如果Map輸出較小，自會(huì)被復(fù)制到JVM的內(nèi)存緩沖區(qū)中，否則，復(fù)制到磁盤中。一旦內(nèi)存緩沖區(qū)達(dá)到閾值，則合并后溢出寫到磁盤中。復(fù)制完所有的Map輸出后，Reduce任務(wù)進(jìn)入到合并階段，合并因子默認(rèn)為10，因此當(dāng)Map數(shù)量很大時(shí)，要經(jīng)過多次合并操作才能將數(shù)據(jù)輸入到Reduce方法中。在Reduce方法中對(duì)已排序的Map輸出中的每個(gè)鍵調(diào)用Reduce方法，最終Reduce方法的輸出被寫入HDFS文件系統(tǒng)中。

2 并行Fp-Growth算法實(shí)現(xiàn)

2.1 經(jīng)典頻繁模式挖掘方法

關(guān)聯(lián)規(guī)則算法的核心在于如何高效地找出滿足最小支持度的頻繁項(xiàng)集[6]。針對(duì)這一問題，Agrawal與R·Srikant在1994年提出了Apriori算法，該算法中用到一個(gè)頻繁項(xiàng)集的重要性質(zhì)，即頻繁項(xiàng)集的所有非空子集也是頻繁項(xiàng)集，這樣大大減少了候選項(xiàng)集的數(shù)量。然而，當(dāng)頻繁項(xiàng)集較多、事務(wù)數(shù)據(jù)庫較大時(shí)，該算法的開銷依然很大。為了克服Apriori的種種不足，韓家煒等[7-9]提出了基于頻繁模式樹的Fp-Growth算法，在Fp-Growth算法中采用了分治的策略：首先，掃描事務(wù)數(shù)據(jù)庫，將代表頻繁項(xiàng)集的事務(wù)壓縮成一顆頻繁模式樹；然后，將這種壓縮后的數(shù)據(jù)庫劃分為一組條件數(shù)據(jù)庫，并分別對(duì)每個(gè)條件數(shù)據(jù)庫進(jìn)行挖掘，以此遞歸，直到找出所有頻繁項(xiàng)。

Fp-Growth算法通過對(duì)原始事務(wù)數(shù)據(jù)庫進(jìn)行壓縮，映射為內(nèi)存中的一個(gè)頻繁模式數(shù)據(jù)，而后對(duì)該樹遞歸挖掘，從而找出所有的頻繁項(xiàng)集。這極大提高了頻繁項(xiàng)的查找效率，比Apriori算法大約快了一個(gè)數(shù)量級(jí)[10]。然而，當(dāng)事務(wù)數(shù)據(jù)增大到一定程度時(shí)，單臺(tái)計(jì)算機(jī)的內(nèi)存將不足以存儲(chǔ)構(gòu)建的巨型頻繁模式樹，計(jì)算資源也難以支持對(duì)這種巨型頻繁模式樹進(jìn)行遞歸挖掘的計(jì)算。因此，隨著事務(wù)數(shù)據(jù)的不斷增大，單節(jié)點(diǎn)的Fp-Growth算法將面臨時(shí)間和空間的雙重瓶頸[11]。對(duì)Fp-Growth算法進(jìn)行并行化改造可以解決這一問題。Fp-Growth算法的并行化將利用多個(gè)節(jié)點(diǎn)的內(nèi)存與計(jì)算資源，解決單節(jié)點(diǎn)算法的時(shí)間和空間瓶頸。本文將詳細(xì)探討基于MapReduce的Fp-Growth算法的并行化改進(jìn)算法FPMMR（Frequent Pattern Mining based on MapReuce）。endprint