滑動窗口中數據流最大頻繁項集挖掘算法研究

尹紹宏，單坤玉，范桂丹

天津工業大學 計算機科學與軟件學院，天津 300387

1 引言

數據流是一組大量的、連續到達的、隨時間不斷變化的數據序列，比如，金融領域中的股票數據，超市里的售貨記錄，電信行業的通話記錄等等。數據流挖掘就是在這樣的一些數據中挖掘出人們事先不知道但又潛在有用的知識和信息的過程。因為數據流是連續到達的而且是大量的數據，這些大量的數據是無法全部保存在內存空間中，只能讀取一次或是有限的幾次，而且對數據流的查詢必須是實時處理的，所以對數據流挖掘算法的要求是只能掃描一次或幾次，并且產生的結果通常是近似結果。顯然，許多靜態的數據挖掘算法并不適合于數據流挖掘。

在現實的實際應用中，人們感興趣的都是近期的數據，所以數據流挖掘一般都是基于某個時間區間來對數據進行挖掘的，從而出現了窗口模型，常見的窗口模型[1]：界標窗口模型、滑動窗口模型和衰減窗口模型。基于界標窗口模型的代表性算法Lossy Counting[2]；基于衰減窗口模型的代表性算法FP-Streaming[3]；基于滑動窗口模型的代表性算法MineSW[4]。但是基于界標窗口模型和衰減窗口模型的挖掘都沒有考慮到數據流出當前窗口的情況，挖掘的結果還是會受過時事務不同程度的影響，在實際應用中，人們關注最多的還是滑動窗口內的數據，因此本文采用的是關注和應用最多的滑動窗口模型。

頻繁項集的挖掘是數據挖掘中關聯規則的基本，按照頻繁項集挖掘的結果，可以將頻繁項集挖掘算法分為[1]完全頻繁項集挖掘，頻繁閉項集挖掘和最大頻繁項集挖掘。因為最大頻繁項集的項集數目相對很少并且已隱含所有的頻繁項集，所以數據流中最大頻繁項集的挖掘具有很好的時空效率并且有很大的意義，也受到了業界更多的關注。針對數據流最大頻繁項集的挖掘，業內人士提出了很多經典的算法，主要包括estDec+[5]、INSTANT[6]和DSM-MFI[7]等算法，上述算法能一次性掃描流過的數據，但仍然存在不足，而且以上算法都是基于界標窗口的，包含大量的歷史數據，但是人們更關心的是近期的數據，即滑動窗口中的數據，如算法FPMFI-DS+[8]等。

算法MFISW[9]提出了基于向量的數據流滑動窗口中最大頻繁項集挖掘方法，通過超集檢測挖掘最大頻繁項集，雖然具有較好的時空效率，但只引用單個頻繁二項集矩陣進行相關操作；算法NSW[10]采用二進制矩陣表示滑動窗口中的事務列表，進行頻繁項集的挖掘；算法MMI-BET[11]提出數據流中基于滑動窗口的最大頻繁項集挖掘算法，采用超集檢測和索引鏈表的方法檢測和存儲最大頻繁項集，但搜索時間效率較低；算法AFMI[12]提出基于事務矩陣挖掘最大頻繁項集，但挖掘過程需迭代多個精簡矩陣并進行邏輯操作，時間效率較差，同時基于算法AFMI提出滑動窗口數據流最大頻繁項集算法AFMI+[12]，基于以上相關算法的研究和啟發，本文提出了滑動窗口中數據流最大頻繁項集挖掘算法SWM-MFI，同時引入兩個矩陣：事務矩陣和二項集矩陣，兩個矩陣均采用二進制0-1表示并通過兩個矩陣的相關操作和子集檢測快速挖掘出最大頻繁項集存儲到數組MFI中。

2 基本概念

設項I={I1,I2,…,Im}，數據流DS是一組連續不斷到達的并且大小可能無限的數據項序列{T1,T2,…,Ti,…,Tn,…}，其中Ti表示第i個到達的事務，而且對于任意Ti，都有Ti?I。

定義1項的集合被稱為項集，k-項集[13]是指包含k個項的集合。

定義2對于?X?I，把窗口中包含X的事務數目稱為X的支持度，記為sup(X)。

