不確定數據流中頻繁模式的并行挖掘算法

常艷芬　王　樂　王輝兵

1(寧波大紅鷹學院信息工程學院　浙江 寧波 315175)2(大連理工大學創新實驗學院 　遼寧 大連 116024)

?

不確定數據流中頻繁模式的并行挖掘算法

常艷芬1王樂2*王輝兵2

1(寧波大紅鷹學院信息工程學院浙江 寧波 315175)2(大連理工大學創新實驗學院 遼寧 大連 116024)

不確定數據集中頻繁模式挖掘的研究熱點之一是挖掘算法的時空效率的提高，特別在目前數據量越來越大的情況下，實際應用對挖掘算法效率的要求也更高。針對動態不確定數據流中的頻繁模式挖掘模型，在算法AT-Mine的基礎上，給出一個基于MapReduce的并行挖掘算法。該算法需要兩次MapReduce就可以從一個滑動窗口中挖掘出所有的頻繁模式。實驗中，多數情況下通過一次MapReduce就可以挖掘到全部頻繁項集，并且能按數據量大小均勻地把數據分配到各個節點上。實驗驗證了該算法的時間效率能提高1個數量級。

不確定數據頻繁模式數據挖掘并行算法

0　引　言

由于數據的不確定性普遍存在于現實世界各個領域中，例如根據對電子商務網站頁面的訪問記錄，只能獲得潛在客戶對特定商品購買傾向的一個估計(即一個概率性指標)；并且隨著數據量快速的增加，而頻繁模式挖掘是數據挖掘中一項重要技術，因此不確定數據流頻繁模式挖掘算法研究成為數據挖掘領域的研究熱點之一。

數據流上的頻繁模式概念，仍然定義在單個事務上，不考慮跨事務的模式(不同時間上的組合模式)；其挖掘方法，一般是采用“窗口”獲取當前用戶關注的數據，然后基于已有的靜態數據集上的頻繁模式挖掘算法，設計數據流中被關注數據上的挖掘算法。

目前有3種典型的窗口模型[1]：界標窗口模型、時間衰減窗口模型和滑動窗口模型，如圖1所示。界標窗口模型中的窗口指特定一時間點(或數據流中一條特定的數據)到當前時間(或當前條數據)之間的數據，如圖1(a)所示，在C1、C2和C3時刻，窗口中的數據分別包含了從S點到C1點、C2點和C3點之間的數據。時間衰減窗口模型和界標窗口模型所包含的數據是相同的，只是衰減窗口中的每條數據有不同的權重，距離當前時間越近，數據的權重越大，如圖1(b)所示。實際上，時間衰減窗口模型是界標窗口模型的一個特例。滑動窗口模型中，每次處理數據的個數固定或者是每次處理數據的時間段長度是固定的，如圖1(c)所示。

已有的不確定數據流上頻繁模式挖掘算法主要通過以上三種窗口方法來獲取要處理的數據，即窗口中的數據，然后基于靜態數據集上的挖掘算法(如UF-Growth)來挖掘窗口數據中的頻繁模式[2-7]。

圖1　三種窗口模型

Leung等[4]提出兩個基于滑動窗口的算法UF-streaming和SUF-Growth，每個滑動窗口包含固定批數的數據，當一個窗口滿了以后，每來一批數據，都會先從窗口中刪除一批最老的數據，然后再將新來數據添加到窗口中。算法UF-streaming采用FP-streaming[8]的方法，預定義兩個最小期望支持數preMinsup和minSup (preMinsup < minSup)。UF-streaming算法利用UF-Growth挖掘每批數據中的期望支持數大于等于preMinsup的項集做為候選項集，并保存到一個樹UF-stream上，UF-stream樹上每個節點記錄窗口中每批數據的期望支持數；當新來一批數據中的候選項集被添加到UF-stream樹上之前，會將樹上最老批次數據對應的候選項集從樹上刪除；當一個節點上總的期望支持數(所有批上的期望支持數的和)大于等于minSup，則該節點到根節點對應的項集就是一個頻繁模式。SUF-Growth算法主要基于算法UF-Growth，該算法將每批數據添加到樹UF-Tree的時候，節點分別記錄每批數據的期望支持數；當新來一批數據的時候，會首先將樹上最老批次的數據刪除，然后將新來數據添加到樹上；挖掘頻繁模式的時候從該樹上讀取數據，采用模式增長的方式進行。

