一種改進(jìn)的數(shù)據(jù)流最大頻繁項(xiàng)集挖掘算法*

胡 健，吳毛毛

(江西理工大學(xué)信息工程學(xué)院，江西 贛州 341000)

一種改進(jìn)的數(shù)據(jù)流最大頻繁項(xiàng)集挖掘算法*

胡 健，吳毛毛

(江西理工大學(xué)信息工程學(xué)院，江西 贛州 341000)

提出了一種基于DSM-MFI算法的改進(jìn)算法DSMMFI-DS算法，它首先將事務(wù)數(shù)據(jù)按一定的全序關(guān)系存入DSFI-list列表中；然后按排序后的順序存儲(chǔ)到類似概要數(shù)據(jù)結(jié)構(gòu)的樹(shù)中；接著刪除樹(shù)中和DSFI-list列表中的非頻繁項(xiàng)，同時(shí)刪除窗口衰退支持?jǐn)?shù)大的事務(wù)項(xiàng)；最后采用自頂向下和自底向上的雙向搜索策略來(lái)挖掘數(shù)據(jù)流的最大頻繁項(xiàng)集。通過(guò)用例分析和實(shí)驗(yàn)表明，該算法比DSM-MFI算法具有更好的執(zhí)行效率。

數(shù)據(jù)挖掘；數(shù)據(jù)流；界標(biāo)窗口；最大頻繁項(xiàng)集；窗口衰減支持?jǐn)?shù)

1 引言

頻繁模式的挖掘是關(guān)聯(lián)挖掘的核心和基礎(chǔ)[1]，是影響挖掘算法效率的一個(gè)決定性的因素，它是產(chǎn)生關(guān)聯(lián)規(guī)則的基礎(chǔ)[2]。因此，在頻繁模式[3～5]挖掘方面取得的任何進(jìn)展都將對(duì)關(guān)聯(lián)挖掘以至于其它數(shù)據(jù)挖掘任務(wù)的效率產(chǎn)生重要的影響。

由于最大頻繁項(xiàng)集[6～9]中隱含著全部的頻繁項(xiàng)集，因此可以將計(jì)算頻繁項(xiàng)集的問(wèn)題轉(zhuǎn)化為計(jì)算最大頻繁項(xiàng)集。在某些應(yīng)用中，只需要最大頻繁項(xiàng)集而并不需要所有的頻繁項(xiàng)集，這樣，研究直接計(jì)算最大頻繁項(xiàng)集的算法顯示出重要意義。

最近，數(shù)據(jù)庫(kù)和數(shù)據(jù)挖掘繼續(xù)集中到一個(gè)新的數(shù)據(jù)模型中，數(shù)據(jù)到達(dá)是以數(shù)據(jù)流的形式。在很多應(yīng)用中，實(shí)時(shí)產(chǎn)生了大量的數(shù)據(jù)流，比如從一個(gè)傳感器網(wǎng)絡(luò)到另一個(gè)傳感器數(shù)據(jù)傳輸產(chǎn)生的數(shù)據(jù)；各個(gè)連鎖店事務(wù)數(shù)據(jù)的流入；Web記錄和在Web上的點(diǎn)擊流；在網(wǎng)絡(luò)監(jiān)控和交通管理的測(cè)量評(píng)估數(shù)據(jù)等[10]。本文就是基于這個(gè)背景提出了一個(gè)有效挖掘數(shù)據(jù)流中最大頻繁項(xiàng)集的算法。

2 相關(guān)工作

Giannella C等人[11]提出了FP-stream算法來(lái)挖掘數(shù)據(jù)流上多個(gè)時(shí)間粒度的頻繁模式，該方法應(yīng)用傾斜時(shí)間窗口策略以精細(xì)的時(shí)間粒度保存數(shù)據(jù)流上最近的頻繁模式信息，而以粗糙的時(shí)間粒度保存歷史的頻繁模式。馬達(dá)等人[12]在一種基于壓縮FP-樹(shù)的最大頻繁項(xiàng)集挖掘算法中提出一種剪枝策略并結(jié)合FP-樹(shù)的結(jié)構(gòu)，并根據(jù)Patricia-樹(shù)的原理設(shè)計(jì)出PFP-樹(shù)，對(duì)數(shù)據(jù)庫(kù)進(jìn)一步壓縮降低內(nèi)存。敖富江等人[13]提出一種新的基于文法順序的FP-Tree的最大頻繁項(xiàng)單遍挖掘算法FPMFI-DS，該算法采用混合搜索空間順序策略，利用子集等級(jí)剪枝策略來(lái)壓縮搜索空間的大??；同時(shí)提出了能夠在線更新挖掘滑動(dòng)窗口內(nèi)數(shù)據(jù)流的最大頻繁項(xiàng)集FPMFI-DS+算法。在界標(biāo)窗口模型中，文獻(xiàn)[14]提出了一種基于界標(biāo)窗口模型的最大頻繁項(xiàng)集的挖掘方法。S-FP-MFI算法[15]是一種基于FP樹(shù)的改進(jìn)的數(shù)據(jù)流最大頻繁項(xiàng)集挖掘算法，它是根據(jù)條件模式基的項(xiàng)目數(shù)對(duì)條件模式基進(jìn)行動(dòng)態(tài)排序，用來(lái)減少函數(shù)調(diào)用的次數(shù)?；谑聞?wù)矩陣挖掘最大頻繁項(xiàng)集的方法AFMI[16]利用了迭代精簡(jiǎn)事務(wù)矩陣的方法來(lái)發(fā)現(xiàn)事務(wù)數(shù)據(jù)中的最大頻繁項(xiàng)集，并提出了滑動(dòng)窗口中的數(shù)據(jù)流最大頻繁項(xiàng)集AFMI+算法。頻繁模式樹(shù)的約束最大頻繁項(xiàng)集快速挖掘算法[17]能夠刪除不滿足約束條件的項(xiàng)集，由于不需要生成候選項(xiàng)目集，所以效率很高。Li Hua-fu等人[18]首先提出的DSM-FI算法通過(guò)將事務(wù)數(shù)據(jù)存儲(chǔ)到概要數(shù)據(jù)結(jié)構(gòu)中，建立IsFI-forest，將每個(gè)項(xiàng)的投影子集存儲(chǔ)到DHT表中，采用自頂向下的搜索策略來(lái)發(fā)現(xiàn)頻繁項(xiàng)集。但是，該算法在刪除一個(gè)非頻繁項(xiàng)集時(shí)需要遍歷整個(gè)項(xiàng)集前綴頻繁項(xiàng)目森林(IsFI-forest)，當(dāng)森林結(jié)構(gòu)復(fù)雜時(shí)，需要?jiǎng)h除很多非頻繁項(xiàng)集，需要很多次遍歷森林，消耗的時(shí)間很多。對(duì)于較長(zhǎng)的非頻繁項(xiàng)集也要建立DHT表，同時(shí)要將各個(gè)子集投影到IsFI-forest中去，這樣不僅使存儲(chǔ)空間加大，而且還造成刪除耗時(shí)。

