馬 可，李玲娟，孫杜靖

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210003)

分布式并行化數(shù)據(jù)流頻繁模式挖掘算法

馬 可，李玲娟，孫杜靖

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210003)

為了提高數(shù)據(jù)流頻繁模式挖掘的效率，文中基于經(jīng)典的數(shù)據(jù)流頻繁模式挖掘算法FP-Stream和分布式并行計(jì)算原理，設(shè)計(jì)了一種分布式并行化數(shù)據(jù)流頻繁模式挖掘算法—DPFP-Stream (Distributed Parallel Algorithm of Mining Frequent Pattern on Data Stream)。該算法將建立頻繁模式樹的任務(wù)分為local和global兩部分，并設(shè)置了參數(shù)“當(dāng)前時(shí)間”；將到達(dá)的流數(shù)據(jù)平均分配到多個(gè)不同的local節(jié)點(diǎn)，各local節(jié)點(diǎn)使用FP-Growth算法產(chǎn)生該單位時(shí)間內(nèi)本節(jié)點(diǎn)的候選頻繁項(xiàng)集，并按照單位時(shí)間將候選頻繁項(xiàng)集及其支持度計(jì)數(shù)打包發(fā)送至global節(jié)點(diǎn)；global節(jié)點(diǎn)按“當(dāng)前時(shí)間”合并各local節(jié)點(diǎn)的中間結(jié)果并更新模式樹Pattern-Tree。在分布式數(shù)據(jù)流計(jì)算平臺(tái)Storm上進(jìn)行的算法實(shí)現(xiàn)和性能測(cè)試結(jié)果表明，DPFP-Stream算法的計(jì)算效率能夠隨著local節(jié)點(diǎn)或local bolt線程的增加而提高，適用于高效挖掘數(shù)據(jù)流中的頻繁模式。

數(shù)據(jù)流；頻繁模式；分布式并行化；Storm

0 引 言

數(shù)據(jù)流是按時(shí)間順序到達(dá)的數(shù)據(jù)所組成的一個(gè)序列，其中的數(shù)據(jù)是動(dòng)態(tài)的，數(shù)據(jù)量潛在無界、數(shù)據(jù)到達(dá)速率快。對(duì)此類數(shù)據(jù)的收集過程和挖掘過程是同時(shí)進(jìn)行的，不允許反復(fù)掃描歷史數(shù)據(jù)，需要用一次掃描算法(single-scan algorithm)來處理[1]。

流數(shù)據(jù)的挖掘有分類、聚類、關(guān)聯(lián)分析等多種任務(wù)[2-4]。在流數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘算法中，經(jīng)典的FP-Stream算法實(shí)現(xiàn)了對(duì)流數(shù)據(jù)的頻繁模式挖掘。該算法將挖掘任務(wù)分為在線挖掘單位時(shí)間的候選頻繁項(xiàng)集與離線處理歷史頻繁項(xiàng)集兩個(gè)部分，通過傾斜時(shí)間框架存儲(chǔ)候選頻繁項(xiàng)集，并可以按照用戶輸入的參數(shù)查詢相應(yīng)時(shí)間的頻繁項(xiàng)集[5-7]。

MapReduce是一種分布式計(jì)算框架，將一個(gè)算法抽象成Map和Reduce兩個(gè)階段進(jìn)行處理，非常適合數(shù)據(jù)密集型計(jì)算，但是它是批處理的。Storm是一種典型的在線流式數(shù)據(jù)分布式計(jì)算架構(gòu)，可以用來在線處理源源不斷流進(jìn)來的數(shù)據(jù)，也可以通過設(shè)置滑動(dòng)時(shí)間窗口等機(jī)制，在實(shí)時(shí)處理到達(dá)數(shù)據(jù)的同時(shí)，實(shí)現(xiàn)類似MapReduce的功能[8]。

文中首先基于經(jīng)典數(shù)據(jù)流頻繁模式挖掘算法FP-Stream[9]和分布式并行計(jì)算的思想，設(shè)計(jì)了一種分布式并行化數(shù)據(jù)流頻繁模式挖掘算法(Distributed Parallel algorithm of mining Frequent Pattern on data Stream，DPFP-Stream)。接著，考慮到將流挖掘算法部署到流平臺(tái)上運(yùn)行是算法實(shí)用化的前提，進(jìn)一步基于Storm集群進(jìn)行了DPFP-Stream算法的實(shí)現(xiàn)。為了評(píng)價(jià)該算法的性能，設(shè)計(jì)了線程處理壓力測(cè)試實(shí)驗(yàn)，并分析了實(shí)驗(yàn)效果。

