基于概率和代表點(diǎn)的數(shù)據(jù)流動(dòng)態(tài)聚類算法

畢安琪　董愛美,2　王士同

1(江南大學(xué)數(shù)字媒體學(xué)院　江蘇無(wú)錫　214122)2(齊魯工業(yè)大學(xué)信息學(xué)院　濟(jì)南　250353)(angela.sue.bi@gmail.com)

基于概率和代表點(diǎn)的數(shù)據(jù)流動(dòng)態(tài)聚類算法

畢安琪1董愛美1,2王士同1

1(江南大學(xué)數(shù)字媒體學(xué)院江蘇無(wú)錫214122)2(齊魯工業(yè)大學(xué)信息學(xué)院濟(jì)南250353)(angela.sue.bi@gmail.com)

摘要為了解決數(shù)據(jù)流動(dòng)態(tài)聚類問題，提出了一種概率化的基于代表點(diǎn)聚類算法.首先，基于概率框架給出了AP(affinity propagation)聚類算法和EEM(enhanced α-expansion move)聚類算法的聯(lián)合目標(biāo)函數(shù)，提出了概率化的基于代表點(diǎn)聚類算法;其次，根據(jù)樣本與其代表點(diǎn)之間的概率，提出了基于概率的漂移動(dòng)態(tài)α-expansion數(shù)據(jù)流聚類算法.該算法使得新數(shù)據(jù)的代表點(diǎn)盡可能貼近原始數(shù)據(jù)的代表點(diǎn)，從而提高聚類性能;另一方面，考慮到原始數(shù)據(jù)與新數(shù)據(jù)的相似性，該算法能夠處理2種漂移過程中的動(dòng)態(tài)聚類問題：1)新數(shù)據(jù)與原始數(shù)據(jù)分享部分?jǐn)?shù)據(jù)，其余數(shù)據(jù)與原始數(shù)據(jù)相似；2)沒有相同的數(shù)據(jù)，新數(shù)據(jù)與原始數(shù)據(jù)有相似關(guān)系.在人工合成數(shù)據(jù)集D31,Birch3以及真實(shí)數(shù)據(jù)集Forest Covertpye,KDD CUP99的實(shí)驗(yàn)結(jié)果均顯示出了所提之算法能夠處理數(shù)據(jù)流聚類問題，并保證聚類性能穩(wěn)定.

關(guān)鍵詞數(shù)據(jù)流;能量函數(shù);概率;優(yōu)化算法;動(dòng)態(tài)聚類

在機(jī)器學(xué)習(xí)領(lǐng)域，聚類算法受到了研究者們廣泛的重視和研究.作為一種無(wú)監(jiān)督學(xué)習(xí)方法，基于不同的聚類特征和理論，研究者們發(fā)展出了各具特色的不同聚類算法，例如基于類中心的聚類分析方法、基于譜理論的聚類分析方法以及基于密度的聚類分析方法等[1-8].隨著信息技術(shù)以及社交網(wǎng)絡(luò)的蓬勃發(fā)展，人們?cè)诂F(xiàn)實(shí)生活中經(jīng)常選擇一個(gè)已存在的實(shí)例作為數(shù)據(jù)簇的類中心(如一位領(lǐng)導(dǎo)或一個(gè)代表).AP(affinity propagation)聚類算法作為一種典型的基于實(shí)例點(diǎn)聚類的方法，于近年來受到廣泛的關(guān)注和使用.2007年，F(xiàn)rey等人[9]將這些實(shí)例類中心稱為代表點(diǎn)(exemplar)，并在文獻(xiàn)[9-10]中證明了此類基于代表點(diǎn)的聚類問題可以看作是Markov隨機(jī)場(chǎng)(Markov random field, MRF)的能量函數(shù)尋優(yōu)問題.因此，可以用MRF能量函數(shù)的優(yōu)化算法求解這類聚類問題，MRF的優(yōu)化算法主要有2種方法：1)基于信息傳遞的LBP(loopy belief propagation)算法[10]；2)基于Graph Cuts的優(yōu)化算法，例如α-expansion[11-12].眾所周知，經(jīng)典的AP聚類算法即是使用LBP算法優(yōu)化目標(biāo)函數(shù)進(jìn)行求解的.然而，2001年文獻(xiàn)[12]通過實(shí)驗(yàn)證明α-expansion優(yōu)化算法較之LBP算法在獲取最終優(yōu)化結(jié)果上更顯優(yōu)勢(shì).因此,2013年，Zheng等人[13]證明基于代表點(diǎn)的聚類算法的目標(biāo)函數(shù)可以用α-expansion優(yōu)化算法進(jìn)行求解，從而提出了一種新的基于代表點(diǎn)的聚類算法EEM(enhancedα-expansion move)，并通過實(shí)驗(yàn)證明了EEM算法具備更加高效的聚類性能.

近年來，針對(duì)數(shù)據(jù)流(data stream)的機(jī)器學(xué)習(xí)方法成為研究熱點(diǎn)，基于數(shù)據(jù)流的動(dòng)態(tài)聚類算法也是重點(diǎn)之一.數(shù)據(jù)流是指數(shù)據(jù)特征隨著時(shí)間的推移而發(fā)生變化的一種特殊數(shù)據(jù)，例如股票行情分析、網(wǎng)絡(luò)流量分析、網(wǎng)絡(luò)異常檢測(cè)、傳感器檢測(cè)是機(jī)器學(xué)習(xí)領(lǐng)域出現(xiàn)的一種新的數(shù)據(jù)模型.現(xiàn)階段針對(duì)數(shù)據(jù)流的研究主要集中在動(dòng)態(tài)聚類[13-21]、突變檢測(cè)[22-23]等方面，并且都取得了標(biāo)志性成果.鑒于數(shù)據(jù)流動(dòng)態(tài)聚類算法的良好應(yīng)用前景，本文將主要關(guān)注動(dòng)態(tài)聚類算法，值得指出的是，本文所研究的問題其前提是數(shù)據(jù)流數(shù)據(jù)特征不發(fā)生突變，同時(shí)新流入的數(shù)據(jù)應(yīng)該與原始數(shù)據(jù)保持一定的相似性，如圖1所示.而新數(shù)據(jù)與原始數(shù)據(jù)的相似性關(guān)系可以分為2種情況：1)部分新數(shù)據(jù)與原始數(shù)據(jù)完全相同，其余數(shù)據(jù)與原始數(shù)據(jù)相似；2)新數(shù)據(jù)與原始數(shù)據(jù)沒有相同的數(shù)據(jù)，僅保持相似關(guān)系.

Fig. 1　Data stream without sudden change.圖1　數(shù)據(jù)流數(shù)據(jù)

根據(jù)上述數(shù)據(jù)流數(shù)據(jù)的特征，經(jīng)研究可知目前的AP聚類方法及其改進(jìn)方法[9,11-12]尚不能解決此類動(dòng)態(tài)聚類問題.根據(jù)數(shù)據(jù)流數(shù)據(jù)特征隨時(shí)間變化這個(gè)特征，數(shù)據(jù)流動(dòng)態(tài)聚類算法需要能夠追蹤原本數(shù)據(jù)的聚類結(jié)果，并結(jié)合這類已知信息與新獲取數(shù)據(jù)提高當(dāng)前的聚類性能.因此，數(shù)據(jù)流動(dòng)態(tài)聚類算法應(yīng)該至少能夠解決2個(gè)問題：1)針對(duì)新數(shù)據(jù)的聚類性能必須不低于以往數(shù)據(jù)的聚類性能；2)在聚類過程中，由于聚類個(gè)數(shù)很難事先設(shè)定，因此數(shù)據(jù)流聚類算法必須能夠自動(dòng)識(shí)別類的個(gè)數(shù).

