宋 鵬，葛洪偉+

1.江南大學(xué) 人工智能與計(jì)算機(jī)學(xué)院，江蘇 無錫 214122

2.江蘇省模式識(shí)別與計(jì)算智能工程實(shí)驗(yàn)室（江南大學(xué)），江蘇 無錫 214122

聚類是機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘中的一種基本方法，旨在把一些數(shù)據(jù)劃分成不同的簇，發(fā)現(xiàn)數(shù)據(jù)內(nèi)部的隱藏結(jié)構(gòu)，要求每個(gè)簇內(nèi)部的相似性高，不同簇之間的相似性低。聚類是一個(gè)熱門的研究領(lǐng)域，也在現(xiàn)實(shí)生活中被廣泛應(yīng)用，扮演著很重要的角色，如機(jī)器學(xué)習(xí)[1]、模式識(shí)別[2]、圖像處理[3]、生物信息學(xué)[4]、蛋白質(zhì)分析[5]、微陣列分析[6]和社交網(wǎng)絡(luò)[7]等。到目前為止，已經(jīng)有很多專家提出了各種聚類算法，可以把這些算法大致分成四類：基于目標(biāo)的方法[8]、基于模型的方法[9-10]、基于層次的方法[11]和基于密度的方法[12-15]。

近年來，基于密度的聚類方法受到了研究者的廣泛關(guān)注。這些方法假設(shè)簇分布在高密度區(qū)域，可以識(shí)別具有任意形狀的簇，并且需要最少的領(lǐng)域知識(shí)就可以將數(shù)據(jù)劃分成不同的簇。DBSCAN（densitybased algorithm for discovering clusters in large spatial databases with noise）[16]是一種著名的基于密度的聚類方法，該方法不需要對(duì)數(shù)據(jù)的分布做出任何假設(shè)便可以估計(jì)出數(shù)據(jù)的密度，并且具有識(shí)別任意形狀聚類、可以處理噪聲和離群點(diǎn)、不需要在聚類之前人工預(yù)先設(shè)定聚類數(shù)目等優(yōu)點(diǎn)。然而，這種方法存在不少缺陷，例如：它不能處理密度不均勻的數(shù)據(jù)集；對(duì)參數(shù)敏感，改變參數(shù)值就會(huì)產(chǎn)生不同的聚類結(jié)果；還有無法識(shí)別出具有重疊密度的簇。為了解決這些問題，一些優(yōu)化算法已經(jīng)被提出，例如：DVBSCAN（density based algorithm for discovering density varied clusters in large spatial databases）[17]、VDBSCA（varied density based spatial clustering of applications with noise）[18]和近些年在Science上提出的密度峰值聚類算法（density peaks clustering，DPC）[19]。該算法與其他方法不同，可以快速識(shí)別非球形團(tuán)簇，并受到了廣泛關(guān)注。DPC的主要思想是簇中心的密度比其相鄰的數(shù)據(jù)點(diǎn)密度高，假設(shè)聚類中心與密度較高的點(diǎn)的距離相對(duì)較大。對(duì)于每個(gè)數(shù)據(jù)點(diǎn)，首先計(jì)算局部密度和基于最小密度的距離，然后繪制二維決策圖，再將具有較大局部密度和最小基于密度的距離的數(shù)據(jù)點(diǎn)識(shí)別為聚類中心，最后將數(shù)據(jù)點(diǎn)分配到與其密度較高的最近鄰相同的簇。與其他聚類方法相比，DPC 不需要指定預(yù)定義的聚類數(shù)目，不需要迭代，能節(jié)省聚類時(shí)間。但是，DPC的參數(shù)截止距離的選取對(duì)聚類結(jié)果有很大的影響，并且在識(shí)別出密度峰值后，將每個(gè)點(diǎn)分配給密度較高的最近鄰的策略可能會(huì)導(dǎo)致“鏈?zhǔn)椒磻?yīng)”。

