面向密度分布不均數據的加權逆近鄰密度峰值聚類算法

呂莉，陳威，肖人彬，韓龍哲，譚德坤

（1.南昌工程學院 信息工程學院, 江西 南昌 330099; 2.南昌工程學院 南昌市智慧城市物聯感知與協同計算重點實驗室, 江西 南昌 330099; 3.華中科技大學 人工智能與自動化學院, 湖北 武漢 430074）

聚類是數據分析中一種重要的無監督學習方法，致力于揭示看似雜亂無章的未知數據背后隱藏的內在屬性和規律，為決策提供支持，并已成功應用于許多領域，如圖像分析[1]、模式識別[2]、社會網絡挖掘[3]、市場統計分析[4]和醫學研究[5]等。

傳統的聚類算法分為基于劃分的[6]、基于層次的[7]、基于網格的[8]、基于模型的[9]和基于密度的[10]聚類算法。K-means[11]是最著名的劃分聚類算法，通過多次迭代獲得最優聚類中心。Kmeans收斂速度快，對大規模數據集的處理效率高，但該算法的性能依賴于初始聚類中心的選擇，且對噪聲點和異常值敏感。BIRCH(balanced iterative reducing and clustering using hierarchies)[12]是一種基于層次的聚類算法，利用聚類特征樹自底向上進行聚類。BIRCH聚類速度快，能識別噪聲點，但不適用于高維和非凸數據。CLIQUE(clustering in quest)[13]是一種基于網格的聚類算法，把數據空間分為不同的網格，將樣本對應到網格中，并進行密度的計算。CLIQUE適用于高維和大規模數據集，但該算法聚類的準確度較低。EM(expectation maximization)[14]是一種基于模型的聚類算法，根據極大后驗概率估計尋找樣本的概率模型參數進行聚類。該算法計算結果穩定、準確，但對初始化數據敏感。DBSCAN(density-based spatial clustering of applications with noise)[15]是典型的基于密度的聚類算法，它將樣本分為核心點和噪聲點，根據密度可達將核心點聚合到同一個集群中。該算法可以識別任意形狀的稠密數據集且對數據集中的異常點不敏感，但不能處理密度差異過大的數據。

2014年，Science發表了通過快速搜索和尋找密度峰值聚類[16](clustering by fast search and find of density peaks, DPC)算法。由于其新穎的設計理念和強大的性能，使得基于密度的聚類算法受到更廣泛的關注和應用。DPC算法基于兩點假設：聚類中心周圍的樣本的局部密度相對較低；不同聚類中心間的距離相對較遠。DPC算法計算過程無需迭代，只需預先設定一個參數來識別聚類中心，但DPC算法仍有一些缺點：1）算法局部密度無法準確識別各類簇間樣本的疏密差異，易造成類簇中心的誤判；2）雖然DPC中的分配規則非常有效，但是當聚類過程出現某一個樣本被錯誤分配，就會出現多米諾骨牌效應。

針對DPC算法易出現類簇中心選取錯誤的問題，呂莉等[17]提出二階K近鄰和多簇合并的密度峰值聚類算法(density peaks clustering with second-order k-nearest neighbors and multi-cluster merging, DPC-SKMM)。DPC-SKMM算法提出最小二階K近鄰的概念，根據K近鄰和二階K近鄰信息重新定義局部密度，凸顯聚中心與非聚類中心的密度差異。Sun等[18]提出了基于最近鄰優化分配策略的自適應密度峰值聚類算法(nearest neighbors-based adaptive density peaks clustering with optimized allocation strategy, NADPC)。NADPC算法提出了候選簇心和相對密度的概念，根據候選聚類中心的相對密度和高密度最近鄰距離，計算聚類中心的可信度，從而選擇聚類中心。趙嘉等[19]提出了K近鄰和加權相似性的密度峰值聚類算法(density peaks clustering algorithm with knearest neighbors and weighted similarity, DPCKWS)。DPC-KWS算法從樣本的K近鄰信息出發，重新定義了局部密度，調整了不同類簇中局部密度的大小。

