周麗娟，王 翔

（首都師范大學(xué) 信息工程學(xué)院，北京100048）

0 引 言

在當(dāng)今數(shù)據(jù)爆炸的時(shí)代，傳統(tǒng)的關(guān)聯(lián)規(guī)則算法在處理海量數(shù)據(jù)時(shí)存在著單位時(shí)間內(nèi)處理量小、面對(duì)大量的數(shù)據(jù)時(shí)處理時(shí)間長、難以達(dá)到預(yù)期效果的缺陷。云計(jì)算融合了分布式計(jì)算、并行計(jì)算、負(fù)載均衡等傳統(tǒng)技術(shù)，通過使用大量的廉價(jià)計(jì)算機(jī)通過網(wǎng)絡(luò)互聯(lián)組成并行計(jì)算環(huán)境，代替了價(jià)格昂貴的高端服務(wù)器，大大降低了成本。將關(guān)聯(lián)規(guī)則算法跟云計(jì)算結(jié)合起來設(shè)計(jì)出高效的并行算法是一個(gè)不可避免的趨勢(shì)。FP－Growth算法是一個(gè)著名的關(guān)聯(lián)規(guī)則算法，該算法的最大優(yōu)點(diǎn)是只進(jìn)行兩次數(shù)據(jù)庫掃描。它不使用候選集，直接壓縮數(shù)據(jù)庫成一個(gè)頻繁模式樹，最后通過這個(gè)樹即FP－Tree生成關(guān)聯(lián)規(guī)則。然而FP－Growth算法的絕大部分時(shí)間消耗在FP－Tree及條件FP－Tree的構(gòu)造與遍歷上，這都影響了算法的時(shí)間及空間方面的效率。本文我們以經(jīng)典的FP－Growth 算法作為切入點(diǎn)，使用Hadoop 平臺(tái)的MapReduce編程模型實(shí)現(xiàn)并行的基于復(fù)合鏈表挖掘的FP－Growth算法，命名為PCL－FP，解決傳統(tǒng)FP－Growth算法的性能瓶頸問題，從大數(shù)據(jù)中快速并且高效地發(fā)現(xiàn)有用的知識(shí)。

1 相關(guān)概念與描述

1.1 FP－Growth算法

2000年，Han等提出了FP－Growth算法，該算法是一個(gè)很著名的高效算法。FP－Growth算法的基本思想是：通過第一次掃描事務(wù)數(shù)據(jù)庫，發(fā)現(xiàn)1頻繁項(xiàng)目集，然后構(gòu)造FP－Tree，基于FP－Tree發(fā)現(xiàn)條件模式基，挖掘頻繁模式。

根據(jù)事務(wù)數(shù)據(jù)庫構(gòu)造對(duì)應(yīng)的FP－Tree［1］：

（1）第一次掃描數(shù)據(jù)庫，獲得1－頻繁項(xiàng)目集L。

（2）創(chuàng)造樹的根結(jié)點(diǎn)，用 “root”標(biāo)記。第二次掃描數(shù)據(jù)庫，對(duì)每一個(gè)事務(wù)創(chuàng)建一個(gè)分支。

根據(jù)FP－Tree挖掘頻繁模式：

（1）對(duì)每一個(gè)項(xiàng)，生成它的條件模式基以及條件FPTree。

（2）對(duì)每一個(gè)新生成的條件FP－Tree，重復(fù)這個(gè)步驟。

（3）直到結(jié)果FP－Tree為空，或者只含唯一的一個(gè)路徑。

FP－Growth算法的時(shí)間主要消耗在FP－Tree及條件FPTree的構(gòu)造與遍歷上。有兩個(gè)問題：一是如果大項(xiàng)集的數(shù)量很多，并且如果得到的FP－Tree 的分枝很多，且分枝長度很長時(shí)，該算法需要構(gòu)造出龐大的FP－Tree；二是在每一次遞歸挖掘時(shí)，算法都要生成一棵新的條件FP－Tree。時(shí)間效率、空間效率都會(huì)變得很低，甚至?xí)诰蚴。?］。PCLFP算法是在云計(jì)算環(huán)境下基于復(fù)合鏈表的并行算法，該算法很好地解決了傳統(tǒng)FP－Growth算法的性能瓶頸。用復(fù)合鏈表代替了FP－Tree，節(jié)省了時(shí)間和空間。同時(shí)基于MapReduce編程模型將大數(shù)據(jù)集分布到各個(gè)計(jì)算節(jié)點(diǎn)上，每個(gè)計(jì)算節(jié)點(diǎn)構(gòu)造的復(fù)合鏈表不會(huì)很大，降低了對(duì)計(jì)算機(jī)硬件的要求。

