聞英友 王少鵬 趙 宏

1(東北大學(xué)計算機科學(xué)與工程學(xué)院 沈陽 110819)2(內(nèi)蒙古大學(xué)計算機學(xué)院 呼和浩特 010021)3 (醫(yī)學(xué)影像計算教育部重點實驗室(東北大學(xué)) 沈陽 110819)(wangshaopeng1984@163.com)

界標(biāo)窗口下數(shù)據(jù)流最大規(guī)范模式挖掘算法研究

聞英友1,3王少鵬1,2趙 宏1,3

1(東北大學(xué)計算機科學(xué)與工程學(xué)院 沈陽 110819)2(內(nèi)蒙古大學(xué)計算機學(xué)院 呼和浩特 010021)3(醫(yī)學(xué)影像計算教育部重點實驗室(東北大學(xué)) 沈陽 110819)(wangshaopeng1984@163.com)

首次對界標(biāo)窗口下數(shù)據(jù)流最大規(guī)范模式挖掘問題進行了研究.為了克服na?ve算法在處理該問題時不具有增量計算的缺點，提出了一種基于邊界界標(biāo)窗口技術(shù)的數(shù)據(jù)流最大規(guī)范模式挖掘(data stream maximal regular patterns mining based on boundary landmark window, DSMRM-BLW)算法.該算法將數(shù)據(jù)流上的第1個待處理窗口定義為邊界界標(biāo)窗口，使用na?ve算法對其進行處理；之后每個窗口上的最大規(guī)范模式都可以基于前一個窗口上的最大規(guī)范模式集合增量獲得，可以克服na?ve算法的缺點.實驗結(jié)果表明:DSMRM-BLW算法是處理界標(biāo)窗口下數(shù)據(jù)流最大規(guī)范模式挖掘的有效方法，與na?ve算法相比，具有相同的執(zhí)行結(jié)果，但時間與空間效率得到了很大的提高.

數(shù)據(jù)流；界標(biāo)窗口；最大規(guī)范模式；增量計算；邊界界標(biāo)窗口技術(shù)

隨著數(shù)據(jù)流應(yīng)用的不斷增多，挖掘數(shù)據(jù)流中用戶感興趣的模式已然成為數(shù)據(jù)流挖掘領(lǐng)域中一類非常重要的問題[1].現(xiàn)有相關(guān)研究關(guān)注較多的是頻繁模式的挖掘[1-5]，但這些研究存在一個共同問題就是所挖掘模式的判別標(biāo)準(zhǔn)是它們在數(shù)據(jù)流區(qū)間中的出現(xiàn)次數(shù)，而并不是模式本身的出現(xiàn)行為(如模式是否周期性、規(guī)律性地出現(xiàn))，所以對于很多更注重模式出現(xiàn)行為的實際應(yīng)用來說，這些研究無法有效解決它們當(dāng)中所涉及到的問題.比如在超市等銷售行業(yè)中，管理人員要獲得一年中常態(tài)情況下貨物的銷售情況，這種常態(tài)通常是指貨物的銷售具有規(guī)律性、周期性且銷售的周期不長.如果我們使用挖掘頻繁模式的方法來處理這個問題，對于像夏天的電扇和蚊香、冬天的電熱寶、雨季的雨具等在一年中某些特定時段內(nèi)銷售頻繁的貨物，也會因為達到頻繁標(biāo)準(zhǔn)而被選擇出來，但顯然它們并不是一年中滿足常態(tài)銷售這樣條件的貨物，所以并不是此時我們關(guān)注的對象.像實例中這樣要求出現(xiàn)具有規(guī)律性、周期性的模式通常被稱為規(guī)范模式(regular pattern)[6-12].而類似應(yīng)用場景的存在也使挖掘規(guī)范模式的研究顯得非常必要.

根據(jù)模式規(guī)范度的度量標(biāo)準(zhǔn)不同，現(xiàn)有規(guī)范模式可分為2類：1)以模式發(fā)生周期序列中的最大值作為規(guī)范度的規(guī)范模式;2)以模式發(fā)生周期序列的方差作為規(guī)范度的規(guī)范模式.比較起來前者更有時間優(yōu)勢，而后者精確度更高.Tanbeer等人在文獻[1]中對數(shù)據(jù)流環(huán)境下第1類規(guī)范模式的挖掘問題進行了研究，給出了基于RPS-tree的處理算法；接著Tanbeer等人又在文獻[6]中對規(guī)范模式的增量挖掘處理機制進行了研究，提出了一種基于IncRT樹的規(guī)范模式挖掘算法，只需單遍掃描所關(guān)注的數(shù)據(jù)內(nèi)容就可以構(gòu)建IncRT樹，接著基于該樹以模式增長的方法獲得規(guī)范模式；Kumar等人在文獻[7]中對于數(shù)據(jù)流環(huán)境下基于窗口的第1類規(guī)范模式挖掘算法進行了研究，提出了VDSRP算法，該算法采用垂直數(shù)據(jù)格式組織窗口中的數(shù)據(jù)，通過類Aprior方法搜索可能的結(jié)果模式，在這個過程中通過比較這些模式規(guī)范度與用戶給定的規(guī)范閾值來確定該模式是否是規(guī)范模式，能夠有效地處理滑動窗口下數(shù)據(jù)流的規(guī)范模式挖掘問題；Verma等人在文獻[8]中對VDSRP算法進行了改進，主要改進點在于進一步使用了bit-sequence來組織窗口中的數(shù)據(jù)，基于窗口中項的bit-sequence執(zhí)行位操作來獲得相關(guān)模式規(guī)范度，提高了算法執(zhí)行效率.很多研究還把這類規(guī)范模式與頻繁模式二者結(jié)合起來.如Kumar等人在文獻[9]中給出了滑動窗口下基于該規(guī)范度的數(shù)據(jù)流規(guī)范頻繁模式挖掘方法RFPDS算法，該算法采用垂直數(shù)據(jù)格式組織窗口中的數(shù)據(jù)，只計算頻繁模式的規(guī)范度，通過與用戶給定的規(guī)范閾值進行比較來確定該模式是否是規(guī)范頻繁模式，能夠有效地處理滑動窗口下數(shù)據(jù)流的規(guī)范頻繁模式挖掘問題.Sreedevi等人在文獻[10]中首次提出了用于處理滑動窗口下基于該規(guī)范度的數(shù)據(jù)流規(guī)范閉模式挖掘算法，該算法將整個規(guī)范頻繁閉模式的求解過程分為2個階段：第1個階段求解規(guī)范模式集合；第2個階段在此基礎(chǔ)上得到規(guī)范頻繁閉模式，可以有效處理這類問題.當(dāng)前有關(guān)第2類規(guī)范模式的研究是將規(guī)范模式與頻繁模式結(jié)合起來展開.如Rashid等人在文獻[11]中對靜態(tài)數(shù)據(jù)庫下基于這種規(guī)范度的規(guī)范頻繁模式挖掘問題進行了研究，并給出了相應(yīng)的處理方法，該方法中使用基于成員出現(xiàn)頻率遞減順序的RF-tree來存放數(shù)據(jù)庫中成員信息，另外使用類FP-growth算法的方式挖掘樹中的規(guī)范頻繁模式；Rashid等人在文獻[12]中設(shè)計了用于尋找傳感網(wǎng)絡(luò)中規(guī)范頻繁傳感器模式的RSP-tree數(shù)據(jù)結(jié)構(gòu)，使用模式出現(xiàn)周期序列的方差作為模式的規(guī)范度，并給出了相應(yīng)的挖掘算法，能夠有效地應(yīng)用于該領(lǐng)域規(guī)范頻繁傳感模式的挖掘.

由文獻[1,13]可知，規(guī)范模式具有向下閉包的特點，即如果一個模式是規(guī)范的，那么它所有的非空子模式也都是規(guī)范的，所以在挖掘數(shù)據(jù)集中的規(guī)范模式時，如果我們只定性地關(guān)注哪些模式是規(guī)范的而不在意它們的具體規(guī)范度，那么完全可以通過挖掘其中所有長度最大的規(guī)范模式來提高挖掘效率.這些長度最大的規(guī)范模式間彼此并不包含，但能保證數(shù)據(jù)集中任何一個規(guī)范模式都是這些長度最大規(guī)范模式集合中某個成員的子集，我們把這類長度最大的規(guī)范模式稱為最大規(guī)范模式.由規(guī)范模式的閉包性可知一個數(shù)據(jù)集上所有的最大規(guī)范模式隱含了這個數(shù)據(jù)集上所有的規(guī)范模式，但數(shù)量卻比全部規(guī)范模式要少，這點與頻繁模式和最大頻繁模式間的關(guān)系類似.但由前面分析可知，當(dāng)前還沒有這個方向的研究.

本文基于這點，首次對以模式周期最大值作為規(guī)范度的界標(biāo)窗口下數(shù)據(jù)流最大規(guī)范模式挖掘問題進行了研究.為了能增量地處理這個問題，本文分析了相鄰窗口上最大規(guī)范模式間的關(guān)系，提出了邊界界標(biāo)窗口技術(shù)，接著在此技術(shù)基礎(chǔ)之上給出了該問題的增量處理方法DSMRM-BLW(data stream maximal regular patterns mining based on border landmark window)算法，一系列公用數(shù)據(jù)集上的實驗證明了該算法的有效性.

1 相關(guān)知識

1.1 IncRT算法

