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

李敏等

摘要：近幾年來，流數(shù)據(jù)成為主流的數(shù)據(jù)形式之一。如網(wǎng)絡(luò)入侵監(jiān)測(cè)數(shù)據(jù)，股票數(shù)據(jù)等都是不斷變化的流數(shù)據(jù)。聚類作為數(shù)據(jù)挖掘領(lǐng)域的主要技術(shù)手段之一，因此流數(shù)據(jù)的聚類也受到了眾多學(xué)者的廣泛關(guān)注。而流數(shù)據(jù)不同于靜態(tài)數(shù)據(jù)的特性給流數(shù)據(jù)的聚類帶來了挑戰(zhàn)。本文總結(jié)了傳統(tǒng)數(shù)據(jù)的聚類算法和流數(shù)據(jù)聚類挖掘的研究方法，并提出了對(duì)未來將群智能應(yīng)用于流數(shù)據(jù)聚類算法的展望。

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

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：2095-2163（2014）01-0013-04

0引言

隨著無線傳感網(wǎng)絡(luò)以及有關(guān)領(lǐng)域的相應(yīng)發(fā)展，流數(shù)據(jù)日益成為主要的數(shù)據(jù)形式之一。例如無線傳感器中的監(jiān)測(cè)數(shù)據(jù)，網(wǎng)絡(luò)入侵監(jiān)測(cè)數(shù)據(jù)，以及金融產(chǎn)業(yè)中不斷變化的股票數(shù)據(jù)等，即屬于此類。這些數(shù)據(jù)都具有與傳統(tǒng)靜態(tài)數(shù)據(jù)不同的特性，諸如實(shí)時(shí)、有序、快速變化等。而對(duì)于目前較為有限的存儲(chǔ)空間，數(shù)據(jù)流卻又無法長(zhǎng)期保存在計(jì)算機(jī)中，因此如何在線實(shí)時(shí)有效地處理這些數(shù)據(jù)，從中挖掘提取有用的知識(shí)，即成為數(shù)據(jù)挖掘領(lǐng)域的熱點(diǎn)問題之一。

數(shù)據(jù)挖掘，亦稱作知識(shí)發(fā)現(xiàn)，是指從大量的數(shù)據(jù)中挖掘得到人們感興趣的知識(shí)的具體發(fā)現(xiàn)過程。現(xiàn)如今，人們可以通過多種渠道獲取信息數(shù)據(jù)，隨著數(shù)據(jù)量的大幅增長(zhǎng)，如何從這些數(shù)據(jù)中找到有價(jià)值的信息，就成為數(shù)據(jù)挖掘的首要任務(wù)。數(shù)據(jù)挖掘的分析方法主要有以下幾種：

（1）關(guān)聯(lián)分析。兩個(gè)或多個(gè)數(shù)據(jù)變量之間存在著某種相關(guān)性，這就是關(guān)聯(lián)。通常情況下，數(shù)據(jù)庫中龐大數(shù)據(jù)的關(guān)聯(lián)性很難發(fā)現(xiàn)，而且關(guān)聯(lián)分析又具有一定的不確定性，因此產(chǎn)生的規(guī)則必須帶有可信度。

（2）分類分析。分類是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)重要技術(shù)手段。一般分為訓(xùn)練學(xué)習(xí)過程和測(cè)試過程。例如，決策樹、神經(jīng)網(wǎng)絡(luò)、k近鄰算法、貝葉斯算法等都是常見的分類技術(shù)。

（3）聚類分析。作為數(shù)據(jù)挖掘、模式識(shí)別等工程和技術(shù)領(lǐng)域的研究熱點(diǎn)之一，聚類分析表現(xiàn)了高度優(yōu)良的性能和效果。聚類就是將一個(gè)整體的數(shù)據(jù)集劃分成若干個(gè)簇，使得不同簇之間的相似性盡可能地小，而同一個(gè)簇中的相似性又盡可能地大。

