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

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

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

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

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

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

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

共享最近鄰；局部密度；密度峰聚類(lèi)；-近鄰；逆近鄰

0 引言

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

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

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

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

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

1 DPC算法及SNN?DPC算法

1.1 DPC算法

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

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

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

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

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

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

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

1.2 SNN-DPC算法

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

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

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

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

未分配的點(diǎn)不符合必然從屬點(diǎn)，則將其定義為可能從屬點(diǎn)，表達(dá)式如下：

1.3 SNN-DPC算法分析

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

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

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

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

5） endwhile

2.2 分配策略

定義10 代表點(diǎn)。如果滿足式（13）則稱(chēng)該點(diǎn)為代表點(diǎn)。

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

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

2.3 算法流程

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

輸出 聚類(lèi)結(jié)果。

2）計(jì)算距離矩陣；

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

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

9）利用算法3分配代表點(diǎn)；

10）利用算法4分配非代表點(diǎn)。

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

算法3 代表點(diǎn)分配算法。

1）使用式（13）計(jì)算得到所有代表點(diǎn)。

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

算法4 非代表點(diǎn)分配算法。

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

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

3.1 實(shí)驗(yàn)環(huán)境及評(píng)價(jià)指標(biāo)

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

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

3.2 結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

[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] 鮑舒婷，孫麗萍，鄭孝遙，等.基于共享近鄰相似度的密度峰聚類(lèi)算法［J］.計(jì)算機(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)化的密度峰聚類(lèi)［J］.計(jì)算機(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] 邱保志，辛杭.一種基于共享近鄰親和度的聚類(lèi)算法［J］.計(jì)算機(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] 錢(qián)雪忠，金輝.自適應(yīng)聚合策略?xún)?yōu)化的密度峰值聚類(lèi)算法［J］.計(jì)算機(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。

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

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

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.