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

摘 要:挖掘數(shù)據(jù)流中最大頻繁項(xiàng)集是從數(shù)據(jù)流中獲得信息的一種有效手段，是數(shù)據(jù)流挖掘研究的熱點(diǎn)之一。結(jié)合數(shù)據(jù)流的特點(diǎn)，提出了一種新的基于滑動(dòng)窗口的最大頻繁項(xiàng)集挖掘算法。該算法用位圖來存儲(chǔ)數(shù)據(jù)流中流動(dòng)的數(shù)據(jù);采用直接覆蓋的方法存儲(chǔ)和更新數(shù)據(jù)流上的數(shù)據(jù);在深度優(yōu)先搜索挖掘最大頻繁項(xiàng)集時(shí)，除采用經(jīng)典的剪枝策略外，還提出了與父等價(jià)原理相對(duì)應(yīng)的子等價(jià)剪枝策略;最后將挖掘結(jié)果存儲(chǔ)在索引鏈表中以提高超集檢測(cè)效率，進(jìn)一步減少挖掘最大頻繁項(xiàng)集的時(shí)間。理論分析和實(shí)驗(yàn)結(jié)果證實(shí)了該算法在時(shí)間和空間上的有效性。

關(guān)鍵詞:數(shù)據(jù)流; 數(shù)據(jù)挖掘; 最大頻繁項(xiàng)集; 滑動(dòng)窗口; 位圖

中圖分類號(hào):TP391

文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1001-3695(2010)02-0519-04

doi:10.3969/j.issn.1001-3695.2010.02.032

Mining maximal frequent itemsets over

data streams using sliding window

YANG Lu-ming， LIU Li-xin， MAO Yi-min， XIE Dong

(School of Information Science Engineering， Central South University， Changsha 410083， China)

Abstract:Mining maximal frequent itemsets over streaming data is one of the most important issues in mining data stream. This paper proposed an efficient algorithm to mine maximal frequent itemsets in sliding window. First， used bitmap to deal with the streaming data. Second， adopted depth first to find maximal frequent itemsets when mining.Moreover， besides typical pruning strategies， this paper developed a new pruning strategy corresponding to the parent equivalency pruning to prune. Third， used index structure to store the maximal frequent itemsets， which could speed up the speed of superset test. Theoretical analysis and experimental results show that the proposed method is efficient.

Key words:data stream; data mining; maximal frequent itemsets; sliding window; bitmap

0 引言

近年來，數(shù)據(jù)流廣泛應(yīng)用于金融分析、傳感器網(wǎng)絡(luò)、Web挖掘、搜索引擎、網(wǎng)絡(luò)監(jiān)控、電信部門和電話分析等領(lǐng)域。從數(shù)據(jù)流中獲得有用信息的一種方法是獲得頻繁項(xiàng)集，數(shù)據(jù)流中的頻繁項(xiàng)集挖掘逐漸成為數(shù)據(jù)挖掘研究的熱點(diǎn)。由于數(shù)據(jù)流的無限性、高速性和不可預(yù)測(cè)性特點(diǎn)[1]，使得應(yīng)用于靜態(tài)數(shù)據(jù)庫(kù)的頻繁項(xiàng)集挖掘算法不能直接應(yīng)用到數(shù)據(jù)流中的頻繁項(xiàng)集挖掘中。

