去中心化加權簇歸并的密度峰值聚類算法

趙力衡，王 建，陳虹君

1.成都錦城學院 電子信息學院，成都611731

2.四川大學 計算機學院，成都610041

聚類算法是模式識別和數據挖掘領域中的一類常見的無監督算法。算法通過某種相似性計算將一組數據對象按照其自身的特征劃分到不同的類簇中，并使同一簇內的對象盡可能相似，不同簇之間的對象盡可能不相似。現有聚類算法模型豐富，大致可以分為層次聚類、劃分聚類、密度聚類、網格聚類、圖論聚類、代表點聚類和模型聚類七種類型，被廣泛應用于生物、能源、交通、圖像處理、流形數據處理等領域。

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

為解決這些問題，近年來眾多學者對DPC算法進行了改進。Xie 等人提出了模糊加權K 最近鄰分配點的密度峰值聚類算法（robust clustering by detecting density peaks and assigning points based on fuzzy weighted K-nearest neighbors，FKNN-DPC）。該算法基于K 近鄰設計了一種獨立于數據集規模且與截斷距離無關的局部密度計算方式，將數據集劃分成核心樣本和離群樣本，再采用新的K 近鄰策略完成對非聚類中心點的分配，有效緩解了DPC 算法的跟隨錯誤。Seyed等人提出了基于動態圖的密度峰值聚類標簽傳播算法（dynamic graph-based label propagation for density peaks clustering，DPC-DLP）。算法根據重新定義的K近鄰密度確定出聚類中心點，然后將類簇中心點和其相鄰中心點形成一個KNN 圖，最后采用圖的標簽傳播方法分配剩余樣本，更適用于圖像聚類。丁世飛等人提出了一種基于不相似性度量優化的密度峰值聚類算法（optimized density peaks clustering algorithm based on dissimilarity measure，DDPC）。算法通過基于塊的不相似性度量實現樣本間的相似度計算，從而避免了小樣本數據集上截斷距離對聚類結果的影響，提高了在高維度數據集上的聚類效果。Liu 等人提出了基于共享近鄰的密度峰值聚類算法（sharednearest-neighbor-based clustering by fast search and find of density peaks，SNN-DPC）。算法通過計算樣本之間共享的近鄰點個數，確定樣本之間的相似度，避免了非聚類中心點分配時的跟隨錯誤。王大剛等人提出了基于二階近鄰的密度峰值聚類算法（density peaks clustering algorithm based on second-orderneighbors，SODPC）。算法通過引入樣本的二階近鄰計算直接密度和間接密度，避免了截斷距離帶來的影響。

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

1 DPC 算法

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

其中，d表示樣本x與樣本x之間的距離。為截斷距離，定義為中任意兩個樣本之間的距離按升序排列后位于用戶指定位置的值。對于函數()有：

當數據集規模較小時，DPC 采用高斯核函數描述局部密度：

相對距離δ表示樣本x距離局部密度比它高且離它最近的樣本的距離，當x不是最大密度樣本點時δ為：

當x是最大密度樣本點時δ為：

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

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

DPC 算法在多數時候能獲得不錯的聚類結果，但尚存在一些不足：

（1）圍繞聚類中心點進行聚類，即首先找出聚類中心點，然后非聚類中心點依據聚類中心點進行分配，從而完成聚類。截斷距離是影響聚類中心選取的重要因素，圖1（a）和圖1（b）分別是flame 數據集在截斷距離取5%和2%時的聚類結果，圖中十字符號為聚類中心。可以看出，當截斷距離不同時選取的距離中心不相同，聚類結果也出現顯著差異。聚類過程中，不同截斷距離除了影響聚類中心的選取外，還會引起局部密度等計算的變化，同樣會影響聚類結果。因此，為消除聚類中心因素外其他因素對聚類結果的影響，圖1（c）中將聚類效果優秀的截斷距離采用5%的聚類中心替換為截斷距離采用2%的聚類中心，替換后聚類結果中大部分樣本被識別為離散點，聚類效果極差。可見聚類中心的選擇可能顯著影響聚類效果。

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

（3）截斷距離由用戶主觀選擇，只體現了數據的分布密度，沒有體現數據的內部特征，因此截斷距離的改變容易使聚類結果變得不穩定。

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

2 DCM-DPC 算法

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

2.1 去中心化的加權核心樣本組策略

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

圖1 不同聚類中心點的聚類效果對比圖Fig.1 Clustering effect contrast diagram of different clustering centers

本文所知的DPC 改進算法文獻均依賴于聚類中心點進行聚類，并沒有在消除聚類中心方向進行優化。嘗試提出一種新的去中心化聚類的核心樣本組策略取代聚類中心點作為樣本劃分依據。核心樣本組指具有較高局部密度且位于同一較高密度區域樣本的集合，采用基于近鄰思想的加權鄰域半徑來度量局部密度。近鄰思想目標是找出加權鄰域半徑內的所有樣本數量。