在靜態(tài)數(shù)據(jù)聚類算法的基礎(chǔ)上，數(shù)據(jù)流的動(dòng)態(tài)聚類算法近年來已經(jīng)取得了一些具有代表性的成果.Guha等人[14]擴(kuò)展了K-means聚類算法使之適用于數(shù)據(jù)流聚類，之后O’ Calloghan等人[15]提出了STREAM算法，采用分級(jí)聚類的技術(shù)提高了算法的聚類性能.同時(shí)，Aggarwal等人[16-17]提出了CluStream算法以及HPStream算法，提出了用微簇來保存聚類的概要數(shù)據(jù)，其擴(kuò)展了BIRCH算法中聚類特征的概念，這2種算法是現(xiàn)在數(shù)據(jù)流聚類算法中的經(jīng)典算法.Cao等人[18]提出了一種基于密度的聚類算法DenStream，同樣采用了CluStream中的在線和離線2階段的思想.然而，這類算法一般通過衰減因子來控制原始數(shù)據(jù)與新數(shù)據(jù)之間的相似性關(guān)系，當(dāng)原始數(shù)據(jù)與新數(shù)據(jù)分享部分?jǐn)?shù)據(jù)時(shí)，這類算法的聚類性能并不穩(wěn)定.

對(duì)于現(xiàn)有的AP算法而言，其在處理數(shù)據(jù)流聚類問題時(shí)，通常的做法是通過對(duì)樣本集的二次計(jì)算獲取針對(duì)當(dāng)前數(shù)據(jù)的聚類結(jié)果，使其不適用于動(dòng)態(tài)聚類的情況，并且不能有效檢測(cè)出數(shù)據(jù)流的變化.為解決這一問題，使得能量函數(shù)的優(yōu)化算法能夠適應(yīng)數(shù)據(jù)流的動(dòng)態(tài)聚類.本文在AP聚類算法和EEM聚類算法的基礎(chǔ)上，提出了一種新的基于概率的漂移動(dòng)態(tài)α-expansion聚類算法(probability drifting dynamicα-expansion clustering algorithm， PDDE).該算法基于MRF能量函數(shù)尋優(yōu)問題，首先基于概率論給出AP聚類算法和EEM聚類算法的聯(lián)合目標(biāo)函數(shù)，之后充分利用原樣本集與新數(shù)據(jù)的相似性，通過樣本的概率信息并借助原樣本數(shù)據(jù)的聚類結(jié)果，在使得新數(shù)據(jù)的代表點(diǎn)與原數(shù)據(jù)的代表點(diǎn)盡可能相似的目標(biāo)下，最終提高對(duì)新數(shù)據(jù)的聚類性能，解決數(shù)據(jù)流動(dòng)態(tài)聚類所面對(duì)的問題1.對(duì)于問題2，由于本文采用了基于代表點(diǎn)聚類算法作為基礎(chǔ)算法，而該類聚類算法本身即能夠完成自動(dòng)聚類而無(wú)需預(yù)先設(shè)定聚類個(gè)數(shù)，因此問題2被自然地解決了.另一方面，由于引入概率框架，當(dāng)原始數(shù)據(jù)與新數(shù)據(jù)分享部分?jǐn)?shù)據(jù)時(shí)，PDDE聚類算法仍然可以進(jìn)行數(shù)據(jù)流動(dòng)態(tài)聚類，即該聚類算法將原始數(shù)據(jù)與新數(shù)據(jù)的2種相似性關(guān)系統(tǒng)一.

1基于代表點(diǎn)聚類算法及相關(guān)擴(kuò)展

基于代表點(diǎn)的聚類算法由于已經(jīng)解決了數(shù)據(jù)流動(dòng)態(tài)聚類所面臨的第2個(gè)問題，使得它在解決這類特殊的聚類問題時(shí)擁有一定的優(yōu)勢(shì).在基于代表點(diǎn)的聚類算法中，具有代表性的研究成果之一就是文獻(xiàn)[9]證明了該類聚類算法目標(biāo)函數(shù)等價(jià)于MRF的能量函數(shù)尋優(yōu)問題，并將這些實(shí)例類中心稱為代表點(diǎn).基于這一重要結(jié)論，如引言所說，根據(jù)MRF能量函數(shù)的不同的優(yōu)化方法，這類聚類算法主要分成2種：1)使用LBP(loopy belief propagation)算法[11]優(yōu)化，例如AP算法；2)使用Graph Cuts算法優(yōu)化，例如EEM算法.本節(jié)將以AP算法和EEM算法為例，在1.1節(jié)和1.2節(jié)對(duì)這2類算法作簡(jiǎn)要的介紹與分析.之后利用概率框架統(tǒng)一這2種算法，進(jìn)而引導(dǎo)出新的基于此框架的數(shù)據(jù)流動(dòng)態(tài)聚類算法.

1.1AP聚類算法

AP聚類算法的目標(biāo)函數(shù)如下：

(1)

其中，xp表示樣本點(diǎn)集合中第p個(gè)樣本點(diǎn)；N是樣本集中樣本點(diǎn)的個(gè)數(shù)，c是待求的代表點(diǎn)集合；cp即為樣本點(diǎn)集合中第p個(gè)樣本點(diǎn)xp的代表點(diǎn)；d(xp,xcp)表示樣本點(diǎn)xp與其代表點(diǎn)xcp之間的距離，一般使用歐氏距離.AP聚類算法使用LBP優(yōu)化算法求解該目標(biāo)函數(shù)，并定義了2個(gè)變量r(i,k)表示候選代表點(diǎn)xk作為樣本點(diǎn)xi的代表點(diǎn)的合適程度，而a(i,k)表示樣本點(diǎn)xi與候選代表點(diǎn)xk的適合程度.具體地，兩者迭代公式為

(2)

(3)

其中，la∈[0,1]，默認(rèn)為0.5，稱為阻尼系數(shù)(damping factor).阻尼系數(shù)還有一個(gè)重要的作用是改進(jìn)算法的收斂性：當(dāng)算法發(fā)生震蕩不能收斂時(shí)，增大la可以消除震蕩.

AP算法完全突出了類中心需要預(yù)設(shè)的限定條件且其聚類結(jié)果十分穩(wěn)定，受到了近年來的廣泛關(guān)注和研究.但由于AP算法采用了LBP策略，該優(yōu)化策略并不能保證其收斂性，文獻(xiàn)[9]使用阻尼技術(shù)來解決這個(gè)問題，然而，阻尼系數(shù)的選擇是一個(gè)非常精細(xì)的工作，不適合的阻尼系數(shù)通常會(huì)導(dǎo)致算法不收斂.另外，由于AP算法僅考慮某一時(shí)刻的數(shù)據(jù)，并不能借助于基于原始數(shù)據(jù)的相關(guān)結(jié)論來提高當(dāng)前數(shù)據(jù)的聚類性能.因此，這些缺陷使得這種經(jīng)典的AP聚類算法不能用來解決數(shù)據(jù)流動(dòng)態(tài)聚類問題.

1.2EEM聚類算法

