結合自然和共享最近鄰的密度峰值聚類算法

柏鍔湘，羅 可，羅 瀟

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

2.國網上海電力公司，上海200000

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

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

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

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

1 DPC 算法基本原理

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

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

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

數據集中xi和xj的相對距離δi為：

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

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

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

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

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

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

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

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

傳統的DPC 算法有明顯的兩個不足：

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

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

2 算法改進

2.1 自然最近鄰

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

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

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

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

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

2.2 共享最近鄰

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

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

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

由于在許多的數據集上，數據點的分布并不是均勻分布的，因此通過密度峰值聚類產生的局部密度峰也不是均勻分布的。從而通過基于共享最近鄰的距離計算方法，在局部密度峰密集的區域縮短其局部密度峰之間的距離，在局部密度峰稀疏的區域放大其局部密度峰之間的距離，如表2、表3 所示。表2 表示的是Spiral 數據集中通過歐式距離計算局部密度峰之間的距離，表3 表示的是Spiral 數據集中通過改進共享最近鄰算法處理后的局部密度峰之間的距離。其中，1、2 為同一類，3、4 為同一類?？梢缘贸龈倪M的共享最近鄰算法優化了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（歸一化局部密度）基于自然最近鄰定義的局部密度計算公式，數據點xi基于自然最近鄰的密度為ρi，歸一化局部密度為Nρi。ρi和Nρi的計算方法如式（8）和式（9）所示。

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

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

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

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

定義6（最短路徑距離）為了提高算法在流形數據上的聚類效果，使用Dijkstra 算法求得候選聚類中心之間的最短路徑[19]。候選中心數據之間的最短路徑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 候選聚類中心集聚類結果圖

Fig.2 Rendering of synthetic data set圖2 合成數據集的效果圖

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

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

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

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

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

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

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

步驟7按照候選聚類中心數據集的聚類結果，分配每個數據點的聚類標簽。

3 實驗結果及分析

3.1 實驗環境與實驗數據集

實驗環境：操作系統Windows10，編譯軟件Matlab R2017a；Intel Corei7 CPU 7700HM@2.8 GHz，8 GB的內存。

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

Table 4 Synthetic data set used in experiment表4 實驗所用合成數據集

Table 5 UCI data set used in experiment表5 實驗所用UCI數據集

3.2 評價指標

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

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

AMI的定義為：

ARI的定義為：

FMI的定義為：

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

3.3 數據預處理

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

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

3.4 實驗結果與分析

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

Table 6 Parameter settings on synthetic data sets表6 合成數據集上的參數設置

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

Table 7 UCI data set parameter setting表7 UCI數據集參數設置

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

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

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

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

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

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

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

4 結束語

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