去中心化加權(quán)簇歸并的密度峰值聚類算法

趙力衡，王 建，陳虹君

1.成都錦城學(xué)院 電子信息學(xué)院，成都611731

2.四川大學(xué) 計(jì)算機(jī)學(xué)院，成都610041

聚類算法是模式識(shí)別和數(shù)據(jù)挖掘領(lǐng)域中的一類常見的無監(jiān)督算法。算法通過某種相似性計(jì)算將一組數(shù)據(jù)對(duì)象按照其自身的特征劃分到不同的類簇中，并使同一簇內(nèi)的對(duì)象盡可能相似，不同簇之間的對(duì)象盡可能不相似?，F(xiàn)有聚類算法模型豐富，大致可以分為層次聚類、劃分聚類、密度聚類、網(wǎng)格聚類、圖論聚類、代表點(diǎn)聚類和模型聚類七種類型，被廣泛應(yīng)用于生物、能源、交通、圖像處理、流形數(shù)據(jù)處理等領(lǐng)域。

聚類算法自應(yīng)用以來，不斷有學(xué)者提出新的聚類算法，Rodriguez 等人于2014 年在上提出了快速搜索和尋找密度峰值聚類算法（clustering by fast search and find of density peaks，DPC）。該算法是一種基于密度的聚類算法，依據(jù)樣本的分布密度能無需迭代地快速找出任意形狀數(shù)據(jù)集中的密度峰值樣本，以之作為聚類中心，從而能夠較高效地得到高精確的聚類結(jié)果。DPC 算法因此受到了廣泛的關(guān)注，但該算法依舊存在著一些缺陷：（1）圍繞聚類中心點(diǎn)進(jìn)行聚類，若聚類中心點(diǎn)選取不當(dāng)會(huì)對(duì)聚類結(jié)果造成顯著影響；（2）DPC 算法需要人工指定聚類中心，使算法的自動(dòng)化程度受到影響；（3）截?cái)嗑嚯x只考慮了數(shù)據(jù)的分布密度，忽略了數(shù)據(jù)的內(nèi)部特征，影響了聚類結(jié)果的穩(wěn)定；（4）DPC 在聚類過程中若存在樣本分配錯(cuò)誤，則錯(cuò)誤樣本鄰近密度更低的樣本將可能隨之被分配到錯(cuò)誤的類簇中，從而放大錯(cuò)誤。

為解決這些問題，近年來眾多學(xué)者對(duì)DPC算法進(jìn)行了改進(jìn)。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）。該算法基于K 近鄰設(shè)計(jì)了一種獨(dú)立于數(shù)據(jù)集規(guī)模且與截?cái)嗑嚯x無關(guān)的局部密度計(jì)算方式，將數(shù)據(jù)集劃分成核心樣本和離群樣本，再采用新的K 近鄰策略完成對(duì)非聚類中心點(diǎn)的分配，有效緩解了DPC 算法的跟隨錯(cuò)誤。Seyed等人提出了基于動(dòng)態(tài)圖的密度峰值聚類標(biāo)簽傳播算法（dynamic graph-based label propagation for density peaks clustering，DPC-DLP）。算法根據(jù)重新定義的K近鄰密度確定出聚類中心點(diǎn)，然后將類簇中心點(diǎn)和其相鄰中心點(diǎn)形成一個(gè)KNN 圖，最后采用圖的標(biāo)簽傳播方法分配剩余樣本，更適用于圖像聚類。丁世飛等人提出了一種基于不相似性度量?jī)?yōu)化的密度峰值聚類算法（optimized density peaks clustering algorithm based on dissimilarity measure，DDPC）。算法通過基于塊的不相似性度量實(shí)現(xiàn)樣本間的相似度計(jì)算，從而避免了小樣本數(shù)據(jù)集上截?cái)嗑嚯x對(duì)聚類結(jié)果的影響，提高了在高維度數(shù)據(jù)集上的聚類效果。Liu 等人提出了基于共享近鄰的密度峰值聚類算法（sharednearest-neighbor-based clustering by fast search and find of density peaks，SNN-DPC）。算法通過計(jì)算樣本之間共享的近鄰點(diǎn)個(gè)數(shù)，確定樣本之間的相似度，避免了非聚類中心點(diǎn)分配時(shí)的跟隨錯(cuò)誤。王大剛等人提出了基于二階近鄰的密度峰值聚類算法（density peaks clustering algorithm based on second-orderneighbors，SODPC）。算法通過引入樣本的二階近鄰計(jì)算直接密度和間接密度，避免了截?cái)嗑嚯x帶來的影響。

