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

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

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

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

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

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