1. FP-Growth算法弊端

FP-Growth算法是挖掘頻繁項集最常用的算法之一，其是基于迭代FP-Tree生成頻繁項集的關聯規則算法。此算法僅進行兩次數據集掃描，遞歸迭代構建FP-Tree(FP條件樹)，當FP-Tree中只有一個單分支時，遞歸迭代構建結束，最終得到頻繁項集，FP-Growth算法在時間、空間復雜度和數據挖掘的效率上相比Apriori都有明顯改善，對于數據量較小的數據挖掘，FP-Growth改進算法具有一定優勢。

但隨著數據量呈指數級增長時，該算法存在以下問題：①如果事務數據庫的數據達到海量級別，FP-Growth算法把所有事務數據中的頻繁項都壓縮至內存中的頻繁模式樹，樹的高度或寬度將達到內存無法接受的規模，可能導致過程失敗；②在挖掘頻繁模式過程中，每次遞歸計算都生成一棵FP-tree，每次遍歷時都會產生條件頻繁模式樹，并消耗大量時間和存儲空間。對于大規模的數據集時，傳統的Apriori算法和FP-Growth算法都是基于串行計算，其計算時間和空間復雜度較高。

2. Hadoop與MapReduce簡介

Hadoop平臺是適合大數據的分布式存儲和計算的平臺，有2個核心組件，分別為分布式存儲系統(HDFS)和分布式計算框架(MapReduce): HDFS為分布式計算存儲提供底層支持，可實現超大文件的容錯和存儲；MapReduce是一種分布式編程模式，能夠實現對大規模數據進行并行運算。

3. MapReduce改造FP-Growth算法

使用MapReduce改造FP-Growth算法，是采用分而治之的思想，通過負載均衡的分組策略，在Hadoop平臺實現FP-Growth算法的并行化，使FP-Growth算法能適應大規模數據的處理要求，同時借助Hadoop平臺在分布式處理方面的優勢，從而提升計算處理能力。

FP-Growth算法主要分為2個步驟：FP-Tree的構建和從FP-Tree中遞歸挖掘頻繁項集；

用MapReduce任務完成頻繁項集的挖掘。其中，結合分布式緩存機制存儲F_List表提高訪問效率，降低I/O操作，通過負載均衡分組策略，平衡各個節點的壓力，充分利用各個節點的計算能力，從而提高該算法的整體性能。

基本思想：FP-Growth算法并行化的基本思想。首先，統計事務數據庫中每個項的頻繁項集F，并刪除小于最小支持度的項，再將剩余的項進行降序排序，得到集合F_List;然后，通過Map過程讀入事務項，按負載均衡分組策略分發到不同的Reduce節點上;接著，各節點同步 Reduce過程構造FP-Tree，并對FP-Tree進行FP-Growth挖掘得到局部頻繁項集，由局部頻繁項集合并成全局頻繁項集；最后，由全局頻繁項集得到最大頻繁項集。

FP-Growth并行化算法的輸入輸出和 傳統的FP-Growth算法相同，輸入事務集和最小支持度計數，輸出所有支持度計數大于最小支持度計數閾值的頻繁項集。該算法包括幾個MapReduce任務、2次掃描事務數據庫。

?? 第1階段，挖掘事務數據庫的1項頻繁集。首先，從分布式文件系統中讀入事務數據集，將事務數據集分成M個數據集并行分發至M個Map節點上。然后，進行第1次事務數據庫掃描，在各個Map節點中并行計算每個節點上的支持度計數，根據設定的最小支持度閾值，刪除小于最小支持度的項。最后，將剩余的項進行降序排序，將所有節點的結果合并得到全局頻繁1項集；

F_List全局頻繁1項集挖掘模型如下圖1所示。

? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ?圖1? 基于MapReduce的并行化全局頻繁1項集挖掘模型

?? 第2階段，負載均衡劃分F_List，得到長度為Q的均衡化分組表G_List，即將G_List中的項劃分為Q組，為每一組分配一個組號gidi(1≤i≤Q)，gidi對應的組記作G_Listgidi，G_Listgidi中的每一項記作αk∈G_Listgidi，1≤k≤G_Listgidi.length。這樣每條事務集的組號與G_List的組號相對應。

?? 第3階段，并行FP-Growth進行第2次事務數據庫掃描。

?? Map階段：第2次掃描事務數據庫，將事務所對應的部分發送到組號為gidi的事務組DB(gidi)中，實現對事務數據庫進行分組，得到一組彼此相互獨立的事務組。Map函數的輸入鍵值對<key=RowNo，value=s>，根據G_List生成一個HashMap，該函數輸出鍵值對為<key=gidi，value = {itemi...itemj}> ，即把以組號gidi為鍵、事務itemi...itemj為值的鍵值對發送到Reduce節點。這樣所有包含G_Listgidi項的事務，所對應的部分都被發送到組號為gidi的分組事務集DB(gidi)中。

?? Reduce階段：對本地事務集按接收的鍵值對構造局部FP-Tree，遞歸挖掘局部頻繁項集。?? 頻繁項集挖掘模型如下圖2所示。

? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ?圖2? 基于MapReduce的并行化頻繁項集挖掘模型

?? 第4階段，合并局部頻繁項集生成全局頻繁項集。讀取HDFS文件中的局部頻繁項集，得到全局支持度，再根據全局支持度進行判斷，最后由全局頻繁項集得到最大頻繁項集。

FP-Growth算法在Hadoop平臺上實現并行化的流程見圖3。

? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ?圖3? 基于MapReduce的FP-Growth算法并行化實現模型

以上就是使用MapReduce改造Fp-Growth算法以適應大規模數據的算法過程。

總結

以上是生活随笔為你收集整理的MapReduce改造fp-growth算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。