數據流聚類算法研究

王高洋 李英梅

摘 要：隨著傳感器數據、互聯網數據、金融數據（股票價格等）、在線拍賣以及事務日志（網站訪問日志、電話記錄日志）等的不斷產生，數據流成為了主要的數據形式。流挖掘是數據庫領域的研究熱點，有很大的應用前景。本文首先簡單介紹了數據流與聚類分析的概念，闡述了數據流中的聚類分析及其要求，詳細說明了主要傳統聚類方法的演變及各自代表性流數據聚類算法，并對其進行總結。在本文的最后，對流數據挖掘的前景做出展望。

關鍵詞：聚類；數據流；數據流聚類；數據挖掘；數據流挖掘

中圖分類號：TP311 文獻標識號：A 文章編號：2095-2163（2014）05-

The Study of Data Stream Clustering Algorithms

WANG Gaoyang， LI Yingmei

（College of Computer Science and Information Engineering， Harbin Normal University， Harbin 150025， China）

Abstract： With the producing of numerous data from financial tickers， network traffic monitoring， web and transaction log analysis， and sensor networks， the stream data has become a kind of main data type. Streaming mining is a hot issue in the career of database and it has a good future. In this article， firstly gives a brief introduction to data stream， clustering analysis and other concepts related to clustering data streaming. Secondly the paper elaborately states the main traditional clustering methods and their typical clustering algorithms of data stream.After that， the paper also makes a summary to them. Finally， the paper makes the prospect of data mining.

Keywords： Clustering； Data Stream； Clustering Data Streaming； Data Mining； Streaming Mining

1 數據流與其挖掘算法的特點

1.1 數據流

最近幾年出現了大量新類型的應用，這些應用的典型特點是數據以序列的形式予以發布，且每時每刻都在不斷地產生，諸如傳感器數據、互聯網數據、金融數據 （股票價格等）、在線拍賣以及事務日志等。這些數據不同于傳統的數據集，而是呈現為海量的、時序的、快速變化的和潛在無限的，該種數據形態即可稱為數據流。

1.2 數據流挖掘算法的特點

基于數據流的特征及特性，將傳統的方法用于數據流挖掘已然不再具有可行性。而經過對數據流挖掘算法的研究分析，可將數據流挖掘算法的實現過程特點歸納總結如下：

（1） 單次且線性掃描。在滿足聚類要求的情況下，要盡可能少地掃描數據集，最好只是一遍掃描；

（2）空間和時間復雜度低。因為流算法的可用空間較為有限，且流算法還是在線算法，就需要算法能夠快速處理任意數據項，以此而保證處理速度不小于數據流速度；

（3） 能夠確保計算結果在理論上有較好的近似度；

（4） 能夠適應不斷變化的流速和數據；

（5） 能夠有效地處理噪音和空值；

（6） 用戶在線提出的任何時間段內挖掘請求均能得到迅捷響應；

（7） 算法在任意時刻都可提供當前數據處理結果。

在以上各條性質要求中，第（1）～（3）條是一個流數據挖掘算法的必要屬性。早期的流數據挖掘算法也都是以這三項為目標設計的。

2 聚類分析及其在流數據挖掘中的應用

2.1 聚類分析

聚類分析，數據挖掘中的一個重要課題。聚類，是將一個給定數據集合中的相似對象劃分成一或者多個組（也稱作簇）的過程。劃分后，同一簇中元素彼此相似，但相異于其它簇中元素。作為獨立工具，聚類分析在眾多領域已然獲得了廣泛應用。

2.2 數據流挖掘中的聚類分析

聚類分析經歷了很多年的研究探討，針對聚類靜態數據集已經提供了許多方法，但是由于上述數據流自身特性卻造成了諸多限制，而不能將傳統聚類方法直接應用于聚類流數據。本次研究所需要的則是適用于流數據模型且滿足其特點的高效聚類方法。

3 傳統聚類方法的演變及其經典算法

3.1 擴展劃分方法

劃分方法就是將含有n個數據元素的數據集組織為k個劃分（k≤n） ，其中的每一獨立劃分均表示一個簇[1]。迄至目前，已經提出的劃分方法主要有k-平均算法（k-Means）及k-中心點算法（k-Medoids）等。

