數(shù)據(jù)流中頻繁模式挖掘方法的研究及應(yīng)用.pdf

1、經(jīng)過近十幾年的研究，數(shù)據(jù)挖掘技術(shù)已經(jīng)相當(dāng)成熟。作為數(shù)據(jù)挖掘研究中的基礎(chǔ)任務(wù)，頻繁模式挖掘一直是一個(gè)熱點(diǎn)問題，得到了廣泛而深入的研究。然而，隨著網(wǎng)絡(luò)、電信和傳感器技術(shù)的發(fā)展，出現(xiàn)了二種新的流數(shù)據(jù)模型。數(shù)據(jù)流是大量的、連續(xù)的、無限的、快速變化的數(shù)據(jù)元素的序號。一般無法將數(shù)據(jù)流中的數(shù)據(jù)全部保存起來，對數(shù)據(jù)流中的數(shù)據(jù)一經(jīng)處理除非刻意保存，否則就無法再次訪問或再次訪問的代價(jià)很大。為了從數(shù)據(jù)流中發(fā)現(xiàn)知識和模式，必須開發(fā)單遍掃描的、聯(lián)機(jī)的、多層的和多

2、維的流處理和分析方法。 數(shù)據(jù)流挖掘是近年來數(shù)據(jù)挖掘領(lǐng)域的一個(gè)熱點(diǎn)，大量數(shù)據(jù)流應(yīng)用的產(chǎn)生促使數(shù)據(jù)流挖掘算法相繼被提出。頻繁模式挖掘是數(shù)據(jù)流挖掘中的重要研究內(nèi)容被廣泛應(yīng)用于關(guān)聯(lián)規(guī)則發(fā)現(xiàn)、冰山查詢、分類和聚類等問題。由于數(shù)據(jù)流本身的特點(diǎn)，數(shù)據(jù)流上的頻繁模式挖掘只能對數(shù)據(jù)掃描一次，因此對頻繁模式挖掘算法在時(shí)間和空間上都提出了更高的要求。許多現(xiàn)有的算法需要多次掃描整個(gè)數(shù)據(jù)集，因此在數(shù)據(jù)流頻繁模式挖掘中的應(yīng)用受到限制。與傳統(tǒng)的頻繁模式挖掘不

3、同，為了挖掘數(shù)據(jù)流中的頻繁模式，一般允許結(jié)果存在一個(gè)足夠小的誤差，以適應(yīng)數(shù)據(jù)流的無限性并提高挖掘的效率。 本文綜述了數(shù)據(jù)流頻繁模式挖掘研究的現(xiàn)狀，分析了兩個(gè)經(jīng)典的算法Lossy Counting和FP-stream，兩者都能夠挖掘數(shù)據(jù)流中的頻繁模式的完全集，但又具有各自的特點(diǎn)。Lossy Counting算法可以將候選項(xiàng)集存儲在外存，使算法具有較好的空間效率，但算法只能給出整個(gè)流上的頻繁模式，不能區(qū)分歷史數(shù)據(jù)的不同影響。而FP-

4、stream算法利用傾斜時(shí)間窗框架存儲每個(gè)模式在多個(gè)時(shí)間粒度下的頻數(shù)，因而具有較好的動態(tài)性，但算法在支持度較低時(shí)占用大量內(nèi)存。 本文在分析已有算法的基礎(chǔ)上，提出了結(jié)合傾斜時(shí)間窗的TWCT樹結(jié)構(gòu)，可以保存不同時(shí)間粒度下的頻繁模式的完全集，并設(shè)計(jì)了其順序更新和刪除算法，使其能夠存儲在外存，從而有效地降低算法的內(nèi)存空間需求。結(jié)合TWCT樹結(jié)構(gòu)特點(diǎn)，提出了數(shù)據(jù)流上的頻繁模式挖掘算法TWCT-Stream，其模式生長的TWCT-Growc

5、h算法按字典順序生成頻繁模式，以配合TWCT結(jié)構(gòu)的順序更新。實(shí)驗(yàn)證實(shí)算法的內(nèi)存需求低于FP-stream等同類算法。本文結(jié)合滑動窗口模型提出了兼有水平數(shù)據(jù)格式和垂直數(shù)據(jù)格式兩者特點(diǎn)的VDT-SW結(jié)構(gòu)，該結(jié)構(gòu)便于處理滑動窗口的數(shù)據(jù)更新，可以結(jié)合使用多種頻繁模式挖掘算法。利用該結(jié)構(gòu)特點(diǎn)，針對即時(shí)查詢問題，提出了一個(gè)時(shí)間復(fù)雜度低的快速項(xiàng)集計(jì)數(shù)查詢算法VDT-SW-Query。將基于VDT-SW結(jié)構(gòu)的數(shù)據(jù)流頻繁模式挖掘應(yīng)用于電信數(shù)據(jù)分析領(lǐng)域，設(shè)