基于自然和加權共享最近鄰的密度峰值聚類算法

中圖分類號：TP181 文獻標志碼：A

Density Peak ClusteringAlgorithm Based on Natural and Weighted Shared Nearest Neighbors

Wang Sen， Chen Xiang，Zhan Xiaoqin， Xu Lu， Wu Qizheng （SchoolofScience，EastChinaJiaotongUniversity，Nanchang33oo13，China）

Abstract： Density peak clustering （DPC）has been widely used as an eficient and non-iterativeclustering algorithm.However，studies have found that DPC struggles to select correct cluster centers，especially in datasets with non-spherical clusters and non-uniformdensity.Moreover，DPCis heavily influenced bythe truncation distance parameter.In order to address the issue of poor performance of DPCon datasets with uneven density distributions，adensity peak clustering algorithm based on natural and weighted shared nearest neighbors is proposed. It first introduced natural nearest neighbor computations tocalculate weights.Then，it redefined thesimilaritybetweendata objects basedonthe definitionsoffirst-order and second-order shared nearestneighbors.Subsequently，by fusing the definitions of shared nearest neighbor similarityand natural nearest neighbor weights，relative density and relative distance were calculated.Finaly，anovel strategy for distributing cluster centers Was designed.

Key words：clustering algorithm; density peak clustering; natural nearest neighbor; shared nearest neighbor; cluster center diffusion

Citationformat：WANG S，CEHN X， ZHANX，et al.Density peak clustering algorithm based on natural and weighted shared nearest neighbors[J].Journal ofEast China Jiaotong University，2025，42（4）： 120-126.

聚類是機器學習中的一種分類方法，旨在根據數據集的某些特征將其劃分為多個潛在的簇。該方法致力于確保簇內的數據對象具有較高相似性，而簇間的相似性則盡可能低]。2014年，Rodriguez等2提出了密度峰值聚類（density peak clustering，DPC）算法。由于DPC算法具有較強的可解釋性、無需迭代、簡單且能夠識別具有形狀的數據集，因此受到了廣泛關注。然而，傳統的DPC算法存在以下不足之處：人為設置的截斷參數值對聚類效果產生較大影響；對于密度分布不均勻的數據集，容易忽略稀疏簇的中心點；DPC算法進行非中心點標簽分配時，一個點的分配錯誤會導致后續點也分配錯誤的鏈式反應[3]。

Liu等4提出的ADPC-KNN算法的核心思想是在計算截斷距離時通過KNN自動計算參數值從而自適應地找到了合適的截斷距離，該算法雖然自適應地找到了合適的截斷距離值，但是卻增加了新的參數 K ；Zhang等借助自然界的衰減現象的規律提出了DGDPC算法，該算法先構造密度衰減圖，根據此圖的互相關系建造關系圖來識別潛在的初始聚類中心，最后根據自然界衰減規律的統一性完成最后聚類任務；Guo等提出了一種基于K近鄰集的NDPC算法，其核心思想是簇中心點被低密度的數據對象包圍，所以也被以該點為鄰居的所有數據對象包圍，計算所有視該點為鄰居的數據對象的個數即可得到該點的相對密度，該方法在密度不均勻的數據集上使用效果較好；Cheng等提出了一種基于局部核心點的DLORE-DPC算法，該算法結合了自然最近鄰的思想先尋找微簇的核心點作為代表點，計算代表點間的相似度，再對微簇進行合并。Liu等8提出了一種基于共享最近鄰的SNN-DPC算法，該算法根據共享最近鄰的概念重新定義了數據對象間的相似度，計算相對距離時提出了基于K近鄰的補償值，最后在分配非中心點時則使用兩步分配策略。

針對DPC算法的不足之處，本文提出一種基于自然和共享最近鄰的密度峰值聚類算法（DPC-NN-WSNN）。

DPC算法

