常艷芬　王　樂　王輝兵

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

?

不確定數(shù)據(jù)流中頻繁模式的并行挖掘算法

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

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

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

不確定數(shù)據(jù)頻繁模式數(shù)據(jù)挖掘并行算法

0　引　言

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

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

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

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

圖1　三種窗口模型

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

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

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

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

1　問題定義

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

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

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

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

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

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

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

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

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

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

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

2　本文提出的算法

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

2.1挖掘候選項集

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

算法1SubProcedure MiningCandidate(D,minExpSup)

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

輸出: 候選項集CFs

Begin

run(Mapper,Reducer)

End

Mapper(minExpSup,LD)

// LD 是一個劃分好的數(shù)據(jù)塊

Begin

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

For each itemset imst in CFs

Output(imst,count);

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

EndFor

End

Reducer()

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

Begin

Output(key,sum(values))

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

End

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

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

2.2對候選項集的剪枝處理

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

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

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

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

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

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

算法2IdentifyFrequentItemsets(D,minExpSup,CFs)

輸入: 不確定數(shù)據(jù)集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)

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

Begin

sum=0;

For each value in values

sum+=value

EndFor

If sum>= minExpSup

output(key,sum)

EndIf

End

3　實驗結(jié)果

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

實驗平臺使用26個節(jié)點組成的集群，其中包含1個主節(jié)點，1個調(diào)度節(jié)點，1個備份節(jié)點， 23個數(shù)據(jù)節(jié)點。每個節(jié)點的硬件配置為2.5 GHz雙核CPU及8 GB內(nèi)存，軟件配置為ubuntu 12.04及Hadoop 0.22.0。

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

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

(a) 數(shù)據(jù)集T20I10D10000K

(b) 數(shù)據(jù)集T40I20D5000K

圖2顯示了2個算法在不同支持度的運行時間?？梢钥闯霰疚奶岢龅姆椒∕FPUD-MR的時間效率明顯高于PFP-U，這是因為隨著支持度的降低，頻繁1項集的個數(shù)增加的比較快，PFP-U中也會出現(xiàn)更多更長的子事務(wù)項集，因而隨著最小支持度的降低，算法PFP-U的運行時間增加的比較快；而算法MFPUD-MR第一次MapReduce產(chǎn)生了全局候選項集，通過候選項集的篩選，候選項集的個數(shù)減少了很多，甚至有時候候選項集為空，不需要第二次的MapReduce來統(tǒng)計候選項項集的期望支持數(shù)，因此算法MFPUD-MR的時間性能比較穩(wěn)定。

3.2算法擴展性

(a) 數(shù)據(jù)集T20I10D10000K

(b) 數(shù)據(jù)集T40I20D5000K

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

3.3算法的加速度性能

(a) 數(shù)據(jù)集T20I10D10000K

(b) 數(shù)據(jù)集T40I20D5000K

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

4　結(jié)　語

本文給出一個不確定數(shù)據(jù)集中的頻繁項集挖掘算法MFPUD-MR。首先并行挖掘出小數(shù)據(jù)塊上的局部頻繁項集作為候選項集，然后對候選項集進行篩選：確定的頻繁項集從候選項集中移到頻繁項集集合中，確定的非頻繁項集從候選項集中刪除；最后再執(zhí)行一次MapReduce對剩余候選項集進行全局期望支持數(shù)進行統(tǒng)計即可得到頻繁項集。從本文的實驗中可以發(fā)現(xiàn)，本文提出的候選項集剪枝策略可以很好地對候選項集進行篩選，在很多情況下，進行剪枝后，候選項集都為空，即不需要第二次執(zhí)行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] 廖國瓊，吳凌琴，萬常選.基于概率衰減窗口模型的不確定數(shù)據(jù)流頻繁模式挖掘[J].計算機研究與發(fā)展,2012,49(5):1105-1115.

[3] 劉殷雷，劉玉葆，陳程.不確定性數(shù)據(jù)流上頻繁項集挖掘的有效算法[J].計算機研究與發(fā)展,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].計算機研究與發(fā)展,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] 李玲娟，張敏.云計算環(huán)境下關(guān)聯(lián)規(guī)則挖掘算法的研究[J].計算機技術(shù)與發(fā)展,2011(2):43-46.

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

[12] 黃立勤，柳燕煌.基于MapReduce并行的Apriori算法改進研究[J].福州大學(xué)學(xué)報(自然科學(xué)版),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的并行關(guān)聯(lián)規(guī)則算法[J].天津理工大學(xué)學(xué)報,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。國家自然科學(xué)基金項目(61370200);寧波市自然科學(xué)基金項目(2013A610115,2014A610073);寧波市軟科學(xué)研究計劃項目(2014A10008);浙江省科技廳計劃項目(2016C31128);浙江省教育廳一般科研項目(Y201533234)。常艷芬，講師，主研領(lǐng)域：數(shù)據(jù)挖掘與軟件工程。王樂，副教授。王輝兵，講師。

TP311.13

A

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