周歡歡，鄭伯川，張征，張琦

（1.西華師范大學(xué) 數(shù)學(xué)與信息學(xué)院，四川 南充 637009； 2.西華師范大學(xué) 計算機學(xué)院，四川 南充 637009）（?通信作者電子郵箱zhengbc@vip.163.com）

基于自適應(yīng)近鄰參數(shù)的密度峰聚類算法

周歡歡1，鄭伯川2*，張征1，張琦1

（1.西華師范大學(xué) 數(shù)學(xué)與信息學(xué)院，四川 南充 637009； 2.西華師范大學(xué) 計算機學(xué)院，四川 南充 637009）（?通信作者電子郵箱zhengbc@vip.163.com）

針對基于共享最近鄰的密度峰聚類算法中的近鄰參數(shù)需要人為設(shè)定的問題，提出了一種基于自適應(yīng)近鄰參數(shù)的密度峰聚類算法。首先，利用所提出的近鄰參數(shù)搜索算法自動獲得近鄰參數(shù)；然后，通過決策圖選取聚類中心；最后，根據(jù)所提出的代表點分配策略，先分配代表點，后分配非代表點，從而實現(xiàn)所有樣本點的聚類。將所提出的算法與基于共享最近鄰的快速密度峰搜索聚類（SNN?DPC）、基于密度峰值的聚類（DPC）、近鄰傳播聚類（AP）、對點排序來確定聚類結(jié)構(gòu)（OPTICS）、基于密度的噪聲應(yīng)用空間聚類（DBSCAN）和K-means這6種算法在合成數(shù)據(jù)集以及UCI數(shù)據(jù)集上進行聚類結(jié)果對比。實驗結(jié)果表明，所提出的算法在調(diào)整互信息（AMI）、調(diào)整蘭德系數(shù)（ARI）和FM指數(shù)（FMI）等評價指標上整體優(yōu)于其他6種算法。所提算法能自動獲得有效的近鄰參數(shù)，且能較好地分配簇邊緣區(qū)域的樣本點。

共享最近鄰；局部密度；密度峰聚類；-近鄰；逆近鄰

0 引言

聚類分析是在無任何先驗知識的條件下，對一組對象進行處理，根據(jù)數(shù)據(jù)對象或者物理對象的相似度將對象劃分為多個類簇，使得類間相似度盡可能小、類內(nèi)相似度盡可能大。聚類分析已經(jīng)被廣泛應(yīng)用在于統(tǒng)計學(xué)、生物學(xué)、醫(yī)學(xué)、模式識別、信息檢索、人工智能和圖像處理等領(lǐng)域。

聚類分析是數(shù)據(jù)挖掘研究中的一個活躍領(lǐng)域。針對不同類型的應(yīng)用程序，研究者們相繼提出了一系列的聚類算法。典型的聚類算法包括：基于劃分的K-means和K-medoids，基于層次的利用代表點聚類（Clustering Using REpresentative， CURE）算法和平衡迭代規(guī)約層次聚類（Balanced Iterative Reducing and Clustering using Hierarchies，BIRCH），基于密度的噪聲應(yīng)用空間聚類（Density-Based Spatial Clustering of Applications with Noise， DBSCAN）［5］和對點排序來確定聚類結(jié)構(gòu)（Ordering Points To Identify the Clustering Structure， OPTICS），基于網(wǎng)格的小波變換聚類算法（WaveCluster）和統(tǒng)計信息網(wǎng)格方法（STatistical INformation Grid-based method， STING），基于模型的統(tǒng)計聚類［1］和基于圖論的光譜聚類［2］。近年來，隨著聚類分析的發(fā)展，一些新的聚類算法被提出，如子空間聚類［3］、集成聚類［4］和深度嵌入聚類［5］。聚類算法的種類繁多，算法的性能也各不相同。