針對分配規則出現的問題，吳潤秀等[20]提出基于相對密度估計和多簇合并的密度峰值聚類算法(density peaks clustering based on relative density estimating and multi cluster merging, DPC-RDMCM)。DPC-RD-MCM算法重新定義了微簇間相似性度量準則，通過多簇合并策略得到最終聚類結果，避免了分配錯誤連帶效應。Ding等[21]提出了基于中心和鄰居的社區檢測算法(community detection by propagating the label of center, DCN)。DCN算法根據樣本的鄰居傳播標簽，提出了標簽傳播的多重策略，有效解決了DPC分配策略的多米諾效應。趙嘉等[22]提出面向流形數據的測地距離與余弦互逆近鄰密度峰值聚類算法(density peaks clustering algorithm based on geodesic distance and cosine mutual reverse nearest neighbors for manifold datasets, DPC-GDCN)。DPC-GDCN算法將互逆近鄰和余弦相似性相結合，得到基于余弦互逆近鄰的樣本相似度矩陣，為流形類簇準確分配樣本。

上述算法均有效提高了DPC算法的聚類效果，但忽略了樣本間的分布特征，無法對密度分布不均等特定數據集取得較好的聚類效果。因此，本文提出了面向密度分布不均數據的加權逆近鄰密度峰值聚類算法(density peak clustering algorithm based on weighted reverse nearest neighbor for uneven density datasets, DPC-WR)。DPC-WR算法充分利用了逆近鄰和共享逆近鄰信息，算法的主要創新點如下：1）結合sigmoid函數及逆近鄰思想重新定義了局部密度，平衡了樣本間疏密程度的差異，提高了類簇中心的識別率；2）在樣本分配策略中，引入逆近鄰及共享逆近鄰信息，避免了稀疏區域樣本的錯誤分配，提高了聚類效果。

1 DPC算法

DPC是一種高效的密度峰值聚類算法，可以快速找到聚類中心，對多種聚類任務具有良好的適應性。該算法基于聚類中心密度大于鄰域密度，聚類中心間的距離相對較遠的思想，提出了兩種描述樣本xi的密度和距離的方法，即局部密度ρi和相對距離δi。

設有數據集X={x1,x2,···,xn}。對數據集X中的每個樣本，樣本間的歐氏距離為

局部密度ρi有兩種定義方式：

式(2)為截斷核，式(3)為高斯核。相對距離δi的定義如下：對于每個樣本xi，找到所有比樣本xi密集的樣本xj，選擇最小的dij；如果情況相反，則選擇最大的dij。δi的計算公式如下：

類簇中心由決策圖確定，以局部密度ρi為橫坐標，相對距離δi為縱坐標，建立決策圖。理想情況下，聚類中心選取為密度較高且相距較遠的樣本。定義如下：

最后，選取前n個 較大的值作為聚類中心，n為最終類簇數。

2 DPC-WR算法

在聚類算法中，K近鄰和逆近鄰在表征密度時起著重要作用。K近鄰能準確反映樣本在空間中的局部分布特征。而逆近鄰基于全局視角檢查它的鄰域，數據分布的變化會對樣本的逆近鄰造成影響，使得算法更容易識別聚類中心和提升算法聚類性能。因此，本文引入逆近鄰和共享逆近鄰信息，重新定義了局部密度，設計了樣本相似度策略，充分考慮了樣本的總體分布，使樣本的局部一致性和全局一致性得到較好的均衡。

2.1 加權逆近鄰的局部密度

定義1逆近鄰[23]。設樣本xi,xj∈X，xi在xj的K近鄰集中，那么xj是xi的逆近鄰，具體定義如下：

定義2隸屬度。樣本xi和xj的隸屬度μij定義如下：

其中：k為樣本的近鄰數；|R(i)|表示樣本xi的逆近鄰數，該值越大，該點的隸屬度越大。

定義3加權逆近鄰的局部密度。局部密度定義如下：

權重系數：

類簇密度不同時，數據稠密區域與數據稀疏區域的樣本對聚類中心選取的貢獻程度是不同的。因此，處理密度分布不均數據時，通過引入權重對樣本的貢獻進行處理，可以達到良好的均衡效果。本文以樣本的逆近鄰數作為衡量密度的重要指標，引入sigmoid函數，對不同類簇中的樣本進行權重調整。