1.2 構(gòu)建云平臺(tái)

本文構(gòu)建了一個(gè)云平臺(tái)來實(shí)現(xiàn)PCL－FP算法。Hadoop能夠充分利用集群的計(jì)算能力高速的計(jì)算以及存儲(chǔ)任務(wù)。Hadoop的文件系統(tǒng)針對(duì)數(shù)據(jù)塊維護(hù)多個(gè)副本，確保機(jī)器節(jié)點(diǎn)故障后數(shù)據(jù)不丟失，保證了數(shù)據(jù)的完整性，同時(shí)該數(shù)據(jù)塊被復(fù)制到另外一臺(tái)正常的機(jī)器節(jié)點(diǎn)上繼續(xù)運(yùn)行，具有很高的可靠性；Hadoop的MapReduce框架，并行處理數(shù)據(jù)，具有很高的效率；Hadoop可以處理PB 級(jí)別的數(shù)據(jù)，具有很好的可伸縮性。因此Hadoop適合作為該算法的云平臺(tái)。

Hadoop組件結(jié)構(gòu)圖如圖1 所示，在架構(gòu)中，Hadoop Common 提供了支持Hadoop 子項(xiàng)目的通用功能塊，MapReduce組件提供Map和Reduce處理，HDFS實(shí)現(xiàn)了文件的分布式存儲(chǔ)機(jī)制，ZooKeeper提供分布式鎖之類的基本服務(wù)，用于構(gòu)建分布式應(yīng)用［3］。Hadoop 的最核心設(shè)計(jì)是Hadoop的分布 式文件 系 統(tǒng) 和MapReduce 計(jì) 算 模 型［4］，HDFS是Hadoop分布式文件系統(tǒng)的一個(gè)實(shí)現(xiàn)，為分布式計(jì)算存儲(chǔ)提供了底層支持。

圖1 Hadoop組件結(jié)構(gòu)

MapReduce是一種用于并行處理數(shù)據(jù)的編程模型。它簡化編程模型，降低了開發(fā)并行應(yīng)用的難度。MapReduce是一種高效的分布式編程模型。它將計(jì)算過程分解為兩個(gè)階段：Map和Reduce，每個(gè)階段的輸入都是一系列的鍵值對(duì) （key／value），每個(gè)階段的輸出也是一系列的鍵值對(duì)［5］。

2 PCL－FP的主要思想

本文提出了一個(gè)并行的基于復(fù)合鏈表挖掘的FPGrowth算法［6］，命名為PCL－FP算法?；趶?fù)合鏈表挖掘代替了傳統(tǒng)的FP－Tree以及每次遞歸過程中構(gòu)建的條件FPTree，節(jié)省了時(shí)間和空間，算法的主要思想如下。

2.1 統(tǒng)計(jì)項(xiàng)的數(shù)目

表1是一個(gè)簡單的事務(wù)數(shù)據(jù)庫樣例。InputFormat將數(shù)據(jù)分成連續(xù)的幾個(gè)部分。每一部分為一個(gè)數(shù)據(jù)分片，將數(shù)據(jù)分片存儲(chǔ)在各個(gè)計(jì)算機(jī)節(jié)點(diǎn)上，接著每個(gè)結(jié)點(diǎn)執(zhí)行MapReduce統(tǒng)計(jì)函數(shù)，統(tǒng)計(jì)各個(gè)項(xiàng)目的個(gè)數(shù)存儲(chǔ)到FP－List中。如圖2所示，已有的數(shù)據(jù)集平均分配給3個(gè)Mapper，每個(gè)Mapper的任務(wù)是負(fù)責(zé)統(tǒng)計(jì)該Mapper的數(shù)據(jù)分片中各個(gè)項(xiàng)的數(shù)目，每個(gè)Mapper輸出的中間結(jié)果經(jīng)過Combiner中間函數(shù)將輸出數(shù)據(jù)進(jìn)行合并，以減少M(fèi)ap任務(wù)和Reduce任務(wù)之間的數(shù)據(jù)傳輸。輸出數(shù)據(jù)再經(jīng)過MapReduce框架處理之后，最后發(fā)送到Reduce函數(shù)，得到最終結(jié)果，統(tǒng)計(jì)出數(shù)據(jù)庫中每個(gè)項(xiàng)的數(shù)目，將大于等于最小支持度的項(xiàng)存入F－List中 （支持度取3），F(xiàn)－List＝｛I4：7，I1：5，I6：5，I7：4，I2：3，I3：3，I5：3｝，即F－List中存的是最大頻繁項(xiàng)目集。

