二階自然最近鄰和多簇合并的密度峰值聚類算法

張紫丹 徐華 楊重陽

摘 要：密度峰值聚類（density peaks clustering，DPC）算法基于局部密度和相對距離識別簇中心，忽視了樣本所處環境對樣本點密度的影響，因此不容易發現低密度區域的簇中心；DPC算法采用的單步分配策略的容錯性差，一旦一個樣本點分配錯誤，將導致后續一系列樣本點分配錯誤。針對上述問題，提出二階自然最近鄰和多簇合并的密度峰值聚類算法（TNMMDPC）。首先，引入二階自然鄰居的概念，同時考慮樣本點的密度與樣本點所處的環境，重新定義了樣本點的局部密度，以降低類簇的疏密對類簇中心選擇的影響；其次，定義了核心點集來選取初始微簇，依據樣本點與微簇間的關聯度對樣本點進行分配；最后引入了鄰居邊界點集的概念對相鄰的子簇進行合并，得到最終的聚類結果，避免了分配錯誤連帶效應。在人工數據集和UCI數據集上，將TNMMDPC算法與DPC及其改進算法進行了對比，實驗結果表明，TNMMDPC算法能夠解決DPC算法所存在的問題，可以有效聚類人工數據集和UCI數據集。

關鍵詞：密度峰值；自然鄰居；局部密度；核心點集；子簇合并

中圖分類號：TP301?? 文獻標志碼：A?? 文章編號：1001-3695（2023）12-006-3559-07

doi：10.19734/j.issn.10013695.2023.04.0162

Secondorder natural nearest neighbors and multiclusters merge density peaks clustering algorithm

Abstract：The DPC algorithm identifies cluster centers based on local density and relative distance，ignoring the influence of the sample environment on the sample point density，so it is not easy to find cluster centers in lowdensity areas.The singlestep allocation strategy of the DPC algorithm has poor fault tolerance，and once a sample point allocation error occurs，it will lead to a series of sample point allocation errors in the followup.To solve the above problems，this paper proposed a density peak clustering algorithm （TNMMDPC） based on secondorder natural nearest neighbor and multicluster merging.Firstly，it introduced the concept of secondorder natural neighbor and considered the density of the sample point and the environment of the sample point at the same time，it redefined the local density of the sample point to reduce the influence of cluster density on the selection of cluster center.Secondly，it defined the core point set to select the initial micro clusters，and allocated the sample points according to the correlation degree between the sample points and the micro clusters.Finally，it introduced the concept of neighbor boundary point set to merge the adjacent subclusters to obtain the final clustering results，avoiding the cascade effect of allocation errors.This paper compared TNMMDPC algorithm with DPC and its improved algorithm on the artificial dataset and the UCI dataset，and the experimental results show that the TNMMDPC algorithm can solve the problems existing in the DPC algorithm and can effectively cluster the artificial dataset and UCI dataset.

Key words：peak density；natural neighbors；local density；core point set；microcluster merging

0 引言

聚類是數據挖掘和機器學習領域中的一個基本但具有挑戰性的主題，它在模式識別中的語音識別和字符識別、機器學習中的圖像分割和機器視覺領域扮演著重要的角色。除此之外，它在統計學、生物學、心理學等領域也起著重要作用。

在過去的幾十年中，許多聚類算法被提出。目前，典型的聚類算法包括基于劃分的Kmeans［1］、MeanShift［2］、基于層次的CHAMELEON［3］、基于網格的CLIQUE［4］、基于密度的DBSCAN［5］以及基于圖論的Spectral Clustering（SC）［6］等。基于密度的聚類算法容易識別出任意形狀的簇，這類算法從樣本密度的角度出發來考慮，考查樣本之間的可連接性，基于可連接樣本擴展聚類簇已獲得最終的聚類結果。典型的基于密度的算法有DBSCAN、OPTICS［7］和DENCLUE［8］算法，其中DBSCAN是最廣為人知。隨后，Mihael等人提出了OPTICS算法，該算法將DBSCAN算法中所需的輸入參數指定為一個范圍，給出了點的可達距離圖像來對數據進行聚類。DENCLUE算法引入影響函數和密度函數的概念用于進行基于密度的聚類。