為解決這些問題，許多專家做了改進(jìn)工作，如DPCKNN（study on density peaks clustering based on Knearest neighbors and principal component analysis）[20]在密度峰值聚類中引入最近鄰的思想計(jì)算局部密度，并且使用主成分分析（principal component analysis，PCA）方法來處理高維數(shù)據(jù)。但是該方法不能識(shí)別具有非球形形狀的簇和識(shí)別重疊的簇。DPC-GD（density peaks clustering using geodesic distances）算法[21]是測地距離與DPC 算法相結(jié)合，有效地處理具有復(fù)雜形狀或多流形結(jié)構(gòu)的數(shù)據(jù)。然而，該算法不能識(shí)別扭曲、折疊或彎曲的簇，并且需要大量的計(jì)算資源?；趧?dòng)態(tài)圖的密度峰值聚類標(biāo)簽傳播算法（dynamic graph-based label propagation for density peaks clustering，DPC-DLP）[22]考慮了實(shí)例間的相關(guān)性和數(shù)據(jù)的局部結(jié)構(gòu)，采用了一種新的基于動(dòng)態(tài)圖的標(biāo)簽傳播方法。但是該算法需要設(shè)置的參數(shù)太多，嚴(yán)重影響在實(shí)際使用中的效果，并且算法在每次迭代時(shí)都會(huì)使用標(biāo)簽數(shù)據(jù)，當(dāng)簇骨干或者在標(biāo)簽傳播過程中出現(xiàn)錯(cuò)誤時(shí)，會(huì)把這個(gè)錯(cuò)誤擴(kuò)大化，最終導(dǎo)致無法產(chǎn)生正確的聚類結(jié)果。另外，當(dāng)?shù)螖?shù)過多時(shí)，會(huì)出現(xiàn)聚類效果惡化的情況。

針對(duì)上述問題，本文提出了一種最近鄰的密度峰值聚類標(biāo)簽傳播算法（nearest neighbor label propagation for density peak clustering，DPC-NLP）。本文提出的算法采用最近鄰傳播標(biāo)簽，可以在聚類的局部和非線性的情況下取得良好的效果，近似流形結(jié)構(gòu)，充分考慮數(shù)據(jù)間的結(jié)構(gòu)情況，并在分配的過程中不斷更新數(shù)據(jù)的狀態(tài)，確保利用更多的信息提高分配的正確率。實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有的一些算法相比，具有良好的性能。

1 相關(guān)工作介紹

1.1 DPC-DLP算法

DPC-DLP算法[22]的核心思想是先在聚類中心附近形成簇骨干，并標(biāo)記成和聚類中心相同的標(biāo)簽，最后使用基于圖的標(biāo)簽傳播方法將標(biāo)簽傳播到剩余點(diǎn)形成最終的聚類。基于圖的動(dòng)態(tài)標(biāo)簽傳播方法的主要思想基于這樣的假設(shè)：如果兩個(gè)樣本在輸入數(shù)據(jù)空間中具有較高的相似性，那么它們在標(biāo)簽空間中也很有可能具有很高的相似性。通過這種方法，可以將標(biāo)簽傳播到其相鄰的節(jié)點(diǎn)上，直到所有的節(jié)點(diǎn)都有標(biāo)簽。也可以說成把有標(biāo)簽數(shù)據(jù)作為監(jiān)督源，通過無標(biāo)簽數(shù)據(jù)推出標(biāo)簽。

首先輸入數(shù)據(jù)由加權(quán)圖G=(V,E,W)表示，其中V對(duì)應(yīng)于所有樣本X={x1,x2,…,xn}，E是一組邊，W是[0,1]范圍內(nèi)的非負(fù)對(duì)稱權(quán)值矩陣，表示頂點(diǎn)xi、xj之間的相似性，定義如下：

其中，d(xi,xj)是歐式距離度量，μ和σ是超參數(shù)，σ的定義采用自適應(yīng)核大小，利用K近鄰的平均距離，如下所示：

Avg({kNNd(xi),kNNd(xj)})表示xi、xj之間的平均距離，k和b都是超參數(shù)，通過實(shí)驗(yàn)獲得。

然后建立基于K近鄰的圖，其中每個(gè)節(jié)點(diǎn)只連接到它的鄰居，權(quán)重值定義如下：

然后將權(quán)重值標(biāo)準(zhǔn)化，在圖上定義一個(gè)轉(zhuǎn)移矩陣，如下所示：

其中，Pi,j表示從節(jié)點(diǎn)xi和xj的轉(zhuǎn)移概率，。P歸一化后是不對(duì)稱的，但它涵蓋了數(shù)據(jù)空間的結(jié)構(gòu)信息。