表1 事務(wù)數(shù)據(jù)庫

圖2 分布式統(tǒng)計(jì)項(xiàng)的數(shù)目

集群上的可用帶寬限制了MapReduce作業(yè)的數(shù)量，因此最重要的一點(diǎn)是盡量避免Map任務(wù)和Reduce任務(wù)之間的數(shù)據(jù)傳輸。Hadoop允許用戶針對(duì)Map任務(wù)的輸出指定一個(gè)合并函數(shù)Combiner，它的輸出作為Reduce的輸入。合并函數(shù)是一個(gè)優(yōu)化方案，程序運(yùn)行過程中不管調(diào)用了多少次Combiner函數(shù)，最終的輸出結(jié)果是一致的［7］。

偽代碼如下：

按照各項(xiàng)頻度大小對(duì)事務(wù)數(shù)據(jù)庫進(jìn)行排序，排序之后的結(jié)果見表2。

表2 排序事務(wù)數(shù)據(jù)庫

2.2 基于復(fù)合鏈表挖掘

本文使用復(fù)合鏈表代替FP－Tree以及條件FP－Tree來記錄事務(wù)記錄中各項(xiàng)之間的關(guān)系。很大程度上節(jié)省了時(shí)間以及空間［8］。復(fù)合鏈表結(jié)構(gòu)如下：

我們?nèi)砸员? 中的數(shù)據(jù)作為例子。header＿table中存放的是F－List中按照支持度降序排列的各項(xiàng)以及各項(xiàng)的支持度。均衡任務(wù)拆分［9，10］，Mapper1獲得分片1，分片1中包含事務(wù)記錄Tid1，Tid2，Tid4；Mapper2獲得分片2，分片2中包含Tid3，Tid7，Tid8，Tid9；Mapper3 獲得分片3，分片3包含剩下的事務(wù)記錄Tid5，Tid6。

Mapper中Tid1包含項(xiàng)I4，I6，I7，逆序?yàn)镮7，I6，I4。我們把I6，I4依次插入到head＿table中I7的itemList中，把I4插入到head＿table中I6 的itemList鏈表中，同時(shí)記錄各項(xiàng)的數(shù)目。同理Tid4 包含項(xiàng)I4I1I6I2，逆序?yàn)镮2，I6，I1，I4，將I6，I1，I4 依次插入到header＿table中I2的itemList鏈表中，將I1，I4依次插入到header＿table中I6的itemList鏈表中，此時(shí)注意itemList中各項(xiàng)按照F－List中支持度升序排列，所以I1在I4前面，I4數(shù)目此時(shí)為2，依次類推，再將I4 插入到header＿table中I1 的itemList中。按照相同的原理操作，Mapper1最終的復(fù)合鏈表如圖3所示［11］。

圖3 Mapper1復(fù)合鏈表

按照相同的原理，Mapper2 以及Mapper3 的復(fù)合鏈表分別如圖4，圖5所示。

圖4 Mapper2復(fù)合鏈表

在Reduce階段，將每一個(gè)Mapper的復(fù)合鏈表合并成一個(gè)復(fù)合鏈表，Reduce最終的復(fù)合鏈表如圖6所示。

在該復(fù)合鏈表上進(jìn)行遍歷，最終得到的頻繁模式見表3，各個(gè)頻繁模式按照支持度降序排列。

表3 挖掘結(jié)果

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

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

本文所有的實(shí)驗(yàn)都是在實(shí)驗(yàn)室搭建的Hadoop平臺(tái)上運(yùn)行的。平臺(tái)有5 臺(tái)機(jī)器，5 臺(tái)機(jī)器都是四核Intel Corei3處理器，8G 內(nèi)存，硬件配置完全相同。各個(gè)結(jié)點(diǎn)運(yùn)行Ubuntu Linux 操作系統(tǒng)。Hadoo版本是0.20.2，java版本是1.6.25，每臺(tái)機(jī)器之間用千兆以太網(wǎng)卡通過交換機(jī)連接。

3.2 實(shí)驗(yàn)數(shù)據(jù)和結(jié)果

實(shí)驗(yàn)數(shù)據(jù)來自實(shí)驗(yàn)室糧棉倉儲(chǔ)項(xiàng)目。為了測(cè)試算法的性能，實(shí)驗(yàn)分別用含有100000、500000、1000000 條記錄的數(shù)據(jù)來進(jìn)行測(cè)試。實(shí)驗(yàn)結(jié)果如表4和圖7所示。圖7中橫坐標(biāo)為數(shù)據(jù)量，縱坐標(biāo)為運(yùn)行時(shí)間，從圖7可以更直觀的看出PCL－FP算法在處理大規(guī)模的數(shù)據(jù)集時(shí)運(yùn)行效率要遠(yuǎn)高于傳統(tǒng)的FP－Growth算法。

