王鑫 劉方愛(ài)

摘要：針對(duì)已有的多數(shù)據(jù)流協(xié)同頻繁項(xiàng)集挖掘算法存在內(nèi)存占用率高以及發(fā)現(xiàn)頻繁項(xiàng)集效率低的問(wèn)題，提出了改進(jìn)的多數(shù)據(jù)流協(xié)同頻繁項(xiàng)集挖掘（MCMDStream）算法。首先，該算法利用單遍掃描數(shù)據(jù)庫(kù)的字節(jié)序列滑動(dòng)窗口挖掘算法發(fā)現(xiàn)數(shù)據(jù)流中的潛在頻繁項(xiàng)集和頻繁項(xiàng)集；其次，構(gòu)建類(lèi)似頻繁模式樹(shù)（FPTree）的壓縮頻繁模式樹(shù)（CPTree）存儲(chǔ)已發(fā)現(xiàn)的潛在頻繁項(xiàng)集和頻繁項(xiàng)集，同時(shí)更新CPTree樹(shù)中每個(gè)節(jié)點(diǎn)生成的對(duì)數(shù)傾斜時(shí)間表中的頻繁項(xiàng)計(jì)數(shù)；最后，通過(guò)匯總分析得出在多條數(shù)據(jù)流中多次出現(xiàn)的且有價(jià)值的頻繁項(xiàng)集，即協(xié)同頻繁項(xiàng)集。相比AStream和HStream算法，MCMDStream算法不僅能夠提高多數(shù)據(jù)流中協(xié)同頻繁項(xiàng)集挖掘的效率，并且還降低了內(nèi)存空間的使用率。實(shí)驗(yàn)結(jié)果表明MCMDStream算法能夠有效地應(yīng)用于多數(shù)據(jù)流的協(xié)同頻繁項(xiàng)集挖掘。

關(guān)鍵詞：

流數(shù)據(jù)挖掘；多數(shù)據(jù)流；滑動(dòng)窗口；頻繁項(xiàng)集；協(xié)同頻繁項(xiàng)集

中圖分類(lèi)號(hào)： TP301.6 文獻(xiàn)標(biāo)志碼：A

0引言

隨著萬(wàn)維網(wǎng)技術(shù)的迅速發(fā)展，復(fù)雜多樣的數(shù)據(jù)呈現(xiàn)爆炸式增長(zhǎng)。數(shù)據(jù)流作為一種特殊形態(tài)的數(shù)據(jù)已在眾多領(lǐng)域中廣泛地應(yīng)用，例如網(wǎng)絡(luò)實(shí)時(shí)監(jiān)控的數(shù)據(jù)[1]、傳感器采集的數(shù)據(jù)[2]和金融市場(chǎng)的證券交易信息等。相對(duì)于傳統(tǒng)靜態(tài)數(shù)據(jù)而言，流數(shù)據(jù)具有實(shí)時(shí)、連續(xù)、大量、不確定和隨時(shí)間變化的特點(diǎn)，因此，在不斷變化的流數(shù)據(jù)上進(jìn)行頻繁項(xiàng)集挖掘更具有挑戰(zhàn)性。