最后使用半監(jiān)督在圖中進(jìn)行標(biāo)簽傳播。將數(shù)據(jù)點(diǎn)分為有標(biāo)記點(diǎn)和無標(biāo)記點(diǎn)，有標(biāo)記點(diǎn)就是之前的核心點(diǎn)（根據(jù)聚類中心形成的簇骨干），其余點(diǎn)為未標(biāo)記點(diǎn)。將標(biāo)簽矩陣定義為Y0=[Yl:Yu]∈Rn×c，Yl是簇的標(biāo)記矩陣，Yu是未標(biāo)記矩陣。對(duì)簇成員使用二進(jìn)制標(biāo)記，如果xi屬于第k個(gè)簇，那么=1，否則就為0。使用的標(biāo)簽傳播是一種半監(jiān)督（semi-supervised learning，SSL）方法，通過多次迭代將數(shù)據(jù)的局部結(jié)構(gòu)（即轉(zhuǎn)移矩陣P）與實(shí)例之間的相關(guān)性(YYT)相結(jié)合，將標(biāo)簽分配給未標(biāo)記的實(shí)例。在每次迭代中，未標(biāo)記的數(shù)據(jù)點(diǎn)的標(biāo)簽將獲得更新，如下所示：

其中，Yt是標(biāo)簽矩陣，F(xiàn)t是融合圖，定義如下：

其中，F(xiàn)t表示實(shí)例YYT和控制相關(guān)率α的關(guān)系。在每次迭代中，Y使用不同的標(biāo)簽，因此需要按下式重置Y。

1.2 DPC-DLP算法缺陷分析

基于圖的動(dòng)態(tài)標(biāo)簽傳播算法考慮了標(biāo)簽空間的相關(guān)性，并以圖的形式進(jìn)行傳播，最終得到了真實(shí)有效的標(biāo)簽。相比其他的聚類算法具有良好的效果，但是它在進(jìn)行標(biāo)簽傳播的時(shí)候需要設(shè)置的參數(shù)太多，嚴(yán)重影響在實(shí)際中的使用效果。

其次在實(shí)際使用中，當(dāng)簇骨干或者在標(biāo)簽傳播中出現(xiàn)錯(cuò)誤點(diǎn)時(shí)，會(huì)把這個(gè)錯(cuò)誤擴(kuò)大化，嚴(yán)重影響聚類效果。這個(gè)缺陷可以根據(jù)式（5）看出，每次迭代都會(huì)使用標(biāo)簽矩陣Y，F(xiàn)t的更新也需要使用標(biāo)簽矩陣Y，這種情況會(huì)使錯(cuò)誤擴(kuò)大化。下面通過一個(gè)實(shí)例來說明這個(gè)情況，采用一個(gè)人工數(shù)據(jù)集，此數(shù)據(jù)集共由三部分組成，兩個(gè)半圓包圍著一個(gè)圓，如圖1 所示。在簇骨干中有一個(gè)錯(cuò)誤點(diǎn)（標(biāo)簽傳播過程中情況相同），如圖2中紅圈所示的位置，錯(cuò)把該樣本歸類為其他的簇，在經(jīng)過DPC-DLP算法的聚類后，得到如圖3所示的結(jié)果，從圖中可以看出，上半圓的右半部分的點(diǎn)在錯(cuò)誤點(diǎn)的影響下，算法把該部分的點(diǎn)都分配到錯(cuò)誤點(diǎn)所在的簇，由此可見錯(cuò)誤點(diǎn)對(duì)此算法的影響很大，并且會(huì)產(chǎn)生使錯(cuò)誤擴(kuò)大化的現(xiàn)象。

圖1 測試數(shù)據(jù)集Fig.1 Testing dataset

圖2 錯(cuò)誤點(diǎn)位置Fig.2 Location of error point

圖3 經(jīng)過DPC-DLP算法后得到的結(jié)果Fig.3 Result of DPC-DLP

另外，DPC-DLP還存在迭代次數(shù)過多時(shí)，聚類效果惡化的情況。如圖4已經(jīng)取得最優(yōu)結(jié)果，此后還繼續(xù)迭代，結(jié)果如圖5 所示，聚類效果會(huì)變差。此實(shí)驗(yàn)是在除迭代次數(shù)外，所有參數(shù)都相同的情況下進(jìn)行的，只增加迭代次數(shù)。

圖4 DPC-DLP獲得的最優(yōu)結(jié)果Fig.4 Optimal result of DPC-DLP

圖5 DPC-DLP增加迭代次數(shù)得到的結(jié)果Fig.5 Result of DPC-DLP by increasing the number of iterations

2 最近鄰的密度峰值聚類標(biāo)簽傳播算法