文獻[6，7]中提出的算法采用的是時間衰減窗口模型，仍然采用UF-Tree來存儲窗口中的事務項集。由于UF-Tree共享同一個節點時，不僅要求項相同，還要求項對應的概率值也相同，因此該樹結構的存儲需要大量的空間，同時也需要較多的處理時間。而另外一個靜態數據集上的頻繁模式挖掘算法AT-Mine[9]可以將數據集以較大的壓縮比維護在一棵樹上，同時沒有丟失事務項集的概率信息，最終算法的挖掘效率得到了較大的提高。

為了快速地處理數據以及大規模的數據，并行算法來進行數據挖掘是一個重要的方法。 目前，模式挖掘的并行算法主要在MapReduce環境下實現，其研究主要集中在靜態數據集的頻繁模式挖掘中。文獻[10-17]中的算法是基于Apriori，并且采用多次MapReduce，如果頻繁模式中最大的模式長度是K，則需要(K+1)次MapReduce。算法PFP[18]是基于FP-Growth，其僅僅需要兩次MapReduce，但是它分配到各個節點上數據存在大量的冗余，并且不能將數據按數據塊的大小較為均勻地分配到各個節點上處理，因此這也會影響到它處理的時間效率。

以上并行算法主要是處理靜態確定數據集中的頻繁模式挖掘，針對不確定數據流中的頻繁模式挖掘，在算法AT-Mine[9]的基礎上，本文給出一個基于MapReduce的并行挖掘算法來挖掘一個窗口中的數據。該算法最多需要兩次MapReduce就可以從一個窗口中挖掘出所有的頻繁模式，在本文的實驗中，多數情況下只需要一次MapReduce，并且數據能按數據量大小均勻分配到各個節點上。實驗驗證了本文提出算法的有效性。

1　問題定義

設D是一個包含n個事務的不確定數據集(記D= {T1,T2,…,Tn})，并且包含m個不同的項(記I= {i1,i2,…,im})，其中D中的第j個事務tj(j=1,2,…,n)表示為{(x1:p1),(x2:p2),…,(xv:pv) }，其中{x1,x2,…,xv}是項集I的一個子集，pu(u= 1,2,…,v)是事務項集中項iu的概率。數據集D中事務個數可以用|D|表示，也被稱為數據集的大小；包含k個不同項的項集被稱為k-項集(k-itemset)，k是項集的長度；|D|表示數據集的大小。

定義1事務項集t中的項集X的概率記為p(X,t)，定義為p(X,t)=∏x∈X∧X?tp(x,t)，其中p(x,t)是事務項集t中項x的概率。

定義2在不確定數據集D中，項集X的期望支持數記為expSN(X)，定義為expSN(X)=∑t?X∧t∈Dp(X,t)。

定義3設minExpSup為用戶預定義的最小期望支持閾值(Minimumexpectedsupportthreshold)，則最小期望支持數minExpSN定義為minExpSN=minExpSup×|D|。

在文獻[2-4,6-7,19-27]中，不確定數據集中的頻繁模式定義為：在不確定數據集D中，如果項集X的期望支持數不小于預定義的最小期望支持數minExpSN，則該項集就是D中的一個頻繁項集或頻繁模式。不確定數據集中的頻繁項集挖掘就是發現期望支持數不小于最小支持數的所有項集。

定義4在不確定事務數據集D中，頻繁項集X的任一超集都不可能是頻繁項集，則項集X也稱為最大頻繁項集(或最大頻繁模式)。

定義5在不確定事務數據集D中，項集X(或項X)的∑t?X∧t∈D∧x∈tP(X,t)×max(p(x,t))稱為X的超一項集的估計期望支持數(其中，max(p(x,t))表示事務項集t中最大的概率值)，記為EexpSN(X)。