近年來(lái)，流數(shù)據(jù)頻繁項(xiàng)集挖掘[3]成為研究的熱點(diǎn)問(wèn)題。1998年，Henzinger等[4]首次將流數(shù)據(jù)作為一種數(shù)據(jù)模型提出來(lái)。根據(jù)處理數(shù)據(jù)流時(shí)所采用的時(shí)序范圍，將數(shù)據(jù)流模型劃分為3個(gè)范疇：界標(biāo)模型、快照模型和滑動(dòng)窗口模型。以界標(biāo)模型為基礎(chǔ)，Manku等[5]提出了一種近似數(shù)據(jù)流頻繁項(xiàng)集挖掘（Lossy Counting）算法，該算法能夠有損耗地計(jì)算整個(gè)數(shù)據(jù)流中元素出現(xiàn)的近似頻率，但因其效率不高、動(dòng)態(tài)性不強(qiáng)；Yu等[6]提出了以假消極結(jié)果為導(dǎo)向在有限內(nèi)存中挖掘數(shù)據(jù)流中頻繁項(xiàng)集的流數(shù)據(jù)頻繁模式挖掘（Frequent Data Stream Pattern Mining， FDPM）算法，但是Lossy Counting和FDPM算法只能得到近似的結(jié)果，因此，從流數(shù)據(jù)中獲得當(dāng)前準(zhǔn)確頻繁項(xiàng)集的科研成果隨之涌現(xiàn)。Mozafari等[7]將滑動(dòng)窗口引入數(shù)據(jù)流的傳送中，并提出了一種新的技術(shù)概念Vertification，以此為基礎(chǔ)設(shè)計(jì)了根據(jù)滑動(dòng)窗口的大小調(diào)節(jié)性能和擴(kuò)展性的滑動(dòng)窗口增量挖掘（Sliding Window Incremental Miner， SWIM）算法。Leung等[8]構(gòu)造了一種能夠精確地挖掘數(shù)據(jù)流中頻繁項(xiàng)集的新型樹(shù)形索引結(jié)構(gòu)（Data Stream Tree，請(qǐng)補(bǔ)充DSTree的英文全稱(chēng)。 DSTree）。以上算法只針對(duì)單數(shù)據(jù)流頻繁項(xiàng)集的挖掘，但是結(jié)合當(dāng)前的諸多應(yīng)用，需要解決在多數(shù)據(jù)流環(huán)境[9-10]中頻繁項(xiàng)集挖掘的問(wèn)題，因此，Guo等[11]提出了HStream算法，目的是發(fā)現(xiàn)多數(shù)據(jù)流中的頻繁項(xiàng)集問(wèn)題。該算法以FPGrowth算法[12]為基礎(chǔ)挖掘單條數(shù)據(jù)流中的頻繁項(xiàng)集并將其頻數(shù)存儲(chǔ)于節(jié)點(diǎn)的自然傾斜時(shí)間窗口表中，通過(guò)匯總挖掘在多條數(shù)據(jù)流中多次出現(xiàn)的頻繁項(xiàng)集。在此過(guò)程中需要多遍掃描數(shù)據(jù)庫(kù)以及生成大量不必要的單位時(shí)間窗口，從而導(dǎo)致發(fā)現(xiàn)頻繁項(xiàng)集時(shí)既耗時(shí)又浪費(fèi)內(nèi)存占用空間。

針對(duì)上述HStream算法低效、內(nèi)存利用率不高的問(wèn)題，本文提出了一種基于滑動(dòng)窗口的多數(shù)據(jù)流協(xié)同頻繁項(xiàng)集挖掘（Mining Collaborative Frequent Itemsets in Multiple Data Stream， MCMDStream）算法。該算法首先通過(guò)基于字節(jié)序列的滑動(dòng)窗口挖掘（Ming Frequent Itemsets within a TimeInterval Sliding Window based on based on bitsequence， TISWMFI）算法發(fā)現(xiàn)數(shù)據(jù)流中的潛在頻繁項(xiàng)集和頻繁項(xiàng)集；然后構(gòu)建CPTree用來(lái)存儲(chǔ)多數(shù)據(jù)流中的頻繁項(xiàng)集和潛在頻繁項(xiàng)集，同時(shí)更新樹(shù)節(jié)點(diǎn)中對(duì)數(shù)傾斜時(shí)間表中項(xiàng)集對(duì)應(yīng)的頻數(shù)；最后匯總分析得出多數(shù)據(jù)流中的協(xié)同頻繁項(xiàng)集。與HStream算法中HTree的自然傾斜時(shí)間窗口表相比，MCMDStream算法中新引入的對(duì)數(shù)傾斜時(shí)間窗口表能夠增量更新CPTree；同時(shí)還能夠大量地減少節(jié)點(diǎn)總數(shù)，從而降低了算法的維護(hù)代價(jià)與空間復(fù)雜度；本文新引入的TISWMFI算法相比HStream中的FPGrowth而言，能夠減少對(duì)數(shù)據(jù)庫(kù)的遍歷次數(shù)以及查詢(xún)時(shí)間，因此，MCMDStream算法具有更強(qiáng)的適應(yīng)性和擴(kuò)展性。

1相關(guān)描述與問(wèn)題定義

設(shè)S={S1，S2，…，Sn}為一組數(shù)據(jù)流集合，其中：Si表示一組大量的連續(xù)到達(dá)的流數(shù)據(jù)d1j，d2j，…，dij的數(shù)據(jù)序列，dij（i≥1，1≤j≤n）表示在第i時(shí)刻第j條數(shù)據(jù)流的值。

定義1項(xiàng)集I[5]。令I(lǐng)={i1，i2，…，im}為所有項(xiàng)的非空集合，其中m為項(xiàng)集的長(zhǎng)度，包含k個(gè)項(xiàng)的項(xiàng)集稱(chēng)為k項(xiàng)集。例如項(xiàng)集{a，b}為2項(xiàng)集。