1 FP-Stream算法分析

FP-Tree(頻繁模式樹)是FP-Growth算法建立的一種數(shù)據(jù)結(jié)構(gòu)，雖然它不能直接用于數(shù)據(jù)流的關(guān)聯(lián)規(guī)則挖掘，但通過對(duì)FP-Tree加以改進(jìn)，可以將其運(yùn)用在數(shù)據(jù)流上[10-11]?；诖怂枷?，Giannella.C等提出了FP-Stream模型，將頻繁模式挖掘算法分為挖掘單位時(shí)間頻繁項(xiàng)集與記錄各時(shí)間段頻繁項(xiàng)集兩個(gè)部分[12]。第一部分設(shè)置了參數(shù)最大支持度誤差(該值小于挖掘頻繁項(xiàng)集的最小支持度)，使用FP-Growth算法對(duì)單位時(shí)間內(nèi)的數(shù)據(jù)進(jìn)行挖掘，挖掘出支持度大于支持度誤差的項(xiàng)集即候選頻繁項(xiàng)集供第二部分處理；第二部分以FP-Tree為基礎(chǔ)，引入傾斜時(shí)間窗口[13]建立Pattern-Tree，用來記錄不同時(shí)間粒度的頻繁項(xiàng)集中間結(jié)果；算法對(duì)外設(shè)置了接口供用戶輸入?yún)?shù)，用戶可以自由地設(shè)置最小支持度、置信度與查詢時(shí)間，根據(jù)不同時(shí)間段參數(shù)方便地查詢頻繁項(xiàng)集及關(guān)聯(lián)規(guī)則。

圖1給出了FP-Stream算法在一個(gè)單位時(shí)間內(nèi)的處理流程。

圖1 FP-Stream算法單位時(shí)間內(nèi)的處理流程

2 DPFP-Stream算法設(shè)計(jì)

2.1 基本思想

FP-Stream算法無法直接運(yùn)用于分布式環(huán)境，因?yàn)楫?dāng)?shù)竭_(dá)的數(shù)據(jù)流速過快，算法第一部分(用FP-Growth算法挖掘單位時(shí)間內(nèi)的候選頻繁項(xiàng)集)無法快速產(chǎn)生結(jié)果，為了提高挖掘速度必須提高最大支持度誤差值，但這會(huì)影響挖掘精度。

針對(duì)這個(gè)問題，文中設(shè)計(jì)了DPFP-Stream算法。其基本思想是：將挖掘任務(wù)分為local和global兩大部分，相應(yīng)地，設(shè)置多個(gè)local節(jié)點(diǎn)和一個(gè)global節(jié)點(diǎn)，local節(jié)點(diǎn)為局部計(jì)算節(jié)點(diǎn)，global節(jié)點(diǎn)為全局合并節(jié)點(diǎn)。到達(dá)的流數(shù)據(jù)平均分配到不同的local節(jié)點(diǎn)，各local節(jié)點(diǎn)使用FP-Growth算法產(chǎn)生該單位時(shí)間內(nèi)本節(jié)點(diǎn)的候選頻繁項(xiàng)集，按照單位時(shí)間將候選頻繁項(xiàng)集及其支持度計(jì)數(shù)打包發(fā)送至global節(jié)點(diǎn)；global節(jié)點(diǎn)合并各local節(jié)點(diǎn)的中間結(jié)果并發(fā)送至Pattern-Tree。此外，設(shè)置參數(shù)“當(dāng)前時(shí)間”來保證被合并數(shù)據(jù)在時(shí)間上的對(duì)應(yīng)性。

2.2 候選頻繁項(xiàng)集的分布式并行化挖掘

候選頻繁項(xiàng)集的挖掘以分布式并行化方式進(jìn)行，到達(dá)的數(shù)據(jù)平均分配到各個(gè)local節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)設(shè)置一個(gè)緩存，接收一個(gè)單位時(shí)間的流數(shù)據(jù)，當(dāng)接收時(shí)間到達(dá)一個(gè)單位時(shí)間，對(duì)這一塊數(shù)據(jù)建立FP-Tree，根據(jù)算法設(shè)定的最大支持度誤差閾值，找到該單位時(shí)間內(nèi)的候選頻繁項(xiàng)集(支持度大于最大支持度誤差的項(xiàng)集)，并將其按照時(shí)間打包發(fā)送至global模塊進(jìn)行處理。圖2為基于單位時(shí)間內(nèi)的數(shù)據(jù)生成FP-Tree的流程。