2014年，Rodriquez等人［9］提出了密度峰值聚類（density peaks clustering，DPC）算法。DPC可以很容易地發現由低密度區域分隔的高密度區域。與Kmeans算法相比，DPC可以自動獲取類簇的數量，而且算法的復雜度較低。與DBSCAN相比，DPC可以在嘈雜的環境中對任意形狀的數據集進行聚類。與MeanShift算法相比，DPC僅考慮點與點之間的距離，無須將數據映射到向量空間。DPC算法原理簡單，它根據給定的截斷距離來計算每個點的局部密度及每個點的相對距離；然后，將所有樣本點的局部密度和相對距離的乘積按降序繪制在決策圖上人為選擇簇中心；最后將未分配點分配給距離該點最近且局部密度更高的樣本點所在的簇。但是，DPC的聚類性能通常受截斷距離、密度峰值、簇中心的選擇以及數據點的分配所影響。DPC算法需要確定截斷距離來計算局部密度，同時局部密度的計算給出了兩種計算公式，沒有統一，DPC算法基于局部密度和相對距離識別簇中心，忽視了樣本點所處環境對樣本點局部密度的影響，因此不容易發現低密度區域的簇中心，導致算法對密度分布不均的數據集聚類效果不理想。由于從決策圖中選取簇中心受人為選擇的影響，導致當數據集中的某個簇出現多個密度峰時，簇中心的選擇存在不統一的情況。除此之外，DPC算法采用的單步分配策略的容錯性差，一旦一個樣本點分配錯誤，將導致后續一系列樣本點分配錯誤，聚類效果不佳。

針對DPC算法存在的缺陷，國內外學者提出諸多改進方法。針對DPC算法局部密度度量方式不統一和分配策略容錯性差的缺陷，Mehmood等人［10］提出了一種FuzzyCFSFDP算法，通過非參數密度估計方法計算局部密度。鮑舒婷等人［11］通過結合歐氏距離和共享近鄰來定義樣本的局部密度，減少了算法對參數截斷距離dc的依賴。薛小娜等人［12］ 將KNN引入進局部密度計算并設計了新的分配策略。Seyed等人［13］基于KNN重新定義了局部密度，提出了DPCDLP算法，同時基于圖的動態標簽分配策略來分配樣本點。Liu等人［14］提出了SNNDPC算法，該算法基于共享鄰居改進了局部密度和相對距離，同時提出了兩步分配策略以提高非中心的分配的準確性。Cheng等人［15］提出了一種DLOREDP算法，該算法基于局部核心密集成員優化局部密度的度量。Liu等人［16］提出了一種DPCWKNNGD算法，基于加權K近鄰和測地距離優化DC的局部密度。Tao等人［17］引入一種具有指數項和尺度因子的流行距離來計算局部密度。趙嘉等人［18］利用K近鄰思想給出局部密度的度量準則。針對數據集中某個簇出現多個密度峰時，DPC算法難以準確識別簇中心的問題，Liang等人［19］提出的3DC算法具有準確識別簇中心的能力。Zhang等人［20］提出了一種基于密度衰減圖的密度峰值聚類（DGDPC）算法，該算法使用密度衰減圖自動形成初始簇，然后通過簡單的方法合并簇，從而避免手動選擇簇中心。丁世飛等人［21］提出了基于不相似性度量優化的密度峰值聚類算法（DDPC），利用基于塊的不相似度量代替簡單的幾何距離度量，重新考慮了樣本之間的距離關系。彭啟慧等人［22］提出了分布的自動閾值密度峰值聚類算法，解決了聚類中心不能自動選取的缺陷。

針對DPC算法的不足之處，本文引入自然鄰居（natural neighbor，NN）［23］的概念，同時考慮樣本點的密度與樣本點所處的環境對樣本點局部密度的；算法定義了核心點集，根據決策值選取樣本點及其自然鄰居集作為核心點集，然后計算樣本點與子簇間的關聯度對樣本點進行分配，最后對相鄰的子簇進行合并，得到最終的聚類結果，避免了分配錯誤連帶效應，同時解決了DPC算法在多密度峰出現在同一個簇時簇中心選擇不準確的問題。

1 DPC算法與缺陷

DPC算法可以自動發現簇中心，實現任意形狀數據的高效聚類。簇中心的選取關鍵是簇中心的兩大特征：a）簇中心的局部密度大于圍繞它的鄰居點的局部密度；b）不同簇中心之間的距離相對較遠。

首先計算每個樣本點的局部密度ρi和相對距離δi。

