云環(huán)境下關(guān)聯(lián)規(guī)則算法的研究

周麗娟，王 翔

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

0 引 言

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

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

1.1 FP－Growth算法

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

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

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

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

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

（1）對每一個項，生成它的條件模式基以及條件FPTree。

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

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

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

1.2 構(gòu)建云平臺

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

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

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

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

2 PCL－FP的主要思想

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

2.1 統(tǒng)計項的數(shù)目

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

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

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

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

偽代碼如下：

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

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

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

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

我們?nèi)砸员? 中的數(shù)據(jù)作為例子。header＿table中存放的是F－List中按照支持度降序排列的各項以及各項的支持度。均衡任務(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包含項I4，I6，I7，逆序為I7，I6，I4。我們把I6，I4依次插入到head＿table中I7的itemList中，把I4插入到head＿table中I6 的itemList鏈表中，同時記錄各項的數(shù)目。同理Tid4 包含項I4I1I6I2，逆序為I2，I6，I1，I4，將I6，I1，I4 依次插入到header＿table中I2的itemList鏈表中，將I1，I4依次插入到header＿table中I6的itemList鏈表中，此時注意itemList中各項按照F－List中支持度升序排列，所以I1在I4前面，I4數(shù)目此時為2，依次類推，再將I4 插入到header＿table中I1 的itemList中。按照相同的原理操作，Mapper1最終的復(fù)合鏈表如圖3所示［11］。

圖3 Mapper1復(fù)合鏈表

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

圖4 Mapper2復(fù)合鏈表

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

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

表3 挖掘結(jié)果

3 實驗及結(jié)果分析

3.1 實驗環(huán)境

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

3.2 實驗數(shù)據(jù)和結(jié)果

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

表4 算法運行時間

圖7 算法運行時間比較

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

圖8 算法運行時間比較

4 結(jié)束語

本文提出了一種云環(huán)境下并行的基于復(fù)合鏈表挖掘的FP－Growth算法，即PCL－FP 算法。該算法搭建云平臺，利用云計算處理大數(shù)據(jù)，同時基于復(fù)合鏈表挖掘頻繁模式代替構(gòu)建FP－Tree以及條件FP－Tree。實驗結(jié)果表明改進(jìn)的算法較之傳統(tǒng)的FP－Growth算法有更高的效率以及更好的擴展性，解決了傳統(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ù)據(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 云計算 ［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é)報，2006，27 （2）：153－156.