基于代表點評分策略的快速自適應(yīng)聚類算法

張遠(yuǎn)鵬 鄧趙紅 鐘富禮 杭文龍 王士同,

1(江南大學(xué)數(shù)字媒體學(xué)院 江蘇無錫 214122)

2(南通大學(xué)醫(yī)學(xué)信息學(xué)系 江蘇南通 226019)

3(香港理工大學(xué)計算學(xué)系 香港 999077)

(155297131@qq.com)

聚類分析是一種無監(jiān)督的學(xué)習(xí)方法，在模式識別領(lǐng)域占有非常重要的地位，成熟的聚類算法目前在圖像分割、數(shù)據(jù)挖掘、生物信息學(xué)以及計算機(jī)視覺等領(lǐng)域得到了廣泛的應(yīng)用[1-3].聚類的目標(biāo)是找到數(shù)據(jù)集中樣本的“自然分組”，即相似樣本的集合，稱之為“簇”.目前聚類的方法有很多種，其中基于代表點的聚類算法近年來受到了廣泛的關(guān)注.

代表點(exemplar)是數(shù)據(jù)集中實際存在的樣本，代表簇中心.目前，基于代表的聚類算法可大體分為3類：

1) 以AP(affinity propagation)[4]和EEM (enhancedα-expansion move)[5]等為代表的聚類算法.該類算法可以通過優(yōu)化Markov隨機(jī)場(Markov random field, MRF)進(jìn)行求解.優(yōu)化MRF的方法有2種：①AP所采用的基于信息傳遞的LBP(loop belief propagation)算法[6]；②EEM所采用基于Graph Cuts的方法[7].在該類算法中，將數(shù)據(jù)集中所有的樣本都當(dāng)成潛在的類中心，然后通過迭代不斷更新每個樣本的吸引度值和歸屬度值，直到產(chǎn)生高質(zhì)量的代表點[5].

2) 以K-medoid[8]及其模糊版本FCMdd(fuzzyc-medoids)[9]等為代表的聚類算法.該類算法首先以隨機(jī)的方式選擇代表點，然后通過不斷迭代調(diào)整，使得距離平方誤差之和達(dá)到最小[4].

3) 以CDP(clustering by fast search and find of density peaks)[10]及其相關(guān)改進(jìn)算法為代表的基于密度的聚類算法[11]，該類算法通過密度估計，可以發(fā)現(xiàn)任意形狀數(shù)據(jù)集的密度峰值點(代表點).

上述不同類型的基于代表點聚類算法，有著各自的優(yōu)缺點.例如，AP算法突破了類中心及類中心個數(shù)需要預(yù)設(shè)的限制，同時算法的魯棒性較好.但是，AP算法在進(jìn)行樣本分配時，將其分配給離自己最近的代表點，因此，算法很難發(fā)現(xiàn)非凸形狀的簇，同時，AP算法的時間復(fù)雜度為O(N2logN)，無法處理大規(guī)模數(shù)據(jù).K-medoid算法由于是隨機(jī)選擇初始代表點，故對初始簇代表點的選擇非常敏感，若初始簇代表點選擇不當(dāng)，會造成聚類的結(jié)果和數(shù)據(jù)的實際分布相差很大.另外和AP一樣，該算法同樣不能很好地發(fā)現(xiàn)非凸形狀的簇.CDP算法認(rèn)為簇代表點的局部密度應(yīng)該大于其鄰居的局部密度，且不同簇代表點之間的距離相對較遠(yuǎn).通過這2種特征，CDP算法很容易發(fā)現(xiàn)簇代表點.該算法所采用的“一步”樣本分配策略(將樣本分配到距離自己最近且局部密度比自己大的樣本所在簇)可以發(fā)現(xiàn)任意形狀的簇，但是，容易出現(xiàn)一步錯、步步錯的局面.

受CDP算法的啟發(fā)，通過概率密度估計來尋找代表點也是一種有效的方法，因為代表點往往出自概率密度高的樣本.Parzen窗(Parzen window, PW)是一種有效的非參數(shù)概率密度估計模型，但該模型在進(jìn)行概率密度估計時需要所有的樣本都參與計算，因此，在樣本規(guī)模較大時概率密度估計的效率低下，不適合大規(guī)模數(shù)據(jù)集[12].解決這個問題的方法通常是用一個能夠代表原數(shù)據(jù)集樣本分布的子集來參與概率密度估計，即對原樣本進(jìn)行數(shù)據(jù)壓縮.目前用于執(zhí)行數(shù)據(jù)壓縮的方法很多，如Catlett[13]提出的隨機(jī)抽樣(random sampling)、分層抽樣(stratified sampling)和窺孔法(peepholing)，Lewis等人[14]提出的不確定抽樣(uncertainty sampling)以及主動學(xué)習(xí)(active learning)算法等.Girolami等人[15]提出的壓縮集密度估計器(reduced set density estimator，RSDE)就是其中具有代表性的一種方法，通過該方法獲得的壓縮集能夠以較高的精確逼近原數(shù)據(jù)集.RSDE的求解過程可等價于二次規(guī)劃問題，因此，時間復(fù)雜度在O(N2)以上，同樣不適合大規(guī)模數(shù)據(jù)集.隨后，Deng等人[16]提出了一種快速壓縮集密度估計器(fast reduced set density estimator， FRSDE)，認(rèn)為RSDE等價于中心約束的最小包含球問題，并利用近似最小包含球的快速核心集技術(shù)求解，使得FRSDE的時間復(fù)雜度和樣本規(guī)模呈近似線性關(guān)系，空間復(fù)雜度與樣本規(guī)模無關(guān)，與近似最小包含球的逼近參數(shù)有關(guān)，且所形成的壓縮集亦能夠以較高的精度逼近原數(shù)據(jù)集.