IncRT算法是由Tanbeer等人在文獻[1]中提出的一種目前唯一用于增量挖掘數(shù)據(jù)庫中規(guī)范項集(或規(guī)范模式)的方法.該方法可以在當(dāng)前數(shù)據(jù)庫成員規(guī)范項集集合的基礎(chǔ)上增量獲得新數(shù)據(jù)成員到來后的數(shù)據(jù)庫中規(guī)范項集集合.整個算法通過1個IncRT樹來維護數(shù)據(jù)庫中的成員信息，該樹以字典順序存放每一條數(shù)據(jù)記錄.樹中每條記錄的尾結(jié)點存放著該記錄在數(shù)據(jù)庫中的索引號，以此標(biāo)識該記錄在數(shù)據(jù)庫中的發(fā)生情況.樹中還維護著1個增量規(guī)范表IncR-table，每個表項分為5個域，i域用于存放樹中項的名稱，IncR-table中該域中成員的排列順序與樹中項的排列順序相同；r域是該項在樹中的規(guī)范度；tl域是該項最近發(fā)生的記錄索引；m域是該項的修改標(biāo)識域；p域是1個指針域，用于指向樹中具有相同項名的結(jié)點，樹中所有具有相同項名的結(jié)點間也有指針彼此連接.在IncRT的構(gòu)造過程中，頭表中除了項的r域外，其他域值都可以設(shè)定.當(dāng)樹構(gòu)造完成后，借助為每個項分配的臨時數(shù)組結(jié)構(gòu)，按照由下而上的順序完成對樹的1次掃描后得到每個項的r域值.當(dāng)樹的構(gòu)造完成后，按照FP-growth模式增長挖掘技術(shù)來獲得所有規(guī)范項集，保留所有規(guī)范項集成員.之后重置頭表成員的m域值.接著把新到來的數(shù)據(jù)成員插入到IncRT中，這個過程中重新設(shè)定頭表中成員的m域值；對于新的IncRT，只對IncR-table中m域發(fā)生變化的項使用FP-growth算法進行挖掘，假設(shè)得到的規(guī)范項集集合為A.對于前一個窗口上的規(guī)范項集集合，找到其中不包含IncR-table中m域發(fā)生變化項的項集，如果在更新它們規(guī)范度后得到的規(guī)范項集集合為B，則A∪B即為當(dāng)前數(shù)據(jù)庫上的規(guī)范項集集合.有關(guān)該算法更詳細(xì)的說明可參見文獻[6].

1.2 PA算法

PA算法是由Verma等人在文獻[8]中提出的一種對數(shù)據(jù)流滑動窗口下以項集周期最大值作為規(guī)范度的規(guī)范項集(或規(guī)范模式)進行挖掘的算法.該算法使用垂直格式組織窗口中的數(shù)據(jù)流成員，不僅如此，該算法還基于當(dāng)前窗口中每個項在窗口數(shù)據(jù)流成員中的出現(xiàn)狀況，定義了這些項在當(dāng)前窗口中的bit-sequence.基于這些bit-sequence，PA算法采用Aprior算法思想可以求得當(dāng)前窗口中所有項集的bit-sequence.因為基于bit-sequence中非0成員的位置情況，可以得到對應(yīng)項集在當(dāng)前窗口中的規(guī)范度，所以該算法可以求得當(dāng)前窗口中所有項集的規(guī)范度，進而得到所有規(guī)范項集.關(guān)于該算法更詳細(xì)的情況，可參考文獻[8].

2 基本概念和問題說明

2.1 基本概念

設(shè)SI={I1,I2,…,Im}是m個項的集合，Ii是第i個項，I中的所有成員按全序(字典序)排列.任給集合P，如果P?SI且l=|P|(即P中含有l(wèi)個SI的成員)，則稱P為l模式，P的長度為l.ST={T1,T2,…,Tn}是事務(wù)集，其中Ti?SI，也即Ti為SI的子集.

定義1. 模式發(fā)生周期[1].任給模式P，令Ti，Tj是事務(wù)集ST中2個包含P的事務(wù)，且在Ti與Tj間沒有任何包含P的其他事務(wù)存在，則i與j的差值被稱為P的一個發(fā)生周期.

定義2. 模式發(fā)生周期集合[1].令SP是ST中所有包含模式P的事務(wù)集合，|SP|是SP中的事務(wù)總數(shù)，這里規(guī)定null事務(wù)(該事務(wù)為ST中第0個事務(wù)，索引值為ST中第1個事務(wù)的索引值-1)和ST中最后一個事務(wù)分別是SP中的第1個和最后1個事務(wù)，它們和ST中其他所有包含P的事務(wù)一起構(gòu)成了SP，SP中所有事務(wù)按它們在ST中的索引遞增排列.如果設(shè)Trank與Trank+1分別是SP中任意2個相鄰事務(wù)，它們在ST中的索引分別為Trank.index與Trank+1.index，則CP={Trank+1.index-Trank.index|1≤k≤|SP|-1，k∈+}是P在ST中的發(fā)生周期集合.

定義3. 規(guī)范模式[1].模式P在ST中的規(guī)范度被定義為CP中成員的最大值，表示為RP，即有RP=max(CP).對于用戶給定的最大規(guī)范閾值λ(1≤λ≤|ST|)，如果RP≤λ，則P是ST中一個規(guī)范模式；如果P的長度為1，則P又被稱為ST中的一個規(guī)范項.

定義4. 最大規(guī)范模式.對于模式P，如果滿足條件Rp≤λ，同時對于任意滿足條件Y?SI且P?Y的模式Y(jié)，均有RY>λ成立，則稱P為ST上的最大規(guī)范模式.

定義5. 數(shù)據(jù)流DS[1].數(shù)據(jù)流DS是一個由連續(xù)到來的事務(wù)組成的事務(wù)序列，表示為DS={T1,T2,…,Ti,…}.Ti為第i個到來的事務(wù).

定義6. 基本窗口(element window,EW)與界標(biāo)窗口(landmark window,LW).EW是一個確定時間內(nèi)連續(xù)到達的數(shù)據(jù)流成員，即EW={Ti,Ti+1,…,Tj}(0

2.2 問題說明

參照文獻[6]中關(guān)于增量挖掘規(guī)范模式的說明，我們可以給出本文要處理問題的說明，即給定數(shù)據(jù)流DS、基本窗口大小|EW|、最大規(guī)范閾值λ(1≤λ≤|EW|)、界標(biāo)窗口起始位置sp，本文要解決的問題就是獲得起始位置為sp的每個界標(biāo)窗口上所有的最大規(guī)范模式.

3 基于邊界界標(biāo)窗口技術(shù)的數(shù)據(jù)流最大規(guī)范模式挖掘算法

當(dāng)前并沒有針對以模式周期最大值為規(guī)范度的界標(biāo)窗口下數(shù)據(jù)流最大規(guī)范模式挖掘的專門研究，所以最直接的處理方式就是從定義出發(fā)來解決這個問題.文獻[6]中的IncRT算法是目前唯一可用于解決以模式周期最大值為規(guī)范度的界標(biāo)窗口下數(shù)據(jù)流規(guī)范模式增量挖掘的算法，基于該算法與最大規(guī)范模式的定義可以得到解決界標(biāo)窗口下數(shù)據(jù)流最大規(guī)范模式挖掘的算法.文獻[8]中的PA算法使用了另外一種不同方法來挖掘滑動窗口中數(shù)據(jù)流的規(guī)范模式.該算法使用垂直格式來組織當(dāng)前窗口上的數(shù)據(jù)流成員，并為窗口中的每個項定義bit-sequence，然后采用類Aprior方法來得到當(dāng)前窗口上的所有規(guī)范模式.如果在PA算法的滑動窗口成員更新步驟中只執(zhí)行加入新數(shù)據(jù)成員的操作，之后對新窗口中成員再使用PA算法進行處理，那么基于這個改動的算法和最大規(guī)范模式的定義，可以得到另外一種挖掘界標(biāo)窗口下數(shù)據(jù)流最大規(guī)范模式的算法.

以上2種算法在挖掘界標(biāo)窗口上數(shù)據(jù)流最大規(guī)范模式的過程中，都會執(zhí)行2個基本操作：1)得到每個界標(biāo)窗口上數(shù)據(jù)流的規(guī)范模式集合；2)消除集合中成員間存在的超集關(guān)系.我們把這2種算法都?xì)w類于na?ve算法，其中基于IncRT算法的方法被稱為NI(na?ve based on IncRT)算法，而基于PA算法的方法被稱為NP(na?ve based on PA)算法.但這2種算法存在明顯問題，就是每個界標(biāo)窗口上(以下簡稱窗口)最大規(guī)范模式集合都需要重新挖掘，而且必須是在得到了所有規(guī)范模式之后，才能得到最大規(guī)范模式集合，所以時間開銷會很大.如果我們能得到相鄰2個窗口上最大規(guī)范模式間的關(guān)系，每次窗口上最大規(guī)范模式的求解都是基于前一個窗口上的結(jié)果來執(zhí)行，那么一方面我們無需在求得數(shù)量龐大的所有規(guī)范模式后再得到最大規(guī)范模式集合；另一方面也可以省去對于相鄰窗口上相同最大規(guī)范模式的重復(fù)挖掘，能夠減小時間開銷.基于這個思想，在這部分我們首先分析了相鄰窗口上規(guī)范模式間的關(guān)系；接著在此基礎(chǔ)上得到了相鄰窗口上最大規(guī)范模式間的關(guān)系(我們稱其為邊界界標(biāo)窗口技術(shù))；隨后又給出了便于該技術(shù)實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)；最后在該數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上得到了能夠增量挖掘界標(biāo)窗口下數(shù)據(jù)流最大規(guī)范模式的DSMRM-BLW算法.

3.1 相鄰窗口上規(guī)范模式間的關(guān)系

設(shè)LWi是第i個界標(biāo)窗口，RSi與USi分別是LWi上的規(guī)范模式與非規(guī)范模式集合，|RSi|與|USi|分別是這2個集合中的成員個數(shù)，ri,j與ui,j分別是RSi與USi中第j個成員.

性質(zhì)1. 設(shè)Tnew,k是LWi后的第k(k>0)個新到事務(wù)，則有USi中任意成員ui,j(1≤j≤|USi|)一定也是LWi∪Tnew,1∪Tnew,2∪…∪Tnew,k上非規(guī)范模式集合中的成員.

證畢.

性質(zhì)2. 設(shè)Tnew,k是LWi后第k(k≥1)個新到事務(wù)，Tnew,k.index是Tnew,k在數(shù)據(jù)流中的索引，LWi.sp是界標(biāo)窗口起始位置的索引.當(dāng)Tnew,k.index-(LWi.sp-1)>λ時，LWi∪Tnew,1∪Tnew,2∪…∪Tnew,k上的規(guī)范模式集合相對于LWi∪Tnew,1∪Tnew,2∪…∪Tnew,k-1上的規(guī)范模式集合，沒有新模式加入.

