施 亮，錢雪忠

（江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫214122）

0 引 言

本文結(jié)合MapReduce［1］云計算編程模型提出一種基于MapReduce的約束頻繁項集挖掘算法DCFIBMR （discover constrained frequent itemsets based on MapReduce）。該算法可以將一個完整的挖掘任務(wù)分成若干個相對獨立的子任務(wù)，然后通過Hadoop［2］框架的MapReduce并行編程模型實現(xiàn)FP－Growth算法的并行化，其原理是DCFIBMR 算法將一個挖掘任務(wù)分成若干個相對獨立的子任務(wù)，然后利用Hadoop框架將子任務(wù)分發(fā)給各個子節(jié)點進(jìn)行處理，該算法在數(shù)千機(jī)器組成的集群中處理數(shù)據(jù)挖掘，因此DCFIBMR 算法可以有效地處理海量的數(shù)據(jù)挖掘任務(wù)。

1 相關(guān)概念

1.1 約束頻繁項

本文中討論的約束是有項約束，即挖掘包含某些項目（或同時包含幾個項目）的頻繁項目集合，設(shè)布爾表達(dá)式B是I上的項約束條件，將B 轉(zhuǎn)換為析取范式 （disjunctive normal form，DNF）的形式，如：B1∨B2∨B3…∨Bn，如果把B寫成集合的形式，形如：set－of－B＝ ｛B1，B2，B3…Bn｝，其中集合B中的任意兩個組成元素均不相等［3］。

1.2 FP－tree的構(gòu)建

在FP－tree［4］中每個節(jié)點包含有5個屬性：該節(jié)點的名稱 （NodeName），該節(jié)點在數(shù)據(jù)庫中出現(xiàn)的次數(shù) （Node－Count），指向下一個同名節(jié)點的指針 （NodeSlider），指向該節(jié)點的父節(jié)點的指針 （ParentNode）及該節(jié)點的子節(jié)點所構(gòu)成的節(jié)點集合 （ChildrenNode）。而該頻繁項按計數(shù)降序排列組成的頭表集合 （HTable）中，每個元素包含3個子對象：頻繁項名稱ItemName，頻繁項計數(shù)ItemCount及指向FP－tree中同名節(jié)點的指針I(yè)temHead。FP－tree［5］的構(gòu)造過程如下：

（1）掃描一次事務(wù)數(shù)據(jù)庫DB，構(gòu)造頻繁項和其支持?jǐn)?shù)組成集合L，將集合L 中不滿足最小支持度的頻繁項刪除并按支持?jǐn)?shù)降序排列，生成支持?jǐn)?shù)降序排列的頻繁項集合F。

（2）構(gòu)造FP－tree樹的根節(jié)點T，并標(biāo)記為 “NULL”，再次掃描事務(wù)數(shù)據(jù)庫DB，遍歷每條事務(wù)Trans，并執(zhí)行如下過程：

1）根據(jù)頻繁項集在F中的順序，對事務(wù)Trans中頻繁項按其支持?jǐn)?shù)降序排列，構(gòu)造 ［p｜P］結(jié)構(gòu)，其中p是事務(wù)Trans中第一個項，P是剩余項。

2）調(diào)用insert＿tree（［p｜P，T］）函數(shù)，該函數(shù)執(zhí)行過程如下：

如果T 存在一個子節(jié)點N，并滿足N.NodeName，＝p.NodeName，那么使節(jié)點N 的計數(shù)NodeCount加1；否則，創(chuàng)建一個新的子節(jié)點N，并且設(shè)置節(jié)點N.NodeName＝p.NodeName、N.NodeCount＝1、p.ParentNode＝T。如果P非空，遞歸調(diào)用insert＿tree（P，N）。

1.3 MapReduce編程模型

MapReduce是Apache下開源云計算框架Hadoop中一種并行計算編程模型，利用MapReduce編程模型Hadoop可以并行處理數(shù)據(jù)量巨大的任務(wù)，該框架可以極大的簡化分布式任務(wù)的處理。而MapReduce編程模型主要有Map和Reduce兩個部分組成，其主要原理是利用一個輸入鍵值對集合，通過處理產(chǎn)生一個輸出鍵值對集合［6］。