本文提出了一種最近鄰的密度峰值聚類標(biāo)簽傳播算法（DPC-NLP）。采用最近鄰傳播標(biāo)簽，可以在聚類的局部和非線性的情況下取得良好的效果。假設(shè)歐氏空間中某點(diǎn)的鄰域也是n維流形中的鄰域。在數(shù)學(xué)上，流形是一個(gè)局部逼近歐式空間附近的每一個(gè)點(diǎn)的拓?fù)淇臻g。近似流形空間的一個(gè)簡單方法是構(gòu)造K 鄰域、ε鄰域[23]。ε鄰域的條件是兩個(gè)點(diǎn)之間的距離小于ε，但是對(duì)于如何確定合適的ε值是困難的。K 鄰域是當(dāng)兩個(gè)點(diǎn)為K 鄰域的關(guān)系時(shí)，只有一個(gè)參數(shù)K相比其他鄰域，是比較高效的。

該方法主要有三個(gè)步驟：（1）利用局部密度ρ和最小距離δ確定聚類中心，此步驟借鑒DPC-NLP 算法[22]；（2）使用聚類中心形成簇骨干；（3）使用最近鄰的標(biāo)簽傳播方法將簇的標(biāo)簽傳播到剩余樣本上。

2.1 確定聚類中心

本節(jié)的目的是確定一組聚類中心。聚類中心一般具有如下特點(diǎn)：（1）它們和相鄰的樣本相比的話，會(huì)具有更高的密度；（2）它們都會(huì)位于一個(gè)密集區(qū)域的中心，并且距離其他中心遠(yuǎn)。為了度量第一個(gè)特性，將局部密度ρ定義為每個(gè)樣本點(diǎn)與其相鄰點(diǎn)的平均距離。將每個(gè)樣本xi的局部密度ρi定義如下：

其中，kNN(xi)是xi的K最近鄰，k=[p×n]，p為輸入樣本的百分?jǐn)?shù)，n為樣本數(shù)量。

為了度量第二個(gè)特性，需要計(jì)算出每對(duì)樣本之間的距離，因此對(duì)于每個(gè)樣本，則計(jì)算出它與其他密度較高的樣本點(diǎn)之間的最小距離δ，定義如下：

通過式（9）可以使高密度的樣本具有高的δ值。在傳統(tǒng)的DPC中，通過繪制局部密度ρ和最小距離δ的決策圖來確定聚類中心。通過決策圖可以使聚類中心不僅具有較大的密度，還保證了兩個(gè)聚類中心足夠遠(yuǎn)。為了消除人為選擇聚類中心帶來的影響，有很多方式可以實(shí)現(xiàn)自動(dòng)確定聚類中心。本文使用了一種快速、簡單確定聚類中心的方式。首先對(duì)樣本使用局部密度ρ和最小距離δ進(jìn)行排序，然后選擇前c個(gè)樣本點(diǎn)作為聚類中心。提出的評(píng)分函數(shù)如下：

使用此度量，只有與高局部密度和高最小距離值相關(guān)聯(lián)的樣本才會(huì)被賦予高分。因此，該度量是決策圖的適當(dāng)替代，而不需要任何人力。為了更清楚地顯示該度量的有效性，圖6（a）給出了兩個(gè)集群的示例數(shù)據(jù)。圖6（b）中相應(yīng)的局部密度ρ和δ值繪制決策圖，從圖中可以看出得分最高的兩個(gè)樣本點(diǎn)被選取為聚類中心。

圖6 聚類中心選取示意圖Fig.6 Schematic diagram of cluster center selection

2.2 形成簇骨干

此步驟的目的是利用已經(jīng)確定的聚類中心為未標(biāo)記的樣本分配標(biāo)簽，把每個(gè)簇中心的標(biāo)簽傳播到未標(biāo)記的樣本上。如果使用歐式聚類計(jì)算聚類中心和樣本點(diǎn)之間的距離，會(huì)增加計(jì)算的復(fù)雜性，不適合作為標(biāo)簽傳播的方法。因此，本文使用鄰域結(jié)構(gòu)進(jìn)行標(biāo)簽傳播，并且可以近似流形結(jié)構(gòu)。本節(jié)使用K鄰域方法構(gòu)建一個(gè)圖，其中每個(gè)樣本點(diǎn)為一個(gè)節(jié)點(diǎn)，并與它的K近鄰相連，最后形成簇骨干。把每個(gè)聚類中心的標(biāo)簽分配給它的鄰域，如下所示：