證明. 基于規(guī)范模式定義可以這樣理解LWi上規(guī)范模式的挖掘過程.首先針對LWi中每個事務(wù)求得該事務(wù)包含的所有子模式(即由構(gòu)成該事務(wù)的項形成的所有子集)，每個子模式的索引都為該事務(wù)的索引，這樣由產(chǎn)生于每個事務(wù)的所有子模式構(gòu)成了候選規(guī)范模式集合CSi；接著求CSi中每個模式的規(guī)范度；最后通過規(guī)范度與最大規(guī)范閾值λ的比較判斷該模式是否為規(guī)范模式.當(dāng)k=1時，令由Tnew,1產(chǎn)生的所有子模式所構(gòu)成的集合為Subsetnew,1.則Subsetnew,1與LWi上的候選規(guī)范模式集合CSi構(gòu)成了LWi∪Tnew,1上的候選規(guī)范模式集合.假設(shè)在Tnew,1到來后有新規(guī)范模式r1產(chǎn)生，則該r1一定位于Subsetnew,1中，而并不位于CSi中.這是因為如果r1也存在于CSi中，由題設(shè)可知，r1在CSi中并不是規(guī)范模式，也即r1在LWi上的規(guī)范度大于λ；當(dāng)Tnew,1到來后，因為r1變成了規(guī)范模式，所以r1在LWi∪Tnew,1上的規(guī)范度小于等于λ.但因為LWi?(LWi∪Tnew,1)，再結(jié)合定義3可知，r1在LWi∪Tnew,1上的規(guī)范度一定大于等于其在LWi上的規(guī)范度，也即大于λ，這與r1是LWi∪Tnew,1上的規(guī)范模式相矛盾，所以r1不存在于CSi中.這樣r1的索引一定為Tnew,1.index.當(dāng)Tnew,1.index-(LWi.sp-1)>λ時，由規(guī)范度定義可知，此時有Rr1>λ，故r1并非規(guī)范模式，這也與假設(shè)矛盾，即在Tnew,1到來后沒有新規(guī)范模式產(chǎn)生.與k=1的證明相類似，容易推得當(dāng)k≥2時，結(jié)論也成立.

證畢.

下面我們通過實例說明性質(zhì)1～2的內(nèi)容.圖1給出了1個數(shù)據(jù)流圖示，其中|EW|=3.

Fig. 1 Illustration of the property 1 and property 2圖1 性質(zhì)1和2的說明

圖1中ID為4的Transaction(圖1中加重且有下劃線的事務(wù)，記為T4)是界標(biāo)窗口LW1后的第1個事務(wù)，由定義2～3可知，E在LW1中的規(guī)范度RE=2.當(dāng)λ=1時，E是LW1上的非規(guī)范模式，這時考慮E在LW1∪T4上的規(guī)范性，由性質(zhì)1可知，E一定是LW1∪T4上的非規(guī)范模式；當(dāng)λ=3時，考慮LW1∪T4上的規(guī)范模式，因為此時有T4.index-(LW1.sp-1)=4-(1-1)=4>λ，所以由性質(zhì)2可知，LW1∪T4上的規(guī)范模式集合與LW1上的規(guī)范模式集合相比，沒有新模式加入.同樣由性質(zhì)2可知，LW1∪T4∪T5∪T6…上的規(guī)范模式集合與LW1上的規(guī)范模式集合相比，沒有新模式加入.

3.2 邊界界標(biāo)窗口技術(shù)

定義7. 邊界基本窗口(border element window, BEW)與邊界界標(biāo)窗口(border landmark window, BLW).令界標(biāo)窗口LW的起始位置為LW.sp，Tran是起始位置后的1個事務(wù)，Tran.index是該事務(wù)在數(shù)據(jù)流中的索引.如果Tran滿足條件Tran.index-(LWi.sp-1)=λ，我們就把Tran所在的基本窗口定義為邊界基本窗口BEW，而以BEW為最后一個基本窗口的界標(biāo)窗口定義為邊界界標(biāo)窗口BLW.

性質(zhì)3. BLW后的任意一個界標(biāo)窗口，其上的規(guī)范模式集合與相鄰前一個界標(biāo)窗口上的規(guī)范模式集合相比，沒有新模式加入.

證明. 由性質(zhì)2容易推得該性質(zhì)成立.

證畢.

性質(zhì)4. 假設(shè)ms是BLW上的最大規(guī)范模式.考慮BLW后第1個界標(biāo)窗口NLW1，有3個結(jié)論成立：

1) 如果ms是該窗口上的規(guī)范模式，則ms一定也是該窗口上的最大規(guī)范模式.

2) 如果ms不是該窗口上的規(guī)范模式，且其中每個成員都是規(guī)范項，設(shè)ms長度為len，將ms所有l(wèi)en-1模式中滿足規(guī)范條件的成員放入結(jié)果集合；然后針對每個不滿足規(guī)范條件的len-1模式，求它們的len-2模式，將所有l(wèi)en-2模式中滿足規(guī)范條件的成員放入結(jié)果集合，這個過程一直到產(chǎn)生的每個模式都滿足規(guī)范條件或者是執(zhí)行到所有1模式為止，如果對此時結(jié)果集合執(zhí)行超集檢測后得到的集合為NS，則NS是當(dāng)前窗口上ms所有子模式的最大規(guī)范模式集合.

3) 如果ms不是該窗口上的規(guī)范模式，且其中存在非規(guī)范項.這時令執(zhí)行了非規(guī)范項刪除操作后的ms為ms1，當(dāng)ms1是規(guī)范模式時，該模式也是當(dāng)前窗口中ms子模式的最大規(guī)范模式；否則按結(jié)論2對其進行處理，能得到當(dāng)前窗口上ms所有子模式的最大規(guī)范模式集合.

證明. 1) 設(shè)BLW與NLW1上的規(guī)范模式集合分別是RS1與RS2.因為ms是BLW上的最大規(guī)范模式，所以由定義4可知我們無法在RS1中找到1個成員rs滿足條件ms?rs.考慮NLW1上情況，如果ms同時也是NLW1上的規(guī)范模式，也即ms滿足條件ms∈RS2，這時因為無法在RS1中找到1個成員rs滿足條件ms?rs，而且由性質(zhì)3可知RS2?RS1，所以也無法在RS2中找到成員rs1滿足條件ms?rs1，也即ms是NLW1上的最大規(guī)范模式.

2) 因為ms是BLW上的最大規(guī)范模式，由規(guī)范模式閉包性可知，ms所有子模式也都是規(guī)范模式，而且ms能覆蓋(覆蓋是指子模式中的所有項都在ms中)這些子模式.另外由性質(zhì)3可知RS2?RS1，所以ms也能覆蓋存在于RS2中ms的所有子模式.但因為ms?RS2，所以ms并不是存在于RS2中ms子模式的最大規(guī)范模式.設(shè)ms長度為len，由Aprior算法可知，ms可由ms的len-1模式執(zhí)行連接操作來得到，而且ms可以覆蓋它的所有l(wèi)en-1模式.依次類推，可得ms的所有l(wèi)en-1模式覆蓋了除ms外所有的ms子模式.所以當(dāng)ms不是NLW1上的規(guī)范模式時，這時判斷ms上的len-1模式，如果它們都是規(guī)范模式，也即它們都是RS2中的成員，那么因為此時ms?RS2，所以由這些規(guī)范模式構(gòu)成了能夠覆蓋存在于RS2中ms子模式的最大規(guī)范模式集合.如果其中存在某個len-1模式不滿足規(guī)范條件，則使用相同方法判斷該模式的len-2模式，一直到關(guān)注的每個模式都滿足規(guī)范條件，則由所有獲得的規(guī)范模式構(gòu)成了結(jié)果集合.由定義4可知，在消除了集合中成員間存在的超集關(guān)系后，該集合即為能夠覆蓋存在于RS2中ms子模式的最大規(guī)范模式集合.

3) 假設(shè)F是ms在NLW1中任意非規(guī)范項,由規(guī)范模式閉包性可知，F(xiàn)在ms中的任何超集都不可能是NLW1上的規(guī)范模式，所以ms上含有F的子模式都不可能是NLW1中的規(guī)范模式，即RS2中不存在ms上含有F的子模式.假設(shè)subsetms是ms的子模式集合，則ms能覆蓋subsetms中每個成員；考慮存在于RS2中的ms子模式集合subset1ms，由前面分析可知subset1ms?subsetms成立，所以ms同樣可以覆蓋subset1ms中的每個成員；從subsetms中刪除所有含有ms在NLW1中非規(guī)范項的子模式，我們把新得到的集合記為subset2ms，則有subset1ms?subset2ms.另外假設(shè)ms在執(zhí)行了刪除所有NLW1中非規(guī)范項的操作后變?yōu)閙s1，則ms1能夠覆蓋subset2ms中的所有成員，進一步可以覆蓋subset1ms中的所有成員.當(dāng)ms1為NLW1上的規(guī)范模式時，結(jié)合定義4可知，ms1是subset1ms中的最大規(guī)范模式；當(dāng)ms1是NLW1上的非規(guī)范模式時，與證明2情況類似，易得結(jié)論成立.

證畢.

性質(zhì)5. 假設(shè)BLW上最大規(guī)范模式集合mset={ms1,ms2,…,msn}，NLW1上最大規(guī)范模式集合為mset1.對于mset與mset1有2個結(jié)論成立：

1) 如果mset中每個成員仍是NLW1上的規(guī)范模式，則mset=mset1.

2) 如果mset中有些成員不是NLW1上的規(guī)范模式，此時mset中的成員可分為3類：①在NLW1上仍然是規(guī)范模式的成員；②在NLW1上不是規(guī)范模式，但模式的構(gòu)成項中都是規(guī)范項的成員；③在NLW1上不是規(guī)范模式，但模式構(gòu)成項中存在非規(guī)范項的成員.分別使用性質(zhì)4的結(jié)論1～3來處理上述3類成員，假設(shè)由這3類成員的處理結(jié)果構(gòu)成的集合為RS，則執(zhí)行了超集檢驗后的RS即為當(dāng)前窗口上的最大規(guī)范模式集合.

