基于數(shù)據(jù)流的數(shù)據(jù)挖掘研究

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

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

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

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

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

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

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

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

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

2.界標(biāo)模型:處理數(shù)據(jù)的范圍從某一個(gè)已知的初始時(shí)間點(diǎn)到當(dāng)前時(shí)間點(diǎn)為止。

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

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

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

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

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

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

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

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

四、結(jié)語

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

參考文獻(xiàn):

[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ù)分析與管理綜述.軟件學(xué)報(bào)，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

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文