柏鍔湘，羅 可，羅 瀟

1.長沙理工大學計算機與通信工程學院，長沙410114

2.國網(wǎng)上海電力公司，上海200000

隨著網(wǎng)絡技術的興起，人們將在生產(chǎn)和生活中產(chǎn)生大量數(shù)據(jù)，其中包含許多有用的知識。但是，由于數(shù)據(jù)中包含的知識都是不完整、含噪聲以及隨機的，因此提取出隱藏在內(nèi)的有用知識，成為了一個亟待解決的問題，數(shù)據(jù)挖掘[1]因此應運而生。聚類分析在數(shù)據(jù)挖掘中起著非常重要的作用。聚類（clustering）是指將抽象的、物理的對象集合成幾個不同的類[2]。

聚類作為數(shù)據(jù)挖掘和機械學習領域重要的研究課題，研究人員提出了大量的聚類算法。Rodriguez等人于2014 年在Science上提出了一種新的基于密度的聚類算法——快速搜索和尋找密度峰值聚類算法（clustering by fast search and find of density peaks，DPC）[3]，DPC 算法與傳統(tǒng)的聚類算法相比較有很多優(yōu)點：第一，它原理簡單且具有較高的效率；第二，它只需要較少的參數(shù)和無需迭代就能實現(xiàn)數(shù)據(jù)集的處理。但是，DPC 算法仍然具有需要人為憑借經(jīng)驗確定截斷距離和無法有效地處理流形的數(shù)據(jù)集等問題。

自從DPC 聚類算法在Science刊登后，吸引了許多研究者的關注。從此，一些研究人員從不同視角、不同應用領域發(fā)表了多篇基于DPC 的論文。例如，為了減少計算量，Bai 等[4]提出了一種基于K-means算法的快速密度聚類算法，解決了DPC 算法不能自動識別聚類中心的問題。王巖等[5]提出了一種基于分布式計算的密度聚類方法，降低了時間復雜度。Liu等人[6]提出了SNN-DPC（shared nearest neighbor based clustering by fast search and find of density peaks），該算法加入了共享最近鄰的思想，可以使其在具有多種尺度，交叉纏繞，各種密度或高維度的數(shù)據(jù)集上的聚類效果更好。Du 等人[7]提出了DPC-KNN-PCA 算法，主要思想是引入了K個最近鄰居（K-nearest neighbor，KNN）來計算一個點的局部密度，并使用主成分分析（principal component analysis，PCA）來減少數(shù)據(jù)集的維數(shù)，這使得聚類算法獲得更好的結(jié)果。Xie 等人[8]提出了模糊加權(quán)K-近鄰密度峰聚類（FKNN-DPC），F(xiàn)KNN-DPC 算法是一種基于K近鄰的新局部密度度量，為對象分配應用了兩種新策略，其中引入了模糊方法，聚類效果比DPC 更好。Xu 等人[9]提出了一種基于預篩選的快速密度峰聚類算法，在保證聚類精度的基礎上，可以有效降低計算復雜度。Seyedi等人[10]提出一種新的動態(tài)密度峰聚類算法，該算法使用基于圖的標簽傳播來將標簽分配給剩余點并形成最終聚類，有效地將真實標簽分配給位于重疊區(qū)域中的邊界點。Huang 等人[11]提出一種新型分層聚類算法。由于聚類中心密度在其K個最近鄰居或反向最近鄰居中是最高的，因此算法首先根據(jù)K近鄰確認聚類中心點。其次，定義了簇之間相似性的新概念，以解決復雜流形數(shù)據(jù)集問題。算法在非球形數(shù)據(jù)和復雜流形數(shù)據(jù)方面有顯著提升。Wu 等人[12]提出基于具有對稱鄰域關系的密度峰值的高效聚類方法，首先在所有數(shù)據(jù)點上建立對稱鄰域圖，基于每個點的K近鄰和反向K近鄰。為了從所有數(shù)據(jù)點中區(qū)分出密度峰值，使用反向K最近鄰計算每個點的局部密度。之后，在峰上估計聚類的初始中心，并在對稱鄰域圖上聚合相似的聚類，最后將每個點成功分配給聚類。杜沛等人[13]提出一種基于K近鄰的比較密度峰值聚類算法，算法結(jié)合了K近鄰思想重新定義截斷距離和局部密度計算方式，使聚類結(jié)果更加符合數(shù)據(jù)的真實性。錢雪忠等人[14]提出自適應聚合策略優(yōu)化的密度峰值聚類算法，算法根據(jù)K近鄰的思想來確定數(shù)據(jù)點的局部密度，然后提出一種新的自適應聚合策略提升了算法的準確性，降低算法受人為的影響。