基于FRSDE，我們提出3點假設(shè)：1)每個簇有一個代表點，且代表點來自簇內(nèi)高密度樣本；2)代表點或在壓縮集中，或在壓縮集附近且與壓縮集中樣本具有高度相似性；3)各簇中樣本圍繞代表點并沿著壓縮集擴(kuò)散.基于以上3個假設(shè)，我們提出一個基于代表點評分策略的快速自適應(yīng)聚類算法(fast self-adaptive clustering algorithm based on exemplar score, ESFSAC)，該算法過程可以分為3部分：1)快速確定簇內(nèi)代表點；2)壓縮集聚類；3)壓縮集標(biāo)簽傳播.本文的貢獻(xiàn)主要體現(xiàn)在3個方面：

1) 在已有工作的基礎(chǔ)上，提出了一種基于壓縮集的快速密度估計方法計算每個樣本的代表點分值(exemplar score, ES)，用于評估樣本成為簇內(nèi)代表點的可能性，且從理論上證明了所提方法的合理性.借助ES，可以發(fā)現(xiàn)具有不同形狀數(shù)據(jù)集的簇內(nèi)代表點；

2) FRSDE“清理”了簇與簇之間的稀疏樣本，使得壓縮集中簇與簇之間的邊界更加清晰，因此，在壓縮集聚類時，摒棄了基于劃分的方法(將樣本分配給離自己最近的代表點)，利用代表點的鄰域不斷傳播標(biāo)簽，使得算法適用于不同形狀的數(shù)據(jù)集；

3) 根據(jù)第3個假設(shè)和ES，提出了一種快速的壓縮集標(biāo)簽傳播方法.該方法以壓縮集中獲得類別標(biāo)簽的樣本作為“種子”，不斷通過其鄰域傳播標(biāo)簽，當(dāng)已經(jīng)標(biāo)記的樣本達(dá)到一定規(guī)模后，利用抽樣方法，加速標(biāo)簽傳播速度.

1 基于概率密度估計的快速數(shù)據(jù)壓縮方法

1.1 RSDE

RSDE通過雇用樣本空間的高密度區(qū)域的樣本來實現(xiàn)對原始樣本空間分布的逼近，其優(yōu)化過程可等價于求解一個二次規(guī)劃問題，優(yōu)化所得到的結(jié)果為一個與樣本對應(yīng)的稀疏向量，向量中的元素表示樣本的權(quán)重系數(shù).對于給定的數(shù)據(jù)集D={x1,x2,…,xN}∈d，該問題可以描述為

(1)

其中，1表示一個N×1的單位向量；C表示一個大小為N×N的矩陣，其元素可表示為

Kh表示一個核函數(shù)，向量p中元素為所有樣本的PW密度估計值，可表示為

1.2 FRSDE

為了使得更多的機(jī)器學(xué)習(xí)中的核化方法等價于MEB問題，Tsang等人[18]將MEB問題擴(kuò)展為中心約束的最小包含球問題(center constrained minimal enclosing ball, CCMEB).

(2)

式(2)的對偶形式可以表示為

(3)

在式(3)中，

(4)

K表示N×N的矩陣，其元素為K(xi,xj)=φ(xi)Tφ(xj).由于式(3)中的約束條件αT1=1，故式(5)與式(3)同解.

(5)

其中η為一常數(shù).對于滿足式(5)且約束條件滿足式(4)的問題，可視為CCMEB問題.在式(1)中，令:

Δ=-diag(C)+2p+η1,

(6)

其中，η取值需要使得Δ≥0，則式(1)可重新表示為

(7)

比較式(7)和式(5)，在K=C,α=γ的情況下，顯然等價.因此，RSDE與CCMEB之間存在等價關(guān)系，可以利用近似MEB的快速核心集技術(shù)求解，具體求解過程請參見文獻(xiàn)[16].

2 代表點評分策略

2.1 代表點分值

為了尋找簇內(nèi)代表點，我們定義一個度量，即代表點分值ES來評價數(shù)據(jù)集中每個樣本成為簇內(nèi)代表點的可能性.對于給定的數(shù)據(jù)集D={x1,x2,…,xN}∈d，xi的代表點分值定義如下：

(8)

其中，j∈{i|βi>0,i=1,2,…,N}，βj表示樣本xj在壓縮集中的權(quán)重系數(shù)，樣本xi的概率密度p(xi)可以通過壓縮集進(jìn)行估計，即：

(9)

其中，Kσ(xi,xj)表示核函數(shù)，由于核函數(shù)的形狀對樣本密度估計的精度影響不大[17]，因此這里選擇比較常用的高斯核函數(shù).從式(9)可以看出，我們僅選擇了壓縮集中的樣本對原數(shù)據(jù)集中的樣本進(jìn)行密度估計，在數(shù)據(jù)集規(guī)模較大時這種方式可以顯著提高效率.

從式(8)中可以看出，ES的提出同時考慮了前文所述的第1個和第2個假設(shè)，即認(rèn)為簇內(nèi)代表點來自密度高的樣本，且代表點或在壓縮集中，或在壓縮集附近且與壓縮集中樣本具有高度相似性.接下來，通過2個定理來論證ES提出的合理性.

2.2 代表點分值合理性分析

定理1. 密度高的樣本是潛在的簇內(nèi)代表點.

證明. 對于給定的數(shù)據(jù)集D={x1,x2,…,xN}∈d，從中選擇M個樣本來估計D中樣本的概率密度，按照PW密度估計理論[19]，D中樣本的概率密度可以表示為p(x)=(1/).若用表示D中樣本真實概率密度，則與p(x)的積分累計誤差為

(10)

其中等式右邊第1項可以表示為數(shù)學(xué)期望的形式，即：

(11)

證畢.

定理2. 聚類的泛化性能僅僅依賴于樣本的概率密度分布.

(13)

(14)

(15)

證畢.

3 ESFSAC算法描述

