數(shù)據(jù)流聚類算法研究

王高洋 李英梅

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

關(guān)鍵詞：聚類；數(shù)據(jù)流；數(shù)據(jù)流聚類；數(shù)據(jù)挖掘；數(shù)據(jù)流挖掘

中圖分類號：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 數(shù)據(jù)流與其挖掘算法的特點

1.1 數(shù)據(jù)流

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

1.2 數(shù)據(jù)流挖掘算法的特點

基于數(shù)據(jù)流的特征及特性，將傳統(tǒng)的方法用于數(shù)據(jù)流挖掘已然不再具有可行性。而經(jīng)過對數(shù)據(jù)流挖掘算法的研究分析，可將數(shù)據(jù)流挖掘算法的實現(xiàn)過程特點歸納總結(jié)如下：

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

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

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

（4） 能夠適應(yīng)不斷變化的流速和數(shù)據(jù)；

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

（6） 用戶在線提出的任何時間段內(nèi)挖掘請求均能得到迅捷響應(yīng)；

（7） 算法在任意時刻都可提供當(dāng)前數(shù)據(jù)處理結(jié)果。

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

2 聚類分析及其在流數(shù)據(jù)挖掘中的應(yīng)用

2.1 聚類分析

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

2.2 數(shù)據(jù)流挖掘中的聚類分析

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

3 傳統(tǒng)聚類方法的演變及其經(jīng)典算法

3.1 擴展劃分方法

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

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

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

由上可知，Stream算法是單層結(jié)構(gòu)，因而表現(xiàn)了一定的局限性，現(xiàn)對其分析如下：

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

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

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

第四，對于復(fù)雜形狀的流數(shù)據(jù)，該算法也不適用。

3.2 擴展層次方法

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

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

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

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

3.2.1 Clustream算法框架

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

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

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

3.2.2 HPStream算法框架

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

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

3.3 擴展基于密度的方法

大多數(shù)聚類算法的距離度量都是基于對象之間的，此類聚類算法僅能發(fā)現(xiàn)球狀簇，但在聚類任意形狀簇時，卻會存在一定困難?；诿芏鹊姆椒粗攸c解決該類問題。具體來說，是將簇看成數(shù)據(jù)空間中利用低密度區(qū)域分隔而成的高密度數(shù)據(jù)區(qū)域[1]。DBSCAN（Density-Based Spatial Clustering of Applications with Noise）算法就是業(yè)界使用頻率最高的一種基于密度的聚類方法。此外基于密度的算法還有DENCLUE、PTICS等。

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

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

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

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

具體地，聯(lián)機部分中，算法維護兩種微簇結(jié)構(gòu)：潛在微簇（p微簇）及孤立點微簇（o微簇）。這兩種微簇在結(jié)構(gòu)上的區(qū)別僅在于各自的約束條件，即孤立點簇是指密度低于某閾值的簇，而潛在微簇則是密度超過此一閾值的簇。當(dāng)有新數(shù)據(jù)點到達時，算法步驟為：

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

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

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

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

3.4 擴展基于網(wǎng)格的方法

基于網(wǎng)格的方法是將數(shù)據(jù)元素空間量化成為有限數(shù)目的單元，從而形成一個網(wǎng)格結(jié)構(gòu)。所有聚類操作都在該網(wǎng)格結(jié)構(gòu)上進行與實現(xiàn)?；诰W(wǎng)格的算法常常與基于密度的算法結(jié)合起來使用，具體示例即如CLIQUE算法。這類算法的一個顯著優(yōu)點就在于算法運行速度非?？?。

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

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

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

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

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

4 結(jié)束語

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

圖1 數(shù)據(jù)流聚類算法發(fā)展與演化示意圖

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

雖然現(xiàn)已提出了大量優(yōu)秀算法及處理框架，數(shù)據(jù)流的聚類分析仍是一個充滿挑戰(zhàn)的科研領(lǐng)域?？梢灶A(yù)測，在未來的幾年中，必將有更多、更為高效的算法相繼出現(xiàn)，藉此解決相關(guān)應(yīng)用領(lǐng)域知識與數(shù)據(jù)流挖掘技術(shù)的結(jié)合問題，從而在相當(dāng)程度上推進相關(guān)領(lǐng)域如天文、物理等實際應(yīng)用的迅猛發(fā)展，以期收獲研究成果上的重大突破。

參考文獻：

[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