本文所知文獻(xiàn)對(duì)DPC 算法的改進(jìn)主要著眼于聚類中心點(diǎn)的選取、避免分配跟隨錯(cuò)誤及效率等方面，沒有采用無中心點(diǎn)聚類的優(yōu)化算法。嘗試提出一種去中心化加權(quán)簇歸并的密度峰值聚類算法（densitypeak clustering algorithm on decentralized and weighted clusters merging，DCM-DPC）。算法在聚類過程中取消了聚類中心點(diǎn)的概念，認(rèn)為位于彼此鄰域內(nèi)的局部高密度樣本屬于同一類簇，采用加權(quán)近鄰思想，重新定義了樣本鄰域半徑，從而劃分出位于不同區(qū)域的局部高密度樣本組，并在尋找樣本組的過程中歸并存在鄰域重疊的區(qū)域，形成歸并的核心樣本組，最后將剩余樣本按其近鄰樣本的眾數(shù)歸屬到某個(gè)核心樣本組中完成聚類。實(shí)驗(yàn)結(jié)果表明，DCM-DPC 算法有效避免了由聚類中心點(diǎn)和截?cái)嗑嚯x帶來的誤差，并在聚類效果上有明顯的提高。

1 DPC 算法

DPC 算法基于樣本密度實(shí)現(xiàn)對(duì)數(shù)據(jù)集的聚類，算法假設(shè)類簇中心具有以下兩個(gè)特征：（1）聚類中心點(diǎn)的局部密度高于周圍樣本的局部密度；（2）聚類中心點(diǎn)之間的距離相對(duì)較遠(yuǎn)。對(duì)于給定的數(shù)據(jù)集={,,…,x}，設(shè)每個(gè)元素的維度為。DPC 算法定義樣本x的局部密度ρ為：

其中，d表示樣本x與樣本x之間的距離。為截?cái)嗑嚯x，定義為中任意兩個(gè)樣本之間的距離按升序排列后位于用戶指定位置的值。對(duì)于函數(shù)()有：

當(dāng)數(shù)據(jù)集規(guī)模較小時(shí)，DPC 采用高斯核函數(shù)描述局部密度：

相對(duì)距離δ表示樣本x距離局部密度比它高且離它最近的樣本的距離，當(dāng)x不是最大密度樣本點(diǎn)時(shí)δ為：

當(dāng)x是最大密度樣本點(diǎn)時(shí)δ為：

DPC 算法使用局部密度ρ和相對(duì)距離δ繪制出決策圖，并選取γ最大的若干個(gè)樣本作為聚類中心，聚類中心個(gè)數(shù)由用戶指定：

以這些密度峰值點(diǎn)作為聚類中心，剩余的非聚類中心樣本被分配給局部密度更高且距離最近的樣本所在類簇，從而完成聚類。

DPC 算法在多數(shù)時(shí)候能獲得不錯(cuò)的聚類結(jié)果，但尚存在一些不足：

（1）圍繞聚類中心點(diǎn)進(jìn)行聚類，即首先找出聚類中心點(diǎn)，然后非聚類中心點(diǎn)依據(jù)聚類中心點(diǎn)進(jìn)行分配，從而完成聚類。截?cái)嗑嚯x是影響聚類中心選取的重要因素，圖1（a）和圖1（b）分別是flame 數(shù)據(jù)集在截?cái)嗑嚯x取5%和2%時(shí)的聚類結(jié)果，圖中十字符號(hào)為聚類中心。可以看出，當(dāng)截?cái)嗑嚯x不同時(shí)選取的距離中心不相同，聚類結(jié)果也出現(xiàn)顯著差異。聚類過程中，不同截?cái)嗑嚯x除了影響聚類中心的選取外，還會(huì)引起局部密度等計(jì)算的變化，同樣會(huì)影響聚類結(jié)果。因此，為消除聚類中心因素外其他因素對(duì)聚類結(jié)果的影響，圖1（c）中將聚類效果優(yōu)秀的截?cái)嗑嚯x采用5%的聚類中心替換為截?cái)嗑嚯x采用2%的聚類中心，替換后聚類結(jié)果中大部分樣本被識(shí)別為離散點(diǎn)，聚類效果極差?？梢娋垲愔行牡倪x擇可能顯著影響聚類效果。

（2）通過決策圖選取聚類中心，但聚類中心個(gè)數(shù)仍需人工指定，使算法的自動(dòng)化程度受到影響。

（3）截?cái)嗑嚯x由用戶主觀選擇，只體現(xiàn)了數(shù)據(jù)的分布密度，沒有體現(xiàn)數(shù)據(jù)的內(nèi)部特征，因此截?cái)嗑嚯x的改變?nèi)菀资咕垲惤Y(jié)果變得不穩(wěn)定。