與頻繁項(xiàng)集和頻繁閉項(xiàng)集相比，最大頻繁項(xiàng)集有更簡(jiǎn)潔的表達(dá)形式和較少的數(shù)量，且在某些情況下只需要最大頻繁項(xiàng)集。因此，數(shù)據(jù)流中最大頻繁項(xiàng)集挖掘得到了廣泛研究，其主要算法有estDec+[2]、DSM-MFI[3]和INSTANT[4]等。其中，estDec+算法采用CP-tree存儲(chǔ)數(shù)據(jù)流上的數(shù)據(jù)，通過控制合并域在盡力減少內(nèi)存消耗情況下找到最大頻繁項(xiàng)集;DSM-MFI算法用投影的方法把每個(gè)事務(wù)的投影子集存儲(chǔ)到概要頻繁項(xiàng)目森林結(jié)構(gòu)中，并采用自頂向下的搜索方法挖掘最大頻繁項(xiàng)集;INSTANT算法采用集合操作處理數(shù)據(jù)，能夠在事務(wù)到達(dá)時(shí)立刻輸出目前所有數(shù)據(jù)的最大頻繁項(xiàng)集。以上算法都是基于界標(biāo)窗口模型挖掘數(shù)據(jù)流中的最大頻繁項(xiàng)集，沒有考慮到數(shù)據(jù)流出當(dāng)前窗口的情況。在實(shí)際應(yīng)用中，人們往往關(guān)心滑動(dòng)窗口內(nèi)的數(shù)據(jù)，因此滑動(dòng)窗口中最大頻繁項(xiàng)集的挖掘受到更多關(guān)注。

本文提出了數(shù)據(jù)流中基于滑動(dòng)窗口的最大頻繁項(xiàng)集挖掘算法MMI-BET(mining maximal itemsets based on bit enumeration tree)。該算法使用位圖存儲(chǔ)數(shù)據(jù)流中的數(shù)據(jù)，在滑動(dòng)窗口已滿階段和未滿階段采用不同的策略處理數(shù)據(jù)流中數(shù)據(jù)的流動(dòng)。當(dāng)用戶發(fā)出查詢請(qǐng)求時(shí)，深度優(yōu)先搜索挖掘滑動(dòng)窗口中最大頻繁項(xiàng)集。理論分析和實(shí)驗(yàn)證明了該算法的時(shí)空效率和在不同數(shù)據(jù)集下有較好的適應(yīng)性。

1 相關(guān)知識(shí)

數(shù)據(jù)流是由一系列連續(xù)的、無窮的、流動(dòng)的事務(wù)組成，各個(gè)事務(wù)記做T1，T2，…，Tn， 可以看做一個(gè)無窮大的數(shù)據(jù)庫(kù)。

定義1 在數(shù)據(jù)庫(kù)中，所有項(xiàng)的集合I={i1，i2，…，im}。其中ik(k=1，2，…，m)代表一個(gè)項(xiàng)目。所有事務(wù)的集合D={T1，T2，…，Tn}。其中每個(gè)事務(wù)Ti(i=1，2， …，n)包含I的一個(gè)子集X和事務(wù)的標(biāo)志號(hào)tid。如果X包含的項(xiàng)的數(shù)目為k，則稱X為k項(xiàng)集。

定義2 項(xiàng)集X的支持度support (X) 是在D中包含X的事務(wù)個(gè)數(shù)占所有事務(wù)個(gè)數(shù)的百分比。用戶指定的支持度的閾值為s。如果support (X)≥s，則稱X是頻繁項(xiàng)集;如果頻繁項(xiàng)集X的所有超集都是不頻繁的，則稱X為最大頻繁項(xiàng)集。所有頻繁項(xiàng)集的集合記做FI(frequent itemsets)，所有最大頻繁項(xiàng)集的集合記做MFI(maximal frequent itemsets)。

關(guān)于頻繁項(xiàng)集和最大頻繁項(xiàng)集，有如下兩個(gè)最基本的性質(zhì):

性質(zhì)1 如果X，YI，若XFI且XY，則YFI。

性質(zhì)2 如果X，YI，若X∈MFI且YX，則YMFI。

定義3 將數(shù)據(jù)流數(shù)據(jù)分段，每一段內(nèi)包含相同的事務(wù)數(shù)，這樣的一個(gè)分段就叫做一個(gè)基本窗口，記為W。每個(gè)基本窗口包含的事務(wù)的個(gè)數(shù)是基本窗口的大小，記為|BW|。滑動(dòng)窗口SW是由一系列連續(xù)的基本窗口組成，記為〈W1，W2， …，WN〉，每一個(gè)滑動(dòng)窗口包含的基本窗口的個(gè)數(shù)是滑動(dòng)窗口的大小，記為|SW|。

2 算法描述