綜上所述，可知聚類技術(shù)是數(shù)據(jù)挖掘領(lǐng)域的重要技術(shù)方法之一，而數(shù)據(jù)流高速動(dòng)態(tài)變化和一次掃描等特性卻給數(shù)據(jù)流聚類帶來了巨大的挑戰(zhàn)。如何能夠僅利用一次掃描就達(dá)到最好的聚類效果，以及如何生成任意形狀的聚類，則是近些年來研究者們深度探討的重點(diǎn)課題之一。

1傳統(tǒng)的數(shù)據(jù)聚類算法

傳統(tǒng)靜態(tài)的數(shù)據(jù)聚類算法對(duì)于后期數(shù)據(jù)流聚類算法的進(jìn)一步研究具有相當(dāng)重要的現(xiàn)實(shí)意義，很多數(shù)據(jù)流聚類算法都是一些常見的經(jīng)典聚類算法的變形。聚類算法一般可以分為三類，分別是基于劃分的方法、基于層次的方法、基于密度的方法。在此，對(duì)這三類方法進(jìn)行分別的探討和解析，具體如下。

1.1傳統(tǒng)的聚類方法

（1）基于劃分的方法

（2）基于層次的聚類方法

基于層次的方法通常分為自頂向下和自底向上兩種情況。在這些方法中，比較常用的就是Birch算法[1]。Birch算法中引入了CF聚類特征和CF tree聚類特征樹這兩個(gè)概念。具體過程為：首先全面掃描數(shù)據(jù)庫，建立一個(gè)初始的聚類特征樹；從根節(jié)點(diǎn)向下，計(jì)算與要插入的數(shù)據(jù)點(diǎn)間的距離，找尋最短距離，直至找到與該數(shù)據(jù)點(diǎn)最近的葉節(jié)點(diǎn)；如果吸收后大于閾值T，刪除或分裂葉節(jié)點(diǎn)。

Birch算法適用于大數(shù)據(jù)集的聚類處理，具有較低的算法空間復(fù)雜度和時(shí)間復(fù)雜度，聚類效果良好。但是，birch算法多是利用半徑來計(jì)算聚類的范圍，因此對(duì)于非球狀的聚類，就不會(huì)達(dá)到理想的效果。

（3）基于密度的聚類方法

基于密度的聚類方法是將具有相似的密度點(diǎn)的數(shù)據(jù)聚合在一起，可以根據(jù)不同的密度變化將聚類拓展到任意的地方，這就彌補(bǔ)了基于距離聚類只能產(chǎn)生球狀實(shí)現(xiàn)效果的缺陷。但是這類算法的復(fù)雜度一般卻比較高。

1.2基于群智能的聚類方法

群智能就是昆蟲或者飛鳥等群體表現(xiàn)出來的群體智能，例如螞蟻覓食，筑巢等過程中所表現(xiàn)出來的智能。近年來，眾多學(xué)者將群智能應(yīng)用于數(shù)據(jù)聚類中，取得了良好的聚類效果。群智能優(yōu)化算法主要有蟻群優(yōu)化算法（ACO）、粒子群優(yōu)化算法（PSO）、人工魚群優(yōu)化算法等。

2003年，Merwe等人[2]最先提出了PSO與K-means算法結(jié)合的混合聚類算法。該算法利用K-means方法得到某組聚類的中心，并在粒子群初始化時(shí)將聚類中心賦值給某個(gè)粒子，其余粒子則隨機(jī)初始化，之后運(yùn)用基本PSO聚類算法完成聚類。

Azzag等人提出了一種基于螞蟻覓食原理的聚類算法[3]。算法中，數(shù)據(jù)點(diǎn)可看作是具有不同屬性的螞蟻，而聚類中心就是螞蟻所要尋找的“食物”， 由此數(shù)據(jù)聚類過程即成為螞蟻尋找食物源的過程。此外，文獻(xiàn)[4]繼續(xù)提出通過螞蟻?zhàn)跃坌袨椤⑦_(dá)到聚類的蟻群聚類算法。該算法中，螞蟻能夠通過自我聚集行為構(gòu)建一個(gè)樹狀結(jié)構(gòu)， 即螞蟻樹（AntTree）。螞蟻不僅代表數(shù)據(jù)，而且也代表該螞蟻樹的節(jié)點(diǎn)，初始狀態(tài)時(shí)將螞蟻置于一個(gè)固定點(diǎn)上， 該點(diǎn)相當(dāng)于樹根。接著螞蟻在樹上已經(jīng)固定的螞蟻身上移動(dòng)， 尋找適合自己的位置。

