摘 要： 單節(jié)點(diǎn)運(yùn)行的傳統(tǒng)SON算法能夠有效降低CPU和I/O負(fù)載，而且算法僅需要對(duì)整個(gè)事務(wù)數(shù)據(jù)集掃描兩次。但是在算法執(zhí)行的階段一中發(fā)現(xiàn)局部頻繁項(xiàng)集時(shí)采用的Apriori算法仍然需要對(duì)每個(gè)分區(qū)進(jìn)行多次掃描。在深入研究SON算法的基礎(chǔ)上，根據(jù)MapReduce編程模型提出了基于FP-growth的SON算法的并行化實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果表明，基于FP-growth的并行SON算法不僅降低了傳統(tǒng)SON算法的運(yùn)行時(shí)間，并且隨著分區(qū)數(shù)目的增加還能獲取比較好的加速比。
關(guān)鍵詞： FP-growth；SON 算法；MapReduce；數(shù)據(jù)挖掘
信息技術(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)出了眾多的開(kāi)源項(xiàng)目，其中Apache基金會(huì)下的Hadoop[5]是其中比較有代表性的分布式并行編程框架。近幾年隨著大數(shù)據(jù)的興起，MapReduce編程模型的研究[6]以及基于MapReduce的數(shù)據(jù)挖掘算法的實(shí)現(xiàn)[7]也愈加火熱。
1 相關(guān)概念
1.1 FP-growth算法簡(jiǎn)介
FP-growth算法是Han Jiawei等人于2000年提出的發(fā)現(xiàn)頻繁項(xiàng)集的算法，該算法采用分治策略將一個(gè)問(wèn)題分解為較小的子問(wèn)題，從而發(fā)現(xiàn)以某個(gè)特定后綴結(jié)尾的所有頻繁項(xiàng)集。該算法使用了一種稱(chēng)之為頻繁模式樹(shù)FP-tree（Frequent Pattern Tree）的數(shù)據(jù)結(jié)構(gòu)，F(xiàn)P-tree是一種特殊的前綴樹(shù)，由頻繁項(xiàng)頭表和項(xiàng)前綴樹(shù)構(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)集。
相比于A(yíng)priori算法,FP-growth算法有如下優(yōu)點(diǎn)：(1)將較大的數(shù)據(jù)庫(kù)壓縮成了較小的數(shù)據(jù)結(jié)構(gòu)保存在內(nèi)存中，從而避免了反復(fù)掃描數(shù)據(jù)庫(kù)，降低了掃描開(kāi)銷(xiāo)；(2)基于FP-tree的挖掘采用遞歸的方式搜索較短的模式并將其逐次連接起來(lái)，從而避免生成大量的候選項(xiàng)集；(3)將原本的挖掘任務(wù)劃分成一組在有限的條件數(shù)據(jù)庫(kù)中挖掘特定的頻繁模式的任務(wù)，從而降低了搜索空間。
1.2 SON算法簡(jiǎn)介
Apriori算法通過(guò)迭代的方式來(lái)挖掘出所有的頻繁項(xiàng)集，即候選(k+1)-項(xiàng)集的產(chǎn)生依賴(lài)于頻繁k-項(xiàng)集，然后通過(guò)掃描事物數(shù)據(jù)集來(lái)計(jì)算出每一個(gè)候選(k+1)-項(xiàng)集支持度計(jì)數(shù)，進(jìn)而判斷得到頻繁(k+1)-項(xiàng)集，因此該算法需要對(duì)事務(wù)數(shù)據(jù)集進(jìn)行多次掃描。如果找到這樣一種方法，通過(guò)該方法得到的候選項(xiàng)集包含了該事務(wù)數(shù)據(jù)集中所有的頻繁項(xiàng)集，那么只需要對(duì)事物數(shù)據(jù)集掃描一遍即可找出所有的頻繁項(xiàng)集。
以上為分區(qū)算法的核心思想。分區(qū)算法需要對(duì)事物數(shù)據(jù)集進(jìn)行兩遍掃描，第一遍掃描找出候選項(xiàng)集，此候選項(xiàng)集包含所有的頻繁項(xiàng)集。第二遍掃描對(duì)所有的候選項(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)集（稱(chēng)之為局部頻繁項(xiàng)集，此項(xiàng)集是潛在的整個(gè)事務(wù)數(shù)據(jù)集的頻繁項(xiàng)集），最后把所有分區(qū)的頻繁項(xiàng)集匯聚到一起就得到了整個(gè)事務(wù)數(shù)據(jù)集的候選項(xiàng)集（稱(chēng)之為全局候選項(xiàng)集）。在第二個(gè)階段，為上一個(gè)階段得到的全局候選項(xiàng)集進(jìn)行計(jì)數(shù)，從而得到候選項(xiàng)集的支持度計(jì)數(shù)，其中大于最小支持度計(jì)數(shù)的候選項(xiàng)集即為全局頻繁項(xiàng)集。以下為SON算法的偽代碼，表1為偽代碼中所用的符號(hào)定義說(shuō)明。
偽代碼中首先將事務(wù)數(shù)據(jù)集D劃分為n個(gè)分區(qū)，階段1分別對(duì)每一個(gè)分區(qū)pi通過(guò)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算法來(lái)計(jì)算每個(gè)分區(qū)的頻繁項(xiàng)集，即同樣需要對(duì)每個(gè)分區(qū)掃描多次才能得到局部頻繁項(xiàng)集，所以SON算法是宏觀(guān)上對(duì)整個(gè)事務(wù)數(shù)據(jù)集掃描兩次，而從局部上來(lái)看仍然需要對(duì)每個(gè)分區(qū)分別掃描多次。本節(jié)提出的算法實(shí)現(xiàn)基于FP-growth，這將有效減少對(duì)分區(qū)的掃描次數(shù)。
SON算法非常適合于并行計(jì)算環(huán)境，SON算法中的每一個(gè)分區(qū)都可以并行地處理。用MapReduce編程模型對(duì)基于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ù)來(lái)判斷是否為頻繁項(xiàng)集。
2.1 第一輪MapReduce迭代
在Map階段，每個(gè)Map任務(wù)完成從事務(wù)數(shù)據(jù)集的某一個(gè)分區(qū)中讀取到的事務(wù)，并將該分區(qū)中所有的事務(wù)存儲(chǔ)在本地內(nèi)存中，然后利用FP-growth算法算出本分區(qū)的局部頻繁項(xiàng)集，最后輸出的是一個(gè)鍵值對(duì)<F，1>(其中F是本分區(qū)的一個(gè)局部頻繁項(xiàng)集，1與鍵沒(méi)有任何關(guān)聯(lián))。
class FirstMapper {
List tSet; //事務(wù)數(shù)據(jù)集
Map localFI; //局部頻繁項(xiàng)集
map(key, value) {
//將value封裝為事務(wù)
t = genTransaction(value);
//將事務(wù)添加到事務(wù)數(shù)據(jù)集中
tSet.add(transaction);
}
cleanup() {
//用FP-growth算法計(jì)算得到局部頻繁項(xiàng)集
localFI = genFrequentItemsets(transaction);
//將局部頻繁項(xiàng)集輸出
for(i = 1; (fis = localFI.get(i)) != null; i++)
for(f : fis)
write(f, 1);
}
}
在Reduce階段，每個(gè)Reduce任務(wù)會(huì)處理一組局部頻繁項(xiàng)集，上個(gè)階段所有的Map任務(wù)輸出的相同的局部頻繁項(xiàng)集會(huì)集中到同一個(gè)Reduce任務(wù)上進(jìn)行處理，Reduce的任務(wù)就是將相同的局部頻繁項(xiàng)集輸出一次即可，最后的輸出結(jié)果即為全局的候選項(xiàng)集。
class FirstReducer {
reduce(key, values) {
write(key, null);
}
}
2.2 第二輪MapReduce迭代
在Map階段，每個(gè)Map任務(wù)仍然處理事務(wù)數(shù)據(jù)集上的一個(gè)分區(qū)，在Map任務(wù)開(kāi)始前，把上一個(gè)MapReduce迭代產(chǎn)生的全局候選項(xiàng)集放入本地內(nèi)存中，Map任務(wù)開(kāi)始后每讀入一個(gè)事務(wù)，找尋全局候選項(xiàng)集中哪些候選項(xiàng)集為此事務(wù)的子集，如果某候選項(xiàng)集為此事務(wù)子集，即輸出<F，1>(其中F為此候選項(xiàng)集，1代表為此事務(wù)的子集)，便于在下一階段計(jì)算此候選項(xiàng)集的支持度計(jì)數(shù)。
class SecondMapper {
List cI; //全局候選項(xiàng)集
setup() {
//初始化全局候選項(xiàng)集
cI = getCandidateItemsets();
}
map(key, value) {
t = genTransaction(value);
//若候選項(xiàng)存在于某事務(wù)中就進(jìn)行輸出
for(f : cI)
if(t.contain(f))
write(f, 1);
}
}
在Reduce階段，每個(gè)Reduce任務(wù)處理一組全局候選項(xiàng)集，上個(gè)階段所有的Map任務(wù)輸出的相同的候選項(xiàng)集會(huì)集中到同一個(gè)Reduce任務(wù)上進(jìn)行處理，計(jì)算全局候選項(xiàng)集的支持度計(jì)數(shù)，根據(jù)其支持度計(jì)數(shù)即可判斷該項(xiàng)集是否為頻繁項(xiàng)集，Reduce任務(wù)會(huì)將得到的全局頻繁項(xiàng)集進(jìn)行輸出。
class SecondReducer {
reduce(key, values) {
sum = 0;
for(val : values)
sum += val.get();
//若候選項(xiàng)大于最小支持度就輸出
if(sum >= minsup)
write(key, null);
}
}
3 實(shí)驗(yàn)結(jié)果與實(shí)驗(yàn)分析
3.1 實(shí)驗(yàn)環(huán)境
整個(gè)實(shí)驗(yàn)在Hadoop平臺(tái)下完成，平臺(tái)采用了Hadoop的1.0.4穩(wěn)定版本。硬件設(shè)備為4臺(tái)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)分析
為了對(duì)基于A(yíng)priori的并行SON算法和基于FP-growth的并行SON算法進(jìn)行比較，首先用MapReduce模型分別實(shí)現(xiàn)兩個(gè)算法。發(fā)現(xiàn)兩個(gè)算法僅在階段1的局部頻繁項(xiàng)集處有異，在階段2沒(méi)有任何差別，所以實(shí)驗(yàn)僅對(duì)兩個(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算法比基于A(yíng)priori的并行SON算法運(yùn)行時(shí)間明顯減少。隨著數(shù)據(jù)集劃分的分區(qū)數(shù)目的增加，兩種算法運(yùn)行的總時(shí)間將明顯減少。
圖2顯示了隨著accidents數(shù)據(jù)集劃分塊數(shù)的增加，基于FP-growth的并行SON算法的運(yùn)行能夠得到接近線(xiàn)性的加速比。
本文分析了傳統(tǒng)的SON算法，指出了SON算法雖然從宏觀(guān)上對(duì)事務(wù)數(shù)據(jù)集掃描了兩次，但是發(fā)現(xiàn)在局部頻繁項(xiàng)集時(shí)采用的Apriori算法仍然需要對(duì)每個(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ú)立的，互相之間沒(méi)有聯(lián)系，這導(dǎo)致了隨著分區(qū)數(shù)目的增加使階段1生成的全局頻繁項(xiàng)集也會(huì)增加。因此，如何利用MapReduce實(shí)現(xiàn)FP-growth的完全并行化實(shí)現(xiàn)將在后續(xù)工作中進(jìn)一步研究。
參考文獻(xià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.