滑動(dòng)窗口中頻繁項(xiàng)集挖掘可以分為數(shù)據(jù)存儲(chǔ)、數(shù)據(jù)更新和頻繁項(xiàng)集挖掘三步。數(shù)據(jù)流的無限性和高速性要求存儲(chǔ)數(shù)據(jù)流上數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)既要盡力節(jié)約內(nèi)存空間，又要適合數(shù)據(jù)流上數(shù)據(jù)的更新。目前，常用的結(jié)構(gòu)有樹(或森林)和位圖結(jié)構(gòu)。本文采用位圖表示數(shù)據(jù)流中的數(shù)據(jù)信息，通過對(duì)位圖數(shù)據(jù)的變換來實(shí)現(xiàn)數(shù)據(jù)的更新。當(dāng)用戶發(fā)出查詢請(qǐng)求時(shí)，MMI-BET算法根據(jù)當(dāng)前滑動(dòng)窗口的位圖信息，采用深度優(yōu)先搜索來挖掘當(dāng)前滑動(dòng)窗口中的最大頻繁項(xiàng)集。

2.1 位圖結(jié)構(gòu)

每個(gè)項(xiàng)集的位圖信息用victor表示，用「滑動(dòng)窗口包含事務(wù)數(shù)/32個(gè)無符號(hào)整型數(shù)據(jù)表示項(xiàng)集在當(dāng)前滑動(dòng)窗口各事務(wù)中是否出現(xiàn)。如果項(xiàng)集在某事務(wù)中出現(xiàn)，相應(yīng)位為1，否則為0。采用位圖結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)的優(yōu)點(diǎn)有:使用邏輯與運(yùn)算，可以根據(jù)k項(xiàng)集的支持信息victor得到k+1項(xiàng)集的支持信息victor;對(duì)無符號(hào)數(shù)據(jù)中的某位置0或置1操作實(shí)現(xiàn)數(shù)據(jù)的存儲(chǔ)和更新;無符號(hào)整型數(shù)據(jù)中含有1的個(gè)數(shù)就是此項(xiàng)集的支持度。

例1 設(shè)數(shù)據(jù)流上的數(shù)據(jù)〈T1:cd〉，〈T2:ad〉，〈T3:ac〉，〈T4:abcd〉，〈T5:bc〉，〈T6:bce〉，…，取滑動(dòng)窗口的基本窗口大小為1，滑動(dòng)窗口大小為5。此時(shí)第一個(gè)滑動(dòng)窗口包含的事務(wù)為T1，T2，T3，T4，T5;第二個(gè)滑動(dòng)窗口包含的事務(wù)為T6，T2，T3，T4，T5。第二個(gè)滑動(dòng)窗口各項(xiàng)集的位圖信息如表1所示。

表1 第二個(gè)窗口的位圖

項(xiàng)集T6T2T3T4T5

a01110

b10011

c10111

d01010

e10000

如果采用無符號(hào)整型數(shù)據(jù)的后五位表示數(shù)據(jù)的位支持信息，項(xiàng)集a的支持信息為a.victor=14， 支持度為support(a)=3;項(xiàng)集b的支持信息b.victor=19，支持度為support(b)=3;項(xiàng)集ab的支持信息為ab.victor=a.victor∩b.victor=14∩19=2，支持度為support(ab)=1。

2.2 滑動(dòng)窗口初始階段和滑動(dòng)階段數(shù)據(jù)的處理

滑動(dòng)窗口技術(shù)可以分為兩個(gè)階段[5]:初始階段和滑動(dòng)階段。在初始階段，新數(shù)據(jù)不斷移入窗口，沒有數(shù)據(jù)需要移出;在滑動(dòng)階段，傳統(tǒng)的滑動(dòng)窗口采用的是移動(dòng)覆蓋的方法來更新數(shù)據(jù)，即隨著窗口的滑動(dòng)，最舊的基本窗口內(nèi)的數(shù)據(jù)被移出，其他基本窗口數(shù)據(jù)前移，覆蓋前一個(gè)基本窗口，新數(shù)據(jù)移入到最末端的基本窗口。當(dāng)滑動(dòng)窗口比較大時(shí)，這種采用移動(dòng)覆蓋的方法因移動(dòng)數(shù)據(jù)時(shí)間消耗會(huì)大大增加。本文采用直接覆蓋的方法來處理滑動(dòng)窗口中數(shù)據(jù)的更新，能夠減少移動(dòng)數(shù)據(jù)的時(shí)間消耗。如果一個(gè)滑動(dòng)窗口內(nèi)有k個(gè)基本窗口，分別標(biāo)記為0，1…，k-1，數(shù)據(jù)存儲(chǔ)和更新算法如算法1所示。