Guha 等人在文獻[1-2]中將 k-平均算法進行了擴展，并將其用于處理流數據。這一擴展算法僅需要單遍掃描，而且需要的存儲空間相對也較少，算法的時間、空間復雜度則可表示為 O（nk）和 O（nε ），其中 n 是數據元素個數，k是簇中心點個數，且ε<1； 相應地，Babcock等人又利用一種叫做指數直方圖（EH， exponential histogram）的數據結構改進了Guha等人提出的算法。算法的思想并未改變，只是用EH結構進行了簇的合并。而在文獻[3]中，Charikar 等人卻利用分而治之（Divide and Conquer）的策略提高了 k-平均算法性能。該算法是將數據進行分塊處理，其最終結果是通過各小數據塊所計算的信息匯總得到的。同樣地，也是基于 k-平均算法，OChallagham 等人更在文獻[4]中提出了 Stream 算法。Stream 算法使用分級聚類技術，并且引入 LSEARCH 算法來改進 k-Means 算法，從而提高了性能，而且得到的結果簇也具有更高的質量。

0Callaghan于2002年成功研發LOCALSEARCH算法的基礎上，更進一步提出了基于分治思想的流數據聚類算法，即Stream算法。在該算法中，對數據流采用一個迭代過程進行k-means聚類，并且將其移植至數據流環境中。具體過程為：首先，Stream算法確定聚類的數目K，再利用批處理方式及分級聚類方法。對最初輸入的n個數據實現聚類，由此得到0（K）個一級的帶權質心，重復上述過程n/O（K）次，從而得到n個一級的帶權質心，接下來，再對得到的n個一級的帶權質心進行聚類，繼續得到0（K）個二級的帶權質心。與其類似，當得到了n個i級的帶權質心，也將對其進行聚類，繼而得到0（K）個i+1級帶權質心。重復此過程直至獲得最終的O（K）個質心，并且任意i+1級帶權質心的權值即是與其對應的i級質心權值之和。

由上可知，Stream算法是單層結構，因而表現了一定的局限性，現對其分析如下：

第一，聚類數目K需預先設定，且要對不斷到達數據的先后順序也較為敏感。

第二，由于算法聚類時，只有聚類中心點的信息被保留下來，因此容易造成有用信息的丟失。

第三，算法只是對當前處理的數據流的實際描述，而并非適用于聚類進化數據流的任何階段。

第四，對于復雜形狀的流數據，該算法也不適用。

3.2 擴展層次方法

層次方法，就是按層次分解數據元素的集合，并且得到一棵聚類構成的樹。BIRCH算法，是該方法的經典模型，此外也還有ROCK、Chameleon及URE等算法問世。在文獻[5]中，Aggarwal 等人就對 BIRCH 算法進行了擴展，從而提出 了CluStream算法。這是一個流數據聚類框架，聚類過程分成了兩部分：聯機微聚類（microclustering）和脫機宏聚類（macroclustering）。此后的許多流數據聚類算法也都隨之而采用了這種兩個階段的處理框架。

在文獻[6]中，Aggarwal等人對CluStream算法實施了進一步的改造，并將其應用于高維的數據流，HPStream算法也隨之而提出。為了更好地支持高維數據流的聚類分析，投影技術和衰減簇結構在算法中相繼獲得了引用。現在，HPStream和CluStream即已成為兩個具有廣闊應用空間的流數據聚類算法。

在文獻[7]中，Udommanetanakit 等人又對HPStream進行了補充，并以其為基礎創新性地提出了E-Stream 算法。

下面即對Clustream算法框架及HPStream算法框架展開詳盡的論述與分析。

3.2.1 Clustream算法框架

作為流數據聚類分析的一個框架。Clustream主要解決了STREAM 算法存在的兩個問題：首先，CLustream是增量式的聚類算法，能在每個數據項來到時給出即時回應；并且，Clustream使用的時間框架是塔式的，能夠給出不同的時間粒度聚類結果。

Aggarwal等人于2003年提出的進化數據流聚類Clustream算法包含兩個部分，也就是在線聚類和離線聚類兩部分。該算法首次提出將數據流看作一個隨時間不斷變化的動態的數據集，而不再只是將其看作一個數據整體進行聚類，并且Clustream算法適用于數據流聚類的進化分析，同時也具有良好的可擴展性，當數據流隨時間變化較大時，即能產生質量高于其他算法的聚類。Clustream算法不僅能夠給出動態數據流整體的聚類結果，還能夠給出流數據任意時間段內的聚類結果，這一特性正是進行數據流進化分析不可或缺的必要結果。另外，算法由在線和離線兩部分構成，其中的在線部分使用微簇來存儲數據流的概要信息，并且引用金字塔時間窗口技術，同時遵照最近及最新的數據優先原則，使用不同的時間粒度實現了數據流的存儲和處理。而離線部分，則將在線部分所保存的微簇信息，按照用戶要求進行更精細的處理分析，從而得到了用戶感興趣的聚類結果。

