王冬秀 張海鵬 李 輝

（1.廣西工學(xué)院，廣西 柳州 545006；2.柳州市公安局，廣西 柳州 545000）

數(shù)據(jù)流聚類算法分析

王冬秀1張海鵬2李 輝1

（1.廣西工學(xué)院，廣西 柳州 545006；2.柳州市公安局，廣西 柳州 545000）

數(shù)據(jù)流作為一種新的數(shù)據(jù)對象，近年來成為了數(shù)據(jù)挖掘領(lǐng)域的研究熱點(diǎn)問題，具有很大的應(yīng)用前景。文章首先比較了數(shù)據(jù)流聚類分析和傳統(tǒng)的聚類分析的一些不同點(diǎn)，然后對目前幾個典型的數(shù)據(jù)流研究成果進(jìn)行了分析，最后對數(shù)據(jù)流的進(jìn)一步研究方向進(jìn)行了展望。

聚類分析；數(shù)據(jù)流；數(shù)據(jù)流聚類

（一）引言

近年來，數(shù)據(jù)流作為一種重要的數(shù)據(jù)對象，受到越來越多學(xué)者的關(guān)注，針對數(shù)據(jù)流的挖掘成為了研究領(lǐng)域的熱點(diǎn)問題。數(shù)據(jù)流是一種數(shù)據(jù)規(guī)模大、變化速度快、時間有序、潛在無限的數(shù)據(jù)。它最大的特點(diǎn)是以一種動態(tài)、流的形式出現(xiàn)，而不像傳統(tǒng)的數(shù)據(jù)被靜態(tài)、固定地存儲在介質(zhì)中，可隨機(jī)多次訪問。那么對于這樣一種特殊且日益主流的數(shù)據(jù)形式，我們該如何從中快速、高效地挖掘出有價(jià)值的信息，成為了眾多應(yīng)用領(lǐng)域的客觀需求，也吸引了國內(nèi)外眾多專家學(xué)者的注意。聚類分析作為數(shù)據(jù)挖掘領(lǐng)域的一種重要的研究方法，受到了廣泛地關(guān)注。本文首先介紹傳統(tǒng)的聚類方法和數(shù)據(jù)流聚類方法的一些特點(diǎn)，然后對最近幾年典型的數(shù)據(jù)流研究成果進(jìn)行了分析和評價(jià)。

（二）傳統(tǒng)的聚類分析

聚類是將數(shù)據(jù)對象分成類或簇的過程，使同一簇中的數(shù)據(jù)對象之間具有很高的相似度，不同簇中的對象高度相異。聚類分析形式定義為：在數(shù)據(jù)空間S中，數(shù)據(jù)集X由許多數(shù)據(jù)點(diǎn)或數(shù)據(jù)對象組成，數(shù)據(jù)點(diǎn) Xi(Xi1, Xi2,…Xin)∈ S，

Xi的每個屬性Xij可以是枚舉型、數(shù)值型等任意類型。數(shù)據(jù)集X相當(dāng)于一個 M × n 的矩陣。假設(shè)X中有M個對象Xi(i=1,2…M)。聚類的目的是把數(shù)據(jù)集X劃分為k個分割Cx(x =1,2…K)，在劃分的過程中，會產(chǎn)生噪聲Cy，Cy不屬于任何一個分割。數(shù)據(jù)集X就是所有這些分割和噪聲Cy的并集，并且分割之間不存在交集，即這些分割xC就是聚類。

聚類分析技術(shù)作為數(shù)據(jù)挖掘領(lǐng)域一個非?；钴S的分支，在很多領(lǐng)域都得到了廣泛地應(yīng)用。在聚類分析中，目前已出現(xiàn)了許多適用于各種數(shù)據(jù)類型和不同應(yīng)用的算法，這些算法概括起來可分為如下幾類：基于劃分的方法（如k－均值、k－中心點(diǎn)算法）、基于層次的方法（如 BIRCH、CURE算法）、基于密度的方法(如DBSCAN、OPTICS 算法)、基于網(wǎng)格的方法（如STING、Wave Cluster算法）、基于模型的方法（如EM 、COBWEB算法）等。這些算法的處理結(jié)果通常從以下幾個標(biāo)準(zhǔn)進(jìn)行評價(jià)：可伸縮性、處理不同屬性數(shù)據(jù)的能力、數(shù)據(jù)記錄的輸入不敏感性、發(fā)現(xiàn)任意形狀的聚類、處理高維數(shù)據(jù)的能力、可解釋性和可應(yīng)用性等。

（三）數(shù)據(jù)流聚類算法的特點(diǎn)

數(shù)據(jù)流數(shù)據(jù)規(guī)模大、變化速度快、到達(dá)速度不確定等特點(diǎn)決定了很多傳統(tǒng)的優(yōu)秀聚類算法不能直接應(yīng)用于數(shù)據(jù)流，必須對其進(jìn)行“量身”改造，相比于傳統(tǒng)的聚類算法，數(shù)據(jù)流聚類算法應(yīng)具備以下特點(diǎn)：