ESFSAC聚類算法過程可以分為3個部分：1)在壓縮集的基礎(chǔ)上，利用代表點評分策略評估所有樣本的ES值；2)根據(jù)每個樣本的ES值，完成壓縮集的類別標(biāo)定，即壓縮集聚類；3)將壓縮集的標(biāo)簽傳遞至整個數(shù)據(jù)集，即剩余集聚類(剩余集指原數(shù)據(jù)集中去除壓縮集剩下的樣本集合).為了易于理解，首先給出算法中所涉及的3個相關(guān)定義.

定義1. 代表點候選集(exemplar candidate set).數(shù)據(jù)集中的樣本按照其ES值進(jìn)行從大到小進(jìn)行排序后所形成的樣本集合，該集合中，排在前面的樣本成為簇內(nèi)代表點的可能性越大.

定義2. 樣本x在數(shù)據(jù)集D中的ξ鄰域Nbξ(x,D).D是所有樣本到x的距離小于等于ξ的樣本的集合.

定義3. 冗余代表點(superfluous exemplar).某一簇中，除去ES值最大的樣本以外，還存在1個或1個以上的樣本xi,xi+1,…的ES值大于其他簇中最大的ES值，則稱xi,xi+1,…為冗余類代表點.

3.1 代表點評分

本節(jié)通過ES值來評估數(shù)據(jù)集中每個樣本成為簇內(nèi)代表點的可能性，并根據(jù)ES值形成代表點候選集.另外，值得注意的是，在評估樣本的ES值時，參與計算的是由FRSDE得到的原數(shù)據(jù)集的子集，由于其規(guī)模遠(yuǎn)小于原數(shù)據(jù)集，故相對于PW來說，其評估速度有較大的提升.本節(jié)的算法描述如算法 1所示：

經(jīng)濟(jì)林是以生產(chǎn)木料或其他林產(chǎn)品直接獲得經(jīng)濟(jì)效益為主要目的的森林。作為特有的土地資源類型，懷洪新河河道管理范圍內(nèi)有大量的堆土區(qū)和沖填區(qū)。目前懷洪新河仍以種植意大利楊為主；也有部分用于糧食作物種植、農(nóng)業(yè)經(jīng)濟(jì)開發(fā)或中草藥種植，無規(guī)模效應(yīng)，經(jīng)濟(jì)效益不明顯，且易引起新的水土流失。

算法1. 估算代表點分值(evaluate exemplar score， EES).

輸出：代表點候選集Dc.

過程：

① 初始化ES集E=?，初始化代表點候選集Dc=?；

② Fori=1 toN

Fork=1 toNr

End For

E=E∪{esi};

End For

③Dc=sort(E,D,‘descending’).

3.2 壓縮集聚類

在此階段，我們需要考慮3個問題：1)如何使得聚類過程具有自適應(yīng)性？即無需事先由用戶指定聚類類別數(shù).2)如何使得聚類算法能夠適應(yīng)不同形狀的數(shù)據(jù)集?3)針對出現(xiàn)的冗余代表點，如何處理？關(guān)于何時會出現(xiàn)冗余代表點，這里作一點簡要說明.當(dāng)數(shù)據(jù)集中各個簇的樣本密度分布較為平衡時(如4.2節(jié)中DS1，DS2，DS3)，一般不會出現(xiàn)冗余代表點.但是，在有些情況下，數(shù)據(jù)集中各個類別之間樣本大小不平衡或者樣本密度分布不均勻，容易出現(xiàn)冗余代表點.如DS4，樣本最多的簇中出現(xiàn)2個冗余代表點.

針對上述問題，我們設(shè)計了壓縮集聚類算法2.算法2的基本思想是從代表點候選集中逐個選擇代表點，并將其類別標(biāo)簽利用ξ鄰域傳遞的方式擴(kuò)散至整個壓縮集，直到所有壓縮集中的樣本都獲得類別標(biāo)簽.顯然，算法2具有自適應(yīng)性，且類別標(biāo)簽是沿著數(shù)據(jù)流的分布進(jìn)行ξ鄰域傳遞，故適合不同形狀的數(shù)據(jù)集.另外，對于某一個簇中的冗余代表點而言，其具有非常明顯的識別特征，因為冗余代表點一般在真實代表點(該簇中ES最大的樣本)附近，真實代表點會先于冗余代表點被選中，故在該簇的真實代表點執(zhí)行類別標(biāo)簽擴(kuò)散時，冗余代表點已經(jīng)獲取到真實代表點的類別信息.因此，在代表點候選集中選擇代表點時，對于已經(jīng)獲取了類別標(biāo)簽的代表點，則過濾.詳細(xì)的算法描述見算法2.

算法2. 壓縮集聚類(reduced set clustering，RSC).

輸出：壓縮集標(biāo)簽向量Labelr.

過程：

① 初始化標(biāo)簽向量Labelr=0；

Fori=1 toN

Continue;

End If

④ WhileDnb≠?

For eachyinDnb

計算Nbξ(y,Dr)在Labelr中將對應(yīng)的標(biāo)簽設(shè)置為i；

Dr=DrNbξ(y,Dr);

Dnb=Dnby;

Dnb=Dnb∪(Nbξ(y,Dr)y);

End For

End While

IfDr==empty

Break;

End If

End For

3.3 剩余集聚類

第3個假設(shè)認(rèn)為，剩余集中的樣本圍繞著代表點和已經(jīng)獲得類別標(biāo)簽的壓縮集分布，故仍然可以采用ξ鄰域類別標(biāo)簽傳遞的方法將壓縮集樣本的類別傳遞至剩余集樣本.但是，隨著已獲得標(biāo)簽的樣本逐漸增多，尤其當(dāng)數(shù)據(jù)集規(guī)模較大時，這種傳遞策略效率低下.因此，為了提高剩余集樣本類別分配的效率，采用Smola等人在文獻(xiàn)[21]中提出的抽樣方法，當(dāng)已經(jīng)獲得類別標(biāo)簽的樣本數(shù)量達(dá)到一定的閾值時(本文設(shè)定為1 000)，從已獲得標(biāo)簽的樣本中不斷進(jìn)行抽樣，傳遞抽樣樣本的標(biāo)簽.這種方法能夠提高剩余集樣本的聚類速度.剩余集聚類算法的詳細(xì)描述見算法3.

