加權(quán)K 近鄰和多簇合并的密度峰值聚類算法

陳 磊，吳潤秀，李沛武，趙 嘉

南昌工程學(xué)院 信息工程學(xué)院，南昌 330099

聚類分析是數(shù)據(jù)挖掘的重要技術(shù)。它根據(jù)數(shù)據(jù)點(diǎn)間的相似性將數(shù)據(jù)集劃分成類簇，使得屬于同一類簇的樣本具有較高相似性，不同類簇間的樣本存在顯著差異。聚類可以揭示數(shù)據(jù)中隱藏的模式和規(guī)律，是認(rèn)識(shí)和了解世界的重要方式，被廣泛應(yīng)用于計(jì)算機(jī)科學(xué)、信息安全、圖像處理等研究領(lǐng)域。

由于聚類算法的廣泛應(yīng)用，學(xué)者們對(duì)聚類算法進(jìn)行了深入研究并提出了眾多的聚類算法。依據(jù)對(duì)樣本的不同處理方式，可分為基于劃分的聚類算法、基于層次的聚類算法、基于密度的聚類算法以及基于網(wǎng)格的聚類算法等。最著名的基于劃分的聚類算法是-means 算法，該算法實(shí)現(xiàn)簡(jiǎn)單，在凸形結(jié)構(gòu)數(shù)據(jù)集上具有良好的聚類效果，但-means 算法的聚類結(jié)果嚴(yán)重依賴于初始類簇中心的選擇，需要指定類簇個(gè)數(shù)，對(duì)噪聲點(diǎn)和離群點(diǎn)敏感。BIRCH（balanced iterative reducing and clustering using hierarchies）是一種基于層次的聚類算法，它能夠快速對(duì)數(shù)據(jù)集進(jìn)行聚類，但是該算法的聚類結(jié)果與樣本的輸入順序有關(guān)，屬于同一類簇的兩樣本可能會(huì)因?yàn)檩斎腠樞蛳嗖钶^遠(yuǎn)而被分配到不同類簇。DBSCAN（densitybased algorithm for discovering clusters in large spatial databases with noise）是一種典型的基于密度的聚類算法，它可以對(duì)任意形狀數(shù)據(jù)進(jìn)行聚類，不需要預(yù)先指定類簇個(gè)數(shù)，但受核心對(duì)象鄰域包含的最少樣本數(shù)和鄰域半徑參數(shù)設(shè)置的影響較大且高維數(shù)據(jù)的聚類效果差。STING（statistical information grid）是一種基于網(wǎng)格的聚類算法，它將樣本所在空間按照不同的維度劃分成有限個(gè)網(wǎng)格單元，所有的處理都以網(wǎng)格單元為對(duì)象，這種方法將數(shù)據(jù)集的聚類操作轉(zhuǎn)變?yōu)閷?duì)數(shù)據(jù)空間中塊的處理，提高了算法效率，但該算法需設(shè)置合理的網(wǎng)格粒度，不同的網(wǎng)格粒度大小對(duì)聚類精度和聚類效率有重要影響。

2014 年Rodriguez 和Laio在上提出了 一種新的快速搜索和尋找密度峰值的聚類算法，簡(jiǎn)稱密度峰值聚類（density peaks clustering，DPC）算法。該算法只有一個(gè)參數(shù)，能快速發(fā)現(xiàn)任意形狀數(shù)據(jù)的密度峰值。DPC 算法基于兩點(diǎn)假設(shè)：（1）類簇中心的局部密度很大，并且被密度均不超過它的鄰居包圍；（2）各類簇中心之間的距離相對(duì)較遠(yuǎn)。

DPC 算法雖然能快速發(fā)現(xiàn)任意形狀數(shù)據(jù)的密度峰值（類簇中心），但存在如下缺陷：（1）DPC 有兩種局部密度定義方式，沒有統(tǒng)一的密度度量準(zhǔn)則，兩種定義方式的聚類結(jié)果差異較大，且人為主觀選取的截?cái)嗑嚯x值對(duì)聚類結(jié)果影響大；（2）DPC 的分配策略是將非密度峰值分配給距其最近且密度比它大的樣本所在類簇，該樣本分配方法很容易產(chǎn)生分配連帶錯(cuò)誤，即一旦某一個(gè)樣本分配錯(cuò)誤，會(huì)導(dǎo)致后續(xù)一連串的樣本分配錯(cuò)誤，造成不理想的聚類效果。