圖2 建立單位時(shí)間內(nèi)的FP-Tree的流程

建立了單位時(shí)間內(nèi)的FP-Tree之后，使用經(jīng)典的FP-Growth算法[14]挖掘該棵FP-Tree中支持度大于最大支持度誤差的頻繁項(xiàng)集，即候選頻繁項(xiàng)集，具體過程可以描述如下：

輸入：待挖掘的FP-Tree；

輸出：所有的頻繁項(xiàng)集。

步驟：

遞歸地挖掘每個(gè)條件FP-Tree，累加后綴頻繁項(xiàng)集，直到找到FP-Tree為空或者FP-Tree只有一條路徑，首先調(diào)用FP-Growth(Tree,null)。

過程FP-Growth (Tree,x)可以描述如下：

procedureFP-Growth(Tree,x)

ifTree含單個(gè)路徑P

then{

for路徑P中節(jié)點(diǎn)的每個(gè)組合(記作b)

產(chǎn)生模式b∪a，其支持度support為b中節(jié)點(diǎn)的最小支持度；

}

else{

foreachai在Tree的頭部(按照支持度計(jì)數(shù)由低到高順序進(jìn)行掃描)

{

產(chǎn)生一個(gè)模式b=ai∪a，其支持度support=ai.support；構(gòu)造b的條件模式基(即順著headertable中item的鏈表，找出所有包含該item的前綴路徑，這些前綴路徑就是條件模式基)，然后構(gòu)造b的條件FP-Tree，即Treeb；

ifTreeb不為空

then調(diào)用FP_Growth(Treeb,b)；

}

}

local節(jié)點(diǎn)在生成一個(gè)單位時(shí)間內(nèi)的候選頻繁項(xiàng)集之后，將該單位時(shí)間內(nèi)的所有頻繁項(xiàng)集與記錄總數(shù)、當(dāng)前時(shí)間一起打包發(fā)送至global節(jié)點(diǎn)進(jìn)行合并。

2.3 分布式并行化挖掘結(jié)果的合并

由于處理能力會(huì)有所不同，各local節(jié)點(diǎn)處理生成中間結(jié)果并發(fā)送至global節(jié)點(diǎn)的速度可能不一致，這使得global節(jié)點(diǎn)會(huì)錯(cuò)誤地將不同時(shí)間段的中間結(jié)果合并至相同時(shí)間段。為了防止此類情況的發(fā)生，DPFP-Stream算法對(duì)global節(jié)點(diǎn)與各local節(jié)點(diǎn)設(shè)置了參數(shù)“當(dāng)前時(shí)間”，global節(jié)點(diǎn)依據(jù)各local節(jié)點(diǎn)發(fā)送的“當(dāng)前時(shí)間”對(duì)中間結(jié)果進(jìn)行合并。

global節(jié)點(diǎn)設(shè)置了閾值threshold，其作用是控制Pattern-Tree的合并。global節(jié)點(diǎn)合并一個(gè)local節(jié)點(diǎn)的中間結(jié)果至Pattern-Tree的過程可以描述如下：

輸入：全局Pattern-Tree，單個(gè)local節(jié)點(diǎn)的中間結(jié)果MR，合并閾值threshold；

輸出：合并后的全局Pattern-Tree。

步驟：

比較MR與Pattern-Tree的當(dāng)前時(shí)間；

if MR.time==PatterTree.time

then{

for each frequent item in MR

{

在Pattern-Tree中找到相應(yīng)節(jié)點(diǎn)，將支持度計(jì)數(shù)加入該節(jié)點(diǎn)的第一塊時(shí)間窗口(若Pattern-Tree中無相應(yīng)節(jié)點(diǎn)，則新建節(jié)點(diǎn)插入相應(yīng)信息)；

}

將該單位時(shí)間內(nèi)記錄總數(shù)加入Root節(jié)點(diǎn)的第一塊時(shí)間窗口；

}

else if MR.time==PatternTree.time+1