通過分析，上述算法未能自動地確定截斷距離，仍需要人為憑借經(jīng)驗預先確定截斷距離參數(shù)或K值。王軍華等人[15]提出自適應快速搜索密度峰值聚類算法，算法構(gòu)造關于截斷距離參數(shù)的局部密度信息熵，通過最小化信息熵自適應地確定截斷距離參數(shù)。本文提出一種基于自然和共享最近鄰的密度峰值聚類算法（natural nearest neighbor and shared nearest neighbor based density peaks clustering algorithm，NSDPC）。NSDPC 算法結(jié)合自然和共享最近鄰算法思想計算樣本局部密度和截斷距離。根據(jù)自然最近鄰計算每個數(shù)據(jù)點局部密度，選出每個數(shù)據(jù)點對應的候選聚類中心，以共享最近鄰思想重新定義候選聚類中心點之間的距離。從而，以候選聚類中心集作為樣本集進行密度峰值聚類，最后將剩余未分配的數(shù)據(jù)點分配給對應的候選聚類中心類簇中，直到完成聚類過程。實驗結(jié)果表明，NSDPC 算法不需要人為確定截斷距離且在流形數(shù)據(jù)集上的聚類效果有顯著的提高。

1 DPC 算法基本原理

DPC 作為一種基于密度的聚類算法，其主要聚類思想是：聚類中心的密度要比周圍鄰居的密度高，且聚類中心點之間的距離較遠[3]。因此，DPC 算法通過畫出局部密度ρi和數(shù)據(jù)點之間的相對距離δi的決策圖，直觀地選出聚類中心點，然后根據(jù)局部密度對其余的數(shù)據(jù)點進行分類[16]。

因此，數(shù)據(jù)集中的每個數(shù)據(jù)點都需要計算兩部分：第一部分，每個數(shù)據(jù)點的局部密度ρi；第二部分，數(shù)據(jù)點的相對距離δi。

假設數(shù)據(jù)集A={xi|i=1,2,…,n}，n代表著數(shù)據(jù)集A的大小。

數(shù)據(jù)集中xi和xj的相對距離δi為：

其中，dij表示數(shù)據(jù)點xi和xj的歐氏距離。相對距離δi指的是數(shù)據(jù)點xi與密度高于它且距離xi最近的數(shù)據(jù)點之間的距離。

數(shù)據(jù)集的局部密度ρi的計算方式有兩種，即截斷核和高斯核。通過計算點xi的點的個數(shù)來定義。

截斷核計算方式如式（3）所示：

其中，當x＜0 時，χ(x)=1；當x≥0 時，χ(x)=0。dc＞0且i≠j，dc表示的是截斷距離。

高斯核計算方式如式（4）所示：

其中，截斷核的定義是指在截止距離范圍內(nèi)的所有數(shù)據(jù)點的個數(shù)之和。高斯核的定義則是指所有數(shù)據(jù)點到該數(shù)據(jù)點的高斯距離之和。

當局部密度ρi和相對距離δi都比較高時，則對應的數(shù)據(jù)點xi為密度峰值（聚類中心點）。通過繪制決策圖來尋找聚類中心點，決策值γi如式（5）所示。

根據(jù)局部密度ρi和數(shù)據(jù)點的相對距離δi繪制出決策圖。在決策圖上，中心點與非中心點明顯分開，可以通過選擇具有較高局部密度ρi和較大距離δi的點，即γi較高的數(shù)據(jù)點，來作為聚類中心點。將所有的數(shù)據(jù)點（除聚類中心點外）分配到距離最近的聚類中心點的類簇中。

傳統(tǒng)的DPC 算法有明顯的兩個不足：

（1）需要根據(jù)用戶的經(jīng)驗預先確定截止距離dc。如果數(shù)據(jù)集中含有真實聚類標簽時，用戶可以通過對比真實聚類標簽不斷調(diào)整截止距離dc。但是，在實際應用的問題上，并沒有真實聚類標簽。