定義2事務(wù)數(shù)據(jù)流T[5]。表示一個(gè)連續(xù)的事務(wù)序列，即T=T1，T2，…，Tn，且TI。設(shè)Tid為事務(wù)數(shù)據(jù)流Ti的唯一標(biāo)識(shí)符，TUid為時(shí)間單位標(biāo)識(shí)符，事務(wù)T={TUid，Tid，Itemset}。

定義3滑動(dòng)窗口SW[4]。指在單位時(shí)間內(nèi)進(jìn)行滑動(dòng)的一個(gè)獨(dú)立窗口，其中單位時(shí)刻TUi包含一個(gè)變量，即SW=[TUn-w+1，TUn-w+2，…，TUn]。其中：n-w+1表示當(dāng)前滑動(dòng)窗口單位時(shí)間標(biāo)識(shí)號(hào)；w表示SW的總長(zhǎng)度，且w=TUn-w+1+TUn-w+2+…+TUn。

定義4頻繁項(xiàng)集（Frequent Itemset， FI）[4]。設(shè)項(xiàng)集X在滑動(dòng)窗口SW中的支持度為Sup（X）SW，若Sup（X）SW≥θ·w，則稱(chēng)X為一個(gè)頻繁項(xiàng)集（FI）。其中，θ（θ∈[0，1]）表示用戶(hù)自定義的最小支持度閾值。

定義5協(xié)同頻繁項(xiàng)集（Collaborative Frequent ItemsetCFI的英文全稱(chēng)補(bǔ)充得是否正確？請(qǐng)明確。， CFI）。設(shè)在給定數(shù)據(jù)流Si中的項(xiàng)集O，若tOSimax-tOSimin≤θ（tOSimax=max{t1，t2，…，tk}，tOSimin=min{t1，t2，…，tk}），則O是一個(gè)協(xié)同項(xiàng)集（Collaborative Itemset， CI）。若協(xié)同項(xiàng)集CI在隨后給定的時(shí)間里以同樣的方式在數(shù)據(jù)流集合Φ的數(shù)據(jù)流Si中頻繁出現(xiàn)，則稱(chēng)CI為一個(gè)協(xié)同頻繁項(xiàng)集。

定義6最大誤差因子ε。令ε在系統(tǒng)允許范圍內(nèi)控制算法精度。若ε≤Sup（X）SW≤θ，則項(xiàng)集X為潛在頻繁項(xiàng)集（Potential Frequent Itemset， PFI）；若Sup（X）SW≤ε，則項(xiàng)集X為非頻繁項(xiàng)集（UnFrequent Itemset請(qǐng)補(bǔ)充PFI、UFI的英文全稱(chēng)。， UFI）。PFI、UFI都是針對(duì)特定時(shí)間段定義的。例如，在時(shí)間段t1內(nèi)，項(xiàng)集X為FI；而在t2內(nèi)，X可能為PFI或UFI。

2算法描述

在本文中，將多數(shù)據(jù)流協(xié)同頻繁項(xiàng)集挖掘分為3步：

第1步利用新引入的TISWMFI算法從數(shù)據(jù)流中產(chǎn)生一組潛在頻繁項(xiàng)集以及頻繁項(xiàng)集；

第2步構(gòu)建一棵基于字典序列的前綴樹(shù)CPTree用來(lái)保存數(shù)據(jù)流中頻繁項(xiàng)集動(dòng)態(tài)的變化趨勢(shì)，在此重新設(shè)計(jì)了CPTree結(jié)構(gòu)，加入了對(duì)數(shù)傾斜時(shí)間窗口記錄FI的頻繁數(shù)；

第3步利用MCMDStream算法從潛在頻繁項(xiàng)集中發(fā)現(xiàn)協(xié)同頻繁項(xiàng)集。

2.1CPTree結(jié)構(gòu)

結(jié)構(gòu)上，CPTree由MTree、Header Table和Logarithmic Tilted Window三部分組成，該結(jié)構(gòu)如圖1所示。

1）MTree。記錄頻繁項(xiàng)集動(dòng)態(tài)變化的一棵字典序列前綴樹(shù)，用來(lái)存儲(chǔ)數(shù)據(jù)流中頻繁的和潛在頻繁的項(xiàng)集。