局部密度的計算方式有兩種，對于大規模數據集選擇截斷核，即式（1）；對于小規模數據集選擇高斯核，即式（2）。

其中：dij為樣本點i和j之間的歐氏距離；dc為截斷距離，是事先人為指定的唯一輸入參數，一般選擇為所有樣本點歐氏距離降序的2%位置處的距離。

對于數據集中密度最大的點來說，相對距離δi為所有樣本點歐氏距離的最大值；對于其余樣本點來說，相對距離δi即計算當前樣本點到局部密度比該樣本點大且距離它最近的點的歐氏距離。計算公式如下：

至此，對于數據集中的每一個樣本點xi，可以算得它的兩個參數（ρi，δi），即局部密度和相對距離。有了這兩個參數之后，便可以尋找聚類中心，即（ρi，δi）都大的數據點就是簇中心點。計算樣本點的決策值γi，選擇決策值較大的樣本點作為簇中心，計算公式如下：

γi=ρi·δi（4）

除了通過決策值來選取簇中心，也可以繪制出ρδ決策圖，選取決策圖右上角部分的點作為簇中心，這些點的ρi值和δi值較大。

確定了簇中心后，其他非中心點被劃分到距離其最近的高密度鄰居的相同簇中。

DPC算法不僅沒有統一高斯核和截斷核的局部密度定義方式，且這兩種定義方式均與截斷距離有關，對于不同的數據集，截斷距離的最佳取值存在較大差異；此外，DPC算法的局部密度主要由截斷距離內的樣本點決定，截斷距離外的樣本點對局部密度的影響很低，導致稀疏區域不容易識別出密度峰值。

DPC算法默認數據集中的每個簇有且只能有一個密度峰，因此，當數據集中的某個簇出現多個密度峰時，人為選擇簇中心的不確定性會導致DPC算法無法準確識別簇中心［24］。

在分配剩余樣本時，DPC算法只考慮了樣本點的密度與距離之間的關系，使得DPC算法雖然能在一些簡單數據集上獲得較好的聚類結果，但對于流型數據集易出現本應屬于同一個簇的樣本被錯誤分配給其他簇，且一旦一個樣本點被分配錯誤，之后一系列的樣本點均被分配錯誤，導致發生分配錯誤連帶效應。

2 自然鄰居

傳統的K最近鄰居（Knearest neighbor，KNN）［25］是一種最經典和最簡單的有監督學習方法之一。在KNN算法思想中，k值的確定是由先驗知識給出的，算法原理簡單。給定數據集X，對于任意的樣本點xi，xi的K最近鄰為數據集中距離該樣本點最近的k個樣本點集合，記為KNNk（xi），自然鄰居無須手動設置參數就能自動形成鄰居關系［26］。自然鄰居是以傳統的KNN算法為基礎，在查找自然鄰居的過程中從k=1開始，自動地對k值進行遞增，并同時觀察所有樣本點相互之間互為鄰居的狀態，以確定是否達到自然穩定狀態。算法自動執行到自然穩定狀態時即可獲取數據集中各個數據點之間的自然鄰居關系，同時得到自然鄰居特征值。由于自然鄰居算法更多地考慮到了數據相互間的分布狀態，所以相比于K最近鄰居更好地體現了鄰居的特性［27］。該算法使得分布在密集區域的樣本點具有更多的自然鄰居，而分布在稀疏區域的點則具有更少的自然鄰居。

定義1 自然穩定狀態［28］。 對于具有N個樣本點的數據集X，搜索次數r從1開始取值，每次增加1，對X進行k=r的K最近鄰居的查找，直到數據集X中的所有樣本點均至少存在另一個樣本點與其互為鄰居，則當前的搜索狀態被稱之為自然穩定狀態。當滿足以下限定條件時達到自然穩定狀態：

（xi）（xj）（r∈N）∧（xi≠xj）→（xi∈KNN（xj））∧（xj∈KNNr（xi））（5）

定義2 自然鄰居特征值λ［28］。當數據集X處于自然穩定狀態時，此時的r為數據集X的自然特征值λ。

定義3 自然鄰居NN［28］。當數據集X處于自然穩定狀態時，互為鄰居的樣本點互為彼此的自然鄰居，即對于樣本點xi，如果另一個樣本點xj與它互為K最近鄰居，則樣本點xj是樣本點xi的自然鄰居。定義如下：

