王紅梅， 李芬田， 王澤儒

(長春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 吉林 長春 130012)

基于滑動(dòng)窗口數(shù)據(jù)流頻繁項(xiàng)集挖掘模型綜述

王紅梅， 李芬田*， 王澤儒

(長春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 吉林 長春 130012)

給出了頻繁項(xiàng)集和滑動(dòng)窗口的相關(guān)定義，根據(jù)數(shù)據(jù)流中不同的時(shí)序范圍對(duì)數(shù)據(jù)流模型進(jìn)行了分類，從數(shù)據(jù)處理模型的角度對(duì)滑動(dòng)窗口進(jìn)行了分類。分析了典型的頻繁項(xiàng)集挖掘算法中滑動(dòng)窗口的使用方法，總結(jié)了各模型中典型頻繁項(xiàng)集挖掘算法的挖掘技術(shù)和效率。

數(shù)據(jù)流； 頻繁項(xiàng)集； 滑動(dòng)窗口； 數(shù)據(jù)處理模型

1 理論基礎(chǔ)

數(shù)據(jù)流是一種潛在無限、快速、連續(xù)、隨時(shí)間不斷變化的數(shù)據(jù)序列[1]。數(shù)據(jù)流是一種新型的數(shù)據(jù)模型，至今為止已經(jīng)出現(xiàn)在許多種應(yīng)用中，如通信數(shù)據(jù)管理、網(wǎng)絡(luò)監(jiān)控、股票交易數(shù)據(jù)分析以及商品銷售分析等。與傳統(tǒng)的靜態(tài)數(shù)據(jù)相比，數(shù)據(jù)流具有無序性、連續(xù)性、實(shí)時(shí)性和無界性的特點(diǎn)[2]，使得數(shù)據(jù)流挖掘算法滿足以下幾個(gè)條件[3]：

1)當(dāng)分析數(shù)據(jù)流的時(shí)候，最多只能訪問一次所有的數(shù)據(jù)元素；

2)雖然在數(shù)據(jù)流中連續(xù)不斷地產(chǎn)生數(shù)據(jù)元素，但是必須滿足有限的分析數(shù)據(jù)流所需要的內(nèi)存空間；

3)新產(chǎn)生的數(shù)據(jù)必須盡可能快地處理，要求具有很高的算法實(shí)時(shí)性；

4)當(dāng)用戶提交查詢時(shí)，最新的數(shù)據(jù)流分析結(jié)果必須被快速并且及時(shí)反饋出來，它有很高的算法時(shí)間效率。因此在今后的發(fā)展中，數(shù)據(jù)流挖掘具有更大的挑戰(zhàn)意義。

在實(shí)際應(yīng)用中，近期數(shù)據(jù)是大部分人感興趣的焦點(diǎn)，所以在一般情況下，數(shù)據(jù)流的挖掘都是基于某個(gè)時(shí)間段內(nèi)對(duì)數(shù)據(jù)進(jìn)行挖掘和研究，從而出現(xiàn)了很多種不同的窗口模型。在此基礎(chǔ)上根據(jù)數(shù)據(jù)流中不同的時(shí)序范圍，可以把數(shù)據(jù)流的模型分為以下3種[4]：

1)界標(biāo)窗口模型。起始時(shí)間是固定的，而結(jié)束時(shí)間是變化的。

2)衰減窗口模型。起始時(shí)間和結(jié)束時(shí)間都是固定的。

3)滑動(dòng)窗口模型。起始時(shí)間和結(jié)束時(shí)間都是變化的。

基于衰減窗口模型和界標(biāo)窗口模型的挖掘，兩者都沒有考慮到數(shù)據(jù)流出所在模型的當(dāng)前窗口的數(shù)據(jù)情況，而且挖掘出來的結(jié)果會(huì)受到已經(jīng)過時(shí)的事務(wù)不同程度的影響，因此在實(shí)際應(yīng)用中，人們關(guān)注最多的還是滑動(dòng)窗口模型。

在挖掘頻繁項(xiàng)集的過程中，根據(jù)不同結(jié)果集的類型，數(shù)據(jù)流頻繁項(xiàng)集挖掘算法被分成3類[5]，分別是最大頻繁項(xiàng)集、頻繁閉項(xiàng)集和完全頻繁項(xiàng)集。文中完善了頻繁項(xiàng)集和滑動(dòng)窗口的相關(guān)定義；根據(jù)數(shù)據(jù)流中不同的時(shí)序范圍對(duì)數(shù)據(jù)流模型進(jìn)行分類；從數(shù)據(jù)處理模型的角度對(duì)滑動(dòng)窗口進(jìn)行分類；從基于界標(biāo)窗口、衰減窗口和滑動(dòng)窗口3種模型的角度總結(jié)了典型的頻繁項(xiàng)集挖掘算法的挖掘技術(shù)和效率。