2）Header Table。一個(gè)指向MTree中不同層中節(jié)點(diǎn)指針的數(shù)組。利用Header Table，能夠高效地從MTree中挖掘出頻繁的和潛在頻繁的項(xiàng)集，減少更新樹(shù)中頻繁項(xiàng)集的時(shí)間，從而提高遍歷樹(shù)結(jié)構(gòu)的效率。

3）Logarithmic Tilted Window。為了進(jìn)一步地降低內(nèi)存占用率以及算法的空間復(fù)雜度，新增加了對(duì)數(shù)傾斜時(shí)間窗口LW?；瑒?dòng)窗口SW由大小固定且連續(xù)的LW序列組成，記為{LW1，LW2，…，LWm}。在每個(gè)時(shí)間間隔內(nèi)，LW為每個(gè)節(jié)點(diǎn)都創(chuàng)建了相對(duì)應(yīng)的時(shí)間窗口表保留頻繁項(xiàng)集的計(jì)數(shù)值。在n組數(shù)據(jù)流中，每個(gè)頻繁項(xiàng)所需操作的數(shù)是對(duì)整個(gè)數(shù)據(jù)流數(shù)據(jù)進(jìn)行操作的總數(shù)再除以N。

2.2TISWMFI算法

針對(duì)在有限的物理存儲(chǔ)空間挖掘頻繁項(xiàng)集會(huì)多次掃描數(shù)據(jù)庫(kù)的問(wèn)題，本文提出了一種新穎的單程掃描算法，即基于字節(jié)序列的滑動(dòng)窗口挖掘（Ming Frequent Itemsets within a TimeInterval Sliding Window based on sequence of bytes， TISWMFI）算法，目的是挖掘給定時(shí)間t中SW內(nèi)數(shù)據(jù)流Si的頻繁項(xiàng)集。TISWMFI將SW內(nèi)所有的數(shù)據(jù)項(xiàng)都以字節(jié)序列的形式表示，保證所有的項(xiàng)只被掃描一次，因此，該算法不僅能夠提高內(nèi)存利用率，而且還提高了動(dòng)態(tài)存儲(chǔ)事務(wù)的速度。

2.2.1字節(jié)序列表示法

字節(jié)序列表示法是指用二進(jìn)制位（0或1）表示在SW內(nèi)數(shù)據(jù)流Si的事務(wù)Ti中項(xiàng)X的支持度計(jì)數(shù)Sup（X）和出現(xiàn)的頻數(shù)fx，項(xiàng)X的字節(jié)序列表示為Bit（X）。設(shè)在當(dāng)前SW中項(xiàng)X存在于Ti中，則項(xiàng)X的第i位記為1，即Bit（X）=1；否則記為0，即Bit（X）=0。隨著窗口的不斷滑動(dòng)，需要維護(hù)項(xiàng)的字節(jié)序列，因此，在計(jì)算Sup（X）時(shí)，2個(gè)k項(xiàng)集的字節(jié)序列進(jìn)行“按位與”操作，便得到（k+1）項(xiàng)集（k≥0）的字節(jié)序列；而在進(jìn)行刪除操作時(shí)只需將原有的字節(jié)序列按位左移一位。該方法能夠使窗口快速地滑動(dòng)而且還能用較小的存儲(chǔ)空間保存所有項(xiàng)集出現(xiàn)的情況。

在滑動(dòng)窗口SW1和SW2中的事務(wù)數(shù)據(jù)流的項(xiàng)集字節(jié)序列為例。在表1中，SW1由〈T1，（abc）〉、〈T2，（bce）〉和〈T3，（abce）〉三條事務(wù)組成，并且項(xiàng)a在SW1的T1和T3中存在，因此Bit（a）=101、Bit（b）=111、Bit（c）=111、Bit（d）=000和Bit（e）=011。

2.2.2TISWMFI算法描述

TISWMFI算法由窗口初始化、窗口滑動(dòng)和頻繁項(xiàng)集生成3個(gè)階段組成。具體過(guò)程如下。

步驟1滑動(dòng)窗口初始化階段。當(dāng)SW=Null時(shí)，將單位時(shí)間TUi內(nèi)事務(wù)Ti中所有項(xiàng)按照字節(jié)序列表示法將其轉(zhuǎn)變?yōu)橄鄬?duì)應(yīng)的字節(jié)序列，直到SW=Full時(shí)結(jié)束。