其中，peak是一組確定的聚類中心，kNN(peakj)是簇中心xj的一組鄰居。也就是每個(gè)中心和它的鄰居被定義為圖中的主干。

2.3 最近鄰標(biāo)簽傳播

本節(jié)提出了一種最近鄰的標(biāo)簽傳播方式。通過這種方法，標(biāo)簽將傳播到其相鄰節(jié)點(diǎn)，直到所有節(jié)點(diǎn)都具有一個(gè)標(biāo)簽。因?yàn)镵近鄰可以近似流形結(jié)構(gòu)，并且反映出數(shù)據(jù)的局部信息。

標(biāo)簽傳播的過程為：首先統(tǒng)計(jì)剩余每個(gè)點(diǎn)的K鄰域中各有幾個(gè)點(diǎn)屬于這c個(gè)簇，從中找出其中最大的個(gè)數(shù)，并把該點(diǎn)分配到最大數(shù)所在的簇，之后再重新統(tǒng)計(jì)，循環(huán)上述步驟，如果屬于這c個(gè)簇點(diǎn)個(gè)數(shù)為0，則把k增加1，繼續(xù)統(tǒng)計(jì)、分配，直到所有點(diǎn)都分配完畢。算法流程如算法1所示。

算法1最近鄰標(biāo)簽傳播

最近鄰的標(biāo)簽傳播過程中，每次只傳播一個(gè)樣本的標(biāo)簽，不斷更新數(shù)據(jù)的狀態(tài)，利用數(shù)據(jù)的最新狀態(tài)來傳播標(biāo)簽，確保利用更多的信息提高分配的正確率。之后充分考慮出現(xiàn)錯(cuò)誤點(diǎn)對(duì)聚類結(jié)果帶來的影響，因此該樣本的標(biāo)簽是由它最近鄰內(nèi)擁有最多數(shù)量的標(biāo)簽決定，即使出現(xiàn)孤立的錯(cuò)誤點(diǎn)，也不會(huì)對(duì)該點(diǎn)的標(biāo)簽產(chǎn)生影響，大大提高了算法的魯棒性。為了更好驗(yàn)證本文提出的DPC-NLP算法在簇骨干或者傳播過程中出現(xiàn)錯(cuò)誤點(diǎn)后的效果，在圖7中給出了效果圖。如圖7（a）所示，此圖為錯(cuò)誤點(diǎn)所在的位置，從圖中可以看出在每個(gè)簇中都存在多個(gè)錯(cuò)誤點(diǎn)，圖7（b）是經(jīng)過DPC-NLP 算法的運(yùn)行后得到的結(jié)果，從圖中可以看出錯(cuò)誤點(diǎn)對(duì)本文算法的后續(xù)運(yùn)行沒有影響，可以得到正確的結(jié)果，具有很好的魯棒性。

圖7 DPC-NLP算法魯棒性實(shí)驗(yàn)示意圖Fig.7 Schematic diagram of DPC-NLP algorithm robustness experiment

DPC-NLP 算法在標(biāo)簽傳播過程中，是不需要進(jìn)行迭代的，因此就不會(huì)存在因迭代次數(shù)增加，聚類效果變差的情況。

DPC-NLP算法的詳細(xì)算法步驟如算法2所示。

算法2DPC-NLP

輸入：X，數(shù)據(jù)矩陣n×m；p，樣本的百分?jǐn)?shù)；k，分配時(shí)最近鄰的個(gè)數(shù)。

輸出：Y，標(biāo)簽矩陣n×1。

1.開始算法

2.計(jì)算近鄰k=[p×n]

3.利用式（8）計(jì)算局部密度ρi

4.利用式（9）計(jì)算最小距離δi

5.利用式（10）計(jì)算評(píng)分score

6.根據(jù)score選擇聚類中心

7.為聚類中心指定標(biāo)簽

8.將簇中心的標(biāo)簽分配給最近的鄰居，形成簇主干。

9.運(yùn)用算法1分配剩余點(diǎn)。

2.4 時(shí)間復(fù)雜度分析

本節(jié)主要分析所提出方法的時(shí)間復(fù)雜度。將點(diǎn)的總數(shù)設(shè)為n，簇中心數(shù)設(shè)為c，鄰居數(shù)設(shè)為k。根據(jù)上一節(jié)算法2的介紹，所提出方法的時(shí)間復(fù)雜度取決于三個(gè)主要步驟：（1）識(shí)別聚類中心（第2～7 行）；（2）形成聚類主干（第8 行）；（3）最近鄰標(biāo)簽傳播（第9行）。

