張紫丹 徐華 楊重陽

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

關(guān)鍵詞：密度峰值；自然鄰居；局部密度；核心點(diǎn)集；子簇合并

中圖分類號：TP301?? 文獻(xiàn)標(biāo)志碼：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 引言

聚類是數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)領(lǐng)域中的一個基本但具有挑戰(zhàn)性的主題，它在模式識別中的語音識別和字符識別、機(jī)器學(xué)習(xí)中的圖像分割和機(jī)器視覺領(lǐng)域扮演著重要的角色。除此之外，它在統(tǒng)計(jì)學(xué)、生物學(xué)、心理學(xué)等領(lǐng)域也起著重要作用。

在過去的幾十年中，許多聚類算法被提出。目前，典型的聚類算法包括基于劃分的Kmeans［1］、MeanShift［2］、基于層次的CHAMELEON［3］、基于網(wǎng)格的CLIQUE［4］、基于密度的DBSCAN［5］以及基于圖論的Spectral Clustering（SC）［6］等?；诿芏鹊木垲愃惴ㄈ菀鬃R別出任意形狀的簇，這類算法從樣本密度的角度出發(fā)來考慮，考查樣本之間的可連接性，基于可連接樣本擴(kuò)展聚類簇已獲得最終的聚類結(jié)果。典型的基于密度的算法有DBSCAN、OPTICS［7］和DENCLUE［8］算法，其中DBSCAN是最廣為人知。隨后，Mihael等人提出了OPTICS算法，該算法將DBSCAN算法中所需的輸入?yún)?shù)指定為一個范圍，給出了點(diǎn)的可達(dá)距離圖像來對數(shù)據(jù)進(jìn)行聚類。DENCLUE算法引入影響函數(shù)和密度函數(shù)的概念用于進(jìn)行基于密度的聚類。

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

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

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

1 DPC算法與缺陷

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

首先計(jì)算每個樣本點(diǎn)的局部密度ρi和相對距離δi。

局部密度的計(jì)算方式有兩種，對于大規(guī)模數(shù)據(jù)集選擇截?cái)嗪?，即式?）；對于小規(guī)模數(shù)據(jù)集選擇高斯核，即式（2）。

其中：dij為樣本點(diǎn)i和j之間的歐氏距離；dc為截?cái)嗑嚯x，是事先人為指定的唯一輸入?yún)?shù)，一般選擇為所有樣本點(diǎn)歐氏距離降序的2%位置處的距離。

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

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

γi=ρi·δi（4）

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

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

DPC算法不僅沒有統(tǒng)一高斯核和截?cái)嗪说木植棵芏榷x方式，且這兩種定義方式均與截?cái)嗑嚯x有關(guān)，對于不同的數(shù)據(jù)集，截?cái)嗑嚯x的最佳取值存在較大差異；此外，DPC算法的局部密度主要由截?cái)嗑嚯x內(nèi)的樣本點(diǎn)決定，截?cái)嗑嚯x外的樣本點(diǎn)對局部密度的影響很低，導(dǎo)致稀疏區(qū)域不容易識別出密度峰值。

DPC算法默認(rèn)數(shù)據(jù)集中的每個簇有且只能有一個密度峰，因此，當(dāng)數(shù)據(jù)集中的某個簇出現(xiàn)多個密度峰時，人為選擇簇中心的不確定性會導(dǎo)致DPC算法無法準(zhǔn)確識別簇中心［24］。

在分配剩余樣本時，DPC算法只考慮了樣本點(diǎn)的密度與距離之間的關(guān)系，使得DPC算法雖然能在一些簡單數(shù)據(jù)集上獲得較好的聚類結(jié)果，但對于流型數(shù)據(jù)集易出現(xiàn)本應(yīng)屬于同一個簇的樣本被錯誤分配給其他簇，且一旦一個樣本點(diǎn)被分配錯誤，之后一系列的樣本點(diǎn)均被分配錯誤，導(dǎo)致發(fā)生分配錯誤連帶效應(yīng)。

2 自然鄰居

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

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

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

定義2 自然鄰居特征值λ［28］。當(dāng)數(shù)據(jù)集X處于自然穩(wěn)定狀態(tài)時，此時的r為數(shù)據(jù)集X的自然特征值λ。

定義3 自然鄰居NN［28］。當(dāng)數(shù)據(jù)集X處于自然穩(wěn)定狀態(tài)時，互為鄰居的樣本點(diǎn)互為彼此的自然鄰居，即對于樣本點(diǎn)xi，如果另一個樣本點(diǎn)xj與它互為K最近鄰居，則樣本點(diǎn)xj是樣本點(diǎn)xi的自然鄰居。定義如下：

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