由于DPC 算法存在上述缺陷，近年來學(xué)者們對(duì)其進(jìn)行了改進(jìn)。針對(duì)局部密度定義存在的問題，紀(jì)霞等人提出了一種相對(duì)鄰域與剪枝策略優(yōu)化的密度峰值聚類算法（relative neighborhood and pruning strategy optimized density peaks clustering algorithm，RP-DPC）。該算法首先利用相對(duì)距離將樣本映射到相對(duì)鄰域中，再從相對(duì)鄰域來計(jì)算各樣本的局部密度，從而縮小各樣本距離計(jì)算及密度統(tǒng)計(jì)的范圍。薛小娜等人提出了結(jié)合K 近鄰的改進(jìn)密度峰值聚類算法（improved density peaks clustering algorithm combining K-nearest neighbors，IDPCA）。IDPCA 算法通過引入相似系數(shù)來調(diào)節(jié)各樣本對(duì)當(dāng)前樣本的密度貢獻(xiàn)權(quán)重，并使用帶有相似系數(shù)的高斯核函數(shù)來定義局部密度。在類簇間樣本數(shù)不均勻的情況下，該局部密度定義能準(zhǔn)確找到密度峰值。Du 等人提出了基于K 近鄰和主成分分析的密度峰值聚類算法（density peaks clustering based on K-nearest neighbors and principal component analysis，DPC-KNN-PCA）。DPC-KNN-PCA 算法采用樣本的K 近鄰信息重新定義了樣本的局部密度。這種局部密度定義方式將密度計(jì)算范圍從整個(gè)數(shù)據(jù)集縮減為樣本的個(gè)近鄰，得到的樣本密度僅與其個(gè)近鄰有關(guān)，能更加體現(xiàn)樣本的局部信息，一定程度上提升了算法對(duì)密度不均勻數(shù)據(jù)的聚類性能。

針對(duì)分配策略設(shè)計(jì)存在的不足，Xie 等人提出了一種基于模糊加權(quán)K 近鄰分配點(diǎn)的密度峰值聚類算法（robust clustering by detecting density peaks and assigning points based on fuzzy weighted K-nearest neighbors，F(xiàn)KNN-DPC）。該算法將樣本分為核心樣本和離群樣本，先從密度峰值開始對(duì)每個(gè)樣本的K近鄰進(jìn)行廣度優(yōu)先搜索來分配核心樣本，再使用加權(quán)K 近鄰技術(shù)對(duì)第一次未分配樣本和離群樣本進(jìn)行分配。這種分配策略能夠有效緩解DPC 算法一步分配導(dǎo)致的分配錯(cuò)誤傳遞問題。賈露等人提出了一種物理學(xué)優(yōu)化的密度峰值聚類算法（optimized density peak clustering algorithm in physics，W-DPC）。該算法根據(jù)第一宇宙速度建立了兩步分配策略對(duì)樣本進(jìn)行分配，即必然從屬于點(diǎn)的分配和可能從屬于點(diǎn)的分配，使得樣本的分配更加精確。

針對(duì)DPC 算法的局部密度定義和分配策略設(shè)計(jì)的不足，本文提出了一種加權(quán)K 近鄰和多簇合并的密度峰值聚類（weighted K-nearest neighbors and multicluster merge density peaks clustering，WKMM-DPC）算法。WKMM-DPC 算法在計(jì)算樣本的局部密度時(shí)采用加權(quán)K 近鄰思想，引入樣本的權(quán)重系數(shù)，重新定義并計(jì)算樣本的局部密度，使樣本局部密度更加依賴于K 近鄰內(nèi)樣本的位置，統(tǒng)一了樣本局部密度定義的度量準(zhǔn)則；采用一種新的類簇間相似性的度量準(zhǔn)則，并據(jù)此度量準(zhǔn)則，對(duì)潛在類簇進(jìn)行合并，直到潛在類簇個(gè)數(shù)等于實(shí)際類簇個(gè)數(shù)為止。

1 相關(guān)工作

1.1 DPC 算法

DPC 算法定義了兩個(gè)重要的概念：一個(gè)是樣本的局部密度ρ，另一個(gè)是樣本與具有更高局部密度樣本的最小距離δ。

對(duì)于給定數(shù)據(jù)集X=[,,…,x]，其中x=[x,x,…,x]，為樣本個(gè)數(shù)，為樣本維數(shù)。樣本x的局部密度表示為ρ，其計(jì)算公式如式（1）所示：