本文提出的DSMMFI-DS(Dictionary Sequence Mining Maximal Frequent Itemsets over Data Streams)算法是基于DSM-MF算法[1]提出來(lái)的，DSMMFI-DS算法先對(duì)流入的數(shù)據(jù)流按一定順序排序(本文是按一種全序關(guān)系)存入DSFI-list(Dictionary Sequence Frequent Item List)列表中，并且按這個(gè)順序存儲(chǔ)到DSSEFI-tree樹(shù)中；接著刪除DSFI-list列表中的非頻繁項(xiàng)對(duì)應(yīng)在DSSEFI-tree樹(shù)中的項(xiàng)；然后刪除DSFI-list列表中的非頻繁項(xiàng)；最后在當(dāng)前的概要數(shù)據(jù)結(jié)構(gòu)中利用自頂向下和自底向上的雙向搜索策略發(fā)現(xiàn)最大頻繁項(xiàng)集。

3 問(wèn)題的定義及相關(guān)知識(shí)

3.1 問(wèn)題定義

從大的數(shù)據(jù)庫(kù)中挖掘最大頻繁項(xiàng)集是關(guān)聯(lián)挖掘的一個(gè)重要問(wèn)題。這個(gè)問(wèn)題是Bayardo首先提出來(lái)的。問(wèn)題的定義如下[1]：設(shè)Ψ={i1,i2,…,in}是一系列的數(shù)據(jù)，in稱作項(xiàng)目。設(shè)數(shù)據(jù)庫(kù)DB是一系列的交易事務(wù)，DB的大小用|DB|表示。一個(gè)事務(wù)T有m個(gè)項(xiàng)目，可以表示成T={i1,i2,…,im}，k-項(xiàng)集就是包含有k個(gè)項(xiàng)目的集合，表示為{x1,x2,…,xk}。一個(gè)項(xiàng)目集X的支持度就是指在這個(gè)數(shù)據(jù)庫(kù)中所有包含X項(xiàng)的總項(xiàng)目數(shù)占這個(gè)數(shù)據(jù)庫(kù)項(xiàng)目總數(shù)的百分比，X項(xiàng)目的支持度用sup(X)表示。如果sup(X)>minsup，那么X就被稱作頻繁項(xiàng)集，minsup是用戶自定義的最小支持度值，它的范圍是[0,1]。所有頻繁項(xiàng)集集合用FI(Frequent Item)表示。如果一個(gè)頻繁項(xiàng)集不是任何一個(gè)頻繁項(xiàng)集的子集，那么就把它叫做最大頻繁項(xiàng)集，一系列最大頻繁項(xiàng)集的集合用MFI(Maximal Frequent Itemsets)表示。本文目的就是找到所有支持度比用戶給定的最小支持度大的最大頻繁項(xiàng)集。

定義1[19]設(shè)數(shù)據(jù)流DS={w1,w2,…,wN}，其中wi(?i=1,2,…,N)的i是每一個(gè)基本窗口的標(biāo)識(shí)，N是最后一個(gè)基本窗口的標(biāo)識(shí)。它是一個(gè)連續(xù)的、無(wú)窮的基本窗口序列，每個(gè)基本窗口含有固定數(shù)目的事務(wù)，〈T1,T2,…,Tk,…〉，Tk={i1,i2,…,im}，Tk(K=1,2,…)稱為事務(wù)。

定義2設(shè)用戶給定的支持度s和允許偏差ε(0<ε

3.2 窗口衰退支持?jǐn)?shù)

由于數(shù)據(jù)流的流動(dòng)性與連續(xù)性，在一段界標(biāo)窗口內(nèi)的事務(wù)數(shù)量可能很大甚至無(wú)限，數(shù)據(jù)流中蘊(yùn)含的知識(shí)會(huì)隨著窗口的推移而發(fā)生變化。而在實(shí)際的數(shù)據(jù)流應(yīng)用中，最近產(chǎn)生事務(wù)所蘊(yùn)含的知識(shí)往往要比歷史事務(wù)的知識(shí)有價(jià)值得多。因此，在數(shù)據(jù)流頻繁模式挖掘時(shí)，人們更希望挖掘出最近產(chǎn)生事務(wù)的頻繁模式或者是最大頻繁模式，而忽略那些歷史事務(wù)的模式。

