摘  要： 單節(jié)點運行的傳統(tǒng)SON算法能夠有效降低CPU和I/O負載，而且算法僅需要對整個事務(wù)數(shù)據(jù)集掃描兩次。但是在算法執(zhí)行的階段一中發(fā)現(xiàn)局部頻繁項集時采用的Apriori算法仍然需要對每個分區(qū)進行多次掃描。在深入研究SON算法的基礎(chǔ)上，根據(jù)MapReduce編程模型提出了基于FP-growth的SON算法的并行化實現(xiàn)。實驗結(jié)果表明，基于FP-growth的并行SON算法不僅降低了傳統(tǒng)SON算法的運行時間，并且隨著分區(qū)數(shù)目的增加還能獲取比較好的加速比。
關(guān)鍵詞： FP-growth；SON 算法；MapReduce；數(shù)據(jù)挖掘

    信息技術(shù)的高速發(fā)展使得各行各業(yè)累積了海量數(shù)據(jù)，如何從中提取有用的信息已經(jīng)成為了數(shù)據(jù)挖掘所面臨的巨大挑戰(zhàn)。頻繁項集是數(shù)據(jù)挖掘中一個非常重要的概念，Apriori算法[1]和FP-growth算法[2]是挖掘頻繁項集最為著名的算法，但其串行計算的復(fù)雜度較高。SON算法[3]為并行化發(fā)現(xiàn)頻繁項集提供了解決思路。
    谷歌于2004年提出了MapReduce編程模型[4]，為并行處理和分析大規(guī)模的數(shù)據(jù)提供了重要的參考。根據(jù)MapReduce編程模型涌現(xiàn)出了眾多的開源項目，其中Apache基金會下的Hadoop[5]是其中比較有代表性的分布式并行編程框架。近幾年隨著大數(shù)據(jù)的興起，MapReduce編程模型的研究[6]以及基于MapReduce的數(shù)據(jù)挖掘算法的實現(xiàn)[7]也愈加火熱。
1 相關(guān)概念
1.1 FP-growth算法簡介
    FP-growth算法是Han Jiawei等人于2000年提出的發(fā)現(xiàn)頻繁項集的算法，該算法采用分治策略將一個問題分解為較小的子問題，從而發(fā)現(xiàn)以某個特定后綴結(jié)尾的所有頻繁項集。該算法使用了一種稱之為頻繁模式樹FP-tree（Frequent Pattern Tree）的數(shù)據(jù)結(jié)構(gòu)，F(xiàn)P-tree是一種特殊的前綴樹，由頻繁項頭表和項前綴樹構(gòu)成。
    FP-growth算法發(fā)現(xiàn)頻繁項集的基本思想是：根據(jù)FP-tree構(gòu)造每個頻繁項的條件FP-tree，每個頻繁項都是一個前綴；每個前綴和其條件FP-tree的每一項合并生成一個新的前綴，根據(jù)此前綴繼續(xù)生成條件FP-tree，直到生成的條件FP-tree為空；每一個前綴都是頻繁的，即算法所得到的所有的前綴即為最終的頻繁項集。
    相比于Apriori算法,FP-growth算法有如下優(yōu)點：(1)將較大的數(shù)據(jù)庫壓縮成了較小的數(shù)據(jù)結(jié)構(gòu)保存在內(nèi)存中，從而避免了反復(fù)掃描數(shù)據(jù)庫，降低了掃描開銷；(2)基于FP-tree的挖掘采用遞歸的方式搜索較短的模式并將其逐次連接起來，從而避免生成大量的候選項集；(3)將原本的挖掘任務(wù)劃分成一組在有限的條件數(shù)據(jù)庫中挖掘特定的頻繁模式的任務(wù)，從而降低了搜索空間。