算法3. 剩余集聚類(remaining set clustering， RMSC).

輸入：數(shù)據(jù)集D、壓縮集Dr、壓縮集標(biāo)簽向量Labelr、距離閾值ξ；

輸出：剩余集標(biāo)簽向量Labelrm.

過程：

① 初始化剩余集標(biāo)簽向量Labelrm=0,

Drm=DDr;

② WhileDrm≠?

IfNr≤1 000

Ds=Dr;

Else

Ds=SmolaRandom(Dr,1 000);

End If

Fori=1 toNs

End For

End While

在算法3中，SmolaRandom表示一個抽樣過程；Labelrm是一個標(biāo)簽向量，代表剩余集中樣本的類別標(biāo)簽；Drm表示剩余集樣本集合.整個算法過程可以分為2個步驟：在步驟①中，初始化標(biāo)簽向量Labelrm以及獲取剩余集樣本集合；在步驟②中，Ds是一個臨時集合，存儲標(biāo)簽傳播的“種子”樣本，在已標(biāo)記樣本數(shù)目小于等于1 000時“種子”即為所有標(biāo)記樣本，當(dāng)已標(biāo)記樣本數(shù)目大于1 000時啟動抽樣過程，然后不斷將“種子”標(biāo)簽傳播至未標(biāo)記樣本，直到所有樣本均獲得標(biāo)簽.

3.4 ESFSAC算法復(fù)雜度分析

4 實驗與分析

4.1 實驗設(shè)置

為了驗證所提出的聚類算法的性能，本節(jié)將采用不同類型的數(shù)據(jù)集進(jìn)行實驗，包括：1)不同形狀和不同規(guī)模的人造數(shù)據(jù)集；2)真實數(shù)據(jù)集.同時，選擇基于代表點的聚類算法K-medoid，AP以及基于密度的聚類算法DBSCAN[23]，OPTICS[24]，KNNCLUST[25]作為對比算法，并利用指標(biāo)NMI(normalized mutual information)[26]和ARI(adjusted rand index)[27]進(jìn)行聚類效果評價，其中NMI基于信息論，ARI基于樣本對計數(shù)，二者的定義如下.

假設(shè)某一數(shù)據(jù)集包含N個樣本，Ni j表示由聚類算法產(chǎn)生的第i個簇與真實的第j個簇的契合程度，Ni和Nj分別表示所述第i個簇與第j個簇的樣本數(shù)，則：

(16)

在實驗部分，ESFSAC算法與對比算法的可調(diào)參數(shù)設(shè)置均采用網(wǎng)格搜索法進(jìn)行確定，具體網(wǎng)格設(shè)置如表1所示，所顯示的評價指標(biāo)均為最優(yōu)參數(shù)下運行50次所獲取的均值與標(biāo)準(zhǔn)差.實驗所采用的硬件環(huán)境為：Intel I5-4950 3.3 GHz×2，8 GB RAM；軟件環(huán)境為：Windows 7 64 bit，MATLAB R2012 b.

4.2 人造數(shù)據(jù)集實驗

為了驗證ESFSAC算法對具有不同形狀人造數(shù)據(jù)集的處理能力，選擇4個不同形狀的數(shù)據(jù)集進(jìn)行實驗，為了方便描述，將這4個數(shù)據(jù)集分別命名為DS1，DS2，DS3，DS4，數(shù)據(jù)集的相關(guān)屬性和分布如表2和圖1所示，數(shù)據(jù)集在進(jìn)行實驗時，全部進(jìn)行歸一化處理.圖2給出了4個人造數(shù)據(jù)集的壓縮集聚類結(jié)果以及在聚類過程中代表點從其候選集中的選擇情況，每個子圖右側(cè)矩形框中的實心圓表示聚類結(jié)束時從代表點候選集中所選擇的代表點，箭頭表示代表點的ES值沿箭頭方向逐漸增大.

Table 2 Synthetic Datasets with Different Shapes表2 不同形狀人造數(shù)據(jù)集的相關(guān)屬性