定義1[6]設(shè)一個(gè)數(shù)據(jù)項(xiàng)I={I1,I2,…,Im}，數(shù)據(jù)流DS是一組大小可能是無限的并且一直連續(xù)不斷到達(dá)的數(shù)據(jù)項(xiàng)序列，記為DS={T1,T2,…,Ti,…,Tn,…}，其中Ti表示第i個(gè)到達(dá)的事務(wù)，而且對(duì)于任意一個(gè)Ti，都有Ti?I。

定義2對(duì)于任意的數(shù)據(jù)集T，如果有任何一個(gè)項(xiàng)集X?Ti(1≤i≤n)，則稱為事務(wù)Ti包含項(xiàng)集X，或者稱為項(xiàng)集X被包含于事務(wù)Ti，數(shù)據(jù)集T中包含項(xiàng)集X的事務(wù)個(gè)數(shù)叫做項(xiàng)集X的支持度，記為sup(X)。給定D和任意項(xiàng)集X，并給定最小支持度閾值min _sup，若sup(X)≥min _sup，則稱項(xiàng)集X為D上的完全頻繁項(xiàng)集，有時(shí)簡稱頻繁項(xiàng)集。D上所有頻繁項(xiàng)集的集合記為：FID={X|X?I∩sup(X)≥min _sup}。

定義3[7]給定一個(gè)滑動(dòng)窗口W和最小支持度min _sup，?X?I，如果滿足sup(X)≥min _sup,并且?(X?Y∩Y?I)，其中Y為項(xiàng)集X的超集，均有sup(Y)

定義4對(duì)于一個(gè)項(xiàng)集X，其閉項(xiàng)集就是它的直接超集的支持度計(jì)數(shù)都不等于它本身的支持度計(jì)數(shù)。在此同時(shí)如果閉項(xiàng)集是頻繁的，那它就稱為閉頻繁項(xiàng)集。

定義5[8]數(shù)據(jù)流DS被分成n(n>0)個(gè)數(shù)據(jù)塊，其中每個(gè)數(shù)據(jù)塊和數(shù)據(jù)流子序列相對(duì)應(yīng)，并且每個(gè)數(shù)據(jù)塊中包含的事務(wù)數(shù)一定，我們就說這樣的一個(gè)數(shù)據(jù)塊是一個(gè)基本窗口，記作W?；敬翱诘拇笮∈侵该總€(gè)基本窗口中包含的事務(wù)個(gè)數(shù)，記作|BW|。一系列連續(xù)的基本窗口組成一個(gè)滑動(dòng)窗口，用SW表示，記作，滑動(dòng)窗口的大小就是每個(gè)滑動(dòng)窗口中包含的基本窗口個(gè)數(shù)，記作|SW|。

2 數(shù)據(jù)流模型的分類

數(shù)據(jù)流中的頻繁項(xiàng)集挖掘是當(dāng)今數(shù)據(jù)挖掘領(lǐng)域的一個(gè)熱門話題，同時(shí)在實(shí)際應(yīng)用中人們感興趣的都是近期的數(shù)據(jù)。設(shè)計(jì)高效處理算法的基礎(chǔ)就是選擇合理的數(shù)據(jù)流模型，從而能夠改善數(shù)據(jù)流的處理速度。數(shù)據(jù)流的分析模型主要包括滑動(dòng)窗口、界標(biāo)窗口和衰減窗口模型。

2.1 滑動(dòng)窗口模型

設(shè)滑動(dòng)窗口的大小是W，在任意一時(shí)間點(diǎn)n，滑動(dòng)窗口模型的查詢范圍都是[max(0,n-w+1),n]，而處在查詢之外的所有數(shù)據(jù)將全部忽略不計(jì)，滑動(dòng)窗口模型主要源于人們對(duì)最新產(chǎn)生的數(shù)據(jù)比較感興趣，其主要特點(diǎn)是窗口會(huì)隨著數(shù)據(jù)流的產(chǎn)生而不斷向前移動(dòng)，這樣自然而然的就會(huì)丟棄過時(shí)的數(shù)據(jù)，有時(shí)候過時(shí)事務(wù)會(huì)影響數(shù)據(jù)流的處理結(jié)果，所以處理過時(shí)的事務(wù)成了滑動(dòng)窗口數(shù)據(jù)處理模型的挑戰(zhàn)。

滑動(dòng)窗口模型如圖1所示。

圖1 滑動(dòng)窗口模型