本文應(yīng)用窗口衰減模型逐步衰減歷史事務(wù)模式支持?jǐn)?shù)的權(quán)重，并由此來(lái)區(qū)分新產(chǎn)生事務(wù)與歷史事務(wù)的模式。如果記模式支持?jǐn)?shù)在單位窗口內(nèi)的衰退比率為衰減因子cf(0

(1)

4 算法描述

DSMMFI-DS算法先把每個(gè)窗口的事務(wù)數(shù)據(jù)存儲(chǔ)到一個(gè)新的概要數(shù)據(jù)結(jié)構(gòu)[19]—改進(jìn)的前綴頻繁項(xiàng)目樹(shù)DSSEFI-tree中;然后根據(jù)DSFI-list列表中計(jì)算的每個(gè)項(xiàng)目的支持?jǐn)?shù)，從DSSEFI-tree中刪除不頻繁項(xiàng)，接著刪除DSFI-list列表中的非頻繁項(xiàng)并將DSSEFI-tree樹(shù)存儲(chǔ)到DSSEFI-forest森林;最后根據(jù)用戶需求或者需要遍歷DSSEFI-forest森林挖掘相應(yīng)項(xiàng)的最大頻繁項(xiàng)集。

4.1 概要數(shù)據(jù)結(jié)構(gòu)

為了適應(yīng)滑動(dòng)窗口內(nèi)最大頻繁項(xiàng)集的挖掘，本節(jié)設(shè)計(jì)了一種前綴概要項(xiàng)目樹(shù)DSSEFI-tree，與DSM-MFI中的SFI-tree相比，除了存儲(chǔ)項(xiàng)目名字item_name、窗口的標(biāo)識(shí)window_count、項(xiàng)目的支持?jǐn)?shù)node_count、指向DSFI-list表中的相同節(jié)點(diǎn)的指針node_link和指向DSSEFI-tree樹(shù)中具有相同項(xiàng)目名字的節(jié)點(diǎn)item_brother外，還增加了一個(gè)參數(shù)就是窗口衰退支持?jǐn)?shù)parameter，該參數(shù)主要記錄著每個(gè)項(xiàng)隨著窗口的移動(dòng)所代表的權(quán)重，當(dāng)parameter很大時(shí)說(shuō)明該項(xiàng)不是最近窗口的項(xiàng)，我們可以盡早將該項(xiàng)從樹(shù)結(jié)構(gòu)中刪除掉。

同時(shí)，為概要項(xiàng)目樹(shù)DSSEFI-tree設(shè)計(jì)了一個(gè)頭項(xiàng)列表DSFI-list，該列表與DSM-MFI算法中的FI-list相比，除了具有存儲(chǔ)項(xiàng)目名字item_name、窗口的標(biāo)識(shí)window_count、項(xiàng)目的支持?jǐn)?shù)node_count、指向DSSEFI-tree樹(shù)中的相同節(jié)點(diǎn)的指針node_link和指向DSSEFI-tree樹(shù)中具有第一個(gè)相同項(xiàng)目名字的節(jié)點(diǎn)item_brother外，也增加了窗口衰退支持?jǐn)?shù)parameter，由這個(gè)參數(shù)我們就可以很快知道樹(shù)中存儲(chǔ)的哪些項(xiàng)是已經(jīng)過(guò)期的，可以很方便地將此項(xiàng)刪除。

4.2 增量更新DSSEFI-tree樹(shù)

由于數(shù)據(jù)流不斷地流入，內(nèi)存的存儲(chǔ)空間有限，需要實(shí)時(shí)地對(duì)樹(shù)進(jìn)行更新，及時(shí)刪除不頻繁項(xiàng)集和過(guò)期的項(xiàng)，同時(shí)要及時(shí)返回用戶查詢的結(jié)果。由于樹(shù)本身在存儲(chǔ)時(shí)是按照頭項(xiàng)列表中的全序關(guān)系進(jìn)行存儲(chǔ)的，不受項(xiàng)到來(lái)的先后順序影響，在對(duì)項(xiàng)進(jìn)行操作時(shí)也比較方便。再根據(jù)用戶設(shè)定的最小支持度和窗口衰退支持?jǐn)?shù)閾值，在每一個(gè)窗口到來(lái)之后就對(duì)樹(shù)進(jìn)行一次更新，這樣可以很快地將樹(shù)中的不頻繁項(xiàng)集和已經(jīng)過(guò)期的項(xiàng)集剪枝掉，在節(jié)省內(nèi)存空間的同時(shí)提高了查詢的效率。假設(shè)新的窗口事務(wù)數(shù)據(jù)TDS(i)=(a1,a2,…,aN)到來(lái)時(shí)，算法1是對(duì)樹(shù)DSSEFI-tree的更新。

算法1增量更新樹(shù)DSSEFI-tree

輸入：事務(wù)數(shù)據(jù)TDS(i)=(a1,a2,…,aN)，用戶設(shè)定的最小支持度s，用戶設(shè)定的窗口衰退支持?jǐn)?shù)閾值p，用戶允許的最大誤差率ε(0,s)；

輸出：更新后的樹(shù)DSSEFI-tree。

(1) ifDSFI-list=?，then {window_count=1；

(2)foreachaj，將aj的item_name、window_count和node_link插入到DSFI-list中；

(3)endfor

(4) 為樹(shù)DSSEFI-tree構(gòu)造根節(jié)點(diǎn)root；

(5)foreachaj,將aj的item_name、window_count、node_count、node_link、item_brother和parameter插入到DSSEFI-tree中；}