從圖2可以看出，由FRSDE所獲得的壓縮集能夠反映出原數(shù)據(jù)集的骨架結(jié)構(gòu)，結(jié)合圖1可知，剩余集中的樣本沿著其骨架結(jié)構(gòu)呈擴(kuò)散狀分布.這一現(xiàn)象符合所提出的第3個假設(shè)，也為剩余集的樣本類別標(biāo)定奠定基礎(chǔ).另外，從壓縮集聚類結(jié)果可以看出，在事先未指定類別數(shù)的前提下，所選的4種不同形狀的數(shù)據(jù)集的壓縮集從視覺角度來看均達(dá)到了幾乎完美的劃分.具體來說，在圖2(a)～(c)中，當(dāng)壓縮集聚類結(jié)束時，從代表點候選集中選擇的代表點的個數(shù)恰好與各個數(shù)據(jù)集真實類別數(shù)相同，且所選代表點均來自原數(shù)據(jù)集中密度較高的區(qū)域.這說明：1)在數(shù)據(jù)集各個簇不存在顯著密度不平衡的情況下，一般不會出現(xiàn)冗余代表點；2)通過所提出的ES值來選擇代表點是有效的，能夠在較低的系統(tǒng)開銷情況下找出各個簇內(nèi)的代表點.在圖1(d)所示的DS4中，菱形(◇)所標(biāo)記的簇與其他簇之間存在顯著密度不平衡關(guān)系，這使得密度較大簇中可能有多個樣本的ES值高于密度較小簇，即存在冗余代表點.例如在圖2(d)中，按照冗余代表點的定義，可以判斷△和?標(biāo)記的樣本(即橢圓內(nèi)的樣本)屬于冗余代表點.冗余代表點的出現(xiàn)，會增加我們從代表點候選集中選擇代表點的個數(shù)(大于真實類別數(shù))，但是并不會影響壓縮集聚類結(jié)果，因為由算法2可知，冗余代表點在被選中時，已經(jīng)通過其所在簇的真實代表點獲取類別標(biāo)簽，即使在后續(xù)過程中被選中，可以通過其標(biāo)簽狀態(tài)進(jìn)行過濾.另外，對比圖2和圖1亦可看出，壓縮集中簇之間的間隔比原數(shù)據(jù)集明顯，更易于劃分.圖3給出了K-medoid，AP，DBSCAN，KNNCLUST，OPTICS以及本文算法在DS1～DS4上的視覺劃分，同時，表3給出了NMI和ARI的評價結(jié)果.另外，由于AP，DBSCAN，KNNCLUST，OPTICS以及本文算法均為自適應(yīng)算法.因此，在表3中，用“NC”表示算法識別出的類別數(shù)，對于K-medoid而言，NC表示指定的類別數(shù)；“Par”表示算法通過網(wǎng)格搜索得到的最優(yōu)參數(shù)設(shè)置.

Fig. 2 Exemplars selecting and clustering results of reduced set for DS1-DS4圖2 DS1～DS4代表點選擇情況以及壓縮集的聚類結(jié)果

從圖3和表3中可以看出，對于非球形數(shù)據(jù)集或不平衡數(shù)據(jù)集，K-medoid和AP算法顯得無能為力，其原因是這2種算法的劃分策略均是將樣本分配給離自己最近的代表點，對于非球形數(shù)據(jù)集或不平衡數(shù)據(jù)集，顯然無法達(dá)到理想的劃分結(jié)果.DBSCAN是一種基于密度的聚類算法，它被認(rèn)為是基于圖的連通性(直接密度可達(dá))進(jìn)行樣本分配，因此能夠發(fā)現(xiàn)任意形狀的簇.但是，對于簇類邊緣稀疏的樣本，由于無法滿足直接密度可達(dá)的條件，故被當(dāng)成噪聲樣本處理，單獨劃分成一類，如圖3(c)的DS1，DS3，DS4.另外，若2個簇之間存在邊界重合的情況，易使得二者達(dá)到連通條件，被劃分成同一類別，如圖3(c)的DS2所示.KNNCLUST算法與使用密度函數(shù)尋找簇之間的“密度低谷”的密度算法不同，它通過最大化分類密度效應(yīng)和函數(shù)來確定數(shù)據(jù)點歸屬，無法較好地識別不同形狀的簇，例如圖3(d)的DS1，DS3.OPTICS算法并非對目標(biāo)數(shù)據(jù)集進(jìn)行直接劃分，而是生成一個樣本的擴(kuò)展序列，該序列反映了數(shù)據(jù)集基于密度的聚類結(jié)構(gòu)，并使用陡變量閾值來劃分序列，自動識別類結(jié)構(gòu).該算法的聚類結(jié)果可被認(rèn)為是一個類的結(jié)構(gòu)樹，其節(jié)點表示一個簇，節(jié)點的子節(jié)點表示為簇的子類.但是這種結(jié)構(gòu)無法確定一個簇是否需要繼續(xù)劃分成子類還是與其他簇進(jìn)行合并，故無法向用戶提供有價值的簇歸屬信息.

Fig. 3 Visual partitions of different algorithms for DS1-DS4圖3 不同算法在DS1～DS4上的視覺劃分

AlgorithmsDS1DS2NMIARINCParNMIARINCParK-medoid0.0100(+)(0.0085)0.0132(+)(0.0118)3K=20.4710(+)(0.0284)0.4102(+)(0.0311)3K=3AP0.4817(+)(0)0.1327(+)(0)17p=-1.10.7005(+)(0)0.4570(+)(0)7p=-1.3DBSCAN0.8850(+)(0)0.9332(0)3minPts=4.00eps=0.0280.7666(+)(0)0.7137(+)(0)2minPts=37eps=0.05KNNCLUST0.4480(+)(0)0.1886(+)(0)11k=1170.8188(+)(0)0.8389(+)(0)3k=87OPTICS0.0032(+)(0)0.0039(+)(0)2minPts=99eps=0.010.0132(+)(0)0.0256(+)(0)3minPts=86eps=0.011ESFSAC0.9300(0.0162)0.9657(0.0094)2ξ=0.13σ=10-3ε=10-40.9540(0.0141)0.9741(0.0081)3ξ=0.13σ=10-3ε=10-4AlgorithmsDS3DS4NMIARINCParNMIARINCParK-medoid0.0115(+)(0.0092)0.0057(+)(0.0110)2K=20.6943(+)(0.0306)0.5054(+)(0.0899)5K=5AP0.5547(+)(0)0.3335(+)(0)5p=-0.580.7359(+)(0)0.4769(+)(0)7p=-37.00DBSCAN0.7949(+)(0)0.8672(+)(0)3minPts=3eps=0.0400.9517(0)0.9479(+)(0)6minPts=10eps=0.059KNNCLUST0.3023(+)(0)0.1532(+)(0)4k=90.9647(0)0.9807(0)5k=380OPTICS0.7631(+)(0)0.8521(+)(0)3minPts=9eps=0.0040.9139(+)(0)0.9480(+)(0)6minPts=23eps=0.015ESFSAC0.8763(0.0094)0.9343(0.0068)2ξ=0.14σ=10-3ε=10-30.9677(0.0083)0.9857(0.0037)5ξ=0.22σ=10-3ε=10-3