步驟2窗口滑動(dòng)階段。在步驟1的基礎(chǔ)上，將項(xiàng)X的字節(jié)序列“按位左移”即可將當(dāng)前SW中失效事務(wù)中的項(xiàng)集移除。若Sup（X）SW=0，則可刪除項(xiàng)X。

步驟3頻繁項(xiàng)集產(chǎn)生階段。即已知的頻繁（K-1）項(xiàng)集以逐層迭代的方式構(gòu)成候選K項(xiàng)集，并將相應(yīng)的字節(jié)序列作“按位與”操作計(jì)算頻繁項(xiàng)集的支持度，即Bit（X）中字節(jié)1的總數(shù)。主要子步驟如下：

1）單遍掃描數(shù)據(jù)流Si，計(jì)算每個(gè)項(xiàng)的支持度，刪除支持度小于θ的項(xiàng)，構(gòu)成頻繁1項(xiàng)集FI1；

2）將兩個(gè)FI1以自連接的方式構(gòu)成包含候選2項(xiàng)集，保留支持度大于θ的項(xiàng)，形成頻繁2項(xiàng)集FI2；

3）以此類(lèi)推，逐層迭代，直到?jīng)]有新的頻繁項(xiàng)集產(chǎn)生為止。

滑動(dòng)窗口SW1和SW2四條事務(wù)數(shù)據(jù)流中的頻繁項(xiàng)集如表2所示，SW2由事務(wù)T2、T3和T4組成，現(xiàn)以SW2中頻繁項(xiàng)集生成過(guò)程為例。設(shè)θ=0.6，w=3，Sup（X）SW2=0.6×3=1.8。由此可得，Sup（b）=111、Sup（b）=3>1.8，Bit（c）=110、Sup（c）=2>1.8和Bit（e）=110、Sup（e）=2>1.8，即（b）、（c）和（e）構(gòu)成FI1；利用FI1執(zhí)行“按位與”操作，得到FI2，Bit（bc）=Bit（b） & Bit（c）=110、Sup（bc）=2，同理，Sup（be）=2、Sup（ce）=2；利用FI2執(zhí)行“按位與”操作，得到FI3，Bit（bce）=Bit（bc） & Bit（be） & Bit（ce），Sup（bce）=2>1.8，因此，F(xiàn)I3為（bce）。

2.3MCMDStream算法

MCMDStream算法將TISWMFI算法中發(fā)現(xiàn)的頻繁項(xiàng)集保存在CPTree中，由θ控制FI的數(shù)量，ε控制CPTree剪枝率；其次，通過(guò)插入新的FI、PFI和刪除UFI持續(xù)更新CPTree；最后，深度優(yōu)先遍歷CPTree發(fā)現(xiàn)多條數(shù)據(jù)流中的協(xié)同頻繁項(xiàng)集。假設(shè)n條數(shù)據(jù)流Si的集合Φ以批處理的方式挖掘，其中在時(shí)間間隔ti（i≥1）產(chǎn)生的第j（1≤j≤n）條數(shù)據(jù)流被標(biāo)記為dij，遍歷自定義數(shù)據(jù)結(jié)構(gòu)中的頻繁項(xiàng)集。多數(shù)據(jù)流協(xié)同頻繁項(xiàng)集挖掘算法偽代碼如下。

有序號(hào)的程序——————————Shift+Alt+Y

程序前

輸入：用戶(hù)自定義的最小支持度閾值θ；n條數(shù)據(jù)流集合S；最大誤差率ε；協(xié)同頻繁項(xiàng)集集合α。

輸出：協(xié)同頻繁項(xiàng)集。

//步驟1：Construct CPTree

1）

FI=Null， PFI=Null， i=1；

2）

for j=1 to n do

3）

FI= FI∪TISWMFI（dij，θ）；

PFI=CI∪TISWMFI（dij，θ，ε）；

4）

end for

5）

MTree=Initialize_MTree（FI，PFI）

//步驟2：Update CPTree

6）

While S≠Null do

7）

I=Null，i=i+1；

8）

Ci1，Ci2，…，Cin=Preprocessing（di1，di2，…，din，MTree，θ，ε）

9）

for j=1 to n do

10）

I=I∪TISWMFI（Cij）；

11）

end for

12）

MTree=Insert_CPTree（I），MTree=Prune_CPTree（MTree，θ，ε）；

13）

end while

//步驟3：Mining collaborative Frequent Itemsets across //Multiple Streams（在多數(shù)據(jù)流中挖掘協(xié)同頻繁項(xiàng)集）

14）