算法為了確定聚類中心，需要計(jì)算每個(gè)數(shù)據(jù)點(diǎn)之間的距離，時(shí)間復(fù)雜度為O(n2)，然后計(jì)算局部密度ρi和最小距離δi，時(shí)間復(fù)雜度為O(n2)，再計(jì)算每個(gè)點(diǎn)的score，時(shí)間復(fù)雜度為O(n)，之后對(duì)數(shù)據(jù)點(diǎn)進(jìn)行排序選取聚類中心，時(shí)間復(fù)雜度為O(nlbn)，因此總體的時(shí)間復(fù)雜度為O(n2+n2+n+nlbn)，因?yàn)樵谟?jì)算過程中存儲(chǔ)了距離矩陣，時(shí)間復(fù)雜度可以降低到O(n2)。在形成簇骨干時(shí)，需要把簇中心的標(biāo)簽傳播到其最近鄰，時(shí)間復(fù)雜度為O(ck)。

根據(jù)最近標(biāo)簽傳播算法1的步驟，首先在最壞的情況下，該算法需要分配所有的點(diǎn)，因此，有一個(gè)乘數(shù)O(n)。然后掃描所有點(diǎn)，時(shí)間復(fù)雜度為O(n)。之后最多有n個(gè)未分配點(diǎn)，每個(gè)點(diǎn)有k個(gè)鄰居，時(shí)間復(fù)雜度為O(kn)。最后尋找最大值的時(shí)間復(fù)雜度為O(cn)。因此，算法1的總體時(shí)間復(fù)雜度為基本循環(huán)O(n)乘以循環(huán)中的最高復(fù)雜度O(kn)或O(cn)，則總體時(shí)間復(fù)雜度是O(kn2)或O(cn2)，可以合并為O((k+c)n2)。

綜上所述，整個(gè)DPC-NLP 算法的時(shí)間復(fù)雜度是O(n2+ck+(k+c)n2)，因?yàn)閗?n，c?n，所以整個(gè)算法的時(shí)間復(fù)雜度為O(n2)。

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

與目前主流的聚類算法，如FCM（fuzzy C-means clustering algorithm）[24]、DPC-KNN[20]、IDPC（improved density peaks method for data clustering）[25]、DPC-DLP[22]通過一系列實(shí)驗(yàn)進(jìn)行比較，來驗(yàn)證DPC-NLP 算法的性能。實(shí)驗(yàn)在一臺(tái)裝有CPU 型號(hào)為AMD Ryzen 5 3600、運(yùn)行內(nèi)存16 GB、Windows 10 64位操作系統(tǒng)和Matlab 2018a編程環(huán)境的PC機(jī)上進(jìn)行。

3.1 數(shù)據(jù)集

本次實(shí)驗(yàn)共在21 個(gè)數(shù)據(jù)集上進(jìn)行，其中4 個(gè)人工數(shù)據(jù)集和17個(gè)真實(shí)數(shù)據(jù)集，其中9個(gè)低維數(shù)據(jù)集、8 個(gè)高維數(shù)據(jù)集。二維人工數(shù)據(jù)集的樣本數(shù)量和具有的簇個(gè)數(shù)如表1 所示。低維數(shù)據(jù)集的具體情況如表2 所示。高維數(shù)據(jù)集的具體情況如表3 所示。這些數(shù)據(jù)集廣泛應(yīng)用于驗(yàn)證聚類算法性能。

表1 人工數(shù)據(jù)集Table 1 Synthetic datasets

表2 低維數(shù)據(jù)基本情況Table 2 Low-dimensional datasets

表3 高維數(shù)據(jù)基本情況Table 3 High-dimensional datasets

3.2 評(píng)價(jià)指標(biāo)

為了更好地比較實(shí)驗(yàn)結(jié)果，本文使用的評(píng)價(jià)指標(biāo)為蘭德系數(shù)（Rand index，RI）、調(diào)整蘭德系數(shù)（adjusted Rand index，ARI）、歸一化互信息（normalized mutual information，NMI）和F-measure 指標(biāo)，以上四個(gè)指標(biāo)都是其值越大，證明該算法的聚類效果越好。

蘭德系數(shù)（RI）評(píng)價(jià)同一樣本在兩種分類結(jié)果中是否被分到同一類別，取值范圍為[0,1]，定義如下：