其中，d為樣本x與x之間的距離，為截?cái)嗑嚯x。當(dāng)d-＜0 時(shí)，(d-)=1；否則，(d-)=0。

對(duì)于小規(guī)模數(shù)據(jù)集，DPC 采用高斯核函數(shù)定義樣本的局部密度，其計(jì)算公式如式（2）所示：

相對(duì)距離δ指樣本與密度比它高且距離它最近樣本的距離。 δ計(jì)算公式如式（3）所示：

對(duì)于密度最大的樣本，δ定義為：

密度峰值通常是局部密度較高且相對(duì)距離較大的樣本。DPC 算法選擇決策值γ較大的樣本作為密度峰值，γ的計(jì)算公式如下：

找到密度峰值后，DPC 將剩余樣本分配給密度比它高且距它最近的樣本所在類簇。

1.2 DPC 算法缺陷分析

實(shí)驗(yàn)證明，DPC 算法在多數(shù)情況下都有不錯(cuò)的聚類性能，但仍然存在以下缺陷：

（1）DPC 算法的樣本局部密度定義的度量準(zhǔn)則不統(tǒng)一且兩者的聚類結(jié)果存在較大差異。DPC 算法有兩種局部密度定義方式：截?cái)嗪撕透咚购?。采用截?cái)嗪擞?jì)算大規(guī)模數(shù)據(jù)集時(shí)，聚類效果更好，小規(guī)模數(shù)據(jù)集，采用高斯核的效果更佳。然而，沒有客觀的度量標(biāo)準(zhǔn)來衡量數(shù)據(jù)集是大規(guī)模還是小規(guī)模，并且選擇不同的密度度量準(zhǔn)則會(huì)對(duì)聚類結(jié)果造成較大影響。如圖1 所示，取相同值時(shí)，分別使用高斯核和截?cái)嗪藢?duì)flame 數(shù)據(jù)集進(jìn)行聚類的結(jié)果可以看出，對(duì)于同一數(shù)據(jù)集，聚類效果依據(jù)局部密度定義方式選擇的不同而存在較大差異。

圖1 DPC 算法對(duì)flame數(shù)據(jù)集的聚類結(jié)果(dc=2)Fig.1 Clustering result of DPC for flame dataset (dc=2)

（2）DPC 算法的分配策略易產(chǎn)生分配連帶錯(cuò)誤。DPC 的分配策略將非密度峰值分配給距其最近且密度比它大的樣本所在類簇，該樣本分配策略會(huì)形成類似“多米諾骨牌效應(yīng)”，即一旦某一個(gè)樣本分配錯(cuò)誤，會(huì)導(dǎo)致后續(xù)一連串的樣本分配錯(cuò)誤。

如圖2 所示，樣本是數(shù)據(jù)集S={208,209,…,227}的局部密度極大值點(diǎn)。該樣本到其他類簇的密度較大值點(diǎn)（圖2 中的樣本）的距離小于它到真實(shí)類簇的密度較大值點(diǎn)（圖2 中的樣本）的距離，因此，樣本被分配到與樣本相同的類簇，致使樣本被錯(cuò)誤分配。樣本分配錯(cuò)誤，會(huì)導(dǎo)致數(shù)據(jù)集合S中的樣本均被錯(cuò)誤分配。這種分配錯(cuò)誤不僅與DPC算法的分配策略缺陷有關(guān)，也和其局部密度定義方式有關(guān)。

圖2 DPC 算法對(duì)Spiral數(shù)據(jù)集的聚類結(jié)果(dc=2)Fig.2 Clustering result of DPC for Spiral dataset (dc=2)

2 WKMM-DPC 算法

通過前文的分析可知，DPC 算法在局部密度定義和分配策略設(shè)計(jì)方面存在缺陷。針對(duì)上述缺陷，本文提出了WKMM-DPC 算法，從局部密度定義和分配策略設(shè)計(jì)兩方面對(duì)DPC 算法進(jìn)行改進(jìn)。

2.1 局部密度定義

K 近鄰（K-nearest neighbours，KNN）是一個(gè)理論上比較成熟的機(jī)器學(xué)習(xí)算法，最早由Cover 和Hart 在1968 年提出，已被廣泛用于分類、回歸、密度估計(jì)及模式識(shí)別等領(lǐng)域。KNN 的目的就是在所有樣本中找到距離目標(biāo)樣本最近的個(gè)近鄰，通常用歐氏距離表示樣本之間的距離。

