最近鄰的密度峰值聚類標簽傳播算法

宋 鵬，葛洪偉+

1.江南大學 人工智能與計算機學院，江蘇 無錫 214122

2.江蘇省模式識別與計算智能工程實驗室（江南大學），江蘇 無錫 214122

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

近年來，基于密度的聚類方法受到了研究者的廣泛關注。這些方法假設簇分布在高密度區域，可以識別具有任意形狀的簇，并且需要最少的領域知識就可以將數據劃分成不同的簇。DBSCAN（densitybased algorithm for discovering clusters in large spatial databases with noise）[16]是一種著名的基于密度的聚類方法，該方法不需要對數據的分布做出任何假設便可以估計出數據的密度，并且具有識別任意形狀聚類、可以處理噪聲和離群點、不需要在聚類之前人工預先設定聚類數目等優點。然而，這種方法存在不少缺陷，例如：它不能處理密度不均勻的數據集；對參數敏感，改變參數值就會產生不同的聚類結果；還有無法識別出具有重疊密度的簇。為了解決這些問題，一些優化算法已經被提出，例如：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]。該算法與其他方法不同，可以快速識別非球形團簇，并受到了廣泛關注。DPC的主要思想是簇中心的密度比其相鄰的數據點密度高，假設聚類中心與密度較高的點的距離相對較大。對于每個數據點，首先計算局部密度和基于最小密度的距離，然后繪制二維決策圖，再將具有較大局部密度和最小基于密度的距離的數據點識別為聚類中心，最后將數據點分配到與其密度較高的最近鄰相同的簇。與其他聚類方法相比，DPC 不需要指定預定義的聚類數目，不需要迭代，能節省聚類時間。但是，DPC的參數截止距離的選取對聚類結果有很大的影響，并且在識別出密度峰值后，將每個點分配給密度較高的最近鄰的策略可能會導致“鏈式反應”。

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

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

1 相關工作介紹

1.1 DPC-DLP算法

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

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

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

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

然后建立基于K近鄰的圖，其中每個節點只連接到它的鄰居，權重值定義如下：

然后將權重值標準化，在圖上定義一個轉移矩陣，如下所示：

其中，Pi,j表示從節點xi和xj的轉移概率，。P歸一化后是不對稱的，但它涵蓋了數據空間的結構信息。

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

其中，Yt是標簽矩陣，Ft是融合圖，定義如下：

其中，Ft表示實例YYT和控制相關率α的關系。在每次迭代中，Y使用不同的標簽，因此需要按下式重置Y。

1.2 DPC-DLP算法缺陷分析

基于圖的動態標簽傳播算法考慮了標簽空間的相關性，并以圖的形式進行傳播，最終得到了真實有效的標簽。相比其他的聚類算法具有良好的效果，但是它在進行標簽傳播的時候需要設置的參數太多，嚴重影響在實際中的使用效果。

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

圖1 測試數據集Fig.1 Testing dataset

圖2 錯誤點位置Fig.2 Location of error point

圖3 經過DPC-DLP算法后得到的結果Fig.3 Result of DPC-DLP

另外，DPC-DLP還存在迭代次數過多時，聚類效果惡化的情況。如圖4已經取得最優結果，此后還繼續迭代，結果如圖5 所示，聚類效果會變差。此實驗是在除迭代次數外，所有參數都相同的情況下進行的，只增加迭代次數。

圖4 DPC-DLP獲得的最優結果Fig.4 Optimal result of DPC-DLP

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

2 最近鄰的密度峰值聚類標簽傳播算法

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

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

2.1 確定聚類中心

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

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

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

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

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

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

2.2 形成簇骨干

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

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

2.3 最近鄰標簽傳播

本節提出了一種最近鄰的標簽傳播方式。通過這種方法，標簽將傳播到其相鄰節點，直到所有節點都具有一個標簽。因為K近鄰可以近似流形結構，并且反映出數據的局部信息。

標簽傳播的過程為：首先統計剩余每個點的K鄰域中各有幾個點屬于這c個簇，從中找出其中最大的個數，并把該點分配到最大數所在的簇，之后再重新統計，循環上述步驟，如果屬于這c個簇點個數為0，則把k增加1，繼續統計、分配，直到所有點都分配完畢。算法流程如算法1所示。