用戶需要重寫兩個函數(shù)：mapper和reducer，MapReduce首先將數(shù)據(jù)分片輸入到mapper函數(shù)中，根據(jù)指定的處理過程產(chǎn)生鍵值對集合并將相同鍵的鍵值對輸出給同一個reducer函數(shù)進(jìn)行處理，reducer函數(shù)根據(jù)用戶的自定義的處理流程處理后將結(jié)果輸出［7］。

2 約束頻繁項集挖掘DCFIBMR算法

給定一個事務(wù)數(shù)據(jù)庫、最小支持度及約束規(guī)則B，DCFIBMR 算法需要執(zhí)行兩次MapReduce過程。

2.1 第一次MapReduce過程

使用一個MapReduce任務(wù)來統(tǒng)計整個事務(wù)數(shù)據(jù)庫中的頻繁項的支持?jǐn)?shù)。每個mapper實例處理一個事務(wù)數(shù)據(jù)庫的數(shù)據(jù)塊。mapper實例接收的數(shù)據(jù)是一種鍵值對的形式，如＜key，value＝Ti＞，其中Ti是事務(wù)數(shù)據(jù)庫 （DB）中的每條記錄，對于每個頻繁項，mapperper實例將處理好的數(shù)據(jù)以一種鍵值對的形式輸出，如＜key’＝aj，value’＝1＞。對于每個mapperper實例的輸出，用一個對應(yīng)的combiner實例進(jìn)行局部的整合，將相同鍵的值進(jìn)行求和，通過此步可有效地減少節(jié)點之間的數(shù)據(jù)通信量。

在所有的mapperper實例執(zhí)行完畢后，Hadoop框架會將具有相同鍵的鍵值對分發(fā)給同一個reducer實例進(jìn)行處理，reducer實例對具有相同鍵 （key’）的值進(jìn)行求和運算，處理結(jié)束后同樣以鍵值對的形式輸出，如＜key’，sum（values’）＞［8］。該階段處理完成后可獲得一個由頻繁項及按支持度降序排列的列表，F(xiàn)。

2.2 第二次MapReduce過程

首先，在Map階段，事務(wù)數(shù)據(jù)庫中的數(shù)據(jù)被處理成組內(nèi)依賴的數(shù)據(jù)塊。然后在Reduce階段每個reducer實例根據(jù)獲取到的數(shù)據(jù)塊構(gòu)建子頻繁模式樹 （SubFP－tree），并在構(gòu)建的子頻繁模式樹上遞歸進(jìn)行頻繁模式的挖掘任務(wù)。在mapper實例的開始階段，它會加載第一次MapReduce過程生成的F［9］。在本文的實現(xiàn)中，F(xiàn)被構(gòu)建成一個Hash映射表，將其包含的每一項映射到相應(yīng)的組的編號（group－id）上。

（1）mapper的輸入?yún)?shù)是事務(wù)數(shù)據(jù)庫中的數(shù)據(jù)切片，每個數(shù)據(jù)切片以鍵值對，如＜key，Value＝Ti＞，的形式傳遞。對于每個Ti，mapper將會按照如下步驟進(jìn)行：

1）按照F中頻繁項的順序?qū)i進(jìn)行降序排列；

2）對于Ti中的每一項i，定位該項左邊的項集，記錄為L；

3）輸出一個鍵值對，形如＜key’＝group－id，value＝｛Ti［1］，Ti［2］，…Ti［L－1］，Ti［L］｝，其中g(shù)roup－id為i在F中的下坐標(biāo)。

（2）reducer實例開始執(zhí)行時同樣會加載F。在這個階段，reducer實例會接受＜key’，Value＝DB （group－id）＞鍵值對，DB （group－id）包含了同一組內(nèi)的所有事務(wù)數(shù)據(jù)塊［10］。針對DB （group－id），reducer實例會遞歸地構(gòu)建和挖掘子頻繁模式樹 （SubFP－tree）。詳細(xì)描述如下：

1）首先設(shè)置前綴項prefix＝F［group－id］；