定義6在一個數據集中，一個項集X的支持數(sn) 是指數據集中包含項集X的事務項集個數。

定義7當一個數據集被劃分為多個數據塊時，一個數據塊上包含的事務個數與最小期望支持閾值的乘積稱為該數據塊上的局部最小期望支持數。

定義8一個項集在數據集的一個數據塊上的期望支持數大于等于該數據塊的局部最小期望支持數，則該項集被稱為該塊上的局部頻繁項集。

性質1一個頻繁項集的所有子集都是頻繁項集，一個非頻繁項集的所有超集都是非頻繁項集。

2　本文提出的算法

本文給出的不確定數據流上的頻繁模式挖掘算法采用滑動窗口方法，針對每個窗口中的數據，提出一個挖掘不確定數據流中頻繁項集的算法MFPUD-MR(Mining Frequent Pattern from Uncertain Data based on MapReduce)。該算法主要包含三步：第一步，根據計算節點個數，將滑動窗口中數據集劃分成若干個數據量相同的數據塊，然后在MapReduce框架下并行找出每個數據塊上的局部頻繁項集作為候選項集；第二步，對候選項集進行篩選，減少候選項集的個數；第三步，在MapReduce框架下并行計算候選項集中每個項集的總期望支持數，其中總期望支持數不小于最小期望支持數的項集就是頻繁項集。

2.1挖掘候選項集

算法MFPUD-MR中第一步挖掘候選項集的子算法如算法1所示，在每個節點上利用AT-Mine算法找到局部頻繁模式，并統計所有一項集的期望支持數和局部數據集上的事務個數。

算法1SubProcedure MiningCandidate(D,minExpSup)

輸入:不確定數據集D,最小期望支持閾值minExpSup

輸出: 候選項集CFs

Begin

run(Mapper,Reducer)

End

Mapper(minExpSup,LD)

// LD 是一個劃分好的數據塊

Begin

利用AT-Mine算法挖掘數據塊LD上局部頻繁項集作為候選項集(候選項集的集合記為CFs);

For each itemset imst in CFs

Output(imst,count);

//計算候選項集中每個項集的期望支持數

EndFor

End

Reducer()

//計算CFs 中的每個項集在所有數據塊上總的期望支持數

Begin

Output(key,sum(values))

//key 是CFs 中的項集，values 是每個項集的期望支持數

End

定理1算法1挖掘出的候選項集包含了數據集中全部的頻繁項集。

設項集X是一頻繁項集，由于頻繁項集的期望支持數不小于最小期望支持閾值，因此X一定在一個或多個數據塊上是頻繁項集，

2.2對候選項集的剪枝處理

算法MFPUD-MR中第二步是對候選項集進行剪枝，剪枝策略如下：

策略1：如果一個項集在一部分數據集上的期望支持數大于等于最小期望支持數，則該項集在全局數據集上的期望支持數一定也大于等于最小期望支持數，所以該項集一定是一個頻繁項集。因此這部分項集可以從候選項集移入到頻繁項集集合中。

策略2：項集X在部分數據塊D1,D2,…,Dj上是頻繁的，設期望支持數之和為S1；在其它數據塊Dj+1,Dj+2,…,Ds不是頻繁的。設數據塊Dj+1,Dj+2,…,Ds總事務個數為S，如果S1+S×minExpSup

策略3：算法1中返回所有1項集的期望支持數，包括非頻繁1項集，根據性質1，如果候選項集包含非頻繁一項集中項，則該候選項集一定是非頻繁項集，因此可以從候選項集集合中刪除。

2.3從處理后的候選項集中確認頻繁項集

算法MFPUD-MR經過第二步對候選項集的處理，如果候選項集不為空，則進行第三步，第三步是計算候選項集中每個項集在全局數據集中總期望支持數算法如算法2所示。

算法2IdentifyFrequentItemsets(D,minExpSup,CFs)

輸入: 不確定數據集D,最小期望支持閾值minExpSup,候選項集CFs

輸出: 頻繁項集FIs

Begin

run(Mapper,Reducer)

End

Mapper(LD,CFs)

Begin

For each transaction itemset Tiin LD