K-means是經(jīng)典的聚類算法，具有良好的聚類性能，但是也存在一些不足。K-means需要大量計算樣本點到聚類中心的距離，時間復(fù)雜度高，影響計算速度。Xia等［6］提出了一種無邊界的快速自適應(yīng)聚類算法減少距離計算；Taylor等［7］則通過GPU運行K-means算法。這些改進算法能有效提高K-means算法的運行速度。另外，K-means算法在凸球形結(jié)構(gòu)的數(shù)據(jù)集上能取得很好的聚類結(jié)果，但是對有任意形狀的簇的數(shù)據(jù)集，容易陷入局部最優(yōu)，聚類效果不理想。DBSCAN算法對類簇的形狀不敏感，抗噪能力強，但是對于密度不均勻和高維數(shù)據(jù)，聚類效果不理想［8-9］。此外，DBSCAN算法對于半徑和閾值的選擇也是一個難點。Rodriguez等［10］提出了基于密度峰值的聚類（Clustering by fast search and find of Density Peaks， DPC）算法。與K-means、DBSCAN、OPTICS等傳統(tǒng)算法相比，DPC算法具有簡單高效、無需迭代目標函數(shù)、能準確找到聚類中心、適應(yīng)于任意形狀的數(shù)據(jù)集等優(yōu)點。由于DPC算法具有較多優(yōu)點，使其在短時間內(nèi)被廣泛應(yīng)用于計算機視覺［11］、圖像識別［12］、文本挖掘［13］等領(lǐng)域。然而，DPC算法存在以下不足：1）聚類結(jié)果對截斷距離敏感；2）局部密度和距離測量的定義過于簡單，導(dǎo)致無法處理多尺度、密度不均衡和其他復(fù)雜特征的數(shù)據(jù)集；3）非聚類中心分配策略容錯能力差。

近年來，許多學(xué)者針對DPC算法存在的不足，對其進行了改進嘗試［14-18］。Du等［14］提出了基于K-近鄰的密度峰聚類（Density Peaks Clustering based onK-Nearest Neighbors，KNN-DPC）算法，解決了DPC算法只考慮數(shù)據(jù)集全局結(jié)構(gòu)的問題，為計算局部密度提供了另一種選擇。Guo等［16］提出了新的密度峰聚類算法（New local density for Density Peak Clustering，NDPC），NDPC算法在DPC算法中加入了逆近鄰，將局部密度改為數(shù)據(jù)點的逆近鄰個數(shù)，根據(jù)每個點的逆近鄰數(shù)來確定聚類中心。該算法的度量方式能有效地解決DPC算法的密度不均衡問題。錢雪忠等［19］提出了自適應(yīng)聚合策略優(yōu)化的密度峰值聚類算法，通過類簇間密度可達來合并相似類簇，不需要輸入簇數(shù)，但是需要輸入近鄰參數(shù)。Liu等［20］提出了一種基于共享最近鄰的快速密度峰搜索聚類（Shared-Nearest-Neighbor-based Clustering by fast search and find of Density Peaks，SNN?DPC）算法，該算法提出了基于共享近鄰的局部密度度量方式和與最近的較大密度點距離的自適應(yīng)度量方式。SNN-DPC算法能處理多尺度、交叉纏繞、密度不均衡和較高維復(fù)雜的數(shù)據(jù)集，并且樣本被錯誤分配時不會導(dǎo)致進一步的錯誤。

2）提出了代表點的概念，并基于該概念提出了新的非聚類中心分配策略，避免數(shù)據(jù)點被錯誤分配時導(dǎo)致進一步的錯誤。

1 DPC算法及SNN?DPC算法

1.1 DPC算法

DPC是一種基于密度和距離的聚類算法。該算法基于以下假設(shè)：聚類中心被具有較低局部密度的鄰居包圍，并且不同聚類中心之間的距離相對較遠。DPC算法有兩個重要指標來描述每個樣本點：樣本的局部密度和樣本到距離最近且局部密度較大樣本點的距離。

DPC算法通過決策圖選取理想的聚類中心，所謂理想的聚類中心是指距離較遠且密度較高的樣本點，即選擇較大的決策值對應(yīng)的樣本點為聚類中心。