（4）非聚類中心樣本被分配給鄰域密度大于該樣本且距離其最近的樣本所屬的類簇。若一個(gè)樣本分配錯(cuò)誤，則該樣本鄰域內(nèi)其他密度更小的樣本就可能跟隨該樣本被分配到錯(cuò)誤的類簇，形成“多米諾”效應(yīng)，導(dǎo)致聚類結(jié)果不理想。

2 DCM-DPC 算法

針對(duì)上述不足，本文嘗試提出一種基于去中心化加權(quán)簇歸并的密度峰值算法（DCM-DPC），從消除聚類中心、簇歸并和非核心樣本分配策略三方面對(duì)DPC 算法進(jìn)行改進(jìn)。

2.1 去中心化的加權(quán)核心樣本組策略

根據(jù)圖1 的分析可以發(fā)現(xiàn)，聚類中心點(diǎn)的質(zhì)量很重要，甚至能顯著影響聚類效果，因此找出合適的聚類中心是現(xiàn)有密度峰值聚類算法的關(guān)鍵。從聚類算法的本質(zhì)看，聚類是將相似的樣本劃分在一起，而不是將樣本圍繞某個(gè)中心點(diǎn)劃分在一起，因此聚類中心并不是必須的，若能識(shí)別出相似的樣本，就能完成聚類。

圖1 不同聚類中心點(diǎn)的聚類效果對(duì)比圖Fig.1 Clustering effect contrast diagram of different clustering centers

本文所知的DPC 改進(jìn)算法文獻(xiàn)均依賴于聚類中心點(diǎn)進(jìn)行聚類，并沒有在消除聚類中心方向進(jìn)行優(yōu)化。嘗試提出一種新的去中心化聚類的核心樣本組策略取代聚類中心點(diǎn)作為樣本劃分依據(jù)。核心樣本組指具有較高局部密度且位于同一較高密度區(qū)域樣本的集合，采用基于近鄰思想的加權(quán)鄰域半徑來度量局部密度。近鄰思想目標(biāo)是找出加權(quán)鄰域半徑內(nèi)的所有樣本數(shù)量。

DPC 算法使用截?cái)嗑嚯x作為鄰域半徑，以截?cái)嗑嚯x內(nèi)的樣本數(shù)量作為局部密度。由于截?cái)嗑嚯x是人為主觀選擇，難以準(zhǔn)確反映數(shù)據(jù)的分布特征，為此本文給出了新的局部密度及相關(guān)定義：

（權(quán)重系數(shù)）設(shè)定權(quán)重系數(shù)如下：

（加權(quán)鄰域半徑）設(shè)定加權(quán)鄰域半徑如下：

式中，d表示樣本x與x之間的距離。

（2）修正系數(shù)p，數(shù)據(jù)集中的離散點(diǎn)對(duì)樣本間距離均值的影響明顯，容易導(dǎo)致鄰域半徑過大而失真，峰度系數(shù)對(duì)此修正不足，因此引入該系數(shù)用于修正鄰域半徑范圍。

（局部密度）局部密度定義如下：

式中，為式（8）中表示的加權(quán)鄰域半徑。

以加權(quán)鄰域半徑內(nèi)的樣本數(shù)量作為局部密度，同時(shí)考慮到了數(shù)據(jù)的密度和內(nèi)部結(jié)構(gòu)的差異，能有效描述樣本的分布狀況，從而提升聚類效果。

算法依據(jù)局部密度將樣本劃分為核心樣本、非核心樣本和離散樣本。

（核心樣本、非核心樣本及離散樣本）核心樣本c指在加權(quán)鄰域半徑內(nèi)的局部密度高于指定閾值m的數(shù)據(jù)點(diǎn)。非核心樣本b指內(nèi)密度不高于指定閾值m的數(shù)據(jù)點(diǎn)。離散樣本s指內(nèi)不存在可以歸屬于任意簇的樣本的數(shù)據(jù)點(diǎn)，如式（10）所示：

其中，ε表示x鄰域半徑內(nèi)的樣本，A表示任意類簇。

本文算法以近鄰樣本之間共享的樣本數(shù)來度量樣本之間相似度。樣本劃分依據(jù)是，核心樣本的近鄰樣本較多，因此容易判斷與近鄰樣本之間的相似性，從而與相似樣本組成類簇，并可作為聚類的依據(jù)。非核心樣本通常位于較低局部密度的區(qū)域，由于近鄰樣本較少，不容易判斷該樣本與近鄰樣本的相似性，若作為聚類依據(jù)，容易發(fā)生漂移。若樣本無近鄰點(diǎn)或雖有近鄰點(diǎn)但這些近鄰點(diǎn)都不屬于任何類簇，則該樣本同樣不能歸屬于任一類簇，因此需要被標(biāo)注為離散樣本。三者的關(guān)系是，核心樣本集與非核心樣本集互斥互補(bǔ)，離散樣本集則是非核心樣本集的子集。