K最近鄰居搜索函數(shù)findKNN（xi，r）返回?cái)?shù)據(jù)集X中任意樣本點(diǎn)xi的第r個最近鄰居。自然鄰居搜索算法的步驟如下：

輸入：數(shù)據(jù)集X。

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

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

b）計(jì)算每個樣本點(diǎn)xi的r近鄰、nb（xi）及NN（xi）；

c）r=r+1；

d）當(dāng)xi使得NN（xi）≠或nb（xi）==0的數(shù)量不再變化時，λ=r，輸出λ和NN，否則跳轉(zhuǎn)至b）。

3 TNMMDPC算法

3.1 簇中心選擇

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

TNMMDPC算法對樣本局部密度定義的同時考慮了樣本點(diǎn)之間的距離和與樣本點(diǎn)所處的環(huán)境。該算法將二階自然最近鄰的概念納入局部密度的設(shè)計(jì)中。因?yàn)樗梢愿玫乇磉_(dá)點(diǎn)之間的接近關(guān)系，從而更準(zhǔn)確、更自然地評估每個點(diǎn)的局部密度。與通過截?cái)嗑嚯x或K最近鄰方法計(jì)算的局部密度相比，該算法使得每個點(diǎn)的局部密度可以在無須手動參數(shù)的情況下自適應(yīng)計(jì)算，因此具有魯棒性。

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

定義4 二階自然鄰居NNN（i）?；谧匀秽従铀枷耄A自然鄰居的定義如下：

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

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

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

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

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

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

3.2 分配策略

TNMMDPC算法定義了樣本點(diǎn)之間的相似度和樣本點(diǎn)與子簇之間的關(guān)聯(lián)度來進(jìn)行樣本點(diǎn)的分配。

定義7 點(diǎn)間相似度ωij。樣本點(diǎn)xi和xj之間的相似度定義為

定義8 點(diǎn)簇關(guān)聯(lián)度Ri→Cj［29］。 樣本點(diǎn)xi和微簇Cj之間的相似度定義為

樣本點(diǎn)xi和xj之間的相似度根據(jù)兩個樣本點(diǎn)之間的歐氏距離distij來定義，若兩個樣本點(diǎn)之間的距離越小，則相似度越高。微簇Cj中的每個樣本點(diǎn)v和樣本點(diǎn)xi之間的相似度的平均值定義為點(diǎn)簇關(guān)聯(lián)度。

將已選擇出的核心點(diǎn)集作為初始微簇，并將其中的樣本點(diǎn)標(biāo)記為已分配樣本。計(jì)算每個未分配點(diǎn)與其他各微簇的點(diǎn)簇關(guān)聯(lián)度矩陣，通過點(diǎn)簇關(guān)聯(lián)度矩陣找到所有未分配樣本點(diǎn)中與微簇關(guān)聯(lián)度最高的樣本點(diǎn)，將該樣本點(diǎn)分配給相應(yīng)微簇，重新計(jì)算點(diǎn)簇關(guān)聯(lián)度并更新關(guān)聯(lián)度矩陣，重新將關(guān)聯(lián)度最高的樣本點(diǎn)進(jìn)行分配，重復(fù)上述操作，直到所有的樣本點(diǎn)均分配完成。

3.3 多簇合并策略

將所有樣本點(diǎn)分配給與它關(guān)聯(lián)度最高的微簇后，可以得到若干個子簇。

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

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

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

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

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

當(dāng)兩個子簇A和B符合合并條件時，表示子簇A和B相距較近且兩個簇邊界點(diǎn)的分布較密集，鄰居邊界點(diǎn)集中的點(diǎn)應(yīng)該位于子簇A和B的連接區(qū)域，因此將這兩個子簇進(jìn)行合并處理。

3.4 TNMMDPC算法步驟和復(fù)雜度分析

原始DPC算法在根據(jù)截?cái)嗑嚯x計(jì)算局部密度和相對距離之后選取簇中心，然后根據(jù)歐氏距離來分配剩余樣本點(diǎn)。本文算法在計(jì)算樣本點(diǎn)的歐氏距離后，在自然鄰居搜索算法的基礎(chǔ)上得到每個樣本點(diǎn)的自然鄰居集合，用自然鄰居集合代替了截?cái)嗑嚯x來計(jì)算局部密度；然后根據(jù)決策值選取多個核心點(diǎn)并擴(kuò)展為核心點(diǎn)集來進(jìn)行樣本點(diǎn)的初始分配；最后進(jìn)行多簇合并，得到最后的聚類結(jié)果。TNMMDPC算法的步驟如下：