2）掃描一次DB（group－id），產(chǎn)生由頻繁項按支持?jǐn)?shù)降序排列的頭表subHTable；

3）再次掃描DB（group－id）構(gòu)建局部子頻繁模式樹subFPtree；

4）判斷由prefix和subHTable中的各個頻繁項構(gòu)成的項集是否滿足約束規(guī)則B，如果滿足則輸出該頻繁項；

5）遍歷subHTable集合，對于集合中的每個頻繁項p，從subFPtree中找到含有p的路徑，并構(gòu)造p的條件模式基集合。然后將prefix＝prefix＋p.NodeName，p的條件模式基集合，約束規(guī)則B 及F 作為輸入?yún)?shù)從步驟2）開始迭代執(zhí)行。

算法的具體執(zhí)行過程如下：

輸入：事務(wù)數(shù)據(jù)庫DB，最小支持度minsup，約束規(guī)則B；

第一次MapReduce：

第二次MapReduce：

3 DCFIBMR 算法實例講解

為了對DCFIBMR 算法的詳細(xì)挖掘流程進(jìn)行講解，設(shè)事務(wù)數(shù)據(jù)庫DB，其數(shù)據(jù)見表1，約束規(guī)則為B＝（f∧c∧p）∨ （b∧i）及最小支持度為30%，從該事物數(shù)據(jù)庫DB中挖掘出滿足約束條件B的所有頻繁項目集合。

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

首先，執(zhí)行一次MapReduce統(tǒng)計事務(wù)數(shù)據(jù)庫中的所有頻繁項及其出現(xiàn)的次數(shù)，產(chǎn)生形如L＝ ［｛f：5｝，｛c：5｝，｛p：5｝，｛m：5｝，｛b：4｝，｛a：4｝，｛n：3｝，｛h：2｝，｛i：3｝， ｛l：4｝， ｛g：1｝］，從中剔除支持?jǐn)?shù)小于1.8 （6×30%）的頻繁項，可以看出g出現(xiàn)次數(shù)小于1.8，將其從L中刪除。然后對L按照支持?jǐn)?shù)降序排列，組成F集合，F(xiàn)＝［f，c，p，m，b，a，l，n，i，h］。

再執(zhí)行一次MapReduce，在本次執(zhí)行中將事務(wù)數(shù)據(jù)庫D，約束規(guī)則B，最小支持度30%及F集合作為輸入，通過相關(guān)的挖掘處理，輸出滿足要求的頻繁項集合。

Map階段：

本階段主要是對事務(wù)數(shù)據(jù)庫D 的分組及數(shù)據(jù)的分發(fā)，以便于后續(xù)的并行計算。以D 中第一行Tid－1為例，首先對Tid－1中的項集按照頻繁項在F中的位置進(jìn)行降序排序，并刪除F中沒有的項集，得到T＝｛f，c，p，m，a，i｝。然后對T 進(jìn)行分組，形式如：｛｛f，c，p，m，a｝｜i｝、｛｛f，c，p，m｝｜a｝、｛｛f，c，p｝｜m｝、｛｛f，c｝｜p｝、｛｛f｝｜c｝。在F中i的下標(biāo)為8，則將 ｛｛f，c，p，m，a｝｜i｝放入第8組中，并輸出：output＜8， ｛f，c，p，m，a｝＞的鍵值對，其中8為組編號，｛f，c，p，m，a｝為i的條件模式基，其余幾項的分組同理i。

Reduce階段：

在Map階段，事務(wù)數(shù)據(jù)庫被進(jìn)行了分組及輸出，而在Reduce階段，會接收到被分到同一組內(nèi)的數(shù)據(jù)集合，形如＜group－id，Values＞，其中g(shù)roup－id為組的編號，Values為同一組內(nèi)的數(shù)據(jù)集合；以頻繁項i為例，將會獲取到group－id＝8，Values＝ （｛f，c，p，m，a｝，｛f，p，b，n｝，｛f，c，m，b，l，n｝）。設(shè)定DB （8）＝ ［｛f，c，p，m，a｝，｛f，p，b，n｝，｛f，c，m，b，l，n｝］。那么基于該局部數(shù)據(jù)庫構(gòu)建subFPtree，可構(gòu)建出如圖1 所示的頭表subHTable及子頻繁模式樹subFPtree。