(6)endfor

(7)endif

(8)else{

window_count=i;

(9)foreachaj按全序插入到DSFI-list中；

(10) if有相同item_name的項(xiàng)itemthenitem.parameter=aj.parameter;

(11)endif

(12)foreachDSFI-list中的每個(gè)項(xiàng)ai對(duì)應(yīng)的parameter項(xiàng)進(jìn)行更新：parameter=cf(P,Ti-1)×cf+c;

(13)ifai.parameter≥p，將ai從樹(shù)DSSEFI-tree中刪除，接著從DSFI-list中刪除;

(14)endif

(15)ifai.node_count

(16)endif

(17)endfor

(18)endfor

(19)}

(20)}endelse

4.3 最大頻繁項(xiàng)集的挖掘算法

更新完樹(shù)DSSEFI-tree后，我們根據(jù)需求來(lái)對(duì)數(shù)據(jù)流進(jìn)行操作，查找相應(yīng)項(xiàng)的最大頻繁項(xiàng)集。本文設(shè)計(jì)一個(gè)改進(jìn)的雙向搜索策略tb-btMFI(top-bottomandbottom-topselectionofMaximalFrequentItems)[20]，雙向搜索從DSSEFI-tree樹(shù)中發(fā)現(xiàn)最大頻繁項(xiàng)集，其中設(shè)計(jì)一個(gè)監(jiān)控參數(shù)monitor，讓自頂向下搜索和自底向上搜索同步進(jìn)行，可以及早發(fā)現(xiàn)不頻繁項(xiàng)，提高挖掘效率。

算法描述：自頂向下搜索，設(shè)置monitor的值為0，對(duì)每一個(gè)項(xiàng)x，將x所在的最長(zhǎng)路徑中所有項(xiàng)合并形成最大頻繁候選項(xiàng)集存儲(chǔ)在M1中(假設(shè)為k項(xiàng)集)，對(duì)這個(gè)最長(zhǎng)的項(xiàng)集進(jìn)行支持度計(jì)算，如果它滿足用戶給定的最小支持度，則它是最大頻繁項(xiàng)集，并將這個(gè)最大頻繁項(xiàng)集加入到MFI中，令monitor為1，轉(zhuǎn)到自底向上搜索，如果M2中某項(xiàng)是MFI的子集，則從M2刪除此項(xiàng)；如果不滿足，則對(duì)x和其他項(xiàng)進(jìn)行任意組合形成k-1項(xiàng)集存儲(chǔ)在M1中，令monitor為1，轉(zhuǎn)到自底向上搜索，如果M2中某項(xiàng)是MFI的子集則從M2刪除此項(xiàng)。依次進(jìn)行下去，直到M1為空為止。自底向上搜索，如果monitor的值為1，從樹(shù)的葉子節(jié)點(diǎn)開(kāi)始對(duì)x項(xiàng)進(jìn)行相鄰兩短項(xiàng)集組合，存儲(chǔ)在M2中，搜索到L層時(shí)仍然保留L-1層中的項(xiàng)，然后對(duì)組合的項(xiàng)集進(jìn)行支持度計(jì)算，對(duì)第L層上的某個(gè)項(xiàng)目集X，若X是MFS中某頻繁項(xiàng)目集的子集，則不對(duì)X進(jìn)行支持度計(jì)算，令monitor的值為0，轉(zhuǎn)到自頂向下搜索；否則，對(duì)X進(jìn)行支持度計(jì)算，若X是第L層中的頻繁項(xiàng)目集，則從M2中刪除X在L-1層中的所有項(xiàng)目子集，否則刪除X，令monitor的值為0，繼續(xù)自頂向下搜索；若第L-1層中的某個(gè)頻繁項(xiàng)目集y在第L層上的所有超集均為非頻繁項(xiàng)目集，則將y加到MFS中并從M2中刪除y，令monitor值為0，繼續(xù)自頂向下搜索。如果monitor的值為1，則處理完第L層上的每一個(gè)項(xiàng)目集,如果monitor的值為1，則生成L+1層上的候選頻繁項(xiàng)目集，依次類推，直到M2為空。如算法2所示。

算法2tb-btMFI算法

輸入：更新后的DSSEFI-tree樹(shù)，當(dāng)前窗口標(biāo)識(shí)N，最小支持度s，用戶允許的最大誤差率ε；

輸出：最大頻繁項(xiàng)集MFI。

(1)令MFI=?，M1=?，M2=?，monitor=0；

(2)for(k=n;k≥1;k--)

(3){

(4)M1={路徑中包含Xi項(xiàng)目的組成最大候選頻繁項(xiàng)集X}；

(5) 計(jì)算各候選頻繁項(xiàng)集的支持度；

(6)if候選項(xiàng)集∈MFIthenM1=M1-X，monitor=1，轉(zhuǎn)到(13)；

(7)else計(jì)算候選項(xiàng)集X的支持度；

(8)ifX.node_count≥s·X.SLorX.node_count<ε·X.SLthen

(9) MFI=MFI∪{X}，monitor=1，轉(zhuǎn)到(13)；

(10)elseM1=M1-{X}，monitor=1，轉(zhuǎn)到(13)；

(11)}

(12)ifM1={?}then退出；

(13)for(k=0; k<=L; k ++){

(14)M2={包含xi項(xiàng)的相鄰兩項(xiàng)組成的候選頻繁項(xiàng)集X}

(15)ifX∈MFIthen

(16)M2=M2-X，monitor=0，轉(zhuǎn)到(2);

(17)if在第k-1層的項(xiàng)X是第k層的子集then

(18)M2=M2-X，monitor=1，轉(zhuǎn)到(2);

(19) 計(jì)算各項(xiàng)目X的支持度；

(20)ifX.node_count≥ s·X.SLorX.node_count< ε·X.SLthen

(21) MFI=MFI∪{X}，monitor=1，轉(zhuǎn)到(2);

(22)elseM2=M2-X，monitor=1，轉(zhuǎn)到(2);

(23)}