將群智能應(yīng)用于聚類挖掘中，能夠獲得明顯優(yōu)于傳統(tǒng)聚類算法的實(shí)驗(yàn)結(jié)果，也不會(huì)象傳統(tǒng)聚類算法（如K-means算法）一樣那么容易產(chǎn)生局部最優(yōu)解，只是算法的收斂時(shí)間較長(zhǎng)。

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

由于數(shù)據(jù)流是隨時(shí)間不斷變化的，每單位時(shí)間段都有大量的數(shù)據(jù)到達(dá)，這就使得數(shù)據(jù)流中的數(shù)據(jù)將無法長(zhǎng)期存儲(chǔ)，此時(shí)若采用傳統(tǒng)的數(shù)據(jù)挖掘聚類算法就無法得到很好的聚類效果。基于此，可知數(shù)據(jù)流聚類挖掘與傳統(tǒng)的靜態(tài)數(shù)據(jù)聚類即有很大的不同，具體分析如下：

首先，簇個(gè)數(shù)無法假定。由于數(shù)據(jù)流的不斷變化，自然簇的個(gè)數(shù)也會(huì)相應(yīng)地隨之變化，因此無法預(yù)知簇的實(shí)際個(gè)數(shù)。

其次，聚類成任意形狀的簇。在很多數(shù)據(jù)集，如網(wǎng)絡(luò)入侵檢測(cè)數(shù)據(jù)集中，聚類的分布情況通常是不均勻、且無規(guī)則的，因此能夠發(fā)掘任意形狀的聚類對(duì)于數(shù)據(jù)流聚類的應(yīng)用則是至關(guān)重要的。

最后，處理噪聲數(shù)據(jù)的能力。在眾多數(shù)據(jù)流應(yīng)用場(chǎng)景中，總會(huì)受到一些意外因素，如傳感器網(wǎng)絡(luò)中電池供電不足的影響等，這些均是數(shù)據(jù)流中產(chǎn)生的一些隨機(jī)的噪聲數(shù)據(jù)，如何能夠分辨并處理這些噪聲數(shù)據(jù)也是數(shù)據(jù)流聚類中的一大難題。

2.1數(shù)據(jù)流模型

流數(shù)據(jù)可以看作隨時(shí)間不斷變化的數(shù)據(jù)集合[5]。流數(shù)據(jù)集合為{X1，X2，X3，…，XN}，其中Xi包含兩個(gè)數(shù)據(jù)項(xiàng)，一個(gè)是數(shù)據(jù)ai，另一個(gè)則是數(shù)據(jù)讀入的時(shí)間點(diǎn)（時(shí)間戳）ti，即Xi=。而流數(shù)據(jù)將隨著時(shí)間不斷地發(fā)生變化，這就不可避免會(huì)有噪聲數(shù)據(jù)出現(xiàn)于其中，可將其稱為異常數(shù)據(jù)和孤立點(diǎn)數(shù)據(jù)。這些數(shù)據(jù)與研究中正常的數(shù)據(jù)行為模式并不一樣，因而如何識(shí)別孤立點(diǎn)噪聲數(shù)據(jù)也是數(shù)據(jù)流挖掘領(lǐng)域亟需解決的重點(diǎn)問題之一。

2.2窗口模型

在數(shù)據(jù)流聚類分析方法中，通常都基于時(shí)間窗口來進(jìn)行。窗口模型一般可分為三種：界標(biāo)窗口模型，滑動(dòng)窗口模型和衰減窗口模型。其中，界標(biāo)窗口模型則包括直方圖方法、抽樣方法、小波方法、哈希方法等。下面對(duì)這三種模型作以分別探討。