對(duì)于MRF的能量函數(shù)尋優(yōu)問題，2003年，文獻(xiàn)[11]已經(jīng)通過實(shí)驗(yàn)證明以α-expansion為代表的Graph Cuts優(yōu)化算法比LBP更優(yōu)，但是α-expansion優(yōu)化算法僅能使用于基于樣本兩兩間關(guān)系(pairwise submodular)的能量函數(shù)優(yōu)化問題.因此，2013年，文獻(xiàn)[13]證明α-expansion優(yōu)化算法也可以用來解決基于代表點(diǎn)的聚類算法的目標(biāo)函數(shù)尋優(yōu)問題，并基于此提出了一種改進(jìn)的算法稱為EEM聚類算法.

EEM聚類算法的目標(biāo)函數(shù)為

(4)

與AP聚類算法類似，目標(biāo)函數(shù)中xp表示樣本點(diǎn)集合中第p個(gè)樣本點(diǎn)，c是待求的樣本點(diǎn)集合，θp,q(cp,cq)是使得代表點(diǎn)集合c有效的約束項(xiàng)，文獻(xiàn)[13]已證明：

對(duì)于?p,q,cp,cq,α∈{1,2,…,N}，有

θp,q(cp,cq)+θp,q(α,α)≤θp,q(cp,α)+θp,q(α,cq)

(5)

成立.

EEM聚類算法是基于代表點(diǎn)聚類算法的最新研究成果，由于使用了不同于AP算法的優(yōu)化算法，實(shí)驗(yàn)證明EEM算法比AP算法更高效、更穩(wěn)定.雖然文獻(xiàn)[2]所提出的EEM算法并不能直接解決數(shù)據(jù)流的動(dòng)態(tài)聚類問題，但是其提供了一個(gè)新的解決該類問題的框架，基于此框架本文第3節(jié)提出了一種新的動(dòng)態(tài)數(shù)據(jù)流聚類算法，考慮到EEM算法在傳統(tǒng)聚類問題中體現(xiàn)出的高性能，該算法在解決動(dòng)態(tài)數(shù)據(jù)聚類問題時(shí)具有不錯(cuò)的應(yīng)用前景.

1.3概率框架下的基于代表點(diǎn)聚類算法

分析AP算法和EEM算法，發(fā)現(xiàn)兩者目標(biāo)函數(shù)之間的相似性.2類算法均將聚類問題看作MRF能量函數(shù)的尋優(yōu)問題，本節(jié)將利用概率的信息表征特征，基于最大后驗(yàn)概率(maximum a posteriori, MAP)原理，給出一個(gè)AP算法和EEM算法的聯(lián)合目標(biāo)函數(shù).

給定數(shù)據(jù)樣本集合X={x1,x2,…,xN}∈N×D(N為樣本總量、D為樣本維數(shù))，E={E(x1),E(x2),…,E(xN)}為樣本選擇的代表點(diǎn)集合，有效的代表點(diǎn)集合E必須滿足：如果樣本集中有其他樣本選擇xi作為代表點(diǎn)，則樣本xi必須選擇其本身為代表點(diǎn)，即如果存在xj，其E(xj)=i，則必須E(xi)=i，即?i∈{1,2,…,N},E(E(xi))=E(xi).

1.3.1相關(guān)概念

高斯混合模型(Gaussian mixture model, GMM)能夠平滑地近似任意形狀的概率密度，根據(jù)GMM的概率密度函數(shù)，本文定義代表點(diǎn)集合的先驗(yàn)概率以及樣本點(diǎn)和代表點(diǎn)的概率關(guān)系如下，其中σ與高斯核中的參數(shù)一致：

定義1. 當(dāng)前代表點(diǎn)集合E的先驗(yàn)概率為

(6)

其中:

(7)

且M是一個(gè)足夠大的常數(shù).

定義2. 樣本點(diǎn)xi與當(dāng)前代表點(diǎn)集合E中的E(xi)的概率關(guān)系如下：

(8)

其中d(xi,E(xi))表示樣本xi與代表點(diǎn)E(xi)之間的歐氏距離，可以作為相似性的一種度量方法.

1.3.2基于概率的代表點(diǎn)聚類算法描述

(9)

定義1,2中的常數(shù)項(xiàng)不影響目標(biāo)函數(shù)的求解，因此目標(biāo)函數(shù)式(9)可以表示為

(10)

當(dāng)其中的參數(shù)取不同數(shù)值時(shí)，該目標(biāo)函數(shù)將等價(jià)于AP算法和EEM算法的目標(biāo)函數(shù)：

1) 當(dāng)σ=1時(shí)，分析該式與EEM算法的目標(biāo)函數(shù)式(4)，發(fā)現(xiàn)式(10)等價(jià)于MRF里的最小能量函數(shù)的尋優(yōu)問題，并可以用改進(jìn)的α-expansion算法進(jìn)行優(yōu)化，此時(shí)EEM聚類算法是該目標(biāo)函數(shù)的一種特例.

2) 當(dāng)M=∞且σ=1時(shí)，式(10)等價(jià)于式(1)，同樣可以看作是MRF的能量函數(shù)尋優(yōu)問題，若使用LBP優(yōu)化算法求解，即為AP聚類算法，因此AP聚類算法是該目標(biāo)函數(shù)的另一種特例.

由以上2點(diǎn)可知，AP算法和EEM算法都要求σ=1，因此本文僅考慮σ=1的情況，而σ取其他值的情況不在本文的討論范圍內(nèi).在本節(jié)中利用目標(biāo)函數(shù)式(10)將2種典型的基于代表點(diǎn)的算法——AP聚類算法和EEM聚類算法——統(tǒng)一起來，使得基于代表點(diǎn)的算法應(yīng)用得更加廣泛，方便在數(shù)據(jù)流動(dòng)態(tài)聚類中使用這種思想.另外，由于定義1,2直接給出了樣本點(diǎn)xi選擇當(dāng)前代表點(diǎn)集合中代表點(diǎn)E(xi)的概率以及代表點(diǎn)集合E的先驗(yàn)概率，因而在數(shù)據(jù)特征不發(fā)生突變的情況下能夠直接度量樣本點(diǎn)及其代表點(diǎn)的概率關(guān)系，并且自然地運(yùn)用于數(shù)據(jù)流的動(dòng)態(tài)聚類問題中.

2基于概率的漂移動(dòng)態(tài)α-expansion聚類算法

2.1基本概念

定義3. 數(shù)據(jù)流.令k表示任意時(shí)間點(diǎn)，Xk表示該時(shí)間達(dá)到的樣本集合，因此，數(shù)據(jù)流可以表示為若干樣本集合DS={X1,X2,…,Xk,…}.

定義4. 數(shù)據(jù)漂移.數(shù)據(jù)漂移描述的是在數(shù)據(jù)流DS={X1,X2,…,Xk,…}上變化的樣本集合.當(dāng)2個(gè)樣本集合A和B，數(shù)據(jù)漂移算法依次處理樣本集合，在時(shí)刻k樣本集合A是穩(wěn)定的，經(jīng)過時(shí)間Δt后，樣本集合為B，即在時(shí)間Δt內(nèi)樣本集合由A漂移為B.從數(shù)據(jù)漂移速度上來說，一般將數(shù)據(jù)漂移分為突變與不發(fā)生突變2種類型，本文主要研究的是不發(fā)生突變數(shù)據(jù)漂移聚類問題.

2.2算法框架