設(shè)置前綴項prefix＝F ［8］＝i，并判斷由subHTable中的各個頻繁項和prefix 組成的項集pattern＝ ｛｛i，f｝，｛i，c｝，｛i，p｝，｛i，m｝，｛i，b｝，｛i，n｝｝是否滿足約束規(guī)則B，從中可以看到頻繁集 ｛i，b｝滿足要求。因此將｛i，b｝輸出。

圖1 頭表及子頻繁模式樹

然后遍歷subHTable，在本例中對于頻繁項n，從sub－FPtree中可以找到以n為前綴的條件模式基集合cbase－n＝｛｛f，c，m，b｝，｛f，p，b｝｝，然后設(shè)置prefix＝prefix＋n，在集合cbase－n上建立頭表及頻繁模式樹，挖掘過程同理i。最終，通過上述執(zhí)行步驟可挖掘出滿足約束規(guī)則B 的所有頻繁項集。

4 算法性能比較與分析

Direct＊算法［11］是一種串行的基于頻繁模式樹的約束頻繁項集挖掘算法，在本次實驗中將DCFIBMR 算法與Direct＊算法進(jìn)行比較，可以得出如下結(jié)論：

（1）Direct＊算法主要是基于Apriori思想，即不斷地由頻繁K 項集產(chǎn)生K＋1候選項集，因此在算法執(zhí)行期間會產(chǎn)生大量的候選項集，并需要多次掃描數(shù)據(jù)庫［11］，而DCFIBMR 算法在執(zhí)行過程中僅需要掃描兩次數(shù)據(jù)庫，因此算法的執(zhí)行效率有顯著的提升。

（2）Direct＊算法是一種典型的單任務(wù)執(zhí)行的算法，即一次只能執(zhí)行一個任務(wù)，因此在處理海量數(shù)據(jù)挖掘任務(wù)時，用戶需要等待很長時間才會看到結(jié)果，而DCFIBMR 算法的主要優(yōu)勢在于可以將一個任務(wù)分成多個相對獨立的子任務(wù)在多臺計算機(jī)中進(jìn)行處理，因此可顯著降低用戶等待的時間。

為了進(jìn)一步驗證本文算法的有效性，實驗設(shè)計如下：

實驗環(huán)境是4臺機(jī)器組成的集群，其中一臺作為主節(jié)點，其余機(jī)器作為子節(jié)點。4 臺機(jī)器具有相同的硬件及軟件配置，每臺機(jī)器有兩個2.4GHz Intel處理器和360G 內(nèi)存，Ubuntu13.10系統(tǒng)，Jdk1.7，以及0.20.2 版本的Hadoop，數(shù)據(jù)集是由IBM 的數(shù)據(jù)模擬生成器［12］所生成，數(shù)據(jù)集含有2113個數(shù)據(jù)項，事務(wù)平均長度64，事務(wù)最長73。

圖2給出了在不同最小支持度 （40%，30%，20%，10%，5%，3%，1%）下隨機(jī)選擇幾個頻繁項組成約束條件B時，Direct＊算法與DCFIBMR 算法的執(zhí)行效率對比。從圖中的數(shù)據(jù)對比可知，在約束條件B 相同的條件下DC－FIBMR 算法的執(zhí)行效率遠(yuǎn)遠(yuǎn)高于Direct＊算法，且隨著支持度的變小，DCFIBMR 算法相對于Direct＊算法的效率顯著提升，因此該實驗驗證了DCFIBMR 算法的有效性。

圖2 兩種算法在不同支持度下的執(zhí)行時間對比

5 結(jié)束語