（2）無法有效地處理流形數(shù)據(jù)集。因為DPC 算法采用的是歐式距離，而歐式距離并不適合用來評估流形數(shù)據(jù)集上的對象之間的差異。

2 算法改進

2.1 自然最近鄰

對于許多的密度聚類算法，大部分算法第一個基本聚類步驟就是找到其鄰居（數(shù)據(jù)）。最常見的是K近鄰和ε近鄰，但是它們都很容易受到參數(shù)選擇的影響。

其中，K近鄰的主要思想是為每個對象找到K個最近或最相似的鄰居（數(shù)據(jù)點）。一個對象與其第K個鄰居（數(shù)據(jù)點）之間的距離越小，則表明該物體的密度值越大。ε近鄰的主要思想是找到小于半徑ε范圍內(nèi)的所有鄰居（數(shù)據(jù)點）總數(shù)。K和ε都是需要人為設置的參數(shù)。為了解決需要人為設置參數(shù)的問題，Zhu 等人[17]在2016 年提出了自然最近鄰。

定義1（自然最近鄰）對于數(shù)據(jù)點xi，在自然最近鄰算法中所有的離群點都被找到時，稱數(shù)據(jù)點xi的supk個鄰居為數(shù)據(jù)點xi的自然最近鄰。supk指的是數(shù)據(jù)點xi的自然特征值。自然特征值對應K近鄰的參數(shù)K，但是自然特征值會根據(jù)不同的數(shù)據(jù)集自適應地選擇。因此，自然最近鄰的計算過程是無需參數(shù)設置的。

在本文中，數(shù)據(jù)集的最高密度如表1 所示。自然鄰居中含有密度最高點的數(shù)據(jù)集是Aggregation 數(shù)據(jù)集。Aggregation 是一個2 維、7 類的數(shù)據(jù)集。其主要由7 塊明顯不同的數(shù)據(jù)組合而成。由于該數(shù)據(jù)集的數(shù)據(jù)點基本是分塊集合在一起，因此每一塊數(shù)據(jù)集的密度不同，從而使用密度峰值聚類可以得到更好的聚類結(jié)果。

Table 1 Peak density of the highest point in data set表1 數(shù)據(jù)集的最高點密度峰值

2.2 共享最近鄰

DPC 算法，通過計算決策值，繪制出決策圖，從而選擇出初始聚類中心點。DPC 算法面對復雜的數(shù)據(jù)集時無法選擇正確的聚類中心點，容易導致錯誤的分類結(jié)果。由于DPC 算法是采用歐式距離直接計算點之間的距離和密度，而不關注點所在的環(huán)境，因此提出一種新的密度峰之間的距離計算方法，即共享最近鄰距離[6]。其主要定義分為兩部分。

定義2（共享最近鄰）局部密度峰點xi的自然最近鄰為T(i),局部密度峰點xj的自然最近鄰為T(j)。則兩個密度峰之間的共享最近鄰數(shù)為它們的交集，如式（6）所示：

定義3（共享最近鄰之間的距離）對于局部密度峰點xi和局部密度峰點xj之間的改進的共享最近鄰距離計算方法如式（7）所示。其中d(i,j)指的是局部密度峰點xi和局部密度峰點xj之間的距離；Max指的是所有局部密度峰之間的兩個相離最遠的距離。

由于在許多的數(shù)據(jù)集上，數(shù)據(jù)點的分布并不是均勻分布的，因此通過密度峰值聚類產(chǎn)生的局部密度峰也不是均勻分布的。從而通過基于共享最近鄰的距離計算方法，在局部密度峰密集的區(qū)域縮短其局部密度峰之間的距離，在局部密度峰稀疏的區(qū)域放大其局部密度峰之間的距離，如表2、表3 所示。表2 表示的是Spiral 數(shù)據(jù)集中通過歐式距離計算局部密度峰之間的距離，表3 表示的是Spiral 數(shù)據(jù)集中通過改進共享最近鄰算法處理后的局部密度峰之間的距離。其中，1、2 為同一類，3、4 為同一類。可以得出改進的共享最近鄰算法優(yōu)化了DPC 算法局部密度峰之間的距離，提升了算法的聚類效果。