滑動(dòng)窗口模型中比較典型的算法是Chi[9]等提出的Moment算法，主要采用由非頻繁節(jié)點(diǎn)、無前途節(jié)點(diǎn)、中間節(jié)點(diǎn)和閉節(jié)點(diǎn)組成的CET樹來保存動(dòng)態(tài)的項(xiàng)集，同時(shí)在線更新CET樹中的所有節(jié)點(diǎn)，從而更新頻繁閉項(xiàng)集。劉學(xué)軍[10]等提出的滑動(dòng)窗口中頻繁閉項(xiàng)集的新算法DS-CFI,主要是以基本窗口為單位來更新滑動(dòng)窗口，并且利用已有的頻繁閉項(xiàng)集挖掘算法挖掘每個(gè)基本窗口的頻繁閉項(xiàng)集，再將挖掘出來的結(jié)果和它們的閉項(xiàng)集一起存儲(chǔ)到一種新的數(shù)據(jù)結(jié)構(gòu)DSCFI-tree中，最后通過DSCFI-tree的增量更新，來達(dá)到挖掘滑動(dòng)窗口中的所有頻繁閉項(xiàng)集的目的。黃國言[11]等提出MFCI-SW算法，主要是通過設(shè)計(jì)有支持度F和窗口序列號(hào)K組成的頻繁閉項(xiàng)集表FCIL和頻繁閉項(xiàng)集模式樹MFCI-SW-Tree，滑動(dòng)窗口每次滑動(dòng)的距離就是基本窗口的大小，并且在每個(gè)窗口中挖掘頻繁閉項(xiàng)集；當(dāng)新的基本窗口到來時(shí)，通過刪除最舊的基本窗口(也就是K值最小的窗口)中的數(shù)據(jù)項(xiàng)，然后插入最新的基本窗口中的事務(wù)項(xiàng)，通過以上過程來完成對(duì)FCIL的更新和MFCI-SW-Tree樹的裁剪，進(jìn)而完成在MFCI-SW-Tree中挖掘出頻繁閉項(xiàng)集的結(jié)果。楊路明[12]等提出了MMI-BET算法，主要采用位圖來存儲(chǔ)數(shù)據(jù)，利用新事務(wù)直接覆蓋舊事務(wù)的方法，并且在經(jīng)典剪枝的基礎(chǔ)上提出了子等價(jià)剪枝策略，為了提高超集的檢測效率，最后將挖掘出來的結(jié)果存儲(chǔ)在索引鏈表中。張?jiān)虑賉13]根據(jù)數(shù)據(jù)流的流動(dòng)性和連續(xù)性兩個(gè)顯著的特點(diǎn)，提出了滑動(dòng)窗口中的頻繁項(xiàng)集挖掘算法NSW，主要是滿足了人們能夠迅速獲取最新頻繁項(xiàng)集的需求，該算法中的事務(wù)是用二進(jìn)制矩陣表示的，窗口滑動(dòng)時(shí)通過直接刪除舊事務(wù)的不產(chǎn)生候選項(xiàng)集方法來達(dá)到節(jié)省時(shí)間和空間開銷的目的?？芟阆糩14]等提出了利用位表來存儲(chǔ)數(shù)據(jù)的概要結(jié)構(gòu)的FIUT-Stream算法，通過窗口的滑動(dòng)將動(dòng)態(tài)更新位表中的數(shù)據(jù)，最后利用FIUT算法來挖掘次頻繁k-項(xiàng)集，進(jìn)而挖掘出完全頻繁項(xiàng)集。

2.2 界標(biāo)窗口模型

界標(biāo)窗口模型主要是從某一個(gè)時(shí)間點(diǎn)t開始到當(dāng)前時(shí)間點(diǎn)T為止的數(shù)據(jù)集合，隨著數(shù)據(jù)流連續(xù)不斷的到達(dá)，界標(biāo)模型的窗口也會(huì)逐漸增大，隨著時(shí)間間隔的不斷增大，窗口中的數(shù)據(jù)會(huì)越來越多，這樣就會(huì)退化所有的歷史數(shù)據(jù)窗口；但是當(dāng)時(shí)間間隔很小的時(shí)候，處理的只是那些局部數(shù)據(jù)，很難適應(yīng)數(shù)據(jù)流的概念漂移性，如圖2所示。

圖2 界標(biāo)窗口模型

界標(biāo)窗口模型中比較經(jīng)典的算法是Manku[15]等提出的Lossy Counting算法，該算法是將數(shù)據(jù)流分成若干個(gè)事務(wù)數(shù)相等的桶，其中桶的大小受誤差參數(shù)的影響，該算法使用D(e,f,Δ)這樣的數(shù)據(jù)結(jié)構(gòu)來保存數(shù)據(jù)信息(其中，f為項(xiàng)集的頻率估計(jì)，Δ為最大誤差)，在桶的邊界對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行更新，刪除頻率低的數(shù)據(jù)項(xiàng)，同時(shí)產(chǎn)生的候選項(xiàng)集存儲(chǔ)在輔存中，通過以上方法可以挖掘出頻繁項(xiàng)和頻繁項(xiàng)集。張廣路[16]等提出了一種界標(biāo)窗口中數(shù)據(jù)流頻繁項(xiàng)集挖掘算法DSMFP_LW，主要是利用擴(kuò)展前綴模式樹來存儲(chǔ)全局臨界頻繁項(xiàng)集，以達(dá)到實(shí)現(xiàn)單邊掃描數(shù)據(jù)流和更新數(shù)據(jù)的目的。聞?dòng)⒂裑17]等為了克服na?ve算法在處理問題時(shí)不具備增量計(jì)算的缺點(diǎn)，提出了一種基于邊界界標(biāo)窗口技術(shù)的數(shù)據(jù)流最大規(guī)范模式挖掘DSMRM-BLW算法，主要是將數(shù)據(jù)流上的第一個(gè)將要處理的窗口定義為邊界界標(biāo)窗口，使用na?ve算法進(jìn)行處理，而后面的窗口可以基于前一個(gè)窗口的最大規(guī)范模式增量獲得。