定義3滑動窗口W沒有明確的起始點，終止點為窗口的當前時刻，窗口的大小即|W|=窗口中包含事物的數目，該值由用戶預先自行設定。每當一個新事物到達時，舊的事務就被刪除并被新事務直接覆蓋，窗口就滑動一次，事務矩陣不斷被更新。

定義4給定W和最小支持度min_sup，對于?X?I，若有sup(X)≥min_sup，則稱X為滑動窗口W中的頻繁項集。

定義5（最大頻繁項集）給定滑動窗口W和最小支持度min_sup，?X?I，若sup(X)≥min_sup并且?(X?Y∩Y?I)，其中Y為項集X的超集，均有sup(Y)＜min_sup，則稱X為滑動窗口W中的最大頻繁項集。

定義6[5]全序關系?。根據字典中的字母順序，若X小于Y，則記為X?Y，例如A?B?C。同理，定義兩個項集的字典順序為?，例如A?ABC?CD。

假定文中所有的項都是按照全序關系排列的。

3 SWM-MFI算法

3.1 算法使用的數據結構

（2）二項集矩陣B：假設項集中有m個項，則構造一個(m-1)×(m-1)的二項集矩陣，首先將矩陣中的每一個元素初始化為0。對于頻繁1-項集L1中的兩個項Ii，Ij，若Ii?Ij，則取事務矩陣A中的第i行和第j行進行邏輯與操作，若其支持度大于或等于min_sup，則項集{Ii,Ij}為頻繁2-項集，并將Bi,j置為1，否則置為0。

3.2 SWM-MFI算法的基本思想

頻繁(k-1)-項集的擴展：頻繁(k-1)-項集可以擴展為k-項集，擴展條件如下：設{Ii1,Ii2,…,Ii(k-1)}是頻繁(k-1)-項集，在二項集矩陣B中，若B[i(k-1),iu]=1，其中Ii(k-1)?Iiu，并且B[i1,iu]=B[i2,iu]=…=B[i(k-2),iu]=1，那么{Ii1,Ii2,…,Ii(k-1),Iiu}可被擴展為k-項集，然后對事務矩陣A中這k個項對應的行做邏輯與操作，若所得的值大于或是等于min_sup，則{Ii1,Ii2,…,Ii(k-1),Iiu}就是頻繁k-項集。然后對{Ii1,Ii2,…,Ii(k-1),Iiu}中的最后一項Iiu進行擴展，即重復以上步驟，直至不能再擴展為止。

最大頻繁項集的產生：子集檢測，首先將頻繁1-項集的集合L1存儲到最大頻繁項集MFI中，然后依次檢查MFI中是否存在頻繁2-項集{Ii1,Ii2}的子集，若有，則刪除該子集，然后將該頻繁2-項集添加到最大頻繁項集MFI中；若沒有，則直接添加到MFI中，重復以上步驟，直至將擴展到最后的一個頻繁項集檢測完MFI是否有其子集為止，算法結束，MFI中存放的就是窗口中所有的最大頻繁項集。

例子：以表1所示的事務數據流為例，介紹SWM-MFI算法的基本原理，設min_sup=2，|W|=5。

表1 事務數據流

（1）窗口初始階段

當窗口內的事務數據小于窗口的大小|W|時處于窗口初始階段。在此階段，新的數據事務不斷進入窗口，直到窗口滿為止。

則表1的事務數據流的事務矩陣A如表2所示。

表2 窗口初始階段構造事務矩陣A

（2）窗口滑動階段

當窗口已滿時處于滑動窗口階段。算法NewMoment[14]采用左移操作刪除舊事務，再將新事務添加到最右邊的位置，極大地降低了時間效率。本文采用的方式是將最舊的事務T1被新到來的事務T6直接覆蓋，提高了時間效率。則表2中的事務矩陣A更新為如表3。

表3 窗口滑動階段更新的事務矩陣A

（3）最大頻繁項集產生階段

步驟1計算表3中的事務矩陣A每行中1的個數，若大于等于min_sup，則為頻繁1-項集。得到L1={I1,I2,I3,I5}，并將頻繁1-項集添加到最大頻繁項集MFI中，得到MFI={I1,I2,I3,I5}。

步驟2構造二項集矩陣B。表4所示，得到L2={{I1,I2},{I1,I3},{I1,I5},{I2,I3},{I2,I5},{I3,I5}}。