本文基于加權(quán)K 近鄰思想，引入樣本的權(quán)重系數(shù)，重新定義樣本的局部密度。采用K 近鄰思想后，WKMM-DPC 算法只需要確定一個(gè)參數(shù)，且是一個(gè)整數(shù)，而DPC 算法需要人為主觀選擇局部密度定義的度量準(zhǔn)則和截?cái)嗑嚯x，且截?cái)嗑嚯x的取值無法枚舉，因此本文算法的魯棒性強(qiáng)于DPC算法的魯棒性。

（樣本的權(quán)重系數(shù)）樣本的局部密度定義應(yīng)盡可能準(zhǔn)確反映樣本的局部分布。樣本的權(quán)重系數(shù)定義如下：

式中，d表示樣本x和樣本x之間的歐氏距離，加權(quán)的目標(biāo)是增加樣本局部信息的差異化，更加準(zhǔn)確地反映樣本的相對(duì)位置。

（樣本的局部密度）基于加權(quán)K 近鄰思想，新的樣本局部密度定義為：

圖3 為Aggregation 數(shù)據(jù)集的真實(shí)分布圖，Aggregation 數(shù)據(jù)集由7 個(gè)堆狀類簇組成，類簇間存在交叉纏繞。圖4為DPC和WKMM-DPC算法對(duì)Aggregation數(shù)據(jù)集聚類時(shí)的決策圖，圖中被圈出的點(diǎn)為密度峰值。從圖4（a）可以看出，DPC 算法決策圖里的密度峰值分布散亂，作為密度峰值的特征不明顯，且難以發(fā)現(xiàn)第7 個(gè)密度峰值。從圖4（b）可以看出，WKMMDPC 算法決策圖的密度峰值分布緊湊，且易發(fā)現(xiàn)所有7 個(gè)密度峰值，其中密度峰值的局部密度均接近所有樣本局部密度的最大值，由此說明本文算法新定義的局部密度能夠更加準(zhǔn)確地表征密度峰值的特性。

圖3 Aggregation 數(shù)據(jù)集的真實(shí)分布圖Fig.3 True distribution of Aggregation dataset

圖4 Aggregation 數(shù)據(jù)集的聚類決策圖Fig.4 Decision gragh of Aggregation dataset

2.2 多簇合并策略設(shè)計(jì)

本節(jié)針對(duì)DPC 分配策略存在的分配連帶錯(cuò)誤，提出一種新的類簇間相似性的度量準(zhǔn)則，并據(jù)此度量準(zhǔn)則，設(shè)計(jì)了一種多簇合并策略。

由式（6）和式（7）計(jì)算樣本的局部密度ρ，由式（3）和式（4）計(jì)算樣本的距離δ，通過式（5）計(jì)算決策值γ，對(duì)進(jìn)行排序，選擇前個(gè)樣本作為最終生成類簇的密度峰值，選擇前(≤)個(gè)樣本作為潛在的密度峰值。通過DPC 的分配策略，將非密度峰值分配給密度比它高的最近的樣本，生成個(gè)類簇，最后通過多簇合并策略完成聚類。

（樣本間的相似度）用樣本間的距離度量定義它們的相似度，新的樣本間的相似度如式（8）所示：

其中，ω為樣本和樣本∈()的相似度，兩樣本距離越近，相似程度就越高，相似度也就越大，并且樣本與其個(gè)近鄰點(diǎn)以外的樣本的相似度為0，這使得樣本間的相似度僅與其個(gè)近鄰樣本有關(guān)，減小了無關(guān)數(shù)據(jù)的干擾。

（樣本到類簇的鄰近度）利用樣本間的相似度，定義樣本到類簇的鄰近度，如式（9）所示：

（類簇間的相似度）類簇與類簇間的相似度如式（10）所示：

其中，(C,C)為兩類簇之間的相似度，樣本∈C到C鄰近度的和越大，C和C之間的相似度越大。

針對(duì)DPC 算法分配策略存在的連帶錯(cuò)誤，通過類簇間的相似度進(jìn)行潛在類簇合并。首先，計(jì)算類簇間的相似度，建立類簇相似度矩陣；其次，找到相似度最高的兩類簇，將上述兩類簇合并，直到潛在類簇個(gè)數(shù)等于真實(shí)的類簇個(gè)數(shù)為止。

2.3 算法步驟

輸入：數(shù)據(jù)集data，樣本最近鄰個(gè)數(shù)。

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

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