Table 2 Euclidean distance to calculate distance between local density peaks表2 歐式距離計算局部密度峰之間距離

Table 3 Shared nearest neighbor to calculate distance between local density peaks表3 共享最近鄰計算局部密度峰之間距離

2.3 NSDPC 算法

定義4（歸一化局部密度）基于自然最近鄰定義的局部密度計算公式，數(shù)據(jù)點xi基于自然最近鄰的密度為ρi，歸一化局部密度為Nρi。ρi和Nρi的計算方法如式（8）和式（9）所示。

其中，supk表示由自然最近鄰算法得到的自然特征值；dij表示數(shù)據(jù)點xi和數(shù)據(jù)點xj的歐幾里德距離；NNi表示數(shù)據(jù)點xi的自然最近鄰集合；meanρi表示數(shù)據(jù)點xi的自然最近鄰的密度的平均值；stdρi表示數(shù)據(jù)點xi的自然最近鄰的密度的標準差。

DPC 算法易受人為主觀影響，即不正確的截斷距離會導致錯誤的初始聚類中心，從而導致聚類結(jié)果的準確性較差[18]。本文參考文獻[18]中局部密度計算方式，結(jié)合自然最近鄰計算局部密度，由于自然最近鄰的整個計算過程可以自動完成，無需任何參數(shù)，從而解決了DPC 算法需要人為確定截斷參數(shù)的影響，提高了算法的性能。

定義5（候選聚類中心）計算所有數(shù)據(jù)點的局部密度，并將所有數(shù)據(jù)點按局部密度從大到小排序，在數(shù)據(jù)點xi的自然最近鄰中，選取局部密度最大并且密度大于0 的數(shù)據(jù)點xj加入候選聚類中心集并對數(shù)據(jù)點xi和它對應的局部密度最大的點xj進行標記，然后找剩下未被標記的數(shù)據(jù)點中局部密度最大并且密度大于0 的數(shù)據(jù)點進行同樣操作，直到所有的點都被標記，就得到了候選聚類中心集。

圖1 表示的是NSDPC 與DPC 算法在ThreeCircles和Jain上的聚類效果圖，其中（a）、（c）表示的是NSDPC算法分別在ThreeCircles 和Jain 數(shù)據(jù)集上候選聚類中心集的聚類效果圖，（b）、（d）表示的是DPC 算法分別在ThreeCircles 和Jain 數(shù)據(jù)集上的聚類效果圖。其中NSDPC 算法使用候選聚類中心的計算方式而形成聚類結(jié)果圖。NSDPC 算法候選聚類中心集聚類效果與DPC 算法和圖2 中數(shù)據(jù)集原始圖形相比，并未對全局和局部特征產(chǎn)生影響。

定義6（最短路徑距離）為了提高算法在流形數(shù)據(jù)上的聚類效果，使用Dijkstra 算法求得候選聚類中心之間的最短路徑[19]。候選中心數(shù)據(jù)之間的最短路徑P=(p1,p2,…,pm)，1 ≤m＜n。候選聚類中心點xi和點xj的距離D(i,j)和相對距離δi如式（10）、式（11）所示。SD(pm-1,pm)指的是候選聚類中心點xi和點xj的最短路徑距離。

Fig.1 Clustering results of candidate cluster center圖1 候選聚類中心集聚類結(jié)果圖

Fig.2 Rendering of synthetic data set圖2 合成數(shù)據(jù)集的效果圖

NS-DPC 算法的流程步驟如下：

步驟1通過自然最近鄰算法將找出待聚類的數(shù)據(jù)點的自然鄰居。

步驟2通過式（8）、式（9）計算每個數(shù)據(jù)點的局部密度。

步驟3將所有的數(shù)據(jù)點，按照密度從大到小的順序排序，標記出候選中心點，獲得候選中心數(shù)據(jù)集。

步驟4將候選中心數(shù)據(jù)集作為一個新的數(shù)據(jù)集，以共享最近鄰算法式（6）、式（7）重新定義密度峰之間的距離。

步驟5通過Dijkstra 算法計算候選中心集的最短路徑，通過式（10）、式（11），計算候選聚類中心數(shù)據(jù)集的相對距離δi。