算法1 數(shù)據(jù)的存儲(chǔ)和更新

輸入:數(shù)據(jù)流中數(shù)據(jù)。

輸出:位圖信息。

updata()

{ if(0<=tid<=k-1)

//窗口未滿階段

{x=tid/32;y=tid%32;

//表示位圖中第x數(shù)的第y位存儲(chǔ)此項(xiàng)集的信息

for(事務(wù)集中每一個(gè)項(xiàng)集item)

{

if(item在此事務(wù)中出現(xiàn))

此項(xiàng)集位圖中第x個(gè)數(shù)據(jù)w的第y位置1;

if(item在此事務(wù)中不出現(xiàn))

此項(xiàng)集位圖中第x個(gè)數(shù)據(jù)w的第y位置0;

}

tid++;}

if(tid>k-1)

//窗口已滿階段

{x=(tid%(|BW||SW|))/32;y=tid%32;

for(事務(wù)集中每一個(gè)項(xiàng)集item)

{

if(item在此事務(wù)中出現(xiàn))

此項(xiàng)集位圖中第x個(gè)數(shù)據(jù)w的第y位置1;

if(item在此事務(wù)中不出現(xiàn))

此項(xiàng)集位圖中第x個(gè)數(shù)據(jù)w的第y位置0;

}

tid++;}

}

當(dāng)滑動(dòng)窗口滑動(dòng)時(shí)，對(duì)于事務(wù)集中每一個(gè)項(xiàng)集，首先直接計(jì)算其位圖中新數(shù)據(jù)存放的位置，然后直接對(duì)該位置進(jìn)行置0或置1。與傳統(tǒng)的滑動(dòng)窗口相比較，含有k個(gè)基本窗口的滑動(dòng)窗口，在每次滑動(dòng)時(shí)，減少了k-1次滑動(dòng)時(shí)間的消耗。更新項(xiàng)集位圖信息對(duì)數(shù)據(jù)置0或置1方法是:通過w=w|(1<<(31-y))和w=w~(1<<(31-y))分別實(shí)現(xiàn)對(duì)數(shù)據(jù)w的左邊第y位置1和置0。

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

集合枚舉樹[6]被很多頻繁項(xiàng)集挖掘算法采用，其中深度優(yōu)先搜索是沿著樹的子孫往下搜索，一旦發(fā)現(xiàn)某個(gè)節(jié)點(diǎn)的頭項(xiàng)集是不頻繁的，該節(jié)點(diǎn)及所有子孫節(jié)點(diǎn)將被剪掉。深度優(yōu)先搜索挖掘最大頻繁項(xiàng)集時(shí)，在保留可能的最大頻繁項(xiàng)集前提下，剪枝策略能刪除無用的或者重復(fù)的節(jié)點(diǎn)以提高算法的挖掘效率，節(jié)約挖掘時(shí)間。

MAFIA[7]是采用深度優(yōu)先搜索較好的算法，其中運(yùn)用了頻繁擴(kuò)展策略、前瞻剪枝策略和父等價(jià)剪枝策略。頻繁擴(kuò)展策略根據(jù)性質(zhì)1得來;前瞻剪枝策略根據(jù)性質(zhì)2得來;父等價(jià)剪枝策略[8]的思想是:節(jié)點(diǎn)n在生成子節(jié)點(diǎn)時(shí)，如果頭項(xiàng)集head支持事務(wù)的集合是可擴(kuò)展項(xiàng)集ei中的項(xiàng)x的支持事務(wù)集合的子集，則任何包含該節(jié)點(diǎn)頭項(xiàng)集的最大頻繁項(xiàng)集也必定包含該項(xiàng)x。

