幾種數據流聚類算法分析

朱 強，周 曉

（合肥師范學院，安徽 合肥 230601）

隨著傳感器技術和網絡通信技術的不斷發展和廣泛應用，一種被稱為數據流的新的數據時時刻刻地不斷產生了，例如在網上商城等web應用、網絡監控、實時監控、衛星遙感系統、股票交易系統、物聯網、氣象與環境監控等動態環境當中產生了大量的實時數據.這類數據與傳統的存儲在物理存儲介質上的靜態數據不同，它是動態的，像水流一樣的形式存在，是一種實時持續到達、數據規模不能預知且宏大、到達速度快、數據到達無序、突變的數據[1].因此處理數據流只能進行單遍掃描算法，一經處理的數據不能或沒有必要再次提取或者提取的代價較高；傳統的數據挖掘算法應用于數據流上效果不同理想，如何高效地從數據流中獲取有價值的信息是目前數據挖掘領域的重要研究內容.聚類分析是數據挖掘的一個重要研究方法，基于數據流的聚類分析也引起了越來越多人的關注，他們提出了多種基于數據流的聚類分析算法，較好地解決了傳統聚類分析的不足.本文首先介紹了數據流和基于數據流的聚類分析算法應該滿足的特點，然后討論了幾種數據流聚類算法，并對其進行分析和評價.

1 數據流定義與窗口模型

數據流是一種實時持續到達、數據規模不能預知且宏大、到達速度快、數據到達無序、突變的數據序列X1,X2,…,Xn…,序列中每一個數據Xi假設是d維，xi=xi1,xi2,…,xid,每一項數據到達的時間假設是T1,T2,…Tn,…,則數據流可可以看作是帶有時間標記的一系列數據項：<X1,T1>,<X2,T2>,….基于數據流的數據挖掘往往是在某一個時間段內進行，也就是在時間窗口內進行，比較常用的時間窗口模型有三種[2]：

1.1 界標窗口模型(Landmark Window Model):該種窗口模型是指被用來挖掘的數據流為從數據流開始到當前到達的所有數據項的集合，即{X1,X2,…,Xn},其中是Xn當前時刻的數據項，且窗口大小隨著數據的到達不斷增加.

1.2 滑動窗口模型(Sliding Window Model):該種窗口模型是指被用來挖掘的數據流從當前時刻開始，到最近到達的N個數據項的集合，N即是滑動窗口的大小，數據項集合為{Xi-N+1…Xi},其中Xi是當前時刻的數據項.這種窗口模型的窗口位置在時間軸上隨著數據流不斷滑動.

1.3 衰減窗口模型(Damped Window Model):該種窗口模型是指被用來挖掘的數據流為從數據流開始到當前到達的所有數據項的集合，但個數據項被賦予不同的權重，較早到達的數據項具有較小的權重，較晚到達的數據項具有較大的權重.各數據項的權重根據某種衰減函數隨著時間不斷地衰減.

用戶根據需求選擇其中一種或幾種窗口模型應用于數據流的挖掘，不論采用哪種窗口模型，一般數據流挖掘都采用相同的挖掘框架，如下圖1所示.

該框架下，算法需要在內存中維護一個概要數據結構[2]，概要數據結構是一種利用較少的內存空間從已往數據流中提取數據特征或信息而形成的數據結構.當新的數據項到達時，數據流挖掘算法通過計算來維護和更新內存中的概要數據結構.當用戶發出挖掘請求時，算法從概要數據結構中讀取信息并處理，再把處理的結果反饋給用戶.不同的概要數據結構對挖掘結果的影響很大，因此，設計出新的概要數據結構也是數據流挖掘的一個重要研究內容.

2 幾種代表性的數據流聚類算法

數據流聚類分析是數據流挖掘的一個重要研究方向，而數據流本身的特點也決定了對于一般數據的聚類分析算法不適合數據流聚類.數據流聚類算法有以下幾個基本的要求[3]：

2.1 由于數據流是源源不斷地持續到達，因此對于數據流聚類算法的速度要很快，甚至實時響應，而傳統的聚類數據是靜態的，對時間復雜度的要求并不苛刻.

2.2 由于數據流持續無限、規模龐大，因此整個流數據集不可能在存儲在內存或硬盤上，須對數據流進行必要的概化舍棄處理；同樣，對數據流的分析也不像傳統的聚類那樣可以多次掃描數據，而只能是單遍掃描.

2.3 數據流數據往往都是高維的、海量的，因此其算法的復雜性比傳統算法更高.目前影響比較大的數據流聚類算法有以下幾種：

2.3.1 CluStream數據流聚類算法[4]