CFI=Collaboration_Mining（α）

15）

Output CFI

程序后

具體算法步驟如下。

步驟1利用TISWMFI算法從第一批數(shù)據(jù)流dij中提取FI和PFI。

步驟2構(gòu)造CPTree，并初始化CPTree的MTree、Header Table和Logarithmic Tilted Window。計(jì)算各項(xiàng)集在指定時(shí)間窗口內(nèi)的平均頻數(shù)并降序排列。將所有數(shù)據(jù)項(xiàng)E∈{FI∪PFI}插入到MTree中；同時(shí)將所有數(shù)據(jù)流中數(shù)據(jù)項(xiàng)E的頻繁項(xiàng)計(jì)數(shù)寫(xiě)入每個(gè)節(jié)點(diǎn)相對(duì)應(yīng)的對(duì)數(shù)時(shí)間窗口表中。根據(jù)頻繁計(jì)數(shù)對(duì)數(shù)據(jù)項(xiàng)E分類(lèi)，同時(shí)，在Header Table增加一個(gè)指針指向MTree每一層首節(jié)點(diǎn)。

步驟3利用最新的數(shù)據(jù)流更新MTree。該過(guò)程有如下4個(gè)子步驟：

1）預(yù)處理最新的數(shù)據(jù)流，刪除dij中的UFI。

2）查找項(xiàng)集I，在每一條被預(yù)處理的數(shù)據(jù)流中查找未被剪枝的項(xiàng)集。

3）將數(shù)據(jù)項(xiàng)集I插入MTree中，若I已插入樹(shù)中，則僅更新窗口表中相對(duì)應(yīng)數(shù)據(jù)項(xiàng)的計(jì)數(shù)值；否則，將在MTree插入I，同時(shí)更新CPTree的三部分。

4）調(diào)用末端剪枝函數(shù)Prune_CPTree（）刪除窗口末端的UFI。

步驟4當(dāng)所有的數(shù)據(jù)流更新完成后，深度優(yōu)先遍歷MTree，在多數(shù)據(jù)流集合Φ中挖掘協(xié)同頻繁項(xiàng)集CFI。

2.4算法性能分析

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

實(shí)驗(yàn)環(huán)境配置為：Windows 7 Professional操作系統(tǒng)，Intel Core CPU i33220 @2.93GHz，1TB RAM。使用Microsoft Visual C++ Version 6.0實(shí)現(xiàn)算法以及數(shù)據(jù)流模擬生成模塊。模擬實(shí)驗(yàn)主要從存儲(chǔ)代價(jià)、算法響應(yīng)時(shí)間、查準(zhǔn)率和查全率4個(gè)方面分別對(duì)AStream、HStream和MCMDStream算法進(jìn)行對(duì)比分析。其中AStream算法是基于Aprior算法的挖掘頻繁項(xiàng)集的算法，通過(guò)對(duì)數(shù)據(jù)流進(jìn)行多次掃描、自底向上的寬度優(yōu)先搜索得到協(xié)同頻繁項(xiàng)集的一種算法。測(cè)試數(shù)據(jù)集是由IBM Quest MarketBasket合成數(shù)據(jù)生成器產(chǎn)生的6條數(shù)據(jù)流。每條數(shù)據(jù)流中包含2000個(gè)事務(wù)，其中：TLen表示每個(gè)事務(wù)的平均長(zhǎng)度，NItems表示每個(gè)事務(wù)中每個(gè)項(xiàng)集的平均長(zhǎng)度，如表3所示。

3.1存儲(chǔ)代價(jià)

內(nèi)存使用量影響著算法的可擴(kuò)展性，將MCMDStream與另外兩個(gè)多數(shù)據(jù)流頻繁項(xiàng)集挖掘算法AStream和HStream進(jìn)行對(duì)比。假定在已處理的數(shù)據(jù)規(guī)模不變的情況下，測(cè)試IBM合成6條數(shù)據(jù)流分批到達(dá)構(gòu)建CPTree樹(shù)結(jié)構(gòu)時(shí)所產(chǎn)生的節(jié)點(diǎn)的總數(shù)。在最小支持度閾值和最大誤差率不變的前提下，分批處理事務(wù)數(shù)據(jù)流長(zhǎng)度為5～30，步長(zhǎng)為5。當(dāng)所有的數(shù)據(jù)項(xiàng)插入CPTree后，各算法生成樹(shù)節(jié)點(diǎn)的總數(shù)如圖2所示。