計(jì)算數(shù)據(jù)集樣本間的歐氏距離，并按距離值升序排列；

根據(jù)式（7）計(jì)算樣本的ρ值；

根據(jù)式（3）、式（4）計(jì)算樣本的δ值；

根據(jù)式（5）計(jì)算樣本的決策值，選出潛在類簇的密度峰值集合，將剩余樣本分配給密度比它高且距離它最近的樣本所在類簇；

根據(jù)式（10）計(jì)算類簇間的相似度(C,C)，建立相似度矩陣，潛在類簇依次進(jìn)行合并，直到潛在類簇個(gè)數(shù)等于真實(shí)類簇個(gè)數(shù)為止。

2.4 算法復(fù)雜度分析

DPC 算法的時(shí)間復(fù)雜度主要由計(jì)算樣本間的距離矩陣的復(fù)雜度，計(jì)算每個(gè)樣本的局部密度的復(fù)雜度和計(jì)算每個(gè)樣本的相對(duì)距離的復(fù)雜度組成。每個(gè)部分的時(shí)間復(fù)雜度均為()，因此總的時(shí)間復(fù)雜度為()。

本文WKMM-DPC 算法的時(shí)間復(fù)雜度主要由四部分組成：（1）計(jì)算樣本間的距離矩陣的復(fù)雜度()；（2）計(jì)算每個(gè)樣本的局部密度的復(fù)雜度()；（3）計(jì)算每個(gè)樣本的相對(duì)距離的復(fù)雜度()；（4）合并潛在類簇，其中，合并潛在類簇的過程中需要計(jì)算樣本間的相似度、樣本到類簇的鄰近度和類簇間相似度，各部分的時(shí)間復(fù)雜度都為()，因此合并潛在類簇總時(shí)間復(fù)雜度為()。因此，本文WKMM-DPC 算法的時(shí)間復(fù)雜度為()，與DPC 算法的時(shí)間復(fù)雜度相同。

對(duì)于樣本規(guī)模為的數(shù)據(jù)集，DPC 算法的空間復(fù)雜度為()。WKMM-DPC 算法比DPC 算法增加了存儲(chǔ)各樣本到其個(gè)近鄰的距離和分配策略中的識(shí)別矩陣，但增加的空間復(fù)雜度不高于(||)，且表示類簇?cái)?shù)的||通常較小，因此，本文WKMM-DPC 算法的空間復(fù)雜度與DPC 算法的空間復(fù)雜度相同。

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

為驗(yàn)證WKMM-DPC 算法的有效性，本文使用人工數(shù)據(jù)集和UCI 數(shù)據(jù)集對(duì)其進(jìn)行測(cè)試和評(píng)價(jià)。表1和表2 詳細(xì)描述了本文實(shí)驗(yàn)所用的數(shù)據(jù)集。將WKMM-DPC 算法與FKNN-DPC、DPCSA（density peaks clustering based on weighted local density sequenceand nearest neighbor assignment）、FNDPC（robust density peaks clustering algorithm using fuzzy neighborhood）、DPC和DBSCAN算法進(jìn)行比較。其中DBSCAN和FNDPC算法參照原文獻(xiàn)使用Matlab2019a編程實(shí)現(xiàn)。DPCSA 算法基于作者提供的源代碼在Matlab2019a中實(shí)現(xiàn)。DPC 算法基于作者提供的源代碼，但由于本文的數(shù)據(jù)集不包含噪聲，刪除“Halo”部分。FKNN-DPC算法無法從論文作者處獲得源代碼，因此參照原文獻(xiàn)實(shí)現(xiàn)了該算法。

表1 人工數(shù)據(jù)集Table 1 Synthetic datasets

表2 UCI數(shù)據(jù)集Table 2 UCI datasets

本文將聚類性能評(píng)價(jià)常用的調(diào)整互信息（adjusted mutual information，AMI）、Fowlkes-Mallows 指 數(shù)（Fowlkes-Mallows index，F(xiàn)MI）、調(diào)整蘭德系數(shù)（adjusted Rand index，ARI）作為聚類性能度量標(biāo)準(zhǔn)。其中，F(xiàn)MI和AMI的取值范圍為[0，1]，ARI取值范圍為[-1,1]，各指標(biāo)值越接近1，表明算法的聚類性能越優(yōu)。實(shí)驗(yàn)環(huán)境：硬件平臺(tái)為IntelCore?i5-7300 CPU@2.50 GHz 2.50 GHz 處理器，8.0 GB 內(nèi)存，Win10 64 bit 操作系統(tǒng)，Matlab2019a軟件。