步驟3取出L2中的第一個頻繁2-項集{I1,I2}，檢測MFI中是否有該項集的子集，有其子集I1和I2，將子集刪除，并將該2-項集添加到MFI中，重復以上步驟，得到MFI={{I1,I2},{I1,I3},{I1,I5},{I2,I3},{I2,I5},{I3,I5}}。

表4 二項集矩陣B

步驟4根據L2中的項和B中的信息，可以將頻繁2-項集擴展到3-項集{{I1,I2,I3},{I1,I2,I5},{I1,I3,I5},{I2,I3,I5}}，再將事務矩陣A中的各相關行做邏輯與運算，求其支持度，得到L3={{I1,I2,I3},{I2,I3,I5}}。然后取出第一個頻繁3-項集{I1,I2,I3}，檢測MFI中是否有其子集，將其子集刪除，并將該項集添加到MFI中，重復以上步驟得到MFI={{I1,I5},{I1,I2,I3},{I2,I3,I5}}。本例不能再產生頻繁4-項集，算法結束。

最后得到的滑動窗口中的所有最大頻繁項集為MFI={{I1,I5},{I1,I2,I3},{I2,I3,I5}}。

3.3 SWM-MFI算法的流程

根據上述例子的分析，該算法大致分為三個關鍵步驟：窗口初始階段、窗口滑動階段，最大頻繁項集產生階段。

算法的偽代碼如下：

算法1偽代碼如下：

輸入：數據流DS，滑動窗口的大小w=|W|

輸出：事務矩陣A。最大頻繁項集MFI

（1）滑動窗口中的事務Tj

（2）Else//窗口已滿，進入窗口滑動階段

算法2偽代碼如下：

算法3偽代碼如下：

4 實驗結果分析

算法采用的實驗環境：Windows XP操作系統，內存2 GB，2.67 GHz CPU的平臺；編程語言C#，開發軟件是Microsoft Visual Studio 2010。采用的實驗數據是由IBM data generator（http：//www.almaden.ibm.com）生成的模擬數據。采用的數據集是稀疏集T10I4D100K和稠密集T40I10D100K，其中T表示事務的平均長度，I表示最大頻繁項集的平均長度，D表示數據流中事務的總數，即實驗中的事務總數是10萬條，最大頻繁項集的平均長度為4和10。設定滑動窗口大小為|W|=1 000。

如圖1所示，比較了算法在兩個數據集上的性能。從圖中可以看出，隨著處理事務數目的不斷增多，兩個數據集的運行時間均呈近似線性增長的趨勢，而且兩個數據集的增長趨勢近似相同，但在稠密數據集上的運行時間要遠遠高于稀疏數據集的運行時間，這是因為稠密數據集事務和最大頻繁項集的平均長度都比較長，在滑動窗口，更新以及尋找子集求得最大頻繁項集的過程中耗費的時間較長。

圖1 不同數據集上算法的運行時間

圖2通過設定不同的最小支持度min_sup來測試min_sup對算法性能的影響。在稀疏集T10I4D100K中分別測試了四個不同的min_sup，從圖中可以看出，隨著事務數的不斷增加，每個min_sup耗費的時間呈平穩增長的趨勢。在處理相同事務數的情況下，min_sup越小，算法運行的時間越長，這是因為min_sup越小，所得到的頻繁項集越多，在插入以及尋找子集的過程中需要耗費較長的時間。

圖2 不同最小支持度下算法的運行時間

圖3通過設定不同的滑動窗口大小|W|，來測試|W|對算法性能的影響。在兩個數據集中分別測試了5個不同的|W|，其中min_sup=80，挖掘10 000條事務。從圖中可以看出稀疏數據集中的事務數據隨著|W|的增大，運行時間也在增加，但是增速很緩慢；稠密數據集增速相對較快。隨著|W|的增大，事務矩陣和二項集矩陣的規模會逐漸擴大，窗口的滑動時間增加，從而造成算法的運行時間增加，但增速還是比較緩和。

圖3 不同|W|算法的運行時間