DPC 算法認(rèn)為聚類中心點(diǎn)的局部密度在其周圍樣本中最高，可推斷聚類中心點(diǎn)位于局部密度較高的區(qū)域，且其近鄰存在局部密度較高的其他核心樣本。如圖2 所示，若樣本1 是DPC 算法的聚類中心點(diǎn)，在鄰域半徑內(nèi)密度最高，樣本3 是樣本1 鄰域內(nèi)一個(gè)局部密度較高的核心樣本，顯然兩者有較高的相似性。DPC 算法認(rèn)為聚類核心彼此距離較遠(yuǎn)，可以推斷樣本3 附近不存在其他聚類核心，可知樣本3 歸屬于樣本1 所在的類簇。同理，假設(shè)樣本2 是樣本3 鄰域內(nèi)另一個(gè)核心樣本，則樣本2 與樣本3 也具有較高的相似性，且同屬于樣本1 所在類別。

圖2 數(shù)據(jù)分布示意圖Fig.2 Schematic diagram of data distribution

可以發(fā)現(xiàn)，位于聚類中心點(diǎn)鄰域半徑內(nèi)的核心樣本和位于這些核心樣本鄰域半徑內(nèi)的其他核心樣本同屬于該聚類中心所在的類簇。樣本4 是樣本1鄰域內(nèi)的非核心樣本，近鄰點(diǎn)較少因此與其近鄰點(diǎn)相似度都不高，難以確定是否屬于同一類別。顯然，非核心樣本的近鄰樣本中屬于某個(gè)類簇的樣本越多，該非核心樣本就與該類簇越相似。因此本文算法以非核心樣本的近鄰點(diǎn)所屬類簇的眾數(shù)確定其歸屬。離散樣本5、6 因沒有可以歸屬于任意類簇的近鄰點(diǎn)，所以不屬于任何類簇?？梢姡?dāng)聚類中心確定時(shí)，屬于該類簇的核心樣本成員，即核心樣本組，亦就可以確定了，DPC 算法的聚類中心點(diǎn)就是核心樣本組中密度最高的點(diǎn)。核心樣本組的尋找可以從任意核心樣本開始，找出其近鄰核心點(diǎn)，進(jìn)而擴(kuò)散到整個(gè)數(shù)據(jù)集，從而實(shí)現(xiàn)無中心點(diǎn)的聚類。

圖3（a）展示了Aggregation 數(shù)據(jù)集的樣本分布圖，由7 個(gè)相鄰且不同形狀的類簇構(gòu)成，分別以不同的顏色表示。圖3（b）是該數(shù)據(jù)集不同類簇的核心樣本和非核心樣本的分布圖，不同類簇的核心樣本顏色與圖3（a）中相同類簇的顏色相同，非核心樣本則以其他顏色表示?？梢园l(fā)現(xiàn)，每個(gè)類簇的核心樣本都集中在類簇中間密度較高的區(qū)域，非核心樣本則圍繞在核心樣本組的周圍局部密度較低的區(qū)域，且當(dāng)類簇密度較高時(shí)，該類簇的核心樣本也較多，反之則偏少?？梢?，由核心樣本構(gòu)成的核心樣本組在反映密度峰值的意義上與DPC 算法的聚類中心是一致的。DPC 算法依據(jù)聚類中心聚類時(shí)，若樣本密度差異較大，同一類簇中可能找到多個(gè)密度峰值，使聚類結(jié)果不理想，而核心樣本組則會(huì)將這些密度峰值劃分到同一核心樣本組中，從而避免該現(xiàn)象。因此核心樣本組不但能夠成為聚類的依據(jù)，而且聚類效果優(yōu)于DPC 算法使用的聚類中心。

圖3 Aggregation 數(shù)據(jù)分布圖Fig.3 Distribution map of Aggregation dataset

2.2 簇歸并策略

在給定數(shù)據(jù)集中，互為近鄰的核心樣本構(gòu)成代表一個(gè)簇的核心樣本組。識(shí)別核心樣本的步驟中，只有核心樣本會(huì)記錄到代表類簇的核心樣本組中，此時(shí)核心樣本組等價(jià)于類簇。由于樣本的順序通常是未經(jīng)排序的，當(dāng)順序遍歷數(shù)據(jù)集尋找核心樣本時(shí)，識(shí)別出的核心樣本通常也是無序的，因此聚類過程中由核心樣本組構(gòu)成的類簇是變化的。由上節(jié)分析可知，互為近鄰的核心樣本屬于同一類簇，因此當(dāng)聚類過程中發(fā)現(xiàn)不同的核心樣本組中存在相互近鄰的樣本時(shí)，表明這些樣本組中的元素應(yīng)屬于同一類簇，需要將這些核心樣本組歸并成一個(gè)。