式(9)中λij為權重系數，它在sigmoid函數的基礎上進行重構，分母部分以樣本的逆近鄰數替代了原函數的變量x值，分子部分采用逆近鄰代替實數值，使密度分布不均數據在不同區域具有辨識度。從函數可知，隨著逆近鄰數逐漸增加，其函數值趨近于1，說明位于高密度區域的樣本所加的權重近似于1。對于較高密度的樣本，被選為聚類中心的概率較大，此時逆近鄰數起到關鍵的作用。當逆近鄰數不斷減少直至為0時，樣本的權重將會從1發生非線性變化減少到0.5，這不僅考慮到各樣本間細微的影響，還提高了聚類中心與非聚類中心的區分，使式(7)的隸屬度定義更為合理。

2.2 逆近鄰和共享逆近鄰的分配策略

定義4共享逆近鄰。設樣本xi的逆近鄰集為RN N(xi)，xj的逆近鄰集為RNN(xj)，樣本xi與xj的共享逆近鄰定義如下所示：

定義5逆近鄰和共享逆近鄰的樣本鄰近度。通過樣本間的逆近鄰信息，定義了鄰近度ωij，其定義如下：

其中max(d)表示數據集X中樣本間歐氏距離的最大值。

式(11)中第一行表示當樣本xj位于樣本xi的逆近鄰范圍內時所賦予的鄰近度；第二行表示當樣本xj不處于樣本xi的逆近鄰范圍時，由于樣本間的緊密程度低，若將值賦0，易忽略未在范圍內的樣本的細微影響，故其鄰近度在逆近鄰范圍的基礎上除以最大距離所得。

定義6樣本相似度?；谀娼徍凸蚕砟娼?，得到樣本xi和xj的相似度：

β(xi,xj)反映了樣本所處空間的緊密程度，分子部分為每個樣本的相似度之和，分母部分為歸一化參數。式(12)考慮了樣本本身及其共享逆近鄰樣本在定義樣本間相似度方面起著重要的作用，因此，只有當樣本之間存在逆近鄰或共享逆近鄰時，才存在相似性。

2.3 算法步驟

輸入數據集X=，近鄰數k

輸出聚類結果C

1）數據歸一化；

2）計算數據集樣本間的歐氏距離；

3）根據式(8)和式(4)分別計算各樣本的局部密度ρi和相對距離δi；

4）根據式(5)計算各樣本的決策值γi并選取聚類中心；

5）根據式(12)計算基于逆近鄰和共享逆近鄰的樣本相似度并構建相似度矩陣；

6）對于所有已分配的樣本，找到相似度最高的未分配樣本并將其分配到已分配樣本所在的簇中；

7）若所有已分配樣本與未分配樣本間的相似度為0，轉至步驟8），否則轉至步驟6）；

8）若還存在未分配的樣本，則按DPC算法分配策略分配；

9）輸出聚類結果。

2.4 算法復雜度分析

設樣本規模為n，k為近鄰數。DPC算法的時間復雜度為O(n2)[24]。DPC-WR算法的時間復雜度主要由以下6個部分組成：1）計算樣本間距離矩陣的復雜度O(n2)；2）計算樣本的局部密度，包括計算樣本間的K近鄰和樣本間的逆近鄰與逆近鄰數，前者復雜度為O(n)，后者為O(kn)和O(n2)；3）計算樣本相對距離的復雜度O(n2)；4）計算樣本決策值的復雜度O(n2)；5）計算樣本的共享逆近鄰與鄰近度的復雜度O(n2)；6）計算樣本最壞分配情況的復雜度O(n2logn)。綜上，DPC-WR算法的時間復雜度為O(n2logn)。

3 實驗結果與分析

3.1 實驗設置