2.3 衰減窗口模型

衰減窗口模型是隨著數(shù)據(jù)流的連續(xù)流入，降低最早流入的數(shù)據(jù)流的權(quán)值，這樣就能夠滿足人們對(duì)最新數(shù)據(jù)的興趣，同時(shí)也不會(huì)丟棄已經(jīng)流入的數(shù)據(jù)流。但是隨著數(shù)據(jù)流的不斷增加，有限的內(nèi)存是不可能存儲(chǔ)所有的數(shù)據(jù)，所以需要利用有效的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)數(shù)據(jù)，目的是提高空間的利用率。衰減窗口模型如圖3所示。

圖3 衰減窗口模型

Giannella[18]等提出的FP-stream頻繁項(xiàng)集挖掘算法是數(shù)據(jù)挖掘中衰減窗口處理模型的經(jīng)典算法，主要思想是將傾斜時(shí)間窗口表嵌入到序列信息頻繁模式樹中去，把近似支持度的時(shí)間敏感頻繁項(xiàng)集挖掘出來，在此基礎(chǔ)上也實(shí)現(xiàn)了多時(shí)間粒度的頻繁模式增量的維護(hù)，同時(shí)提出了“頻繁閉項(xiàng)集能夠提高一種不丟失支持度信息的最小單位的表示”，這樣在挖掘頻繁閉項(xiàng)集的過程中提高了空間和時(shí)間的復(fù)雜度。賴軍[19]等提出了一種新的基于字典順序的前綴樹LOP-Tree的頻繁項(xiàng)集挖掘算法STFWFI，該算法采用了符合網(wǎng)絡(luò)流特點(diǎn)的滑動(dòng)時(shí)間衰減窗口模型，在樹結(jié)構(gòu)上提出了一種新的基于統(tǒng)計(jì)分布的節(jié)點(diǎn)權(quán)值的計(jì)算方法SDNW來代替?zhèn)鹘y(tǒng)的統(tǒng)計(jì)方法。李國徽[20]等提出了一種新的MSW算法，該算法是在數(shù)據(jù)流過時(shí)，使用滑動(dòng)窗口樹SW-tree進(jìn)行一次掃描數(shù)據(jù)流的同時(shí)要及時(shí)捕獲數(shù)據(jù)流上最新的模式信息，SW-tree樹上不頻繁的模式和過時(shí)的事務(wù)可以被此方法刪除，該方法利用了時(shí)間衰減模型來依次降低歷史事務(wù)模式支持?jǐn)?shù)的權(quán)重，同時(shí)用此來區(qū)分最新事務(wù)和最舊事務(wù)的模式。吳楓[21]等提出了界標(biāo)窗口模型和時(shí)間衰減窗口模型相結(jié)合的數(shù)據(jù)流頻繁項(xiàng)集挖掘算法。主要是通過動(dòng)態(tài)構(gòu)建全局模式樹，然后利用時(shí)間指數(shù)衰減函數(shù)來對(duì)模式樹中各個(gè)模式的支持度進(jìn)行詳細(xì)統(tǒng)計(jì)，以此刻畫出界標(biāo)窗口內(nèi)模式的頻繁程度；為了有效降低空間開銷，設(shè)計(jì)了剪枝閾值函數(shù)，利用該方法可以刪除那些不頻繁的模式。

3 滑動(dòng)窗口模型分類

滑動(dòng)窗口從數(shù)據(jù)處理模型的角度分為以下幾類，分別是基于事務(wù)的滑動(dòng)窗口、基于時(shí)間戳的滑動(dòng)窗口、基于權(quán)值的滑動(dòng)窗口和可變滑動(dòng)窗口等。下面分別討論這4種滑動(dòng)窗口模型。

基于事務(wù)的滑動(dòng)窗口與基于時(shí)間戳的滑動(dòng)窗口如圖4所示。

圖4 基于事務(wù)的滑動(dòng)窗口與基于時(shí)間戳的滑動(dòng)窗口

3.1 基于事務(wù)的滑動(dòng)窗口

1)定義6設(shè)DS={T1,T2,…,Tn}表示數(shù)據(jù)流，若TWj={Tj,Tj+1,…,Tw+j-1}且TWj∈DS(即TWj是DS的一個(gè)子集)，W為窗口TWj的寬度，那么TWj就稱為基于事務(wù)的滑動(dòng)窗口，它也是一種比較傳統(tǒng)的滑動(dòng)窗口。

基于事務(wù)的可變滑動(dòng)窗口，一般情況下滑動(dòng)窗口的大小是變化的，并且它的大小隨著時(shí)間的變化而變化。因此，對(duì)于以絕對(duì)最小支持度作為閾值的方法我們不再使用，主要是因?yàn)樵趧?dòng)態(tài)變化的滑動(dòng)窗口中,不同時(shí)間段的事務(wù)分布不均勻，從而導(dǎo)致挖掘出來的結(jié)果準(zhǔn)確性不高。