then{

for each frequent item in MR

{

在Pattern-Tree中找到相應(yīng)節(jié)點(diǎn)，將節(jié)點(diǎn)內(nèi)窗口的數(shù)據(jù)向后滑動(dòng)，并將支持度計(jì)數(shù)加入該節(jié)點(diǎn)的第一塊時(shí)間窗口(若Pattern-Tree中無相應(yīng)節(jié)點(diǎn)，則新建節(jié)點(diǎn)插入相應(yīng)信息)，Root節(jié)點(diǎn)內(nèi)窗口的數(shù)據(jù)向后滑動(dòng)，并將記錄總數(shù)加入Root節(jié)點(diǎn)的第一塊時(shí)間窗口；

}

Pattern-Tree.time+1；

}

else if MR.time

then{

依據(jù)PatternTree.time-MR.time，找到該事件對(duì)應(yīng)到傾斜時(shí)間窗口的具體位置，對(duì)MR中的所有頻繁項(xiàng)集，在Pattern-Tree中進(jìn)行更新；

}

else{

將Pattern-Tree當(dāng)前時(shí)間發(fā)送至local節(jié)點(diǎn)，更新local節(jié)點(diǎn)當(dāng)前時(shí)間，使之與global節(jié)點(diǎn)一致；

}

3 DPFP-Stream算法在Storm平臺(tái)上的實(shí)現(xiàn)

3.1 Storm系統(tǒng)

Storm[15]是Twitter支持開發(fā)的一款分布式的、開源的、實(shí)時(shí)的、主從式大數(shù)據(jù)流式計(jì)算系統(tǒng)，是一種典型的流式數(shù)據(jù)計(jì)算架構(gòu)，數(shù)據(jù)在任務(wù)拓?fù)渲斜挥?jì)算，并輸出有價(jià)值的信息。

任務(wù)拓?fù)涫荢torm的邏輯單元，一個(gè)實(shí)時(shí)應(yīng)用的計(jì)算任務(wù)將被打包為任務(wù)拓?fù)浜蟀l(fā)布，任務(wù)拓?fù)湟坏┨峤缓缶蜁?huì)一直運(yùn)行，除非顯式地去中止。一個(gè)任務(wù)拓?fù)涫怯梢幌盗蠸pout和Bolt構(gòu)成的有向無環(huán)圖，通過數(shù)據(jù)流實(shí)現(xiàn)Spout和Bolt之間的關(guān)聯(lián)。如圖3所示，Spout負(fù)責(zé)從外部數(shù)據(jù)源不間斷地讀取數(shù)據(jù)，并以元組形式發(fā)送給相應(yīng)的Bolt，Bolt負(fù)責(zé)對(duì)接收到的數(shù)據(jù)流進(jìn)行計(jì)算，可以級(jí)聯(lián)，也可以向外發(fā)送數(shù)據(jù)流。

圖3 Storm拓?fù)涫纠?/p>

3.2 DPFP-Stream算法在Storm上的部署

基于Storm流計(jì)算框架的編程模型，文中設(shè)計(jì)了DPFP-Stream算法在Storm上的部署方案。

圖4為DPFP-Stream算法在Storm上的拓?fù)涫疽鈭D。

圖4 DPFP-Stream的Storm拓?fù)鋱D

如圖4所示，Kakfa[16]作為消息中間件，接收用戶發(fā)送的配置參數(shù)與查詢參數(shù)，發(fā)送至InputSpout供后續(xù)計(jì)算；DataSpout接收待挖掘數(shù)據(jù)，將到達(dá)的數(shù)據(jù)打上時(shí)間戳標(biāo)記并平均發(fā)送至各Local Bolt線程進(jìn)行計(jì)算；InputSpout接收用戶輸入的配置參數(shù)與查詢參數(shù)，將所有參數(shù)(支持度、支持度誤差、置信度、查詢時(shí)間)發(fā)送至Global Bolt供挖掘計(jì)算與查詢，同時(shí)將參數(shù)最大支持度誤差發(fā)送至Local Bolt供生成候選頻繁項(xiàng)集；Local Bolt為算法在Storm上實(shí)現(xiàn)的并行化部分，按時(shí)間戳對(duì)單位時(shí)間內(nèi)到達(dá)的數(shù)據(jù)使用FP-Growth算法挖掘候選頻繁項(xiàng)集；Global Bolt為算法在Storm上實(shí)現(xiàn)的合并部分，對(duì)各Local Bolt生成的中間結(jié)果進(jìn)行合并，生成最新的Pattern-Tree；用戶可向系統(tǒng)輸入查詢參數(shù)查詢最新Pattern-Tree。

4 實(shí)驗(yàn)與結(jié)果分析

