滑動(dòng)窗口中數(shù)據(jù)流最大頻繁項(xiàng)集挖掘算法研究

尹紹宏，單坤玉，范桂丹

天津工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300387

1 引言

數(shù)據(jù)流是一組大量的、連續(xù)到達(dá)的、隨時(shí)間不斷變化的數(shù)據(jù)序列，比如，金融領(lǐng)域中的股票數(shù)據(jù)，超市里的售貨記錄，電信行業(yè)的通話(huà)記錄等等。數(shù)據(jù)流挖掘就是在這樣的一些數(shù)據(jù)中挖掘出人們事先不知道但又潛在有用的知識(shí)和信息的過(guò)程。因?yàn)閿?shù)據(jù)流是連續(xù)到達(dá)的而且是大量的數(shù)據(jù)，這些大量的數(shù)據(jù)是無(wú)法全部保存在內(nèi)存空間中，只能讀取一次或是有限的幾次，而且對(duì)數(shù)據(jù)流的查詢(xún)必須是實(shí)時(shí)處理的，所以對(duì)數(shù)據(jù)流挖掘算法的要求是只能掃描一次或幾次，并且產(chǎn)生的結(jié)果通常是近似結(jié)果。顯然，許多靜態(tài)的數(shù)據(jù)挖掘算法并不適合于數(shù)據(jù)流挖掘。

在現(xiàn)實(shí)的實(shí)際應(yīng)用中，人們感興趣的都是近期的數(shù)據(jù)，所以數(shù)據(jù)流挖掘一般都是基于某個(gè)時(shí)間區(qū)間來(lái)對(duì)數(shù)據(jù)進(jìn)行挖掘的，從而出現(xiàn)了窗口模型，常見(jiàn)的窗口模型[1]：界標(biāo)窗口模型、滑動(dòng)窗口模型和衰減窗口模型?；诮鐦?biāo)窗口模型的代表性算法Lossy Counting[2]；基于衰減窗口模型的代表性算法FP-Streaming[3]；基于滑動(dòng)窗口模型的代表性算法MineSW[4]。但是基于界標(biāo)窗口模型和衰減窗口模型的挖掘都沒(méi)有考慮到數(shù)據(jù)流出當(dāng)前窗口的情況，挖掘的結(jié)果還是會(huì)受過(guò)時(shí)事務(wù)不同程度的影響，在實(shí)際應(yīng)用中，人們關(guān)注最多的還是滑動(dòng)窗口內(nèi)的數(shù)據(jù)，因此本文采用的是關(guān)注和應(yīng)用最多的滑動(dòng)窗口模型。

頻繁項(xiàng)集的挖掘是數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則的基本，按照頻繁項(xiàng)集挖掘的結(jié)果，可以將頻繁項(xiàng)集挖掘算法分為[1]完全頻繁項(xiàng)集挖掘，頻繁閉項(xiàng)集挖掘和最大頻繁項(xiàng)集挖掘。因?yàn)樽畲箢l繁項(xiàng)集的項(xiàng)集數(shù)目相對(duì)很少并且已隱含所有的頻繁項(xiàng)集，所以數(shù)據(jù)流中最大頻繁項(xiàng)集的挖掘具有很好的時(shí)空效率并且有很大的意義，也受到了業(yè)界更多的關(guān)注。針對(duì)數(shù)據(jù)流最大頻繁項(xiàng)集的挖掘，業(yè)內(nèi)人士提出了很多經(jīng)典的算法，主要包括estDec+[5]、INSTANT[6]和DSM-MFI[7]等算法，上述算法能一次性?huà)呙枇鬟^(guò)的數(shù)據(jù)，但仍然存在不足，而且以上算法都是基于界標(biāo)窗口的，包含大量的歷史數(shù)據(jù)，但是人們更關(guān)心的是近期的數(shù)據(jù)，即滑動(dòng)窗口中的數(shù)據(jù)，如算法FPMFI-DS+[8]等。

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

2 基本概念

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

定義1項(xiàng)的集合被稱(chēng)為項(xiàng)集，k-項(xiàng)集[13]是指包含k個(gè)項(xiàng)的集合。

定義2對(duì)于?X?I，把窗口中包含X的事務(wù)數(shù)目稱(chēng)為X的支持度，記為sup(X)。

定義3滑動(dòng)窗口W沒(méi)有明確的起始點(diǎn)，終止點(diǎn)為窗口的當(dāng)前時(shí)刻，窗口的大小即|W|=窗口中包含事物的數(shù)目，該值由用戶(hù)預(yù)先自行設(shè)定。每當(dāng)一個(gè)新事物到達(dá)時(shí)，舊的事務(wù)就被刪除并被新事務(wù)直接覆蓋，窗口就滑動(dòng)一次，事務(wù)矩陣不斷被更新。

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

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

定義6[5]全序關(guān)系?。根據(jù)字典中的字母順序，若X小于Y，則記為X?Y，例如A?B?C。同理，定義兩個(gè)項(xiàng)集的字典順序?yàn)?，例如A?ABC?CD。

