Fp—Growth算法在MapReduce框架下的實現

舒遠仲+戴海輝+吳小玲

摘 要：Fp-Growth算法是頻繁模式挖掘的經典算法，已在許多領域得到了良好應用。傳統Fp-Growth算法是基于內存的，而計算機內存卻無法裝載入大數據，故傳統Fp-Growth算法并不能有效地處理大數據。提出一種新的基于MapReduce并行計算框架的Fp-Growth實現，使Fp-Growth算法在多臺計算機上并行計算，從而實現大數據的有效處理。實驗結果表明，該算法具有很好的擴展性，頻繁模式挖掘效率隨著用于計算的主機的增加而平穩提升。

關鍵詞：大數據；Fp-Growth算法；MapReduce；數據挖掘

DOIDOI：10.11907/rjdk.171258

中圖分類號：TP312

文獻標識碼：A 文章編號文章編號：1672-7800（2017）008-0025-04

0 引言

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

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

1 MapReduce編程模型

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

在Reduce端，Reduce任務從所有的Map任務中選擇自己對應的分區復制其中的數據。默認情況下，Reduce有5個線程來并行地取得Map的輸出。如果Map輸出較小，自會被復制到JVM的內存緩沖區中，否則，復制到磁盤中。一旦內存緩沖區達到閾值，則合并后溢出寫到磁盤中。復制完所有的Map輸出后，Reduce任務進入到合并階段，合并因子默認為10，因此當Map數量很大時，要經過多次合并操作才能將數據輸入到Reduce方法中。在Reduce方法中對已排序的Map輸出中的每個鍵調用Reduce方法，最終Reduce方法的輸出被寫入HDFS文件系統中。

2 并行Fp-Growth算法實現

2.1 經典頻繁模式挖掘方法

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

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