其中，a表示在真實(shí)類別和聚類結(jié)果中都是同一類別的樣本對(duì)數(shù)，b表示在真實(shí)類別和聚類結(jié)果中都是不同類別的樣本對(duì)數(shù)是所有可能的樣本組合對(duì)。

為了實(shí)現(xiàn)“在聚類結(jié)果隨機(jī)產(chǎn)生的情況下，指標(biāo)應(yīng)該接近零”，調(diào)整蘭德系數(shù)（ARI）被提出，取值范圍為[-1,1]，它具有更高的區(qū)分度，定義如下：

歸一化互信息（NMI）用來衡量真實(shí)標(biāo)簽與實(shí)際聚類結(jié)果分布的吻合情況，范圍為[0,1]，定義如下：

其中，MI表示互信息，H表示信息熵，F(xiàn)(H(Y),H(C))通常取算數(shù)平均，即F(H(Y),H(C))=。

F-measure 又稱F-score，是精確度與召回率的加權(quán)調(diào)和平均，取值范圍為[0,1]，定義如下：

其中，P為精確度，R為召回率。

3.3 結(jié)果

3.3.1 在人工數(shù)據(jù)集上的結(jié)果

本小節(jié)的目的是比較在4 個(gè)人工數(shù)據(jù)集上本文提出的DPC-NLP算法和DPC-DLP算法的效果。圖8是比較了兩種算法在Aggregation 數(shù)據(jù)集上的結(jié)果。此數(shù)據(jù)集具有7 個(gè)大小不同并且分布不均勻的集群組成，其中兩處具有連接點(diǎn)，這種情況的聚類算法的考驗(yàn)是很大的。結(jié)果表明，本文算法可以為數(shù)據(jù)分配正確的標(biāo)簽。本文算法只有1 個(gè)點(diǎn)出現(xiàn)了錯(cuò)誤聚類的情況，并且這個(gè)點(diǎn)在兩個(gè)簇的連接處。而DPCDLP 有5 個(gè)點(diǎn)聚類錯(cuò)誤，也是在同樣的位置上，不能正確分類連通的點(diǎn)。圖9 是比較兩種算法在Flame數(shù)據(jù)集上的結(jié)果，此數(shù)據(jù)集也是上下兩部分連通在一起。本文算法對(duì)于此數(shù)據(jù)集全部聚類正確，而DPCDLP算法再次反映出不能很好分類出連通處的點(diǎn)。

圖8 DPC-DLP和DPC-NLP在Aggregation數(shù)據(jù)集上的結(jié)果Fig.8 Result of DPC-DLP and DPC-NLP on Aggregation dataset

圖9 DPC-DLP和DPC-NLP在Flame數(shù)據(jù)集上的結(jié)果Fig.9 Result of DPC-DLP and DPC-NLP on Flame dataset

CMC數(shù)據(jù)集是DPC-DLP文章里人工數(shù)據(jù)集，圖10 是比較兩種算法在此數(shù)據(jù)集上的結(jié)果，兩種算法都在此數(shù)據(jù)集上聚類正確，沒有錯(cuò)誤點(diǎn)。

圖10 DPC-DLP和DPC-NLP在CMC數(shù)據(jù)集上的結(jié)果Fig.10 Result of DPC-DLP and DPC-NLP on CMC dataset

Spiral 數(shù)據(jù)集是一個(gè)流形數(shù)據(jù)集，由3 個(gè)螺線組成，能夠很好地驗(yàn)證算法對(duì)流形數(shù)據(jù)的處理能力。圖11 是比較兩種算法在此數(shù)據(jù)集上的結(jié)果，從圖中可以看出DPC-DLP算法不能發(fā)現(xiàn)數(shù)據(jù)集中的流形結(jié)構(gòu)，導(dǎo)致無法對(duì)流形數(shù)據(jù)集進(jìn)行聚類。本文算法能夠很好地識(shí)別出數(shù)據(jù)集的流形結(jié)構(gòu)，并且全部聚類正確。

圖11 DPC-DLP和DPC-NLP在Spiral數(shù)據(jù)集上的結(jié)果Fig.11 Result of DPC-DLP and DPC-NLP on Spiral dataset

3.3.2 在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