根據(jù)文獻［18］可知，DPC算法分為兩個步驟：1）通過計算每個點的和，得到?jīng)Q策圖，然后從決策圖中選擇決策值較高的點作為聚類中心。2）將剩余的點分配給距其最近且具有較高密度的點所在的簇。

通過DPC算法獲得的實驗結(jié)果表明，在許多情況下處理數(shù)據(jù)集都能得到很好的聚類結(jié)果，但是它的缺點也顯而易見，比如：1）聚類結(jié)果對參數(shù)敏感。2）對于密度不均衡數(shù)據(jù)，錯誤選擇聚類中心，導(dǎo)致聚類結(jié)果不理想，如圖1所示的經(jīng)典Jain數(shù)據(jù)集。3）非聚類中心的分配策略敏感，容錯能力差，如圖2所示的Pathbased數(shù)據(jù)集。

圖1 Jain數(shù)據(jù)集聚類結(jié)果Fig. 1 Clustering results of Jain dataset

圖2 Pathbased數(shù)據(jù)集聚類結(jié)果Fig. 2 Clustering results of Pathbased dataset

針對DPC算法存在的上述問題，文獻［20］中提出了一種基于共享近鄰的密度峰快速搜索算法SNN-DPC。

1.2 SNN-DPC算法

由于DPC算法直接計算樣本點之間的距離和密度，沒有關(guān)注樣本點所在的環(huán)境，所以DPC算法在某些復(fù)雜的數(shù)據(jù)集上無法產(chǎn)生令人滿意的結(jié)果。理論上樣本點的大多數(shù)鄰居應(yīng)該屬于同一個簇，據(jù)此引入了共享近鄰SNN的概念來描述樣本點的局部密度和樣本點之間的距離，考慮到了每個點受周圍鄰居的影響。

SNN的基本思想為：若兩個樣本點共享的鄰居總數(shù)之和越大，則它們被認為更相似。下面詳細介紹SNN-DPC相關(guān)定義。

定義2 逆近鄰［22］。假設(shè)樣本點，樣本點在樣本點的-近鄰集中，則稱樣本點為點的逆近鄰，表達式如下：

在SNN-DPC算法中，首先根據(jù)決策圖確定聚類中心，然后分配滿足式（11）的必然從屬點，最后分配滿足式（12）的可能從屬點。

未分配的點不符合必然從屬點，則將其定義為可能從屬點，表達式如下：

1.3 SNN-DPC算法分析

SNN-DPC算法引入了共享近鄰的概念［23］，改進了局部密度和距最近密度較大點的距離的定義，能反映數(shù)據(jù)集的局部特征，進而可以反映數(shù)據(jù)的自然結(jié)構(gòu)；因此該算法能處理交叉纏繞、不同密度和高維度的復(fù)雜數(shù)據(jù)集，抗噪能力強，同時保留了DPC算法的大多數(shù)優(yōu)點。對于非聚類中心采用兩步分配方法，避免數(shù)據(jù)點被錯誤分配時出現(xiàn)進一步錯誤。在SNN-DPC算法中，通過值來確定每個樣本點的鄰域，它影響著算法過程中的關(guān)鍵步驟。換言之，近鄰參數(shù)直接決定SNN-DPC算法的性能。然而，SNN-DPC算法需要人工確定近鄰參數(shù)。因此，本文提出了基于自適應(yīng)近鄰參數(shù)的密度峰聚類算法，可以有效解決近鄰參數(shù)的設(shè)定問題。

2 基于自適應(yīng)近鄰參數(shù)的密度峰聚類算法

2.1 近鄰參數(shù)搜索算法

樣本點之間的相關(guān)程度不僅與近鄰有關(guān)，還與逆近鄰有關(guān)。數(shù)據(jù)集密集區(qū)域的樣本點具有較多的互為近鄰的點，稀疏區(qū)域的樣本點有相對較少的互為近鄰的點。因此，每個樣本的互為近鄰數(shù)能反映數(shù)據(jù)集局部分布情況。當最離群的樣本點都有互為近鄰的點時，數(shù)據(jù)集中所有點都應(yīng)該有互為近鄰點。基于這一假設(shè)，本文提出了一種近鄰參數(shù)搜索算法，用于自動獲得近鄰參數(shù)值。

