基于MapReduce的約束頻繁項集挖掘算法

施 亮，錢雪忠

（江南大學 物聯網工程學院，江蘇 無錫214122）

0 引 言

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

1 相關概念

1.1 約束頻繁項

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

1.2 FP－tree的構建

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

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

（2）構造FP－tree樹的根節點T，并標記為 “NULL”，再次掃描事務數據庫DB，遍歷每條事務Trans，并執行如下過程：

1）根據頻繁項集在F中的順序，對事務Trans中頻繁項按其支持數降序排列，構造 ［p｜P］結構，其中p是事務Trans中第一個項，P是剩余項。

2）調用insert＿tree（［p｜P，T］）函數，該函數執行過程如下：

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

1.3 MapReduce編程模型

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

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

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

給定一個事務數據庫、最小支持度及約束規則B，DCFIBMR 算法需要執行兩次MapReduce過程。

2.1 第一次MapReduce過程

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

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

2.2 第二次MapReduce過程

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

（1）mapper的輸入參數是事務數據庫中的數據切片，每個數據切片以鍵值對，如＜key，Value＝Ti＞，的形式傳遞。對于每個Ti，mapper將會按照如下步驟進行：

1）按照F中頻繁項的順序對Ti進行降序排列；

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

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

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

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

2）掃描一次DB（group－id），產生由頻繁項按支持數降序排列的頭表subHTable；

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

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

5）遍歷subHTable集合，對于集合中的每個頻繁項p，從subFPtree中找到含有p的路徑，并構造p的條件模式基集合。然后將prefix＝prefix＋p.NodeName，p的條件模式基集合，約束規則B 及F 作為輸入參數從步驟2）開始迭代執行。

算法的具體執行過程如下：

輸入：事務數據庫DB，最小支持度minsup，約束規則B；

第一次MapReduce：

第二次MapReduce：

3 DCFIBMR 算法實例講解

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

表1 事務數據庫D

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

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

Map階段：

本階段主要是對事務數據庫D 的分組及數據的分發，以便于后續的并行計算。以D 中第一行Tid－1為例，首先對Tid－1中的項集按照頻繁項在F中的位置進行降序排序，并刪除F中沒有的項集，得到T＝｛f，c，p，m，a，i｝。然后對T 進行分組，形式如：｛｛f，c，p，m，a｝｜i｝、｛｛f，c，p，m｝｜a｝、｛｛f，c，p｝｜m｝、｛｛f，c｝｜p｝、｛｛f｝｜c｝。在F中i的下標為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階段，事務數據庫被進行了分組及輸出，而在Reduce階段，會接收到被分到同一組內的數據集合，形如＜group－id，Values＞，其中group－id為組的編號，Values為同一組內的數據集合；以頻繁項i為例，將會獲取到group－id＝8，Values＝ （｛f，c，p，m，a｝，｛f，p，b，n｝，｛f，c，m，b，l，n｝）。設定DB （8）＝ ［｛f，c，p，m，a｝，｛f，p，b，n｝，｛f，c，m，b，l，n｝］。那么基于該局部數據庫構建subFPtree，可構建出如圖1 所示的頭表subHTable及子頻繁模式樹subFPtree。

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

圖1 頭表及子頻繁模式樹

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

4 算法性能比較與分析

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

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

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

為了進一步驗證本文算法的有效性，實驗設計如下：

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

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

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

5 結束語

從海量的數據中挖掘出滿足用戶指定約束條件的頻繁項集，使用傳統的串行算法是很難完成的任務。針對此類問題并結合目前流行的開源框架MapReduce，提出一種并行的約束頻繁項集挖掘算法DCFIBMR，該算法由用戶來指定約束規則，利用MapReduce框架將一個完整任務拆分為若干個相對獨立的子任務，由這些子任務根據約束規則從待處理的數據中挖掘出符合要求的頻繁項集，將從各個子任務中處理的結果進行匯總整合，得到最終的處理結果。通過理論分析及實驗驗證了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－hajj，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］.計算機工程，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）.［徐驍勇，潘郁，凌晨.云計算環境下資源的節能調度 ［J］.計算機應用，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）.［李濤，肖南峰.適用大數據集的帶權頻繁項集挖掘算法 ［J］.計算機工程與設計，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）. ［劉怡，張戡.基于負載平衡和經驗值的工作流任務分配策略 ［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］.計算機技術與發展，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）.［左利云，左利鋒.云計算中基于預先分類的調度優化算法［J］.計算機工程與設計，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］.計算機工程與應用，2009，45 （3）：161－164.］

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