For each itemset X in CFs

If X is the subset of Ti

X.expSN+= p(X,Ti);

EndIf

EndFor

EndFor

For each itemset X in CFs

output(X,X.expSN)

EndFor

End

Reducer(key,values,minExpSup)

//找出總期望支持數(sum)不小于最小期望支持數的項集

Begin

sum=0;

For each value in values

sum+=value

EndFor

If sum>= minExpSup

output(key,sum)

EndIf

End

3　實驗結果

為了測試本文算法的有效性，本文將PFP算法[18]改為不確定數據集中的頻繁模式挖掘算法，這里記為PFP-U，算法MFPUD-MR和PFP-U采用Python實現，AT-Mine是Java語言實現。為了測試算法MFPUD-MR的運算效率、加速度比和算法的擴展性，本節設計了如下的實驗。

實驗平臺使用26個節點組成的集群，其中包含1個主節點，1個調度節點，1個備份節點， 23個數據節點。每個節點的硬件配置為2.5 GHz雙核CPU及8 GB內存，軟件配置為ubuntu 12.04及Hadoop 0.22.0。

利用IBM數據生成器來產生兩個數據T20I10D10000K和T40I20D5000K，其中T表示事務項集的平均長度，I表示事物項集默認閾值下的頻繁項集長度，D表示數據集中事務個數(其中K表示1000)；同時采用常用方法，為每個事務項集的每項隨機生成一個范圍在(0，1]的數做為概率值。由于MapReduce默認將一個大的數據文件分割成68M大小的數據塊，本文中為了充分利用23個數據節點，本文將被測試的數據文件大小均勻的分割為20個小數據文件。

3.1不同最小期望閾值下的運行時間對比

(a) 數據集T20I10D10000K

(b) 數據集T40I20D5000K

圖2顯示了2個算法在不同支持度的運行時間。可以看出本文提出的方法MFPUD-MR的時間效率明顯高于PFP-U，這是因為隨著支持度的降低，頻繁1項集的個數增加的比較快，PFP-U中也會出現更多更長的子事務項集，因而隨著最小支持度的降低，算法PFP-U的運行時間增加的比較快；而算法MFPUD-MR第一次MapReduce產生了全局候選項集，通過候選項集的篩選，候選項集的個數減少了很多，甚至有時候候選項集為空，不需要第二次的MapReduce來統計候選項項集的期望支持數，因此算法MFPUD-MR的時間性能比較穩定。

3.2算法擴展性

(a) 數據集T20I10D10000K

(b) 數據集T40I20D5000K

圖3是采用不同數據規模的數據集來測試2個算法的時間性能。當數據規模發生變化的時候，頻繁1項集的個數變化不大，但是算法PFP-U會產生子事務項集的個數增加的比較快，因此算法PFP-U的運行時間基本上都是成比例的增加；而算法MFPUD-MR在挖掘局部頻繁項集的時候，它的運行時間會隨著數據規模的增加而稍微的增加，并且很多情況下，不需要第二次的MapReduce來統計候選項項集的期望支持數，因而算法MFPUD-MR的時間性能比較穩定。

3.3算法的加速度性能

(a) 數據集T20I10D10000K

(b) 數據集T40I20D5000K

圖4是2個算法在不同數據集上加速比實驗結果。而加速度是指算法在一個節點上總運行時間和在多個節點上的總運行時間的比值。理想的加速度(Ideal)是隨著節點個數的增加，算法的運行時間也成比例的增加，如圖4中Ideal的那條線。算法MFPUD-MR的加速度和理想的加速度(Ideal)比較接近，之所以不能完全達到理想的加速度這是因為節點越多，節點之間的通訊需要的時間也會越多，這會導致總的運行時間增加。而算法PFP-U不能將數據按大小均勻的分配到各個節點上執行，而它的運行時間總是和一個負擔重的節點上任務相關。綜上，算法MFPUD-MR的加速度比較理想。

4　結　語