5） endwhile

2.2 分配策略

定義10 代表點。如果滿足式（13）則稱該點為代表點。

由于樣本點的逆近鄰數(shù)不會受數(shù)據(jù)集密度不均衡的影響，能更準確地反映數(shù)據(jù)集的分布特征。以Aggregation數(shù)據(jù)集為例，圖3（a）為所有點分布圖，圖3（b）為代表點分布圖。如圖3所示，具有少量逆近鄰的樣本點普遍分布在數(shù)據(jù)集每個簇的邊緣，代表點具有相對較多的逆近鄰數(shù)，所以代表點通常不會出現(xiàn)在數(shù)據(jù)集每個簇的邊緣。因此本文提出了以逆近鄰數(shù)為主的非聚類中心兩步分配策略。該策略先將代表點分配給相應(yīng)的簇，最后分配非代表點。通過近鄰參數(shù)搜索算法得到的近鄰參數(shù)，能選出數(shù)據(jù)集相對集中區(qū)域的樣本點作為代表點。

圖3 原始樣本點和代表點分布情況Fig. 3 Distribution of original sample points and representative points

2.3 算法流程

算法2 基于自適應(yīng)近鄰參數(shù)的密度峰聚類算法。

輸出 聚類結(jié)果。

2）計算距離矩陣；

3）根據(jù)式（8）計算相似矩陣；

5）根據(jù)式（10）計算樣本點與距離最近且密度較大的樣本點之間的距離；

9）利用算法3分配代表點；

10）利用算法4分配非代表點。

算法2中利用算法3分配代表點，利用算法4分配非代表點，它們的具體實現(xiàn)如下。

算法3 代表點分配算法。

1）使用式（13）計算得到所有代表點。

b） 如果該近鄰點是代表點且不屬于任何簇，則將其分配到頭部點所在的簇，同時，如果該近鄰點和頭部點的共享近鄰數(shù)大于等于，則將該近鄰點添加到隊列的尾部；

算法4 非代表點分配算法。

5）循環(huán)步驟1）～4），直至非代表點分配完。

3 實驗與結(jié)果分析

3.1 實驗環(huán)境及評價指標

本文算法采用Matlab 2018a實現(xiàn)，硬件配置為Windows 10操作系統(tǒng)，8 GB物理內(nèi)存，硬件環(huán)境為Intel Xeon CPU E3-1240 v5@3.50 GHz。

為驗證本文算法的有效性，分別在經(jīng)典的合成數(shù)據(jù)集和UCI真實數(shù)據(jù)集上進行聚類實驗。實驗中，以SNN?DPC［20］、DPC［10］、DBSCAN、OPTICS、近鄰傳播聚類（Affinity Propagation， AP）［24］和K-means作為對照比較算法。所有對比算法都是針對已知簇數(shù)的情況下進行聚類，除了簇數(shù)外不同的方法需要設(shè)置不同的參數(shù)：本文算法不需要其他參數(shù)；SNN?DPC算法需要一個參數(shù)（每個樣本點的鄰居數(shù)量）；DPC算法需要參數(shù)：（截斷距離）；DBSCAN和OPTICS算法需要兩個參數(shù)：（鄰域半徑）和（鄰域半徑內(nèi)期望樣本個數(shù)），前者是浮點數(shù)，后者是整數(shù)；AP算法有一個參數(shù)：偏好參數(shù)（樣本點作為聚類中心的參考度）；K-means算法直接采用已知的簇數(shù)。實驗聚類結(jié)果中的參數(shù)值是各算法取得最佳結(jié)果時的參數(shù)值。由于所有算法采用已知簇數(shù)，因此沒有給出具體簇數(shù)參數(shù)。實驗中采用調(diào)整互信息（Adjusted Mutual Information， AMI）［25］、調(diào)整蘭德系數(shù)（Adjusted Rand Index， ARI）［25］和FM指數(shù)（Fowlkes and Mallows Index， FMI）［26］這三種評價指標對聚類結(jié)果進行評價。AMI用于計算聚類結(jié)果與真實分類的相似性，取值范圍為，該值越接近1表示聚類結(jié)果越好，反之則聚類效果越差。ARI衡量聚類結(jié)果與真實分類的吻合程度，取值范圍為［-1，1］，該值越接近1表示聚類結(jié)果越準確，反之則聚類結(jié)果越差。FMI計算聚類結(jié)果與真實值得到精確率和召回率的幾何平均數(shù)，取值范圍為［0，1］，該值越接近1表示聚類結(jié)果越接近真實值，反之則聚類的質(zhì)量越差。在進行實驗之前，需對數(shù)據(jù)進行預(yù)處理，采用最小最大歸一化方法將數(shù)據(jù)每維都歸一化到［0，1］，從而消除維度差異的影響。