Notes:“(+)” represents that the improvement of the proposed ESFSAC is significant at 5% significance level, i.e.;p-value is less than 0.05 compared with the comparison algorithms; data in parenthesis represent standard deviation.

本文所提出的聚類算法對DS1～DS4達(dá)到了近乎完美的劃分，并且能夠正確地識別出簇的個數(shù)，其原因可以歸結(jié)為4個方面：

1) 所提出的用于評價樣本成為簇內(nèi)代表點可能性的ES值，能夠較為準(zhǔn)確地發(fā)現(xiàn)簇內(nèi)代表點，同時結(jié)合自適應(yīng)的聚類策略，這成為本文算法成功的關(guān)鍵所在；

2) 原始數(shù)據(jù)集經(jīng)過FRSDE壓縮之后，獲取了反映原始樣本骨干結(jié)構(gòu)的壓縮集，這使得原始數(shù)據(jù)集中簇之間的間隔在壓縮集中變得更加明顯，也更容易劃分，這亦為本文所提算法能夠正確發(fā)現(xiàn)簇個數(shù)的主要原因，這一點通過圖1和圖2的對比，更加形象地體現(xiàn)出來；

3) 在壓縮集類別標(biāo)定策略上，摒棄了傳統(tǒng)的劃分方法(將樣本分配給離其最近的代表點)，利用鄰域傳播的策略，沿著數(shù)據(jù)流方向進(jìn)行樣本標(biāo)簽傳播，這使得所提算法能夠適應(yīng)不同形狀的數(shù)據(jù)集；

4) 由于剩余集中的樣本沿著其骨架結(jié)構(gòu)(壓縮集)呈擴(kuò)散狀分布，故在剩余集類別標(biāo)定策略上，仍然利用鄰域傳播將壓縮集中樣本類別標(biāo)簽傳遞至剩余集，這種標(biāo)定策略不會破壞在壓縮集聚類過程中所形成的簇結(jié)構(gòu).

利用壓縮集來估計樣本的ES值以及在剩余集樣本標(biāo)定過程中抽樣加速策略的使用，對于提高本文所提算法的效率有著非常大的幫助，接下來，通過不同規(guī)模的數(shù)據(jù)集來驗證二者所帶來的加速效果.按照圖4中的概率分布圖[10]生成10個不同規(guī)模大小的數(shù)據(jù)集DS5.1～DS5.10，樣本的規(guī)模S分別為1 500，3 000，8 000，12 000，22 000，44 000，88 000，180 000，260 000，340 000.對于DS5.1～DS5.4，直接選擇所有的樣本參與ES值的計算；而對于DS5.5～DS5.10，利用FRSDE對原始數(shù)據(jù)集進(jìn)行壓縮，選擇壓縮集參與ES值的計算.

Fig. 4 The probability distribution of DS5.1-DS5.10圖4 DS5.1～DS5.10樣本概率分布圖

為了驗證既定的目標(biāo)，分別統(tǒng)計EES，RSC，RMSC的運行時間，結(jié)果如表4所示:

Table 4 CPU Seconds of Three Components of the Proposed ESFSAC

Note: Data in parenthesis represent standard deviation.

在表4中，由于DS5.1～DS5.4是所有樣本參與ES值的計算，故在RSC模塊，所有樣本已全部標(biāo)定完成，無RMSC過程，在表4中以“空白”表示，另外，表4中的“0.00”表示大于0的一個非常小的數(shù).從表4中加粗的兩行可以看出，對于DS5.5，由于是其壓縮集參與ES值計算，在數(shù)據(jù)集規(guī)模顯著高于DS5.4的情況下，EES過程的執(zhí)行時間仍然低于DS5.4，這充分說明通過壓縮集來進(jìn)行ES值計算能顯著提高代表點尋找速度.另外，由于通過FRSDE獲取的壓縮集在規(guī)模上已經(jīng)遠(yuǎn)小于原數(shù)據(jù)集，故在樣本分配階段，其時間主要消耗在RMSC模塊，而在RMSC模塊，采用了抽樣加速策略，能保證以較快的速度完成剩余集樣本的分配.為了進(jìn)一步突出ESFSAC算法的聚類速度優(yōu)勢，圖5給出了ESFSAC與其他對比算法在DS5.1～DS5.10上的運行時間.由于AP算法的算法復(fù)雜度較高，當(dāng)樣本數(shù)超過20 000時，其尋參時間超出了可接受范圍，故僅給出DS5.1～DS5.4的運行結(jié)果.從圖5中可以看出，相比所選的對比算法而言，本文所提的聚類算法在運行時間上具有一定的優(yōu)勢，正如前面所述，這得益于規(guī)模較小的壓縮集代替整個樣本參與ES值計算以及剩余集樣本標(biāo)定時的抽樣加速.

Fig. 5 Clustering performance in terms of CPU seconds for ten datasets with different sizes圖5 不同算法在DS5.1～DS5.10上運行時間比較

4.3 UCI數(shù)據(jù)集實驗

為了驗證本文所提算法在真實數(shù)據(jù)集上的表現(xiàn)，選擇6個來自UCI*http://archive.ics.uci.edu/ml/index.html的數(shù)據(jù)集進(jìn)行實驗，所選數(shù)據(jù)集的相關(guān)屬性如表5所示，數(shù)據(jù)集在進(jìn)行實驗時全部進(jìn)行歸一化處理.

Table 5 UCI Datasets表5 UCI數(shù)據(jù)集的相關(guān)屬性

ESFSAC算法與5個對比算法在UCI數(shù)據(jù)集上運行的結(jié)果如表6所示，由于AP算法在shuttle和skin上以及DBSCAN和OPTICS在skin上無法在可容忍的時間范圍內(nèi)進(jìn)行參數(shù)尋優(yōu)，故在表6中以“空白”表示.圖6以可視化的方式突出各個算法在評價指標(biāo)NMI和ARI上的差異.