本文給出一個不確定數據集中的頻繁項集挖掘算法MFPUD-MR。首先并行挖掘出小數據塊上的局部頻繁項集作為候選項集，然后對候選項集進行篩選：確定的頻繁項集從候選項集中移到頻繁項集集合中，確定的非頻繁項集從候選項集中刪除；最后再執行一次MapReduce對剩余候選項集進行全局期望支持數進行統計即可得到頻繁項集。從本文的實驗中可以發現，本文提出的候選項集剪枝策略可以很好地對候選項集進行篩選，在很多情況下，進行剪枝后，候選項集都為空，即不需要第二次執行MapReduce。本文實驗也很好地驗證了MFPUD-MR算法的時間效率明顯高于算法PFP-U，同時該算法的加速度還比較理想。

[1] Rawat R,Jain N.A Survey on Frequent ItemSet Mining Over Data Stream[J].International Journal of Electronics Communication and Computer Engineering (IJECCE),2013,4(1):86-87.

[2] 廖國瓊，吳凌琴，萬常選.基于概率衰減窗口模型的不確定數據流頻繁模式挖掘[J].計算機研究與發展,2012,49(5):1105-1115.

[3] 劉殷雷，劉玉葆，陳程.不確定性數據流上頻繁項集挖掘的有效算法[J].計算機研究與發展,2011(S3):1-7.

[4] Leung C K,Hao B.Mining of frequent itemsets from streams of uncertain data[C]//Proceedings of the International Conference on Data Engineering,Shanghai,China,March 29-April 2，IEEE Computer Society,Washington,DC,2009.

[5] 王爽，王國仁.基于滑動窗口的Top-K概率頻繁項查詢算法研究[J].計算機研究與發展,2012,49(10):2189-2197.

[6] Leung C K,Jiang F.Frequent itemset mining of uncertain data streams using the damped window model [C]//Proceedings of the 26th Annual ACM Symposium on Applied Computing (SAC 2011),TaiChung,Taiwan,March 2-24.Association for Computing Machinery,2011.[7] Leung C K,Jiang F.Frequent pattern mining from time-fading streams of uncertain data[C]//Proceedings of the 13th International Conference on Data,Warehousing and Knowledge Discovery (DaWaK 2011),Toulouse,France,August 29-September 2，Springer Verlag,2011.

[8] Giannella C,Han J,Pei J,et al.Mining frequent patterns in data streams at multiple time granularities[J].Next generation data mining,2003,2003(212):191-212.

[9] Wang L,Feng L,Wu M.AT-Mine:An Efficient Algorithm of Frequent Itemset Mining on Uncertain Dataset[J].Journal of Computers,2013,8(6):1417-1426.

[10] 李玲娟，張敏.云計算環境下關聯規則挖掘算法的研究[J].計算機技術與發展,2011(2):43-46.

[11] 戎翔，李玲娟.基于MapReduce的頻繁項集挖掘方法[J].西安郵電學院學報,2011(4):37-39.

[12] 黃立勤，柳燕煌.基于MapReduce并行的Apriori算法改進研究[J].福州大學學報(自然科學版),2011(5):680-685.

[13] Xiao T,Yuan C,Huang Y.PSON:A parallelized SON algorithm with MapReduce for mining frequent sets[C]//Proceedings of the 2011 4th International Symposium on Parallel Architectures,Algorithms and Programming,Tianjin,China,December 9-11,IEEE Computer Society,2011.

[14] Riondato M,Debrabant J A,Fonseca R,et al.PARMA:A parallel randomized algorithm for approximate association rules mining in MapReduce [C]//Proceedings of the 21st ACM International Conference on Information and Knowledge Management (CIKM 2012),Maui,HI,United states,October 29-November 2,Association for Computing Machinery,2012.

[15] Yang X Y,Liu Z,Fu Y.MapReduce as a programming model for association rules algorithm on Hadoop[C]//Proceedings of the 3rd International Conference on Information Sciences and Interaction Sciences,Chengdu,China,June 23-25,IEEE Computer Society,2010.

[16] Cryans J,Ratte S,Champagne R.Adaptation of apriori to MapReduce to build a warehouse of relations between named entities across the web[C]//Proceedings of the 2nd International Conference on Advances in Databases,Knowledge,and Data Applications (DBKDA 2010),Menuires,France,April-April 16,IEEE Computer Society,2010.

