[摘 要] 由于數(shù)據(jù)流自身的特性，數(shù)據(jù)流挖掘已經成為數(shù)據(jù)挖掘的一個新的研究方向，在介紹數(shù)據(jù)流的概念的基礎上，分析了數(shù)據(jù)流挖掘的概念和模型，總結了現(xiàn)有的數(shù)據(jù)流挖掘算法。

[關鍵詞] 數(shù)據(jù)流 數(shù)據(jù)流挖掘 模型 算法

近年來，隨著計算機技術和通信網絡技術的蓬勃發(fā)展，由于眾多應用領域的需求，數(shù)據(jù)流處理問題，特別是基于數(shù)據(jù)流的挖掘問題已受到越來越多的研究人員關注。

一、數(shù)據(jù)流以及數(shù)據(jù)流挖掘

1.數(shù)據(jù)流。數(shù)據(jù)流由一系列按序到達的數(shù)據(jù)組成，也可看作是信息傳輸過程中經編碼處理的數(shù)字信號串。若令t表示任一時間戳，at表示在t時刻到達的數(shù)據(jù)元素，則數(shù)據(jù)流可以表示為無限集合{…，at-1，，at，at+1，…}。

2.數(shù)據(jù)流挖掘。數(shù)據(jù)流挖掘就是在數(shù)據(jù)流上發(fā)現(xiàn)提取隱含在其中的。人們事先不知道的，但又潛在有用的信息和知識的過程。流數(shù)據(jù)挖掘方面的研究主要包括多數(shù)據(jù)流挖掘和單數(shù)據(jù)流挖掘，挖掘多條數(shù)據(jù)流的主要目的是分析多條并行到達的數(shù)據(jù)流之間的關聯(lián)，對單數(shù)據(jù)流的挖掘則涵蓋了分類、頻繁模式挖掘、聚類等多項傳統(tǒng)數(shù)據(jù)挖掘中的主要任務，挖掘變化的數(shù)據(jù)流是一項特殊的任務，目前主要是以單數(shù)據(jù)流為對象進行研究的。

二、數(shù)據(jù)流挖掘的模型

按算法處理數(shù)據(jù)流時所選取的時序范圍，數(shù)據(jù)流模型可分為以下幾類。

1.快照模型:處理數(shù)據(jù)的范圍限制在兩個預定義的時間戳之間。

2.界標模型:處理數(shù)據(jù)的范圍從某一個已知的初始時間點到當前時間點為止。

3.滑動窗口模型:處理數(shù)據(jù)的范圍由某個固定大小的滑動窗口確定，此滑動窗口的終點永遠為當前時刻，其中，滑動窗口的大小可以由一個時間區(qū)間定義，也可以由窗口所包含的數(shù)據(jù)項數(shù)目定義。

典型的數(shù)據(jù)流挖掘模型如圖所示。

三、數(shù)據(jù)流挖掘算法

目前數(shù)據(jù)流挖掘方面的研究成果主要集中在數(shù)據(jù)流的聚類、分類和頻繁模式挖掘方面。

1.數(shù)據(jù)流分類算法。數(shù)據(jù)流分類就是提出一個分類模型(或函數(shù)），并通過單遍掃描數(shù)據(jù)流，持續(xù)地利用分類模型將數(shù)據(jù)對象（數(shù)據(jù)流的數(shù)據(jù)點或元組等)映射到某一個給定的類別中。P.Domingos 和 G..Hulten他們提出了一種Hoeffding決策樹分類算法VFDT(Very Fast Decision Tree)，使用恒定的內存大小和時間處理每個樣本，有效地解決了時間、內存和樣本對數(shù)據(jù)挖掘，特別是高速數(shù)據(jù)流上的數(shù)據(jù)挖掘的限制。VFDT使用信息熵選擇屬性，通過建立Hoeffding樹來進行決策支持，并使用 Hoeffding 約束來保證高精度地處理高速數(shù)據(jù)流。

由于VFDT算法假設數(shù)據(jù)是從靜態(tài)分布中隨機獲取的，所以不能反映數(shù)據(jù)隨時間變化的趨勢。因此，P.Domingos和G..Hulten引入了滑動窗口技術，對VFDT算法進行改進，提出了CVFDT (Concept-adapting Very Fast Decision Tree)算法，除了保留VFDT算法在速度和精度方面的優(yōu)點外，增加了對數(shù)據(jù)產生過程中變化趨勢的檢測和響應，使得算法更好地適應對高速時變流數(shù)據(jù)的分類。

2.數(shù)據(jù)流聚類算法。流數(shù)據(jù)本身所具有的特征使得傳統(tǒng)的聚類算法不可能直接應用于(甚至不能應用于)流數(shù)據(jù)聚類， 數(shù)據(jù)流聚類算法就是通過單遍掃描數(shù)據(jù)流，持續(xù)地將數(shù)據(jù)流數(shù)據(jù)對象（數(shù)據(jù)點、元組等）分組成多個類或簇，在同一個簇中的數(shù)據(jù)對象之間具有較高的相似度，而不同簇間的數(shù)據(jù)對象的相似度很小。近年來，學者們提出的應用于大規(guī)模數(shù)據(jù)集的一趟聚類算法，如Squeezer算法和BIRCH算法，也可以應用于某些數(shù)據(jù)流問題，也有學者提出了針對流數(shù)據(jù)的聚類算法，典型的有STREAM算法和CluStream算法。

3.數(shù)據(jù)流頻繁模式挖掘算法。數(shù)據(jù)流頻繁模式挖掘就是單遍掃描數(shù)據(jù)流，來連續(xù)地發(fā)現(xiàn)其中的頻繁項集。頻繁項集是滿足最小支持度的項集(Itemset）。對于數(shù)據(jù)流上的頻繁項集挖掘的研究方法大多數(shù)都采用ε-算法和基于FP-tree模型的有效算法FP-stream。FP-stream算法采用傾斜時間窗口技術來維護頻繁模式以解決時間敏感問題，研究了在數(shù)據(jù)流中構造、維護和更新 FP-stream 結構的有效算法，提出了計算和維護所有頻率模式并動態(tài)更新它們。建立一個框架來挖掘帶近似支持度的時間敏感模式，為每個模式在多時間粒度上增量維護一個傾斜時間窗口，在這種框架下可以構建和回答感興趣的查詢。

四、結語

由于數(shù)據(jù)流具有獨特的性質，對其進行挖掘是一個挑戰(zhàn)性的問題，當前的有關算法的研究有很多是在傳統(tǒng)的增量式挖掘技術基礎之上發(fā)展而來的，探索數(shù)據(jù)流挖掘技術與傳統(tǒng)的靜態(tài)數(shù)據(jù)挖掘技術之間的本質區(qū)別，提出更有效、新穎、快速挖掘算法是當前研究面臨的重要問題。

參考文獻:

[1]Gibbons P B，Matias Y:New sampling based summary statistic for improving approximate query answers[A].Proc of the ACM SIGMOD Int’l Confon Management of Data [C].Seattle:ACMPress，1998.331～342

[2]金澈清 錢衛(wèi)寧 周傲英:流數(shù)據(jù)分析與管理綜述.軟件學報，2004，15(8):1172～1181

[3]Domingos.P，Hulten.G.Mining high-speed data streams[C].Proc of ACM SIGKDD Int Conf Knowledge Discovery in Databases(KDD'00)，2000.71～80

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文