如圖4 所示，核心樣本按標(biāo)號(hào)順序被識(shí)別出。核心樣本3 被識(shí)別時(shí)由于沒有位于樣本1 的鄰域半徑內(nèi)，樣本1 與樣本3 此時(shí)應(yīng)分別屬于不同的簇（核心樣本組）。當(dāng)同時(shí)位于二者鄰域半徑內(nèi)的樣本5 被識(shí)別出時(shí)，可以發(fā)現(xiàn)三個(gè)樣本是相似的，樣本1 和樣本3所在的簇是相似簇，需要以樣本5 為介質(zhì)進(jìn)行歸并。若不同核心樣本所在簇不相似，則不進(jìn)行歸并，如樣本1、3、5 和樣本2、4 所在的簇。

圖4 核心樣本組歸并示意圖Fig.4 Schematic diagram of core sample groups

（類簇相似度）類簇相似度定義如下：

式中，C和C分別表示類簇A和A的核心樣本組，c是C和C共享的核心樣本。當(dāng)(A,A)≥1時(shí)，類簇A和A相似。

當(dāng)識(shí)別出所有核心樣本后，沒有歸并的簇就組成了全部核心樣本組。

2.3 非核心樣本歸屬判定策略

樣本與近鄰點(diǎn)是相似的，越多近鄰點(diǎn)屬于同一類簇，表示樣本與該類簇越相似，因此非核心樣本b的歸屬采用近鄰點(diǎn)所屬類簇的眾數(shù)來決定，包含b近鄰點(diǎn)數(shù)p最多的類簇即為b最相似的類簇：

其中，N(b)∈A表示樣本b屬于類簇A的近鄰點(diǎn)數(shù)量。當(dāng)p=0 時(shí)，表示b為離散點(diǎn)。

DPC 算法中非聚類中心樣本x單純依賴于距離最近且局部密度更高的樣本x，若x分配錯(cuò)誤，x會(huì)跟隨分配錯(cuò)誤，容錯(cuò)率很低。本文算法使非核心樣本的分配由多個(gè)近鄰點(diǎn)共同決定，大幅提高了樣本劃分的容錯(cuò)率，因此能有效避免跟隨錯(cuò)誤。

特別是當(dāng)數(shù)據(jù)集中出現(xiàn)類簇糾纏時(shí)，邊界樣本更容易出現(xiàn)距離其他類簇中有更高局部密度的樣本更近的現(xiàn)象，因此本文算法相對(duì)于DPC 算法能更準(zhǔn)確地識(shí)別出邊界樣本的所屬類簇，使邊界樣本的分配更加精確可靠。

2.4 算法步驟

為消除樣本屬性之間量綱不一致帶來的影響，本文將在計(jì)算前對(duì)數(shù)據(jù)進(jìn)行歸一化處理，將原始屬性值通過線性變換映射到[0,1]區(qū)間。

（數(shù)據(jù)歸一化）樣本x的屬性歸一化定義如下：

式中，max(x)為樣本x的屬性的最大值，min(x)為樣本x的屬性的最小值。

算法步驟如下：

輸入：數(shù)據(jù)集={,,…,x}；核心對(duì)象鄰域密度閾值m；鄰域半徑修正權(quán)值p。

根據(jù)式（13）對(duì)數(shù)據(jù)歸一化。

根據(jù)式（8）計(jì)算加權(quán)鄰域半徑。

根據(jù)式（9）計(jì)算樣本鄰域密度ρ，然后根據(jù)式（9）劃分樣本：

將ρ＞m的樣本錄入其近鄰核心樣本所在核心樣本組，若樣本的近鄰核心樣本還未被識(shí)別或無近鄰核心樣本，則該樣本錄入新核心樣本組；

將ρ≤m的樣本錄入非核心對(duì)象隊(duì)列中；

每當(dāng)識(shí)別出一個(gè)核心樣本時(shí)，檢查該樣本是否為核心樣本組的共享樣本，如果是則合并相似類簇。

完成核心樣本識(shí)別后，對(duì)非核心樣本按其近鄰點(diǎn)所屬類簇的眾數(shù)，降序歸入最相似的類簇中。

標(biāo)識(shí)非核心樣本隊(duì)列中剩余沒有近鄰點(diǎn)的樣本為離散點(diǎn)。

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

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