從圖2可得，MCMDStream算法中樹(shù)結(jié)構(gòu)生成的節(jié)點(diǎn)數(shù)量與AStream和HStream相比最少，因此所占用的內(nèi)存空間最小，算法的存儲(chǔ)空間最低，即MCMDStream算法的空間復(fù)雜度較小。這是因?yàn)锳Stream算法僅用ε控制樹(shù)的剪枝率，因此包含了大量的潛在頻繁項(xiàng)集，HStream使用θ與ε同時(shí)控制剪枝率，而MCMDStream算法在使用θ與ε控制CPTree剪枝率的基礎(chǔ)上采用對(duì)數(shù)傾斜時(shí)間窗口，減少了每個(gè)節(jié)點(diǎn)中時(shí)間窗口的數(shù)量，便于冗余剪枝。最終減小了樹(shù)結(jié)構(gòu)的內(nèi)存使用率，從而降低了存儲(chǔ)代價(jià)。

3.2算法響應(yīng)時(shí)間

該算法根據(jù)不同的支持度閾值產(chǎn)生不同的響應(yīng)時(shí)間。測(cè)試各算法在IBM合成的6條數(shù)據(jù)流的響應(yīng)時(shí)間。設(shè)在IBM數(shù)據(jù)集的支持度閾值變化范圍為1～5，步長(zhǎng)為1。實(shí)驗(yàn)結(jié)果分別如圖3所示。

從圖3中得出，HStream算法具有較高的事務(wù)敏感性。當(dāng)事務(wù)數(shù)據(jù)量逐漸增大時(shí)，該算法因受剪枝策略的影響會(huì)產(chǎn)生較冗余的分支。HStream算法是在FPGrowth算法的基礎(chǔ)上進(jìn)行頻繁項(xiàng)集挖掘，不僅需要掃描兩遍數(shù)據(jù)庫(kù)，而且還會(huì)產(chǎn)生大量的候選頻繁項(xiàng)集，因此在進(jìn)行挖掘過(guò)程中消耗大量的時(shí)間。MCMDStream算法是基于字節(jié)序列的滑動(dòng)窗口的頻繁項(xiàng)集挖掘，其在查詢(xún)過(guò)程中，只需建立一棵頻繁模式樹(shù)且只掃描一遍數(shù)據(jù)庫(kù)，因此節(jié)省了查詢(xún)響應(yīng)時(shí)間，從而降低了MCMDStream算法的時(shí)間復(fù)雜度，查詢(xún)效率高于HStream和AStream。

3.3查準(zhǔn)率和查全率

最大誤差值ε是算法中一項(xiàng)重要的剪枝參數(shù)，查準(zhǔn)率是指算法發(fā)現(xiàn)的實(shí)際協(xié)同頻繁項(xiàng)集數(shù)與算法發(fā)現(xiàn)輸出數(shù)量的百分比，而查全率則為算法發(fā)現(xiàn)的實(shí)際協(xié)同頻繁項(xiàng)集數(shù)與真實(shí)數(shù)量的百分比。挖掘數(shù)據(jù)集的協(xié)同頻繁項(xiàng)集以最大誤差值ε作為剪枝參數(shù)，在更新樹(shù)結(jié)構(gòu)時(shí)能夠影響算法的查準(zhǔn)、查全率。圖4～5分別評(píng)估了在IBM合成的6條數(shù)據(jù)流中不同誤差值對(duì)算法查準(zhǔn)、查全率的影響。假定誤差值ε分別為0.0002，0.0008，0.0014和0.002時(shí)IBM合成數(shù)據(jù)流中S1、S2和S3三條數(shù)據(jù)流的查準(zhǔn)率和查全率。

從圖4和圖5中可以看出，對(duì)于不同的誤差值，MCMDStream算法的查準(zhǔn)率和查全率高于其他算法。當(dāng)誤差值增大時(shí)，頻繁項(xiàng)集的數(shù)量減少，因此用戶(hù)指定的誤差值越大，頻繁項(xiàng)集數(shù)量越少，挖掘多條數(shù)據(jù)流中的協(xié)同頻繁項(xiàng)集時(shí)的準(zhǔn)確率和查全率就會(huì)越高。

4結(jié)語(yǔ)

