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

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

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

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

(155297131@qq.com)

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

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

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

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

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

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

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

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

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

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

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

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

1.1 RSDE

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

(1)

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

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

1.2 FRSDE

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

(2)

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

(3)

在式(3)中，

(4)

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

(5)

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

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

(6)

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

(7)

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

2 代表點(diǎn)評(píng)分策略

2.1 代表點(diǎn)分值

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

(8)

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

(9)

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

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

2.2 代表點(diǎn)分值合理性分析

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

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

(10)

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

(11)

證畢.

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

(13)

(14)

(15)

證畢.

3 ESFSAC算法描述

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

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

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

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

3.1 代表點(diǎn)評(píng)分

本節(jié)通過ES值來評(píng)估數(shù)據(jù)集中每個(gè)樣本成為簇內(nèi)代表點(diǎn)的可能性，并根據(jù)ES值形成代表點(diǎn)候選集.另外，值得注意的是，在評(píng)估樣本的ES值時(shí)，參與計(jì)算的是由FRSDE得到的原數(shù)據(jù)集的子集，由于其規(guī)模遠(yuǎn)小于原數(shù)據(jù)集，故相對(duì)于PW來說，其評(píng)估速度有較大的提升.本節(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. 估算代表點(diǎn)分值(evaluate exemplar score， EES).

輸出：代表點(diǎn)候選集Dc.

過程：

① 初始化ES集E=?，初始化代表點(diǎn)候選集Dc=?；

② Fori=1 toN

Fork=1 toNr

End For

E=E∪{esi};

End For

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

3.2 壓縮集聚類

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

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

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

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

過程：

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

Fori=1 toN

Continue;

End If

④ WhileDnb≠?

For eachyinDnb

計(jì)算Nbξ(y,Dr)在Labelr中將對(duì)應(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個(gè)假設(shè)認(rèn)為，剩余集中的樣本圍繞著代表點(diǎn)和已經(jīng)獲得類別標(biāo)簽的壓縮集分布，故仍然可以采用ξ鄰域類別標(biāo)簽傳遞的方法將壓縮集樣本的類別傳遞至剩余集樣本.但是，隨著已獲得標(biāo)簽的樣本逐漸增多，尤其當(dāng)數(shù)據(jù)集規(guī)模較大時(shí)，這種傳遞策略效率低下.因此，為了提高剩余集樣本類別分配的效率，采用Smola等人在文獻(xiàn)[21]中提出的抽樣方法，當(dāng)已經(jīng)獲得類別標(biāo)簽的樣本數(shù)量達(dá)到一定的閾值時(shí)(本文設(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表示一個(gè)抽樣過程；Labelrm是一個(gè)標(biāo)簽向量，代表剩余集中樣本的類別標(biāo)簽；Drm表示剩余集樣本集合.整個(gè)算法過程可以分為2個(gè)步驟：在步驟①中，初始化標(biāo)簽向量Labelrm以及獲取剩余集樣本集合；在步驟②中，Ds是一個(gè)臨時(shí)集合，存儲(chǔ)標(biāo)簽傳播的“種子”樣本，在已標(biāo)記樣本數(shù)目小于等于1 000時(shí)“種子”即為所有標(biāo)記樣本，當(dāng)已標(biāo)記樣本數(shù)目大于1 000時(shí)啟動(dòng)抽樣過程，然后不斷將“種子”標(biāo)簽傳播至未標(biāo)記樣本，直到所有樣本均獲得標(biāo)簽.

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

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)設(shè)置

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

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

(16)

在實(shí)驗(yàn)部分，ESFSAC算法與對(duì)比算法的可調(diào)參數(shù)設(shè)置均采用網(wǎng)格搜索法進(jìn)行確定，具體網(wǎng)格設(shè)置如表1所示，所顯示的評(píng)價(jià)指標(biāo)均為最優(yōu)參數(shù)下運(yùn)行50次所獲取的均值與標(biāo)準(zhǔn)差.實(shí)驗(yà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ù)集實(shí)驗(yàn)

為了驗(yàn)證ESFSAC算法對(duì)具有不同形狀人造數(shù)據(jù)集的處理能力，選擇4個(gè)不同形狀的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，為了方便描述，將這4個(gè)數(shù)據(jù)集分別命名為DS1，DS2，DS3，DS4，數(shù)據(jù)集的相關(guān)屬性和分布如表2和圖1所示，數(shù)據(jù)集在進(jìn)行實(shí)驗(yàn)時(shí)，全部進(jìn)行歸一化處理.圖2給出了4個(gè)人造數(shù)據(jù)集的壓縮集聚類結(jié)果以及在聚類過程中代表點(diǎn)從其候選集中的選擇情況，每個(gè)子圖右側(cè)矩形框中的實(shí)心圓表示聚類結(jié)束時(shí)從代表點(diǎn)候選集中所選擇的代表點(diǎn)，箭頭表示代表點(diǎn)的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個(gè)假設(shè)，也為剩余集的樣本類別標(biāo)定奠定基礎(chǔ).另外，從壓縮集聚類結(jié)果可以看出，在事先未指定類別數(shù)的前提下，所選的4種不同形狀的數(shù)據(jù)集的壓縮集從視覺角度來看均達(dá)到了幾乎完美的劃分.具體來說，在圖2(a)～(c)中，當(dāng)壓縮集聚類結(jié)束時(shí)，從代表點(diǎn)候選集中選擇的代表點(diǎn)的個(gè)數(shù)恰好與各個(gè)數(shù)據(jù)集真實(shí)類別數(shù)相同，且所選代表點(diǎn)均來自原數(shù)據(jù)集中密度較高的區(qū)域.這說明：1)在數(shù)據(jù)集各個(gè)簇不存在顯著密度不平衡的情況下，一般不會(huì)出現(xiàn)冗余代表點(diǎn)；2)通過所提出的ES值來選擇代表點(diǎn)是有效的，能夠在較低的系統(tǒng)開銷情況下找出各個(gè)簇內(nèi)的代表點(diǎn).在圖1(d)所示的DS4中，菱形(◇)所標(biāo)記的簇與其他簇之間存在顯著密度不平衡關(guān)系，這使得密度較大簇中可能有多個(gè)樣本的ES值高于密度較小簇，即存在冗余代表點(diǎn).例如在圖2(d)中，按照冗余代表點(diǎn)的定義，可以判斷△和?標(biāo)記的樣本(即橢圓內(nèi)的樣本)屬于冗余代表點(diǎn).冗余代表點(diǎn)的出現(xiàn)，會(huì)增加我們從代表點(diǎn)候選集中選擇代表點(diǎn)的個(gè)數(shù)(大于真實(shí)類別數(shù))，但是并不會(huì)影響壓縮集聚類結(jié)果，因?yàn)橛伤惴?可知，冗余代表點(diǎn)在被選中時(shí)，已經(jīng)通過其所在簇的真實(shí)代表點(diǎn)獲取類別標(biāo)簽，即使在后續(xù)過程中被選中，可以通過其標(biāo)簽狀態(tài)進(jìn)行過濾.另外，對(duì)比圖2和圖1亦可看出，壓縮集中簇之間的間隔比原數(shù)據(jù)集明顯，更易于劃分.圖3給出了K-medoid，AP，DBSCAN，KNNCLUST，OPTICS以及本文算法在DS1～DS4上的視覺劃分，同時(shí)，表3給出了NMI和ARI的評(píng)價(jià)結(jié)果.另外，由于AP，DBSCAN，KNNCLUST，OPTICS以及本文算法均為自適應(yīng)算法.因此，在表3中，用“NC”表示算法識(shí)別出的類別數(shù)，對(duì)于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代表點(diǎn)選擇情況以及壓縮集的聚類結(jié)果

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

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.

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

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

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

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

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