算法1最近鄰標簽傳播

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

圖7 DPC-NLP算法魯棒性實驗示意圖Fig.7 Schematic diagram of DPC-NLP algorithm robustness experiment

DPC-NLP 算法在標簽傳播過程中，是不需要進行迭代的，因此就不會存在因迭代次數增加，聚類效果變差的情況。

DPC-NLP算法的詳細算法步驟如算法2所示。

算法2DPC-NLP

輸入：X，數據矩陣n×m；p，樣本的百分數；k，分配時最近鄰的個數。

輸出：Y，標簽矩陣n×1。

1.開始算法

2.計算近鄰k=[p×n]

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

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

5.利用式（10）計算評分score

6.根據score選擇聚類中心

7.為聚類中心指定標簽

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

9.運用算法1分配剩余點。

2.4 時間復雜度分析

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

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

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

綜上所述，整個DPC-NLP 算法的時間復雜度是O(n2+ck+(k+c)n2)，因為k?n，c?n，所以整個算法的時間復雜度為O(n2)。

3 實驗與分析

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

3.1 數據集

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

表1 人工數據集Table 1 Synthetic datasets

表2 低維數據基本情況Table 2 Low-dimensional datasets

表3 高維數據基本情況Table 3 High-dimensional datasets

3.2 評價指標

為了更好地比較實驗結果，本文使用的評價指標為蘭德系數（Rand index，RI）、調整蘭德系數（adjusted Rand index，ARI）、歸一化互信息（normalized mutual information，NMI）和F-measure 指標，以上四個指標都是其值越大，證明該算法的聚類效果越好。

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

其中，a表示在真實類別和聚類結果中都是同一類別的樣本對數，b表示在真實類別和聚類結果中都是不同類別的樣本對數是所有可能的樣本組合對。

為了實現“在聚類結果隨機產生的情況下，指標應該接近零”，調整蘭德系數（ARI）被提出，取值范圍為[-1,1]，它具有更高的區分度，定義如下：

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

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

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

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

3.3 結果

3.3.1 在人工數據集上的結果

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

圖8 DPC-DLP和DPC-NLP在Aggregation數據集上的結果Fig.8 Result of DPC-DLP and DPC-NLP on Aggregation dataset

圖9 DPC-DLP和DPC-NLP在Flame數據集上的結果Fig.9 Result of DPC-DLP and DPC-NLP on Flame dataset

CMC數據集是DPC-DLP文章里人工數據集，圖10 是比較兩種算法在此數據集上的結果，兩種算法都在此數據集上聚類正確，沒有錯誤點。

圖10 DPC-DLP和DPC-NLP在CMC數據集上的結果Fig.10 Result of DPC-DLP and DPC-NLP on CMC dataset

Spiral 數據集是一個流形數據集，由3 個螺線組成，能夠很好地驗證算法對流形數據的處理能力。圖11 是比較兩種算法在此數據集上的結果，從圖中可以看出DPC-DLP算法不能發現數據集中的流形結構，導致無法對流形數據集進行聚類。本文算法能夠很好地識別出數據集的流形結構，并且全部聚類正確。

圖11 DPC-DLP和DPC-NLP在Spiral數據集上的結果Fig.11 Result of DPC-DLP and DPC-NLP on Spiral dataset

3.3.2 在真實數據集上的實驗結果

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

表4 低維數據集上的F-measure指標結果Table 4 F-measure index results on low-dimensional datasets

表5 低維數據集上的RI指標結果Table 5 RI index results on low-dimensional datasets

表6 低維數據集上的ARI指標結果Table 6 ARI index results on low-dimensional datasets

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

表7 在高維數據集上的RI指標結果Table 7 RI index results on high-dimensional datasets

表8 在高維數據集上的ARI指標結果Table 8 ARI index results on high-dimensional datasets

表9 在高維數據集上的NMI指標結果Table 9 NMI index results on high-dimensional datasets

4 結束語

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