DPC算法其核心思想基于兩個假設：首先，每個簇的中心密度相對較高且被低密度區域所包圍；其次，每個簇中心之間的距離會相對較遠。為了對應這兩個假設引入了相對密度 ρ_i 和相對距離 δ_i 這兩個定義，數據對象 i 的相對密度記作 ρ_i ，定義為

式中： i 和 j 分別為數據集中的兩個數據對象；dist（?） 為歐式距離， d_c 為截斷距離； χ（?） 表示以 d_c 為半徑的領域內的數據點數量即為該點的相對密度，該公式也被稱為截斷核密度公式。除了截斷核密度公式之外，還有高斯核密度公式，定義為

式中： 表示底數為e的冪函數。當數據集規模較大時一般使用截斷核相對密度公式，數據集規模較小時則使用高斯核相對密度公式。

數據集中每個數據對象到其密度更高的且最近的數據對象的相對距離 δ_i 定義為

DPC算法認為當相對密度 ρ_i 和相對距離 δ_i 的值都較大時，對應的數據對象被選取為簇中心，最后將剩余非中心點分配至距離最近且密度比其大的簇。

2 優化算法DPC-NN-WSNN

2.1基于自然和共享最近鄰的加權相對密度

Zhu等[提出了自然最近鄰的概念，該定義自適應地根據數據對象的特點尋找自身的自然最近鄰，無須設置參數 K 就能自適應找到每個數據對象的自然最近鄰，可以降低參數值對聚類結果產生的影響。基于自然最近鄰的思想，將提出自然最近鄰權重值的定義。

定義1數據對象i的自然近鄰權重值記作

W_n（i） ，定義為

式中： NN（i） 為自然近鄰集函數； ?_m 為自然近鄰集的任意一點。

在計算孤立點的相對密度時，由于孤立點遠離簇中心，在有些情況下找不到其一階共享最近鄰也難以計算其一階共享最近鄰相似度，并且一階共享最近鄰的信息在計算過程中是不夠精確的，二階鄰居的信息對計算結果也能產生較大的影響。針對一階共享最近鄰的缺陷，在此基礎上提出二階共享最近鄰的定義，并且提出基于二階共享最近鄰的相似度定義。

定義2數據對象 i 和 j 的二階共享最近鄰記作SSNN（i，j） ，函數定義為

SSNN（i，j）=SKNN（i）?SKNN（j）

式中： SKNN（i） 為數據對象 x_i 的二階鄰居集合函數。

定義3數據對象 i 和 j 的二階共享最近鄰相似度記作 SSim（i，j） ，函數定義為

式中： |SSim（i，j）| 為點 x_i 和點 x_j 的二階共享最近鄰數量函數； p 為二階共享最近鄰集的任意一點。特別地，當數據對象 i 和 j 沒有二階共享最近鄰時，二階共享最近鄰相似度設置為0。

定義4數據對象 i 和 j 的融合相似度記作FSim（i，j） ，函數定義為

FSim（i，j）=αSim（i，j）+（1-α）SSim（i，j）

式中： a 為可以調整的平衡值，考慮到一階共享最近鄰相似度對數據對象的相似度貢獻值較大，后續實驗將 a 的值設置為0.8。該式計算了數據對象的融合相似度，其中包括了多階的融合共享最近鄰信息，對于數據集中的邊界點或者孤立點，有效地提升了其相似度的計算精度[]。

定義5數據對象 i 的相對密度記作 ρ_r（i） ，定義為

式中： L（i） 為與數據對象i的融合相似度最高的 K 個點的集合。該式計算所有點數據對象 i 的融合相似度，找到最高的 K 個點然后相加，就能得到融合相似度之和，再乘上該點的自然最近鄰權重值W_n（i） ，即為該數據對象的相對密度。

本文提出的相對密度 ρ_r 能夠自適應地根據簇的稀疏程度通過自然近鄰權重值調整數據對象的相對密度值，對于處于稀疏簇的數據對象，其相對密度值會因此放大，得到更為真實的相對密度值[12]。

2.2基于自然最近鄰的加權相對距離

在DPC算法中，相對距離 δ_i 的計算方式是數據對象 i 到密度比它大的數據對象的最短距離，但是這樣計算忽略了數據對象的周圍環境信息，對于密度稀疏的點沒有權重補正[13]，因此本小節提出基于自然最近鄰的加權相對距離表達式。

定義6數據對象 i 的加權相對距離表達式記作 δ_r（i） ，定義為

該式對于稀疏簇來說，依然會有效放大其相對距離值，有助于識別正確地簇中心[14]。

2.3分類型簇中心擴散策略

傳統DPC算法的分配過程只要有一個標簽分配錯誤，后面就會出現鏈式錯誤。針對這個問題，提出了分類型簇中心擴散策略[15]，該策略基于圖1對從屬點的解釋圖，對稀疏和密集簇中心點進行區分，設計了不同的識別從屬點閾值，

定義7必然從屬點：假設數據對象 i 的標簽已經被分配，當且僅當 i 滿足如下條件時

j 是 i 的一個必然從屬點，如圖1所示。

圖1必然從屬點 Fig.1InevitableSubordinatePoint

定義8可能從屬點：假設數據對象 i 的標簽已經被分配，當且僅當 j 滿足如下條件時

j 是 i 的一個可能從屬點，如圖2所示。

圖2可能從屬點Fig.2Possible subordinate point

定義9不可能從屬點：假設數據對象 i 的標簽已經被分配，當且僅當 j 滿足如下條件時

j 是 i 的一個不可能從屬點，如圖3所示。

圖3不可能從屬點

Fig.3Impossible subordinatepoint

條件時

x_i 為相對高密度簇中心。

定義11相對低密度簇中心：假設數據對象 i 是被決策圖選取出的簇中心，當且僅當 i 滿足如下條件時

i 為相對低密度簇中心。

式（13），式（14）中： L（c_i） 是所有被識別出的簇中心集合； |L（c_i）| 簇中心的個數是右式計算的是簇中心的自然最近鄰權重的平均值。因為自然最近鄰權重越大，密度相對越低，所以所有簇中心里自然最近鄰權重值大于平均值的都視為相對低密度簇中心，反之為相對高密度簇中心。對于密度較低的簇中心，設置更大的 n 值，從而減小閾值，保證低密度簇在進行標簽分配時也能識別更多的必然從屬點，從而可以進行更精確的分配[。分類型簇中心擴散策略如下。

輸入：數據集 X 的初始簇中心 C（X）=（c₁， c₂，…，c_m）

Step1：初始化創建隊列 ，將 C（X） 里的簇中心索引加入隊列中；

式（10）～式（12）中： k 為最近鄰的數量； n 為任意正整數（后續實驗取值為2或者3）；如果數據對象 i 和 j 共享最近鄰數量高于閾值 ，那么 j 是i的必然從屬點， j 和 i 的標簽將會保持一致，反之 j 是 i 的可能從屬點。特別地，共享最近鄰數量為0時， j 是 i 的不可能從屬點。

Step2：檢查所有簇中心的自然最近鄰權重值， （20號其權重值小于 的簇中心設置為相對高密度簇中心，反之則設置為低密度簇中心；

對于密度較高的簇，數據對象分布更密集，會識別出更多的共享最近鄰，所以在進行簇中心擴散分配策略時，處于密度較高簇的中心點更容易識別出更多的從屬點，從而影響標簽分配的準確率。針對這個問題，提出兩個定義對兩種密度差別較大的簇中心進行分類，然后分類使用不同的從屬點的判斷閾值以解決這一問題[]。

定義10相對高密度簇中心：假設數據對象 i 是被決策圖選取出的簇中心，當且僅當 i 滿足如下

Step3：對于隊列中的相對高密度簇中心 n 設定為2，低密度簇中心 n 設定為3，并找到其鄰居點 i 并檢查其是否已經被分配過標簽且和其一階共享最近鄰的數量是否大于 ，如果都滿足則將 i 分配給該簇，并且將 i 加入隊列 ，并且重復迭代擴展隊列 ;

Step4：初始化創建數組 A ，將未被分配的點的索引加入數組中，檢查剩下未被分配的點的鄰居點的分配情況，查詢每個簇在鄰居點里的數量，找到數量最多的簇，將其分配到數量最多的簇里；

Step5：更新數組 A ，去除已經分配的點，如果仍然有未被分配的點，重復Step4;

Step6：如果依然有未被分配的點，則 k+1 。

輸出：聚類結果 ?=（C₁，C₂，…，C_m） ， m 為簇的個數。

3 對比實驗

該算法在Jain、Pathbased、Compound-2、Aggre-gation數據集上進行實驗。表1列出了數據集的具體信息，本實驗采用調整后的互信息（AMI）、調整后的蘭德系數（ARI和Fowlkes-Mallows指標（FMI）3個常用的聚類算法評價指標進行算法性能評估。

3.1實驗結果

本節展示算法DPC-NN-WSNN在4個數據集上相較于DBSCAN，DPC，SNN-DPC算法的優勢，圖4至圖7分別可視化了在4種數據集上聚類算法的結果圖，表2列出了4組聚類評價指標的對比。

表1實驗數據集Tab.1 Experimentaldatasets

3.2 分析與評估

根據聚類結果圖和聚類評價指標的表格，優化算法DPC-NN-WSNN在4個數據集上有著相等甚至更好的聚類效果，而在簇間密度差異較大的Compound-2和Jain數據集上聚類準確性有著顯著提升。故相比于其余3個聚類算法，本文提出的基于自然和加權共享最近鄰的密度峰值聚類算法不僅能發現并利用數據集潛在的結構和形狀信息，避免了稀疏簇的遺漏，同時也能更為準確地識別簇中心并且完成聚類后續標簽的分配。

圖44種算法在Jain的聚類結果對比

圖54種算法在Pathbased的聚類結果對比

圖64種算法在Compound-2的聚類結果對比 Fig.6Comparisonofclustering resultsof4algorithmsin Compound-2

圖74種算法在Aggregation的聚類結果對比 Fig.7Comparisonofclusteringresultsof 4algorithmsinAggregation

表24種算法在4個數據集的評價指標對比Tab.2 Comparison ofevaluation indicatorsof 4algorithmsin4datasets

4結論

采用在不同數據集上進行對比實驗的方法，針對DPC各種不足之處進行了相關改進，得出以下結論。

1）為了使DPC算法能在識別不同形狀和不同密度的簇時有更好的表現，在傳統DPC算法的基礎上提出了一種基于自然和加權共享最近鄰的密度峰值聚類算法，在多個數據集上的實驗結果表明，DPC-NN-WSNN算法在應對復雜形狀和簇間稀疏程度差異大的數據上具有明顯的優勢，聚類精度更高。

2）該算法加入二階共享最近鄰導致時間復雜度較高，如何對該算法進行降維以適應高維數據集可以作為未來繼續探索研究的方向。

3）該算法在處理包含噪聲點和識別簇間有連接部分的數據集時聚類效果有所下降，如何去除噪聲點的影響和對連接部分的數據點進行準確的分配可以作為未來繼續探索研究的方向。

參考文獻：

[1]王森，邢帥杰，劉琛.密度峰值聚類算法研究綜述[J].華 東交通大學學報，2023，40（1）：106-116. WANG S，XING SJ，LIU C. Survey of density peak clustering algorithm[J].Journal of East China Jiaotong University，2023，40（1）： 106-116.

[2]RODRIGUEZ A，LAIO A. Clustering by fast search and find of density peaks[J]. Science，2014，344（6191）：1492- 1496.

[3]XING S，SUQM，XIONGYJ，et al.PDCSN： a partition density clustering with self-adaptive neighborhoods[J]. Expert Systemswith Applications，2023，227：120195.

[4]LIUYH，MA ZM，YUF.Adaptive density peak clusteringbased on K-nearest neighbors with aggregating strategy[J].Knowledge-Based Systems，2017，133：208-220.

[5]ZHANG ZY， ZHU Q S， ZHU F， et al.Density decay graph-based densitypeak clustering[J].Knowledge-Based Systems，2021，224：107075.

[6]GUO W J，WANG WH， ZHAO S P， et al. Density peak clustering with connectivity estimation[J]. KnowledgeBased Systems，2022，243：108501.

[7]CHENG D D， ZHANG S L，HUANG JL.Dense members of local cores-based density peaks clustering algorithm[J].Knowledge-Based Systems，2020，193：105454.

[8]LIU R，WANG H， YU X M. Shared- nearest- neighborDaseq ciustering by Iast searcn anq Inu oI qensity peaks[JJ. Information Sciences，2018，450：200-226.

[9] 王芙銀，張德生，肖燕婷.基于加權共享近鄰與累加序列 的密度峰值算法[J].計算機工程，2022，48（4）：61-69. WANG FY， ZHANG D S， XIAO Y T. Density peak algorithm based onweighted shared nearest neighbor and accumulated sequence[J]. Computer Engineering，2022， 48 （4）： 61-69.

[10] ZHUQS，FENGJ，HUANGJL.Natural neighbor：a selfadaptive neighborhood method without parameter K[J]. Pattern Recognition Letters，2016，80： 30-36.

[11] ZHAO J，WANG G，PANJS， et al.Density peaks clustering algorithm based on fuzzy and weighted shared neighbor for uneven density datasets[J]. Pattern Recognition， 2023，139：109406.

[12] GUANJY，LI S， ZHUJH， et al. Fast main density peak clustering within relevant regions via a robust decision graph[J].Pattern Recognition，2024，152：110458.

[13]徐曉，丁世飛，丁玲.密度峰值聚類算法研究進展[J].軟 件學報，2022，33（5）：1800-1816. XU X，DING SF，DING L.Survey on density peaks clustering algorithm[J].Journal of Software，2022，33（5）： 1800-1816.

[14]孫林，秦小營，徐久成，等.基于K近鄰和優化分配策略 的密度峰值聚類算法[J].軟件學報，2022，33（4）：1390- 1411. SUN L， QIN X Y， XUJ C，et al. Density peak clustering algorithm based on K -nearest neighbors and optimized allocation strategy[J]. Journal of Software，2022，33（4）： 1390-1411.

[15]呂莉，朱梅子，康平，等.面向密度分布不均數據的混合 近鄰密度峰值聚類算法[J].控制理論與應用，2024，41 （10）： 1821-1830. LYULI， ZHUMZ，KANGP， et al.Multiplex neighbor density peaksclustering for uneven density data sets[J]. Control Theory amp; Applications，2024，41（10）：1821- 1830.

[16]丁志成，葛洪偉.優化分配策略的密度峰值聚類算法[J]. 計算機科學與探索，2020，14（5）：792-802. DING Z C，GE H W. Density peaks clustering with optimized allocation strategy[J].Journal of Frontiersof ComputerScienceand Technology，2020，14（5）：792-802.

[17]趙嘉，姚占峰，呂莉，等.基于相互鄰近度的密度峰值聚 類算法[J].控制與決策，2021，36（3）：543-552. ZHAOJ，YAOZF，LYUL，etal.Densitypeaksclusteringbased on mutual neighbor degree[J].Control and Decision，2021，36（3）：543-552.

第一作者：王森（1969一），男，教授，碩士生導師，研究方向計算機算法與應用。E-mail：0012@ecjtu.edu.cn。

通信作者：陳翔（1998一），男，碩士研究生，研究方向為聚類分析與數據挖掘。E-mail：2022088085410004@ecjtu.edu.cn。

（責任編輯：姜紅貴）