數據流聚類算法分析

王冬秀 張海鵬 李 輝

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

數據流聚類算法分析

王冬秀1張海鵬2李 輝1

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

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

聚類分析；數據流；數據流聚類

（一）引言

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

（二）傳統的聚類分析

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

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

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

（三）數據流聚類算法的特點

數據流數據規模大、變化速度快、到達速度不確定等特點決定了很多傳統的優秀聚類算法不能直接應用于數據流，必須對其進行“量身”改造，相比于傳統的聚類算法，數據流聚類算法應具備以下特點：

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

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

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

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

圖1 數據流處理通用模型

數據流的這些特點，使得許多傳統的優秀的聚類算法不再有效，因此，許多傳統的聚類方法必須針對數據流進行“量身改造”才能獲得有意義的結果，數據流聚類算法就在這樣的背景下應運而生了。

（四）數據流聚類算法

目前，由于數據流的大量涌現，國內外眾多專家學者紛紛投入了數據流的研究中，尤其是數據流在現實生活中的廣泛應用，如網絡監控、傳感器網絡、行星遙感、股票交易分析、Web點擊流、氣象與環境監控等方面的廣泛應用，使得數據流的研究成為了一個前沿的熱點問題，本文對現有的比較典型的數據流聚類算法進行介紹，并分析了這些算法的優缺點。

1.CLIQUE算法

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

2.CluStream算法

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

3.SHStream算法

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

4.CELL TREE算法

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

5.SWClustering算法

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

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

（五）結論

本文回顧了最近幾年來國內外數據流聚類的研究成果，并對該領域的幾個典型的算法進行了分析和討論。近年來，數據流聚類正在蓬勃發展，數據流聚類是一個非常活躍且具有挑戰性的研究課題。隨著經濟的快速發展，實際生產和生活中，實時的數據流將大量產生，基于實時的數據流聚類技術具有重要的理論和實際意義。隨著研究的不斷深入，實時的數據流聚類技術必將在航天航空、行星遙感、工業控制、交通監控等領域扮演越來越重要的角色。

[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著.數據挖掘:概念與技術[Ml.范明,孟小峰,譯.北京:機械工業出版社,2006.

[3] 紀希禹,韓秋明,李微,李華鋒,等.數據挖掘技術應用實例[Ml.機械工業出版社,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] 金澈清,錢衛寧,周傲英,等.流數據分析與管理綜述[Jl.軟件學報,2004,15(8):1172-1181.

TP311

A

1008-1151(2011)05-0029-02

2011-02-21

王冬秀（1981－），女，廣西桂林人，廣西工學院財政經濟系實驗師，碩士研究生，研究方向為數據挖掘、數據流聚類；張海鵬（1974－），男，廣東惠州人，柳州市公安局工程師，研究方向為數據挖掘；李輝（1981－），男，廣西桂林人，廣西工學院財政經濟系講師，碩士研究生，研究方向為數據挖掘，模式識別。