（1）單遍掃描：由于數(shù)據(jù)流具有數(shù)據(jù)量大、流速快，因此每個數(shù)據(jù)元素只能被檢測一次，即只能進(jìn)行單遍掃描；

（2）存儲空間有限性：由于數(shù)據(jù)流的數(shù)據(jù)是潛在無限的，因此不可能存儲如此海量的數(shù)據(jù)，待對其進(jìn)行清洗后再進(jìn)行處理，只能在盡量不影響聚類結(jié)果的前提下，存儲數(shù)據(jù)流的摘要信息；

（3）實(shí)時性：由于數(shù)據(jù)流的速度非常快，因此對數(shù)據(jù)流的處理要適應(yīng)“流”的快速變化，每條記錄的處理時間應(yīng)該越少越好。

數(shù)據(jù)流的以上特點(diǎn)決定了我們不可能存儲海量的數(shù)據(jù)，待對其進(jìn)行清洗和整理后再進(jìn)行處理，因此其研究核心是設(shè)計(jì)高效的聚類算法，在一個遠(yuǎn)小于數(shù)據(jù)規(guī)模的內(nèi)存空間里不斷更新一個代表數(shù)據(jù)集的結(jié)構(gòu)—概要數(shù)據(jù)結(jié)構(gòu)，使得在用戶有任何請求時，都能夠根據(jù)這個結(jié)構(gòu)迅速獲得近似查詢結(jié)果。一個通用的數(shù)據(jù)流處理模型如圖1所示：

圖1 數(shù)據(jù)流處理通用模型

數(shù)據(jù)流的這些特點(diǎn)，使得許多傳統(tǒng)的優(yōu)秀的聚類算法不再有效，因此，許多傳統(tǒng)的聚類方法必須針對數(shù)據(jù)流進(jìn)行“量身改造”才能獲得有意義的結(jié)果，數(shù)據(jù)流聚類算法就在這樣的背景下應(yīng)運(yùn)而生了。

（四）數(shù)據(jù)流聚類算法

目前，由于數(shù)據(jù)流的大量涌現(xiàn)，國內(nèi)外眾多專家學(xué)者紛紛投入了數(shù)據(jù)流的研究中，尤其是數(shù)據(jù)流在現(xiàn)實(shí)生活中的廣泛應(yīng)用，如網(wǎng)絡(luò)監(jiān)控、傳感器網(wǎng)絡(luò)、行星遙感、股票交易分析、Web點(diǎn)擊流、氣象與環(huán)境監(jiān)控等方面的廣泛應(yīng)用，使得數(shù)據(jù)流的研究成為了一個前沿的熱點(diǎn)問題，本文對現(xiàn)有的比較典型的數(shù)據(jù)流聚類算法進(jìn)行介紹，并分析了這些算法的優(yōu)缺點(diǎn)。

1.CLIQUE算法

R.Agarwal 等人在文獻(xiàn)中提出的CLIQUE算法，該算法采用自下而上的方式搜索數(shù)據(jù)集的所有子空間，由于CLIQUE把每一維劃分成網(wǎng)格狀的結(jié)構(gòu)，并且根據(jù)每個網(wǎng)格單元所包含點(diǎn)的數(shù)目來確定該網(wǎng)格單元是否稠密，因此該算法是基于密度和基于網(wǎng)格方法的一種集成。該算法吸收了 Apriori算法的思想，在算法的執(zhí)行過程中，不斷地搜索滿足指定閾值的稠密網(wǎng)格單元，同一子空間內(nèi)相連的稠密網(wǎng)格單元作為聚類輸出。對于一個稠密的區(qū)域，該區(qū)域在所有低維子空間的投影都將是稠密的，因此輸出的聚類簇可能會存在大量重疊。

2.CluStream算法

為了跟蹤進(jìn)化數(shù)據(jù)流聚類，2003年Aggarwal等提出了一種基于劃分的 CluStream算法，該算法分為在線和離線雙層結(jié)構(gòu)處理數(shù)據(jù)流，在線部分執(zhí)行 K - means算法產(chǎn)生微簇，離線部分執(zhí)行 K - means算法以微簇累積快照產(chǎn)生宏簇。至今很多算法還沿用這種雙層結(jié)構(gòu)。

3.SHStream算法

2006年，在文獻(xiàn)中，周曉云等人提出一種基于Hoeffding界的高維數(shù)據(jù)流子空間聚類發(fā)現(xiàn)及維護(hù)算法—SHStream，該算法將數(shù)據(jù)流分段（分段長度由Hoeffding界確定），在數(shù)據(jù)分段上進(jìn)行子空間聚類，由于該算法采用 Apriori方法得到候選密集單元，在操作過程中，會產(chǎn)生大量的候選單元，占用大量的存儲資源，這無疑降低了算法的效率。

4.CELL TREE算法

