基于數據流的數據挖掘研究

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

[關鍵詞] 數據流 數據流挖掘 模型 算法

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

一、數據流以及數據流挖掘

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

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

二、數據流挖掘的模型

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

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

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

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

典型的數據流挖掘模型如圖所示。

三、數據流挖掘算法

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

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

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

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

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

四、結語

由于數據流具有獨特的性質，對其進行挖掘是一個挑戰(zhàn)性的問題，當前的有關算法的研究有很多是在傳統(tǒng)的增量式挖掘技術基礎之上發(fā)展而來的，探索數據流挖掘技術與傳統(tǒng)的靜態(tài)數據挖掘技術之間的本質區(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)寧 周傲英:流數據分析與管理綜述.軟件學報，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格式閱讀原文