本文研究的動(dòng)態(tài)數(shù)據(jù)聚類算法是在數(shù)據(jù)漂移且特征不發(fā)生突變的情況下對(duì)數(shù)據(jù)流進(jìn)行聚類分析.為方便下文的研究，設(shè)原始數(shù)據(jù)聚類產(chǎn)生的代表點(diǎn)集合為E0，x0表示漂移的樣本點(diǎn)，N0表示漂移的樣本數(shù)，xi表示當(dāng)前需處理的樣本點(diǎn)，N表示當(dāng)前樣本總數(shù).由于數(shù)據(jù)流數(shù)據(jù)的特性以及本文研究的數(shù)據(jù)環(huán)境，在動(dòng)態(tài)數(shù)據(jù)流算法的構(gòu)造過程中主要考慮到2點(diǎn)：1)與目標(biāo)函數(shù)式(10)的構(gòu)造目的一致，在數(shù)據(jù)流動(dòng)態(tài)聚類中，當(dāng)前樣本從已確定的代表點(diǎn)集合中選擇概率最大的代表點(diǎn)，如圖2(a)所示，所有樣本根據(jù)自身與代表點(diǎn)集合中代表點(diǎn)的概率關(guān)系選擇其中的E(a)，E(b)，E(c)為代表點(diǎn)；2)由于不同時(shí)間點(diǎn)樣本間的相似性，動(dòng)態(tài)聚類算法所產(chǎn)生的代表點(diǎn)應(yīng)該與原始數(shù)據(jù)產(chǎn)生的代表點(diǎn)具有高度的相似性，如圖2所示，圖2(b)為原始數(shù)據(jù)的聚類結(jié)果，圖2(a)為某一時(shí)刻數(shù)據(jù)聚類結(jié)果，圖2(a)與圖2(b)具有相似性，即圖2(a)(b)中的代表點(diǎn)具有相似性.

Fig. 2　Dynamic clustering for data stream.圖2　數(shù)據(jù)流動(dòng)態(tài)聚類過程

因此，PDDE聚類算法的目標(biāo)函數(shù)為

(11)

在原始樣本點(diǎn)高效聚類的前提下，PDDE聚類算法的構(gòu)造不考慮數(shù)據(jù)量很大的原始樣本集，僅借鑒了原始樣本的代表點(diǎn)信息，因此相比其他的數(shù)據(jù)流聚類算法，PDDE算法能夠更快地完成算法優(yōu)化.根據(jù)之前對(duì)基于代表點(diǎn)的聚類算法與MRF能量函數(shù)之間關(guān)系的研究，PDDE聚類算法的目標(biāo)函數(shù)式(11)也可以看作是MRF能量函數(shù)的優(yōu)化問題.

文獻(xiàn)[13]中已經(jīng)證明EEM的目標(biāo)函數(shù)，即式(4)可以用α-expansion算法進(jìn)行優(yōu)化，以α-expansion算法為代表的Graph Cut優(yōu)化算法，在求解MRF能量函數(shù)問題時(shí)已被證明優(yōu)于LBP優(yōu)化算法.基于文獻(xiàn)[13]的結(jié)論，可以證明PDDE算法的目標(biāo)函數(shù)式(11)也可以使用α-expansion算法進(jìn)行優(yōu)化，證明過程如下：

證明. 不考慮公式中常數(shù)項(xiàng)的影響，式(11)可以變?yōu)?/p>

(12)

ηi,j(E(xi),E(xj))+ηi,j(α,α)≤

ηi,j(E(xi),α)+ηi,j(α,E(xj))

(13)

成立.同時(shí)，文獻(xiàn)[25]證明，當(dāng)式(13)成立時(shí)，形如目標(biāo)函數(shù)式(12)的能量函數(shù)可以用α-expansion算法優(yōu)化.

證畢.

根據(jù)一般的α-expansion優(yōu)化算法，每次迭代時(shí)，根據(jù)α的不同，樣本點(diǎn)有2種選擇:1)代表點(diǎn)不變；2)代表點(diǎn)變?yōu)棣?然而，若按這種尋優(yōu)方式，將會(huì)使得算法的時(shí)間復(fù)雜度較大，因此本文將使用一種改進(jìn)的α-expansion算法來優(yōu)化目標(biāo)函數(shù)式(11)，將在2.3節(jié)詳細(xì)討論.

2.3算法優(yōu)化

具體的優(yōu)化過程，根據(jù)當(dāng)前樣本點(diǎn)的種類將分為2種情況.由于常數(shù)項(xiàng)不影響算法的性能，因此若無(wú)特殊說明，本文下面的優(yōu)化算法過程中涉及能量耗損都已經(jīng)忽略了常數(shù)項(xiàng)的影響.

Fig. 3　Two types for when xαis an exemplar.圖3　xα是代表點(diǎn)時(shí)2種α -expansion情況

情形1. 當(dāng)xα是代表點(diǎn)時(shí).

若E(xl)不改變，經(jīng)典的α-expansion優(yōu)化過程中將l簇中某些樣本點(diǎn)的代表點(diǎn)變?yōu)閤α，如圖3(b)所示.改進(jìn)的α-expansion優(yōu)化算法則充分考慮到代表點(diǎn)集合有效的前提條件，即所有樣本點(diǎn)已經(jīng)選擇當(dāng)前代表點(diǎn)集合E中最有可能作為其代表點(diǎn)的樣本作為代表點(diǎn)，因此在改進(jìn)的α-expansion優(yōu)化過程中，l簇中所有樣本點(diǎn)的代表點(diǎn)均不會(huì)改變，如圖3(d)所示.此時(shí)，能量函數(shù)損耗為0，即R=0.

若E(xl)改變，經(jīng)典的α-expansion優(yōu)化過程中將l簇中所有樣本點(diǎn)的代表點(diǎn)變?yōu)閤α，如圖3(c)所示.由于改進(jìn)的α-expansion優(yōu)化算法擴(kuò)張了代表點(diǎn)集合的搜索空間，因此l簇中的樣本點(diǎn)將根據(jù)自身與代表點(diǎn)的相似性有選擇地將代表點(diǎn)變成S(i)，如圖3(e)所示.此時(shí)，能量函數(shù)的損耗可以表示為

(14)

因此，在改進(jìn)的α-expansion優(yōu)化過程中，若RXl<0，則進(jìn)行圖3(e)所示的擴(kuò)張，即令E(xi)=S(i),?xi∈Xl；否則進(jìn)行圖3(d)所示擴(kuò)張，即代表點(diǎn)集合E不變化.

因此，當(dāng)xα是代表點(diǎn)時(shí)，執(zhí)行操作如算法1所述：

算法1. 情形1算法.

ifE(xα)=α

for每個(gè)其余代表點(diǎn)xl

計(jì)算l簇中每個(gè)樣本點(diǎn)的次優(yōu)代表點(diǎn)S(i)；

根據(jù)式 (14) 計(jì)算RXl；

ifRXl<0

l簇中樣本點(diǎn)的代表點(diǎn)改為S(i)；

end if

end for

end if

情形2. 當(dāng)xα是一般點(diǎn)時(shí).

建立一個(gè)新的代表點(diǎn)集合E′=E，而E′(xα)=α，之后的優(yōu)化過程與情形1一致，如圖4所示.