數據流聚類算法CluStream是有C.Aggarwal等人提出的，它把不是把數據流看成一個整體，而是看成是一個隨時間變化的過程進行聚類分析，因此，算法優點是當數據流隨著時間變化較大時，它的聚類結果質量更高.而且，CluStream算法可以給出任意時間范圍內的聚類結果及進行數據流的進化分析.CluStream算法的聚類過程包含兩部分或兩階段：在線的微聚類和離線的宏聚類.在線部分用micro-cluster定時存儲數據流的摘要信息，以增量的方式對數據進行處理和更新，并在金字塔時間框架下分級保存摘要信息；離線部分是用micro-cluster在在線部分保存的中間結果再進行分析得到指定時間范圍內的聚類結果.CluSTream算法提出的這個兩階段處理框架被之后的許多數據流聚類算法所改進和采用.但是由于算法的micro-cluster采用類似于BRICH算法所用的特征值記錄它所產生的子聚類，因此算法對球形的聚類結果很好，但對其它形狀聚類并不能產生很好的聚類結果.

2.3.2 HPStream數據流聚類算法[5]

Aggarwal等人后來為了解決高維數據流聚類問題又提出了一種基于投影的數據流聚類算法HPStream，該算法是將投影的技術應用到數據流聚類中，在相關維形成的子空間內算法解決了高維數據的稀疏性問題，提供了聚類的質量.HPStream算法使用衰減結構，利用可調衰減因子較好地將當前數據和歷史數據結合起來，在數據流的進化中逐步刪除過期的歷史數據，體現了當前數據的重要.但是HPStream算法和CluStream算法一樣，對球形的聚類結果很好，但對其它形狀聚類并不能產生很好的聚類結果.

2.3.3 DenStream數據流聚類算法[6]

DenStream數據流聚類算法是由Cao等人提出的一種基于密度的聚類算法，它改進了DenStream算法，采用CluStream算法中提出的兩階段處理框架，引入了核心微聚類簇、孤立點微聚類簇和潛在微聚類簇等概念以獲取較準確的聚類結果,可挖掘在有噪聲環境下衰減窗口內數據流中任意形狀的簇.但因為采用全局一致的絕對密度作參數,所以聚類結果對參數值比較敏感，同時，由于需要統計輸入數據帶有時間特性的特征向量及大量密度計算，所以其時間復雜度也比較高.SDStream算法[7]是在DenStream算法的基礎上，利用滑動窗口來處理數據流，雖然減少了時間復雜度，但是卻只能獲取到最近數據流中任意形狀的聚類簇.

2.3.4 D-Stream數據流聚類算法[8]

D-Stream數據流聚類算法是一種典型的數據流網格聚類算法.網格聚類往往是將數據空間首先劃分為由一定數目的網格單元組成的網格結構，然后將數據流映射到網格結構中，形成網格密度的概念，相鄰的高密度網格的集合代表一個聚類，聚類操作在網格上進行.D-Stream算法在線部分將數據映射到一個網格，在離線部分計算網格的密度，從而形成基于密度的簇.D-Stream算法使用密度衰減技術來捕獲數據流的動態變化，通過實時地調整簇，以探索衰減因、數據密度和簇結構間的關系，合理地移除屬于離群的點的稀疏網格，提高系統的空間和時間效率.D-Stream算法能有效地對高速數據流進行聚類而不損失聚類質量，能發現任意形狀的簇，能準確地識別實時數據流的演化行為，但其聚類效果明顯會受到網格粒度的影響.

3 結論

基于數據流的聚類算法得到了眾多人員的研究，也產生了很多的聚類算法成果，但是在實時數據流聚類、高維數據流聚類以及提高聚類的質量和降低時間復雜度等方面還存在不足，數據流的模糊聚類還處于起步階段，這也是下一步努力的方向.

〔1〕萬仁霞.數據流聚類算法研究[D].上海：東華大學，2009.

〔2〕曹鋒.數據流聚類分析算法[D].上海：復旦大學，2006.

〔3〕趙煥平，曹蕾.基于密度的數據流聚類算法[J].南陽理工學院學報，2012,4（2）:73-75.

〔4〕C.Aggarwal,J.Han,et al.A framework for clustering evolvingdata streams[J].Proc.of VLDB,2003:81-87.

〔5〕C.Aggarwal,J.Han,et al.A framework for projected clustering of high dimensional data streams[J].Proc.of VLDB,2004:850-859.

〔6〕F.Cao,A.zhou,etc.Density -based clustering over an evolving data stream with noise [J].Proc.of the SIAM Conf.on Data Mining.2006.

〔7〕Ren J D,Ma R Q.Density-based data streams clustering over sliding windows.Proceedings of the 6th International Conference on FKD,2009:240-251.

〔8〕Chen Y X,Tu L.Density-based clusteing for real-time stream data.Proceeding of the 13th ACM SIGKDD,2007:130-140.