Table 6 Clustering Results of Different Algorithms for UCI Datasets表6 不同算法在UCI數(shù)據(jù)集上的聚類結(jié)果

Notes: “(+)” represents that the improvement of the proposed ESFSAC is significant at 5% significance level, i.e.;p-value is less than 0.05 compared with the comparison algorithms; data in parenthesis represent standard deviation.

Fig. 6 Comparison of clustering results on UCI dataset for different algorithms圖6 不同算法在UCI數(shù)據(jù)集上聚類精度比較

除了在Waveform數(shù)據(jù)集上，ESFSAC算法的NMI指標(biāo)低于OPTICS外，其他均優(yōu)于比較算法，故總體來說具有一定的優(yōu)勢.另外，AP，DBSCAN，KNNCLUST，OPTICS算法由于不包含任何隨機(jī)過程，故這些算法每次運行的NMI和ARI均相同，因此標(biāo)準(zhǔn)差為0;K-medoid算法和ESFSAC算法均包含隨機(jī)過程，但從實驗結(jié)果來看，本文算法的標(biāo)準(zhǔn)差總體來說小于K-medoid算法，這說明本文算法較K-medoid算法穩(wěn)定.

4.4 參數(shù)敏感性分析

本文所提算法的重要參數(shù)包括3個，分別為FRSDE中的逼近參數(shù)ε、壓縮集和剩余集類別標(biāo)定時使用的距離閾值ξ以及高斯核參數(shù)σ.對于高斯核參數(shù)，可以通過交叉驗證策略得到，這里就不做過多的闡述，重點分析逼近參數(shù)和距離閾值參數(shù).

Deng等人[16]指出，F(xiàn)RSDE的逼近速度和逼近精度均受ε影響，較大的ε可以取得較好的逼近速度，但卻以犧牲逼近精度為代價.如何在逼近速度和逼近精度之間尋找折中的參數(shù)顯得非常重要.圖7給出了在不同逼近參數(shù)ε下本文所提算法在DS4，Iris數(shù)據(jù)集上的聚類結(jié)果(僅給出NMI指標(biāo)，ARI類似).這里需要注意的是，由于距離閾值ξ的設(shè)定與逼近參數(shù)ε之間存在相關(guān)性，較大ε往往需要較大的ξ，這是因為較大ε會導(dǎo)致較為粗放的逼近和較高的壓縮率(壓縮集規(guī)模和原數(shù)據(jù)集規(guī)模的比值)，換言之，較大的ε會使得壓縮集變得更加稀疏，樣本間距更大，因此需要更大的距離閾值.故為了突出ε的影響，對于不同的ε，設(shè)定最優(yōu)的距離閾值.如對于DS4數(shù)據(jù)集，ξ的最優(yōu)值分別為0.22，0.22，0.22，0.22，0.22，0.22，0.22，0.27，0.27，0.3，0.34;對于Iris數(shù)據(jù)集，ξ的最優(yōu)值分別為0.17，0.17，0.17，0.17，0.18，0.18，0.18，0.18，0.20，0.3，0.34.對這2個數(shù)據(jù)集，最優(yōu)高斯核參數(shù)均為10-3.

Fig. 7 The NMI values on two datasets with different approximation parameters 圖7 逼近參數(shù)對聚類指標(biāo)NMI的影響

Fig. 8 The reduced set of DS4 with ε=1圖8 DS4在逼近參數(shù)ε=1時的壓縮集

根據(jù)Deng等人[16]的建議，ε=10-6對于FRSDE來說是最佳選擇，但是從圖7中可以看出，10-5，10-4，10-3甚至10-2均能保證較好的聚類精度，這是因為本文算法所需要的壓縮集無需精確逼近原數(shù)據(jù)集，只需反映原數(shù)據(jù)集的骨架即可.隨著ε的進(jìn)一步增大，壓縮集分布已經(jīng)“失真”，例如圖8給出了DS4在ε=1時的壓縮集，已經(jīng)無法反映原數(shù)據(jù)集的骨干結(jié)構(gòu).

對于距離閾值ξ的設(shè)定，與數(shù)據(jù)集樣本分布的疏密程度有關(guān)，通過大量實驗，我們給出該參數(shù)的估計原則：

(18)

其中，Nr表示壓縮集的規(guī)模，NC表示期望劃分的類別數(shù)，Dis(xi,xj)表示樣本xi和xj之間的距離，通過該原則可以計算出ξ的估計值，在尋優(yōu)過程中在該估計值的附近進(jìn)行搜索尋優(yōu).圖9給出了不同的距離閾值對聚類精度的影響(DS4:ε=10-3，σ=10-3;Iirs:ε=10-4，σ=10-3)，可以看出，本文算法的最優(yōu)結(jié)果對該參數(shù)比較敏感.

Fig. 9 The NMI values on two datasets with different distance thresholds圖9 距離閾值對聚類指標(biāo)NMI的影響

5 結(jié) 論

本文在已有的工作基礎(chǔ)上，提出了一種基于代表點評分策略的快速自適應(yīng)聚類算法，該算法的提出基于3個重要假設(shè).根據(jù)前2個假設(shè)，提出了簇代表點的評分策略來評價樣本成為代表點的可能性，并從理論上論證了該策略的合理性；根據(jù)第3個假設(shè)，構(gòu)建了一種剩余集樣本標(biāo)定策略，同時，為了提高效率，引入抽樣方法.通過在人工數(shù)據(jù)集上的實驗，證實了該算法對于不同形狀數(shù)據(jù)集的有效性，同時能夠處理大規(guī)模數(shù)據(jù)集，另外，通過真實數(shù)據(jù)集證實了該算法的實際應(yīng)用能力.