如圖4(b)所示，經(jīng)典的α-expansion優(yōu)化過程中將該類樣本的代表點(diǎn)變?yōu)閤α，本文采用改進(jìn)的α-expansion優(yōu)化過程則將這部分樣本的代表點(diǎn)變?yōu)镾(i)，如圖4(d)所示，相比經(jīng)典的α-expansion優(yōu)化算法，改進(jìn)后的α-expansion算法保證樣本點(diǎn)選擇了更合理的代表點(diǎn).此時(shí)，能量函數(shù)的損耗為

(15)

Fig. 4　Two types for when xαis not an exemplar.圖4　xα不是代表點(diǎn)時(shí)2種α -expansion情況

如果E′(xl)改變，與情形1中圖3(b)類擴(kuò)張類似，在經(jīng)典的α-expansion優(yōu)化過程中，l簇中所有樣本將選擇xα作為代表點(diǎn)，如圖4(c)所示.這顯然是不合理的，因此，在改進(jìn)的α-expansion優(yōu)化中，l簇中所有樣本都需要將他們的代表點(diǎn)改成S(i)，如圖4(e)所示，此時(shí)能量函數(shù)的損耗為

(16)

R2=d(xα,E(xα))-d(xα,xα)+λ[(p(xα,E(xα)))2-

2(p(xα,E(xα))-p(xα,xα))×p(xα,E0(xα))-

(17)

因此，當(dāng)xα不是代表點(diǎn)時(shí)，執(zhí)行操作如算法2所述：

算法2. 情形2算法.

ifE(xα)≠α

設(shè)置E′=E，而E′(xα)=α；

for每個(gè)其余代表點(diǎn)xl

計(jì)算l簇中每個(gè)樣本點(diǎn)的次優(yōu)代表點(diǎn)S(i)；

根據(jù)式 (16) 計(jì)算RXl；

l簇中樣本點(diǎn)的代表點(diǎn)改為S(i)；

else

end if

end for

end if

2.4PDDE算法整體流程

根據(jù)2.3節(jié)相關(guān)優(yōu)化理論及迭代公式推導(dǎo)所獲取的學(xué)習(xí)規(guī)則，本節(jié)將給出PDDE聚類算法的具體步驟詳見算法3.

算法3. PDDE算法.

輸入：數(shù)據(jù)流數(shù)據(jù)X={X1,X2,…,Xk,…}每個(gè)樣本自身相似性d(xi,xi)，正則化平衡因子λ；

輸出：當(dāng)前樣本集中的有效代表點(diǎn)集合E.

步驟1. 使用AP算法或者EEM算法對(duì)該時(shí)刻前數(shù)據(jù)進(jìn)行聚類，產(chǎn)生原始的代表點(diǎn)集合E0，令t=1；

步驟2. 隨機(jī)產(chǎn)生α-expansion的順序o，根據(jù)式(8)計(jì)算漂移數(shù)據(jù)選擇其代表點(diǎn)的概率p(xi,E0(xi))，以及新的樣本集內(nèi)兩兩樣本間的互為代表點(diǎn)的概率p(xi,xj)；

步驟3. 按照α-expansion的順序o，如果xα是代表點(diǎn)，則執(zhí)行算法1，否則執(zhí)行算法2；

步驟4. 根據(jù)式(17)更新R2，若R2>0，E=E′，否則E不改變,轉(zhuǎn)到步驟3；

步驟5.t=t+1；

步驟6. 算法收斂后，輸出所得代表點(diǎn)集E.

3仿真實(shí)驗(yàn)

為了驗(yàn)證本文對(duì)數(shù)據(jù)流聚類任務(wù)的有效性，充分體現(xiàn)本文所提的PDDE聚類算法對(duì)漂移數(shù)據(jù)的聚類性能，本節(jié)將在人工合成數(shù)據(jù)集D31,Birch3及真實(shí)數(shù)據(jù)集Forest CoverType,KDD CUP99數(shù)據(jù)流上進(jìn)行驗(yàn)證，并與AP算法以及EEM聚類算法進(jìn)行比較，并對(duì)此結(jié)果進(jìn)行適當(dāng)?shù)姆治龊徒忉?

為了公正地對(duì)聚類算法的聚類性能做出合理的評(píng)價(jià)，本文將采用2種評(píng)價(jià)指標(biāo)進(jìn)行算法的性能分析:

1) 聚類純度(purity)[18]

(18)

其中，E={e1,e2,…,ek}是聚類算法得到的聚類結(jié)果，C={c1,c2,…,cj}是真實(shí)的類標(biāo)集合.其取值范圍為[0,1]，且隨著數(shù)值的偏高顯示出算法的性能越為優(yōu)越.

2)SSQ(sum of square distance)[17]

(19)

其中，xk表示第k類的代表點(diǎn)，xi表示k類中第i個(gè)樣本，d(xk,xi)表示兩者的歐氏距離，SSQ的值越小聚類結(jié)果越緊密.

在本文的實(shí)驗(yàn)部分，各可調(diào)參數(shù)的設(shè)置均遵循文獻(xiàn)[22,24,26]的計(jì)算策略，具體如表1所示.由于PDDE算法的初始化含有隨機(jī)過程，因此在本文下面的實(shí)驗(yàn)部分中，如無(wú)特殊說明，均為在每個(gè)參數(shù)下10次算法完整運(yùn)行后的均值所組成.

Table 1　Parameters of the PDDE Algorithm

實(shí)驗(yàn)環(huán)境：實(shí)驗(yàn)硬件平臺(tái)為Intel?CoreTMi3-3240 CPU，其主頻為3.40 GHz，內(nèi)存為4 GB.操作系統(tǒng)為64位Windows 7，編程環(huán)境為MATLAB 2010a等.

3.1人工合成數(shù)據(jù)集實(shí)驗(yàn)

為了充分驗(yàn)證本文所提的PDDE算法對(duì)數(shù)據(jù)流數(shù)據(jù)的動(dòng)態(tài)聚類效果，并能夠體現(xiàn)數(shù)據(jù)隨時(shí)間變化的特征，人工合成的數(shù)據(jù)集須遵循2項(xiàng)原則：

1) 原始數(shù)據(jù)應(yīng)包含良好的聚類特征，即原始數(shù)據(jù)必須滿足由其總結(jié)得到的聚類結(jié)果是可靠的，從而保證在此基礎(chǔ)上對(duì)變化后的數(shù)據(jù)進(jìn)行聚類能夠提高其有效性；

2) 變化后的數(shù)據(jù)集與原始數(shù)據(jù)集應(yīng)該具有相似性，或者共享部分?jǐn)?shù)據(jù)，且其余數(shù)據(jù)有相似性.

本文采用的人工合成數(shù)據(jù)集D31[27]以及Birch3[28]是聚類算法中常用的驗(yàn)證算法聚類性能的數(shù)據(jù)集之一.其中D31數(shù)據(jù)集包括3 100個(gè)2維樣本，共31類，其均勻分布如圖5(a)所示；Birch3數(shù)據(jù)集則包括了10 000個(gè)2維樣本，其聚類形狀及樣本分布均滿足隨機(jī)性.在實(shí)驗(yàn)過程中，認(rèn)為數(shù)據(jù)中樣本的輸入順序即為樣本隨著時(shí)間的流入順序，在D31數(shù)據(jù)中，假設(shè)原始樣本總數(shù)為1 000，單位時(shí)間內(nèi)流入數(shù)據(jù)的個(gè)數(shù)為Sspeed=620，而針對(duì)Birch3數(shù)據(jù)集，假設(shè)原始樣本總數(shù)為10 000，單位時(shí)間內(nèi)流入數(shù)據(jù)的個(gè)數(shù)為Sspeed=1 000.由于目標(biāo)樣本數(shù)應(yīng)該不足以保證傳統(tǒng)聚類算法的聚類性能，因此實(shí)驗(yàn)中目標(biāo)樣本總數(shù)遠(yuǎn)小于原始樣本總數(shù).