在界標(biāo)窗口模型中，其中之一的直方圖技術(shù)就是將一個(gè)大的數(shù)據(jù)集分割成若干個(gè)小數(shù)據(jù)集。該技術(shù)能夠直觀地反映大數(shù)據(jù)集的輪廓梗概，因此在商業(yè)數(shù)據(jù)庫中得到了廣泛應(yīng)用。另外，對(duì)于抽樣方法來說，顧名思義，就是從大的整體數(shù)據(jù)集中抽取樣本來代表整個(gè)數(shù)據(jù)集，并在樣本查詢中獲得結(jié)果。而小波分析方法則與傅里葉變換相似，小波分析是將數(shù)據(jù)輸入的模擬量，變換成一系列的小波參數(shù)，而大部分能量?jī)H僅包含于少數(shù)幾個(gè)小波參數(shù)中，因此選擇利用少量的小波參數(shù)就能夠還原出原始的信號(hào)。

分類之二的滑動(dòng)窗口模型提出了一個(gè)時(shí)間窗口的概念。設(shè)有數(shù)據(jù)流DS=（a1，a2，a3，…，an），其中的ax是數(shù)據(jù)項(xiàng)，Xi是數(shù)據(jù)流中的數(shù)據(jù)樣本點(diǎn)，Xt則是進(jìn)入滑動(dòng)窗口的時(shí)間點(diǎn)。W為窗口大小，tn是任意的時(shí)間點(diǎn)。只有時(shí)間窗口{tn-w+1，…，tn}內(nèi)的數(shù)據(jù)才得以處理，而窗口外的數(shù)據(jù)則予以忽略。可用圖1表示滑動(dòng)窗口模型，具體如圖1所示。

2.3在線-離線聚類方法

Clustream算法完全能夠適應(yīng)數(shù)據(jù)流快速到達(dá)，有序無限以及單遍掃描的特點(diǎn)，并且還能夠挖掘出數(shù)據(jù)流的潛在演化特征。但是由于算法所采用的相似度標(biāo)準(zhǔn)是距離，這也就造成了該算法只能夠產(chǎn)生球形的聚類結(jié)果。而且當(dāng)數(shù)據(jù)流中存在噪聲數(shù)據(jù)時(shí)，算法將會(huì)表現(xiàn)出不穩(wěn)定性，而因?yàn)樵肼晹?shù)據(jù)無法被現(xiàn)有的微簇所接受，噪聲數(shù)據(jù)就會(huì)創(chuàng)建新的微簇，進(jìn)一步地，隨著噪聲數(shù)據(jù)的增加，微簇?cái)?shù)量也隨之增多。與此同時(shí)，算法又將限制微簇?cái)?shù)量，由此一些微簇就必須要進(jìn)行相應(yīng)的合并或者刪除，這就不可避免地降低了算法聚類結(jié)果的準(zhǔn)確度。

而后，針對(duì)Clustream算法的這些不足，學(xué)者們又相繼提出了多種解決辦法。2004年，Aggarwal等人提出了HPStream （ High-dimensional Projected Stream Clustering method） 算法框架[7]。HPStream做出的主要改進(jìn)有兩方面：一是算法中使用投影聚類的方法來處理高維數(shù)據(jù)流的聚類問題；二是使用一個(gè)衰減簇的概念來代替Clustream中提出的微簇，以保存歷史數(shù)據(jù)，從而利用衰減因子來實(shí)現(xiàn)不斷衰減歷史數(shù)據(jù)對(duì)整體聚類影響的不斷衰減。

在已有研究的基礎(chǔ)上，曹峰等人又提出了一種基于密度的進(jìn)化數(shù)據(jù)流聚類算法DenStream算法[8]，同樣這也是一種在線-離線兩階段處理方法。該算法主要提出三個(gè)概念：核心微簇，潛在核心微簇和離群微簇。算法實(shí)現(xiàn)可描述為：當(dāng)接收到一個(gè)新的數(shù)據(jù)點(diǎn)時(shí)，算法首先判斷這一數(shù)據(jù)是否可以被潛在核心微簇（p微簇）接收，如果不可以，再嘗試將其合并到距離最近的離群微簇（o微簇）當(dāng)中。如果合并后的離群微簇半徑大于閾值，則將此離群微簇轉(zhuǎn)化為潛在核心微簇。離線部分主要采用DBSCAN算法的變形來實(shí)現(xiàn)聚類。算法微簇維護(hù)的流程圖如圖2所示。