證明. 1) 設(shè)RS1與RS2分別是BLW與NLW1上的規(guī)范模式集合.因為mset是BLW上的最大規(guī)范模式集合，所以可知：①mset中的成員覆蓋了RS1中的所有規(guī)范模式；②mset中任意2個成員msk與msl都有如下關(guān)系msk∩msl≠msk，且msk∩msl≠msl成立；③對于mset中任意成員mst，我們在RS1中無法找到1個成員rs，使得條件mst?rs成立.如果mset中每個成員仍是NLW1上的規(guī)范模式，由性質(zhì)4的結(jié)論1可知，這些成員也是NLW1上的最大規(guī)范模式，即mset也是NLW1上最大規(guī)范模式的集合.又由性質(zhì)3可知RS2?RS1，而且再由前面①可推得mset中的成員也覆蓋了RS2中的所有規(guī)范模式，另外前面的②和③顯然在NLW1上也依然成立，即mset也是NLW1上的最大規(guī)范模式集合.

2) 由證明1可知，如果mset中每個成員仍是NLW1上的規(guī)范模式，則mset=mset1，結(jié)合定義4可知，對于NLW1上任意1個規(guī)范模式，在mset(此時也即mset1)中至少有1個成員會完成對該模式的覆蓋.假設(shè)此時mset中有M個成員，我們可以根據(jù)RS2中成員(即NLW1中規(guī)范模式)被這M個成員所覆蓋情況，將其中成員分為M類，當(dāng)然這M類成員彼此間可能會有重合.每一類中成員都被對應(yīng)mset中的成員所覆蓋.當(dāng)mset中某些成員并不是NLW1上的規(guī)范模式時，NLW1上本來應(yīng)該由這些成員覆蓋的所有規(guī)范模式，此時可能就沒有最大規(guī)范模式覆蓋了，所以需要求這部分規(guī)范模式的最大規(guī)范模式.假設(shè)將mset中不是NLW1上規(guī)范模式的成員組合成集合nset，對于nset中任意成員nseti，如果nseti的構(gòu)成項都是規(guī)范項，由性質(zhì)4的結(jié)論2可知，使用該結(jié)論處理nseti后可以得到集合NSi，該集合是NLW1上nseti所有子模式的最大規(guī)范模式集合，覆蓋了存在于RS2中nseti的所有子模式；如果nseti的構(gòu)成項中存在非規(guī)范項，由性質(zhì)4的結(jié)論3可知，在使用該結(jié)論處理nseti后，也可以得到該成員在NLW1上所有子模式的最大規(guī)范模式集合，覆蓋了存在于RS2中nseti的所有子模式；設(shè)從mset中除去nset中的成員后得到的集合為mset|nset，由前面分析及由性質(zhì)4的結(jié)論1可知，這些成員也是NLW1上的最大規(guī)范模式，可以覆蓋存在于RS2中每個mset|nset中成員的所有子模式，所以由這3部分構(gòu)成的RS覆蓋了RS2中所有規(guī)范模式，由定義4可知，RS集合在執(zhí)行超集檢測后，即成為NLW1上的最大規(guī)范模式集合.

證畢.

我們?nèi)砸詧D1為例說明這些性質(zhì)內(nèi)容.設(shè)LW1上λ=3時的規(guī)范模式集合為RS，由圖1可知RS={A,B,C,D,E,F,AC,AD,AB,AE,AF,BC,BE,BF,EF,CE,ABC,ABE,ABF,BCE,BEF,AEC,AEF,ABCE,ABEF}；顯然最大規(guī)范模式集合MRS={ABCE,ABEF,AD}；在求LW2上最大規(guī)范模式時，如果ABCE,ABEF與AD仍是LW2上的規(guī)范模式，則LW2上的最大規(guī)范模式集合仍然為{ABCE,ABEF,AD}(性質(zhì)5的結(jié)論1).因為ABCE與ABEF都是LW2上的規(guī)范模式，所以它們?nèi)匀皇荓W2上的最大規(guī)范模式(性質(zhì)4的結(jié)論1)；又因為AD不是LW2上的規(guī)范模式，而且這時D不是LW2上的規(guī)范模式，所以這時只考慮A.因為A是規(guī)范模式，所以A是AD在LW2上所有子模式的最大規(guī)范模式(性質(zhì)4的結(jié)論3).令A(yù)與ABEF以及ABCE構(gòu)成集合Stem，由性質(zhì)5的結(jié)論2可知，在對該集合執(zhí)行超集檢測后，可得LW2上λ=3時的MRS={ABCE,ABEF}.

由性質(zhì)4～5不難推得BLW后任意2個相鄰界標(biāo)窗口上最大規(guī)范模式集合間都有相同結(jié)論成立.另外由2.2節(jié)可知，本文中λ的取值范圍為1≤λ≤|EW|，所以本文中BLW為最大規(guī)范模式挖掘過程中的第1個界標(biāo)窗口.由性質(zhì)5可知，從第2個界標(biāo)窗口開始，可以基于前一個窗口上最大規(guī)范模式集合來獲得當(dāng)前窗口上最大規(guī)范模式集合.具體方法為首先考慮前一個窗口上最大規(guī)范模式集合中每個成員模式的規(guī)范度，如果這些模式規(guī)范度都滿足規(guī)范條件，則它們構(gòu)成了新窗口上的最大規(guī)范模式集合，否則使用性質(zhì)5中的結(jié)論2對其進行處理，則可以得到當(dāng)前窗口上的全部最大規(guī)范模式.這種從邊界界標(biāo)窗口的下一個窗口開始，基于前一個窗口最大規(guī)范模式集合求得當(dāng)前窗口最大規(guī)范模式集合的方法被稱為邊界界標(biāo)窗口技術(shù).

3.3 數(shù)據(jù)結(jié)構(gòu)

通過前面對邊界界標(biāo)窗口技術(shù)的分析可知，該技術(shù)執(zhí)行的1個重要前提就是需要一種便于計算前一個窗口上最大規(guī)范模式在當(dāng)前窗口上規(guī)范度的方法，而這種方法還需要便于計算當(dāng)前窗口上由規(guī)范項所構(gòu)成的任意模式的規(guī)范度.本部分主要給出了相關(guān)的數(shù)據(jù)結(jié)構(gòu)，而這些數(shù)據(jù)結(jié)構(gòu)的使用可以滿足邊界界標(biāo)窗口技術(shù)使用的前提條件.

3.3.1BV(bit-vector) table

參照文獻[8]中的bit-sequence思想，我們對于邊界界標(biāo)窗口中每個項維護一個bit-vector結(jié)構(gòu).窗口中所有項的bit-vector構(gòu)成了bit-vectortable(簡稱BVtable).因為通過性質(zhì)3可以知道，BLW后的每個窗口上的規(guī)范模式都是BLW上規(guī)范模式的子集，進一步可知，BLW后每個窗口上所有規(guī)范項的集合都是BLW上所有規(guī)范項集合的子集，所以我們只要維護好邊界界標(biāo)窗口上的BVtable在每個新窗口上的狀態(tài)，無論計算前一個窗口上的最大規(guī)范模式在當(dāng)前窗口上的規(guī)范度，還是計算當(dāng)前窗口上由規(guī)范項所構(gòu)成模式的規(guī)范度，只需在當(dāng)前窗口的BVtable中找到模式中項對應(yīng)的bit-vector，然后基于它們執(zhí)行與操作，最后對得到的結(jié)果計算規(guī)范度即可.

1)BVtable結(jié)構(gòu)

BVtable包含name，bit-sequence，reg，lastpos，sign這5個域，分別對應(yīng)項的名稱、項在當(dāng)前窗口中的bit序列、項的規(guī)范度reg、bit-sequence后|EW|個bit序列中最后一個非0位置以及該項在當(dāng)前窗口上的規(guī)范度是否不大于規(guī)范閾值λ的結(jié)果.其中bit-sequence是1個長度為|LW|×|EW|的位序列，每一位與界標(biāo)窗口中的每個數(shù)據(jù)流成員相對應(yīng).如果該項在這個數(shù)據(jù)流成員中出現(xiàn)，則對應(yīng)的bit-sequence位設(shè)為1，否則設(shè)為0.BVtable中每條記錄與當(dāng)前窗口中的每個項對應(yīng)，該記錄也是對應(yīng)項的bit-vector.BVtable中所有項按字典順序排列.表1給出了圖1中LW1上當(dāng)λ=3時的BVtable.

Table 1 BV table over the LW1

2) 構(gòu)建BVtable

由定義7分析可知，本文中BLW是界標(biāo)窗口中第1個窗口，所以BVtable在第1個窗口中成員到來后開始構(gòu)建.①首先將BLW中的數(shù)據(jù)流成員按字典順序轉(zhuǎn)換成垂直格式，完成BVtable中每個項bit-sequence的構(gòu)造；②將bit-sequence中非0成員位置記錄下來形成1個序列，該序列在增加頭成員0和尾成員|EW|后形成1個新序列，求該序列中相鄰成員差值的最大值，以此作為該項的reg值，同時將bit-sequence中最后一個非0成員的位置作為該項的lastpos；③根據(jù)該項reg值與規(guī)范閾值λ間的關(guān)系，完成sign域的賦值.當(dāng)完成這些操作后，BLW上的BVtable構(gòu)造完成.具體如表1所示.

3) 更新BVtable

首先，結(jié)合規(guī)范模式的性質(zhì)與BVtable結(jié)構(gòu)特點，可以得到性質(zhì)6：

性質(zhì)6. BLW上的BVtable中如果有項A的sign域值為false，則有2個性質(zhì)成立：①之后每個界標(biāo)窗口上的BVtable中，該項的sign域值都為false；②BLW上及其之后的每個窗口上的規(guī)范模式集合中，都不會有含有該項的模式出現(xiàn).

② 由規(guī)范模式向下閉包性的性質(zhì)可知，每個界標(biāo)窗口上都不會有含該項的規(guī)范模式出現(xiàn).性質(zhì)6中結(jié)論②成立.

證畢.

由性質(zhì)6可知，在我們得到邊界界標(biāo)窗口上的BVtable在每個新窗口上的狀態(tài)時，我們只需對前一窗口上BVtable中sign域值為true的項執(zhí)行更新即可.