DPC 算法使用截斷距離作為鄰域半徑，以截斷距離內的樣本數量作為局部密度。由于截斷距離是人為主觀選擇，難以準確反映數據的分布特征，為此本文給出了新的局部密度及相關定義：

（權重系數）設定權重系數如下：

（加權鄰域半徑）設定加權鄰域半徑如下：

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

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

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

式中，為式（8）中表示的加權鄰域半徑。

以加權鄰域半徑內的樣本數量作為局部密度，同時考慮到了數據的密度和內部結構的差異，能有效描述樣本的分布狀況，從而提升聚類效果。

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

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

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

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

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

圖2 數據分布示意圖Fig.2 Schematic diagram of data distribution

可以發現，位于聚類中心點鄰域半徑內的核心樣本和位于這些核心樣本鄰域半徑內的其他核心樣本同屬于該聚類中心所在的類簇。樣本4 是樣本1鄰域內的非核心樣本，近鄰點較少因此與其近鄰點相似度都不高，難以確定是否屬于同一類別。顯然，非核心樣本的近鄰樣本中屬于某個類簇的樣本越多，該非核心樣本就與該類簇越相似。因此本文算法以非核心樣本的近鄰點所屬類簇的眾數確定其歸屬。離散樣本5、6 因沒有可以歸屬于任意類簇的近鄰點，所以不屬于任何類簇。可見，當聚類中心確定時，屬于該類簇的核心樣本成員，即核心樣本組，亦就可以確定了，DPC 算法的聚類中心點就是核心樣本組中密度最高的點。核心樣本組的尋找可以從任意核心樣本開始，找出其近鄰核心點，進而擴散到整個數據集，從而實現無中心點的聚類。

圖3（a）展示了Aggregation 數據集的樣本分布圖，由7 個相鄰且不同形狀的類簇構成，分別以不同的顏色表示。圖3（b）是該數據集不同類簇的核心樣本和非核心樣本的分布圖，不同類簇的核心樣本顏色與圖3（a）中相同類簇的顏色相同，非核心樣本則以其他顏色表示。可以發現，每個類簇的核心樣本都集中在類簇中間密度較高的區域，非核心樣本則圍繞在核心樣本組的周圍局部密度較低的區域，且當類簇密度較高時，該類簇的核心樣本也較多，反之則偏少。可見，由核心樣本構成的核心樣本組在反映密度峰值的意義上與DPC 算法的聚類中心是一致的。DPC 算法依據聚類中心聚類時，若樣本密度差異較大，同一類簇中可能找到多個密度峰值，使聚類結果不理想，而核心樣本組則會將這些密度峰值劃分到同一核心樣本組中，從而避免該現象。因此核心樣本組不但能夠成為聚類的依據，而且聚類效果優于DPC 算法使用的聚類中心。

圖3 Aggregation 數據分布圖Fig.3 Distribution map of Aggregation dataset

2.2 簇歸并策略

在給定數據集中，互為近鄰的核心樣本構成代表一個簇的核心樣本組。識別核心樣本的步驟中，只有核心樣本會記錄到代表類簇的核心樣本組中，此時核心樣本組等價于類簇。由于樣本的順序通常是未經排序的，當順序遍歷數據集尋找核心樣本時，識別出的核心樣本通常也是無序的，因此聚類過程中由核心樣本組構成的類簇是變化的。由上節分析可知，互為近鄰的核心樣本屬于同一類簇，因此當聚類過程中發現不同的核心樣本組中存在相互近鄰的樣本時，表明這些樣本組中的元素應屬于同一類簇，需要將這些核心樣本組歸并成一個。

如圖4 所示，核心樣本按標號順序被識別出。核心樣本3 被識別時由于沒有位于樣本1 的鄰域半徑內，樣本1 與樣本3 此時應分別屬于不同的簇（核心樣本組）。當同時位于二者鄰域半徑內的樣本5 被識別出時，可以發現三個樣本是相似的，樣本1 和樣本3所在的簇是相似簇，需要以樣本5 為介質進行歸并。若不同核心樣本所在簇不相似，則不進行歸并，如樣本1、3、5 和樣本2、4 所在的簇。

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

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

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

當識別出所有核心樣本后，沒有歸并的簇就組成了全部核心樣本組。

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

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

其中，N(b)∈A表示樣本b屬于類簇A的近鄰點數量。當p=0 時，表示b為離散點。

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

特別是當數據集中出現類簇糾纏時，邊界樣本更容易出現距離其他類簇中有更高局部密度的樣本更近的現象，因此本文算法相對于DPC 算法能更準確地識別出邊界樣本的所屬類簇，使邊界樣本的分配更加精確可靠。

2.4 算法步驟

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

（數據歸一化）樣本x的屬性歸一化定義如下：

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

算法步驟如下：

輸入：數據集={,,…,x}；核心對象鄰域密度閾值m；鄰域半徑修正權值p。