xj∈NN（xi）（xi∈KNNλ（xj））∧（xi∈KNNλ（xj））（6）

K最近鄰居搜索函數findKNN（xi，r）返回數據集X中任意樣本點xi的第r個最近鄰居。自然鄰居搜索算法的步驟如下：

輸入：數據集X。

輸出：自然鄰居特征值λ，樣本點xi的自然鄰居集合NN（xi）。

a）初始化搜索次數r=1，自然近鄰數nb=和自然鄰居集合NN=；

b）計算每個樣本點xi的r近鄰、nb（xi）及NN（xi）；

c）r=r+1；

d）當xi使得NN（xi）≠或nb（xi）==0的數量不再變化時，λ=r，輸出λ和NN，否則跳轉至b）。

3 TNMMDPC算法

3.1 簇中心選擇

簇中心的選擇在DPC算法中是很重要的一步，根據樣本點的局部密度和相對距離來得到決策值，選取決策值較大的點為簇中心點。TNMMDPC算法首先重新定義了樣本點的局部密度。

TNMMDPC算法對樣本局部密度定義的同時考慮了樣本點之間的距離和與樣本點所處的環境。該算法將二階自然最近鄰的概念納入局部密度的設計中。因為它可以更好地表達點之間的接近關系，從而更準確、更自然地評估每個點的局部密度。與通過截斷距離或K最近鄰方法計算的局部密度相比，該算法使得每個點的局部密度可以在無須手動參數的情況下自適應計算，因此具有魯棒性。

根據自然鄰居搜索算法可以得到數據集的自然鄰居特征值λ和每個樣本點的自然鄰居集合，自然鄰居特征值在一定程度上反映了樣本點的鄰居特性。

定義4 二階自然鄰居NNN（i）。基于自然鄰居思想，二階自然鄰居的定義如下：

定義5 局部密度ρi?；谧匀秽従铀枷?，新的樣本局部密度定義為

其中：distij為樣本點xi和xj之間的歐氏距離；NN（i）為樣本點xi的自然鄰居集合；∑j∈NN（i）distij可以體現樣本點xi在它自然鄰居點上的離群程度，該值越大，樣本點xi周圍的樣本點越稀疏；∑v∈NN（j）∑j∈NN（i）distvj為樣本點xi的二階自然鄰居的離群程度之和，該值越大，該點的局部密度越大。

ρi的計算分為兩個部分：第一個部分僅關注樣本點和它的自然鄰居點間的距離，該值越小，局部密度越大；第二部分關注樣本點所處環境的樣本分布，計算的是該點與其自然鄰居點的相對密度，能夠調節不同的樣本分布中樣本點的局部密度，避免簇中心的選擇集中在同一個密集區域。通過這兩個部分的結合來共同定義樣本點的局部密度，在考慮樣本點距離的同時也考慮到樣本點周圍的分布情況。

然后根據式（3）和（4）計算每個樣本點的決策值，將決策值從大到小排序，選擇前m（m值根據數據集的大小來定，一般取數據集樣本點個數的1%～3%）個樣本點作為初始簇中心。

定義6 核心點集。若初始簇中心中自然鄰居點的局部密度大于平均局部密度的個數多于該樣本點自然鄰居點的一半，則這個初始簇中心被選為簇中心。同時，將簇中心及其自然鄰居點定義為核心點集。

圖1為TNMMDPC算法通過式（8）（3）和（4）為pathbased數據集選取的簇中心點，以“+”形式顯示，其周圍的點集為選出來的核心點集。從圖中可以看出，算法選擇出來的五個簇中心點沒有全部聚集在兩個密集簇中，在稀疏簇中也有三個簇中心被選擇了出來。由此可以看出，本文算法定義的局部密度增加了樣本點所處環境的影響，稀疏簇的簇中心也能被選擇出來，更加準確地表征了密度峰值的特性。

3.2 分配策略

TNMMDPC算法定義了樣本點之間的相似度和樣本點與子簇之間的關聯度來進行樣本點的分配。

定義7 點間相似度ωij。樣本點xi和xj之間的相似度定義為

定義8 點簇關聯度Ri→Cj［29］。 樣本點xi和微簇Cj之間的相似度定義為

樣本點xi和xj之間的相似度根據兩個樣本點之間的歐氏距離distij來定義，若兩個樣本點之間的距離越小，則相似度越高。微簇Cj中的每個樣本點v和樣本點xi之間的相似度的平均值定義為點簇關聯度。