步驟6將相對距離δi、候選聚類中心數(shù)據(jù)集和候選聚類中心局部密度輸入到原始的DPC 算法中進行聚類。

步驟7按照候選聚類中心數(shù)據(jù)集的聚類結(jié)果，分配每個數(shù)據(jù)點的聚類標簽。

3 實驗結(jié)果及分析

3.1 實驗環(huán)境與實驗數(shù)據(jù)集

實驗環(huán)境：操作系統(tǒng)Windows10，編譯軟件Matlab R2017a；Intel Corei7 CPU 7700HM@2.8 GHz，8 GB的內(nèi)存。

實驗所用的數(shù)據(jù)集：本實驗主要采用的數(shù)據(jù)集是合成數(shù)據(jù)集和UCI部分數(shù)據(jù)集，數(shù)據(jù)集如表4和表5所示，原始數(shù)據(jù)集圖形如圖2 所示。

Table 4 Synthetic data set used in experiment表4 實驗所用合成數(shù)據(jù)集

Table 5 UCI data set used in experiment表5 實驗所用UCI數(shù)據(jù)集

3.2 評價指標

本文實驗所采用的評價指標分別是調(diào)整信息（adjusted mutual information，AMI）[25]、調(diào)整蘭德系數(shù)（adjusted Rand index，ARI）[25]和FMI 指數(shù)（Fowlkes Mallows index，F(xiàn)MI）[26]。以上三個指標的上限均是1，即越接近1 聚類效果越好。

假設U和V分別是同一種數(shù)據(jù)的兩種標簽（U表示真實標簽，V表示聚類結(jié)果）。

AMI的定義為：

ARI的定義為：

FMI的定義為：

在上述式子中，a表示在U中為同一簇且在V中也為同一簇的數(shù)據(jù)點個數(shù)，b表示在U中為同一類但在V中不為同一簇的數(shù)據(jù)點個數(shù)，c表示在U中不為同一簇但在V中為同一簇的數(shù)據(jù)點個數(shù)，d表示在U中不為同一簇且在V中也不為同一簇的數(shù)據(jù)點個數(shù)。

3.3 數(shù)據(jù)預處理

本文實驗所用的數(shù)據(jù)集如表4 和表5 所示，分別是合成數(shù)據(jù)集和UCI 真實數(shù)據(jù)集。以上兩種數(shù)據(jù)集均廣泛地應用于測試聚類算法的有效性。并且所選的數(shù)據(jù)集在樣本個數(shù)、屬性個數(shù)和類別上均有明顯的差異。

在進行實驗之前，需要對數(shù)據(jù)集進行預處理，以消除數(shù)據(jù)的缺失值和不同維數(shù)的差異對實驗結(jié)果的影響。將相同維度的所有有效數(shù)據(jù)的平均值代替缺失值。采用式（15）所示的最大最小歸一化方法，消除不同維度對聚類結(jié)果產(chǎn)生的影響。

3.4 實驗結(jié)果與分析

本文的實驗主要將NSDPC算法與DPC[3]、DBSCAN（density-based algorithm for discovering clusters in large spatial databases with noise）[27]和K-means[28]算法進行比較。其中，NSDPC 算法需要提供的參數(shù)為類別數(shù)目NC。DPC 算法的截斷距離dc參照文獻[3]，統(tǒng)一設置為2%。DBSCAN 算法需要設定兩個參數(shù)：半徑ε和最小樣本數(shù)MinPts。為了取得最佳結(jié)果，選擇不同的半徑ε和最小樣本數(shù)MinPts 來進行實驗。K-means 算法需要給定類的個數(shù)，并且每次K-means算法選取的初始聚類中心的不同導致聚類結(jié)果也不同。因此，對數(shù)據(jù)集進行30 次重復實驗，取實驗結(jié)果的均值。表6 顯示了4 種算法在合成數(shù)據(jù)集上的較優(yōu)參數(shù)的設置。

Table 6 Parameter settings on synthetic data sets表6 合成數(shù)據(jù)集上的參數(shù)設置

表7 是DPC、DBSCAN、K-means 和本文算法在UCI 數(shù)據(jù)集上的參數(shù)設置。表8 是4 種算法在UCI 數(shù)據(jù)集上的聚類結(jié)果，表中加粗的字體表示較優(yōu)的聚類性能。