如圖5(a)所示，D31數(shù)據(jù)集中目標(biāo)數(shù)據(jù)與原始數(shù)據(jù)無(wú)論在分布上存在較高的相似性，另一方面，圖5(b)所示的Birch3數(shù)據(jù)集則體現(xiàn)了另一種數(shù)據(jù)間的相似性，即原始數(shù)據(jù)與目標(biāo)數(shù)據(jù)共享部分?jǐn)?shù)據(jù).由本文之前的分析可知，PDDE算法能夠處理包括這2種情況在內(nèi)的數(shù)據(jù)流動(dòng)態(tài)聚類問題.

Fig. 5　Synthetic dataset.圖5　人造數(shù)據(jù)集

由于Birch3數(shù)據(jù)集沒有提供數(shù)據(jù)的標(biāo)簽信息，因此在Birch3實(shí)驗(yàn)中，除了SSQ評(píng)價(jià)標(biāo)準(zhǔn)外，本文還采用的聚類數(shù)作為聚類性能的評(píng)價(jià)標(biāo)準(zhǔn).

另一方面，實(shí)驗(yàn)中涉及到的3種算法均包含了樣本損耗，根據(jù)表1，3種算法中的樣本損耗均為所有樣本相似度的中值乘以[0.01,0.1,1,10,50,100]中的最優(yōu)系數(shù).根據(jù)實(shí)驗(yàn)結(jié)果，當(dāng)聚類性能最優(yōu)時(shí)，PDDE算法中該系數(shù)為0.1，而AP及EEM算法中該系數(shù)為1.

考慮到數(shù)據(jù)流動(dòng)態(tài)聚類中不能對(duì)算法中涉及到的參數(shù)進(jìn)行尋優(yōu)，因此在實(shí)驗(yàn)中均在固定參數(shù)環(huán)境下對(duì)不同時(shí)刻的數(shù)據(jù)進(jìn)行聚類，具體設(shè)置如下：在D31實(shí)驗(yàn)中，經(jīng)過2個(gè)單位時(shí)間，因此實(shí)驗(yàn)結(jié)果中包括2個(gè)時(shí)刻T1和T2;而在Birch3實(shí)驗(yàn)中，數(shù)據(jù)經(jīng)過5個(gè)單位時(shí)間，因此實(shí)驗(yàn)結(jié)果包括時(shí)刻T1,T2,T3,T4,T5的聚類結(jié)果.

人造數(shù)據(jù)集實(shí)驗(yàn)結(jié)果如表2及圖6～9所示.其中表2及圖6是基于D31數(shù)據(jù)流的實(shí)驗(yàn)結(jié)果，由于EEM針對(duì)該數(shù)據(jù)集的聚類性能極不穩(wěn)定，因此表中沒有列出EEM的聚類結(jié)果，圖6(a)是AP算法針對(duì)原始數(shù)據(jù)的聚類結(jié)果，圖6(b)及6(c)是PDDE算法分別對(duì)時(shí)刻T1和T2數(shù)據(jù)的聚類結(jié)果，圖6(d)則為AP算法針對(duì)T1時(shí)刻數(shù)據(jù)聚類結(jié)果.圖7～9則顯示了Birch3的聚類結(jié)果，其中圖7(a)是Birch3中原始數(shù)據(jù)的聚類結(jié)果，圖7(b)～(d)則是某時(shí)刻PDDE聚類算法、EEM聚類算法和AP聚類算法的聚類結(jié)果，圖8為3種算法在不同時(shí)刻聚類總數(shù)的比較，圖9為PDDE算法在不同時(shí)刻聚類結(jié)果的SSQ性能比較.

Table 2　Comparison of Different Algorithms Based on D31

Fig. 6　Clustering results based on D31.圖6　基于D31數(shù)據(jù)集聚類結(jié)果

Fig. 7　Clustering results based on Brich3.圖7　基于Birch3 數(shù)據(jù)集聚類結(jié)果

Fig. 8　Comparison of the number of clusters based on Birch3.圖8　不同λ的聚類數(shù)比較(Birch3數(shù)據(jù)集)

Fig. 9　Comparison of SSQ based on Birch3.圖9　不同λ的SSQ比較(Birch3數(shù)據(jù)集)

分析表2及圖6～9可知，在處理數(shù)據(jù)流動(dòng)態(tài)聚類問題時(shí),PDDE算法具有穩(wěn)定、高效等特征.相比AP聚類及EEM聚類算法，PDDE聚類產(chǎn)生的結(jié)果更有效，尤其是當(dāng)新進(jìn)入的數(shù)據(jù)量不足，AP聚類算法及EEM聚類算法根據(jù)有限的樣本量產(chǎn)生的聚類結(jié)果實(shí)際上與樣本本身的分布存在較大的差異，而PDDE算法借助于原始數(shù)據(jù)的聚類結(jié)果，在樣本量不足的情況下仍能得到具有較高可信度的聚類結(jié)果.圖6、圖7直觀地表明，由于原始數(shù)據(jù)可靠的聚類結(jié)果，PDDE算法得到的聚類結(jié)果更加高效.

3.2真實(shí)數(shù)據(jù)集

在基于真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)中，使用2種廣泛使用的真實(shí)數(shù)據(jù)流，KDD CUP99和Forest CoverType.其中KDD CUP99是網(wǎng)絡(luò)入侵檢測(cè)數(shù)據(jù)，由MIT林肯實(shí)驗(yàn)室花費(fèi)2周時(shí)間檢測(cè)而成.數(shù)據(jù)集中共包含494 031個(gè)樣本，每個(gè)樣本41維，與文獻(xiàn)[19]中實(shí)驗(yàn)設(shè)置一致，實(shí)驗(yàn)中使用其中的34維連續(xù)屬性，所有樣本被分為五大類.為了構(gòu)造時(shí)序性數(shù)據(jù)，在實(shí)驗(yàn)過程中，認(rèn)為數(shù)據(jù)中樣本的輸入順序即為數(shù)據(jù)中隨著時(shí)間流入的數(shù)據(jù).對(duì)KDD CUP99數(shù)據(jù)做如下改造：初始數(shù)據(jù)為N0=10 000，每個(gè)單位時(shí)間內(nèi)流入的數(shù)據(jù)個(gè)數(shù)為Sspeed=2 000.為了保證新進(jìn)入的數(shù)據(jù)與原始數(shù)據(jù)具有充分的相似性，其中1 000個(gè)數(shù)據(jù)是從原始數(shù)據(jù)以及之前流入的數(shù)據(jù)中隨機(jī)選擇的，另外1 000個(gè)數(shù)據(jù)為數(shù)據(jù)集中樣本的順序進(jìn)入，即原始數(shù)據(jù)與新數(shù)據(jù)共享部分?jǐn)?shù)據(jù).