根據式（13）對數據歸一化。

根據式（8）計算加權鄰域半徑。

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

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

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

每當識別出一個核心樣本時，檢查該樣本是否為核心樣本組的共享樣本，如果是則合并相似類簇。

完成核心樣本識別后，對非核心樣本按其近鄰點所屬類簇的眾數，降序歸入最相似的類簇中。

標識非核心樣本隊列中剩余沒有近鄰點的樣本為離散點。

輸出：聚類結果集。

2.5 算法復雜度分析

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

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

3 實驗結果與分析

3.1 實驗數據集與評估指標

為驗證DCM-DPC 算法的有效性，本文采用人工數據集與UCI 數據集進行測試和評估。為使測試數據多樣化，選取的數據集在樣本數量、屬性數和類簇數跨度較大，這些數據集皆廣泛地應用于聚類算法有效性的測試。數據集具體屬性如表1 和表2 所示。

表1 人工數據集Table 1 Artificial datasets

表2 UCI數據集Table 2 UCI datasets

在以上數據集上選擇DPC、FKNN-DPC、SNNDPC、DBSCAN和-means++算法與本文DCMDPC 算法進行比較。其中，DPC 和SNN-DPC 算法使用的是作者公開的源代碼，FKNN-DPC、DBSCAN 和-means++算法參照原文獻使用Python3.8 實現。本文依據參考文獻對各算法的參數均進行了調優，以保證各算法的聚類效果。-means++算法因初始聚類中心的選取具有隨機性會影響聚類結果，表3 和表4中采用100 次聚類結果的均值。

評估指標采用調整互信息（adjusted mutual information，AMI）、調整蘭德系數（adjusted Rand index，ARI）和FMI 指數（Fowlkes Mallows index，FMI）。其中，AMI和FMI取值范圍為[0,1]，ARI取值范圍為[-1,1]，三者均是越接近1，表明聚類效果越優。

3.2 實驗結果分析

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

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

表4 展示了6 種算法在人工數據集上的聚類結果，其中加粗字體表示較優的實驗結果。實驗結果顯示，DCM-DPC 算法在參與測試的各個數據集上的聚類指標都較優秀，且比較平穩。在Aggregation、Jain、Spiral 和R15 人工數據集上，DCM-DPC 算法的聚類指標優于或持平對比算法，并在Jain 和Spiral 數據集上實現了零差錯；在D31 和Flame 數據集中指標分別略低于FKNN-DPC 算法、SNN-DPC 算法和DPC算法。

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

圖5～圖10 展示了6 種算法在人工數據集上的聚類效果，其中-means++算法選取實驗聚類指標最優結果。不同類簇的樣本以及離散點分別用不同的顏色表示。在同一組聚類效果對比圖中，代表不同聚類算法的圖片之間相同的顏色表示對應于同一個類簇。

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

圖5 Aggregation 數據集聚類效果Fig.5 Clustering effect on Aggregation dataset

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

圖6 D31 數據集聚類效果Fig.6 Clustering effect on D31 dataset

圖7 的Flame 數據集特點是一個類簇半包圍著另一個類簇。除了-means++算法因其球形聚類特征使得聚類效果最差外，其余5 種算法在數據集上都取得了良好的聚類效果，其中DPC 算法聚類效果最優。DCM-DPC 算法在兩個類簇交界處的樣本劃分非常準確，而FKNN-DPC、SNN-DPC 和DBSCAN 算法則在分配邊界樣本時都出現了錯誤。但DCMDPC 算法將左上側2 個遠離類簇的樣本誤判成了離散值，導致聚類指標略低于DPC 算法。

圖7 Flame數據集聚類效果Fig.7 Clustering effect on Flame dataset

圖8 的數據集Jain 是兩個月牙狀的類簇相互咬合。DPC、FKNN-DPC、SNN-DPC 和-means++算法在類簇咬合處都出現了大量樣本分配錯誤，因此聚類指標較差。DBSCAN 算法則在聚類中心個數的確定上出現失誤，將數據劃分成了3 類。DCM-DPC 算法對咬合處樣本的分配依舊非常準確，并實現了聚類結果零差錯。

圖8 Jain 數據集聚類效果Fig.8 Clustering effect on Jain dataset

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

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

圖10 展示了6 種算法對R15 數據集的聚類結果。該數據集由15 個類簇組成，外圈類簇間隔明顯，內圈類簇則相互糾纏。DCM-DPC、DPC、FKNNDPC 和SNN-DPC 算法聚類效果優于DBSCAN 和means++算法，且對內圈類簇邊緣糾纏的樣本歸屬判斷準確度都較高。由于內圈的類簇中存在樣本深入到其他類簇中，被其他類簇的樣本包圍，導致6 種算法均在此出現了誤判。

圖10 R15 數據集聚類效果Fig.10 Clustering effect on R15 dataset

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

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

4 結束語

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