如圖4和圖5所示，實驗對SWM-MFI和AFMI以及AFMI+算法進行了比較。AFMI是基于事務矩陣初步挖掘最大頻繁項集，然后通過事務矩陣的相關操作產生壓縮矩陣和交集矩陣，再從交集矩陣中進一步挖掘最大頻繁項集，顯然此算法在運行過程中需要不斷迭代事務矩陣，并在多個矩陣上進行邏輯運算，對事務矩陣進行排序和多次掃描來搜索最大頻繁項集，并需要不斷剪枝，因此耗費了大量的時間。而SWM-MFI算法在挖掘最大頻繁項集的過程中，省去了剪枝操作，只基于兩個矩陣進行挖掘，無需迭代和排序，只需一次掃描事務數據，提高了挖掘的時間效率。圖4是在挖掘1 000條事務，窗口大小|W|=1 000的前提下，即滑動窗口處于初始階段，沒有數據需要移出，在稀疏集T10I4D100K上進行的實驗，相當于是在靜態數據集上挖掘最大頻繁項集。在不同最小支持度下算法SWM-MFI和AFMI的運行時間比較，如圖4所示。通過實驗可以看出，隨著最小支持度的不斷減小，本文算法的時間效率提高的越明顯。

圖4 不同最小支持度下，不同算法運行時間的比較

圖5是將算法SWM-MFI和AFMI+進行比較，AFMI+算法是基于算法AFMI研究的挖掘滑動窗口中數據流最大頻繁項集，存在的不足與算法AFMI相同。本實驗的前提是在稀疏集T10I4D100K中，滑動窗口大小|W|=1 000，最小支持度min_sup=9。從圖中可以看出，在處理不同數目的事務下，本算法的時間效率要遠遠高于算法AFMI+的時間效率。

圖5 不同事務數下，不同算法的運行時間的比較

5 結束語

本文提出的在滑動窗口中基于矩陣的數據流最大頻繁項集挖方法SWM-MFI，引入了兩個矩陣：事務矩陣和二項集矩陣，通過兩個矩陣的相關操作并采用尋找子集的方法挖掘出最大頻繁項集存儲到數組MFI中。通過與算法AFMI，AFMI+的比較，證明了該算法具有很好的時效性。

[1]毛伊敏.數據流頻繁模式挖掘關鍵算法及其應用研究[D].長沙：中南大學，2011.

[2]Manku G S，Motwani R.Approximate frequency counts over data streams[C]//Proceeding of the 28th International Conference on VLDB，Hong Kong，2002.

[3]Giannella C，Han J，Pei J.Mining frequent patterns in data streams at multiple time granularities[C]//Proceeding of the NSF Workshop on Next Generation Data Mining，2002：191-212.

[4]Cheng J，Ke Y，Ng W.Maintaining frequent itemsets over high-speed data streams[C]//Proceeding of the 10th PAKDD，2006.

[5]Lee Daesu，Lee Wonsuk.Finding maximal frequent itemsets over online data streams adaptively[C]//Proc of Fifth IEEE InternationalConference on Data Mining.Washington DC：IEEE Computer Society，2005：266-273.

[6]Mao Guojun，Wu Xindong，Zhu Xingquan.Mining maximal frequent itemsets from data streams[J].Joumal of Information Science，2007，33（3）：251-262.

[7]Li Hua-Fu，Lee Suh-Yin，Shan Man-Kwan.Online mining（recently）maximal frequent itemset over data streams[C]//Proc of the 15th International Workshops on Research Issuesin DataEngineering：Stream DataMining and Application，2005：11-18.

[8]獒富江，顏躍進.在線挖掘數據流滑動窗口中最大頻繁項集[J].系統仿真學報，2009，21（4）：1134-1139.

[9]徐嘉莉，陳佳，胡慶，等.基于向量的數據流滑動窗口中最大頻繁項集挖掘[J].計算機應用研究，2012，29（3）：837-840.

[10]張月琴.滑動窗口中數據流頻繁項集挖掘方法[J].計算機工程與應用，2010，46（16）：132-134.

[11]楊路明，劉立新，毛伊敏.數據流中基于滑動窗口的最大頻繁項集挖掘算法[J].計算機應用研究，2010，27（2）：519-522.

[12]張月琴，陳東.數據流最大頻繁項挖掘方法[J].計算機工程，2010，36（22）：86-90.

[13]韓家煒.數據挖掘概念與技術[M].北京：機械工業出版社，2012.

[14]Li Hua-Fu，Ho Chin-Chuan，Kuo Fang-Fei.A new algorithm for maintaining closed frequent itemsets in data streams by incremental updates[J].Expert Systems with Applications，2009，36（2）：2451-2458.