對(duì)于樣本規(guī)模為的數(shù)據(jù)集，DPC 算法的時(shí)間復(fù)雜度主要來自計(jì)算任意兩個(gè)樣本間的距離、計(jì)算所有樣本的局部密度以及計(jì)算每對(duì)樣本之間的相對(duì)距離。每部分的時(shí)間復(fù)雜度均為()，因此DPC 算法的總時(shí)間復(fù)雜度為()。

本文DCM-DPC 算法的時(shí)間復(fù)雜度主要來源于：（1）計(jì)算數(shù)據(jù)集加權(quán)鄰域半徑的時(shí)間復(fù)雜度()。（2）計(jì)算每個(gè)樣本的局部密度的時(shí)間復(fù)雜度()。（3）簇歸并的時(shí)間復(fù)雜度()，其中為核心樣本個(gè)數(shù)，小于樣本個(gè)數(shù)，因此()＜()。（4）劃分非核心樣本并標(biāo)注離散點(diǎn)的時(shí)間復(fù)雜度＜()，其中為樣本的近鄰點(diǎn)個(gè)數(shù)，?，相比來說可以忽略不記；為非核心樣本個(gè)數(shù)，＜，且+=，有()≈()＜()，因此本文算法總時(shí)間復(fù)雜度為()，與DPC 算法的時(shí)間復(fù)雜度相同。

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

3.1 實(shí)驗(yàn)數(shù)據(jù)集與評(píng)估指標(biāo)

為驗(yàn)證DCM-DPC 算法的有效性，本文采用人工數(shù)據(jù)集與UCI 數(shù)據(jù)集進(jìn)行測(cè)試和評(píng)估。為使測(cè)試數(shù)據(jù)多樣化，選取的數(shù)據(jù)集在樣本數(shù)量、屬性數(shù)和類簇?cái)?shù)跨度較大，這些數(shù)據(jù)集皆廣泛地應(yīng)用于聚類算法有效性的測(cè)試。數(shù)據(jù)集具體屬性如表1 和表2 所示。

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

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

在以上數(shù)據(jù)集上選擇DPC、FKNN-DPC、SNNDPC、DBSCAN和-means++算法與本文DCMDPC 算法進(jìn)行比較。其中，DPC 和SNN-DPC 算法使用的是作者公開的源代碼，F(xiàn)KNN-DPC、DBSCAN 和-means++算法參照原文獻(xiàn)使用Python3.8 實(shí)現(xiàn)。本文依據(jù)參考文獻(xiàn)對(duì)各算法的參數(shù)均進(jìn)行了調(diào)優(yōu)，以保證各算法的聚類效果。-means++算法因初始聚類中心的選取具有隨機(jī)性會(huì)影響聚類結(jié)果，表3 和表4中采用100 次聚類結(jié)果的均值。

評(píng)估指標(biāo)采用調(diào)整互信息（adjusted mutual information，AMI）、調(diào)整蘭德系數(shù)（adjusted Rand index，ARI）和FMI 指數(shù)（Fowlkes Mallows index，F(xiàn)MI）。其中，AMI和FMI取值范圍為[0,1]，ARI取值范圍為[-1,1]，三者均是越接近1，表明聚類效果越優(yōu)。

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

表3 展示了6 種算法在UCI 數(shù)據(jù)集上的聚類結(jié)果，其中加粗字體表示較優(yōu)的實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)結(jié)果顯示，DPC 和FKNN-DPC 算法在屬性數(shù)較多的數(shù)據(jù)集Soybean 上和Statlog 上聚類效果較差，但在屬性較少的數(shù)據(jù)集Iris 上相對(duì)于SNN-DPC 和DBSCAN 算法取得了顯著的優(yōu)勢(shì)；SNN-DPC 算法在Iris 和Soybean（Small）數(shù)據(jù)集上的聚類指標(biāo)相對(duì)較差，但在Statlog（Heart）上取得了較好的聚類結(jié)果；-means++算法聚類效果正好與SNN-DPC 算法相反；DBSCAN 算法在3 個(gè)數(shù)據(jù)集上的聚類結(jié)果都不太理想；DCM-DPC 算法在Iris 數(shù)據(jù)集上的指標(biāo)低于FKNN-DPC 算法，但在其余兩個(gè)UCI 數(shù)據(jù)集上的聚類指標(biāo)均優(yōu)于全部對(duì)比算法，尤其在屬性數(shù)量較多的數(shù)據(jù)集Soybean（Small）上和Statlog（Heart）上，算法根據(jù)近鄰樣本所屬類簇的眾數(shù)分配樣本的策略有效利用了多個(gè)屬性提供的維度信息來判斷近鄰樣本間的相似性，使得DCMDPC 算法的聚類指標(biāo)相對(duì)對(duì)比算法更具有明顯的優(yōu)勢(shì)。