為了有效地跟蹤高維數(shù)據(jù)流聚類，2007年Nam Hun Park等人又提出了 CELL TREE算法，該算法吸收了子空間聚類算法的思想，是一個基于網(wǎng)格和密度算法的結(jié)合，改進(jìn)了hybrid-partition算法，在內(nèi)存中維護(hù)一個聚類模型，它把一個密集網(wǎng)格單元劃分為一定數(shù)量的相等互斥的網(wǎng)格單元。該算法能夠有效地處理在線的高維數(shù)據(jù)流，具有以下優(yōu)點(diǎn)：（1）不需要事先知道聚類的數(shù)量；（2）能夠處理任意形狀的聚類；（3）能夠較好地處理高維數(shù)據(jù)流。但該算法也存在一定的問題：（1）需要大量的存儲空間來保存網(wǎng)格單元的密度信息，使算法的空間伸縮性受到限制；（2）在處理過程中，內(nèi)存網(wǎng)格單元的更新需要大量的計(jì)算時間，使算法的時間效率受到了限制；（3）該算法在劃分的過程中，會產(chǎn)生大量空網(wǎng)格單元，隨著數(shù)據(jù)維數(shù)的增加，內(nèi)存的使用量迅速增長。

5.SWClustering算法

為了跟蹤進(jìn)化數(shù)據(jù)流聚類，2008年Aoying zhou等人提出了SWClustering算法，該算法結(jié)合指數(shù)直方圖技術(shù)，提出了一種新的數(shù)據(jù)結(jié)構(gòu) EHCF(the Exponential Histogram of Cluster Features)，EHCF為跟蹤進(jìn)化數(shù)據(jù)流提供了一個靈活的框架，能夠有效地跟蹤聚類而不受其它聚類的干擾。

盡管以上這些算法的設(shè)計(jì)都適應(yīng)了數(shù)據(jù)流的特點(diǎn)，并取得了較好的效果，但面向數(shù)據(jù)流的聚類分析方法仍然存在很多問題，如：（1）算法在運(yùn)行過程中會產(chǎn)生大量的侯選子空間，聚類效果相對較差；（2）在操作過程中，會產(chǎn)生大量空的網(wǎng)格單元，算法的時間和空間效率均受到一定的限制等。因此對數(shù)據(jù)流聚類算法的深入研究具有十分重要的意義。

（五）結(jié)論

本文回顧了最近幾年來國內(nèi)外數(shù)據(jù)流聚類的研究成果，并對該領(lǐng)域的幾個典型的算法進(jìn)行了分析和討論。近年來，數(shù)據(jù)流聚類正在蓬勃發(fā)展，數(shù)據(jù)流聚類是一個非?；钴S且具有挑戰(zhàn)性的研究課題。隨著經(jīng)濟(jì)的快速發(fā)展，實(shí)際生產(chǎn)和生活中，實(shí)時的數(shù)據(jù)流將大量產(chǎn)生，基于實(shí)時的數(shù)據(jù)流聚類技術(shù)具有重要的理論和實(shí)際意義。隨著研究的不斷深入，實(shí)時的數(shù)據(jù)流聚類技術(shù)必將在航天航空、行星遙感、工業(yè)控制、交通監(jiān)控等領(lǐng)域扮演越來越重要的角色。

[1]B.Babcock,S.Babu,M.Datar,R.Motwani,J.Widom.Models and issues in data stream systems.In Proceedings of the Twenty-first ACM SIGACT SIGMOD-SIGART Symposium on Principles of Database Systems,June 3-5,Madison,Wisconsin,USA,pp.1-16.ACM,2002.

[2] J.W.Han,M.Kamber著.數(shù)據(jù)挖掘:概念與技術(shù)[Ml.范明,孟小峰,譯.北京:機(jī)械工業(yè)出版社,2006.

[3] 紀(jì)希禹,韓秋明,李微,李華鋒,等.數(shù)據(jù)挖掘技術(shù)應(yīng)用實(shí)例[Ml.機(jī)械工業(yè)出版社,2009:53.

[4] M.Garofalakis, J.Gehrke, R.Rastogi. Querying and mining data streams: you only get one look.in: The Tutorial Notes of the 28th International Conference on Very Large Databases, Hong Kong,China,August2002.

[5] 金澈清,錢衛(wèi)寧,周傲英,等.流數(shù)據(jù)分析與管理綜述[Jl.軟件學(xué)報(bào),2004,15(8):1172-1181.

TP311

A

1008-1151(2011)05-0029-02

2011-02-21

王冬秀（1981－），女，廣西桂林人，廣西工學(xué)院財(cái)政經(jīng)濟(jì)系實(shí)驗(yàn)師，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘、數(shù)據(jù)流聚類；張海鵬（1974－），男，廣東惠州人，柳州市公安局工程師，研究方向?yàn)閿?shù)據(jù)挖掘；李輝（1981－），男，廣西桂林人，廣西工學(xué)院財(cái)政經(jīng)濟(jì)系講師，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘，模式識別。