(24)ifM2={?}then退出；

(25)endfor

5 算法的復(fù)雜性分析與用例分析

5.1 算法的復(fù)雜性分析

(1)時(shí)間復(fù)雜度。

(2)

對(duì)于MMFI-DS算法：(1)在SEFI-tree構(gòu)造和維護(hù)算法中，算法需把T×N個(gè)項(xiàng)目插入到SEFI-tree中，刪除一個(gè)不頻繁項(xiàng)目，算法需刪除此不頻繁項(xiàng)在EIS-tree中節(jié)點(diǎn)的個(gè)數(shù)，設(shè)其數(shù)目為C3。(2)在發(fā)現(xiàn)最大頻繁項(xiàng)集的算法中，MMFI-DS算法的時(shí)間復(fù)雜度為[19]：

T×N+C1×C3+C2×

(3)

對(duì)于DSMMFI-DS算法：(1)在DSSEFI-tree樹(shù)的增量更新中，算法也要把T×N個(gè)項(xiàng)目插入到DSSEFI-tree中，刪除一個(gè)不頻繁項(xiàng)目，算法需刪除此不頻繁項(xiàng)在DSSEFI-tree中節(jié)點(diǎn)的個(gè)數(shù)，設(shè)其數(shù)目為C4。(2)在發(fā)現(xiàn)最大頻繁項(xiàng)集的算法中，DSMMFI-DS算法的時(shí)間復(fù)雜度為：

T×N+C1×C4+C2×

(3)

(2)空間復(fù)雜度。

DSM-MFI算法在內(nèi)存中需要保存FI-list表、OFI-list表和SFI-tree樹(shù)；MMFI-DS算法在內(nèi)存中需要保存FI-list表、OFI-list表和EIS-tree樹(shù)；DSMMFI-DS算法在內(nèi)存中保存DSFI-list表和DSSEFI-tree樹(shù)。DSM-MFI算法和MMFI-DS算法都用了投影子集的方法，將投影子集項(xiàng)存放在OFI-list表中，這樣占用了一定大小的內(nèi)存空間，DSMMFI-DS算法用DSFI-list表來(lái)存放頻繁一項(xiàng)集,一方面，不需要存儲(chǔ)每個(gè)項(xiàng)目的投影子集，就節(jié)省了內(nèi)存的空間，另一方面因用DSSEFI-tree樹(shù)結(jié)構(gòu)的存儲(chǔ)經(jīng)過(guò)全序排序后樹(shù)的分支少，結(jié)構(gòu)簡(jiǎn)單，同時(shí)在節(jié)點(diǎn)數(shù)據(jù)域中增加了監(jiān)控參數(shù)monitor，這樣可以盡早地刪減已經(jīng)過(guò)期的或者對(duì)用戶沒(méi)有意義的頻繁項(xiàng)，從而更節(jié)省了內(nèi)存的開(kāi)銷。假設(shè)頻繁1-項(xiàng)目的樹(shù)為k，DSM-MFI算法需要存儲(chǔ)2k個(gè)節(jié)點(diǎn)，MMFI-DS算法需要存儲(chǔ)C×k(C為常數(shù))個(gè)節(jié)點(diǎn)，DSMMFI-DS算法則需要存儲(chǔ)C×r個(gè)節(jié)點(diǎn)(r為k個(gè)頻繁項(xiàng)集刪除過(guò)期或者用戶不感興趣的項(xiàng)后剩下的頻繁項(xiàng)目樹(shù)r≤k)，顯然，C×r≤C×k<2k，所以DSMMFI-DS算法比DSM-MFI算法和MMFI-DS算法在相同環(huán)境中處理同樣數(shù)據(jù)流更節(jié)省內(nèi)存空間。

5.2 用例分析

假設(shè)某一數(shù)據(jù)流W1=[c,f,a,d,e,p,m;f,c,d,a;m,a,b,c,d;b,c,a,m,p,i]，從窗口中讀入完數(shù)據(jù)存儲(chǔ)到DSFI-list中的結(jié)構(gòu)。

如圖1所示，假定用戶給定的最小支持度為3，從DSFI-list中刪除，然后根據(jù)DSFI-list列表中的順序存儲(chǔ)到DSSEI-tree中的結(jié)構(gòu)，如圖2所示。

同樣地用DSM-MFI算法得到的SFI-tree樹(shù)存儲(chǔ)結(jié)構(gòu)如圖3和圖4所示。

Figure 1 Tree storage structure of DSSEFI-tree after DSMMFI-DS algorithm reads the data streams圖1 DSMMFI-DS算法讀取完數(shù)據(jù)流后 DSSEFI-tree樹(shù)存儲(chǔ)結(jié)構(gòu)

Figure 2 Tree storage structure of DSSEFI-tree after DSMMFI-DS algorithm removes not frequent itemsets圖2 DSMMFI-DS算法刪除不頻繁項(xiàng)集后的 DSSEFI-tree樹(shù)存儲(chǔ)結(jié)構(gòu)

Figure 3 Tree storage structure of SFI-tree after DSM-MFI algorithm reads the data streams圖3 DSM-MFI算法讀取完數(shù)據(jù)流后 SFI-tree樹(shù)存儲(chǔ)結(jié)構(gòu)