3.2 結(jié)果分析

選取8個經(jīng)典的合成數(shù)據(jù)集和4個UCI真實數(shù)據(jù)集進行實驗，所選數(shù)據(jù)集在聚類總體分布和屬性以及數(shù)量方面有所不同。因此，所選數(shù)據(jù)集能更好地比較各種聚類算法的性能。數(shù)據(jù)詳細信息如表1～2所示。

表1 合成數(shù)據(jù)集信息Tab. 1 Synthetic dataset information

表2 UCI數(shù)據(jù)集信息Tab. 2 UCI dataset information

圖4～11為8個合成數(shù)據(jù)集的原始聚類圖和本文算法獲得的聚類效果圖，其中具有不同顏色的點被分配給不同的簇，聚類中心以星號表示。從圖4～11中可以看出，本文聚類算法在各種形狀的數(shù)據(jù)集上都能準確找到聚類中心，能較準確地對每個樣本點劃分簇，而且對螺旋型和密度不均衡數(shù)據(jù)集也能正確聚類；另外也可以看出，代表點分配策略對簇邊緣區(qū)域樣本點聚類效果比較理想。

為了驗證本文算法的聚類效果，以AMI、ARI和FMI為評價指標判斷其聚類效果。實驗中分別記錄了本文算法、SNN-DPC算法、DPC算法、DBSCAN算法、OPTICS算法、AP算法和K-means算法在8個合成數(shù)據(jù)集和4個UCI真實數(shù)據(jù)集上的AMI、ARI和FMI值，結(jié)果如表3～4所示。表3～4中，除了本文算法和SNN?DPC算法的實驗結(jié)果外，其他算法的實驗結(jié)果來自于文獻［20］。

圖4 Aggregation數(shù)據(jù)集聚類效果Fig. 4 Clustering effect of Aggregation dataset

圖5 Flame數(shù)據(jù)集聚類效果Fig. 5 Clustering effect of Flame dataset

圖6 Jain數(shù)據(jù)集聚類效果Fig. 6 Clustering effect of Jain dataset

圖7 Pathbased數(shù)據(jù)集聚類效果Fig. 7 Clustering effect of Pathbased dataset

圖8 R15數(shù)據(jù)集聚類效果Fig. 8 Clustering effect of R15 dataset

表3是在合成數(shù)據(jù)集上的實驗結(jié)果，除了Flame數(shù)據(jù)集和D31數(shù)據(jù)集，本文算法的AMI、ARI和FMI指標在合成數(shù)據(jù)集上都優(yōu)于或等于SNN-DPC算法。其中，對于Aggregation數(shù)據(jù)集，本文算法的AMI、ARI和FMI指標相較SNN-DPC算法分別提高了2.94個百分點、2.61個百分點和2.05個百分點；對于Pathbased數(shù)據(jù)集，本文算法的AMI、ARI和FMI指標相較SNN-DPC算法分別提高了1.85個百分點、3.92個百分點和1.38個百分點。如表4所示，本文算法的3個指標在UCI數(shù)據(jù)集上優(yōu)于或等于SNN-DPC算法，其中對于Seeds數(shù)據(jù)集，本文算法的AMI、ARI和FMI指標相較SNN-DPC算法分別提高了24.91個百分點、21.1個百分點和17.24個百分點。因此，本文算法通過自動計算近鄰參數(shù)和分配策略達到甚至超過了SNN?DPC算法的聚類性能，克服了SNN?DPC算法需要人工設(shè)置參數(shù)的不足。