本文提出一種與父等價(jià)剪枝策略相對(duì)應(yīng)的新的剪枝策略——子等價(jià)剪枝策略。它能剪掉以上三種策略不能剪掉的節(jié)點(diǎn)，且使用上述四種剪枝策略能大大縮小搜索空間。為了最佳地發(fā)揮剪枝策略，同時(shí)對(duì)擴(kuò)展項(xiàng)目集ei中的項(xiàng)目進(jìn)行動(dòng)態(tài)排序。

引理1 子等價(jià)剪枝策略。在集合枚舉樹中，每個(gè)節(jié)點(diǎn)由頭項(xiàng)集head、可擴(kuò)展項(xiàng)集ei、位支持信息victor組成。對(duì)于節(jié)點(diǎn)n，如果n.ei中的某項(xiàng)集y有:n.head∪y的支持事務(wù)集合是頭項(xiàng)集n.head的支持事務(wù)集合的子集，說明任何包含項(xiàng)集y的節(jié)點(diǎn)也必定包含項(xiàng)集n.head，則可以把同層中位于節(jié)點(diǎn)n右邊的節(jié)點(diǎn)的ei中的項(xiàng)集y去掉，也可以把以y為頭項(xiàng)集的節(jié)點(diǎn)及其子樹去掉。

證明 設(shè)項(xiàng)集X的支持事務(wù)集合表示為TS(X)，那么對(duì)于節(jié)點(diǎn)n右邊的任意節(jié)點(diǎn)p有(p.head∪y)(p.head∪y∪n.head)。由于TS(n.head∪y)TS(n.head)，如果p.head∪y是頻繁的，那么p.head∪y∪n.head也是頻繁的;如果p.head∪y是不頻繁的，那么p.head∪y∪n.head也是不頻繁的。說明在遍歷節(jié)點(diǎn)n右邊包含y的節(jié)點(diǎn)不會(huì)產(chǎn)生新的最大頻繁項(xiàng)集。

MMI-BET算法在深度優(yōu)先搜索時(shí)采用上述四種剪枝策略和基于索引的超集檢測(cè)方法挖掘最大頻繁項(xiàng)集的遞歸算法如算法2所示。

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

輸入:當(dāng)前滑動(dòng)窗口頻繁一項(xiàng)集和相應(yīng)的位圖支持信息。

輸出:當(dāng)前滑動(dòng)窗口中的最大頻繁項(xiàng)集。

search(node)

{if(none.head∪node.ei是頻繁的)

//前瞻策略剪枝

{檢測(cè)在MFI中是否存在超集，如不存在則加入到MFI;return;}

for(node.ei中每一個(gè)項(xiàng)目x)

{if((node.head∪x)小于最小支持度)

node.ei=node.ei-x;

//頻繁擴(kuò)展策略剪枝

if(support(node.head∪x)=support(node.head))

{node.head=node.head+x;node.ei=node.ei-x;}

//父等價(jià)原理剪枝

if(support(node.head∪x)=support(x))

{for(每一個(gè)node的右邊節(jié)點(diǎn)right-node)

right-node.tail=right-node.tail-x;

delete right-node.head=x;}

//子等價(jià)原理剪枝

}

reorder ei by increaming support;

if(node.head是葉節(jié)點(diǎn))

//葉子節(jié)點(diǎn)進(jìn)行超級(jí)索引檢測(cè)

在MFI中檢測(cè)是否存在超集，若不存在則加入到MFI;

else

for(node.ei中每一個(gè)項(xiàng)目x)

{creatnode.head=node.head+x; creatnode.ei=node.ei-x;

search (creatnode); }

//對(duì)新節(jié)點(diǎn)遞歸調(diào)用此函數(shù)

}