1.2 SON算法簡介
    Apriori算法通過迭代的方式來挖掘出所有的頻繁項集，即候選(k+1)-項集的產(chǎn)生依賴于頻繁k-項集，然后通過掃描事物數(shù)據(jù)集來計算出每一個候選(k+1)-項集支持度計數(shù)，進而判斷得到頻繁(k+1)-項集，因此該算法需要對事務(wù)數(shù)據(jù)集進行多次掃描。如果找到這樣一種方法，通過該方法得到的候選項集包含了該事務(wù)數(shù)據(jù)集中所有的頻繁項集，那么只需要對事物數(shù)據(jù)集掃描一遍即可找出所有的頻繁項集。
    以上為分區(qū)算法的核心思想。分區(qū)算法需要對事物數(shù)據(jù)集進行兩遍掃描，第一遍掃描找出候選項集，此候選項集包含所有的頻繁項集。第二遍掃描對所有的候選項集新型計數(shù)，其中大于最小支持度計數(shù)的候選項集即為頻繁項集。
    根據(jù)分區(qū)算法兩遍掃描的思想，算法的執(zhí)行分為兩個階段。在第一個階段，算法把事物數(shù)據(jù)集劃分為數(shù)個互不相交的分區(qū)，然后分別為每個分區(qū)計算出本分區(qū)的頻繁項集（稱之為局部頻繁項集，此項集是潛在的整個事務(wù)數(shù)據(jù)集的頻繁項集），最后把所有分區(qū)的頻繁項集匯聚到一起就得到了整個事務(wù)數(shù)據(jù)集的候選項集（稱之為全局候選項集）。在第二個階段，為上一個階段得到的全局候選項集進行計數(shù)，從而得到候選項集的支持度計數(shù)，其中大于最小支持度計數(shù)的候選項集即為全局頻繁項集。以下為SON算法的偽代碼，表1為偽代碼中所用的符號定義說明。

    偽代碼中首先將事務(wù)數(shù)據(jù)集D劃分為n個分區(qū)，階段1分別對每一個分區(qū)pi通過gen_large_itemsets方法計算其局部頻繁項集L′，該方法采用的是Apriori算法。在合并階段，算法將每個分區(qū)局部頻繁項集合并成一個全局候選項集CG。在階段2中，算法計算每個全局候選項集的支持度計數(shù)，其中大于最小支持度計數(shù)minSup的為最終的頻繁項集LG。
2 基于FP-growth的SON算法的并行化實現(xiàn)
    從SON算法的描述中可以看出，在算法第一階段中需要計算出局部頻繁項集，原始的SON算法采用Apriori算法來計算每個分區(qū)的頻繁項集，即同樣需要對每個分區(qū)掃描多次才能得到局部頻繁項集，所以SON算法是宏觀上對整個事務(wù)數(shù)據(jù)集掃描兩次，而從局部上來看仍然需要對每個分區(qū)分別掃描多次。本節(jié)提出的算法實現(xiàn)基于FP-growth，這將有效減少對分區(qū)的掃描次數(shù)。
    SON算法非常適合于并行計算環(huán)境，SON算法中的每一個分區(qū)都可以并行地處理。用MapReduce編程模型對基于FP-growth的SON算法進行并行化實現(xiàn)。算法的實現(xiàn)需要兩輪迭代，第一輪MapReduce迭代計算出每一個分區(qū)的局部頻繁項集并由此生成全局候選項集。第二輪MapReduce迭代計算出每一個全局候選項集的支持度計數(shù)，并根據(jù)支持度計數(shù)來判斷是否為頻繁項集。
2.1 第一輪MapReduce迭代
    在Map階段，每個Map任務(wù)完成從事務(wù)數(shù)據(jù)集的某一個分區(qū)中讀取到的事務(wù)，并將該分區(qū)中所有的事務(wù)存儲在本地內(nèi)存中，然后利用FP-growth算法算出本分區(qū)的局部頻繁項集，最后輸出的是一個鍵值對<F，1>(其中F是本分區(qū)的一個局部頻繁項集，1與鍵沒有任何關(guān)聯(lián))。
    class FirstMapper {
       List tSet; //事務(wù)數(shù)據(jù)集
       Map localFI; //局部頻繁項集
       map(key, value) {
        //將value封裝為事務(wù)
        t = genTransaction(value);
        //將事務(wù)添加到事務(wù)數(shù)據(jù)集中
        tSet.add(transaction);
       }
       cleanup() {
        //用FP-growth算法計算得到局部頻繁項集
        localFI = genFrequentItemsets(transaction);
        //將局部頻繁項集輸出
        for(i = 1; (fis = localFI.get(i)) != null; i++)
           for(f : fis)
            write(f, 1);
       }
    }
    在Reduce階段，每個Reduce任務(wù)會處理一組局部頻繁項集，上個階段所有的Map任務(wù)輸出的相同的局部頻繁項集會集中到同一個Reduce任務(wù)上進行處理，Reduce的任務(wù)就是將相同的局部頻繁項集輸出一次即可，最后的輸出結(jié)果即為全局的候選項集。

    class FirstReducer {
       reduce(key, values) {
        write(key, null);
       }
    }