圖9 Spiral數(shù)據(jù)集聚類效果Fig. 9 Clustering effect of Spiral dataset

圖10 D31數(shù)據(jù)集聚類效果Fig. 10 Clustering effect of D31 dataset

圖11 S2數(shù)據(jù)集聚類效果Fig. 11 Clustering effect of S2 dataset

另外，對于表3的合成數(shù)據(jù)集，除了在Aggregation數(shù)據(jù)集和Flame數(shù)據(jù)集上本文算法的3個評價指標略低于DPC，在S2數(shù)據(jù)集上本文算法的3個指標略低于K-means算法外，本文算法的指標在其他數(shù)據(jù)集上都優(yōu)于DPC、DBSCAN、OPTICS、AP和K-means算法。對于表4的真實數(shù)據(jù)集，在Wine和Seeds數(shù)據(jù)集上，本文算法的3個評價指標都等于或者超過其他算法；在Blance Scale數(shù)據(jù)集上，DPC算法的3個指標都優(yōu)于其他算法，本文算法的3個指標只優(yōu)于SNN-DPC；在Segmentation數(shù)據(jù)集上，本文算法的3個指標只略低于DPC算法，但優(yōu)于其他算法。

表3 不同算法在合成數(shù)據(jù)集上的聚類結(jié)果Tab. 3 Clustering results of different algorithms on synthetic datasets

表4 不同算法在UCI數(shù)據(jù)集上的聚類結(jié)果Tab. 4 Clustering results of different algorithms on UCI datasets

綜上，可以看出，本文算法的整體聚類性能較好，只在個別數(shù)據(jù)集上略低于其他算法，這可能與數(shù)據(jù)集的特征有關(guān)系，比如，在Blance Scale數(shù)據(jù)集上，所有對比算法的3個評價指標都較低。另外，在幾個數(shù)據(jù)集上DPC算法的指標比本文算法好，其原因可能是：DPC算法通過人工逐一測試出最佳參數(shù)，而本文算法是自動計算出來的參數(shù)k。因此，從算法通用性上來講，本文算法優(yōu)于DPC算法。

4 結(jié)語

在經(jīng)典合成數(shù)據(jù)集和UCI數(shù)據(jù)集上的實驗結(jié)果表明，所提算法不僅保留了SNN-DPC算法能準確找到聚類中心、抗噪能力強、能處理分布不均和任意形狀的數(shù)據(jù)集等優(yōu)點，還可以自適應(yīng)確定近鄰參數(shù)，此外，該算法還可以較好地分配簇邊緣區(qū)域的樣本點。實驗結(jié)果表明，所提基于自適應(yīng)近鄰參數(shù)的密度峰聚類算法是一種有效的自適應(yīng)聚類算法，能自適應(yīng)得到近鄰參數(shù)。然而，在無先驗知識的情況下，如何確定算法中數(shù)據(jù)集的簇數(shù)需要進一步的研究。

[1] DEMPSTER A P， LAIRD N M， RUBIN D B. Maximum likelihood from incomplete data via the EM algorithm ［J］. Journal of the Royal Statistical Society： Series B （Methodological）， 1977， 39 （1）： 1-22.

[2] LUXBURG U von. A tutorial on spectral clustering ［J］. Statistics and Computing， 2007， 17（4）： 395-416.

[3] AGRAWAL R， GEHRKE J， GUNOPULOS D， et al. Automatic subspace clustering of high dimensional data for data mining applications ［C］// Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data. New York： ACM， 1998： 94-105.

[4] STREHL A， GHOSH J. Cluster ensembles — a knowledge reuse framework for combining multiple partitions ［J］. Journal of Machine Learning Research， 2002， 3： 583-617.