本文提出了一種能夠高效地挖掘多數(shù)據(jù)流協(xié)同頻繁項(xiàng)集的MCMDStream算法。該算法不僅能夠減小內(nèi)存利用率、縮短挖掘的查詢(xún)響應(yīng)時(shí)間，而且還可以提高算法的查準(zhǔn)率和查全率。模擬實(shí)驗(yàn)利用IBM合成數(shù)據(jù)集驗(yàn)證了該算法的性能優(yōu)于AStream和HStream算法，能夠很好地應(yīng)用于多數(shù)據(jù)流協(xié)同頻繁項(xiàng)集的挖掘，但是本文只考慮了單機(jī)上的多數(shù)據(jù)流頻繁項(xiàng)集挖掘問(wèn)題，在今后的研究中，將采用分布式集群這一有效的途徑，實(shí)現(xiàn)大規(guī)模多數(shù)據(jù)流中協(xié)同頻繁項(xiàng)集發(fā)現(xiàn)問(wèn)題。

參考文獻(xiàn)：

[1]

BHATTACHARYA S， MOON S. Network performance monitoring and measurement： techniques and experience [M]// Universal Access in HumanComputer Interaction. Access to Interaction. Berlin： Springer， 2015： 528-537.

[2]

王爽，王國(guó)仁.面向不確定感知數(shù)據(jù)的頻繁項(xiàng)查詢(xún)算法[J].計(jì)算機(jī)學(xué)報(bào)，2013，36（3）：571-581.（WANG S， WANG G R. Frequent items query algorithm for uncertain sensing data [J]. Chinese Journal of Computers， 2013， 36（3）： 571-581.）

[3]

金澈清，錢(qián)衛(wèi)寧，周傲英.流數(shù)據(jù)分析與管理綜述[J].軟件學(xué)報(bào)，2004，15（8）：1172-1181.（JIN C Q， QIAN W N， ZHOU A Y. Analysis and management of streaming data [J]. Journal of Software， 2004， 15（8）： 1172-1181.

[4]

HENZINGER M R， RAGHAVAN P， RAJAGOPALAN S. Computing on data streams [C]// Proceedings of the 1999 External Memory Algorithms： DIMACS Workshop External Memory and Visualization. Boston： American Mathematical Society， 1999： 107-118.

[5]

MANKU G， MOTWANI R. Approximate frequency counts over data streams [C]// Proceedings of the 28th International Conference on Very Large Data Bases. [S.l.]： VLDB Endowment， 2002： 346-357.

[6]

YU J， CHONG Z， LU H， et al. False positive or false negative： mining frequent itemsets from high speed transactional data streams [C]// Proceedings of the Thirtieth International Conference on Very Large Data Bases. [S.l.]： VLDB Endowment， 2004： 204-215.

[7]

MOZAFARI B， THANKKAR H， ZANIOLO C. Verifying and mining frequent patterns from large windows over data streams [C]// ICDE 2008： Proceedings of the IEEE 24th International Conference on Data Engineering. Piscataway， NJ： IEEE， 2008： 179-188.

[8]

LEUNG C K S， KHAN Q. DSTree： a tree structure for the mining of frequent sets from data streams [C]// ICDM06： Proceedings of the 2006 Sixth International Conference on Data Mining. Piscataway， NJ： IEEE， 2006： 928-932.

[9]

HRISTIDIS V， VALDIVIA O， VLACHOS M， et al. Information discovery across multiple streams [J]. Information Sciences， 2009， 179（19）： 3268-3285.

[10]

YEH M Y， DAI B R， CHEN M S. Clustering over multiple evolving streams by events and correlations [J]. IEEE Transactions on Knowledge and Data Engineering， 2007， 19（10）： 1349-1362.

[11]

GUO J， ZHANG P， TAN J， et al. Mining frequent patterns across multiple data streams [C]// Proceedings of the 20th ACM International Conference on Information and Knowledge Management. New York： ACM， 2011： 2325-2328.

[12]

HAN J， PEI J， YIN Y， et al. Mining frequent patterns without candidate generation： a frequentpattern tree approach [J]. Data Mining and Knowledge Discovery， 2004， 8（1）： 53-87.

[13]

CHANG J H， LEE W S. Finding recent frequent itemsets adaptively over online data streams [C]// Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2003： 487-492.

[14]

AGRAWAL R， SRIKANT R. Privacypreserving data mining [C]// Proceedings of the 2009 ACM SIGMOD Record. New York： ACM， 2000， 29（2）： 439-450.

[15]

BERNECKER T， CHENG R， CHEUNG D W， et al. Modelbased probabilistic frequent itemset mining [J]. Knowledge and Information Systems， 2013， 37（1）： 181-217.