2.2 第二輪MapReduce迭代
    在Map階段，每個Map任務(wù)仍然處理事務(wù)數(shù)據(jù)集上的一個分區(qū)，在Map任務(wù)開始前，把上一個MapReduce迭代產(chǎn)生的全局候選項集放入本地內(nèi)存中，Map任務(wù)開始后每讀入一個事務(wù)，找尋全局候選項集中哪些候選項集為此事務(wù)的子集，如果某候選項集為此事務(wù)子集，即輸出<F，1>(其中F為此候選項集，1代表為此事務(wù)的子集)，便于在下一階段計算此候選項集的支持度計數(shù)。
    class SecondMapper {
       List cI; //全局候選項集
       setup() {
        //初始化全局候選項集
        cI = getCandidateItemsets();
       }
       map(key, value) {
        t = genTransaction(value);
        //若候選項存在于某事務(wù)中就進行輸出
        for(f : cI)
           if(t.contain(f))
            write(f, 1);
       }
    }
    在Reduce階段，每個Reduce任務(wù)處理一組全局候選項集，上個階段所有的Map任務(wù)輸出的相同的候選項集會集中到同一個Reduce任務(wù)上進行處理，計算全局候選項集的支持度計數(shù)，根據(jù)其支持度計數(shù)即可判斷該項集是否為頻繁項集，Reduce任務(wù)會將得到的全局頻繁項集進行輸出。
    class SecondReducer {
       reduce(key, values) {
        sum = 0;
        for(val : values)
        sum += val.get();
        //若候選項大于最小支持度就輸出
        if(sum >= minsup)
        write(key, null);
       }
    }
3 實驗結(jié)果與實驗分析
3.1 實驗環(huán)境
    整個實驗在Hadoop平臺下完成，平臺采用了Hadoop的1.0.4穩(wěn)定版本。硬件設(shè)備為4臺x86架構(gòu)的PC，主設(shè)備節(jié)點采用Intel志強四核處理器，內(nèi)存為2 GB；從設(shè)備節(jié)點采用了AMD四核處理器，主頻為2.7 GHz，內(nèi)存為2 GB。
3.2 實驗數(shù)據(jù)集
    實驗采用accidents[8]作為實驗事務(wù)數(shù)據(jù)集，該數(shù)據(jù)集包含1991年～2000年Flanders地區(qū)的交通事故記錄。該數(shù)據(jù)集的大小為34 678 KB，共340 184條事務(wù)，有572個不同的項，平均每條事務(wù)包含45個項。
3.3 實驗分析
    為了對基于Apriori的并行SON算法和基于FP-growth的并行SON算法進行比較，首先用MapReduce模型分別實現(xiàn)兩個算法。發(fā)現(xiàn)兩個算法僅在階段1的局部頻繁項集處有異，在階段2沒有任何差別，所以實驗僅對兩個算法的階段1的運行進行比較。兩個算法分別在同等的集群條件和同樣的數(shù)據(jù)集下運行。由于分布式環(huán)境下的實驗結(jié)果具有一定的顛簸性，所有實驗的最終結(jié)果均為多次實驗后取得的合理值。
    圖1為accidents數(shù)據(jù)集在保持不變和劃分為2塊、4塊、8塊的情況下，兩種算法分別在第一輪迭代時消耗的總時間。從圖1可以看出，在算法采用相同的分區(qū)數(shù)目時，基于FP-growth的并行SON算法比基于Apriori的并行SON算法運行時間明顯減少。隨著數(shù)據(jù)集劃分的分區(qū)數(shù)目的增加，兩種算法運行的總時間將明顯減少。

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

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