具體更新過程在新EW中所有成員到達后執(zhí)行，設(shè)前一個界標(biāo)窗口上的BVtable為PV.首先我們會針對PV中所有sign域為true的項，按照它們在新EW的數(shù)據(jù)流成員中是否出現(xiàn)的情況，構(gòu)建這些項在新EW中的bit-sequence(記為item.bit-sequence).同時記下item.bit-sequence中第1個非0成員位置fp和最后一個非0成員位置lp.如果item.bit-sequence=0，我們令fp=|EW|，lp=0；接著按照定義1～3對item.bit-sequence進行處理可以得到該項的reg值，記為item.reg.為便于說明，假設(shè)PV中sign域值為true的項I在新EW上的信息組成的臨時表為TemI，另設(shè)項I在PV中對應(yīng)的bit-vector為PVI，則可通過3個步驟更新PVI中信息：①PVI.bit-sequence=PVI.bit-sequence∪TemI.bit-sequence；②PVI.reg=max(|EW|-PVI.lastpos+TemI.fp，PVI.reg，TemI.reg)；③PVI.lastpos=TemI.lp.表2給出了圖1中LW2上當(dāng)λ=3時的BVtable.

Table 2 BV table over the LW2

4)BVtable的結(jié)構(gòu)分析

令item是BLW上任意規(guī)范項.由界標(biāo)窗口特點可知，相鄰下一個界標(biāo)窗口是在當(dāng)前窗口上加1個基本窗口構(gòu)成的，也就是任何項在下一個界標(biāo)窗口上的bit-sequence是由該項在當(dāng)前窗口上的bit-sequence與其在下一個基本窗口上的bit-sequence構(gòu)成.設(shè)BScur是item在BLW上的bit-sequence，而BSnext是item在NLW1上的bit-sequence，則BScur與BSnext之間除了最后|EW|個位序列，其余完全相同.因為我們要求item在下一個窗口上的規(guī)范度，也即基于BSnext求item的規(guī)范度，而在處理BLW時我們基于BScur已經(jīng)得到了item在該窗口上的規(guī)范度，所以在基于BSnext求item的規(guī)范度時，我們可以先求得BSnext中后|EW|個位序列上的規(guī)范度，把這個作為1個最終可能規(guī)范度.另外需要注意的是，BSnext的后|EW|中的第1個非0位與前面序列中最后一個非0位之間的差值，也可能是規(guī)范度，所以我們設(shè)立了lastpos域，我們把這個作為第2個最終的可能規(guī)范度.由定義3可知，這2個可能規(guī)范度和BScur上規(guī)范度3者中的最大值為最終item的reg值.這樣就使我們在只關(guān)注item在新界標(biāo)窗口上bit-sequence中的后|EW|個位序列的情況下，能夠得到該項在新界標(biāo)窗口上的規(guī)范度.類似地，任意界標(biāo)窗口上規(guī)范項都有這樣的規(guī)律.而和基于新界標(biāo)窗口上該項的整個bit-sequence來計算該項的規(guī)范度相比，顯然現(xiàn)有的方法可以更好地減少運算量.

3.3.2 Hash索引表HIT(Hash index table)

在基于BVtable計算前一個窗口上的最大規(guī)范模式在當(dāng)前窗口上的規(guī)范度，或者是求得當(dāng)前窗口上由規(guī)范項所構(gòu)成的任意模式的規(guī)范度時，我們需要隨時能得到模式的每個項在當(dāng)前窗口BVtable中的bit-sequence.如果直接使用BVtable，因為求得每個項在當(dāng)前窗口中的bit-sequence，實際上都需要對BVtable執(zhí)行一次掃描操作，所以效率較低.為解決這個問題，我們以項名為key，以項在BVtable中索引位置index為value設(shè)計了Hash索引表HIT.通過這個數(shù)據(jù)結(jié)構(gòu)，我們能以O(shè)(1)的時間開銷找到當(dāng)前窗口中任何項在BVtable中的位置，進而得到該項的bit-sequence.圖2說明了LW1上λ=3時的HIT與BVtable間的關(guān)系.

Fig. 2 The relationship between the HIT and the BV table over the LW1圖2 LW1上的HIT與BV table間的關(guān)系

性質(zhì)7. 每個窗口上BVtable的HIT都是相同的，無需隨著窗口成員的更新而更新.

證明. 由BVtable的更新過程可知,每個窗口上的BVtable中項的個數(shù)與位置并不會發(fā)生變化，所以與每個窗口上BVtable相關(guān)的HIT也不會發(fā)生變化，無需隨著窗口成員的更新而更新.

證畢.

3.3.3 優(yōu)化策略

性質(zhì)8. 在按照邊界界標(biāo)窗口技術(shù)求得當(dāng)前窗口上的最大規(guī)范模式集合時，我們需要計算前一窗口上的所有最大規(guī)范模式在當(dāng)前窗口上的規(guī)范度.在這個過程中，假設(shè)前一個窗口上的最大規(guī)范模式中存在著某些成員項，這些項在當(dāng)前窗口BVtable中的sign域值為false，則我們在處理該最大規(guī)范模式時可以忽略對于這些項的處理.

證明. 由規(guī)范模式向下閉包性特點，性質(zhì)4的結(jié)論3以及性質(zhì)5的結(jié)論2可得性質(zhì)8成立.

證畢.

該優(yōu)化策略可以減少我們在使用邊界界標(biāo)窗口技術(shù)求得界標(biāo)窗口上最大規(guī)范模式過程中對于很多不必要成員項的處理，能夠提高整個執(zhí)行過程的時間效率.

我們以LW3上最大規(guī)范模式的求解過程為例來說明優(yōu)化策略的內(nèi)容，表3是圖1中LW3上當(dāng)λ=3時的BVtable.

Table 3 BV table over the LW3

由前面可知LW2上λ=3的最大規(guī)范模式集合為RS2={ABCE,ABEF}.又由表3可知A，F(xiàn)在LW3上BVtable中的sign域值為false，所以按照優(yōu)化策略，當(dāng)重新計算ABCE與ABEF在LW3上的規(guī)范度時，可以忽略對其中A，F(xiàn)的處理.也就是說，只需計算BCE和BE的規(guī)范度.對于BCE來說，因為它在LW3上的規(guī)范度為4，所以不滿足規(guī)范條件.按照邊界界標(biāo)窗口技術(shù)考慮BCE長度為2的子模式:BC，BE，CE.因為BC的規(guī)范度為3，CE的規(guī)范度為2，都滿足規(guī)范條件，所以它們?nèi)允钱?dāng)前窗口上BCE所有子模式的最大規(guī)范模式集合中的成員;對于BCE的另一個長度為2的子模式BE，因為它在LW3上的規(guī)范度為4，所以不滿足規(guī)范條件.按照邊界界標(biāo)窗口技術(shù)考慮BE的長度為1的項子模式:B，E.顯然B，E此時都滿足規(guī)范條件.令Stem={BC,CE,B,E}，按邊界界標(biāo)窗口技術(shù)可知，當(dāng)消除了Stem中成員之間存在的超集關(guān)系后，Stem={BC,CE}即為當(dāng)前窗口上BCE所有子模式的最大規(guī)范模式集合；對于RS2中此時需要處理的另外一個模式BE，類似地可以得到S1tem={B,E}為當(dāng)前窗口上BE所有子模式的最大規(guī)范模式集合.同樣由邊界界標(biāo)窗口技術(shù)可知，假設(shè)Stem與S1tem中成員構(gòu)成了新集合Sfinal，即Sfinal={BC,CE,B,E}，那么當(dāng)消除了該集合中成員間存在的超集關(guān)系后，該集合便是LW3上當(dāng)λ=3的最大規(guī)范模式集合RS3，也即RS3={BC,CE}.

3.4 DSMRM-BLW算法

由邊界界標(biāo)窗口技術(shù)可知，在使用na?ve算法求得第1個界標(biāo)窗口上最大規(guī)范模式集合后，我們可以基于該集合求得相鄰下一個窗口上的最大規(guī)范模式集合.依次類推，可以得到之后每個界標(biāo)窗口上的最大規(guī)范模式集合.另外通過文獻[1,6]可知，NI算法在第1個窗口上的執(zhí)行效果與文獻[1]中的RPS-tree算法相同，又由文獻[8]可知，PA算法求得滑動窗口上規(guī)范模式的時間開銷小于RPS-tree算法.所以我們可以在第1個窗口上執(zhí)行NP算法，即使用PA算法求得該窗口上的規(guī)范模式集合，然后消除該集合成員間存在的超集關(guān)系，以此來得到該窗口上的最大規(guī)范模式集合，對于之后每一個界標(biāo)窗口上的最大規(guī)范模式集合，使用邊界界標(biāo)窗口技術(shù)來獲得，我們把這種算法稱為DSMRM-BLW算法.另外由前面BVtable結(jié)構(gòu)可知，該數(shù)據(jù)結(jié)構(gòu)中含有PA算法執(zhí)行所需的bit-sequence，所以DSMRM-BLW算法在第1個窗口上的執(zhí)行無需再構(gòu)造其他數(shù)據(jù)結(jié)構(gòu)，直接使用BVtable中的bit-sequence即可.

DSMRM-BLW算法在前面數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上，完成了基于邊界界標(biāo)窗口技術(shù)挖掘每個界標(biāo)窗口上數(shù)據(jù)流最大規(guī)范模式的操作.算法具體描述如下:

算法1. DSMRM-BLW.

輸入：數(shù)據(jù)流DS、界標(biāo)窗口LW的起始位置sp、規(guī)范閾值λ、基本窗口大小|EW|；

輸出：每個界標(biāo)窗口上的最大規(guī)范模式集合.

① 從數(shù)據(jù)流中索引為sp的成員開始，對每個界標(biāo)窗LW執(zhí)行如下操作；

