幾種數(shù)據(jù)流聚類(lèi)算法分析

朱 強(qiáng)，周 曉

（合肥師范學(xué)院，安徽 合肥 230601）

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

1 數(shù)據(jù)流定義與窗口模型

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

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

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

1.3 衰減窗口模型(Damped Window Model):該種窗口模型是指被用來(lái)挖掘的數(shù)據(jù)流為從數(shù)據(jù)流開(kāi)始到當(dāng)前到達(dá)的所有數(shù)據(jù)項(xiàng)的集合，但個(gè)數(shù)據(jù)項(xiàng)被賦予不同的權(quán)重，較早到達(dá)的數(shù)據(jù)項(xiàng)具有較小的權(quán)重，較晚到達(dá)的數(shù)據(jù)項(xiàng)具有較大的權(quán)重.各數(shù)據(jù)項(xiàng)的權(quán)重根據(jù)某種衰減函數(shù)隨著時(shí)間不斷地衰減.

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

該框架下，算法需要在內(nèi)存中維護(hù)一個(gè)概要數(shù)據(jù)結(jié)構(gòu)[2]，概要數(shù)據(jù)結(jié)構(gòu)是一種利用較少的內(nèi)存空間從已往數(shù)據(jù)流中提取數(shù)據(jù)特征或信息而形成的數(shù)據(jù)結(jié)構(gòu).當(dāng)新的數(shù)據(jù)項(xiàng)到達(dá)時(shí)，數(shù)據(jù)流挖掘算法通過(guò)計(jì)算來(lái)維護(hù)和更新內(nèi)存中的概要數(shù)據(jù)結(jié)構(gòu).當(dāng)用戶(hù)發(fā)出挖掘請(qǐng)求時(shí)，算法從概要數(shù)據(jù)結(jié)構(gòu)中讀取信息并處理，再把處理的結(jié)果反饋給用戶(hù).不同的概要數(shù)據(jù)結(jié)構(gòu)對(duì)挖掘結(jié)果的影響很大，因此，設(shè)計(jì)出新的概要數(shù)據(jù)結(jié)構(gòu)也是數(shù)據(jù)流挖掘的一個(gè)重要研究?jī)?nèi)容.

2 幾種代表性的數(shù)據(jù)流聚類(lèi)算法

數(shù)據(jù)流聚類(lèi)分析是數(shù)據(jù)流挖掘的一個(gè)重要研究方向，而數(shù)據(jù)流本身的特點(diǎn)也決定了對(duì)于一般數(shù)據(jù)的聚類(lèi)分析算法不適合數(shù)據(jù)流聚類(lèi).數(shù)據(jù)流聚類(lèi)算法有以下幾個(gè)基本的要求[3]：

2.1 由于數(shù)據(jù)流是源源不斷地持續(xù)到達(dá)，因此對(duì)于數(shù)據(jù)流聚類(lèi)算法的速度要很快，甚至實(shí)時(shí)響應(yīng)，而傳統(tǒng)的聚類(lèi)數(shù)據(jù)是靜態(tài)的，對(duì)時(shí)間復(fù)雜度的要求并不苛刻.

2.2 由于數(shù)據(jù)流持續(xù)無(wú)限、規(guī)模龐大，因此整個(gè)流數(shù)據(jù)集不可能在存儲(chǔ)在內(nèi)存或硬盤(pán)上，須對(duì)數(shù)據(jù)流進(jìn)行必要的概化舍棄處理；同樣，對(duì)數(shù)據(jù)流的分析也不像傳統(tǒng)的聚類(lèi)那樣可以多次掃描數(shù)據(jù)，而只能是單遍掃描.

2.3 數(shù)據(jù)流數(shù)據(jù)往往都是高維的、海量的，因此其算法的復(fù)雜性比傳統(tǒng)算法更高.目前影響比較大的數(shù)據(jù)流聚類(lèi)算法有以下幾種：

2.3.1 CluStream數(shù)據(jù)流聚類(lèi)算法[4]

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

2.3.2 HPStream數(shù)據(jù)流聚類(lèi)算法[5]

Aggarwal等人后來(lái)為了解決高維數(shù)據(jù)流聚類(lèi)問(wèn)題又提出了一種基于投影的數(shù)據(jù)流聚類(lèi)算法HPStream，該算法是將投影的技術(shù)應(yīng)用到數(shù)據(jù)流聚類(lèi)中，在相關(guān)維形成的子空間內(nèi)算法解決了高維數(shù)據(jù)的稀疏性問(wèn)題，提供了聚類(lèi)的質(zhì)量.HPStream算法使用衰減結(jié)構(gòu)，利用可調(diào)衰減因子較好地將當(dāng)前數(shù)據(jù)和歷史數(shù)據(jù)結(jié)合起來(lái)，在數(shù)據(jù)流的進(jìn)化中逐步刪除過(guò)期的歷史數(shù)據(jù)，體現(xiàn)了當(dāng)前數(shù)據(jù)的重要.但是HPStream算法和CluStream算法一樣，對(duì)球形的聚類(lèi)結(jié)果很好，但對(duì)其它形狀聚類(lèi)并不能產(chǎn)生很好的聚類(lèi)結(jié)果.

2.3.3 DenStream數(shù)據(jù)流聚類(lèi)算法[6]

DenStream數(shù)據(jù)流聚類(lèi)算法是由Cao等人提出的一種基于密度的聚類(lèi)算法，它改進(jìn)了DenStream算法，采用CluStream算法中提出的兩階段處理框架，引入了核心微聚類(lèi)簇、孤立點(diǎn)微聚類(lèi)簇和潛在微聚類(lèi)簇等概念以獲取較準(zhǔn)確的聚類(lèi)結(jié)果,可挖掘在有噪聲環(huán)境下衰減窗口內(nèi)數(shù)據(jù)流中任意形狀的簇.但因?yàn)椴捎萌忠恢碌慕^對(duì)密度作參數(shù),所以聚類(lèi)結(jié)果對(duì)參數(shù)值比較敏感，同時(shí)，由于需要統(tǒng)計(jì)輸入數(shù)據(jù)帶有時(shí)間特性的特征向量及大量密度計(jì)算，所以其時(shí)間復(fù)雜度也比較高.SDStream算法[7]是在DenStream算法的基礎(chǔ)上，利用滑動(dòng)窗口來(lái)處理數(shù)據(jù)流，雖然減少了時(shí)間復(fù)雜度，但是卻只能獲取到最近數(shù)據(jù)流中任意形狀的聚類(lèi)簇.

2.3.4 D-Stream數(shù)據(jù)流聚類(lèi)算法[8]

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

3 結(jié)論

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

〔1〕萬(wàn)仁霞.數(shù)據(jù)流聚類(lèi)算法研究[D].上海：東華大學(xué)，2009.

〔2〕曹鋒.數(shù)據(jù)流聚類(lèi)分析算法[D].上海：復(fù)旦大學(xué)，2006.

〔3〕趙煥平，曹蕾.基于密度的數(shù)據(jù)流聚類(lèi)算法[J].南陽(yáng)理工學(xué)院學(xué)報(bào)，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.