[17] 余楚禮，肖迎元，尹波.一種基于Hadoop的并行關聯規則算法[J].天津理工大學學報,2011(1):25-28.

[18] Li H,Wang Y,Zhang D,et al.PFP:Parallel FP-growth for query recommendation[C]//Proceedings of the 2008 2nd ACM International Conference on Recommender Systems25,2008,Lausanne,Switzerland,October 23-25.Association for Computing Machinery,2008.

[19] Lin C W,Hong T P.A new mining approach for uncertain databases using CUFP trees[J].Expert Systems with Applications,2012,39(4):4084-4093.

[20] Aggarwal C C,Yu P S.A survey of uncertain data algorithms and applications[J].IEEE Transactions on Knowledge and Data Engineering,2009,21(5):609-623.

[21] Leung C K,Mateo M A F,Brajczuk D A.A tree-based approach for frequent pattern mining from uncertain data[C]//Proceedings of the 12th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 2008),Osaka,Japan,May 20-23,Springer Verlag,2008.

[22] Sun X,Lim L,Wang S.An approximation algorithm of mining frequent itemsets from uncertain dataset[J].International Journal of Advancements in Computing Technology,2012,4(3):42-49.

[23] Calders T,Garboni C,Goethals B.Approximation of frequentness probability of itemsets in uncertain data[C]//Proceedings of the IEEE International Conference on Data Mining (ICDM 2010),Sydney,NSW,Australia,Dec.13-17,IEEE Computer Society,Washington,DC,2010.

[24] Wang L,Cheung D W,Cheng R,et al.Efficient Mining of Frequent Itemsets on Large Uncertain Databases[J].IEEE Transactions on Knowledge and Data Engineering,2012,24(12):2170-2183.

[25] Leung C K,Carmichael C L,Hao B.Efficient mining of frequent patterns from uncertain data[C]//Proceedings of the IEEE International Conference on Data Mining Workshops (ICDM Workshops 2007),Omaha,NE,United states,Oct.28-31,IEEE Computer Society,Washington,DC,2007.

[26] Aggarwal C C,Li Y,Wang J,et al.Frequent pattern mining with uncertain data[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2009),Paris,France,June 28-July 1,ACM,NewYork,2009.

[27] Liu Y.Mining frequent patterns from univariate uncertain data[J].Data and Knowledge Engineering,2012,71(1):47-68.

A PARALLEL MINING ALGORITHM WITH FREQUENT PATTERN FOR UNCERTAIN DATA STREAM

Chang Yanfen1Wang Le2*Wang Huibing2

1(School of Information Engineering,Ningbo Dahongying University,Ningbo 315175,Zhejiang,China)2(SchoolofInnovationExperiment,DalianUniversityofTechnology,Dalian116024,Liaoning,China)

One of the research focuses of frequent pattern mining in uncertain dataset is to improve time and space efficiency of the mining algorithm,especially in the case of growing data amount increase at present,the practical applications have higher demand on the efficiency of mining algorithms as well.Aiming at the frequent pattern mining model for dynamic uncertain data streams,we propose a MapReduce-based parallel mining algorithm on the basis of the algorithm of AT-Mine.By invoking twice at most the MapReduce procedures this algorithm can mine all the frequent patterns from a sliding window.In experiments presented in the paper,in majority cases by only executing MapReduce once it is able mine all frequent itemset,and the stream data can be distributed uniformly to each node according to the size of their amount.Experiments validate that the proposed algorithm can raise the time efficiency one order of magnitude.

Uncertain dataFrequent patternData miningParallel algorithm

2015-05-04。國家自然科學基金項目(61370200);寧波市自然科學基金項目(2013A610115,2014A610073);寧波市軟科學研究計劃項目(2014A10008);浙江省科技廳計劃項目(2016C31128);浙江省教育廳一般科研項目(Y201533234)。常艷芬，講師，主研領域：數據挖掘與軟件工程。王樂，副教授。王輝兵，講師。

TP311.13

A

10.3969/j.issn.1000-386x.2016.09.005