為驗證DPC-WR算法的性能，本文在密度分布不均數據集、復雜形態數據集和UCI真實數據集上進行實驗。將DPC-WR算法與IDPC-FA[25]、FNDPC[26]、FKK-DPC[20]、DPC[16]和DPCSA[27]算法進行比較。其中，IDPC-FA、DPCSA和DPC算法由原作者提供，FNDPC和FKNN-DPC算法參照原文獻編程實現。除了DPCSA和IDPC-FA無需對參數調優外，其余算法均需要調整參數。DPCWR和FKNN-DPC算法參數k值的選取是1～50之間的最優值；DPC算法的截斷距離dc的選取在0.1%～5%，步長為0.1%；FNDPC算法參數ε的選取在0.01～1，步長為0.01。實驗環境為Win10 64 bit操作系統，AMD Ryzen 7 5800H with Radeon Graphics 3.20 GHz處理器，16.0GB內存。

本文采用調整互信息（adjusted mutual information, AMI）[28]、Fowlkes-Mallows指數（fowlkesmallows index, FMI）[28]和調整蘭德系數（adjusted rand index, ARI）[29]對聚類效果進行評價，其中，3個指標的最佳結果都為1，各指標值接近1的程度越高，表明聚類結果越好。

3.2 密度分布不均數據集的實驗結果與分析

本文選取了6個不同規模的密度分布不均數據集進行實驗，其基本特征如表1所示。

表1 密度分布不均數據集的基本特征Table 1 Basic characteristics of datasets with uneven density distribution

表2給出了6種算法在密度分布不均數據集上的聚類結果，其中最優結果以粗體表示，“Arg-”表示各算法的最優參數取值?！啊北硎静缓瑓?。DPC-WR算法在6個數據集上均獲得最佳的聚類效果。IDPC-FA算法對Jain和LineBlobs具有較好的聚類效果，對其他數據集的聚類效果較差。FKNN-DPC算法對Cmc和LineBlobs數據集聚類效果較好，對其他數據集聚類效果不佳。DPCSA算法僅對LineBlobs數據集具有較好的聚類效果。FNDPC和DPC算法在6個數據集上的聚類性能均低于DPC-WR和FKNN-DPC算法。

表2 6種算法在密度分布不均數據集上的聚類結果Table 2 Clustering results of six algorithms on datasets with uneven density distribution

Friedman檢驗[30]是利用秩實現對多個總體分布是否存在顯著差異的非參數檢驗方法。將對比算法進行檢驗可以更準確地反映算法間評價指標的差異，秩均值越高則算法的聚類效果越優。從表3可以發現，在密度分布不均數據集上聚類評價指標AMI、ARI和FMI的秩均值排名中，DPCWR算法都位列第1，且秩均值都大于5.4。

表3 6種算法在密度分布不均數據集上的秩均值Table 3 Rank mean of the six algorithms on the unevenly distributed density datasets

由于篇幅所限，本文選取了1個典型的密度分布不均數據集。圖1給出了DPC-WR、IDPCFA、FNDPC、FKNN-DPC、DPC和DPCSA算法在Jain數據集上的聚類結果。圖中不同的顏色代表不同的類簇，類簇中心用“六角星”表示。

圖1 6種算法在Jain數據集上的聚類結果Fig.1 The clustering results of 6 algorithms on Jain dataset

Jain數據集由2個稠密程度不同的新月形類簇構成。從圖1可知，DPC-WR和IDPC-FA算法充分考慮了樣本間的密度差，能準確地找到類簇中心；FNDPC和FKNN-DPC算法雖然找到了正確的類簇中心，但樣本分配策略存在錯誤，導致稀疏類簇樣本的錯誤分配；DPC和DPCSA算法沒有找到正確的聚類中心，導致聚類效果不佳。

3.3 復雜形態數據集的實驗結果與分析

復雜形態數據集是指具有多尺度、簇類形狀多樣等結構的數據集。本文選取了6個復雜形態的數據集，其基本特征如表4所示。表5給出了6種算法在復雜形態數據集上的聚類結果。從表5可知，DPC-WR和IDPC-FA算法比其他對比算法的聚類結果更優，都存在4個聚類效果較好的數據集。從整體來看，DPC-WR算法的聚類效果最佳，具體表現在Flame、R15、Sticks和Pathbased數據集。

表4 復雜形態數據集的基本特征Table 4 Basic characteristics of complex