假定文中所有的項(xiàng)都是按照全序關(guān)系排列的。

3 SWM-MFI算法

3.1 算法使用的數(shù)據(jù)結(jié)構(gòu)

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

3.2 SWM-MFI算法的基本思想

頻繁(k-1)-項(xiàng)集的擴(kuò)展：頻繁(k-1)-項(xiàng)集可以擴(kuò)展為k-項(xiàng)集，擴(kuò)展條件如下：設(shè){Ii1,Ii2,…,Ii(k-1)}是頻繁(k-1)-項(xiàng)集，在二項(xiàng)集矩陣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}可被擴(kuò)展為k-項(xiàng)集，然后對(duì)事務(wù)矩陣A中這k個(gè)項(xiàng)對(duì)應(yīng)的行做邏輯與操作，若所得的值大于或是等于min_sup，則{Ii1,Ii2,…,Ii(k-1),Iiu}就是頻繁k-項(xiàng)集。然后對(duì){Ii1,Ii2,…,Ii(k-1),Iiu}中的最后一項(xiàng)Iiu進(jìn)行擴(kuò)展，即重復(fù)以上步驟，直至不能再擴(kuò)展為止。

最大頻繁項(xiàng)集的產(chǎn)生：子集檢測(cè)，首先將頻繁1-項(xiàng)集的集合L1存儲(chǔ)到最大頻繁項(xiàng)集MFI中，然后依次檢查MFI中是否存在頻繁2-項(xiàng)集{Ii1,Ii2}的子集，若有，則刪除該子集，然后將該頻繁2-項(xiàng)集添加到最大頻繁項(xiàng)集MFI中；若沒(méi)有，則直接添加到MFI中，重復(fù)以上步驟，直至將擴(kuò)展到最后的一個(gè)頻繁項(xiàng)集檢測(cè)完MFI是否有其子集為止，算法結(jié)束，MFI中存放的就是窗口中所有的最大頻繁項(xiàng)集。

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

表1 事務(wù)數(shù)據(jù)流

（1）窗口初始階段

當(dāng)窗口內(nèi)的事務(wù)數(shù)據(jù)小于窗口的大小|W|時(shí)處于窗口初始階段。在此階段，新的數(shù)據(jù)事務(wù)不斷進(jìn)入窗口，直到窗口滿(mǎn)為止。

則表1的事務(wù)數(shù)據(jù)流的事務(wù)矩陣A如表2所示。

表2 窗口初始階段構(gòu)造事務(wù)矩陣A

（2）窗口滑動(dòng)階段

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

表3 窗口滑動(dòng)階段更新的事務(wù)矩陣A

（3）最大頻繁項(xiàng)集產(chǎn)生階段

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

步驟2構(gòu)造二項(xiàng)集矩陣B。表4所示，得到L2={{I1,I2},{I1,I3},{I1,I5},{I2,I3},{I2,I5},{I3,I5}}。

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

表4 二項(xiàng)集矩陣B

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

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

3.3 SWM-MFI算法的流程

根據(jù)上述例子的分析，該算法大致分為三個(gè)關(guān)鍵步驟：窗口初始階段、窗口滑動(dòng)階段，最大頻繁項(xiàng)集產(chǎn)生階段。

算法的偽代碼如下：

算法1偽代碼如下：

輸入：數(shù)據(jù)流DS，滑動(dòng)窗口的大小w=|W|

輸出：事務(wù)矩陣A。最大頻繁項(xiàng)集MFI

（1）滑動(dòng)窗口中的事務(wù)Tj

（2）Else//窗口已滿(mǎn)，進(jìn)入窗口滑動(dòng)階段

算法2偽代碼如下：

算法3偽代碼如下：

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

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

如圖1所示，比較了算法在兩個(gè)數(shù)據(jù)集上的性能。從圖中可以看出，隨著處理事務(wù)數(shù)目的不斷增多，兩個(gè)數(shù)據(jù)集的運(yùn)行時(shí)間均呈近似線(xiàn)性增長(zhǎng)的趨勢(shì)，而且兩個(gè)數(shù)據(jù)集的增長(zhǎng)趨勢(shì)近似相同，但在稠密數(shù)據(jù)集上的運(yùn)行時(shí)間要遠(yuǎn)遠(yuǎn)高于稀疏數(shù)據(jù)集的運(yùn)行時(shí)間，這是因?yàn)槌砻軘?shù)據(jù)集事務(wù)和最大頻繁項(xiàng)集的平均長(zhǎng)度都比較長(zhǎng)，在滑動(dòng)窗口，更新以及尋找子集求得最大頻繁項(xiàng)集的過(guò)程中耗費(fèi)的時(shí)間較長(zhǎng)。

圖1 不同數(shù)據(jù)集上算法的運(yùn)行時(shí)間