3.1 算法參數(shù)選擇

為客觀評(píng)價(jià)算法的聚類性能，本文對(duì)各算法進(jìn)行參數(shù)調(diào)優(yōu)，從而保證各算法的最佳聚類效果。WKMMDPC 及FKNN-DPC 算法的值選擇為1～100 間的最優(yōu)值。DPC 算法依據(jù)經(jīng)驗(yàn)法則，將樣本間的距離降序排列，取前1%至2%的距離作為截?cái)嗑嚯x的值。通過實(shí)驗(yàn)發(fā)現(xiàn)，并不是所有數(shù)據(jù)都能在這個(gè)范圍內(nèi)取得最好的結(jié)果，修改這個(gè)百分比以獲得最好的聚類效果。DPCSA 算法設(shè)置了一個(gè)固定參數(shù)，它的取值為5。FNDPC 算法的參數(shù)在0.01～1.00 之間選取。DBSCAN 算法有和兩個(gè)參數(shù)：從0.01 到1.00 之間選取，步長為0.01；從1 到100 之間選取，步長為1。

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

表3 給出了6 種聚類算法對(duì)表1 所示8 個(gè)人工數(shù)據(jù)集聚類結(jié)果的三種評(píng)價(jià)指標(biāo)AMI、ARI、FMI 的值。表3 中的“—”表示沒有對(duì)應(yīng)值，Arg-為各算法的最優(yōu)參數(shù)，加粗的值表示較好的實(shí)驗(yàn)結(jié)果。

表3 6 種聚類算法在8 個(gè)人工數(shù)據(jù)集上的聚類性能Table 3 Performance of 6 clustering algorithms on 8 synthetic datasets

從表3 可以看出，處理Pathbased 數(shù)據(jù)集時(shí)，WKMM-DPC 算法聚類效果低于DBSCAN 和FKNNDPC 算法聚類效果，但要好于其余算法。處理D31數(shù)據(jù)集時(shí)，WKMM-DPC 算法的聚類效果優(yōu)于DBSCAN算法，略低于其余聚類算法。剩余的Spiral、Jain、Flame、Aggregation、S2 和R15 數(shù)據(jù)集上，WKMMDPC算法的聚類效果優(yōu)于或持平與之比較的算法。

圖5～圖12 展示了人工數(shù)據(jù)集的聚類結(jié)果，相同顏色的點(diǎn)屬于同一聚類。除DBSCAN 外，其他方法的聚類中心用“六角星”表示，DBSCAN 算法中的“叉”代表該算法的噪聲點(diǎn)。

圖5 6 種算法對(duì)Aggregation 數(shù)據(jù)集的聚類結(jié)果Fig.5 Clustering results of 6 algorithms on Aggregation dataset

圖6 6 種算法對(duì)Flame數(shù)據(jù)集的聚類結(jié)果Fig.6 Clustering results of 6 algorithms on Flame dataset

圖7 6 種算法對(duì)Jain 數(shù)據(jù)集的聚類結(jié)果Fig.7 Clustering results of 6 algorithms on Jain dataset

圖8 6 種算法對(duì)Pathbased 數(shù)據(jù)集的聚類結(jié)果Fig.8 Clustering results of 6 algorithms on Pathbased dataset

圖9 6 種算法對(duì)Spiral數(shù)據(jù)集的聚類結(jié)果Fig.9 Clustering results of 6 algorithms on Spiral dataset

圖10 6 種算法對(duì)R15 數(shù)據(jù)集的聚類結(jié)果Fig.10 Clustering results of 6 algorithms on R15 dataset

圖11 6 種算法對(duì)D31 數(shù)據(jù)集的聚類結(jié)果Fig.11 Clustering results of 6 algorithms on D31 dataset

圖12 6 種算法對(duì)S2 數(shù)據(jù)集的聚類結(jié)果Fig.12 Clustering results of 6 algorithms on S2 dataset