將已選擇出的核心點集作為初始微簇，并將其中的樣本點標記為已分配樣本。計算每個未分配點與其他各微簇的點簇關聯度矩陣，通過點簇關聯度矩陣找到所有未分配樣本點中與微簇關聯度最高的樣本點，將該樣本點分配給相應微簇，重新計算點簇關聯度并更新關聯度矩陣，重新將關聯度最高的樣本點進行分配，重復上述操作，直到所有的樣本點均分配完成。

3.3 多簇合并策略

將所有樣本點分配給與它關聯度最高的微簇后，可以得到若干個子簇。

TNMMDPC算法提出了新的合并策略來合并相鄰的子簇。

定義9 簇平均距離meandist。對任意一個簇A，簇平均距離是簇A中所有點間歐氏距離的平均值。

定義10 鄰居邊界點集。對任意兩個簇A和B，簇A中存在一個樣本點xi，簇B中存在一個樣本點xj，樣本點xi和xj互為自然鄰居，則稱這樣的點對（xi，xj）為鄰居邊界點對。兩個簇中所有鄰居邊界點對的集合稱為鄰居邊界點集，公式化定義為

bound（A，B）={i，j|i∈NN（j） and j∈NN（i），i∈A，j∈B，A≠B}（11）

其中：bound（A，B）表示簇A和簇B的鄰居邊界點集；NN（i）表示樣本點xi的自然鄰居集。

當兩個子簇A和B符合合并條件時，表示子簇A和B相距較近且兩個簇邊界點的分布較密集，鄰居邊界點集中的點應該位于子簇A和B的連接區域，因此將這兩個子簇進行合并處理。

3.4 TNMMDPC算法步驟和復雜度分析

原始DPC算法在根據截斷距離計算局部密度和相對距離之后選取簇中心，然后根據歐氏距離來分配剩余樣本點。本文算法在計算樣本點的歐氏距離后，在自然鄰居搜索算法的基礎上得到每個樣本點的自然鄰居集合，用自然鄰居集合代替了截斷距離來計算局部密度；然后根據決策值選取多個核心點并擴展為核心點集來進行樣本點的初始分配；最后進行多簇合并，得到最后的聚類結果。TNMMDPC算法的步驟如下：

輸入：數據集X。

輸出：聚類結果C。

a）對數據進行歸一化；

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

c）根據自然鄰居搜索算法得到每個樣本點的自然鄰居集合；

d）根據式（8）計算樣本點的局部密度ρi；

e）根據式（3）計算樣本點的相對距離δi；

f）根據式（4）計算樣本點的決策值γi，選取決策值較大的樣本點作為潛在的初始簇中心，若初始簇中心中自然鄰居點的局部密度大于平均局部密度的個數多于自然鄰居點的一半，則這個初始簇中心被選為簇中心，同時將簇中心及其自然鄰居點選取為核心點集，作為初始微簇；

g）根據式（8）計算樣本點間的相似度ωij；

h）根據式（9）計算每個未分配點和初始微簇的點簇關聯度Ri→Cj，構造關聯度矩陣；

i）將關聯度矩陣中關聯度最高的樣本點分配給相對應的微簇，重新計算點簇關聯度并更新關聯度矩陣；

j）重復步驟i），直到所有樣本點均分配完成；

k）對任意兩個子簇A和B，分別計算其平均簇距離meandistA和meandistB；

DPC算法的時間復雜度主要由以下三部分組成：a）計算樣本間距離的時間復雜度為O（n2）；b）計算樣本局部密度的時間復雜度為O（n2）；c）計算樣本間相對距離的時間復雜度為O（n2）。綜上，DPC算法總的時間復雜度為O（n2）。TNMMDPC算法時間復雜度主要由以下五部分組成：a）計算樣本間的歐氏距離的時間復雜度為O（n2）；b）自然鄰居搜索算法的整體時間復雜度為O（n log n）；c）計算樣本局部密度的時間復雜度為O（n2）；d）非簇中心樣本點分配給微簇過程中的時間復雜度為O（n2）；e）多簇合并過程的時間復雜度為O（n2）。綜上，本文算法的時間復雜度為O（n2），與DPC算法的時間復雜度量級相同。

4 實驗結果與分析