2)相應(yīng)的算法。尹紹宏[22]等提出SWM-MFI算法，該算法同時(shí)引入了用于存儲(chǔ)事務(wù)數(shù)據(jù)的事務(wù)矩陣和用于存儲(chǔ)頻繁2-項(xiàng)集的二項(xiàng)集矩陣。通過二項(xiàng)集矩陣逐漸擴(kuò)展到頻繁k-項(xiàng)集。均由二進(jìn)制表示的這兩個(gè)矩陣，通過它們的子集檢測和一系列相關(guān)操作，快速挖掘出最大頻繁項(xiàng)集，并且將挖掘出來的結(jié)果存儲(chǔ)到數(shù)組MFI中。

宋威[23]等提出MHUIDS算法。它主要由4部分組成，分別是數(shù)據(jù)表示、窗口初始化、滑動(dòng)窗口和高效用項(xiàng)集挖掘，它的主要優(yōu)勢有：第一，構(gòu)造了與壓縮原始數(shù)據(jù)庫的樹型結(jié)構(gòu)不同的HTWUI-樹，HTWUI-樹的主要功能有兩個(gè)，一個(gè)是它可以有效且準(zhǔn)確地描述搜索空間，另一個(gè)是它能與二進(jìn)制向量一起合作來實(shí)現(xiàn)項(xiàng)集的枚舉和事務(wù)加權(quán)效用的計(jì)算；第二，降低了數(shù)據(jù)庫掃描開銷并且也減少候選事務(wù)加權(quán)效用的項(xiàng)集數(shù)量。

3.2 基于時(shí)間戳的滑動(dòng)窗口

1)定義7設(shè)DS={T1,T2,…,Tn}表示數(shù)據(jù)流，若在一個(gè)時(shí)間間隔T上的輸出關(guān)系滿足R(τ)={DS|∈DS∧(τ′≤τ)∧(τ′≥max{τ-T,0})}，T為數(shù)據(jù)流DS運(yùn)行時(shí)間的計(jì)算周期，那么就稱為基于時(shí)間戳的滑動(dòng)窗口。其中存在兩種特殊情況：當(dāng)T=0時(shí)，R(τ)由數(shù)據(jù)流DS中帶有時(shí)間戳τ的元素組成；當(dāng)T=時(shí)，R(τ)由數(shù)據(jù)流DS中所有時(shí)間戳τ≤T的元素組成。

在超市中，由于客流量在不同時(shí)間段基本上是不同的，在客流量高峰期，交易一般會(huì)集中出現(xiàn)，而在其它時(shí)段的客流量比較少。傳統(tǒng)的滑動(dòng)窗口模型的窗口大小是由事務(wù)的數(shù)量決定的。圖4展示的是數(shù)據(jù)流到達(dá)的情況，從圖中我們可以看到基于時(shí)間戳的滑動(dòng)窗口中數(shù)據(jù)的變化情況。如圖4(a)所示，假如用Ti表示超市中的半天時(shí)間，但是在T6結(jié)束的時(shí)候，管理員想了解一下當(dāng)天銷售情況的分析，也就是在這一天中，從T5時(shí)刻到T6時(shí)刻的銷售分析，那么有待分析的數(shù)據(jù)就是{ac,cd}，在這種情況下，滑動(dòng)窗口的大小是由時(shí)間戳來確定的，而且能夠精確、快速地定位用戶的需求，如圖4(c)展示的是基于時(shí)間戳的滑動(dòng)窗口模型的數(shù)據(jù)的變化情況，該模型能夠準(zhǔn)確、詳細(xì)地體現(xiàn)用戶對(duì)近期數(shù)據(jù)分析的需求。

2)相應(yīng)的算法。李海峰[24]等提出了一種頻繁項(xiàng)集挖掘算法FIMoTS，該算法具有高效性和精確性，它最大的特點(diǎn)是可以動(dòng)態(tài)地把項(xiàng)集分成幾類，因?yàn)榛瑒?dòng)窗口的大小是時(shí)刻變化的，所以可以根據(jù)它的變化來對(duì)項(xiàng)集進(jìn)行延遲處理，只有在項(xiàng)集的變化界限超出一個(gè)給定的閾值時(shí)，支持度才會(huì)被重新計(jì)算，從而實(shí)現(xiàn)剪枝的目的。主要貢獻(xiàn)有：第一，提出了與傳統(tǒng)滑動(dòng)窗口模型不同的基于時(shí)間區(qū)間的滑動(dòng)窗口模型，他們的不同主要體現(xiàn)在滑動(dòng)窗口大小的決定因素的不同，傳統(tǒng)窗口模型的窗口大小是由事務(wù)的數(shù)量來決定的，而基于時(shí)間區(qū)間的滑動(dòng)窗口也能更好地體現(xiàn)數(shù)據(jù)流的時(shí)間特性。第二，基于時(shí)間區(qū)間的滑動(dòng)窗口模型可以轉(zhuǎn)換成傳統(tǒng)的基于事務(wù)的可變的滑動(dòng)窗口模型，并根據(jù)該模型新定義了一個(gè)挖掘問題，那就是基于相對(duì)支持度的頻繁項(xiàng)集的挖掘問題。第三，最后還引入了類型變化界限的定義，動(dòng)態(tài)地把項(xiàng)集分成了幾類，通過對(duì)數(shù)據(jù)計(jì)算進(jìn)行推遲處理，提出的這個(gè)挖掘算法既能夠節(jié)省空間開銷，也能提高挖掘效率。