所提的算法仍然存在一定的后續(xù)研究的空間，例如對于少量離群點，經(jīng)過FRSDE后，無法保留在壓縮集中，在剩余集聚類時，無法在有效的距離閾值范圍內(nèi)進(jìn)行標(biāo)定.

[1] Ying Wenhao, Xu Min, Wang Shitong, et al. Fast adaptive clustering by synchronization on large scale datasets[J]. Journal of Computer Research and Development, 2014, 51(4): 707-720 (in Chinese)

(應(yīng)文豪, 許敏, 王士同, 等. 在大規(guī)模數(shù)據(jù)集上進(jìn)行快速自適應(yīng)同步聚類[J]. 計算機(jī)研究與發(fā)展, 2014, 51(4): 707-720)

[2] Bi Anqi, Dong Aimei, Wang Shitong. A dynamic data stream clustering algorithm based on probability and exemplar[J]. Journal of Computer Research and Development, 2016, 53(5): 1029-1042 (in Chinese)

(畢安琪, 董愛美, 王士同. 基于概率和代表點的數(shù)據(jù)流動態(tài)聚類算法[J]. 計算機(jī)研究與發(fā)展, 2016, 53(5): 1029-1042)

[3] Wang Jie, Liang Jiye, Zheng Wenping. A graph clustering method for detecting protein complexes[J]. Journal of Computer Research and Development, 2015, 52(8): 1784-1793 (in Chinese)

(王杰, 梁吉業(yè), 鄭文萍. 一種面向蛋白質(zhì)復(fù)合體檢測的圖聚類方法[J]. 計算機(jī)研究與發(fā)展, 2015, 52(8): 1784-1793)

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

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

[6] 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

[7] 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

[8] Zhou Jin, Pan Yuqi, Chen C L P, et al.K-medoids method based on divergence for uncertain data clustering[C] //Proc of IEEE Int Conf on Systems, Man, Cybernetics. Piscataway, NJ: IEEE, 2016: 2671-2674

[9] Krishnapuram R, Joshi A, Nasraoui O, et al. Low-complexity fuzzy relational clustering algorithms for Web mining[J]. IEEE Trans on Fuzzy Systems, 2001, 9(4): 595-607

[10] Rodriguez A, Laio A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496

[11] Xie Juanying, Gao Hongchao, Xie Weixing.K-nearest neighbors optimized clustering algorithm by fast search and finding the density peaks of a dataset[J]. Scientia Sinica: Informationis, 2016, 46(2): 258-280 (in Chinese)

(謝娟英, 高紅超, 謝維信.K近鄰優(yōu)化的密度峰值快速搜索聚類算法[J]. 中國科學(xué): 信息科學(xué), 2016, 46(2): 258-280)

[12] Hoti F. On estimation of a probability density function and mode[J]. Annals of Mathematical Statistics, 2003, 33(3): 1065-1076

[13] Catlett J. Megainduction: Machine learning on very large databases[C]//Proc of the 31st Int Conf on VLDB’05. New York: ACM, 1991: 23-45

[14] Lewis D D, Catlett J. Heterogeneous uncertainty sampling for supervised learning[C]//Proc of the 8th Int Conf on Machine Learning. San Francisco: Morgan Kaufmann 1994: 148-156

[15] Girolami M, He Chao. Probability density estimation from optimally condensed data samples[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2003, 25(10): 1253-1264

[16] Deng Zhaohong, Chung Fu-lai, Wang Shitong. FRSDE: Fast reduced set density estimator using minimal enclosing ball approximation[J]. Pattern Recognition, 2008, 41(4): 1363-1372

[17] Kollios G, Gunopulos D, Koudas N, et al. Efficient biased sampling for approximate clustering and outlier detection in large data sets[J]. IEEE Trans on Knowledge and Data Engineering, 2003, 15(5): 1170-1187

[18] Tsang I W, Kwok J T, Cheung P M, et al. Core vector machines: Fast SVM training on very large data sets[J]. Journal of Machine Learning Research, 2005, 6(1): 363-392

[19] Parzen E. On estimation of probability density function and mode[J]. Annals of Mathematical Statistics, 1961, 33(3): 1065-1076

[20] Goldberger J, Gordon S, Greenspan H. An efficient image similarity measure based on approximations of KL-divergence between two Gaussian mixtures[C] //Proc of IEEE Int Conf on Computer Vision. Los Alamitos, CA: IEEE Computer Society, 2003: 487-493

[21] Smola A J, Sch?kopf B. Sparse greedy matrix approximation for machine learning[C]//Proc of the 17th Int Conf on Machine Learning. San Francisco: Morgan Kaufmann, 2000: 911-918

[22] Bādoiu M, Har-Peled S, Indyk P. Approximate clustering via core-sets[C] //Proc of the 3rd-4th Annual ACM Symp on Theory of Computing. New York: ACM, 2002: 250-257

[23] Ester M, Kriegel H P, Sander J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C] //Proc of the 2nd Int Conf on Knowledge Discovery and Data Mining. Menlo Park, CA: AAAI, 1996: 226-231

[24] Ankerst M, Breunig M M, Kriegel H P, et al. OPTICS: Ordering points to identify the clustering structure[C] //Proc of the 1999 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 1999: 49-60

[25] Tran T N, Wehrens R, Buydens L M C. KNN-kernel density-based clustering for high-dimensional multivariate data[J]. Computational Statistics and Data Analysis, 2006, 51(2): 513-525

[26] Jiang Yizhang, Chung Fu-lai, Wang Shitong, et al. Collaborative fuzzy clustering from multiple weighted views[J]. IEEE Trans on Cybernetics, 2014, 45(4): 688-701

[27] Qian Pengjiang, Chung Fu-lai, Wang Shitong, et al. Fast Graph-based relaxed clustering for large data sets using minimal enclosing ball[J]. IEEE Trans on Cybernetics, 2012, 42(3): 672-87