3未來發(fā)展趨勢(shì)

FlockStream算法是將Denstream算法與一種多代理群智能Flocking模型相結(jié)合而加以設(shè)計(jì)并最終實(shí)現(xiàn)的。該算法采用分散的、自下而上的自我組織戰(zhàn)略對(duì)相似的數(shù)據(jù)點(diǎn)進(jìn)行聚類分組，數(shù)據(jù)點(diǎn)與仿生模型中的boid相關(guān)聯(lián)并應(yīng)用啟發(fā)式策略進(jìn)行聚類，在聚類效果上占有很大的優(yōu)勢(shì)[11]。該算法將仿生模型與數(shù)據(jù)流聚類算法相結(jié)合。獲得了比較好的聚類效果。

通過以上分析可以看到，近幾年來數(shù)據(jù)流聚類算法得到了許多學(xué)者的關(guān)注。同時(shí)，群智能算法具有魯棒性和自組織等優(yōu)點(diǎn)，并且能夠在沒有建立全局模型的情況下，對(duì)大量的數(shù)據(jù)搜索亦能取得良好的效果，群智能算法確實(shí)有著其它優(yōu)化算法無可比擬的優(yōu)勢(shì)。進(jìn)一步地，將群智能算法與傳統(tǒng)的聚類算法相結(jié)合，也已獲取了較好的聚類效果。因此在未來的研究中，可以將群智能優(yōu)化算法應(yīng)用到流數(shù)據(jù)聚類算法中，旨在實(shí)現(xiàn)聚類效果的高效性和穩(wěn)定性。

參考文獻(xiàn)：

[1]ZHANG T， RAMAKRISHNAN R， LLVNY M. BIRCH：An effieient data clustering method for very large databases[C]//Proc.1996ACM-SIGMOD Int.Conf. Magement of data（SIGMOD，96），103-114.

[2]MERWE D W van der ENGELBRECHTA P. Data clustering using particle swarm optimization[C] //Proc of IEEE Congress on Evolutionary Computation， 2003： 215-220.

[3]楊欣斌， 孫京誥， 黃道.基于蟻群聚類算法的離群挖掘方法[J].計(jì)算機(jī)工程與應(yīng)用， 2003，（9）： 12-13+37.

[4]AZZAG H， MONMARCHE N， SLIMANCE M， et al. AntTree： a new model for clustering with artificial ants[C]//IEEE Congress on Evolutionary Computation， Canberra， Australia， 2003： 8-12.

[5]ENZINGER H M R， RAGHAVAN P， RAJAGOPALAN S . Computing on data streams. SRC Technical Note 1998-011. Digital systems research center： Palo Al t o， California， 1998.

[6]AGGARWAL C C， HAN J， WANG J， et al. A framework for clustering evolving data streams. FREYTAG J C， LOCKE M P C， ABITEBOUL S， et al， eds[C]// Proc. of the Intl Conf. on Very Large Data Bases. Berlin： Morgan Kaufmann Publishers， 2003： 81-92.

[7]AGGARWAL C C，HAN J，WANG J，et a1.A framework for projected clustering of high dimensional data streams[C]//Proceedings of the 30th Informational Conference on Very Large Data Bases，2004：852-863.

[8]CAO F， ESTER M， QIAN W， et al. Density-based clustering over evolving data stream with noise[C]//Proceedings of the sixth SIAM international conference on data mining （SIAM06）， Bethesda， 2006：326–337.

[9]CHEN Y X，TU L.Density-based clustering for real-time stream data [C]//Proceedings of the 13th ACM SIGKDD international conference on Knowledge Discovery and Data Mining.California：ACM，2007：133-142.

[10]黃德才，吳天虹.基于密度的混合屬性數(shù)據(jù)流聚類算法[J]. 控制與決策，2010，（3）：416-421.

[11]FORESTIERO A， PIZZUTI C， SPEZZANO G. A single pass algorithm for clustering evolving data streams based on swarm intelligence[J]. Data Min Knowl Disc，2013，26：1–26.