Figure 4 Tree storage structure of SFI-tree after DSM-MFI algorithm removes not frequent itemsets圖4 DSM-MFI算法刪除非頻繁項(xiàng)集后的 SFI-tree樹(shù)存儲(chǔ)結(jié)構(gòu)

從上面的結(jié)構(gòu)圖我們可以看到,MMFI-DS算法由于沒(méi)有對(duì)讀入的數(shù)據(jù)流進(jìn)行排序，那么它的有些計(jì)數(shù)少的項(xiàng)目存儲(chǔ)到EIS-tree樹(shù)中可能成為根節(jié)點(diǎn)，這樣我們?cè)谟米皂斚蛳碌乃惴ㄋ阉鲿r(shí)發(fā)現(xiàn)最大頻繁項(xiàng)集時(shí)會(huì)花費(fèi)更多的時(shí)間來(lái)計(jì)算項(xiàng)目的支持度；另一方面，由于沒(méi)有進(jìn)行排序，那么頻繁項(xiàng)目在存儲(chǔ)時(shí)可能分布在樹(shù)的各個(gè)分支中，這樣在存儲(chǔ)空間方面又會(huì)造成浪費(fèi)。在DSM-MFI算法里，不但要存儲(chǔ)IsFI-forest，而且還要存儲(chǔ)每個(gè)項(xiàng)的投影子集，在同樣多的事務(wù)數(shù)據(jù)下需要更多的內(nèi)存來(lái)存儲(chǔ)。而DSMMFI-DS算法在讀入時(shí)對(duì)項(xiàng)目按一定的順序排序后，那么它們共享的前綴個(gè)數(shù)就多了，使樹(shù)的存儲(chǔ)結(jié)構(gòu)得到了簡(jiǎn)化，節(jié)省了存儲(chǔ)空間；另一方面，在挖掘最大頻繁項(xiàng)集時(shí)也由于共享的前綴個(gè)數(shù)多，所以會(huì)在較短的時(shí)間里發(fā)現(xiàn)最大頻繁項(xiàng)集。

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

實(shí)驗(yàn)在CPU為Intel Pentium(R) Dual-Core 3.20 GHz、內(nèi)存為2.00 GB、操作系統(tǒng)為Windows 7 Ultimate的PC機(jī)上進(jìn)行，所有的實(shí)驗(yàn)程序均采用Visual C++ 6.0實(shí)現(xiàn)。實(shí)驗(yàn)中的模擬數(shù)據(jù)由IBM數(shù)據(jù)生成器產(chǎn)生，為了符合數(shù)據(jù)流產(chǎn)生的特點(diǎn)，我們?cè)O(shè)定產(chǎn)生10 000 k條數(shù)據(jù)項(xiàng)，其中1 k表示1 000條數(shù)據(jù)項(xiàng)，同時(shí)我們?cè)O(shè)定每個(gè)窗口的事務(wù)數(shù)據(jù)以及其他所有參數(shù)都使用默認(rèn)值。用戶設(shè)定的最小支持?jǐn)?shù)為0.1%，最大允許誤差ε固定為0.1Xs。對(duì)DSM-MFI和DSMMFI-DS兩種算法執(zhí)行時(shí)的時(shí)間和占內(nèi)存空間進(jìn)行比較，圖5顯示DSMMFI-DS算法比DSM-MFI算法的執(zhí)行時(shí)間要少，一方面DSMMFI-DS算法不需要為每個(gè)項(xiàng)建立投影，另一方面在發(fā)現(xiàn)最大頻繁項(xiàng)集時(shí)DSMMFI-DS采用雙向搜索策略，所以DSMMFI-DS算法比DSM-MFI算法的執(zhí)行效率要高。圖6顯示DSMMFI-DS算法比DSM-MFI算法在運(yùn)行時(shí)所占的內(nèi)存空間要小，特別是在隨著窗口數(shù)目增多時(shí)，這種效果更明顯：

(1)DSM-MFI需要為每個(gè)項(xiàng)做投影，內(nèi)存需要存儲(chǔ)每個(gè)項(xiàng)的投影子集；

(2)每個(gè)項(xiàng)在建立相應(yīng)的樹(shù)時(shí)沒(méi)有進(jìn)行排序，那么樹(shù)的分支也會(huì)比較多，存儲(chǔ)時(shí)需要更多的內(nèi)存空間；

(3)DSMMFI-DS算法會(huì)根據(jù)每個(gè)項(xiàng)的窗口衰減支持?jǐn)?shù)，及時(shí)將支持?jǐn)?shù)小的項(xiàng)刪除。因此，DSMMFI-DS算法所占的內(nèi)存空間比DSM-MFI要小。

Figure 5 Execution time of DSM-MFI algorithm and DSMMFI-DS algorithm圖5 DSM-MFI算法和DSMMFI-DS算法執(zhí)行時(shí)間

Figure 6 Memory of DSM-MFI algorithm and DSMMFI-DS algorithm圖6 DSM-MFI算法和DSMMFI-DS算法存儲(chǔ)內(nèi)存

MMFI-DS算法也是對(duì)DSM-MFI算法的改進(jìn)，為了驗(yàn)證MMFI-DS算法和DSMMFI-DS算法的優(yōu)越性，也對(duì)MMFI-DS算法進(jìn)行了實(shí)驗(yàn)對(duì)比。如圖7和圖8所示。

Figure 7 Execution time of MMFI-DS algorithm and DSMMFI-DS algorithm圖7 MMFI-DS算法和DSMMFI-DS算法執(zhí)行時(shí)間

Figure 8 Memory of MMFI-DS algorithm and DSMMFI-DS algorithm 圖8 MMFI-DS算法和DSMMFI-DS算法存儲(chǔ)內(nèi)存