表5 6種算法在復雜形態數據集上的聚類結果Table 5 Clustering results of six algorithms on complex morphological datasets

表6為6種算法在6個復雜形態數據集上評價指標的秩均值。從表6可以發現，DPC-WR算法在AMI、ARI和FMI評價指標的秩均值中位列第一，其次是IDPC-FA算法，然后是FNDPC算法。

表6 6種算法在復雜形態數據集上的秩均值Table 6 Rank mean of 6 algorithms on complex morphological datasets

3.4 UCI數據集的實驗結果與分析

UCI數據集又稱真實數據集，它是一個常用的標準測試數據集。為了進一步驗證DPCWR算法的有效性，本文選取了8個真實數據集，對6種算法進行實驗。其中測試的數據集包括Iris、Wine、Seeds、Ecoli、Inonsphere、Libras、Dermatology和Wdbc。表7給出了各數據集的基本特征。表8為6種算法在UCI數據集上的聚類效果。從表8可以發現，處理Seeds數據集時，DPC-WR算法的聚類效果不及IDPC-FA、FKNN-DPC和DPC算法。處理Inonsphere數據集時，DPC-WR算法的聚類效果低于FKNN-DPC算法。處理Dermatology數據集時，DPC-WR算法的聚類效果比DPCSA算法好，但略遜于其他算法。剩余的Iris、Wine、Ecoli、Libras和Wdbc數據集，DPC-WR算法的聚類效果都優于其他算法。

表7 UCI數據集的基本特征Table 7 Basic characteristics of UCI datasets

表8 6種算法在UCI數據集上的聚類結果Table 8 Clustering results of six algorithms on UCI datasets

表9為6種算法在UCI數據集上評價指標的秩均值。從表9可知，DPC-WR算法相較于其他對比算法評價指標的秩均值都是最高的，其次是FKNN-DPC和IDPC-FA算法。由此可以得出，在UCI真實數據集上，DPC-WR算法的聚類效果明顯優于IDPC-FA、FNDPC、FKNN-DPC、DPC和DPCSA算法。

表9 6種算法在UCI數據集上的秩均值Table 9 Rank mean of six algorithms on UCI datasets

3.5 算法的仿真時間與分析

本文中，仿真時間指完成單個數據集聚類所花費的時長，是評價算法聚類性能的重要指標。為計算聚類算法的聚類時間，本文針對前述3類數據集進行了相應的實驗，結果詳見表10。

表10 6種算法在3類數據集上的仿真時間Table 10 Simulation time of six algorithms on three types of datasetss

從表10可以發現，對于樣本規模較小的數據集，如Jain、LineBlobs等，DPC-WR算法可以與對比算法相媲美或者更優；對于樣本規模較大的數據集，如Twomoons、Cmc等，DPC-WR算法弱于FNDPC、FKNN-DPC、DPC和DPCSA算法，但是，相較于IDPC-FA算法，DPC-WR算法加速效應明顯。這主要是由于DPC-WR算法的時間復雜度為O(n2logn)，樣本規模的增大，logn的影響將變得更加明顯。

4 結束語

針對DPC算法在面對密度分布不均數據集時易出現誤選類簇中心以及樣本分配錯誤的問題，本文提出了一種面向密度分布不均數據的加權逆近鄰密度峰值聚類算法。DPC-WR算法首先引入基于sigmoid函數的權重系數及逆近鄰思想，重新定義樣本的局部密度；隨后，利用逆近鄰和共享逆近鄰計算樣本相似度；最后，按照樣本相似度將剩余樣本進行分配。實驗結果表明，DPC-WR算法有效改善了類簇間樣本疏密差異導致誤判聚類中心以及稀疏區域樣本錯誤分配的問題，在密度分布不均數據集、復雜形態數據集和UCI數據集上的聚類效果明顯優于其對比算法。由于DPC-WR的聚類結果往往取決于參數k的選擇，如何快速選擇k的最佳值是下一步的研究重點。同時，群體智能[31-32]的引入有望進一步提升聚類算法的性能，特別是借助群智能進化[33-35]的途徑將使得聚類算法的自適應性更加趨于完善。