一種基于FP-growth的并行SON算法的實現

郭進偉 ，皮建勇

（1.貴州大學 計算機科學與技術學院，貴州 貴陽550025；2.貴州大學 云計算與物聯網研究中心，貴州 貴陽550025）

信息技術的高速發展使得各行各業累積了海量數據，如何從中提取有用的信息已經成為了數據挖掘所面臨的巨大挑戰。頻繁項集是數據挖掘中一個非常重要的概念，Apriori算法[1]和 FP-growth算法[2]是挖掘頻繁項集最為著名的算法，但其串行計算的復雜度較高。SON算法[3]為并行化發現頻繁項集提供了解決思路。

谷歌于 2004年提出了 MapReduce編程模型[4]，為并行處理和分析大規模的數據提供了重要的參考。根據MapReduce編程模型涌現出了眾多的開源項目，其中A-pache基金會下的Hadoop[5]是其中比較有代表性的分布式并行編程框架。近幾年隨著大數據的興起，MapReduce編程模型的研究[6]以及基于MapReduce的數據挖掘算法的實現[7]也愈加火熱。

1 相關概念

1.1 FP-growth算法簡介

FP-growth算法是Han Jiawei等人于2000年提出的發現頻繁項集的算法，該算法采用分治策略將一個問題分解為較小的子問題，從而發現以某個特定后綴結尾的所有頻繁項集。該算法使用了一種稱之為頻繁模式樹FP-tree（Frequent Pattern Tree）的數據結構，FP-tree 是一種特殊的前綴樹，由頻繁項頭表和項前綴樹構成。

FP-growth算法發現頻繁項集的基本思想是：根據FP-tree構造每個頻繁項的條件FP-tree，每個頻繁項都是一個前綴；每個前綴和其條件FP-tree的每一項合并生成一個新的前綴，根據此前綴繼續生成條件FP-tree，直到生成的條件FP-tree為空；每一個前綴都是頻繁的，即算法所得到的所有的前綴即為最終的頻繁項集。

相比于Apriori算法,FP-growth算法有如下優點：(1)將較大的數據庫壓縮成了較小的數據結構保存在內存中，從而避免了反復掃描數據庫，降低了掃描開銷；(2)基于FP-tree的挖掘采用遞歸的方式搜索較短的模式并將其逐次連接起來，從而避免生成大量的候選項集；(3)將原本的挖掘任務劃分成一組在有限的條件數據庫中挖掘特定的頻繁模式的任務，從而降低了搜索空間。

1.2 SON算法簡介

Apriori算法通過迭代的方式來挖掘出所有的頻繁項集，即候選(k+1)-項集的產生依賴于頻繁k-項集，然后通過掃描事物數據集來計算出每一個候選(k+1)-項集支持度計數，進而判斷得到頻繁(k+1)-項集，因此該算法需要對事務數據集進行多次掃描。如果找到這樣一種方法，通過該方法得到的候選項集包含了該事務數據集中所有的頻繁項集，那么只需要對事物數據集掃描一遍即可找出所有的頻繁項集。

以上為分區算法的核心思想。分區算法需要對事物數據集進行兩遍掃描，第一遍掃描找出候選項集，此候選項集包含所有的頻繁項集。第二遍掃描對所有的候選項集新型計數，其中大于最小支持度計數的候選項集即為頻繁項集。

根據分區算法兩遍掃描的思想，算法的執行分為兩個階段。在第一個階段，算法把事物數據集劃分為數個互不相交的分區，然后分別為每個分區計算出本分區的頻繁項集（稱之為局部頻繁項集，此項集是潛在的整個事務數據集的頻繁項集），最后把所有分區的頻繁項集匯聚到一起就得到了整個事務數據集的候選項集（稱之為全局候選項集）。在第二個階段，為上一個階段得到的全局候選項集進行計數，從而得到候選項集的支持度計數，其中大于最小支持度計數的候選項集即為全局頻繁項集。以下為SON算法的偽代碼，表1為偽代碼中所用的符號定義說明。

表1 符號定義

偽代碼中首先將事務數據集D劃分為n個分區，階段1分別對每一個分區pi通過gen_large_itemsets方法計算其局部頻繁項集L′，該方法采用的是Apriori算法。在合并階段，算法將每個分區局部頻繁項集合并成一個全局候選項集CG。在階段2中，算法計算每個全局候選項集的支持度計數，其中大于最小支持度計數minSup的為最終的頻繁項集LG。

2 基于FP-growth的SON算法的并行化實現

從SON算法的描述中可以看出，在算法第一階段中需要計算出局部頻繁項集，原始的SON算法采用Apriori算法來計算每個分區的頻繁項集，即同樣需要對每個分區掃描多次才能得到局部頻繁項集，所以SON算法是宏觀上對整個事務數據集掃描兩次，而從局部上來看仍然需要對每個分區分別掃描多次。本節提出的算法實現基于FP-growth，這將有效減少對分區的掃描次數。

SON算法非常適合于并行計算環境，SON算法中的每一個分區都可以并行地處理。用MapReduce編程模型對基于FP-growth的SON算法進行并行化實現。算法的實現需要兩輪迭代，第一輪MapReduce迭代計算出每一個分區的局部頻繁項集并由此生成全局候選項集。第二輪MapReduce迭代計算出每一個全局候選項集的支持度計數，并根據支持度計數來判斷是否為頻繁項集。