將提出的TNMMDPC算法與DPC、SNNDPC和DBSCAN算法在人工數據集和UCI數據集上進行比較。DPC和DBSCAN算法的實驗結果基于作者提供的源代碼，在PyCharm2021中實現。SNNDPC算法參照原文獻使用PyCharm2021編程實現。

本文使用三個評價指標評估聚類結果，即調整蘭德系數（adjusted Rand index，ARI）、調整互信息（adjusted mutual information，AMI）、FowlkesMallows指數（FowlkesMallows index，FMI），ARI和AMI都是用來衡量兩個分布的吻合程度，取值為［-1，1］，數值越接近1越好，FMI是對聚類結果和真實值計算得到的召回率和精確率，進行幾何平均的結果，取值為［0，1］，數值越接近1越好。

4.1 數據集介紹

實驗選擇了十個人工數據集和幾個來自UCI上的真實數據集進行實驗，數據集的具體屬性分別如表1和2所示。

4.2 人工數據集實驗結果分析

表3給出了所有四種算法對表1中十個人工數據集的實驗結果，其中，TNMMDPC、SNNDPC和DBSCAN算法均選取最優參數得到最優的實驗結果。

從表3可以看出，在處理aggregation數據集和R15數據集時，TNMMDPC算法的聚類效果略低于其他三個聚類算法，在剩余的八個數據集上，TNMMDPC算法的聚類效果要優于或持平其他三個聚類算法。SNNDPC算法在spiral、pathbased、LineBlobs和cth3數據集上的效果較好，但在其他四個數據集上的聚類效果較差，其中在jain、ls3和d6數據集上的聚類結果明顯錯誤。DPC算法僅在spiral、aggregation和R15數據集上的效果較好，在其他幾個數據集上的聚類結果明顯錯誤。DBSCAN算法在spiral、LineBlobs、cth3和ls3數據集上的效果較好，但在其他四個數據集上的聚類效果較差，其中在pathbased數據集上的聚類結果明顯錯誤。綜合比較四種算法在十個數據集上的聚類結果可知，TNMMDPC算法的聚類效果優于其他三個算法。

圖2～8展示了TNMMDPC、SNNDPC、DPC和DBSCAN算法在jain、flame、pathbased、LineBlobs、cth3、ls3和d6數據集上的聚類結果，其中相同顏色的點屬于同一聚類，在DBSCAN聚類算法的聚類結果中，黑色點代表算法選取出來的噪聲點（見電子版）。

圖2顯示了四種算法對jain數據集的聚類結果。jain數據集由兩個倒過來的U型類簇組成，且下半部分的簇數據點分布密集，上半部分倒過來的U型簇數據點分布稀疏。從圖2可以看出，除TNMMDPC算法外，其余三個算法均聚類錯誤。SNNDPC和DPC算法均將兩個簇中心選取到了數據點分布密集的下半部分，數據集的稀疏區域沒有樣本點被選為聚類中心。DBSCAN算法甚至將jain數據集分成了四個簇。

圖3顯示了四種算法對flame數據集的聚類結果。flame數據集樣本點分布較為均勻，但兩個簇的邊界不易區分。四種算法對flame數據集的聚類效果相差不大。圖4顯示了四種算法對pathbased數據集的聚類結果。從圖中可以看出，pathbased數據集是一個復雜的流形數據集，由三個簇組成，一個環形簇包圍了兩個簇，由于兩個內部簇和環形簇連接部TNMMDPC和SNNDPC算法的聚類結果相差不大，大體能將pathbased數據集正確分為三類，DPC算法將環形簇的部分錯誤分配給了兩個內部簇，而DBSCAN算法則聚類錯誤。圖5和6顯示了四種算法對LineBlobs和cth3數據集的聚類結果。LineBlobs數據集形如笑臉，從圖5（c）中可以看出，DPC算法將笑臉的下圓弧部分錯誤分配給了兩個方形簇，從圖6（c）中可以看出，DPC算法將外圈的簇部分因分配錯誤的連帶效應錯誤地分配給了內部簇，而其他三個算法均聚類正確。圖7和8顯示了四種算法在ls3和d6數據集上的聚類結果。從圖中可以看出，TNMMDPC和DBSCAN算法均能正確聚類，SNNDPC和DPC算法均聚類錯誤。

4.3 UCI數據集實驗結果分析