為了測(cè)試DPFP-Stream算法的分布式并行化效果，設(shè)計(jì)了如下實(shí)驗(yàn)。

(1)實(shí)驗(yàn)數(shù)據(jù)集與環(huán)境。

實(shí)驗(yàn)數(shù)據(jù)集是預(yù)處理過的超市購物數(shù)據(jù)集，實(shí)驗(yàn)中分別使用經(jīng)典的FP-Stream算法與文中設(shè)計(jì)的DPFP-Stream算法對(duì)該數(shù)據(jù)集進(jìn)行頻繁模式挖掘。

實(shí)驗(yàn)環(huán)境：1個(gè)Nimbus節(jié)點(diǎn)、2個(gè)Supervisor的Storm集群，每臺(tái)機(jī)器內(nèi)存8 GB，處理器為主頻2.70 GHz的i7處理器，操作系統(tǒng)為CentOS 6.4。使用Kafka作為消息中間件，設(shè)置一個(gè)producer每秒選取數(shù)據(jù)集中有特定關(guān)聯(lián)規(guī)則的數(shù)據(jù)，打上相應(yīng)時(shí)間戳，按照每秒10 000條的速率發(fā)送至Kafka，算法的Storm拓?fù)鋸腒afka中獲取數(shù)據(jù)進(jìn)行相應(yīng)挖掘計(jì)算。支持度設(shè)為0.5，置信度設(shè)為0.8，經(jīng)典FP-Stream算法的支持度誤差設(shè)為0.3，DPFP-Stream算法的支持度誤差設(shè)為0.1，線程數(shù)設(shè)為3。

(2)實(shí)驗(yàn)結(jié)果與分析。

在FP-Stream算法與DPFP-Stream算法的對(duì)比方面：各算法分別處理完100萬條數(shù)據(jù)后，兩種算法的挖掘結(jié)果一致，而Storm系統(tǒng)的StormUI中顯示FP-Stream相應(yīng)線程的capacity(線程處理壓力)為0.143，DPFP-Stream相應(yīng)線程的平均capacity為0.113。這說明，盡管DPFP-Stream的參數(shù)支持度誤差設(shè)置的比較小，但是在得出一致的挖掘結(jié)果的同時(shí)，單個(gè)線程所承受的計(jì)算壓力反而減小了。

在DPFP-Stream算法的線程處理壓力隨算法參數(shù)設(shè)置和線程數(shù)的變化方面：實(shí)驗(yàn)結(jié)果如圖5所示，在每秒到達(dá)拓?fù)涞臄?shù)據(jù)流速率為10 000條不變的情況下，無論支持度誤差為0.1或是0.3，DPFP-Stream算法的capacity都隨著Local Bolt線程個(gè)數(shù)的增加呈倒數(shù)減小，說明算法的處理能力可隨線程數(shù)的增加呈近線性增加；而當(dāng)支持度誤差為0.1時(shí)，雖然線程處理壓力比支持度誤差為0.3時(shí)大，但是可以挖掘出更多的頻繁項(xiàng)集。

圖5 DPFP-Stream算法多線程測(cè)試結(jié)果

從圖中可以看出，DPFP-Stream算法能有效地降低計(jì)算處理壓力，并且不影響挖掘結(jié)果。此外，在線程處理壓力不變的情況下，由于DPFP-Stream算法可以設(shè)置更低的支持度誤差，故能在一定的情況下挖掘出FP-Stream算法挖掘不到的結(jié)果。

5 結(jié)束語

基于FP-Stream算法和分布式并行計(jì)算思想，文中設(shè)計(jì)了一種分布式并行化數(shù)據(jù)流頻繁模式挖掘算法(DPFP-Stream)，并在流計(jì)算平臺(tái)Storm上進(jìn)行了算法實(shí)現(xiàn)與性能測(cè)試。結(jié)果表明，該算法借助分布式并行化機(jī)制，能以更小的線程處理壓力獲得同樣的挖掘精度，也說明了文中對(duì)FP-Stream算法所做的基于Storm的分布式并行化工作的可行性和有效性。

[1] Li Lingjuan,Li Xiong.An improved online stream data clustering algorithm[C]//Proceedings of second international conference on business computing and global informatization.Shanghai,China:[s.n.],2012:526-529.

[2] Gaber M,Zaslavsky A,Krishnaswamy S.Mining data streams:a review[J].SIGMOD Record,2005,34(2):18-26.

[3] Han J,Kamber M,Pei J.Data mining:concepts and techniques[M].[s.l.]:Elsevier,2006:242-248.

