摘  要： 單節(jié)點運行的傳統(tǒng)SON算法能夠有效降低CPU和I/O負載，而且算法僅需要對整個事務數(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]是挖掘頻繁項集最為著名的算法,，但其串行計算的復雜度較高,。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)存中，從而避免了反復掃描數(shù)據(jù)庫,，降低了掃描開銷,；(2)基于FP-tree的挖掘采用遞歸的方式搜索較短的模式并將其逐次連接起來，從而避免生成大量的候選項集,；(3)將原本的挖掘任務劃分成一組在有限的條件數(shù)據(jù)庫中挖掘特定的頻繁模式的任務,，從而降低了搜索空間。
1.2 SON算法簡介
    Apriori算法通過迭代的方式來挖掘出所有的頻繁項集,，即候選(k+1)-項集的產(chǎn)生依賴于頻繁k-項集,，然后通過掃描事物數(shù)據(jù)集來計算出每一個候選(k+1)-項集支持度計數(shù)，進而判斷得到頻繁(k+1)-項集,，因此該算法需要對事務數(shù)據(jù)集進行多次掃描,。如果找到這樣一種方法，通過該方法得到的候選項集包含了該事務數(shù)據(jù)集中所有的頻繁項集，那么只需要對事物數(shù)據(jù)集掃描一遍即可找出所有的頻繁項集,。
    以上為分區(qū)算法的核心思想,。分區(qū)算法需要對事物數(shù)據(jù)集進行兩遍掃描，第一遍掃描找出候選項集,，此候選項集包含所有的頻繁項集,。第二遍掃描對所有的候選項集新型計數(shù)，其中大于最小支持度計數(shù)的候選項集即為頻繁項集,。
    根據(jù)分區(qū)算法兩遍掃描的思想,，算法的執(zhí)行分為兩個階段。在第一個階段,，算法把事物數(shù)據(jù)集劃分為數(shù)個互不相交的分區(qū),，然后分別為每個分區(qū)計算出本分區(qū)的頻繁項集（稱之為局部頻繁項集，此項集是潛在的整個事務數(shù)據(jù)集的頻繁項集）,，最后把所有分區(qū)的頻繁項集匯聚到一起就得到了整個事務數(shù)據(jù)集的候選項集（稱之為全局候選項集）,。在第二個階段，為上一個階段得到的全局候選項集進行計數(shù),，從而得到候選項集的支持度計數(shù),，其中大于最小支持度計數(shù)的候選項集即為全局頻繁項集。以下為SON算法的偽代碼,，表1為偽代碼中所用的符號定義說明,。

    偽代碼中首先將事務數(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算法是宏觀上對整個事務數(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任務完成從事務數(shù)據(jù)集的某一個分區(qū)中讀取到的事務,，并將該分區(qū)中所有的事務存儲在本地內(nèi)存中，然后利用FP-growth算法算出本分區(qū)的局部頻繁項集,，最后輸出的是一個鍵值對<F,，1>(其中F是本分區(qū)的一個局部頻繁項集，1與鍵沒有任何關(guān)聯(lián)),。
    class FirstMapper {
       List tSet; //事務數(shù)據(jù)集
       Map localFI; //局部頻繁項集
       map(key, value) {
        //將value封裝為事務
        t = genTransaction(value);
        //將事務添加到事務數(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任務會處理一組局部頻繁項集，上個階段所有的Map任務輸出的相同的局部頻繁項集會集中到同一個Reduce任務上進行處理,，Reduce的任務就是將相同的局部頻繁項集輸出一次即可,，最后的輸出結(jié)果即為全局的候選項集。

    class FirstReducer {
       reduce(key, values) {
        write(key, null);
       }
    }
2.2 第二輪MapReduce迭代
    在Map階段,，每個Map任務仍然處理事務數(shù)據(jù)集上的一個分區(qū)，在Map任務開始前,，把上一個MapReduce迭代產(chǎn)生的全局候選項集放入本地內(nèi)存中,，Map任務開始后每讀入一個事務，找尋全局候選項集中哪些候選項集為此事務的子集,，如果某候選項集為此事務子集,，即輸出<F，1>(其中F為此候選項集,，1代表為此事務的子集),，便于在下一階段計算此候選項集的支持度計數(shù)。
    class SecondMapper {
       List cI; //全局候選項集
       setup() {
        //初始化全局候選項集
        cI = getCandidateItemsets();
       }
       map(key, value) {
        t = genTransaction(value);
        //若候選項存在于某事務中就進行輸出
        for(f : cI)
           if(t.contain(f))
            write(f, 1);
       }
    }
    在Reduce階段,，每個Reduce任務處理一組全局候選項集,，上個階段所有的Map任務輸出的相同的候選項集會集中到同一個Reduce任務上進行處理，計算全局候選項集的支持度計數(shù),，根據(jù)其支持度計數(shù)即可判斷該項集是否為頻繁項集,，Reduce任務會將得到的全局頻繁項集進行輸出。
    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)定版本,。硬件設備為4臺x86架構(gòu)的PC，主設備節(jié)點采用Intel志強四核處理器,，內(nèi)存為2 GB,；從設備節(jié)點采用了AMD四核處理器,，主頻為2.7 GHz，內(nèi)存為2 GB,。
3.2 實驗數(shù)據(jù)集
    實驗采用accidents[8]作為實驗事務數(shù)據(jù)集,，該數(shù)據(jù)集包含1991年～2000年Flanders地區(qū)的交通事故記錄。該數(shù)據(jù)集的大小為34 678 KB,，共340 184條事務,，有572個不同的項，平均每條事務包含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算法雖然從宏觀上對事務數(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)系,，這導致了隨著分區(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].電子學報，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.