雖然，Clustream算法通過時間框架的傾斜使用，CluStream保留了數據流變化的歷史信息，當數據流發生劇烈變化時仍能夠產生較高質量聚類結果。但是該算法卻并未考慮歷史數據衰減問題，也就是未能突出近期數據的重要性。另外，在將CluStream算法運用于聚類高維數據流時，具體表現也依然不佳。

3.2.2 HPStream算法框架

為了解決CluStream 存在的問題，Aggarwal 等人即于2004年提出了 HPStream 算法框架。該算法基于衰減簇結構，并隨著時間推進衰減因子呈指數方式對歷史數據進行衰減，當有過多聚類數目時，則刪除最先加入聚類的數據；同時在每個衰減簇結構中，亦需維護要進行投影的維度列表，而且在微簇級別上進行了降維處理，從而在聚類過程中提升了微簇的純度。

尤其是，文獻[6]中通過對網絡入侵檢測和森林覆蓋類型兩種流數據集進行了對比仿真實驗。結果表明 HPStream 在存儲性能和處理速度上都要優于 CluStream。由此可以得出結論：HPStream 算法現已成為數據流聚類的主流算法之一。

3.3 擴展基于密度的方法

大多數聚類算法的距離度量都是基于對象之間的，此類聚類算法僅能發現球狀簇，但在聚類任意形狀簇時，卻會存在一定困難。基于密度的方法即重點解決該類問題。具體來說，是將簇看成數據空間中利用低密度區域分隔而成的高密度數據區域[1]。DBSCAN（Density-Based Spatial Clustering of Applications with Noise）算法就是業界使用頻率最高的一種基于密度的聚類方法。此外基于密度的算法還有DENCLUE、PTICS等。

在文獻[6]中，Cao F 等人對 DBSCAN 算法進行了擴展，提出了基于密度的面向數據流的DenStream聚類算法。其中采用的是 CluStream 算法所提出的兩階段處理框架，并且引入了孤立點簇結構和潛在簇結構。實際上，當聚類請求到來時，DenStream 算法仍會采用 DBSCAN 算法以得到最終的聚類結果。

擴展層次和劃分的方法，諸如 STREAM、HPStream 和 CluStream等算法存在的主要問題是：這些算法僅在聚類分析球狀的數據流時表現良好，而當處理任意形狀的數據流時，其效果表現即發生了走低的趨向，具體原因就在于這些算法采用的是距離度量。

針對這一狀況，DenStream 算法則對基于密度的傳統數據集聚類算法DBSCAN進行了擴展，旨在解決數據流形狀任意時現有算法存在的聚類問題。與此同時，該算法又強調了孤立點的檢測問題，即將孤立點和正常的數據元素進行了有效區分。

實現過程中，DenStream 算法使用了 CluStream 的兩階段處理框架，也就是同樣地將聚類分析過程分為聯機、脫機兩部分。

具體地，聯機部分中，算法維護兩種微簇結構：潛在微簇（p微簇）及孤立點微簇（o微簇）。這兩種微簇在結構上的區別僅在于各自的約束條件，即孤立點簇是指密度低于某閾值的簇，而潛在微簇則是密度超過此一閾值的簇。當有新數據點到達時，算法步驟為：

（1） 首先，嘗試將其合并到最鄰近的 p微簇中；

（2） 若嘗試失敗，則試圖將其合并到其最鄰近的 o微簇中。若合并成功，則將該o微簇的密度與閾值進行比較，而當該值大于閾值，該 o微簇將轉換成 p微簇；

（3） 若仍無法找到其最鄰近的o微簇，即新建一個 o微簇容納此數據點。

對于脫機部分而言，當用戶的聚類要求到來時，DenStream 算法先忽略密度不足的兩類微簇，再使用DBSCAN 算法，對當前的 p-micro-cluster 和 o-micro-cluster 進行處理，得到聚類結果，并最終返回。

3.4 擴展基于網格的方法

基于網格的方法是將數據元素空間量化成為有限數目的單元，從而形成一個網格結構。所有聚類操作都在該網格結構上進行與實現。基于網格的算法常常與基于密度的算法結合起來使用，具體示例即如CLIQUE算法。這類算法的一個顯著優點就在于算法運行速度非常快。