② {if (theLWis BLW)

③ {構(gòu)建BLW上的BVtablecurtable與HIT;

④Sregular=PA(curtable);*使用PA算法 得到當(dāng)前窗口上完整的規(guī)范模式集 合*

⑤ 消除Sregular中任意2個成員間存在的超集關(guān)系；

⑥Smaxregular=Sregular；

⑦ outputSmaxregular;*輸出BLW上的最大規(guī)范模式集合*

⑧ }

⑨ else

⑩ {基于新EW的成員,按照3.3.1節(jié)3)的 方法更新curtable；

DSMRM-BLW算法在使用邊界界標(biāo)窗口技術(shù)求得當(dāng)前窗口上最大規(guī)范模式集合時，如果前一窗口上最大規(guī)范模式在當(dāng)前窗口上不滿足規(guī)范條件，則需要求得該模式在當(dāng)前窗口上所有子規(guī)范模式的最大規(guī)范模式.下面的GetMRM-subset算法給出了具體求解過程.

算法2. GetMRM-subset.

輸入：規(guī)范閾值λ、在當(dāng)前窗口上不滿足規(guī)范條件的前一窗口上最大規(guī)范模式eset、當(dāng)前窗口上的BVtablecurtable；

輸出：eset所有子規(guī)范模式的最大規(guī)范模式集合MRSeset.

① for (eset每個長leneset-1的子集esubset)

② {計算esubset的規(guī)范度regesubset；

③ if (regesubset<λ)*判斷esubset的規(guī)范度regesubset是否小于λ*

④MRSeset←esubset；

⑤ else

⑥MRSeset←GetMRM-subset (λ,esubset,curtable)；

⑦ }

⑧ 消除MRSeset中任意2個成員間的超集關(guān)系；

⑨ returnMRSeset.

設(shè)eset的長度為leneset，對于eset中每個長為leneset-1的子集esubset執(zhí)行如下步驟：如果esubset滿足規(guī)范條件，則將該子集放入MRSeset中(行③～④)；如果esubset的規(guī)范度不滿足規(guī)范條件，設(shè)lenesubset是esubset的長度，則使用相同方法對于esubset的長度為lenesubset-1的子集進行處理(行⑥)；當(dāng)處理完eset中每個長為leneset-1的子集后，只需消除MRSeset中成員間的超集關(guān)系，便可得到eset中所有子規(guī)范模式的最大規(guī)范模式集合MRSeset(行⑧～⑨).

4 實驗及結(jié)果分析

本部分實驗主要分3部分:1)實驗驗證最大規(guī)范模式相對于規(guī)范模式的優(yōu)勢，這也是本文的研究意義所在；2)驗證本文提出的DSMRM-BLW算法在挖掘界標(biāo)窗口上數(shù)據(jù)流最大規(guī)范模式時的有效性；3)對DSMRM-BLW算法性能進行了評價.

4.1 實驗環(huán)境

本文全部實驗都在一臺配置為Intel?coreTMi5 CPU 650 @3.20 GHz CPU、1.12 GHz主頻、4 GB內(nèi)存、Windows XP 的PC機上執(zhí)行.算法由VC++6.0實現(xiàn).實驗使用了頻繁模式挖掘公用數(shù)據(jù)集中的mushroom和retail數(shù)據(jù)集.其中mushroom是1個稠密數(shù)據(jù)集，共有8 124條記錄，大小為0.54 MB，item的個數(shù)為120，平均記錄長度為23(即含有23個item)；retail是1個稀疏數(shù)據(jù)集，共有88 162條記錄，大小為3.97 MB，16 470個item，平均每條記錄的大小為13；另外在實驗中，我們設(shè)定界標(biāo)窗口的起始位置都為數(shù)據(jù)樣本中第1個成員的位置.因為當(dāng)前并沒有關(guān)于這個方向的研究，所以實驗中的對比算法為前面第3節(jié)提到的NI與NP2類na?ve算法(其中基于IncRT算法的方法被稱為NI算法；而基于PA算法的方法被稱為NP算法).

4.2 最大規(guī)范模式相對于規(guī)范模式的優(yōu)點

本節(jié)就最大規(guī)范模式相對于規(guī)范模式的優(yōu)勢作了實驗驗證.具體實驗方法是首先對數(shù)據(jù)樣本分別執(zhí)行NI與IncRT算法以得到最大規(guī)范模式集合A與規(guī)范模式集合B；接著比較這2個結(jié)果集合中成員的內(nèi)容與數(shù)目.為便于說明，我們定義了2個參數(shù)：1)Raccommodate，該參數(shù)用于表征集合A對于集合B的容納程度；2)Rreduction，用于描述集合A相對于集合B的約減程度.設(shè)|A|與|B|分別表示集合A，B中的成員個數(shù)，又設(shè)變量Naccommodate表示集合A所容納集合B中成員的數(shù)目，該變量的更新變化規(guī)則是，對于集合B中的每個成員elementb，如果能在A中找到一個成員elementa，使得elementb是elementa的子集，則令Naccommodate加1.基于這樣的規(guī)定，我們可以將集合A相對于集合B的Raccommodate與Rreduction具體定義描述如下：

Raccommodate=|Naccommodate||B|，

(1)

Rreduction= |A||B|.

(2)

由上面的定義描述可知，如果實驗結(jié)果中能夠保持Raccommodate=1，且Rreduction<1，則可以說明最大規(guī)范模式集合具有全部規(guī)范模式集合的信息，同時規(guī)模比規(guī)范模式集合要小.具體針對不同真實數(shù)據(jù)樣本的實驗結(jié)果，如圖3所示：

Fig. 3 The Raccommodate and Rreduction about maximal regular patterns over the regular ones when different data samples are taken圖3 不同數(shù)據(jù)樣本下最大規(guī)范模式相對于規(guī)范模式的Raccommodate與Rreduction

由圖3可以看到，在不同數(shù)據(jù)樣本下，最大規(guī)范模式集合相對于規(guī)范模式集合的Raccommodate始終為1，而Rreduction取值也遠(yuǎn)小于1.由前面分析可知，這樣的實驗結(jié)果足以說明最大規(guī)范模式集合含有規(guī)范模式集合所有的信息，同時數(shù)量規(guī)模上也小于規(guī)范模式集合，所以，當(dāng)我們只想定性地確定數(shù)據(jù)集中哪些是規(guī)范模式，而不關(guān)注具體每個規(guī)范模式規(guī)范度時，挖掘最大規(guī)范模式更有效率，這也是本文的研究意義所在.

4.3 DSMRM-BLW算法的有效性

本節(jié)實驗主要用于驗證DSMRM-BLW算法在挖掘界標(biāo)窗口上數(shù)據(jù)流最大規(guī)范模式時的有效性.這里我們使用的方法是將DSMRM-BLW算法的執(zhí)行結(jié)果與最基本的na?ve算法執(zhí)行結(jié)果進行比較.為了便于比較，我們定義了DSMRM-BLW算法相對于其他算法的查全率與查準(zhǔn)率.具體定義如下.設(shè)DSresult與Nresult分別為相同參數(shù)下DSMRM-BLW和na?ve算法的執(zhí)行結(jié)果集合，|DSresult|與|Nresult|分別是這2個集合中成員數(shù)目.令Vequal是這2個集合中相等的成員個數(shù).這里定義DSresult中任一成員A與Nresult中成員B，如果它們對應(yīng)的窗口起始位置相同，且A與B也相同，則A，B相等；如果二者中有1項不同，則A，B不相等.基于這些我們定義了DSMRM-BLW相對于na?ve算法的查全率(recall)與查準(zhǔn)率(precision)，分別用Rrecall與Rprecision表示.使用它們來評價DSMRM-BLW算法的有效性.

Rrecall=Vequal|Nresult|,

(3)

Rprecision=Vequal|DSresult|.

(4)

表4給出了mushroom與retail樣本下DSMRM-BLW算法分別相對于NI與NP算法的查全率與查準(zhǔn)率.表4中我們用Rrecall,NI和Rprecision,NI分別表示DSMRM-BLW算法相對于NI算法的查全率與查準(zhǔn)率，而用Rrecall,NP和Rprecision,NP分別表示DSMRM-BLW算法相對于NP算法的查全率與查準(zhǔn)率.

Table 4 Parameters and Results in Experiment 2

由表4可見，在不同數(shù)據(jù)樣本及參數(shù)設(shè)置下，DSMRM-BLW算法相對于na?ve算法的Rrecall與Rprecision的取值都為1，也即DSMRM-BLW算法與na?ve算法的執(zhí)行結(jié)果相同，即DSMRM-BLW算法能正確地得到界標(biāo)窗口下數(shù)據(jù)流的最大規(guī)范模式.

4.4 DSMRM-BLW算法的性能評價

本節(jié)對DSMRM-BLW算法的時間與空間性能作了評測.因為目前并沒有關(guān)于這方面的研究，所以使用的對比算法為前面提到的2類na?ve算法.具體來說，我們在4.4.1節(jié)討論了不同|EW|，λ以及樣本大小Lsample與算法執(zhí)行時間間的關(guān)系；而在4.4.2節(jié)討論了不同|EW|，λ以及樣本大小Lsample與算法空間開銷間的關(guān)系.

4.4.1 DSMRM-BLW算法的時間開銷分析

首先分析不同λ大小與算法執(zhí)行時間之間的關(guān)系.實驗效果如圖4所示.

由圖4可見，2類樣本下DSMRM-BLW算法執(zhí)行時間遠(yuǎn)小于其他2類算法.這說明邊界界標(biāo)窗口技術(shù)是有效的.另外還可以看到，2類樣本下3種算法執(zhí)行時間都隨λ大小的增加而增加.這是因為λ越大，每個界標(biāo)窗口中滿足規(guī)范度小于λ條件的成員就越多.也即在同一窗口中，λ變大后滿足規(guī)范度小于λ的成員個數(shù)大于等于λ變大前滿足規(guī)范度小于λ的成員個數(shù).對于NI算法，滿足規(guī)范度小于λ的成員個數(shù)越多，算法需要處理的成員就越多，得到的規(guī)范模式數(shù)目也會增加.而因為我們需要消除所有規(guī)范模式間存在的超集關(guān)系，所以這時需要執(zhí)行該操作的成員數(shù)目變得更多，算法時間會增加.同理對于NP算法，當(dāng)滿足規(guī)范度小于λ的成員個數(shù)增加時，算法中也增加了基于bit-sequence執(zhí)行邏輯與操作的成員個數(shù)，得到的規(guī)范模式數(shù)目也會增加，而對于所有這些規(guī)范模式，NP算法也會通過消除它們間存在的超集關(guān)系來得到最大規(guī)范模式集合，所以算法時間會增加；DSMRM-BLW算法在第1個窗口上的情況與NP算法一樣，之后每個窗口上會使用邊界界標(biāo)窗口技術(shù)來處理，所以算法時間開銷主要決定于第1個窗口.由前面分析可知，該窗口上算法時間會隨著滿足規(guī)范度小于λ的成員個數(shù)增加而增加.另外當(dāng)λ取值的增加并沒有使窗口中滿足規(guī)范度小于λ的項成員個數(shù)增加時，算法在這些窗口上的執(zhí)行情況在λ取值改變前后變化不大(如圖4(a)中的λ分別在40～60，80～100中取值)；當(dāng)λ取值的增加使窗口中滿足規(guī)范度小于λ的項成員個數(shù)增加時，算法在這些窗口上執(zhí)行時間會增加.