表4 算法運(yùn)行時(shí)間

圖7 算法運(yùn)行時(shí)間比較

圖8中橫坐標(biāo)為節(jié)點(diǎn)數(shù)，縱坐標(biāo)為運(yùn)行時(shí)間，圖例項(xiàng)為數(shù)據(jù)量，從圖8中可以看出，隨著集群中節(jié)點(diǎn)數(shù)的增多，算法的效率也就增高，由此也驗(yàn)證了PCL－FP 算法具有良好的伸縮性和擴(kuò)展性，可以有效地用于大規(guī)模數(shù)據(jù)的分析挖掘。

圖8 算法運(yùn)行時(shí)間比較

4 結(jié)束語

本文提出了一種云環(huán)境下并行的基于復(fù)合鏈表挖掘的FP－Growth算法，即PCL－FP 算法。該算法搭建云平臺(tái)，利用云計(jì)算處理大數(shù)據(jù)，同時(shí)基于復(fù)合鏈表挖掘頻繁模式代替構(gòu)建FP－Tree以及條件FP－Tree。實(shí)驗(yàn)結(jié)果表明改進(jìn)的算法較之傳統(tǒng)的FP－Growth算法有更高的效率以及更好的擴(kuò)展性，解決了傳統(tǒng)算法的性能瓶頸。下一步將著重研究重寫Hadoop InputFormat類中的getSplits方法，合理切分?jǐn)?shù)據(jù)分片，均衡分配任務(wù)，進(jìn)一步提高算法效率。

［1］MAO Guojun，DUAN Lijuan，WANG Shi，et al.Data mining principles and algorithms［M］.2nd ed.Beijing：Tsinghua University Press，2007：82－85 （in Chinese）. ［毛國軍，段立娟，王實(shí)，等.數(shù)據(jù)挖掘原理與算法 ［M］.2版.北京：清華大學(xué)出版社，2007：82－85.］

［2］Totad S G，Geeta r B，ReddY P.Batch incremental processing for FP－tree construction using FP－Growth algorithm ［J］.Knowledge and Information Systems，2012，33 （2）：475－490.

［3］ZHAO Shulan.Typical Hadoop cloud computing［M］.Beijing：Electronic Industry Press，2013：13－18 （in Chinese）.［趙 書蘭.典型Hadoop 云計(jì)算 ［M］.北京：電子工業(yè)出版社，2013：13－18.］

［4］Dean J，Ghemawat S.Mapreduce：Simplified data processing on large clusters ［J］.Communications of The ACM，2008，51（1）：107－113.

［5］WANG Zhengkui，AGRAWAL D，TAN K L.COSAC：A framework for combinatorial statistical analysis on cloud ［J］. IEEE Transactions on Knowledge and Data Engineering，2012，25 （9）：2010－2023.

［6］Jin Hui，Sun Xianhe.Performance comparison under failures of MPI and MapReduce：An analytical approach ［J］.Future Generation Computer Systems－The International Journal of Grid Computing and Escience，2013，29 （7）：1808－1815.

［7］White T.Hadoop：The definitive guide［M］.2nd ed.Beijing：Tsinghua University Press，2011：28－32 （in Chinese）.［懷特.Hadoop 權(quán)威指南 ［M］.北京：清華大學(xué)出版社，2011：28－32.］

［8］LI Haoyuan，WANG Yi，ZHANG Dong，et al.Pfp：Parallel fp－growth for query recommendation ［C］／／Proc of the ACM Conference on Recommender Systems，2008：107－114.

［9］Vianna E，Comarela G，Pontes T，et al.Analytical performance modelsfor mapreduce workloads ［J］.International Journal of Parallel Programming，2013，41 （4）：495－525.

［10］Brauckhoff D，Dimitropoulos X，Wagner A，et al.Anomaly extraction in backbone networks using association rules ［J］.IEEE－ACM Transactions on Networking，2012，20 （6）：1788－1799.

［11］JIAO Minghai，JIANG Huiyan，TANG Jiafu.An improved FP－growth algorithm based on polymer chains［J］.Journal of Northeastern University，2006，27 （2）：153－156 （in Chinese）.［焦明海，姜慧研，唐加福.一種基于聚合鏈的改進(jìn)FP－Growth算法 ［J］.東北大學(xué)學(xué)報(bào)，2006，27 （2）：153－156.