Forest CoverType數(shù)據(jù)集來自常用的UCI數(shù)據(jù)集，共包含581 012個(gè)樣本，每個(gè)樣本24維，與文獻(xiàn)[18]一致，實(shí)驗(yàn)中采用了其中10維連續(xù)屬性，F(xiàn)orest CoverType數(shù)據(jù)集將數(shù)據(jù)分為了七大類.與KDD CUP99一樣，認(rèn)為數(shù)據(jù)中樣本的輸入順序即為數(shù)據(jù)中隨著時(shí)間流入的數(shù)據(jù).對(duì)Forest CoverType數(shù)據(jù)做如下改造：初始數(shù)據(jù)為N0=1 000，每個(gè)單位時(shí)間內(nèi)流入的數(shù)據(jù)個(gè)數(shù)為Sspeed=200，其中100個(gè)數(shù)據(jù)是從原始數(shù)據(jù)以及之前流入的數(shù)據(jù)中隨機(jī)選擇的，另外100個(gè)數(shù)據(jù)為數(shù)據(jù)集中樣本的順序進(jìn)入，即原始數(shù)據(jù)與新數(shù)據(jù)共享部分?jǐn)?shù)據(jù).由于EEM算法在該數(shù)據(jù)集聚類結(jié)果非常不穩(wěn)定，因此將不考慮EEM的聚類結(jié)果.

實(shí)驗(yàn)中均為經(jīng)過5個(gè)單位時(shí)間，對(duì)每個(gè)單位時(shí)間內(nèi)新進(jìn)入的數(shù)據(jù)進(jìn)行聚類，并使用聚類純度，即式(18)作為聚類性能的評(píng)價(jià)標(biāo)準(zhǔn).實(shí)驗(yàn)中涉及到的參數(shù)環(huán)境如表1所示.由表1可知，3種算法中的樣本損耗均為所有樣本相似度的中值乘以[0.01,0.1,1,10,50,100]中的最優(yōu)系數(shù).實(shí)驗(yàn)證明，當(dāng)聚類性能最優(yōu)時(shí)，PDDE算法中樣本損耗為100，而AP及EEM算法中樣本損耗為50.具體實(shí)驗(yàn)結(jié)果如表3所示，圖10、圖11所示，說明PDDE算法能夠高效地處理數(shù)據(jù)流動(dòng)態(tài)聚類問題.

Table 3　Comparison of Different Algorithms Based on Real Dataset

Fig. 10　Comparison of clustering effectiveness based on Forest CoverType.圖10　基于Forest CoverType數(shù)據(jù)集聚類性能比較

Fig. 11　Comparison of clustering effectiveness based on KDD CUP99.圖11　基于KDD CUP99數(shù)據(jù)集聚類性能比較

3.3實(shí)驗(yàn)結(jié)果分析

分析3.1節(jié)和3.2節(jié)中基于人造數(shù)據(jù)集D31,Birch3和真實(shí)數(shù)據(jù)集Forest Covertype,KDD CUP99的實(shí)驗(yàn)結(jié)果，關(guān)于PDDE動(dòng)態(tài)數(shù)據(jù)流聚類算法可以得到3個(gè)結(jié)論：

1) PDDE算法能夠穩(wěn)定、高效地處理數(shù)據(jù)流的動(dòng)態(tài)聚類問題.在借助原始數(shù)據(jù)可靠的聚類結(jié)果后，通過PDDE算法得到的聚類結(jié)果比傳統(tǒng)的聚類算法更加有效.

2) 正則化平衡因子λ對(duì)實(shí)驗(yàn)結(jié)果影響較大.

3) 經(jīng)過多個(gè)單位時(shí)間后，由于PDDE算法借鑒了原始數(shù)據(jù)的聚類結(jié)果，在參數(shù)固定的情況下，聚類性能仍然非常穩(wěn)定，并優(yōu)于傳統(tǒng)的基于代表點(diǎn)聚類算法AP算法和EEM算法.

4結(jié)論

本文針對(duì)當(dāng)前基于代表點(diǎn)的聚類算法不具有處理數(shù)據(jù)流動(dòng)態(tài)聚類問題的能力，首先從概率角度給出了AP算法和EEM算法的聯(lián)合目標(biāo)函數(shù)，利用概率框架來度量樣本點(diǎn)選擇另一個(gè)樣本為代表點(diǎn)的可能性，以及代表點(diǎn)集合的先驗(yàn)概率來度量該代表點(diǎn)集合的穩(wěn)定性.由于該理論能夠直接度量某樣本與其代表點(diǎn)之間的相似性，為解決數(shù)據(jù)流的動(dòng)態(tài)聚類問題提供了前提條件.另一方面，本文進(jìn)一步使用Graph Cuts優(yōu)化算法求解能量函數(shù)，進(jìn)而保證了算法的聚類有效性.

此外，本文的另一大貢獻(xiàn)在于改進(jìn)了AP及EEM算法的聯(lián)合目標(biāo)函數(shù)，使之能夠適用于時(shí)序數(shù)據(jù)動(dòng)態(tài)聚類問題.通過樣本與其代表點(diǎn)之間的概率，借助于原始樣本與其代表點(diǎn)之間的概率關(guān)系，引入正則化平衡因子保證漂移后的樣本所選擇的代表點(diǎn)仍然能夠與之前的代表點(diǎn)保持較高的相似性，進(jìn)而提出了一種新的適用于時(shí)序數(shù)據(jù)聚類的有效算法——PDDE算法.同時(shí)，由于引入了概率，PDDE算法能夠處理原始數(shù)據(jù)與新數(shù)據(jù)之間的2種相似性關(guān)系，即不論原始數(shù)據(jù)與新數(shù)據(jù)是否共享部分?jǐn)?shù)據(jù)，PDDE算法都能夠完成數(shù)據(jù)流動(dòng)態(tài)聚類.通過在人工合成數(shù)據(jù)集D31和Birch3以及常用的真實(shí)數(shù)據(jù)集KDD CUP99,Forest CoverType的實(shí)驗(yàn)結(jié)果，均顯示本文方法較AP聚類以及EEM算法具有更穩(wěn)定、高效的聚類性能.

參考文獻(xiàn)