表3 6 種算法在UCI數(shù)據(jù)集上的聚類性能Table 3 Clustering performance of 6 algorithms on UCI datasets

表4 展示了6 種算法在人工數(shù)據(jù)集上的聚類結(jié)果，其中加粗字體表示較優(yōu)的實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)結(jié)果顯示，DCM-DPC 算法在參與測(cè)試的各個(gè)數(shù)據(jù)集上的聚類指標(biāo)都較優(yōu)秀，且比較平穩(wěn)。在Aggregation、Jain、Spiral 和R15 人工數(shù)據(jù)集上，DCM-DPC 算法的聚類指標(biāo)優(yōu)于或持平對(duì)比算法，并在Jain 和Spiral 數(shù)據(jù)集上實(shí)現(xiàn)了零差錯(cuò)；在D31 和Flame 數(shù)據(jù)集中指標(biāo)分別略低于FKNN-DPC 算法、SNN-DPC 算法和DPC算法。

表4 6 種算法在人工數(shù)據(jù)集上的聚類性能Table 4 Clustering performance of 6 algorithms on artificial datasets

圖5～圖10 展示了6 種算法在人工數(shù)據(jù)集上的聚類效果，其中-means++算法選取實(shí)驗(yàn)聚類指標(biāo)最優(yōu)結(jié)果。不同類簇的樣本以及離散點(diǎn)分別用不同的顏色表示。在同一組聚類效果對(duì)比圖中，代表不同聚類算法的圖片之間相同的顏色表示對(duì)應(yīng)于同一個(gè)類簇。

圖5 顯示了6 種算法對(duì)Aggregation 數(shù)據(jù)集的聚類結(jié)果。除了-means++算法，其余5 種算法都在Aggregation 數(shù)據(jù)集上取得了較好的聚類效果。但DBSCAN 算法將左上角類簇右邊緣部分樣本和右側(cè)兩個(gè)類簇的鄰接處樣本誤判成了離散點(diǎn)。在數(shù)據(jù)集左右兩側(cè)類簇的2 處邊緣樣本糾纏處，SNN-DPC 算法錯(cuò)誤分配了17 個(gè)樣本，DPC 和FKNN-DPC 算法分別錯(cuò)誤分配了2 個(gè)樣本；DCM-DPC 算法僅有1 個(gè)樣本分配錯(cuò)誤，聚類效果最好，對(duì)邊緣樣本的分配也是最準(zhǔn)確的。

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

圖6 顯示了6 種算法對(duì)D31 數(shù)據(jù)集的聚類結(jié)果。D31 數(shù)據(jù)集特點(diǎn)是規(guī)模較大，大部分樣本聚合比較緊密，多處邊緣樣本存在糾纏，也有少數(shù)較為離散的樣本。6 種算法聚類指標(biāo)相差不大，DBSCAN 算法將大量類簇邊緣樣本誤判成了離散點(diǎn)，指標(biāo)最低；DCMDPC 算法對(duì)相互糾纏的邊緣樣本判斷較準(zhǔn)確，但在聚類過程中將右側(cè)距離類簇較遠(yuǎn)的3 個(gè)樣本誤判成了離散點(diǎn)，使聚類指標(biāo)略低于FKNN-DPC 和SNNDPC 算法。此外，D31 數(shù)據(jù)集中部分類簇存在少量樣本深入到其他類簇的樣本中，被其他類簇的樣本包圍，6 種聚類算法在此都進(jìn)行了不同程度的誤判，導(dǎo)致聚類效果有所下降。

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

圖7 的Flame 數(shù)據(jù)集特點(diǎn)是一個(gè)類簇半包圍著另一個(gè)類簇。除了-means++算法因其球形聚類特征使得聚類效果最差外，其余5 種算法在數(shù)據(jù)集上都取得了良好的聚類效果，其中DPC 算法聚類效果最優(yōu)。DCM-DPC 算法在兩個(gè)類簇交界處的樣本劃分非常準(zhǔn)確，而FKNN-DPC、SNN-DPC 和DBSCAN 算法則在分配邊界樣本時(shí)都出現(xiàn)了錯(cuò)誤。但DCMDPC 算法將左上側(cè)2 個(gè)遠(yuǎn)離類簇的樣本誤判成了離散值，導(dǎo)致聚類指標(biāo)略低于DPC 算法。

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