韓萌[25]等提出了一種基于時(shí)間衰減模型的數(shù)據(jù)流閉項(xiàng)集頻繁模式挖掘算法TDMCS，他們區(qū)分滑動(dòng)窗口中的歷史權(quán)重和新近事務(wù)的權(quán)重是根據(jù)時(shí)間衰減模型來區(qū)分的，采用閉合算子來提高閉合模式挖掘的效率；為了避免概念漂移，設(shè)計(jì)了一種最小支持度、最大誤差率和衰減因子這樣的三層架構(gòu)，設(shè)計(jì)一種均值衰減因子平衡算法的高查全率；該算法比較適合挖掘大小不同的滑動(dòng)窗口，同時(shí)對(duì)于那些長序列、長模式和高密度的數(shù)據(jù)流的挖掘也比較合適。

3.3 基于權(quán)值的滑動(dòng)窗口模型

1)定義8若存在一個(gè)窗口Wij，且每個(gè)窗口包含x1，x2，…，xk數(shù)據(jù)項(xiàng)，并且賦予窗口Wij的權(quán)值為aj，這樣的滑動(dòng)窗口被稱為基于權(quán)值的滑動(dòng)窗口。其中該模型允許用戶具體給定挖掘窗口的數(shù)量，窗口大小(周期性查詢的時(shí)間段定義為窗口大小，如窗口的大小為t)和每個(gè)窗口的權(quán)值。

基于權(quán)值的滑動(dòng)窗口數(shù)據(jù)處理模型如圖5所示。

圖5 基于權(quán)值的滑動(dòng)窗口數(shù)據(jù)處理模型

假設(shè)T1是當(dāng)前挖掘的時(shí)間點(diǎn)，滑動(dòng)窗口的數(shù)量是一個(gè)定值，設(shè)為4，并且每個(gè)窗口的大小是t。窗口W1j的權(quán)值aj分別如下：

假設(shè)在W11，W12，W13，W14中，數(shù)據(jù)項(xiàng)a的支持度計(jì)數(shù)分別是10，20，50和100；在W11，W12，W13，W14中，數(shù)據(jù)b的支持度計(jì)數(shù)分別是80，50，20和20。根據(jù)上面的定義可以得知，每個(gè)滑動(dòng)窗口的數(shù)據(jù)項(xiàng)a的權(quán)值支持度計(jì)數(shù)為

10×0.4+20×0.3+50×0.2+100×0.1=30

數(shù)據(jù)項(xiàng)b的權(quán)值支持度計(jì)數(shù)為

80×0.4+50×0.3+20×0.2+20×0.1=53

假設(shè)在窗口W11，W12，W13，W14中，分別包含的事務(wù)數(shù)量是300，200，200和300，最小的支持度為0.2。那么，在窗口W11，W12，W13，W14中，最小支持度計(jì)數(shù)分別是60，40，40和60。根據(jù)上面定義可知，最小的權(quán)值支持度計(jì)數(shù)是每個(gè)滑動(dòng)窗口中的權(quán)值與最小支持度計(jì)數(shù)乘積的總和。因此，最小的權(quán)值支持度計(jì)數(shù)為：

60×0.4+40×0.3+40×0.2+60×0.1=50

通過觀察數(shù)據(jù)項(xiàng)a和b可以得知，數(shù)據(jù)項(xiàng)a在窗口W11，W12，W13，W14中的支持度計(jì)數(shù)之和為180，但是它的權(quán)值支持度計(jì)數(shù)是30，并且我們也知道最小的權(quán)值支持度計(jì)數(shù)是50，因此可得權(quán)值支持度小于最小的權(quán)值支持度。從而得知，數(shù)據(jù)項(xiàng)a在該數(shù)據(jù)模型中是非頻繁項(xiàng)。同樣的道理可得數(shù)據(jù)項(xiàng)b在該數(shù)據(jù)模型中是頻繁項(xiàng)。

2)相應(yīng)的算法。白川平[26]等提出了基于權(quán)值滑動(dòng)窗口數(shù)據(jù)處理模型中的頻繁項(xiàng)集挖掘算法FIMWSW和改進(jìn)的算法FIMWSW-Imp，F(xiàn)IMWSW算法的主要特點(diǎn)就是它掃描數(shù)據(jù)庫的方式是進(jìn)行單邊掃描的，然后通過比較計(jì)算出來的候選項(xiàng)集的值來判斷它是不是頻繁項(xiàng)集。而改進(jìn)FIMWSW-Imp算法首先在前面的窗口就已經(jīng)判斷了該項(xiàng)集是否是頻繁項(xiàng)集，這樣就大大縮減了時(shí)間的開銷，從而提高挖掘效率。