UCI數據集的屬性較多、維數較高，聚類難度比人工數據集更高。為進一步驗證TNMMDPC算法的聚類性能，在表2給出的四個UCI數據集上對TNMMDPC和SNNDPC、DPC、DBSCAN算法進行了比較。四種算法對UCI數據集的聚類結果如表4所示。

實驗結果表明，處理iris數據集時，TNMMDPC算法的聚類效果低于SNNDPC和DPC算法，但高于DBSCAN算法。在處理ecoli和seeds數據集時，TNMMDPC算法的聚類效果優于其他三個算法。處理zoo數據集時，TNMMDPC算法的聚類效果低于SNNDPC算法，但高于DPC和DBSCAN算法。

5 結束語

針對DPC算法局部密度定義的度量準則不統一導致的稀疏類簇不易被發現簇中心和分配策略產生的分配連帶錯誤等問題，本文提出了自然最近鄰和多簇合并的密度峰值聚類算法，簡寫為TNMMDPC算法。TNMMDPC算法引入了自然鄰居的概念，重新定義了局部密度，增強了樣本點所處環境對樣本點局部密度的影響，并引入了核心點集的概念，在選取簇中心的基礎上選擇出了核心點集。此外，TNMMDPC算法定義了樣本點之間的相似度和樣本點與微簇之間的關聯度來進行樣本點的分配。最后，引入了鄰居邊界點集的概念，通過比較簇平均密度合并相鄰的子簇。在人工數據集和UCI數據集上的實驗結果表明，TNMMDPC算法有較好的聚類效果。

參考文獻：

［1］Jain A K.Data clustering：50 years beyond Kmeans［J］.Pattern Recognition Letters，2010，31（18）：651-666.

［2］Fukunaga K，Hostetler L.The estimation of the gradient of a density function，with applications in pattern recognition［J］.IEEE Trans on Information Theory，1975，21（1）：3240.

［3］Katherine D，Suvra P，Siddiqua J A.Stochastic EM algorithm for generalized exponential cure rate model and an empirical study［J］.Journal of Applied Statistics，2021，48（12）：21122135.

［4］Sun Shaopeng，Hou Kaihu，Chen Lihua.The improvement of the CLIQUE algorithm based on high dimensional data cleaning［J］.Advance Material Research，2012，452453：381385.

［5］Ester M，Kriegel H P，Sander J，et al.A densitybased algorithm for discovering clusters in large spatial databases with noise［C］//Proc of the 2nd International Conference on Knowledge Discovery and Data Mining.Palo Alto，CA：AAAI Press，1996：226-231.

［6］Luxburg U V.A tutorial on spectral clustering［J］.Statistics and Computing，2007，17（4）：395-416.

［7］Ankerst M，Breunig M M，Kriegel H P，et al.OPTICS：ordering points to identify the clustering structure［C］//Proc of ACM SIGMOD International Conference on Management of Data.New York：ACM Press，1999：4960.

［8］Hinneburg A，Keim D A.An efficient approach to clustering in large multimedia databases with noise［C］//Proc of the 4th International Conference on Knowledge Discovery and Data Mining.Palo Alto，CA：AAAI Press，1998：58-65.

［9］Rodriguez A，Laio A.Clustering by fast search and find of density peaks［J］.Science，2014，344（6191）：14921496.

［10］Mehmood R，Zhang Guangzhi，Bie Rongfang，et al.Clustering by fast search and find of density peaks via heat diffusion［J］.Neurocomputing，2016，208：210217.

［11］鮑舒婷，孫麗萍，鄭孝遙，等.基于共享近鄰相似度的密度峰聚類算法［J］.計算機應用，2018，38（6）：16011607.（Bao Shuting，Sun Liping，Zheng Xiaoyao，et al.Density peaks clustering algorithm based on shared near neighbors similarity［J］.Journal of Computer Applications，2018，38（6）：16011607.）

［12］薛小娜，高淑萍，彭弘銘，等.結合K近鄰的改進密度峰值聚類算法［J］.計算機工程與應用，2018，54（7）：3643.（Xue Xiaona，Gao Shuping，Peng Hongming，et al.Improved density peak clustering algorithm combined with K nearest neighbors［J］.Computer Engineering and Applications，2018，54（7）：36-43.）

［13］Seyedi S A，Lotfi A，Moradi P，et al.Dynamic graphbased label propagation for density peaks clustering［J］.Expert Systems with Applications，2019，115：314328.

