一種基于FP-growth的并行SON算法的實(shí)現(xiàn)

郭進(jìn)偉 ，皮建勇

（1.貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽550025；2.貴州大學(xué) 云計(jì)算與物聯(lián)網(wǎng)研究中心，貴州 貴陽550025）

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

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

1 相關(guān)概念

1.1 FP-growth算法簡介

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

FP-growth算法發(fā)現(xiàn)頻繁項(xiàng)集的基本思想是：根據(jù)FP-tree構(gòu)造每個(gè)頻繁項(xiàng)的條件FP-tree，每個(gè)頻繁項(xiàng)都是一個(gè)前綴；每個(gè)前綴和其條件FP-tree的每一項(xiàng)合并生成一個(gè)新的前綴，根據(jù)此前綴繼續(xù)生成條件FP-tree，直到生成的條件FP-tree為空；每一個(gè)前綴都是頻繁的，即算法所得到的所有的前綴即為最終的頻繁項(xiàng)集。

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

1.2 SON算法簡介

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

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

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

表1 符號定義

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

2 基于FP-growth的SON算法的并行化實(shí)現(xiàn)

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

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

2.1 第一輪MapReduce迭代

在Map階段，每個(gè)Map任務(wù)完成從事務(wù)數(shù)據(jù)集的某一個(gè)分區(qū)中讀取到的事務(wù)，并將該分區(qū)中所有的事務(wù)存儲在本地內(nèi)存中，然后利用FP-growth算法算出本分區(qū)的局部頻繁項(xiàng)集，最后輸出的是一個(gè)鍵值對(其中 F是本分區(qū)的一個(gè)局部頻繁項(xiàng)集，1與鍵沒有任何關(guān)聯(lián))。

在Reduce階段，每個(gè)Reduce任務(wù)會處理一組局部頻繁項(xiàng)集，上個(gè)階段所有的Map任務(wù)輸出的相同的局部頻繁項(xiàng)集會集中到同一個(gè)Reduce任務(wù)上進(jìn)行處理，Reduce的任務(wù)就是將相同的局部頻繁項(xiàng)集輸出一次即可，最后的輸出結(jié)果即為全局的候選項(xiàng)集。

2.2 第二輪MapReduce迭代

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

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

3 實(shí)驗(yàn)結(jié)果與實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)環(huán)境

整個(gè)實(shí)驗(yàn)在Hadoop平臺下完成，平臺采用了Hadoop的1.0.4穩(wěn)定版本。硬件設(shè)備為4臺x86架構(gòu)的PC，主設(shè)備節(jié)點(diǎn)采用 Intel志強(qiáng)四核處理器，內(nèi)存為2 GB；從設(shè)備節(jié)點(diǎn)采用了AMD四核處理器，主頻為 2.7 GHz，內(nèi)存為2 GB。

3.2 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)采用accidents[8]作為實(shí)驗(yàn)事務(wù)數(shù)據(jù)集，該數(shù)據(jù)集包含1991年～2000年Flanders地區(qū)的交通事故記錄。該數(shù)據(jù)集的大小為34 678 KB，共340 184條事務(wù)，有572個(gè)不同的項(xiàng)，平均每條事務(wù)包含45個(gè)項(xiàng)。

3.3 實(shí)驗(yàn)分析

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

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

圖1 算法第一階段運(yùn)行時(shí)間

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

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

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

[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].電子學(xué)報(bào)，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.