基于自適應近鄰參數的密度峰聚類算法

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

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

基于自適應近鄰參數的密度峰聚類算法

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

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

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

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

0 引言

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

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

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

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

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

1 DPC算法及SNN?DPC算法

1.1 DPC算法

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

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

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

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

圖1 Jain數據集聚類結果Fig. 1 Clustering results of Jain dataset

圖2 Pathbased數據集聚類結果Fig. 2 Clustering results of Pathbased dataset

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

1.2 SNN-DPC算法

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

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

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

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

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

1.3 SNN-DPC算法分析

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

2 基于自適應近鄰參數的密度峰聚類算法

2.1 近鄰參數搜索算法

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

5） endwhile

2.2 分配策略

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

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

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

2.3 算法流程

算法2 基于自適應近鄰參數的密度峰聚類算法。

輸出 聚類結果。

2）計算距離矩陣；

3）根據式（8）計算相似矩陣；

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

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

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

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

算法3 代表點分配算法。

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

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

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

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

3 實驗與結果分析

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

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

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

3.2 結果分析

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

表1 合成數據集信息Tab. 1 Synthetic dataset information

表2 UCI數據集信息Tab. 2 UCI dataset information

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

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

圖4 Aggregation數據集聚類效果Fig. 4 Clustering effect of Aggregation dataset

圖5 Flame數據集聚類效果Fig. 5 Clustering effect of Flame dataset

圖6 Jain數據集聚類效果Fig. 6 Clustering effect of Jain dataset

圖7 Pathbased數據集聚類效果Fig. 7 Clustering effect of Pathbased dataset

圖8 R15數據集聚類效果Fig. 8 Clustering effect of R15 dataset

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

圖9 Spiral數據集聚類效果Fig. 9 Clustering effect of Spiral dataset

圖10 D31數據集聚類效果Fig. 10 Clustering effect of D31 dataset

圖11 S2數據集聚類效果Fig. 11 Clustering effect of S2 dataset

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

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

表4 不同算法在UCI數據集上的聚類結果Tab. 4 Clustering results of different algorithms on UCI datasets

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

4 結語

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

[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］.計算機應用，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］.計算機工程與應用，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］.計算機工程與應用，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ōu)化的密度峰值聚類算法［J］.計算機科學與探索，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。

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

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

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.