把某一頻繁項(xiàng)集加入到MFI時(shí)，首先對(duì)其進(jìn)行超集檢測(cè)，即在MFI中查找是否存在它的超集。超集檢測(cè)的性能很大程度上依賴于MFI集合的大小，如果MFI較大，按照順序逐個(gè)對(duì)比判斷是非常耗時(shí)的。MAFIA引用局部最大頻繁項(xiàng)集來縮小超集檢測(cè)空間，但是存儲(chǔ)局部最大頻繁項(xiàng)集也消耗一定的空間。本文采用索引鏈表方法來存儲(chǔ)已經(jīng)找到的最大頻繁項(xiàng)集，超集檢測(cè)時(shí)根據(jù)索引來減少超集檢測(cè)的檢測(cè)空間，提高了超集檢測(cè)的效率，并且沒有因超集檢測(cè)消耗額外的空間。

MFI中的每一個(gè)最大頻繁項(xiàng)集的第一個(gè)項(xiàng)目作為一級(jí)索引index1，第二個(gè)項(xiàng)目作為二級(jí)索引index2，其余部分以鏈表形式存儲(chǔ)。 假設(shè)要進(jìn)行超集檢測(cè)的頻繁項(xiàng)集的第一個(gè)項(xiàng)目是x1，第二個(gè)項(xiàng)目是x2，根據(jù)集合枚舉樹的特性得出需要檢測(cè)的空間分兩種情況:index1

例1中，取最小支持?jǐn)?shù)為2，在第二個(gè)滑動(dòng)窗口中1項(xiàng)集a，b，c，d是頻繁的，e是不頻繁的。根據(jù)a，b，c，d的位圖信息與集合枚舉樹枚舉思想，沒有采用任何剪枝策略時(shí)的搜索空間如圖1所示。

采用MMI-BET算法的搜索空間和搜索結(jié)果如圖2所示，其中node1.head=a和其擴(kuò)展項(xiàng)集中d滿足子等價(jià)原理，可以進(jìn)行子等價(jià)剪枝;node2.head=b和其擴(kuò)展項(xiàng)集中c滿足父等價(jià)原理，可以進(jìn)行父等價(jià)剪枝。線框內(nèi)標(biāo)出的項(xiàng)集是挖掘的最大頻繁項(xiàng)集。

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

實(shí)驗(yàn)環(huán)境為一臺(tái)Windows XP操作系統(tǒng)的PC機(jī)，AMD Turion 64位雙核處理器、512 MB內(nèi)存，且程序在VC++ 6.0環(huán)境中運(yùn)行。實(shí)驗(yàn)采用IBM模擬數(shù)據(jù)產(chǎn)生器(http://www.almaden.ibm.com )產(chǎn)生的數(shù)據(jù)集，合成數(shù)據(jù)的主要參數(shù)為:T表示事務(wù)的平均長(zhǎng)度，I表示頻繁項(xiàng)集的平均長(zhǎng)度，D表示事務(wù)的數(shù)目，1k代表1 000條事務(wù)，實(shí)驗(yàn)中所有的項(xiàng)目數(shù)目固定在1 000。

3.1 算法的適應(yīng)性

滑動(dòng)窗口大小為10k且流入窗口的數(shù)據(jù)流的事務(wù)數(shù)也為10k，即滑動(dòng)窗口處于初始階段，沒有數(shù)據(jù)需要移出，運(yùn)行MMI-BET算法，此時(shí)與在靜態(tài)數(shù)據(jù)集挖掘最大頻繁項(xiàng)集類似。同時(shí)在10k的靜態(tài)數(shù)據(jù)集下運(yùn)行MAFIA算法，并使用稀疏數(shù)據(jù)集T10I4D100k和稠密數(shù)據(jù)集T30I20D100k來分析MMI-BET和MAFIA算法在這兩種不同數(shù)據(jù)集下的適應(yīng)性。

3.2 算法的收縮性

使用稀疏數(shù)據(jù)集T10I4D100k和稠密數(shù)據(jù)集T30I20D100k來評(píng)估算法MMI-BET的收縮性，這兩套數(shù)據(jù)集的最小支持度分別為0.3% 和1%，滑動(dòng)窗口的大小均為10k。圖4(a)說明在兩套數(shù)據(jù)集下，當(dāng)事務(wù)數(shù)從10k增長(zhǎng)到100k時(shí)，即滑動(dòng)窗口滑動(dòng)了10次，運(yùn)行時(shí)間逐漸趨于穩(wěn)定。因?yàn)镸MI-BET算法數(shù)據(jù)存儲(chǔ)和更新的速度很快，并且只在最近的滑動(dòng)窗口中挖掘最大頻繁項(xiàng)集。圖4(b)說明在兩套數(shù)據(jù)集下，當(dāng)滑動(dòng)窗口不斷移動(dòng)時(shí)，所消耗的存儲(chǔ)容量都趨于穩(wěn)定。因?yàn)榛瑒?dòng)窗口只存儲(chǔ)最近基本窗口的數(shù)據(jù)，且使用位圖存儲(chǔ)數(shù)據(jù)流中數(shù)據(jù)所占內(nèi)存空間非常小。實(shí)驗(yàn)證明，MMI-BET算法具有可收縮性和可行性。

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