圖8 的數(shù)據(jù)集Jain 是兩個(gè)月牙狀的類簇相互咬合。DPC、FKNN-DPC、SNN-DPC 和-means++算法在類簇咬合處都出現(xiàn)了大量樣本分配錯(cuò)誤，因此聚類指標(biāo)較差。DBSCAN 算法則在聚類中心個(gè)數(shù)的確定上出現(xiàn)失誤，將數(shù)據(jù)劃分成了3 類。DCM-DPC 算法對(duì)咬合處樣本的分配依舊非常準(zhǔn)確，并實(shí)現(xiàn)了聚類結(jié)果零差錯(cuò)。

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

圖9 展示了6 種算法對(duì)Spiral 數(shù)據(jù)集的聚類結(jié)果。該數(shù)據(jù)集由三組相距明顯的漩渦狀類簇組成，類簇內(nèi)部樣本相鄰緊密，類簇間樣本相距較遠(yuǎn)，邊界清晰，非常適合于密度聚類。除-means++算法外，其余5 種算法都準(zhǔn)確無誤地完成了聚類。

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

圖10 展示了6 種算法對(duì)R15 數(shù)據(jù)集的聚類結(jié)果。該數(shù)據(jù)集由15 個(gè)類簇組成，外圈類簇間隔明顯，內(nèi)圈類簇則相互糾纏。DCM-DPC、DPC、FKNNDPC 和SNN-DPC 算法聚類效果優(yōu)于DBSCAN 和means++算法，且對(duì)內(nèi)圈類簇邊緣糾纏的樣本歸屬判斷準(zhǔn)確度都較高。由于內(nèi)圈的類簇中存在樣本深入到其他類簇中，被其他類簇的樣本包圍，導(dǎo)致6 種算法均在此出現(xiàn)了誤判。

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

實(shí)驗(yàn)結(jié)果表明，DCM-DPC 算法在UCI 數(shù)據(jù)集Soybean（Small）和Statlog（Heart）的各項(xiàng)聚類指標(biāo)均優(yōu)于對(duì)比算法，在Iris 的聚類指標(biāo)僅低于FKNN-DPC算法，且在屬性較多的Soybean（Small）和Statlog（Heart）數(shù)據(jù)集上得益于多屬性帶來的豐富信息，聚類指標(biāo)更加突出。在人工數(shù)據(jù)集Aggregation、Jain、Spiral 和R15 上，DCM-DPC 算法的三個(gè)指標(biāo)均優(yōu)于或等于對(duì)比算法。但由于DCM-DPC 算法在離散樣本的判定上較為嚴(yán)格，可能會(huì)造成誤判，這也是算法在數(shù)據(jù)集D31 上指標(biāo)略低于FKNN-DPC 和SNNDPC 算法，在數(shù)據(jù)集Flame 上指標(biāo)略低于DPC 算法的主要原因。

綜合來看，DCM-DPC 算法在不同規(guī)模和屬性數(shù)的數(shù)據(jù)集上都有良好的表現(xiàn)，對(duì)數(shù)據(jù)的適應(yīng)廣泛，并具有良好的魯棒性。特別是對(duì)邊界相互糾纏或咬合的類簇，能精確地分配其邊界樣本，相對(duì)于對(duì)比算法具有明顯優(yōu)勢(shì)。

4 結(jié)束語

本文嘗試提出了一種去中心化加權(quán)簇歸并的密度峰值聚類算法DCM-DPC。DPC 算法依托聚類中心點(diǎn)聚類的方法容易影響聚類效果，且聚類中心點(diǎn)的選擇需要人為干預(yù)。對(duì)此本文提出了消除聚類中心點(diǎn)的核心樣本組聚類方法，通過由位于較高局部密度且互為近鄰的樣本組成的核心樣本組形成類簇雛形，并取代聚類中心點(diǎn)成為其余樣本劃分的依據(jù)。核心樣本組較聚類中心更加穩(wěn)定，能使聚類具有更好的魯棒性。新定義的局部密度更好地描述了數(shù)據(jù)的內(nèi)部結(jié)構(gòu)，使本文算法可以在不同規(guī)模、屬性數(shù)和類簇的數(shù)據(jù)集上得到良好的聚類結(jié)果；通過樣本的近鄰點(diǎn)所屬類簇的眾數(shù)來決定樣本歸屬，使樣本劃分時(shí)與類簇的關(guān)聯(lián)性更強(qiáng)，有效緩解了跟隨錯(cuò)誤的產(chǎn)生。在人工和UCI數(shù)據(jù)集上的實(shí)驗(yàn)顯示，本文算法在同類算法中具有較好的表現(xiàn)，且較對(duì)比算法能更加精確地分配相互糾纏或咬合的類簇的邊界樣本。由于本文算法在離散值的判定上比較嚴(yán)格，可能對(duì)游離的樣本產(chǎn)生誤判，提高對(duì)離散點(diǎn)的識(shí)別將是下一步的研究方向。