3.4 可變的滑動(dòng)窗口

1)定義9若令(TSi,FTWi,TWi)表示一個(gè)分區(qū)窗口，TSi(TS是Timestamp的縮寫)表示每個(gè)事務(wù)到達(dá)的時(shí)刻，F(xiàn)TWi表示固定事務(wù)窗口和TWi表示可調(diào)時(shí)間窗口，如果滿足

VSW={(TS1,FTW1,TW1),(TS2,FTW2,TW2),…,(TSi,FTWi,TWi),…,(TSn,FTWn,TWn)}

其中(TSn,FTWn,TWn)是最近到達(dá)滑動(dòng)窗口的數(shù)據(jù)，那么就稱VSW是可變的滑動(dòng)窗口。

滑動(dòng)窗口結(jié)構(gòu)如圖6所示。

圖6 滑動(dòng)窗口結(jié)構(gòu)

2)相應(yīng)的算法。蘇勇[27]等提出了一種數(shù)據(jù)流頻繁項(xiàng)集挖掘算法DS-stream，并且該算法的滑動(dòng)窗口的大小是可變的，主要采用的是一種分區(qū)窗口機(jī)制，它的計(jì)算單位是以滑動(dòng)窗口中的分區(qū)窗口為標(biāo)準(zhǔn)，基本窗口和時(shí)間窗口兩者之間相結(jié)合，并且在考慮數(shù)據(jù)流的海量特性和時(shí)間特性基礎(chǔ)上，利用現(xiàn)成的頻繁閉項(xiàng)集挖掘算法來計(jì)算每個(gè)分區(qū)窗口的臨界頻繁閉合項(xiàng)集，將結(jié)果和子集動(dòng)態(tài)地壓縮存儲(chǔ)在DS-tree中，從而進(jìn)行數(shù)據(jù)的增量更新。DS-tree是通過FP-tree進(jìn)行一系列改進(jìn)而形成的一棵前綴壓縮樹，窗口的大小是根據(jù)數(shù)據(jù)流中數(shù)據(jù)分布的變化而變化的，因此它能夠自適應(yīng)調(diào)整滑動(dòng)窗口的大小，從而節(jié)省了空間與時(shí)間的浪費(fèi)和開銷。

4 結(jié) 語

數(shù)據(jù)流中挖掘頻繁項(xiàng)集是一個(gè)漫長的過程，它經(jīng)過了長期的研究與發(fā)展，并且已經(jīng)成為當(dāng)前研究領(lǐng)域中重要的研究方向，頻繁項(xiàng)集挖掘算法是關(guān)聯(lián)規(guī)則挖掘的關(guān)鍵，并且在頻繁項(xiàng)集挖掘算法的設(shè)計(jì)及優(yōu)化方面日趨成熟，廣泛應(yīng)用于通信數(shù)據(jù)管理、金融、網(wǎng)絡(luò)監(jiān)控等許多領(lǐng)域。文中總結(jié)了在該領(lǐng)域中，最近幾年來國內(nèi)外的研究成果；介紹了數(shù)據(jù)流及其頻繁模式挖掘的相關(guān)概念和特點(diǎn)，以及針對(duì)這些特點(diǎn)分析了數(shù)據(jù)流模型的發(fā)展?fàn)顩r和最新進(jìn)展。但是該領(lǐng)域在未來研究方向仍具有很大的挑戰(zhàn)性，今后可以考慮將該領(lǐng)域與其他跨學(xué)科領(lǐng)域合理結(jié)合起來，從而挖掘更有效的算法。

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

[2] Golab L, ?zsu M T. Issues in data stream management [J]. ACM Sigmod Record,2003,32(2):5-14.

[3] 陳輝.數(shù)據(jù)流頻繁模式挖掘及數(shù)據(jù)預(yù)測算法研究[D].武漢:華中科技大學(xué),2008.

[4] 段躍蘭.數(shù)據(jù)流閉合頻繁模式挖掘算法的研究[D].哈爾濱：哈爾濱工程大學(xué),2009.

[5] Han J, Pei J, Kamber M. Data mining: concepts and techniques [M]. [S.l.]: Elsevier,2011.

[6] 徐嘉莉,陳佳,胡慶,等.基于向量的數(shù)據(jù)流滑動(dòng)窗口中最大頻繁項(xiàng)集挖掘[J].計(jì)算機(jī)應(yīng)用研究,2012,29(3)：837-840.

[7] 顏躍進(jìn).最大頻繁項(xiàng)集挖掘算法的研究[D].長沙：國防科技大學(xué),2005.

[8] 劉潔,楊路明,毛伊敏,等.改進(jìn)的數(shù)據(jù)流頻繁閉項(xiàng)集挖掘算法[J].計(jì)算機(jī)工程,2011,37(9)：75-77.

[9] Chi Y, Wang H, Yu P S, et al. Moment: Maintaining closed frequent itemsets over a stream sliding window[C]//Data Mining, 2004, ICDM.04, Fourth IEEE International Conference on. IEEE,2004:59-66.