其次分析不同|EW|大小與算法執(zhí)行時間之間的關(guān)系.實驗效果如圖5所示.

Fig. 4 The comparison of the execution time about different algorithms when λ changes圖4 算法在λ變化時的執(zhí)行時間比較

Fig. 5 The comparison of the execution time about different algorithms when |EW| changes圖5 算法在|EW|變化時的執(zhí)行時間比較

由圖5可見，2類樣本下DSMRM-BLW算法執(zhí)行時間小于其他2類算法，這說明邊界界標(biāo)窗口技術(shù)是有效的.另外可以看到NI與NP算法時間都隨|EW|的增加而減少，這是因為對于同一個數(shù)據(jù)流來說，|EW|越大，算法在該數(shù)據(jù)流上執(zhí)行最大規(guī)范模式挖掘的次數(shù)就越少，而且對于數(shù)據(jù)流上起始位置不變、終止位置以|EW|為單位不斷滑動的界標(biāo)窗口來說，當(dāng)|EW|小時，na?ve算法在數(shù)據(jù)流上執(zhí)行挖掘的總次數(shù)以及所處理數(shù)據(jù)流成員的總量，大于|EW|變大后算法所執(zhí)行挖掘的總次數(shù)以及所處理的數(shù)據(jù)流成員的總量，所以它們的時間都隨窗口大小的增加而減少.DSMRM-BLW算法在第1個窗口上與NP算法一樣，之后每個窗口上會使用邊界界標(biāo)窗口技術(shù)來處理，所以算法時間開銷主要決定于第1個窗口.因為當(dāng)|EW|變大時，變化后第1個窗口上的規(guī)范項數(shù)目小于等于變化前該窗口上的規(guī)范模式數(shù)目，所以對于稠密樣本下第1個窗口上的DSMRM-BLW算法來說，當(dāng)該窗口上規(guī)范模式數(shù)目不變時，因為窗口大小的增加會使該窗口上參與運算的bit-sequene規(guī)模變大，所以執(zhí)行時間會增加(圖5(a)中|EW|大小在100～500，700～900)；當(dāng)該窗口上的規(guī)范模式數(shù)目減少時，特別是當(dāng)窗口大小的增加使得原第1個窗口上本來規(guī)范的項變得不規(guī)范時，界于樣本自身的稠密特征，該算法在新窗口上的規(guī)范模式集合與原窗口上的規(guī)范模式集合相比，會少了很多與被刪除項有關(guān)的規(guī)范模式，這樣后期再執(zhí)行消除規(guī)范模式集合中成員間超集關(guān)系的操作，時間開銷會少很多，所以此時算法時間開銷會減少(圖5(a)中|EW|大小在500～700).對于稀疏樣本下第1個窗口上的DSMRM-BLW算法，樣本稀疏的特點會使得該窗口上的規(guī)范模式不多，同時數(shù)據(jù)結(jié)構(gòu)的規(guī)模會很大，所以該窗口上的時間開銷更多的是在于挖掘規(guī)范模式本身所花費的時間，消除所有規(guī)范模式間超集關(guān)系所花費的時間反而不多.當(dāng)|EW|增加時，因為第1個窗口上數(shù)據(jù)結(jié)構(gòu)的規(guī)模會變大，所以執(zhí)行時間會增加.另外我們可以看到3種算法彼此間的時間差異會隨|EW|的減少而增加，這是因為|EW|越小，算法執(zhí)行挖掘的窗口及次數(shù)就越多，每個窗口上這3類算法執(zhí)行時間都會有差異，隨著窗口數(shù)目的增加，這種差異的累積就會越來越大，所以它們間執(zhí)行時間的差別也會越來越大.

最后分析樣本大小Lsample與算法執(zhí)行時間之間的關(guān)系.實驗效果如圖6所示：

Fig. 6 The comparison of the execution time about different algorithms when Lsample changes圖6 算法在Lsample變化時的執(zhí)行時間比較

由圖6可見，2類樣本下DSMRM-BLW算法執(zhí)行時間小于其他2類算法，這說明邊界界標(biāo)窗口技術(shù)是有效的.另外可以看到這3類算法時間都隨樣本大小的增加而增加，這是因為對于同一個數(shù)據(jù)流來說，樣本越大，算法在該樣本上需要處理的數(shù)據(jù)流成員就越多，所以執(zhí)行時間會隨著樣本大小的增加而增加；另外由圖6中還可以看到，3類算法彼此間的時間差異會隨著樣本大小的增加而增加.這是因為樣本越大，算法執(zhí)行挖掘的窗口及次數(shù)就越多，每個窗口上這3類算法執(zhí)行時間都會有差異，隨著窗口數(shù)目的增加，這種差異的累積就會越來越大，所以它們間執(zhí)行時間的差別也會越來越大.

4.4.2 DSMRM-BLW算法的空間開銷分析

1) 分析不同λ大小與算法空間開銷之間的關(guān)系.實驗效果如圖7所示.

Fig. 7 The comparison of the space consumption about different algorithms when λ changes圖7 算法在λ變化時的空間開銷比較

由圖7可以看到，在空間開銷上DSMRM-BLW

Fig. 8 The comparison of the space consumption about different algorithms when |EW| changes圖8 算法在|EW|變化時的空間開銷比較

另外從圖7可以看到，3種算法空間開銷隨λ大小增加而單調(diào)增加.對于稠密樣本下的NI與NP算法，樣本的稠密性會使算法的空間開銷決定于每個窗口上所有規(guī)范模式的規(guī)模.而當(dāng)λ增加時，每個窗口中滿足規(guī)范度小于λ的項成員數(shù)目可能會有2種變化：①數(shù)量保持不變；②數(shù)量增加.NI算法需要保留每個窗口上完整的規(guī)范模式集合，同時還需要開辟空間用于在該集合基礎(chǔ)上得到最大規(guī)范模式集合，所以如果λ的增加沒有使窗口中滿足規(guī)范條件的成員數(shù)目發(fā)生變化，則NI算法用于存放規(guī)范模式集合的空間保持不變(如圖7(a)中λ取值在40～60和80～100區(qū)間)；如果λ的增加使得窗口中滿足規(guī)范條件的成員數(shù)目增加，則NI算法用于存放規(guī)范模式的空間就會增加.對于NP算法，因為NP算法需要對每個窗口上所有項構(gòu)建bit-sequence序列，另外NP算法也要開辟空間基于每個窗口上的完整規(guī)范模式集合來得到最大規(guī)范模式集合，所以NP算法與NI算法一樣，空間開銷都會隨著λ取值的增加而單調(diào)遞增.DSMRM-BLW算法在第1個窗口上執(zhí)行情況與NP算法一樣，所以該窗口上空間開銷會隨著λ的增加而單調(diào)遞增.又因為該算法在其他窗口上使用邊界界標(biāo)窗口技術(shù)，所以空間開銷并不大，也即此時整個算法的空間開銷集中在第1個窗口上，于是空間開銷會增加.總體來看，DSMRM-BLW算法在每個窗口上的空間開銷會隨著λ取值的增加而單調(diào)遞增.對于稀疏樣本下的算法，樣本的稀疏性會使得每個窗口上規(guī)范模式的數(shù)目較少，且數(shù)據(jù)結(jié)構(gòu)規(guī)模較大.這種情況下算法的空間開銷決定于每個窗口上數(shù)據(jù)結(jié)構(gòu)的規(guī)模.又因為3類算法在每個窗口上的數(shù)據(jù)結(jié)構(gòu)與λ無關(guān)，所以可以看到它們在每個窗口上的空間開銷基本相同.

2) 分析不同|EW|大小與算法空間開銷間的關(guān)系.實驗效果如圖8所示.

由圖8可以看到，DSMRM-BLW算法具有最好的空間開銷，而且不同算法間空間開銷的關(guān)系與λ變化時所呈現(xiàn)的狀態(tài)一樣.具體原因與在λ變化時不同算法空間開銷間關(guān)系分析中己有說明，篇幅原因，這里不再贅述.稠密樣本下2種na?ve算法在每個窗口上的空間開銷，都隨|EW|增加而減小.這是因為對于界標(biāo)窗口而言，當(dāng)λ確定時，基本窗口較大情況下界標(biāo)窗口中規(guī)范模式數(shù)目會小于等于基本窗口較小情況下界標(biāo)窗口中的規(guī)范模式數(shù)目，所以用于存放小基本窗口下界標(biāo)窗口中所有規(guī)范模式的空間開銷大于等于大基本窗口下界標(biāo)窗口中用于存放所有規(guī)范模式的空間開銷.對于DSMRM-BLW算法，因為mushroom樣本稠密性的特點，該算法在第1個窗口上的空間開銷遠(yuǎn)遠(yuǎn)大于其他窗口上的空間開銷，這時該算法的空間開銷主要決定于這個窗口,當(dāng)|EW|增加時，需要處理的界標(biāo)窗口數(shù)會變小，這樣平均每個窗口上的空間開銷就會增加；retail樣本下算法的空間開銷都隨|EW|增加而單調(diào)增加.這是因為樣本稀疏的特點會使得每個界標(biāo)窗口上滿足規(guī)范條件的項變得很少，而且同時又會使窗口上的數(shù)據(jù)結(jié)構(gòu)規(guī)模增加，所以這種情況下算法空間開銷決定于每個窗口的數(shù)據(jù)結(jié)構(gòu)規(guī)模.對于NI算法，因為窗口越大，其中成員越多，每個窗口上的前綴樹規(guī)模就越大，所以空間開銷會增加；對于NP算法與DSMRM-BLW算法，因為窗口越大，每個窗口上BVtable規(guī)模就越大，所以空間開銷單調(diào)增加.

