常艷芬　王　樂(lè)　王輝兵

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

?

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

常艷芬1王樂(lè)2*王輝兵2

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

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

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

0　引　言

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

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

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

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

圖1　三種窗口模型

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

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

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

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

1　問(wèn)題定義

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

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

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

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

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

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

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

定義6在一個(gè)數(shù)據(jù)集中，一個(gè)項(xiàng)集X的支持?jǐn)?shù)(sn) 是指數(shù)據(jù)集中包含項(xiàng)集X的事務(wù)項(xiàng)集個(gè)數(shù)。

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

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

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

2　本文提出的算法

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

2.1挖掘候選項(xiàng)集

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

算法1SubProcedure MiningCandidate(D,minExpSup)

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

輸出: 候選項(xiàng)集CFs

Begin

run(Mapper,Reducer)

End

Mapper(minExpSup,LD)

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

Begin

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

For each itemset imst in CFs

Output(imst,count);

//計(jì)算候選項(xiàng)集中每個(gè)項(xiàng)集的期望支持?jǐn)?shù)

EndFor

End

Reducer()

//計(jì)算CFs 中的每個(gè)項(xiàng)集在所有數(shù)據(jù)塊上總的期望支持?jǐn)?shù)

Begin

Output(key,sum(values))

//key 是CFs 中的項(xiàng)集，values 是每個(gè)項(xiàng)集的期望支持?jǐn)?shù)

End

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

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

2.2對(duì)候選項(xiàng)集的剪枝處理

算法MFPUD-MR中第二步是對(duì)候選項(xiàng)集進(jìn)行剪枝，剪枝策略如下：

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

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

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

2.3從處理后的候選項(xiàng)集中確認(rèn)頻繁項(xiàng)集

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

算法2IdentifyFrequentItemsets(D,minExpSup,CFs)

輸入: 不確定數(shù)據(jù)集D,最小期望支持閾值minExpSup,候選項(xiàng)集CFs

輸出: 頻繁項(xiàng)集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)

//找出總期望支持?jǐn)?shù)(sum)不小于最小期望支持?jǐn)?shù)的項(xiàng)集

Begin

sum=0;

For each value in values

sum+=value

EndFor

If sum>= minExpSup

output(key,sum)

EndIf

End

3　實(shí)驗(yàn)結(jié)果

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

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

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

3.1不同最小期望閾值下的運(yùn)行時(shí)間對(duì)比

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

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

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

3.2算法擴(kuò)展性

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

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

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

3.3算法的加速度性能

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

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

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

4　結(jié)　語(yǔ)

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

[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] 廖國(guó)瓊，吳凌琴，萬(wàn)常選.基于概率衰減窗口模型的不確定數(shù)據(jù)流頻繁模式挖掘[J].計(jì)算機(jī)研究與發(fā)展,2012,49(5):1105-1115.

[3] 劉殷雷，劉玉葆，陳程.不確定性數(shù)據(jù)流上頻繁項(xiàng)集挖掘的有效算法[J].計(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] 王爽，王國(guó)仁.基于滑動(dòng)窗口的Top-K概率頻繁項(xiàng)查詢算法研究[J].計(jì)算機(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] 李玲娟，張敏.云計(jì)算環(huán)境下關(guān)聯(lián)規(guī)則挖掘算法的研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2011(2):43-46.

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

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

TP311.13

A

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