通過(guò)實(shí)驗(yàn)可以看出，DSMMFI-DS算法比MMFI-DS算法的執(zhí)行效率更高。在圖7中，由于DSMMFI-DS算法采用的是全序關(guān)系存儲(chǔ)數(shù)據(jù)，與數(shù)據(jù)到來(lái)的時(shí)間順序沒(méi)有關(guān)系，在存儲(chǔ)上更節(jié)省時(shí)間；而MMFI-DS算法沒(méi)有按一定的順序存儲(chǔ)，在進(jìn)行挖掘操作時(shí)需要花費(fèi)很多時(shí)間來(lái)搜索。在圖8中，在窗口數(shù)目比較小時(shí)，MMFI-DS算法和DSMMFI-DS算法的存儲(chǔ)空間相差不大，但是隨著窗口數(shù)目的不斷增多，DSMMFI-DS算法更具有優(yōu)越性，占用的內(nèi)存空間小，主要是因?yàn)镈SMMFI-DS算法能夠及時(shí)地將不頻繁項(xiàng)集從樹(shù)中刪除。

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

本文提出了改進(jìn)的界標(biāo)窗口內(nèi)數(shù)據(jù)流最大頻繁項(xiàng)集挖掘算法DSMMFI-DS，該算法采用了按全序排序存儲(chǔ)，不需要對(duì)每個(gè)項(xiàng)進(jìn)行投影，并存儲(chǔ)投影子集；該算法在發(fā)現(xiàn)最大頻繁項(xiàng)集時(shí)采用自頂向下和自底向上的雙向搜索策略，能快速發(fā)現(xiàn)最大頻繁項(xiàng)集，最后該算法存儲(chǔ)每個(gè)項(xiàng)的窗口衰退支持?jǐn)?shù)，根據(jù)設(shè)定的窗口衰退支持?jǐn)?shù)閾值能夠盡早地刪除那些支持?jǐn)?shù)小的項(xiàng)，節(jié)省了內(nèi)存空間。通過(guò)實(shí)驗(yàn)得出DSMMFI-DS算法比DSM-MFI算法和MMF-DS算法具有更好的執(zhí)行效率。

[1] Li H, Lee S, Shan M. Online mining (recently) maximal frequent itemsets over data streams[C]∥Proc of the 15th International Workshops on Research Issues in Data Engineering:Stream Data Mining and Applications, 2005:11-18.

[2] Han J,Kamber M.Data mining:Concept and techniques[M].2nd edition. San Fransisco:Higher Education Press, 2001.

[3] Pan Yun-he,Wang Jin-long,Xu Cong-fu.State of the art on frequent pattern mining in data streams[J].Acta Automatica Sinica, 2006,32(4):594-602. (in Chinese)

[4] Meng Cai-xia. Research on mining frequent itemsets in data streams[J].Computer Engineering and Applications, 2010,46(24):138-140. (in Chinese)

[5] Zhuang Bo,Liu Xi-yu,Long Kun.TWCT-stream:Algorithm for mining frequent patterns in data streams[J]. Computer Engineering and Applications, 2009,45(20):147-150. (in Chinese)

[6] Yan Yue-jin.Research on mining algorithms of maximal frequent item sets[D]. Changsha:National University of Defense Technology,2005. (in Chinese)

[7] Yan Yue-jin, Li Zhou-jun, Chen Huo-wang. A depth-first search algorithm for mining maximal frequent itemsets[J].Journal of Computer Research and Development, 2005,42(3):462-467. (in Chinese)

[8] Huang Shu-cheng,Qu Ya-hui.Survey on data stream classification technologies[J].Application Research of Computers, 2009,26(10):3604-3609. (in Chinese)

[9] Ji Gen-lin,Yang Ming,Song Yu-qing, et al.Fast updating maximum frequent itemsets[J].Chinese Journal of Computer, 2005,28(1):128-135. (in Chinese)

[10] Li Hua Fu,Lee Suh Yin.Mining frequent itemsets over data streams using efficient window sliding techniques[J].Expert Systems with Applications, 2009,36(2,Part 1):1466-1477.

[11] Giannella C, Han Jia-wei, Pei Jian, et al. Mining frequent patterns in data streams at multiple time granularities[M]∥Data Mining:Next Generation Challenges and Future Directions,Cambridge:MIT, 2003.

[12] Ma Da,Wang Jia-qiang.A compressed FP-tree based on algorithm for mining maximal frequent itemsets[J].Journal of Changchun University of Science and Technology(Natural Science Edition), 2009,32(3):457-461. (in Chinese)

[13] Ao Fu-jiang,Yan Yue-jin,Liu Bao-hong, et al.Online mining maximal frequent itemsets in sliding window over data streams[J].Journal of Sytem Simulation, 2009,21(4):1134-1139. (in Chinese)

[14] Li Hai-feng,Zhang Ning. Maximal frequent itemsets mining method over data stream[J].Computer Engineering, 2012,38(21):45-48. (in Chinese)

[15] Hu De-min, Zhao Rui-ke. An improved algorithm for mining maximum frequent itemsets[J].Computer Applications and Software, 2012,29(12):186-188. (in Chinese)

[16] Zhang Yue-qin, Chen Dong. Mining method of data stream maximum frequent itemsets[J].Computer Engineering, 2010,36(22):86-90. (in Chinese)

[17] Hua Hong-juan, Zhang Jian, Chen Shao-hua. Mining algorithm for constrained maximum frequent itemsets based on frequent pattern tree[J].Computer Engineering, 2011,37(9):78-80. (in Chinese)