Table 7 UCI data set parameter setting表7 UCI數(shù)據(jù)集參數(shù)設置

表8 實驗結(jié)果顯示，在Iris 數(shù)據(jù)集上，本文算法聚類效果比其他3 個算法好。在Segment 數(shù)據(jù)集上，本文算法的AMI 要優(yōu)于其他3 個算法，ARI 與FMI 略低于DPC 算法。在Landsat 數(shù)據(jù)集上，本文算法的聚類效果要優(yōu)于其余算法。在處理Pendigits數(shù)據(jù)集時，本文算法除了AMI 略低于DPC 算法，ARI 與FMI 均要優(yōu)于其余算法。

Table 8 Clustering performance of 4 algorithms on UCI data set表8 4 種算法在UCI數(shù)據(jù)集上的聚類性能

表9 顯示了4 種算法在合成數(shù)據(jù)集上的聚類性能（AMI、ARI、FMI），表中加粗的值表示較好的實驗結(jié)果。圖3 和圖4 展示的是DPC、DBSCAN、K-means和本文算法對Jain 和ThreeCircles 數(shù)據(jù)集的聚類結(jié)果圖。Jain 數(shù)據(jù)集是一個由兩部分月牙類簇組成的二維數(shù)據(jù)集，由圖3 可以明顯地看出，K-means 與DPC原始算法無法取得較好的聚類結(jié)果，DBSCAN 算法錯誤地將原始數(shù)據(jù)集分成了3 類。由于K-means 算法比較擅長處理球形數(shù)據(jù)集，而Jain 數(shù)據(jù)集是由兩個月牙組成，因此未能正確聚類。DPC 算法未能正確確認局部密度峰值，導致數(shù)據(jù)點的錯誤分配。由表9可知，本文算法在數(shù)據(jù)集Jain 上取得了準確的聚類，DBSCAN 取得較好的聚類結(jié)果，其余兩個算法均未能達到較好的聚類效果。

ThreeCircles 數(shù)據(jù)集是由3 個環(huán)形類簇組合成的三維數(shù)據(jù)集。從圖4 可以看出，NSDPC 算法與DBSCAN 算法均能取得正確的聚類結(jié)果，DPC 與Kmeans 算法未能取得比較好的聚類效果。由于DPC算法計算相對距離和局部密度采用的是歐式距離計算方式，導致DPC 算法無法正確地區(qū)分密集區(qū)域與稀疏區(qū)域。由于ThreeCircles 數(shù)據(jù)集并不是球形數(shù)據(jù)集，因此K-means 算法并未能取得好的聚類效果。由表9 也能看出，NSDPC 與DBSCAN 算法取得了準確的聚類結(jié)果，而DPC 與K-means 的聚類效果并不好。

Table 9 Clustering performance of 4 algorithms on synthetic data set表9 4 種算法在合成數(shù)據(jù)集上的聚類性能

Fig.3 Clustering effect diagram of 4 algorithms on synthetic data set Jain圖3 4 種算法在合成數(shù)據(jù)集Jain 的聚類效果圖

Fig.4 Clustering effect of 4 algorithms on synthetic data set ThreeCircles圖4 4 種算法在合成數(shù)據(jù)集ThreeCircles的聚類效果圖

4 結(jié)束語

本文提出了一種基于自然最近鄰和共享最近鄰的密度峰值聚類算法，簡稱NSDPC。首先，采用自然最近鄰算法來定義局部密度和截斷距離，提出了一種新的共享鄰居距離計算公式，并且采取了候選聚類中心計算思想，減少了原始數(shù)據(jù)的大小，較好地維護了原始數(shù)據(jù)的局部以及全局特征。在合成數(shù)據(jù)集上和在UCI數(shù)據(jù)集上，本文算法聚類效果總體上要較優(yōu)于其他3 個算法。NSDPC 算法有效地解決了DPC算法需要人為確認截止距離參數(shù)和無法處理流形數(shù)據(jù)集的問題。但是，本文算法在處理高維度含有噪聲的真實數(shù)據(jù)集上，聚類效果并不能達到無噪聲低維度數(shù)據(jù)集上的聚類效果。高效地處理高維度且含有噪聲的數(shù)據(jù)集將是下一步的研究方向。