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

聞英友 王少鵬 趙 宏

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

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

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

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

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

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

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

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

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

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

1 相關知識

1.1 IncRT算法

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

1.2 PA算法

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

2 基本概念和問題說明

2.1 基本概念

設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}是事務集，其中Ti?SI，也即Ti為SI的子集.

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

定義2. 模式發(fā)生周期集合[1].令SP是ST中所有包含模式P的事務集合，|SP|是SP中的事務總數，這里規(guī)定null事務(該事務為ST中第0個事務，索引值為ST中第1個事務的索引值-1)和ST中最后一個事務分別是SP中的第1個和最后1個事務，它們和ST中其他所有包含P的事務一起構成了SP，SP中所有事務按它們在ST中的索引遞增排列.如果設Trank與Trank+1分別是SP中任意2個相鄰事務，它們在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，均有RY>λ成立，則稱P為ST上的最大規(guī)范模式.

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

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

2.2 問題說明

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

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

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

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

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

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

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

證畢.

性質2. 設Tnew,k是LWi后第k(k≥1)個新到事務，Tnew,k.index是Tnew,k在數據流中的索引，LWi.sp是界標窗口起始位置的索引.當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中每個事務求得該事務包含的所有子模式(即由構成該事務的項形成的所有子集)，每個子模式的索引都為該事務的索引，這樣由產生于每個事務的所有子模式構成了候選規(guī)范模式集合CSi；接著求CSi中每個模式的規(guī)范度；最后通過規(guī)范度與最大規(guī)范閾值λ的比較判斷該模式是否為規(guī)范模式.當k=1時，令由Tnew,1產生的所有子模式所構成的集合為Subsetnew,1.則Subsetnew,1與LWi上的候選規(guī)范模式集合CSi構成了LWi∪Tnew,1上的候選規(guī)范模式集合.假設在Tnew,1到來后有新規(guī)范模式r1產生，則該r1一定位于Subsetnew,1中，而并不位于CSi中.這是因為如果r1也存在于CSi中，由題設可知，r1在CSi中并不是規(guī)范模式，也即r1在LWi上的規(guī)范度大于λ；當Tnew,1到來后，因為r1變成了規(guī)范模式，所以r1在LWi∪Tnew,1上的規(guī)范度小于等于λ.但因為LWi?(LWi∪Tnew,1)，再結合定義3可知，r1在LWi∪Tnew,1上的規(guī)范度一定大于等于其在LWi上的規(guī)范度，也即大于λ，這與r1是LWi∪Tnew,1上的規(guī)范模式相矛盾，所以r1不存在于CSi中.這樣r1的索引一定為Tnew,1.index.當Tnew,1.index-(LWi.sp-1)>λ時，由規(guī)范度定義可知，此時有Rr1>λ，故r1并非規(guī)范模式，這也與假設矛盾，即在Tnew,1到來后沒有新規(guī)范模式產生.與k=1的證明相類似，容易推得當k≥2時，結論也成立.

證畢.

下面我們通過實例說明性質1～2的內容.圖1給出了1個數據流圖示，其中|EW|=3.

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

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

3.2 邊界界標窗口技術

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

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

證明. 由性質2容易推得該性質成立.

證畢.

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

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

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

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

證明. 1) 設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，而且由性質3可知RS2?RS1，所以也無法在RS2中找到成員rs1滿足條件ms?rs1，也即ms是NLW1上的最大規(guī)范模式.

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

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

證畢.

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

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

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

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

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

證畢.

我們仍以圖1為例說明這些性質內容.設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}(性質5的結論1).因為ABCE與ABEF都是LW2上的規(guī)范模式，所以它們仍然是LW2上的最大規(guī)范模式(性質4的結論1)；又因為AD不是LW2上的規(guī)范模式，而且這時D不是LW2上的規(guī)范模式，所以這時只考慮A.因為A是規(guī)范模式，所以A是AD在LW2上所有子模式的最大規(guī)范模式(性質4的結論3).令A與ABEF以及ABCE構成集合Stem，由性質5的結論2可知，在對該集合執(zhí)行超集檢測后，可得LW2上λ=3時的MRS={ABCE,ABEF}.

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

3.3 數據結構

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

3.3.1BV(bit-vector) table

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

1)BVtable結構

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

Table 1 BV table over the LW1

2) 構建BVtable

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

3) 更新BVtable

首先，結合規(guī)范模式的性質與BVtable結構特點，可以得到性質6：

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

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

證畢.

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

具體更新過程在新EW中所有成員到達后執(zhí)行，設前一個界標窗口上的BVtable為PV.首先我們會針對PV中所有sign域為true的項，按照它們在新EW的數據流成員中是否出現的情況，構建這些項在新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.為便于說明，假設PV中sign域值為true的項I在新EW上的信息組成的臨時表為TemI，另設項I在PV中對應的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上當λ=3時的BVtable.

Table 2 BV table over the LW2

4)BVtable的結構分析

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

3.3.2 Hash索引表HIT(Hash index table)

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

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

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

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

證畢.

3.3.3 優(yōu)化策略

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

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

證畢.

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

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

Table 3 BV table over the LW3

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

3.4 DSMRM-BLW算法

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

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

算法1. DSMRM-BLW.

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

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

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

② {if (theLWis BLW)

③ {構建BLW上的BVtablecurtable與HIT;

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

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

⑥Smaxregular=Sregular；

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

⑧ }

⑨ else

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

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

算法2. GetMRM-subset.

輸入：規(guī)范閾值λ、在當前窗口上不滿足規(guī)范條件的前一窗口上最大規(guī)范模式eset、當前窗口上的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個成員間的超集關系；

⑨ returnMRSeset.

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

4 實驗及結果分析

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

4.1 實驗環(huán)境

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

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

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

Raccommodate=|Naccommodate||B|，

(1)

Rreduction= |A||B|.

(2)

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

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

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

4.3 DSMRM-BLW算法的有效性

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

Rrecall=Vequal|Nresult|,

(3)

Rprecision=Vequal|DSresult|.

(4)

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

Table 4 Parameters and Results in Experiment 2

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

4.4 DSMRM-BLW算法的性能評價

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 總結與展望

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

[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)(李國徽, 陳輝. 挖掘數據流任意滑動窗口內頻繁模式[J]. 軟件學報, 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)(韓萌, 王志海, 原繼東. 一種基于時間衰減模型的數據流閉合模式挖掘方法[J]. 計算機學報, 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

國家自然科學基金項目(60903159,61173153,61402096,61163011,61262082,61662054)；中央高?；究蒲袠I(yè)務費專項資金項目(N110818001,N100218001,N130504007,N120104001)；國家“八六三”高技術研究發(fā)展計劃基金項目(2015AA016005)；沈陽市科技計劃項目(1091176 -1-00)；內蒙古自然科學基金項目(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