[1]Yu S, Tranchevent L C, Liu X, et al. Optimized data fusion for kernelK-means clustering[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2012, 34(5): 1031-1039

[2]Jing L, Ng M K, Huang J Z. An entropy weightingk-means algorithm for subspace clustering of high-dimensional sparse data[J]. IEEE Trans on Knowledge and Data Engineering, 2007, 19(8): 1026-1041

[3]Zhu L, Chung F L, Wang S. Generalized fuzzyC-means clustering algorithm with improved fuzzy partitions[J]. IEEE Trans on Systems, Man, and Cybernetics, Part B: Cybernetics, 2009, 39(3): 578-591

[4]Hall L O, Goldgof D B. Convergence of the single-pass and online fuzzyc-means algorithms[J]. IEEE Trans on Fuzzy Systems, 2011, 19(4): 792-794

[5]Wang S, Chung F L, Deng Z H. Robust maximum entropy clustering algorithm with its labeling for outliers[J]. Soft Computing, 2006, 10(7): 555-563

[6]Karayiannis N B. MECA: Maximum entropy clustering algorithm[C]Proc of the 3rd IEEE Conf on Fuzzy Systems. Piscataway, NJ: IEEE, 1994: 630-635

[7]Shannon C E. A mathematical theory of communication[J]. ACM SIGMOBILE Mobile Computing and Communications Review, 2001, 5(1): 3-55

[8]Wu Yingjie, Tang Qingming, Ni Weiwei, et al. A clustering hybrid based algorithm for privacy preserving trajectory data publishing[J]. Journal of Computer Research and Development, 2013, 50(3): 578-593 (in Chinese)(吳英杰, 唐慶明, 倪巍偉, 等. 基于聚類雜交的隱私保護(hù)軌跡數(shù)據(jù)發(fā)布算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(3): 578-593)

[9]Frey B J, Dueck D. Clustering by passing messages between data points[J]. Science, 2007, 315(5814): 972-976

[10]Murphy K P, Weiss Y, Jordan M I. Loopy belief propagation for approximate inference: An empirical study[C]Proc of the 15th Conf on Uncertainty in Artificial Intelligence. San Francisco: Morgan Kaufmann, 1999: 467-475

[11]Tappen M F, Freeman W T. Comparison of graph cuts with belief propagation for stereo, using identical MRF parameters[C]Proc of the 9th IEEE Int Conf on Computer Vision. Piscataway, NJ: IEEE, 2003: 900-906

[12]Boykov Y, Veksler O, Zabih R. Fast approximate energy minimization via graph cuts[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2001, 23(11): 1222-1239

[13]Zheng Yun, Chen Pei. Clustering based on enhancedα-expansion move[J]. IEEE Trans on Knowledge and Data Engineering, 2013, 25(10): 2206-2216

[14]Guha S, Meyerson A, Mishra N, et al. Clustering data streams: Theory and practice[J]. IEEE Trans on Knowledge and Data Engineering, 2003, 15(3): 515-528

[15]O’Callaghan L, Mishra N, Meyerson A, et al. Streaming-data algorithms for high-quality clustering[C]Proc of the 18th IEEE Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2002: 685-694

[16]Aggarwal C C, Han J, Wang J, et al. A framework for clustering evolving data streams[C]Proc of the 29th Int Conf on Very Large Data Bases. San Francisco: Morgan Kaufmann, 2003: 81-92

[17]Aggarwal C C, Han J, Wang J, et al. A framework for projected clustering of high dimensional data streams[C]Proc of the 30th Int Conf on Very Large Data Bases. San Francisco: Morgan Kaufmann, 2004: 852-863

[18]Cao F, Ester M, Qian W, et al. Density-based clustering over an evolving data stream with noise[C]Proc of 2006 SIAM Int Conf on Data Mining. Philadelphia, PA: SIAM, 2006: 328-339

[19]Yu Yanwei, Wang Qin, Kuang Jun, et al. An on-line density-based clustering algorithm for spatial data stream[J]. Acta Automatica Sinica, 2012, 38(6): 1061-1059 (in Chinese)(于彥偉, 王沁, 鄺俊, 等. 一種基于密度的空間數(shù)據(jù)流在線聚類算法[J]. 自動(dòng)化學(xué)報(bào), 2012, 38(6): 1051-1059)

[20]Yu Xiang, Yin Guisheng, Xu Xiandong, et al. A data stream subspace clustering algorithm based on region partition[J]. Journal of Computer Research and Development, 2014, 51(1): 88-95 (in Chinese)(于翔, 印桂生, 許憲東, 等. 一種基于區(qū)域劃分的數(shù)據(jù)流子空間聚類方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(1): 88-95)

[21]Deng Z H, Choi K S, Chung F L, et al. Enhanced soft subspace clustering integrating within-cluster and between-cluster information[J]. Pattern Recognition, 2010, 43(3): 767-781

[22]Sun A, Zeng D D, Chen H. Burst detection from multiple data streams: A network-based approach[J]. IEEE Trans on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 2010, 40(3): 258-267

[23]Zhu Y, Shasha D. Efficient elastic burst detection in data streams[C]Proc of the 9th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York; ACM, 2003: 336-345

[24]Jiang Yizhang, Deng Zhaohong, Wang Jun, et al. Transfer generalized fuzzyc-means clustering algorithm with improved fuzzy partitions by leveraging knowledge[J]. Pattern Recognition and Artificial Intelligence, 2013, 10(26): 975-984 (in Chinese)(蔣亦樟, 鄧趙紅, 王駿, 等. 基于知識(shí)利用的遷移學(xué)習(xí)一般化增強(qiáng)模糊劃分聚類算法[J]. 模式識(shí)別與人工智能, 2013, 10(26): 975-984)

[25]Kolmogorov V, Zabih R. What energy functions can be minimized via graph cuts?[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2004, 26(2): 147-159

[26]Huang Chengquan, Wang Shitong, Jiang Yizhang. A new fuzzy clustering algorithm with entropy index constraint[J]. Journal of Computer Research and Development, 2014, 51(9): 2117-2129 (in Chinese)(黃成泉, 王士同, 蔣亦樟. 熵指數(shù)約束的模糊聚類新算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(9): 2117-2129)

[27] Veenman C J, Reinders M J T, Backer E. A maximum variance cluster algorithm[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2002. 24(9): 1273-1280

[28]Zhang T, Ramakrishnan R, Livny M. BIRCH: A new data clustering algorithm and its applications[J]. Data Mining and Knowledge Discovery, 1997, 1 (2): 141-182

Bi Anqi, born in 1989. PhD candidate. Her current research interests include pattern recognition, intelligent computation and their application.

Dong Aimei, born in 1978. PhD candidate at the School of Digital Media, Jiangnan University, and lecturer at Qilu University of Technology. Her research interests include artificial intelligence, pattern recognition, and machine learning.

Wang Shitong, born in 1964. Professor and PhD supervisor. Senior member of China Computer Federation. Received his MS degree in computer science from Nanjing University of Aeronautics and Astronautics, China, in 1987. His current research interests include artificial intelligence, pattern recognition, fuzzy system, medical image processing, data mining, and intelligent computation and their applications.

A Dynamic Data Stream Clustering Algorithm Based on Probability and Exemplar

Bi Anqi1, Dong Aimei1,2, and Wang Shitong1

1(SchoolofDigitalMedia,JiangnanUniversity,Wuxi,Jiangsu214122)2(SchoolofInformation,QiluUniversityofTechnology,Jinan250353)

AbstractWe propose an efficient probability drifting dynamic α-expansion clustering algorithm, which is designed for data stream clustering problem. In this paper, we first develop a unified target function of both affinity propagation (AP) and enhanced α-expansion move (EEM) clustering algorithms, namely the probability exemplar-based clustering algorithm. Then a probability drifting dynamic α-expansion (PDDE) clustering algorithm has been proposed considering the probability framework. The framework is capable of dealing with data stream clustering problem when current data points are similar with pervious data points. In the process of clustering, the proposed algorithm ensures that the clustering result of current data points is at least comparable well with that of previous data points. What’s more, the proposed algorithm is capable of dealing with two kinds of similarities between current and previous data points, that is whether current data points share some points with previous data points or not. Besides, experiments based on both synthetic (D31, Birch 3) and real-world dataset (Forest Covertype, KDD CUP99) have indicated the capability of PDDE in clustering data streams. The advantage of the proposed clustering algorithm in contrast to both AP and EEM algorithms has been shown as well.

Key wordsdata stream; energy function; probability; optimization algorithm; dynamic clustering

收稿日期：2014-12-23；修回日期：2015-06-02

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(6127220);山東省高等學(xué)校科技計(jì)劃項(xiàng)目(J14LN05);江蘇省普通高校研究生科研創(chuàng)新計(jì)劃基金項(xiàng)目(KYLX_1124)

中圖法分類號(hào)TP391

This work was supported by the National Natural Science Foundation of China (6127220), the Project of Shandong Province Higher Educational Science and Technology Program (J14LN05), and Jiangsu Graduate Student Innovation Projects (KYLX_1124).