mapreduce算法實例，MapReduce框架下的FP Growth算法概述

轉載自：http://blog.sina.com.cn/s/blog_68ffc7a40100uebi.html

前面的博客分析了關聯分析中非常重要的一個算法-FP Growth.該算法根據數據庫在內存中構造一個精巧的數據結構-FP Tree,通過對FP Tree不斷的遞歸挖掘就可以得到所有的完備Frequent Patterns.但是在目前海量數據的現狀下，FP Tree已經大到無法駐留在計算機的內存中。因此，并行化是唯一的選擇。這篇博客主要講一下如何在MapReduce框架下進行并行FP挖掘，它主要的算法在文獻1中有詳細描述。

如何進行FP Growth的并行化呢？一個很自然的想法就是，將原始的數據庫劃分成幾個分區，這幾個分區分別在不同的機器上，這樣的話我們就可以對不同數據分區并行得進行FP Growth挖掘，最后將不同機器上的結果結合起來得到最終的結果。的確，這是一個正確的思路。但問題是：我們按照什么樣的方法來把數據庫劃分成區塊呢？如果FP Growth能夠真正的獨立進行并行化，那么就需要這些數據分區必須能夠互相獨立，也就是這些分區針對某一部分項目來說是完備的。于是就有一種方法：通過對數據庫的一次掃描，構造一個Frequent Item列表F_List = {I1:count1, I2:count2, I3:count3…} ^ (count1> count2 > count3>…)，然后將F_List分成幾個Group，形成幾個G_List.這時候我們再掃描數據庫的每一條Transaction，如果這條Transaction中包含一條G_List中的Item，那么這條transaction就被添加到該group對應的數據庫分區中去，這樣就形成了幾個數據庫分區，每個數據庫分區對應一個group和一個group_list。這種分區方法就保證對group_list里面的item而言，數據庫分區是完備的。這種分區方式會導致數據會有冗余，因為一條transaction可能會在不同的分區中都有備份,但為了保持數據的獨立性,這是一個不得已方法。

下面就簡單談談該算法的步驟:

第一步:數據庫分區.把數據庫分成連續的不同的分區,每一個分區分布在不同的機器上.每一個這樣的分區稱之為shard。

第二步:計算F_list,也就是所有item的support count.這個計算通過一個MapReduce就可以完成.想想hadoop上word count的例子,本質上和這一步是一樣的.

第三步:條目分組.將F_list里的條目分成Q個組,這樣的話就行成了一個group_list,group_list里的每一個group都被分配一個group_id,每個group_list都包含一組item的集合.

第四步:并行FP Growth.這一步是關鍵.它也是由一個MapReduce來完成的.具體來看看.

Mapper:

這個Mapper完成的主要功能是數據庫分區。它和第一步中的shard有所不同，它利用第一步shard的數據庫分區，一個一個處理shard數據庫分區中的每一條transaction,將transaction分成一個一個item，每一個item根據group_list映射到合適的group里去。這樣的話，通過mapper，屬于同一個group的item集合都被聚合到一臺機器上，這樣就形成了我們前面講到的完備數據集，在下一步的reducer中就可以并行得進行FP Growth算法了。

Reducer：

基于mapper形成的完備數據集，進行local的FP_Growth算法

第五步：聚合，將各臺機器上的結果聚合成最終我們需要的結果。

前面的博客分析了關聯分析中非常重要的一個算法-FP Growth.該算法根據數據庫在內存中構造一個精巧的數據結構-FP Tree,通過對FP Tree不斷的遞歸挖掘就可以得到所有的完備Frequent Patterns.但是在目前海量數據的現狀下，FP Tree已經大到無法駐留在計算機的內存中。因此，并行化是唯一的選擇。這篇博客主要講一下如何在MapReduce框架下進行并行FP挖掘，它主要的算法在文獻1中有詳細描述。

如何進行FP Growth的并行化呢？一個很自然的想法就是，將原始的數據庫劃分成幾個分區，這幾個分區分別在不同的機器上，這樣的話我們就可以對不同數據分區并行得進行FP Growth挖掘，最后將不同機器上的結果結合起來得到最終的結果。的確，這是一個正確的思路。但問題是：我們按照什么樣的方法來把數據庫劃分成區塊呢？如果FP Growth能夠真正的獨立進行并行化，那么就需要這些數據分區必須能夠互相獨立，也就是這些分區針對某一部分項目來說是完備的。于是就有一種方法：通過對數據庫的一次掃描，構造一個Frequent Item列表F_List = {I1:count1, I2:count2, I3:count3…} ^ (count1> count2 > count3>…)，然后將F_List分成幾個Group，形成幾個G_List.這時候我們再掃描數據庫的每一條Transaction，如果這條Transaction中包含一條G_List中的Item，那么這條transaction就被添加到該group對應的數據庫分區中去，這樣就形成了幾個數據庫分區，每個數據庫分區對應一個group和一個group_list。這種分區方法就保證對group_list里面的item而言，數據庫分區是完備的。這種分區方式會導致數據會有冗余，因為一條transaction可能會在不同的分區中都有備份,但為了保持數據的獨立性,這是一個不得已方法。

下面就簡單談談該算法的步驟:

第一步:數據庫分區.把數據庫分成連續的不同的分區,每一個分區分布在不同的機器上.每一個這樣的分區稱之為shard。

第二步:計算F_list,也就是所有item的support count.這個計算通過一個MapReduce就可以完成.想想hadoop上word count的例子,本質上和這一步是一樣的.

第三步:條目分組.將F_list里的條目分成Q個組,這樣的話就行成了一個group_list,group_list里的每一個group都被分配一個group_id,每個group_list都包含一組item的集合.

第四步:并行FP Growth.這一步是關鍵.它也是由一個MapReduce來完成的.具體來看看.

Mapper:

這個Mapper完成的主要功能是數據庫分區。它和第一步中的shard有所不同，它利用第一步shard的數據庫分區，一個一個處理shard數據庫分區中的每一條transaction,將transaction分成一個一個item，每一個item根據group_list映射到合適的group里去。這樣的話，通過mapper，屬于同一個group的item集合都被聚合到一臺機器上，這樣就形成了我們前面講到的完備數據集，在下一步的reducer中就可以并行得進行FP Growth算法了。

Reducer：

基于mapper形成的完備數據集，進行local的FP_Growth算法

第五步：聚合，將各臺機器上的結果聚合成最終我們需要的結果。

上面的圖就給出了算法步驟的框圖。有了這個框圖，大家可能對算法的步驟就有一定的認識了。后面的博客就針對每一步進行具體的分析。

上面的圖就給出了算法步驟的框圖。有了這個框圖，大家可能對算法的步驟就有一定的認識了。后面的博客就針對每一步進行具體的分析。