圖2通過(guò)設(shè)定不同的最小支持度min_sup來(lái)測(cè)試min_sup對(duì)算法性能的影響。在稀疏集T10I4D100K中分別測(cè)試了四個(gè)不同的min_sup，從圖中可以看出，隨著事務(wù)數(shù)的不斷增加，每個(gè)min_sup耗費(fèi)的時(shí)間呈平穩(wěn)增長(zhǎng)的趨勢(shì)。在處理相同事務(wù)數(shù)的情況下，min_sup越小，算法運(yùn)行的時(shí)間越長(zhǎng)，這是因?yàn)閙in_sup越小，所得到的頻繁項(xiàng)集越多，在插入以及尋找子集的過(guò)程中需要耗費(fèi)較長(zhǎng)的時(shí)間。

圖2 不同最小支持度下算法的運(yùn)行時(shí)間

圖3通過(guò)設(shè)定不同的滑動(dòng)窗口大小|W|，來(lái)測(cè)試|W|對(duì)算法性能的影響。在兩個(gè)數(shù)據(jù)集中分別測(cè)試了5個(gè)不同的|W|，其中min_sup=80，挖掘10 000條事務(wù)。從圖中可以看出稀疏數(shù)據(jù)集中的事務(wù)數(shù)據(jù)隨著|W|的增大，運(yùn)行時(shí)間也在增加，但是增速很緩慢；稠密數(shù)據(jù)集增速相對(duì)較快。隨著|W|的增大，事務(wù)矩陣和二項(xiàng)集矩陣的規(guī)模會(huì)逐漸擴(kuò)大，窗口的滑動(dòng)時(shí)間增加，從而造成算法的運(yùn)行時(shí)間增加，但增速還是比較緩和。

圖3 不同|W|算法的運(yùn)行時(shí)間

如圖4和圖5所示，實(shí)驗(yàn)對(duì)SWM-MFI和AFMI以及AFMI+算法進(jìn)行了比較。AFMI是基于事務(wù)矩陣初步挖掘最大頻繁項(xiàng)集，然后通過(guò)事務(wù)矩陣的相關(guān)操作產(chǎn)生壓縮矩陣和交集矩陣，再?gòu)慕患仃囍羞M(jìn)一步挖掘最大頻繁項(xiàng)集，顯然此算法在運(yùn)行過(guò)程中需要不斷迭代事務(wù)矩陣，并在多個(gè)矩陣上進(jìn)行邏輯運(yùn)算，對(duì)事務(wù)矩陣進(jìn)行排序和多次掃描來(lái)搜索最大頻繁項(xiàng)集，并需要不斷剪枝，因此耗費(fèi)了大量的時(shí)間。而SWM-MFI算法在挖掘最大頻繁項(xiàng)集的過(guò)程中，省去了剪枝操作，只基于兩個(gè)矩陣進(jìn)行挖掘，無(wú)需迭代和排序，只需一次掃描事務(wù)數(shù)據(jù)，提高了挖掘的時(shí)間效率。圖4是在挖掘1 000條事務(wù)，窗口大小|W|=1 000的前提下，即滑動(dòng)窗口處于初始階段，沒(méi)有數(shù)據(jù)需要移出，在稀疏集T10I4D100K上進(jìn)行的實(shí)驗(yàn)，相當(dāng)于是在靜態(tài)數(shù)據(jù)集上挖掘最大頻繁項(xiàng)集。在不同最小支持度下算法SWM-MFI和AFMI的運(yùn)行時(shí)間比較，如圖4所示。通過(guò)實(shí)驗(yàn)可以看出，隨著最小支持度的不斷減小，本文算法的時(shí)間效率提高的越明顯。

圖4 不同最小支持度下，不同算法運(yùn)行時(shí)間的比較

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

圖5 不同事務(wù)數(shù)下，不同算法的運(yùn)行時(shí)間的比較

5 結(jié)束語(yǔ)

本文提出的在滑動(dòng)窗口中基于矩陣的數(shù)據(jù)流最大頻繁項(xiàng)集挖方法SWM-MFI，引入了兩個(gè)矩陣：事務(wù)矩陣和二項(xiàng)集矩陣，通過(guò)兩個(gè)矩陣的相關(guān)操作并采用尋找子集的方法挖掘出最大頻繁項(xiàng)集存儲(chǔ)到數(shù)組MFI中。通過(guò)與算法AFMI，AFMI+的比較，證明了該算法具有很好的時(shí)效性。

[1]毛伊敏.數(shù)據(jù)流頻繁模式挖掘關(guān)鍵算法及其應(yīng)用研究[D].長(zhǎng)沙：中南大學(xué)，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ìn).在線(xiàn)挖掘數(shù)據(jù)流滑動(dòng)窗口中最大頻繁項(xiàng)集[J].系統(tǒng)仿真學(xué)報(bào)，2009，21（4）：1134-1139.

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

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

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

[12]張?jiān)虑伲悥|.數(shù)據(jù)流最大頻繁項(xiàng)挖掘方法[J].計(jì)算機(jī)工程，2010，36（22）：86-90.

[13]韓家煒.數(shù)據(jù)挖掘概念與技術(shù)[M].北京：機(jī)械工業(yè)出版社，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.