[5] XIE J Y， GIRSHICK R， FARHADI A. Unsupervised deep embedding for clustering analysis ［C］// Proceedings of the 2016 33rd International Conference on International Conference on Machine Learning. New York： JMLR.org， 2016： 478-487.

[6] XIA S Y， PENG D W， MENG D Y， et al. Ballk-means： fast adaptive clustering with no bounds ［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2022， 44（1）： 87-99.

[7] TAYLOR C， GOWANLOCK M. Accelerating the Yinyangk-means algorithm using the GPU ［C］// Proceedings of the 2021 IEEE 37th International Conference on Data Engineering. Piscataway： IEEE， 2021：1835-1840.

[8] TAN P N， STEINBACK M， KARPATNE A， et al. Introduction to Data Mining ［M］. 2nd ed. London： Pearson， 2019：565-570.

[9] XIE J Y， GAO H C， XIE W X， et al. Robust clustering by detecting density peaks and assigning points based on fuzzy weightedK-nearest neighbors ［J］. Information Sciences， 2016， 354：19-40.

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

[11] SHI Y， CHEN Z S， QI Z Q， et al. A novel clustering-based image segmentation via density peaks algorithm with mid-level feature ［J］. Neural Computing and Applications， 2017， 28（S1）： 29-39.

[12] CHEN Y W， LAI D H， QI H， et al. A new method to estimate ages of facial image for large database ［J］. Multimedia Tools and Applications， 2016， 75（5）： 2877-2895.

[13] ZHANG Y， XIA Y Q， LIU Y， et al. Clustering sentences with density peaks for multi-document summarization ［C］// Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics： Human Language Technologies. Stroudsburg： Association for Computational Linguistics， 2015： 1262-1267.

[14] DU M J， DING S F， JIA H J. Study on density peaks clustering based onk-nearest neighbors and principal component analysis ［J］. Knowledge-Based Systems， 2016， 99： 135-145.

[15] 鮑舒婷，孫麗萍，鄭孝遙，等.基于共享近鄰相似度的密度峰聚類算法［J］.計算機應(yīng)用，2018，38（6）：1601-1607.（BAO S T， SUN L P，ZHENG X Y， et al. Density peaks clustering algorithm based on shared near neighbors similarity ［J］. Journal of Computer Applications， 2018， 38（6）： 1601-1607.）

[16] GUO Z S， HUANG T Y， CAI Z L， et al. A new local density for density peak clustering ［C］// Proceedings of the 2018 Pacific-Asia Conference on Knowledge Discovery and Data Mining， LNCS 10939. Cham：Springer， 2018： 426-438.

[17] 朱慶峰，葛洪偉.K近鄰相似度優(yōu)化的密度峰聚類［J］.計算機工程與應(yīng)用，2019，55（2）：148-153，252.（ZHU Q F， GE H W. Density peaks clustering optimized byKnearest neighbor’s similarity ［J］. Computer Engineering and Applications， 2019， 55（2）： 148-153， 252.）

[18] 邱保志，辛杭.一種基于共享近鄰親和度的聚類算法［J］.計算機工程與應(yīng)用，2018，54（18）：184-187，222.（QIU B Z， XIN H. Shared nearest neighbor affinity based clustering algorithm ［J］. Computer Engineering and Applications， 2018， 54（18）： 184-187， 222.）

[19] 錢雪忠，金輝.自適應(yīng)聚合策略優(yōu)化的密度峰值聚類算法［J］.計算機科學(xué)與探索，2020，14（4）：712-720.（QIAN X Z， JIN H. Optimized density peak clustering algorithm by adaptive aggregation strategy ［J］. Journal of Frontiers of Computer Science and Technology ， 2020， 14（4）： 712-720.）

[20] LIU R， WANG H， YU X M. Shared-nearest-neighbor-based clustering by fast search and find of density peaks ［J］. Information Sciences， 2018， 450： 200-226.