本文提出了一種新的數(shù)據(jù)流中基于滑動(dòng)窗口的最大頻繁項(xiàng)集挖掘算法MMI-BET。

a)該算法采用位圖信息存儲(chǔ)數(shù)據(jù)流中的數(shù)據(jù)，在數(shù)據(jù)更新時(shí)不采用傳統(tǒng)的移動(dòng)覆蓋技術(shù)，而是計(jì)算出最舊數(shù)據(jù)的位置之后，最新的數(shù)據(jù)直接覆蓋最舊數(shù)據(jù)，這樣減少了數(shù)據(jù)存儲(chǔ)和更新花費(fèi)的時(shí)間。

b)在采用深度優(yōu)先策略挖掘最大頻繁項(xiàng)集時(shí)，除了采用經(jīng)典的剪枝策略外，還提出了子等價(jià)剪枝策略，此策略能剪掉已有的剪枝策略不能剪掉的節(jié)點(diǎn)。

c)在沒有增加額外存儲(chǔ)空間前提下，根據(jù)索引和集合枚舉樹的特點(diǎn)來縮小超集檢測(cè)的檢測(cè)空間，進(jìn)一步減少最大頻繁項(xiàng)挖掘時(shí)間。實(shí)驗(yàn)結(jié)果表明，MMI-BET算法能快速準(zhǔn)確地輸出數(shù)據(jù)流中當(dāng)前滑動(dòng)窗口中的最大頻繁項(xiàng)集。

參考文獻(xiàn):

[1]LI Huo-fu， LEE S Y. Mining frequent itemsets over data streams using efficient window sliding techniques[J]. Expert Systems with Applications， 2009，36(2):1466-1477.

[2]LEE D， LEE W. Finding maximal frequent itemsets over online data stream adaptively[C]//Proc of the 5th IEEE International Conference on Data Mining.Houston: Institute of Electrical and Electronics Engineers Inc， 2005:266-273.

[3]LI Hua-fu， LEE S Y， SHAN M K. Online mining (recently) maximal frequent itemsets over data stream[C]//Proc of the 15th RIDE-SDMA Conference. Tokyo:IEEE Computer Society ，2005:11-18.

[4]MAO Guo-jun， Wu Xin-dong， ZHU Xing-quan， et al. Mining maximal frequent itemsets from data stream[J]. Journal of Information Science， 2007， 33(3):251-262.

[5]SIRISH C， FRANKLIN M J. A system for streaming queries over streaming data[C]//Porc of the 28th International Conference on Very Large Data Bases. New York: Springer-Verlag， 2002:140-156.

[6]MANNILA H， TOIVONEN H. Level wise search and borders of theories in knowledge discovery[J]. Data Mining and Knowledge Discovery，1997，11(3):241-258.

[7]BURDICK D， CALIMLIM M. MAFIA: a maximal frequent itemset algorithm for transaction databases[C]//Proc of the 17th International Conference on Data Engineering. [S.l.]:IEEE Educational Activities Department，2001:1490-1504.

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