[4] 孫大為,張廣艷,鄭緯民.大數(shù)據(jù)流式計(jì)算:關(guān)鍵技術(shù)及系統(tǒng)實(shí)例[J].軟件學(xué)報(bào),2014,25(4):839-862.

[5] 孫玉芬,盧炎生.流數(shù)據(jù)挖掘綜述[J].計(jì)算機(jī)科學(xué),2007,34(1):1-5.

[6] Charikar M,Chen K,Farach-Colton M.Finding frequent items in data streams[C]//Proceedings of automata,languages and programming.Berlin:Springer,2002:693-703.

[7] 李國徽,陳 輝.挖掘數(shù)據(jù)流任意滑動(dòng)時(shí)間窗口內(nèi)頻繁模式[J].軟件學(xué)報(bào),2008,19(10):2585-2596.

[8] Ma Ke,Li Lingjuan,Ji Yimu,et al.Research on parallelized stream data micro clustering algorithm[C]//Proceedings of ICCAET 2015.Zhengzhou,China:[s.n.],2015:629-634.

[9] Giannella C,Han J,Pei J,et al.Mining frequent patterns in data streams at multiple time granularities[J].Next Generation Data Mining,2003,212:191-212.

[10] 唐耀紅.數(shù)據(jù)流環(huán)境中關(guān)聯(lián)規(guī)則挖掘技術(shù)的研究[D].北京:北京交通大學(xué),2012.

[11] 劉學(xué)軍,徐宏炳,董逸生,等.挖掘數(shù)據(jù)流中的頻繁模式[J].計(jì)算機(jī)研究與發(fā)展,2015,42(12):2192-2198.

[12] 程轉(zhuǎn)流,王本年.數(shù)據(jù)流中的頻繁模式挖掘[J].計(jì)算機(jī)技術(shù)與發(fā)展,2007,17(12):53-55.

[13] Jin R,Agrawal G.An algorithm for in-core frequent itemset mining on streaming data[C]//Proceedings of fifth IEEE international conference on data mining.[s.l.]:IEEE,2005:210-217.

[14] Han J,Pei J,Yin Y,et al.Mining frequent patterns without candidate generation:a frequent-pattern tree approach[J].Data Mining and Knowledge Discovery,2004,8(1):53-87.

[15] Marz N.Storm:distributed and fault-tolerant realtime computation[EB/OL].2012.http://storm.apache.org.

[16] Apache.Apache Kafka:a high-throughput,distributed,publish-subscribe messaging system[EB/OL].2015.http://kafka.Apache.org.

Distributed Parallel Algorithm of Mining Frequent Pattern on Data Stream

MA Ke，LI Ling-juan，SUN Du-jing

(School of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

In order to improve the efficiency of mining frequent pattern on data stream,a Distributed Parallel Algorithm of Mining Frequent Pattern on Data Stream,named DPFP-Stream,is designed in this paper based on the ideas of classical FP-Stream and the distributed parallel computing.It divides the task of building frequent pattern tree into two parts:local and global,and introduces a new parameter “current time”.The arrival data will be equally distributed into different local nodes.Then every local node uses FP-Growth algorithm to produce candidate frequent items,and packages them with relevant support count according to unit time,and sends them to the global node.The global node combines the results produced by local nodes according to the “current time” and updates the global Pattern-Tree.The results of implementing DPFP-Stream algorithm and testing its performance on Storm,a distribution data stream computing platform,show that the computing efficiency of DPFP-Stream can increase linearly with the increasing of local nodes or the local bolts,and DPFP-Stream is applicable to effectively mine frequent pattern from data stream.

data stream;frequent pattern;distributed parallelization;Storm

2015-10-10

2016-01-20

時(shí)間：2016-06-22

國家自然科學(xué)基金資助項(xiàng)目(61302158，61571238)；中興通訊產(chǎn)學(xué)研項(xiàng)目

馬 可(1991-)，男，碩士研究生，CCF會(huì)員，研究方向?yàn)榱鲾?shù)據(jù)挖掘、信息安全；李玲娟，教授，CCF會(huì)員，通訊作者，研究方向?yàn)閿?shù)據(jù)挖掘、信息安全、分布式計(jì)算。

http://www.cnki.net/kcms/detail/61.1450.TP.20160621.1701.014.html

TP311

A

1673-629X(2016)07-0075-05

10.3969/j.issn.1673-629X.2016.07.16