圖5 顯示了6 種算法對(duì)Aggregation 數(shù)據(jù)集的聚類結(jié)果。Aggregation 數(shù)據(jù)集由7 個(gè)堆狀類簇組成，其特征較為明顯，但類簇間存在交叉纏繞。WKMMDPC 算法的聚類性能最好，它能夠完全正確地發(fā)現(xiàn)密度峰值并完成聚類。對(duì)于DBSCAN 算法，雖然可以比較準(zhǔn)確地完成聚類，但存在一些噪聲點(diǎn)。DPCSA算法不能對(duì)Aggregation 數(shù)據(jù)集最右邊的兩類簇進(jìn)行準(zhǔn)確聚類，產(chǎn)生了較明顯的聚類錯(cuò)誤。

圖6 顯示了6 種算法對(duì)Flame 數(shù)據(jù)集的聚類結(jié)果。DBSCAN 算法會(huì)將一些邊界點(diǎn)識(shí)別為噪聲點(diǎn)。FKNN-DPC 算法可以正確地找到密度峰值，但有兩個(gè)樣本被分配錯(cuò)誤。WKMM-DPC、DPC、DPCSA 和FNDPC 算法均能準(zhǔn)確找到密度峰值并正確分配剩余樣本。

圖7 顯示了6 種算法對(duì)Jain 數(shù)據(jù)集的聚類結(jié)果。Jain 數(shù)據(jù)集由兩個(gè)月牙形的類簇組成，且樣本密度分布不均勻。從圖7 可以看出，由于下面類簇樣本比較密集，DPC 和DPCSA 算法均在下面的類簇中找到兩個(gè)密度峰值，從而導(dǎo)致密集類簇中的部分樣本錯(cuò)誤分配。DPSCAN、FKNN-DPC 和FNDPC 算法均不能對(duì)Jain 數(shù)據(jù)集進(jìn)行準(zhǔn)確聚類，WKMM-DPC 算法可以同時(shí)發(fā)現(xiàn)正確的密度峰值和完成聚類。

圖8 顯示了6 種算法對(duì)于Pathbased 數(shù)據(jù)集的聚類結(jié)果。Pathbased 數(shù)據(jù)集是一個(gè)復(fù)雜的流形數(shù)據(jù)集，由3 個(gè)類簇組成，其特別之處在于一個(gè)環(huán)型類簇包圍了其余兩個(gè)類簇，由于環(huán)型類簇之間聯(lián)系緊密，剩余的樣本分配很容易發(fā)生錯(cuò)誤。DBSCAN 算法和FKNN-DPC 算法對(duì)Pathbased 數(shù)據(jù)集的聚類效果較好，剩余聚類算法對(duì)Pathbased 數(shù)據(jù)集的聚類效果均不太理想。

圖9 顯示了6 種算法對(duì)Spiral 數(shù)據(jù)集的聚類結(jié)果。Spiral 數(shù)據(jù)集是由3 個(gè)螺旋類簇組成的流形數(shù)據(jù)集。除了密度峰值的選取不同，所有的聚類算法都能正確地分配剩余的樣本。

6 種算法得到的R15 數(shù)據(jù)集的聚類結(jié)果如圖10所示。R15 數(shù)據(jù)集包含15 個(gè)類簇。最外層的7 個(gè)類簇距離較遠(yuǎn)，所有的聚類算法都能正確聚類這7 個(gè)類簇，最里面的8 個(gè)類簇彼此相鄰且交叉纏繞，因此這8個(gè)類簇的樣本容易被錯(cuò)誤分配。從圖10 可以看出，所有聚類算法都能較好地對(duì)R15 數(shù)據(jù)集進(jìn)行聚類，只是最里面8 個(gè)類簇的個(gè)別樣本會(huì)產(chǎn)生分配錯(cuò)誤。

圖11 顯示了6 種算法對(duì)D31 數(shù)據(jù)集的聚類結(jié)果。各算法對(duì)該數(shù)據(jù)集均能獲得較好的聚類效果，F(xiàn)KNN-DPC 算法的聚類效果最好，但是DBSCAN 算法卻將一些點(diǎn)標(biāo)記為噪聲點(diǎn)，使得最終的聚類結(jié)果有所偏差。

圖12 顯示了6 種算法對(duì)S2 數(shù)據(jù)集的聚類結(jié)果。S2 數(shù)據(jù)集包含15 個(gè)類簇。其中，WKMM-DPC 算法的聚類效果最好，而DBSCAN 算法卻將右下角的三個(gè)簇合并成了一個(gè)簇，并且將許多的邊界點(diǎn)標(biāo)記為噪聲點(diǎn)，其余的聚類算法均能達(dá)到較好的聚類效果。