輸入：數(shù)據(jù)集X。

輸出：聚類結(jié)果C。

a）對數(shù)據(jù)進(jìn)行歸一化；

b）計(jì)算數(shù)據(jù)集樣本間的歐氏距離；

c）根據(jù)自然鄰居搜索算法得到每個樣本點(diǎn)的自然鄰居集合；

d）根據(jù)式（8）計(jì)算樣本點(diǎn)的局部密度ρi；

e）根據(jù)式（3）計(jì)算樣本點(diǎn)的相對距離δi；

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

g）根據(jù)式（8）計(jì)算樣本點(diǎn)間的相似度ωij；

h）根據(jù)式（9）計(jì)算每個未分配點(diǎn)和初始微簇的點(diǎn)簇關(guān)聯(lián)度Ri→Cj，構(gòu)造關(guān)聯(lián)度矩陣；

i）將關(guān)聯(lián)度矩陣中關(guān)聯(lián)度最高的樣本點(diǎn)分配給相對應(yīng)的微簇，重新計(jì)算點(diǎn)簇關(guān)聯(lián)度并更新關(guān)聯(lián)度矩陣；

j）重復(fù)步驟i），直到所有樣本點(diǎn)均分配完成；

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

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

4 實(shí)驗(yàn)結(jié)果與分析

將提出的TNMMDPC算法與DPC、SNNDPC和DBSCAN算法在人工數(shù)據(jù)集和UCI數(shù)據(jù)集上進(jìn)行比較。DPC和DBSCAN算法的實(shí)驗(yàn)結(jié)果基于作者提供的源代碼，在PyCharm2021中實(shí)現(xiàn)。SNNDPC算法參照原文獻(xiàn)使用PyCharm2021編程實(shí)現(xiàn)。

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

4.1 數(shù)據(jù)集介紹

實(shí)驗(yàn)選擇了十個人工數(shù)據(jù)集和幾個來自UCI上的真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)集的具體屬性分別如表1和2所示。

4.2 人工數(shù)據(jù)集實(shí)驗(yàn)結(jié)果分析

表3給出了所有四種算法對表1中十個人工數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果，其中，TNMMDPC、SNNDPC和DBSCAN算法均選取最優(yōu)參數(shù)得到最優(yōu)的實(shí)驗(yàn)結(jié)果。

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

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

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

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

4.3 UCI數(shù)據(jù)集實(shí)驗(yàn)結(jié)果分析

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

實(shí)驗(yàn)結(jié)果表明，處理iris數(shù)據(jù)集時，TNMMDPC算法的聚類效果低于SNNDPC和DPC算法，但高于DBSCAN算法。在處理ecoli和seeds數(shù)據(jù)集時，TNMMDPC算法的聚類效果優(yōu)于其他三個算法。處理zoo數(shù)據(jù)集時，TNMMDPC算法的聚類效果低于SNNDPC算法，但高于DPC和DBSCAN算法。

5 結(jié)束語

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

參考文獻(xiàn)：

［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］.計(jì)算機(jī)應(yīng)用，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］薛小娜，高淑萍，彭弘銘，等.結(jié)合K近鄰的改進(jìn)密度峰值聚類算法［J］.計(jì)算機(jī)工程與應(yīng)用，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］丁世飛，徐曉，王艷茹.基于不相似性度量優(yōu)化的密度峰值聚類算法［J］.軟件學(xué)報(bào)，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］.計(jì)算機(jī)工程與應(yīng)用，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］馮驥.自然鄰居思想概念及其在數(shù)據(jù)挖掘領(lǐng)域的應(yīng)用［D］.重慶：重慶大學(xué)，2016.（Feng Ji.Concept of natural neighbors and its application in data mining［D］.Chongqing：Chongqing University，2016.）

［24］徐曉，丁世飛，丁玲.密度峰值聚類算法研究進(jìn)展［J］.軟件學(xué)報(bào)，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］金輝，錢雪忠.自然最近鄰優(yōu)化的密度峰值聚類算法［J］.計(jì)算機(jī)科學(xué)與探索，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］劉娟，萬靜.自然反向最近鄰優(yōu)化的密度峰值聚類算法［J］.計(jì)算機(jī)科學(xué)與探索，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］馮驥，張程，朱慶生.一種具有動態(tài)鄰域特點(diǎn)的自適應(yīng)最近鄰居算法［J］.計(jì)算機(jī)科學(xué)，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ì)和多簇合并的密度峰值聚類算法［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.）