本小節(jié)通過在低維和高維數(shù)據(jù)集上進(jìn)行一系列實(shí)驗(yàn)來驗(yàn)證算法的性能。低維數(shù)據(jù)集上的結(jié)果如表4～表6所示，最好的結(jié)果用加粗字標(biāo)記出來。表4比較了本文算法和FCM、DPC-KNN、IDPC、DPC-DLP的F-measure 指標(biāo)。從結(jié)果中可以看出，本文算法在所有數(shù)據(jù)集上都取得了最好的效果，并且平均結(jié)果高出DPC-DLP 算法0.058 3。表5、表6 為RI 指標(biāo)和ARI指標(biāo)的評(píng)價(jià)結(jié)果。從結(jié)果中可以看出，在大多數(shù)情況下，本文算法都取得了最好的結(jié)果，RI 指標(biāo)和ARI 指標(biāo)的平均值分別高于DPC-DLP 算法0.044 0和0.352 3。從以上結(jié)果可以看出，本文提出的DPCNLP算法的性能在低維數(shù)據(jù)上遠(yuǎn)遠(yuǎn)高于其他先進(jìn)的聚類算法。

表4 低維數(shù)據(jù)集上的F-measure指標(biāo)結(jié)果Table 4 F-measure index results on low-dimensional datasets

表5 低維數(shù)據(jù)集上的RI指標(biāo)結(jié)果Table 5 RI index results on low-dimensional datasets

表6 低維數(shù)據(jù)集上的ARI指標(biāo)結(jié)果Table 6 ARI index results on low-dimensional datasets

高維數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果如表7～表9所示，本文算法分別與FCM、DPC-KNN、IDPC、DPC-DLP 算法比較了RI、ARI 和NMI 指標(biāo)。在表7 中的RI 指標(biāo)結(jié)果中，只有在Drivface 數(shù)據(jù)集上和DPC-DLP 算法相差0.002 3，在剩下的數(shù)據(jù)集都取得最好的結(jié)果，并且平均RI 指標(biāo)值高于DPC-DLP 算法0.043 0。從表8 的ARI 指標(biāo)結(jié)果看出，在大多數(shù)情況下，該算法取得了較好的效果，并且ARI 平均指標(biāo)高于DPC-DLP 算法0.029 0。從表9 的NMI 指標(biāo)結(jié)果看出，除了Yeast 數(shù)據(jù)集上的結(jié)果，在剩下的數(shù)據(jù)集上都取得了最好的結(jié)果。通過以上結(jié)果的對(duì)比可以看出本文提出的DPC-NLP算法在大多數(shù)數(shù)據(jù)集上可以取得較好的結(jié)果，說明在高維數(shù)據(jù)集上，DPC-NLP具有良好性能。

表7 在高維數(shù)據(jù)集上的RI指標(biāo)結(jié)果Table 7 RI index results on high-dimensional datasets

表8 在高維數(shù)據(jù)集上的ARI指標(biāo)結(jié)果Table 8 ARI index results on high-dimensional datasets

表9 在高維數(shù)據(jù)集上的NMI指標(biāo)結(jié)果Table 9 NMI index results on high-dimensional datasets

4 結(jié)束語

本文提出了一種最近鄰的密度峰值聚類標(biāo)簽傳播算法DPC-NLP。該算法利用最近鄰信息將標(biāo)簽傳播到剩余點(diǎn)，并形成最終的聚類。該算法充分考慮數(shù)據(jù)間的結(jié)構(gòu)情況，并在分配的過程中不斷更新數(shù)據(jù)的狀態(tài)，確保利用更多的信息提高分配正確率。DPC-DLP由三個(gè)主要步驟組成：第一步，利用局部密度和最小距離來識(shí)別聚類中心。第二步，用K鄰域方法構(gòu)造簇骨干。在這一步中，每個(gè)簇中心及其對(duì)應(yīng)的K近鄰形成一個(gè)簇骨干。第三步，利用一種新的最近鄰標(biāo)簽傳播將標(biāo)簽傳播到其余樣本。該方法可以有效地應(yīng)用于圖像聚類、基因表達(dá)、生物信息等領(lǐng)域，并發(fā)現(xiàn)流形等復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果表明，相比其他聚類算法，DPC-NLP 具有很好的性能和魯棒性，并可以處理流形等復(fù)雜數(shù)據(jù)。當(dāng)然，本文還存在計(jì)算局部密度和標(biāo)簽傳播時(shí)都需要參數(shù)設(shè)定、計(jì)算成本較大等問題，今后將對(duì)以上問題進(jìn)行改進(jìn)。