Friedman 檢驗(yàn)是一種顯著性差異檢驗(yàn)方法，其秩均值體現(xiàn)了算法的綜合表現(xiàn)。為展現(xiàn)算法的綜合性能，采用Friedman 檢驗(yàn)分別對(duì)AMI、ARI、FMI 評(píng)價(jià)指標(biāo)進(jìn)行了秩均值檢驗(yàn)。實(shí)驗(yàn)中，秩均值越大，對(duì)應(yīng)算法綜合的性能越好。人工數(shù)據(jù)集中的三種聚類評(píng)價(jià)指標(biāo)的Friedman 檢驗(yàn)值如表4 所示。

由表4 可知，在3 種聚類評(píng)價(jià)指標(biāo)上，WKMMDPC 算法的秩均值均排行第一，F(xiàn)KNN-DPC 排行第二。綜合分析可知，6 種比較的聚類算法中，WKMMDPC 算法的綜合性能最優(yōu)。

表4 3 種評(píng)價(jià)指標(biāo)在人工數(shù)據(jù)集上的Friedman 檢驗(yàn)值Table 4 Friedman test value of 3 evaluation indices on synthetic datasets

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

為進(jìn)一步驗(yàn)證WKMM-DPC 算法的聚類性能。在8 個(gè)UCI數(shù)據(jù)集上將WKMM-DPC 算法與另外5 種聚類算法進(jìn)行比較。6 種算法對(duì)UCI 數(shù)據(jù)集的聚類結(jié)果如表5 所示。實(shí)驗(yàn)結(jié)果表明，處理Wine 數(shù)據(jù)集時(shí)，WKMM-DPC 算法的聚類效果低于FNDPC 和FKNN-DPC 算法。處理Seeds 數(shù)據(jù)集時(shí)，WKMMDPC 算法的聚類效果低于FKNN-DPC、FNDPC 和DPC 算法。處理Waveform 數(shù)據(jù)集時(shí)，WKMM-DPC算法的聚類效果略遜于FNDPC 算法，但好于其余算法。剩余的Ecoli、Libras、Dermatology 和Glass 數(shù) 據(jù)集，WKMM-DPC 算法的聚類效果都要優(yōu)于與之比較的算法。

表5 6 種聚類算法在8 個(gè)UCI數(shù)據(jù)集上的聚類性能Table 5 Performance of 6 clustering algorithms on 8 UCI datasets

UCI 數(shù)據(jù)集上的三種聚類評(píng)價(jià)指標(biāo)的Friedman檢驗(yàn)值如表6 所示。由表6 可知，3 種聚類評(píng)價(jià)指標(biāo)上，WKMM-DPC 算法的秩均值均排行第一，F(xiàn)KNNDPC 排行第二。綜合分析可知，在6 種比較的聚類算法中，WKMM-DPC 算法的綜合性能最優(yōu)。

表6 3 種評(píng)價(jià)指標(biāo)在UCI數(shù)據(jù)集上的Friedman 檢驗(yàn)值Table 6 Friedman test value of 3 evaluation indices on UCI datasets

4 結(jié)束語

DPC 算法存在局部密度定義的度量準(zhǔn)則不統(tǒng)一和分配策略易產(chǎn)生分配連帶錯(cuò)誤的問題，針對(duì)這兩個(gè)問題，本文提出了一種加權(quán)K 近鄰和多簇合并的密度峰值聚類算法。WKMM-DPC 算法結(jié)合加權(quán)K近鄰的思想，重新定義了局部密度，增強(qiáng)了樣本與其個(gè)最近鄰樣本之間的聯(lián)系，解決了DPC 算法局部密度定義的度量準(zhǔn)則不統(tǒng)一的問題。同時(shí)，WKMMDPC 算法采用了多簇合并策略，緩解了DPC 算法分配策略存在的分配連帶錯(cuò)誤。在人工數(shù)據(jù)集及UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，WKMM-DPC 算法能夠更加準(zhǔn)確地找到數(shù)據(jù)集的密度峰值和處理各種形狀的數(shù)據(jù)集，且算法的聚類性能優(yōu)異。隨著大數(shù)據(jù)時(shí)代的到來，數(shù)據(jù)正向海量數(shù)據(jù)、高維樣本方向發(fā)展，傳統(tǒng)基于樣本間的距離度量定義相似度的方式面臨算法時(shí)空復(fù)雜性高等弊端，因此，研究新的更高級(jí)度量樣本間相似性的方式將是今后的研究熱點(diǎn)和難點(diǎn)。