[10] 劉學(xué)軍,徐宏炳,董逸生,等.基于滑動(dòng)窗口的數(shù)據(jù)流閉合頻繁模式的挖掘[J].計(jì)算機(jī)研究與發(fā)展,2006,43(10):1738-1743.

[11] 黃國言,王立波,任家東.一種基于滑動(dòng)窗口的數(shù)據(jù)流頻繁閉項(xiàng)集挖掘算法[C]//第26屆中國數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集(B輯).2009,46(S):428-432.

[12] 楊路明,劉立新,毛伊敏,等.數(shù)據(jù)流中基于滑動(dòng)窗口的最大頻繁項(xiàng)集挖掘算法[J].計(jì)算機(jī)應(yīng)用研究,2010,27(2)：519-522.

[13] 張?jiān)虑?滑動(dòng)窗口中數(shù)據(jù)流頻繁項(xiàng)集挖掘方法[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(16):132-134.

[14] 寇香霞,任永功,宋奎勇.一種基于滑動(dòng)窗口的數(shù)據(jù)流頻繁項(xiàng)集挖掘算法[J].計(jì)算機(jī)應(yīng)用與軟件,2013,30(1):143-146.

[15] Manku G S, 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.

[16] 張廣路,雷景生,吳興惠.界標(biāo)窗口中數(shù)據(jù)流頻繁模式挖掘算法研究[J].計(jì)算機(jī)工程,2012,38(1):55-58,61.

[17] 聞?dòng)⒂?王少鵬,趙宏.界標(biāo)窗口下數(shù)據(jù)流最大規(guī)范模式挖掘算法研究[J].計(jì)算機(jī)研究與發(fā)展,2017,54(1):94-110.

[18] 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.

[19] 賴軍,李雙慶.挖掘滑動(dòng)時(shí)間衰減窗口中網(wǎng)絡(luò)流頻繁項(xiàng)集[J].計(jì)算機(jī)應(yīng)用研究,2011,28(3):895-898.

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

[21] 吳楓,仲妍,吳泉源.基于時(shí)間衰減模型的數(shù)據(jù)流頻繁模式挖掘[J].自動(dòng)化學(xué)報(bào),2010,36(5):674-684.

[22] 尹紹宏,單坤玉,范桂丹.滑動(dòng)窗口中數(shù)據(jù)流最大頻繁項(xiàng)集挖掘算法研究[J].計(jì)算機(jī)工程與應(yīng)用,2015，22:145-149.

[23] 宋威,劉明淵,李晉宏.基于事務(wù)型滑動(dòng)窗口的數(shù)據(jù)流中高效用項(xiàng)集挖掘算法[J].南京大學(xué)學(xué)報(bào)：自然科學(xué)版,2014(4)：494-504.

[24] 李海峰,章寧,朱建明,等.時(shí)間敏感數(shù)據(jù)流上的頻繁項(xiàng)集挖掘算法[J].計(jì)算機(jī)學(xué)報(bào),2012,35(11):2283-2293.

[25] 韓萌,王志海,原繼東.一種基于時(shí)間衰減模型的數(shù)據(jù)流閉合模式挖掘方法[J].計(jì)算機(jī)學(xué)報(bào),2015,38(7):1473-1483.

[26] 白川平.數(shù)據(jù)流頻繁項(xiàng)集挖掘算法的研究[D].蘭州：蘭州理工大學(xué),2014.

[27] 蘇勇,范玉玲.可變滑動(dòng)窗口在數(shù)據(jù)流頻繁模式挖掘上的應(yīng)用[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2011,20(6):200-202.

Asummaryoffrequentitem-setsminingmodelofdataflowbasedonslidingwindow

WANG Hongmei， LI Fentian*， WANG Zeru

(School of Computer Science & Engineering, Changchun University of Technology, Changchun 130012， China)

Definitions of frequent item-sets and sliding windows are given here. Data flow models are classified based on series in data stream. Sliding windows are categorized based on data processing model. Applications of sliding windows in typical frequent item-sets mining algorithms are analyzed. Finally, mining techniques and efficiency of typical frequent item-sets mining algorithms are discussed for each model.

data stream; frequent item-sets; sliding window; data processing model.

2017-02-20

吉林省科技廳發(fā)展計(jì)劃基金資助項(xiàng)目(20160415013JH)

王紅梅(1968-)，女，漢族，吉林圖們?nèi)?，長春工業(yè)大學(xué)教授，博士，主要從事數(shù)據(jù)挖掘與應(yīng)用及算法與程序設(shè)計(jì)方向研究,E-mail:2497545904@qq.com. *通訊作者：李芬田(1990-)，女，漢族，河北滄州人，長春工業(yè)大學(xué)碩士研究生，主要從事數(shù)據(jù)挖掘與應(yīng)用及算法與程序設(shè)計(jì)方向研究,E-mail:asytiantian@163.com.

10.15923/j.cnki.cn22-1382/t.2017.5.14

TP 301

A

1674-1374(2017)05-0484-07