2.1 第一輪MapReduce迭代

在Map階段，每個Map任務完成從事務數據集的某一個分區中讀取到的事務，并將該分區中所有的事務存儲在本地內存中，然后利用FP-growth算法算出本分區的局部頻繁項集，最后輸出的是一個鍵值對(其中 F是本分區的一個局部頻繁項集，1與鍵沒有任何關聯)。

在Reduce階段，每個Reduce任務會處理一組局部頻繁項集，上個階段所有的Map任務輸出的相同的局部頻繁項集會集中到同一個Reduce任務上進行處理，Reduce的任務就是將相同的局部頻繁項集輸出一次即可，最后的輸出結果即為全局的候選項集。

2.2 第二輪MapReduce迭代

在Map階段，每個Map任務仍然處理事務數據集上的一個分區，在Map任務開始前，把上一個MapReduce迭代產生的全局候選項集放入本地內存中，Map任務開始后每讀入一個事務，找尋全局候選項集中哪些候選項集為此事務的子集，如果某候選項集為此事務子集，即輸出(其中 F為此候選項集，1代表為此事務的子集)，便于在下一階段計算此候選項集的支持度計數。

在Reduce階段，每個Reduce任務處理一組全局候選項集，上個階段所有的Map任務輸出的相同的候選項集會集中到同一個Reduce任務上進行處理，計算全局候選項集的支持度計數，根據其支持度計數即可判斷該項集是否為頻繁項集，Reduce任務會將得到的全局頻繁項集進行輸出。

3 實驗結果與實驗分析

3.1 實驗環境

整個實驗在Hadoop平臺下完成，平臺采用了Hadoop的1.0.4穩定版本。硬件設備為4臺x86架構的PC，主設備節點采用 Intel志強四核處理器，內存為2 GB；從設備節點采用了AMD四核處理器，主頻為 2.7 GHz，內存為2 GB。

3.2 實驗數據集

實驗采用accidents[8]作為實驗事務數據集，該數據集包含1991年～2000年Flanders地區的交通事故記錄。該數據集的大小為34 678 KB，共340 184條事務，有572個不同的項，平均每條事務包含45個項。

3.3 實驗分析

為了對基于Apriori的并行SON算法和基于FP-growth的并行 SON算法進行比較，首先用MapReduce模型分別實現兩個算法。發現兩個算法僅在階段1的局部頻繁項集處有異，在階段2沒有任何差別，所以實驗僅對兩個算法的階段1的運行進行比較。兩個算法分別在同等的集群條件和同樣的數據集下運行。由于分布式環境下的實驗結果具有一定的顛簸性，所有實驗的最終結果均為多次實驗后取得的合理值。

圖1為accidents數據集在保持不變和劃分為2塊、4塊、8塊的情況下，兩種算法分別在第一輪迭代時消耗的總時間。從圖1可以看出，在算法采用相同的分區數目時，基于FP-growth的并行SON算法比基于Apriori的并行SON算法運行時間明顯減少。隨著數據集劃分的分區數目的增加，兩種算法運行的總時間將明顯減少。

圖1 算法第一階段運行時間

圖2顯示了隨著accidents數據集劃分塊數的增加，基于FP-growth的并行SON算法的運行能夠得到接近線性的加速比。

圖2 基于FP-growth的并行SON算法的加速比

本文分析了傳統的SON算法，指出了SON算法雖然從宏觀上對事務數據集掃描了兩次，但是發現在局部頻繁項集時采用的Apriori算法仍然需要對每個分區掃描多次。根據MapReduce編程模型，本文提出的基于FP-growth的并行SON算法的實現，不僅減少了SON算法在階段1中的運行時間，并且算法運行在Hadoop集群上，為處理海量數據提供了可能。雖然本文提出的算法的實現從某種程度上可以看作是FP-growth算法的并行化實現，但是每個分區生成的FP-tree都是獨立的，互相之間沒有聯系，這導致了隨著分區數目的增加使階段1生成的全局頻繁項集也會增加。因此，如何利用MapReduce實現FP-growth的完全并行化實現將在后續工作中進一步研究。

[1]AGRAWAL R，SRIKANT R.Fast algorithms for mining association rules[C].Proceedings of 20th Conference on Very Large Data Bases，1994：487-499.

[2]Han Jiawei，Pei Jian，Yin Yiwen.Mining frequent patterns without candidate generation[C].Proceedings of Conference on the Management of Data，2000：1-12.

[3]SAVASERE A，OMIECINSKI E，NAVATHE S.An efficient algorithm for mining association rules in large databases[C].Proceedings of the 21st Conference on Very Large Database，1995：432-444.

[4]DEAN J，GHEMAWAT S.MapReduce：simplified data processing on large clusters[J].Communications of the ACM，2008，51(1)：107-113.

[5]Apache Hadoop[EB/OL].[2013-07-12].http://hadoop.apache.org.

[6]李建江，崔健，王聃，等.MapReduce并行編程模型研究綜述[J].電子學報，2011，39(11)：2635-2642.

[7]Apache Mahouts[EB/OL].[2013-08-12].http://mahout.apache.org/.

[8]Frequent Itemset Mining Dataset Repository[EB/OL].[2013-08-28].http://fimi.ua.ac.be/data.