從海量的數(shù)據(jù)中挖掘出滿足用戶指定約束條件的頻繁項集，使用傳統(tǒng)的串行算法是很難完成的任務(wù)。針對此類問題并結(jié)合目前流行的開源框架MapReduce，提出一種并行的約束頻繁項集挖掘算法DCFIBMR，該算法由用戶來指定約束規(guī)則，利用MapReduce框架將一個完整任務(wù)拆分為若干個相對獨立的子任務(wù)，由這些子任務(wù)根據(jù)約束規(guī)則從待處理的數(shù)據(jù)中挖掘出符合要求的頻繁項集，將從各個子任務(wù)中處理的結(jié)果進(jìn)行匯總整合，得到最終的處理結(jié)果。通過理論分析及實驗驗證了DCFIBMR 算法的有效性。

［1］Hai Duong，Tin Truong，Bac Le.An efficient algorithm for mining frequent itemsets with single constraint［J］.Advanced Computational Methods for Knowledge Engineering，2013，479：367－378.

［2］Mohammad El－h(huán)ajj，Osmar R Zaiane.Parallel leap：Largescale maximal pattern mining in a distributed environment［C］／／12th International Conference on Parallel and Distributed Systems，2006：230－232.

［3］HUA Hongjuan，ZHANG Jian，CHEN Shaohua.Miningalgorithm for constrained maximum frequent itemsets based on frequent pattern tree ［J］.Computer Engineering，2011，37（9）：78－80 （in Chinese）.［花紅娟，張健，陳少華.基于頻繁模式樹的約束最大頻繁項集挖掘算法 ［J］.計算機(jī)工程，2011，37 （9）：78－80.］

［4］XU Xiaoyong，PAN Yu，LING Chen.Energy saving and scheduling resources under the cloud computing environment［J］.Journal of Computer Applications，2012，32 （7）：421－426 （in Chinese）.［徐驍勇，潘郁，凌晨.云計算環(huán)境下資源的節(jié)能調(diào)度 ［J］.計算機(jī)應(yīng)用，2012，32 （7）：421－426.］

［5］LI Tao，XIAO Nanfeng.Suitable large data sets of weighted frequent itemsets mining algorithm ［J］.Computer Engineering and Design，2014，35 （6）：2114－2118 （in Chinese）.［李濤，肖南峰.適用大數(shù)據(jù)集的帶權(quán)頻繁項集挖掘算法 ［J］.計算機(jī)工程與設(shè)計，2014，35 （6）：2114－2118.］

［6］Yang C，Yen C，Tan C，et al.Osprey：Implementing Map－Reducer－style fault tolerance in a shared－nothing distributed database［C］／／International Conference on Data Engineering，2010：657－668.

［7］Dean J，Ghemawat S.MapReduce：A flexible data processing tool［J］.Commun ACM，2011，53 （1）：72－77.

［8］LIU Yi，ZHANG Kan.Workflow task assignmen strategy based on load balance and experiential value ［J］.Computer Engineering，2009，35 （21）：232－234 （in Chinese）. ［劉怡，張戡.基于負(fù)載平衡和經(jīng)驗值的工作流任務(wù)分配策略 ［J］.計算機(jī)工程，2009，35 （21）：232－234.］

［9］LV Xueji，LI Longshu.Research on the algorithm of MapRe－duce FP－Growth ［J］.Computer Technology and Development，2012 （11）：123－126 （in Chinese）. ［呂雪驥，李龍澍.FPGrowth算法MapReduce 化研究 ［J］.計算機(jī)技術(shù)與發(fā)展，2012 （11）：123－126.］

［10］ZUO Liyun，ZUO Lifeng.Cloud computing scheduling optimization algorithm based on reservation category ［J］.Computer Engineering and Design，2012，33 （4）：1357－1361 （in Chinese）.［左利云，左利鋒.云計算中基于預(yù)先分類的調(diào)度優(yōu)化算法［J］.計算機(jī)工程與設(shè)計，2012，33 （4）：1357－1361.］

［11］LI Yingjie.New item constraint method for mining frequent itemsets［J］.Computer Engineering and Applications，2009，45 （3）：161－164 （in Chinese）. ［李英杰.項約束頻繁項集挖掘的新方法 ［J］.計算機(jī)工程與應(yīng)用，2009，45 （3）：161－164.］

［12］IBM.IBM quest synthetic data generation code ［EB／OL］.http：／／www.almaden.ibm.com／，2009.