利用壓縮集來估計(jì)樣本的ES值以及在剩余集樣本標(biāo)定過程中抽樣加速策略的使用，對(duì)于提高本文所提算法的效率有著非常大的幫助，接下來，通過不同規(guī)模的數(shù)據(jù)集來驗(yàn)證二者所帶來的加速效果.按照?qǐng)D4中的概率分布圖[10]生成10個(gè)不同規(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.對(duì)于DS5.1～DS5.4，直接選擇所有的樣本參與ES值的計(jì)算；而對(duì)于DS5.5～DS5.10，利用FRSDE對(duì)原始數(shù)據(jù)集進(jìn)行壓縮，選擇壓縮集參與ES值的計(jì)算.

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

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

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

4.3 UCI數(shù)據(jù)集實(shí)驗(yàn)

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

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

ESFSAC算法與5個(gè)對(duì)比算法在UCI數(shù)據(jù)集上運(yùn)行的結(jié)果如表6所示，由于AP算法在shuttle和skin上以及DBSCAN和OPTICS在skin上無法在可容忍的時(shí)間范圍內(nèi)進(jìn)行參數(shù)尋優(yōu)，故在表6中以“空白”表示.圖6以可視化的方式突出各個(gè)算法在評(píng)價(jià)指標(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)勢(shì).另外，AP，DBSCAN，KNNCLUST，OPTICS算法由于不包含任何隨機(jī)過程，故這些算法每次運(yùn)行的NMI和ARI均相同，因此標(biāo)準(zhǔn)差為0;K-medoid算法和ESFSAC算法均包含隨機(jī)過程，但從實(shí)驗(yàn)結(jié)果來看，本文算法的標(biāo)準(zhǔn)差總體來說小于K-medoid算法，這說明本文算法較K-medoid算法穩(wěn)定.

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

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

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

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

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

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

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

(18)

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

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

5 結(jié) 論

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

所提的算法仍然存在一定的后續(xù)研究的空間，例如對(duì)于少量離群點(diǎn)，經(jīng)過FRSDE后，無法保留在壓縮集中，在剩余集聚類時(shí)，無法在有效的距離閾值范圍內(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ì)算機(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)

(畢安琪, 董愛美, 王士同. 基于概率和代表點(diǎn)的數(shù)據(jù)流動(dòng)態(tài)聚類算法[J]. 計(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ù)合體檢測(cè)的圖聚類方法[J]. 計(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]. 中國(guó)科學(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