Chen 等人在文獻[8]中提出了 D-Stream ，通過使用密度網格，即基于密度與網格，從而得到高質量的聚類結果。概括地說，該算法就是基于密度與網格的算法。而且，與 DenStream 算法相同的是，該算法也旨在解決任意形狀數據流的聚類問題，既強調了孤立點檢測，又依據密度而判斷聚類；但與其不同的卻是，該算法也還是基于網格方法的算法，因而采用了密度網格結構。

推演開來，D-Stream 算法也分為聯機、脫機兩部分：聯機部分可將其接收到的每個元素映射到某個網格中，而脫機部分則計算網格的密度，并對這些網格進行基于密度的聚類。

具體地，聯機部分不斷地讀入新數據元素，并將多維數據元素映射到其對應的多維空間中的離散的密度網格中，同時又將密度網格的特征向量進行即時更新。而脫機部分，則每隔一個時間空隙 （gap time）就要動態地調整當前簇，第一個時間隙后形成的可稱為初始簇，此后，算法將周期性地移除零星簇，并調整已生成的簇。使用網格結構，將不再需要對大量原始數據進行保留，而只要對網格進行操作即可。

綜上所述，由于聯機部分僅是將數據元素映射到其對應的網格中，再也無需計算權值或距離，D-Stream將比不曾采用網格的算法實現起來更為高效，且更具良好的可擴展性，即算法速度不會隨數據量的增大而變慢。然而，D-Stream 算法也存在相應的問題，就是處理高維數據流時，其需要的網格數量將可能偏大。

仍需提及的是，在文獻[9]中，Bhatnagar等人又提出了ExCC（Exclusive and Complete Clustering of Streams）算法，該數據流聚類算法也是基于網格與密度的。該算法即專門針對簇聚類的完備性 （completeness） 與排他性 （exclusiveness），進而提出完備性聚類概念，亟需深入探討和重點研究。

4 結束語

圖1給出了聚類算法由面向傳統數據向面向流數據的發展和演變過程。需要說明的是，該圖并不完全，一些正在演進中的算法及思想并沒有體現于其中。

圖1 數據流聚類算法發展與演化示意圖

Fig.1 The development and evolution of data stream clustering algorithms

雖然現已提出了大量優秀算法及處理框架，數據流的聚類分析仍是一個充滿挑戰的科研領域。可以預測，在未來的幾年中，必將有更多、更為高效的算法相繼出現，藉此解決相關應用領域知識與數據流挖掘技術的結合問題，從而在相當程度上推進相關領域如天文、物理等實際應用的迅猛發展，以期收獲研究成果上的重大突破。

參考文獻：

[1] GUHA S， MISHRA N， MOTWANI R，et al. Clustering data streams[C]//Proceedings of the Annual Symposium on Foundations of Computer Science， IEEE， 2000.

[2] GUHA S， MEYERSON A， MISHRA N， et al. Clustering data streams： theory and practice[J]. IEEE Transactions on Knowledge and Data Engineering， 2003，15（3）：515-528.

[3] CHARIKAR M， O'CALLAGHAN L， PANIGRAHY R. Better streaming algorithms for clustering problems[C]//Proc. of 35th ACM Symposium on Theory of Computing， 2003.

[4] L.OCALLAGHAN L，MISHRA N，MEYERSON A，et al. Streaming-data algorithms for high-quality clustering[C]//Proc.of ICDE Conf.of IEEE International Conference on Data Engineering， March 2002：685-694.

[5] AGGARWAL C， HAN J， WWANG J， et al. A framework for clustering evolving data streams[C]//Proceedings of the 29th VLDB Conference， Berlin， Germany， 2003.

[6] AGGARWAL C， HAN J， WANG J， et al. A framework for projected clustering of high dimensional data Streams[C]//Proceedings of the 30th VLDB Conference， Toronto， Canada， 2004.

[7] Udommanetanakit K， Rakthanmanon T and Waiyamai K. E-Stream： Evolution-Based Technique for Stream Clustering[M]. Springer-Verlag Berlin Heidelberg， 2007： 605-615.

[8] CHEN Y， TU L. Density-based clustering for real-time Stream data[C]//KDD07， San Jose， California， USA，August 12–15，2007：133-142.

[9] Bhatnagar V， and Kaur S. Exclusive and Complete Clustering of Streams[M]. Springer-Verlag Berlin Heidelberg， 2007：629–638