3) 分析樣本大小Lsample與算法空間開銷之間的關(guān)系.實驗效果如圖9所示:

Fig. 9 The comparison of the space consumption on different algorithms when Lsample changes圖9 算法在Lsample變化時的空間開銷比較

由圖9可見，DSMRM-BLW算法具有最好的空間開銷;另外還可以看到稠密樣本下3種算法空間開銷都隨樣本大小增加而單調(diào)遞減.對于2類na?ve算法，因為隨著樣本大小的增加，會出現(xiàn)更多需要處理的界標(biāo)窗口，而且這些窗口大小會越來越大，窗口上規(guī)范模式的數(shù)目會小于等于之前出現(xiàn)的窗口上規(guī)范模式的數(shù)目，所以平均每個窗口上的空間開銷會單調(diào)減少；對于DSMRM-BLW算法，因為該樣本下的空間開銷決定于第1個界標(biāo)窗口，所以隨著窗口數(shù)目的增加，平均每個窗口的空間開銷會越來越小.另外還可以看到稀疏樣本下算法的空間開銷都會隨著樣本大小的增加而單調(diào)增加.這是因為這類樣本下算法的空間開銷主要決定于每個窗口上的數(shù)據(jù)結(jié)構(gòu)規(guī)模.對于NI算法，因為每個新增加窗口上的前綴樹規(guī)模大于等于相鄰前一個窗口上的前綴樹規(guī)模，所以在樣本大小增加過程中，每個窗口上平均空間開銷會增加；對于NP算法，因為每個新增加窗口上的BVtable規(guī)模會大于相鄰前一個窗口上的BVtable規(guī)模，所以在樣本大小增加過程中，每個窗口上的平均空間開銷也會增加；同理DSMRM-BLW算法在樣本大小增加過程中，每個窗口上平均空間開銷也會增加.

總之，由本節(jié)實驗可以看到：①在需要定性確定數(shù)據(jù)集上哪些成員是規(guī)范模式時，挖掘最大規(guī)范模式有更好的效率，能在不減少規(guī)范模式所蘊含信息的同時，極大減少需要挖掘的模式數(shù)量；②DSMRM-BLW算法在挖掘界標(biāo)窗口下數(shù)據(jù)流最大規(guī)范模式時，與na?ve算法執(zhí)行結(jié)果相同；③同2類na?ve算法相比，DSMRM-BLW算法具有更好的時間與空間效率.

5 總結(jié)與展望

本文首次對于界標(biāo)窗口下數(shù)據(jù)流最大規(guī)范模式挖掘問題進行了研究.首先給出了該問題的形式化描述；接著對處理該問題的na?ve算法中相鄰窗口上最大規(guī)范模式間的關(guān)系進行了分析，得到了邊界界標(biāo)窗口技術(shù)，并由此提出了DSMRM-BLW算法，與na?ve算法相比，該算法在保持查詢結(jié)果不變的同時，很好地減少了時間與空間開銷；最后通過對于公有數(shù)據(jù)樣本的實驗證明了該算法的有效性.因為規(guī)范模式與頻繁模式二者都具有向下閉包的特點，所以很多與數(shù)據(jù)流最大頻繁模式挖掘相關(guān)的技術(shù)應(yīng)該可以直接或間接地應(yīng)用于數(shù)據(jù)流最大規(guī)范模式的挖掘中，所以未來研究中我們會著重分析這二者間的關(guān)系，爭取進一步提高DSMRM-BLW算法的執(zhí)行效率；另外，界標(biāo)窗口中歷史數(shù)據(jù)的重要性會隨著時間的推移而減小.為了能夠體現(xiàn)出這個特點，可以將衰減模型與DSMRM-BLW算法相結(jié)合，這也是未來應(yīng)該著手做的一個研究方向.

[1]Tanbeer S K, Ahmed C F, Jeong B S. Mining regular patterns in data streams[C]Proc of the 15th Int Conf on Data Systems for Advanced Applications. Berlin: Springer, 2010: 399-413

[2]Li Guohui, Chen Hui. Mining the frequent patterns in an arbitrary sliding window over online data stream[J]. Journal of Software, 2008, 19(10): 2585-2596 (in Chinese)(李國徽, 陳輝. 挖掘數(shù)據(jù)流任意滑動窗口內(nèi)頻繁模式[J]. 軟件學(xué)報, 2008, 19(10): 2585-2596)

[3]Yun U, Lee G, Ryu K H. Mining maximal frequent patterns by considering weight conditions over data streams[J]. Knowledge-Based Systems, 2014, 55: 49-65

[4]Lee G, Yun U, Ryu K H. Sliding window based weighted maximal frequent pattern mining over data streams[J]. Expert Systems with Applications, 2014, 41(2): 694-708

[5]Hang Meng, Wang Zhihai, Yuan Jidong. Efficient method for mining closed frequent patterns from data streams based on time decay model[J]. Chinese Journal of Computers, 2015, 38(7): 1473-1483 (in Chinese)(韓萌, 王志海, 原繼東. 一種基于時間衰減模型的數(shù)據(jù)流閉合模式挖掘方法[J]. 計算機學(xué)報, 2015, 38(7): 1473-1483)

[6]Tanbeer S K, Ahmed C F, Jeong B S. Mining regular patterns in incremental transactional databases[C]Proc of the 12th Asia-Pacific Web Conf. Piscataway, NJ: IEEE, 2010: 375-377

[7]Kumar G V, Sreedevi M, Kumar N P. Mining regular patterns in data streams using vertical format[J]. International Journal of Computer Science and Security, 2012, 6(2): 142-149

[8]Verma V K, Saxena K. Mining regular pattern over dynamic data stream using bit stream sequence[J]. International Journal of Innovative Technology and Exploring Engineering, 2013, 3(7): 7-10

[9]Kumar G V, Kumari V V. Sliding window technique to mine regular frequent patterns in data streams using vertical format[C]Proc of the Int Conf on Computational Intelligence and Computing Research. Piscataway, NJ: IEEE, 2012: 1-4

[10]Sreedevi M, Reddy L S S. Mining closed regular patterns in data streams[J]. International Journal of Computer Science & Information Technology, 2013, 5(1): 171-179

[11]Rashid M M, Karim M R, Jeong B S, et al. Efficient mining regularly frequent patterns in transactional databases[C]Proc of the 17th Int Conf on Database Systems for Advanced Applications. Berlin: Springer, 2012: 258-271

[12]Rashid M M, Gondal I, Kamruzzaman J. Regularly frequent patterns mining from sensor data stream[C]Proc of the 20th Int Conf on Neural Information Processing. Berlin: Springer, 2013: 417-424

[13]Agrawal R, Srikant R. Fast algorithms for mining association rules in large database[C]Proc of the 20th Int Conf on Very Large Data Bases. San Francisco, CA: Morgan Kaufmann, 1994: 1-32

Wen Yingyou, born in 1974. PhD and post doctor of Northeastern University. Member of CCF. His main research interests include next generation network, wireless sensor network, network security and network management (wenyy@neusoft.com).

Wang Shaopeng, born in 1984. PhD from Northeastern University. Member of CCF. His main research interests include data stream and wireless sensor network.

Zhao Hong, born in 1954. Professor and PhD supervisor of Northeastern University. Senior member of CCF. His main research interests include computer network security and information security, distributed multimedia, and network management (zhaoh@neusoft.com).

The Maximal Regular Patterns Mining Algorithm Based on Landmark Windowover Data Stream

Wen Yingyou1,3, Wang Shaopeng1,2, and Zhao Hong1,3

1(CollegeofComputerScienceandEngineering,NortheasternUniversity,Shenyang110819 )2(CollegeofComputerScience,InnerMongoliaUniversity,Huhhot010021)3(KeyLaboratoryofMedicalImageComputing(NortheasternUniversity),MinistryofEducation,Shenyang110819 )

Mining regular pattern is an emerging area. To the best of our knowledge, no method has been proposed to mine the maximal regular patterns about data stream. In this paper, the problem of mining maximal regular patterns based on the landmark window over data stream is focused at the first time. In order to resolve the issue that the na?ve algorithm which is used to handle the maximal regular patterns mining based on the landmark window over data stream does not have the characteristic of incremental computation, the DSMRM-BLW(data stream maximal regular patterns mining based on boundary landmark window) algorithm is proposed. It takes the first window as the boundary landmark window, and handles it with the na?ve algorithm. For all other windows, it can obtain the maximal regular patterns over them based on the ones over the adjacent last window incrementally, and can overcome the drawback of the na?ve algorithm. It is revealed by the extensive experiments that the DSMRM-BLW algorithm is effective in dealing with the maximal regular patterns mining based on the landmark window over data stream, and outperforms the na?ve algorithm in execution time and space consumption.

data stream; landmark window; maximal regular pattern; incremental calculation; boundary landmark window technology

2015-09-06；

2016-02-16

國家自然科學(xué)基金項目(60903159,61173153,61402096,61163011,61262082,61662054)；中央高?；究蒲袠I(yè)務(wù)費專項資金項目(N110818001,N100218001,N130504007,N120104001)；國家“八六三”高技術(shù)研究發(fā)展計劃基金項目(2015AA016005)；沈陽市科技計劃項目(1091176 -1-00)；內(nèi)蒙古自然科學(xué)基金項目(2015MS0612) This work was supported by the National Natural Science Foundation of China (60903159, 61173153, 61402096, 61163011, 61262082, 61662054), the Fundamental Research Funds for the Central Universities (N110818001, N100218001, N130504007, N120104001), the National High Technology Research and Development Program of China (863 Program)(2015AA016005), the Science and Technology Plan of Shenyang of China (1091176-1-00), and the Natural Science Foundation of Inner Mongolia (2015MS0612).

TP311