[21] COVER T， HART P. Nearest neighbor pattern classification ［J］. IEEE Transactions on Information Theory，1967， 13（1）： 21-27.

[22] KORN F， MUTHUKRISHNAN S. Influence sets based on reverse nearest neighbor queries ［J］. ACM SIGMOD Record， 2000， 29（2）： 201-212.

[23] JARVIS R A， PATRICK E A. Clustering using a similarity measure based on shared near neighbors ［J］. IEEE Transactions on Computers， 1973， C-22（11）： 1025-1034.

[24] FREY B J， DUECK D. Clustering by passing messages between data points ［J］. Science， 2007， 315（5814）： 972-976.

[25] VINH N X， EPPS J， BAILEY J. Information theoretic measures for clusterings comparison： variants， properties， normalization and correction for chance ［J］. Journal of Machine Learning Research， 2010， 11： 2837-2854.

[26] FOWLKES E S， MALLOWS C L. A method for comparing two hierarchical clusterings ［J］. Journal of the American Statistical Association， 1983， 78（383）： 553-569.

Density peak clustering algorithm based on adaptive nearest neighbor parameters

ZHOU Huanhuan1， ZHENG Bochuan2*， ZHANG Zheng1， ZHANG Qi1

（1.School of Mathematics and Information，China West Normal University，Nanchong Sichuan637009，China；2.School of Computer Science，China West Normal University，Nanchong Sichuan637009，China）

Aiming at the problem that the nearest neighbor parameters need to be set manually in density peak clustering algorithm based on shared nearest neighbor， a density peak clustering algorithm based on adaptive nearest neighbor parameters was proposed. Firstly， the proposed nearest neighbor parameter search algorithm was used to automatically obtain the nearest neighbor parameters. Then， the clustering centers were selected through the decision diagram. Finally，according to the proposed allocation strategy of representative points， all sample points were clustered through allocating the representative points and the non-representative points sequentially. The clustering results of the proposed algorithm was compared with those of the six algorithms such as Shared-Nearest-Neighbor-based Clustering by fast search and find of Density Peaks （SNN?DPC）， Clustering by fast search and find of Density Peaks （DPC）， Affinity Propagation （AP）， Ordering Points To Identify the Clustering Structure （OPTICS）， Density-Based Spatial Clustering of Applications with Noise （DBSCAN）， andK-means on the synthetic datasets and UCI datasets. Experimental results show that， the proposed algorithm is better than the other six algorithms on the evaluation indicators such as Adjusted Mutual Information （AMI）， Adjusted Rand Index （ARI） and Fowlkes and Mallows Index （FMI）. The proposed algorithm can automatically obtain the effective nearest neighbor parameters， and can better allocate the sample points in the edge region of the cluster.

shared nearest neighbor; local density; density peak clustering;k-neighbor; inverse neighbor

TP181

A

1001-9081（2022）05-1464-08

10.11772/j.issn.1001-9081.2021050753

2021?05?11；

2021?08?27；

2021?08?30。

國家自然科學(xué)基金資助項目（62176217）。

周歡歡（1996—），女，重慶人，碩士研究生，主要研究方向：機器學(xué)習(xí)、聚類分析； 鄭伯川（1974—），男，四川自貢人，教授，博士，CCF會員，主要研究方向：機器學(xué)習(xí)、深度學(xué)習(xí)、計算機視覺； 張征（1978—），女，四川自貢人，副教授，碩士，主要研究方向：運籌與優(yōu)化； 張琦（1996—），女，重慶人，碩士研究生，主要研究方向：機器學(xué)習(xí)、聚類分析。

This work is partially supported by National Natural Science Foundation of China （62176217）.

ZHOU Huanhuan， born in 1996， M. S. candidate. Her research interests include machine learning，clustering analysis.

ZHENG Bochuan， born in 1974， Ph. D.， professor. His research interests include machine learning， deep learning， computer vision.

ZHANG Zheng， born in 1978， M. S.， associate professor. Her research interests include operations research and optimization.

ZHANG Qi， born in 1996， M. S. candidate. Her research interests include machine learning， clustering analysis.