［14］Liu Rui，Wang Hong，Yu Xiaomei.Sharednearestneighborbased clustering by fast search and find of density peaks［J］.Information Sciences，2018，450：200226.

［15］Cheng Dongdong，Zhang Sulan，Huang Jinlong.Dense members of local coresbased density peaks clustering algorithm［J］.KnowledgeBased Systems，2020，193：105454.

［16］Liu Lina，Yu Donghua.Density peaks clustering algorithm based on weighted knearest neighbors and geodesic distance［J］.IEEE Access，2020，8：168282168296.

［17］Tao Xinmin，Guo Wenjie，Ren Chao，et al.Density peak clustering using global and local consistency adjustable manifold distance［J］.Information Sciences，2021，577：769804.

［18］趙嘉，姚占峰，呂莉，等.基于相互鄰近度的密度峰值聚類算法［J］.控制與決策，2021，36（3）：543552.（Zhao Jia，Yao Zhanfeng，Lyu Li，et al.Density peak clustering algorithm based on mutual proximity［J］.Control and Decision，2021，36（3）：543552.）

［19］Liang Zhou，Chen Pei.Deltadensity based clustering with a divideandconquer strategy：3DC clustering［J］.Pattern Recognition Letters，2016，73：52-59.

［20］Zhang Zhiyong，Zhu Qingsheng，Zhu Fan，et al.Density decay graphbased density peak clustering［J］.KnowledgeBased Systems，2021，224：107075.

［21］丁世飛，徐曉，王艷茹.基于不相似性度量優化的密度峰值聚類算法［J］.軟件學報，2020，31（11）：33213333.（Ding Shifei，Xu Xiao，Wang Yanru.Optimized density peaks clustering algorithm based on dissimilarity measure［J］.Journal of Software，2020，31（11）：33213333.）

［22］彭啟慧，宣士斌，高卿.分布的自動閾值密度峰值聚類算法［J］.計算機工程與應用，2021，57（5）：7178.（Peng Qihui，Xuan Shibin，Gao Qing.Automatic threshold density peak clustering algorithm for distribution［J］.Computer Engineering and Applications，2021，57（5）：7178.）

［23］馮驥.自然鄰居思想概念及其在數據挖掘領域的應用［D］.重慶：重慶大學，2016.（Feng Ji.Concept of natural neighbors and its application in data mining［D］.Chongqing：Chongqing University，2016.）

［24］徐曉，丁世飛，丁玲.密度峰值聚類算法研究進展［J］.軟件學報，2022，33（5）：18001816.（Xu Xiao，Ding Shifei，Ding Ling.Research progress of density peak clustering algorithm［J］.Journal of Software，2022，33（5）：18001816.）

［25］Xiao Qingtao，Zhong Xin，Zhong Chen.Application research of KNN algorithm based on clustering in big data talent demand information classification［J］.International Journal of Pattern Recognition and Artificial Intelligence，2020，34（6）：2050015.

［26］金輝，錢雪忠.自然最近鄰優化的密度峰值聚類算法［J］.計算機科學與探索，2019，13（4）：711720.（Jin Hui，Qian Xuezhong.Density peak clustering algorithm optimized by natural nearest neighbor［J］.Computer Science and Exploration，2019，13（4）：711720.）

［27］劉娟，萬靜.自然反向最近鄰優化的密度峰值聚類算法［J］.計算機科學與探索，2021，15（10）：18881899.（Liu Juan，Wan Jing.Density peak clustering algorithm for natural inverse nearest neighbor optimization［J］.Computer Science and Exploration，2021，15（10）：18881899.）

［28］馮驥，張程，朱慶生.一種具有動態鄰域特點的自適應最近鄰居算法［J］.計算機科學，2017，44（12）：194201.（Feng Ji，Zhang Cheng，Zhu Qingsheng.An adaptive nearest neighbor algorithm with dynamic neighborhood characteristics［J］.Computer Science，2017，44（12）：194-201.）

［29］吳潤秀，尹士豪，趙嘉，等.基于相對密度估計和多簇合并的密度峰值聚類算法［J］.控制與決策，2023，38（4）：10471055.（Wu Runxiu，Yin Shihao，Zhao Jia，et al.Density peak clustering algorithm based on relative density estimation and multicluster merging［J］.Control and Decision，2023，38（4）：10471055.）