[18] Li H, Lee S, Shan M. An efficient algorithm for mining frequent itemsets over the entire history of data streams[C]∥Proc of the 1st International Workshop on Knowledge Discovery in Data Streams, held in conjunction with the 15th European Conference on Machine Learning (ECML 2004) and the 8th European Conference on the Principles and Practice of Knowledge Discovery in Databases (PKDD 2004), 2004:1.

[19] Mao Yi-min,Yang Lu-ming,Li Hong, et al. An effective algorithm of mining maximal frequent patterns on data stream[J]. Chinese High Technology Letters, 2010,3(3):100-107. (in Chinese)

[20] Song Yu-qing,Zhu Yu-quan,Sun Zhi-hui, et al.An algorithm and its updating algorithm based on FP-tree for mining maximum frequent itemsets[J].Journal of Software, 2003,14(9):1586-1592. (in Chinese)

附中文參考文獻(xiàn)：

[3] 潘云鶴，王金龍，徐從富.數(shù)據(jù)流頻繁模式挖掘研究進(jìn)展[J].自動(dòng)化學(xué)報(bào),2006,32(4):594-602.

[4] 孟彩霞.面向數(shù)據(jù)流的頻繁項(xiàng)集挖掘研究[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(24):138-140.

[5] 莊波，劉希玉，隆坤.TWCT-Stream：數(shù)據(jù)流上的頻繁模式挖掘算法[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(20):147-150.

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

[7] 顏躍進(jìn)，李舟軍，陳火旺.一種挖掘最大頻繁項(xiàng)集的深度優(yōu)先算法[J].計(jì)算機(jī)研究與發(fā)展,2005,42(3):462-467.

[8] 黃樹(shù)成，曲亞輝.數(shù)據(jù)流分類技術(shù)研究綜述[J].計(jì)算機(jī)應(yīng)用研究,2009,26(10):3604-3609.

[9] 吉根林，楊明，宋余慶,等.最大頻繁項(xiàng)目集的快速更新[J].計(jì)算機(jī)學(xué)報(bào)，2005,28(1):128-135.

[12] 馬達(dá)，王佳強(qiáng).一種基于壓縮FP-樹(shù)的最大頻繁項(xiàng)集挖掘算法[J].長(zhǎng)春理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2009,32(3):457-461.

[13] 敖富江，顏躍進(jìn)，劉寶宏，等.在線挖掘數(shù)據(jù)流滑動(dòng)窗口中最大頻繁項(xiàng)集[J].系統(tǒng)仿真學(xué)報(bào),2009,21(4):1134-1139.

[14] 李海峰，章寧.數(shù)據(jù)流上的最大頻繁項(xiàng)集挖掘方法[J].計(jì)算機(jī)工程,2012,38(21):45-48.

[15] 胡德敏，趙瑞可.一種改進(jìn)的最大頻繁項(xiàng)集挖掘算法[J].計(jì)算機(jī)應(yīng)用與軟件,2012,29(12):186-188.

[16] 張?jiān)虑?，陳東.數(shù)據(jù)流最大頻繁項(xiàng)集挖掘方法[J].計(jì)算機(jī)工程,2010,36(22):86-90.

[17] 花紅娟，張健，陳少華.基于頻繁模式樹(shù)的約束最大頻繁項(xiàng)集挖掘算法[J].計(jì)算機(jī)工程，2011,37(9):78-80.

[19] 毛伊敏，楊路明，李宏,等.一種有效的數(shù)據(jù)流最大頻繁模式挖掘算法[J].高技術(shù)通訊,2010,3(3):100-107.

[20] 宋余慶，朱玉全，孫志揮,等.基于FP-Tree的最大頻繁項(xiàng)目集挖掘及更新算法[J].軟件學(xué)報(bào),2003,14(9):1586-1592.

HUJian,born in 1967,PhD,professor,his research interests include knowledge engineering and knowledge discovery, and software engineering.

吳毛毛(1987-),男,江西鷹潭人，碩士生，研究方向?yàn)閿?shù)據(jù)挖掘。E-mail:wumaomao2010@163.com

WUMao-mao,born in 1987,MS candidate,his research interest includes data mining.

Animprovedalgorithmforminingmaximalfrequentitemsetsoverdatastreams

HU Jian,WU Mao-mao

(Institute of Information Engineering,Jiangxi University of Science and Technology,Ganzhou 341000,China)

Based on the algorithm of DSM-MFI, an improved algorithm, named DSMMFI-DS (Dictionary Sequence Mining Maximal Frequent Itemsets over Data Streams), is proposed. Firstly, it stores transaction data into DSFI-list in alphabetical order. Secondly, the data are stored sequentially into the tree similar to the summary data structure. Thirdly, non-frequent items in the tree and DSFI-list are removed, and the transaction items with the maximum count of window attenuation supports are deleted. Finally, the strategy (top-down and bottom-up two-way search) is used to mine maximal frequent itemsets over data streams, and case analysis and experiments prove that the algorithm DSMMFI-DS has better performance than the algorithm DSM-MFI.

data mining;data stream;landmark windows;maximal frequent itemsets;window attenuation support count

1007-130X(2014)05-0863-08

2012-12-03;

：2013-04-03

TP274.2

：A

10.3969/j.issn.1007-130X.2014.05.030

胡健(1967-),男,江西贛州人，博士，教授，研究方向?yàn)橹R(shí)工程與知識(shí)發(fā)現(xiàn)、軟件工程。E-mail:1050023437@qq.com

通信地址：341000 江西省贛州市客家大道156號(hào)

Address:156 Kejia Avenue,Ganzhou 341000,Jiangxi,P.R.China