自然反向最近鄰優化的密度峰值聚類算法

劉 娟，萬 靜

哈爾濱理工大學 計算機科學與技術學院，哈爾濱 150080

聚類分析作為一種重要的數據挖掘技術，在數據挖掘中起到了十分重要的作用，聚類分析技術被廣泛應用于其他研究領域，例如：機器學習、人工智能、圖像處理、云計算[1]等。聚類是一個按照數據對象間的相似性將數據集劃分為各個不同的簇的過程，要求屬于同一個簇的數據對象盡可能類似，同時屬于不同簇的數據對象盡可能不同。到目前為止，已經提出了很多不同的聚類算法，主要包括基于劃分的聚類算法、基于層次的聚類算法、基于密度的聚類算法、基于網格的聚類算法、基于模糊的聚類算法。

基于劃分的聚類算法利用迭代控制策略優化一個目標函數，通過迭代重定位的方法，不斷改變聚類中心和簇中的數據對象，進而改進每次的劃分結果。K-means 算法[2]是經典的基于劃分的聚類算法，由于K-means 算法隨機選擇聚類中心，初始聚類中心的選擇將對聚類結果產生很大影響，而且該算法不能處理非球形的簇?；趯哟蔚木垲愃惴軌蛱幚矸乔蛐蔚拇兀珻hameleon 算法[3]是一種混合了“自頂向下”和“自底向上”兩種策略的層次聚類算法，Chameleon算法首先在原始數據集上構造k鄰域圖，然后利用一種高效的圖劃分算法對k鄰域圖進行劃分得到初始類簇，最后合并子簇，但是該算法對噪聲點敏感并且時間復雜度較高。基于密度的聚類算法認為簇是數據空間中被稀疏區域分開的稠密區域所構成的集合，DBSCAN（density based spatial clustering of applications with noise）算法[4]能夠發現任意形狀的簇而且對噪聲點不敏感，但時間復雜度較高，并且對鄰域參數比較敏感，不同的參數可能會得到不同的聚類結果。為了解決參數敏感的問題，文獻[5]提出利用反向最近鄰作為數據對象的密度估計方法，使用基于k鄰域圖的類似于DBSCAN 的方法進行聚類?；诰W格的聚類算法將數據對象空間按照不同的維度劃分成有限個單元，所有的處理都以單元為對象，這種方法將對數據集的聚類操作轉化為對數據空間中塊的處理，從而提高算法效率。CLIQUE（clustering in quest）算法[6]結合了基于網格和基于密度的聚類算法的特點，利用頻繁模式和關聯規則挖掘的先驗性質，得到了稠密單元關于維度的單調性，進而通過識別稠密單元進行聚類。FCM（fuzzy C-means clustering）算法[7]是一種經典的基于模糊的聚類算法，該算法通過迭代優化一個目標函數，根據隸屬度矩陣分配數據對象。由于預先指定類簇個數，如果參數選擇不當，容易陷入局部最優。

Rodriguez 等人在2014 年提出了DPC（density peak clustering）算法[8]，該算法不需要預先指定類簇個數，需要較少的參數就能發現非球狀的簇并且對噪聲不敏感。但是，DPC 算法在很多方面也存在很多不足[9]，包括以下三點：（1）通過人工設定截斷距離具有一定的隨機性，對聚類結果影響較大；（2）在計算數據對象的局部密度時沒有考慮數據內部的結構差異，當類簇間的數據密集程度差異較大時，不能得到理想的聚類結果；（3）不能很好地處理高維數據和大規模數據。針對DPC 算法存在的不足，已經提出了很多算法解決上述問題。文獻[10]提出算法結合k近鄰概念重新定義了截斷距離和局部密度的度量方法，對任意數據集能自適應地生成截斷距離，并使局部密度的計算結果更符合數據的真實分布。同時在決策圖中引入距離比較量代替原距離參數，使類簇中心在決策圖上更加明顯。文獻[11]利用k近鄰的思想計算數據對象的局部密度，雖然在很大程度上解決了截斷距離參數對聚類結果的影響，但是參數k的選擇問題需要進一步研究。文獻[12]引入自然鄰居計算數據對象的局部密度，從而解決了參數k的選擇問題。Ni 等人[13]提出了一種基于顯著密度峰值的PPC（prominent peak clustering）算法，該算法的主要思想是將數據對象劃分為多個勢簇，然后對密度峰值不明顯的簇進行合并，得到準確的聚類結果。文獻[14]通過萬有引力定律定義數據對象的局部密度，基于第一宇宙速度建立了兩步策略對剩余數據對象進行分配，使剩余數據對象的分配更加準確。文獻[15]通過引入加權局部密度序列和兩步分配策略改進DPC 算法，并使用近鄰動態表提高算法的聚類效率。Du 等人[16]將k近鄰和PCA（principal component analysis）方法引入DPC 算法中，使其能夠很好地處理高維數據。文獻[17]利用相似度指標MS 分配數據集的數據點，然后通過dc近鄰法重新界定邊界區域的噪聲點。該算法適用于高維數據、復雜數據結構的數據集，但是該算法不能自動確定聚類中心。文獻[18]提出利用網格的方法處理大規模數據。

針對密度峰聚類算法的缺陷，本文提出一種基于自然反向最近鄰的密度峰聚類算法（density peak clustering algorithm based on natural reverse nearest neighbor，RNN-DPC）。首先，該算法引入反向最近鄰計算數據對象的局部密度。其次，通過代表點和密度相結合的方式選取初始聚類中心。然后，應用密度自適應距離計算初始聚類中心之間的距離，利用DPC 算法聚類初始聚類中心，在初始聚類中心上構建決策圖，并通過決策圖選擇最終的聚類中心。最后，將未分配的數據對象分配到距離其最近的初始聚類中心所在的簇中。

1 相關工作

1.1 DPC 算法

DPC 算法是一種基于密度的聚類算法，該算法的基本思想基于兩個假設：（1）聚類中心局部密度最高并且被局部密度較低的近鄰數據對象包圍；（2）任意聚類中心與比它密度更高的數據對象間的距離都較遠。對于數據集中的任意數據對象i，DPC 算法需要計算數據對象的局部密度ρi以及到密度比它大的最近數據對象的距離δi，其中局部密度ρi的定義如式（1）所示。

其中，χ(x) 為分段函數，當x<0 時，χ(x)=1，否則χ(x)=0。dij表示數據對象i和數據對象j之間的距離，dc表示截斷距離。從式（1）可以看出，數據對象i的局部密度ρi等于分布在數據對象i的dc鄰域范圍內的數據對象的個數。δi則是通過計算數據對象i與其他密度更高的數據對象之間的相對距離來測量，δi的表達式如式（2）所示。

對于局部密度最大的數據對象i，則可以取δi=maxjdij。

DPC 算法的另外一種計算局部密度的方法為利用指數核進行計算，如式（3）所示。

DPC 算法利用局部密度ρ和距離δ構造決策圖，選擇樣本中ρ、δ都較大的樣本點作為聚類中心。在選出聚類中心后，將剩余的數據對象分配給距其最近并具有較高密度的近鄰所在的簇中。根據文獻[19]，DPC 算法的具體步驟如算法1 所示。由于輸入了局部密度和距離矩陣，DPC 算法的時間復雜度為O(N)，N為數據對象的個數。

算法1DPC(ρ,d)

輸入：局部密度ρ，距離矩陣d。

輸出：聚類結果CL。

1.2 代表點選取方法

接下來介紹一下基于代表點的聚類方法[20]，可以用式（4）表示這種聚類方法。

其中，xi、xj為數據集X={x1,x2,…,xn} 中的數據對象；dij為數據點xi和xj之間的距離；?j為該算法的損益值，一般取距離中值；yj為數據點xj是否作為代表點的指示，取值為1 表示該數據點可以作為代表點，取值為0 表示該數據點不能作為代表點。

1.3 密度自適應距離度量

一個好的相似性度量應該滿足以下兩個聚類假設：（1）鄰近的數據對象之間應該具有較高的相似性；（2）同一簇中的數據對象也應該具有較高的相似性。但是，歐式距離僅僅考慮了數據的局部信息，不能描述數據集的全局結構。如圖1 所示，數據對象a和c的相似性較高，因為a和c位于同一簇中，然而，使用歐式距離計算的結果是a與b的距離更小，這就不滿足聚類假設的全局一致性。顯而易見，簡單地使用基于歐式距離的相似性度量不能有效反映復雜數據集的真實分布。

Fig.1 Manifold data圖1 流形數據

文獻[21-22]提出了一種新的密度自適應距離度量方法來刻畫簇的分布特征并且滿足聚類假設的局部和全局一致性。因此，這種度量方法不會保證兩個直接相連的數據對象之間的距離是最短的。換言之，如果兩個數據對象在同一個簇中，這意味著存在一條連續的連接曲線僅通過高密度區域；否則，每條曲線一定穿過整個低密度區域。

在數據集上構建圖，記作G=(V,E)，其中V={v1,v2,…,vn}，每個vi表示一個頂點，也就是一個數據對象，(vi,vj)∈E由基于距離的函數加權。在高密度區域中如果一對數據對象之間存在許多連接線，那么這對數據對象的相似性較大，否則，相似性較低。首先定義了密度敏感線長度，其表達式如式（5）所示。

其中，||vi-vj||表示數據對象vi和vj之間的歐式距離。ρ>1 是密度因子，這種方法縮小了高密度區域數據對象之間的距離，而擴大了低密度區域數據對象之間的距離。這種方法能夠應用到凸形數據集和非凸形數據集。因為它不滿足三角不等式，所以它不能直接作為相似性度量方法。

設P={p1,p2,…,pl}∈V表示從p1到pl的路徑，并且路徑長度為l=|P|，(pk,pk+1)∈E，1 ≤k

其中，L(pk,pk+1)是路徑P上的兩個鄰接數據對象的密度敏感線長度，該度量方法與數據相關并且隨著局部密度自動調節大小。根據文獻[21]，本文的密度因子ρ取值為3。

1.4 自然鄰居

自然鄰居是近幾年提出的一種新的近鄰概念，其提出的目的是為了解決最近鄰概念中的參數選擇問題。與k近鄰和ε近鄰相比，自然鄰居通過不斷擴大鄰域搜索范圍自動適應數據集的分布結構特征，不需要人為設置參數，而是在自然鄰居的搜索過程中自適應得到。對于數據集X中的數據對象而言，如果數據對象xi把數據對象xj當作鄰居，同時數據對象xj把數據對象xi當作鄰居，那么數據對象xj就是數據對象xi的自然鄰居。如果數據集中的每一個數據對象都有一個自然鄰居，則此數據集達到了一個相對穩定狀態。

定義1（自然穩定狀態[23]）自然鄰居搜索過程達到自然穩定狀態，需要滿足式（7）所示的條件。

其中，xi、xj為數據集X中的數據對象，KNNk(xi)為xi的k近鄰。

定義2（k-最近鄰[19]）xi和xj是數據集X中的數據對象，數據對象xi的k最近鄰是該數據對象到其他數據對象的距離中最近的k個點，其定義如式（8）所示。

其中，index_dist(xi,xj)表示數據對象xi到其他數據對象的距離升序排序后的索引值，數據對象xi和xj之間的距離用歐式距離計算。

定義3（反向k最近鄰[19]）xi和xj是數據集中的數據對象，數據對象xi在數據對象xj的k最近鄰集KNNk(xj)中，那么數據對象xj是數據對象xi的反向最近鄰，其定義如式（9）所示。

定義4（自然特征值[23]）當自然鄰居搜索算法達到自然穩定狀態時，搜索次數k為自然特征值，記作λ，λ的表達式如式（10）所示。

其中，k初始值為1，nbk(xi)為數據對象xi在第k輪迭代時的反向最近鄰數，f(y)的定義如式（11）所示。

定義5（自然鄰居[24]）在達到自然穩定狀態時，如果數據對象xi屬于數據對象xj的鄰居，而數據對象xj屬于數據對象xi的鄰居，那么數據對象xi和xj屬于彼此的自然鄰居。如式（12）所示。

定義6（大值相互鄰域圖（maximum mutual neighborhood graph，MMNG）[25]）如果xi是xj的max{nb}近鄰之一，并且xj是xi的max{nb}近鄰之一，那么xi是xj的大值相互近鄰并且xj是xi的大值相互近鄰。通過連接每個數據對象的大值相互近鄰構建的圖就是大值相互鄰域圖。

基于以上分析，給出自然鄰居搜索算法的基本思想：在每輪迭代過程中，首先搜索每個數據對象xi的k最近鄰，并計算數據對象xi的反向最近鄰個數。然后確定是否滿足迭代終止條件：（1）沒有反向最近鄰的數據對象的個數為零；（2）在連續兩次迭代的過程中，沒有反向最近鄰的數據對象的數量不變。自然鄰居搜索算法NaNe-Searching 如算法2 所示。

算法2NaNe_Searching(X)

輸入：數據集X={x1,x2,…,xn}。

輸出：自然特征值λ，反向最近鄰數nb，λ-反向最近鄰RNNλ。

算法2 的時間復雜度分析：假設數據集的數據對象個數為n，利用KD 樹搜索數據對象的近鄰所消耗的時間為O(nlbn)，由于n的個數是有限的，此步驟是可終止的。因此算法2 的時間復雜度為O(nlbn)。

2 RNN-DPC 算法

在接下來的內容中，介紹如何篩選初始聚類中心，確定最終的聚類中心以及分配數據對象，并給出相關定義和算法。

2.1 篩選初始聚類中心

本文利用反向最近鄰計算數據對象的局部密度，反向最近鄰根據自然鄰居搜索算法自適應得到，從而有效解決了密度峰值算法在計算局部密度時對截斷距離dc敏感的問題。數據對象xi的局部密度表達式如式（13）所示。

其中，RNNλ(xi)表示數據對象xi的λ-反向最近鄰，λ為自然特征值，dist(xi,xj)表示數據對象xi和xj之間的歐式距離。

密度峰值聚類算法對于聚類中心的描述是聚類中心的局部密度比其鄰居的局部密度大，因此聚類中心往往出現在稠密區域。根據文獻[26]中的定理1：具有更高密度的數據對象更有可能成為聚類中心。因此稀疏區域的低密度數據對象不可能成為聚類中心，通過設定密度閾值將低于密度閾值的數據對象排除在外，以減少后續的迭代次數。可以通過設定百分比α的方式確定密度閾值，根據式（13）計算數據對象的局部密度，按照從高到低的順序排序，第α%個數據對象的密度即設為密度閾值，這樣數據集中后(1-α)% 的數據對象就被當作低密度數據對象而被排除。

排除數據集中的低密度數據對象之后，對數據集中剩余的數據對象通過代表點和密度相結合的方式選取初始聚類中心，進而提出了選取初始聚類中心的目標表達式，該表達式如式（14）所示。

其中，dij表示數據對象xi到初始聚類中心xj的距離，?j為損益值，一般取距離中值，yj為是否選取數據對象xj作為初始聚類中心的標記值，yj的取值范圍為：取值為1 表示該數據對象可以作為初始聚類中心，取值為0 表示該數據對象不能作為初始聚類中心。

基于以上分析，進一步給出選取初始聚類中心的基本思想：首先，根據式（13）計算數據對象xi的局部密度，并采用快速排序的方法將這些數據對象按照局部密度的高低進行遞減排序。然后，選取具有密度最大值的數據對象作為初始聚類中心，并根據式（14）計算初始目標函數J的值。最后，選取前α%的數據對象按降序排列加入到初始聚類中心集合IntCenter中，并通過式（14）計算目標函數J的值，若小于上次所計算的目標函數J的值，則在聚類中心集合中保留該數據對象，否則將其從聚類中心集合中刪除。循環上述過程，直至聚類中心點集合IntCenter遍歷結束或者目標函數J的值不再發生變化。選取初始聚類中心算法Acquire_IntCenter如算法3 所示。

算法3Acquire_IntCenter(X,α%)

輸入：數據集X={x1,x2,…,xn}，百分比α。

輸出：初始聚類中心集合IntCenter。

算法3 的時間復雜度分析：假設數據集中的數據對象的個數為n，假設從數據集中舍棄α%的數據對象后，數據集中的數據對象的個數為m，因此篩選初始聚類中心的時間復雜度為O(m)，由于m的個數是有限的，此步驟是可終止的。因此算法3 的時間復雜度為O(m)。

2.2 分配數據對象

找到初始聚類中心后，使用算法1 對初始聚類中心進行聚類，對于一個初始聚類中心xi，重新定義了它的局部密度ρ(xi)和相對距離δ(xi)。局部密度ρ(xi)用反向最近鄰進行計算，表達式如式（15）所示。

為了確保初始聚類中心具有良好的連通性，首先在原始數據集上構建大值相互鄰域圖，然后計算兩個鄰接數據對象間的密度敏感線長度，最后應用Dijkstra算法計算初始聚類中心之間的最短路徑。并且計算出來的最短路徑就是初始聚類中心之間的密度自適應距離。基于文獻[25]對局部核心點之間的距離計算方法，本文的相對距離的計算方式如式（16）所示。

其中，D(xi,xj)是兩個初始聚類中心xi和xj之間的密度自適應距離，根據式（6）計算密度自適應距離。

對于具有密度最高的初始聚類中心xi，它的相對距離δ(xi)的表達式如式（17）所示。

根據每一個初始聚類中心xi的局部密度ρ(xi)和相對距離δ(xi)在所有初始聚類中心上構建決策圖，并根據決策圖選擇最終的聚類中心。對于剩余的初始聚類中心，將其分配到密度較高并且密度自適應距離最小的初始聚類中心所在的簇中。將剩余的數據對象分配到距離其最近的初始聚類中心所在的簇中。

基于以上分析，進一步給出RNN-DPC 算法的基本思想：首先，引入反向最近鄰的思想計算數據對象的局部密度。其次，根據代表點和密度相結合的方式篩選初始聚類中心。利用DPC 算法聚類初始聚類中心，利用基于反向最近鄰計算的局部密度和重新定義的相對距離構建決策圖，并根據決策圖選擇最終的聚類中心。最后，將未分配的數據對象分配到距離其最近的初始聚類中心所在的簇中。RNN-DPC算法的具體步驟如算法4 所示。

算法4RNN_DPC(X)

輸入：數據集X={x1,x2,…,xn}。

輸出：聚類結果CL。

算法4 的時間復雜度分析：假設數據集的數據對象個數為n，調用算法2 的時間復雜度為O(nlbn)，調用算法3 的時間復雜度為O(m)。在使用DPC 算法前，需要計算初始聚類中心之間的最短路徑，其主要的時間消耗為Dijkstra 算法的時間復雜度為O(n2)。假設初始聚類中心的個數為u(u?n)，因此計算最短路徑的時間復雜度為O(un2) 。通過利用堆優化，Dijkstra 算法的時間復雜度可以減少到O((n+e)lbn)，e為圖中邊的個數。大值相互鄰域圖是一個稀疏圖，其邊的數量少于n(max_nb/2)（max_nb是一個常量），那么計算最短路徑的時間復雜度為O(unlbn)，因此算法4 的時間復雜度為O(unlbn)。

3 實驗結果與分析

為了證明RNN-DPC 算法的有效性，本章將采用不同的數據集進行實驗，包括不同形狀和不同規模的合成數據集和UCI 真實數據集。合成數據集和真實數據集的基本屬性將在3.1 節和3.2 節給出。同時，通過與基于聚類中心的聚類算法K-means 算法、基于密度的聚類算法DBSCAN、DPC 算法、基于k近鄰優化的DPC-KNN-PCA 算法和FKNN-DPC[27]算法進行各項指標的比較，從而驗證RNN-DPC 算法的性能。

本文將采用在聚類算法中廣泛使用的聚類精度（accuracy，ACC）、標準互信息（normalized mutual information，NMI）、F值（F-measure）這三個指標作為聚類算法性能度量標準。其中，NMI、F值和ACC 的取值范圍為[0,1]，值越大，表示聚類結果越好。

實驗環境：系統環境為Win10 的64 位操作系統。硬件環境為Intel?CoreTMi5-8265U CPU@1.60 GHz 1.80 GHz 處理器，8.00 GB RAM，256 GB ROM。所有程序采用Java語言實現。

在進行實驗之前，需要對數據集進行預處理，以消除缺失值的影響以及不同維度范圍的差異。數據集的預處理包括處理缺失數據和對數據進行標準化[27]，用均值替代缺失數據，數據的標準化采用式（18）所示的最大最小化方法。經過數據標準化，不僅消除了不同量綱對實驗結果的影響，而且降低了算法運行時間開銷。

其中，xij′表示第i行和第j列重新縮放的數據，xij表示第i行和第j列中的原始數據，xj是整個j列中的原始數據，max(xj)、min(xj)分別表示j列中的最大值和最小值。

3.1 合成數據集實驗結果分析

本節選取7 個合成數據集進行實驗，各數據集的基本屬性如表1 所示。

在合成數據集上分別計算F值、NMI、ACC。對上述對比算法進行100 次聚類，取各算法的各指標值的平均值作為其最終的結果值，如表2 所示。

Table 2 Comparison of evaluation criteria of clustering algorithms on synthetic data sets表2 各聚類算法在合成數據集上的評價指標對比

從表2 展示的RNN-DPC 算法、DPC-KNN-PCA算法、FKNN-DPC 算法、DPC 算法、DBSCAN 算法、Kmeans 算法共6 種聚類算法對各合成數據集的聚類結果的F值、NMI、ACC 等評價指標值的比較可以看出，本文的RNN-DPC 算法在各個數據集上的聚類指標均高于其他算法。具體情況是：在Atom 數據集上，RNN-DPC 算法的性能高于其他算法，DPC-KNNPCA 算法和FKNN-DPC 算法的性能相當。在Pathbased 數據集上，RNN-DPC 算法的各評價指標最高，DPC-KNN-PCA 算法和FKNN-DPC 算法的性能相當。在S4 數據集上，RNN-DPC 算法的各評價指標最高，DPC-KNN-PCA 算法次之，而DBSCAN 算法的性能最差。在Jain 數據集上，RNN-DPC 算法的評價指標值最高，聚類結果最好，DPC-KNN-PCA 算法次之，而FKNN-DPC 算法的性能最差。在D6 數據集上，RNN-DPC 算法的性能明顯優于其他聚類算法，DBSCAN 算法次之，其他聚類算法在該數據集上的聚類結果均很差。在Zigzag 和Parabolic 數據集上，RNN-DPC 算法的聚類指標值也均高于其他聚類算法，FKNN-DPC 和DPC-KNN-PCA 算法的性能相當，K-means 算法的各個指標值最低。Jain 數據集、D6 數據集、Zigzag 數據集、Parabolic 數據集均為復雜流形數據，從表中的聚類結果可以看出，RNN-DPC 算法的各個聚類指標值均高于其他聚類算法，說明RNNDPC 算法在處理流形數據時具有較大優勢。

3.2 真實UCI數據集實驗結果分析

本節選取7 個UCI 真實數據集進行實驗，真實數據集的基本屬性如表3 所示。

Table 3 Real data sets from UCI表3 真實UCI數據集

在UCI真實數據集上分別計算F值、NMI、ACC。對上述對比算法進行100 次聚類，取各算法的各指標值的平均值作為其最終的結果值，如表4 所示。

真實數據集的聚類結果采用3 個聚類指標F值、NMI、ACC，表4 給出了本文提出RNN-DPC 算法與上述對比算法在7 個UCI 真實數據集上的聚類結果。從表4 中的3 個指標上的聚類結果可以看出，本文的RNN-DPC 算法在各個數據集上的聚類結果皆高于其他對比算法。在Iris 數據集上，RNN-DPC 算法的各評價指標高于其他對比算法，FKNN-DPC 算法和DPC 算法的性能相當。在Segment 數據集上，RNNDPC 算法的性能最好，DPC-KNN-PCA 算法的性能最差，DPC 算法和K-means 算法性能相當。在Pageblocks 數據集上，RNN-DPC 算法的各評價指標最高，K-means算法的性能最差。在Cancer數據集上，RNNDPC 算法的各個聚類評價指標最高，DPC-KNN-PCA算法和FKNN-DPC 算法的性能相當，而DPC 算法的性能最差。在Wine 數據集上，RNN-DPC 算法和DPC算法的性能相當，而DBSCAN 算法的聚類性能最差。在Breast 數據集上，RNN-DPC 算法和K-means 算 法的性能相當，DPC-KNN-PCA 算法次之，而DBSCAN算法的聚類性能最差。在Control 數據集上，RNNDPC 算法在各個指標上的聚類結果優于其他算法，DBSCAN 算法和DPC-KNN-PCA 算法在各個指標上的聚類結果最差。

在表5 的算法運行時間對比中，K-means 算法在各個數據集上運行的時間最少，因為K-means 算法通過迭代一個目標函數，所以運行時間最少。其次是DPC 算法，因為DPC 算法的主要時間消耗為計算數據對象之間的歐式距離，并且它的一步分配策略使算法比較高效。當數據集規模較小時，DBSCAN 算法的時間消耗與DPC 算法相當，當數據集規模較大時，DBSCAN 算法的時間消耗與FKNN-DPC 算法相當。DPC-KNN-PCA 算法和FKNN-DPC 算法的時間消耗相當。RNN-DPC 算法首先利用KD 樹搜索數據對象的近鄰，為了確保初始聚類中心具有良好的連通性，需要在原始數據集上構建大值相互鄰域圖，然后需要計算兩個鄰接點之間的密度自適應距離，最后應用Dijkstra 算法計算初始聚類中心之間的最短距離，這個最短距離也就是兩個初始聚類中心之間的密度自適應距離。由于需要計算一系列的距離，RNNDPC 算法在不同規模的數據集上所消耗的時間較其他對比算法都是較高的。

Table 4 Comparison of evaluation criteria of clustering algorithms on real data sets from UCI表4 各聚類算法在真實UCI數據集上的評價指標對比

Table 5 Comparison of running time of clustering algorithms on real data sets from UCI表5 各聚類算法在真實UCI數據集上的運行時間對比

3.3 密度閾值的魯棒性實驗

通過選擇合成數據集D6 數據集和Zigzag 數據集進行實驗，D6 數據集包含一定量的噪聲點，Zigzag數據集不包含噪聲點。α的值從85%變到100%，即高密度數據的比例從85%變到100%。圖2 表示D6數據集在不同百分比α上的聚類精度情況，圖3 表示Zigzag數據集在不同百分比α上的聚類精度情況。通過圖2 和圖3 可以看出，針對不同的α值，RNN-DPC算法都能得到正確的聚類結果。從而表明RNNDPC 算法對設置的百分比α是魯棒的。

Fig.2 ACC of different density threshold α on D6圖2 D6 數據集在不同密度閾值α 上的聚類精度

Fig.3 ACC of different density threshold α on Zigzag圖3 Zigzag 數據集在不同密度閾值α 上的聚類精度

4 結論

本文提出了一種基于自然反向最近鄰的密度峰值聚類算法RNN-DPC。首先，引入反向最近鄰計算數據對象的局部密度，不用輸入任何參數，避免了截斷距離參數敏感的問題。其次，通過代表點和密度相結合的方式選取初始聚類中心并應用密度自適應距離計算初始聚類中心之間的距離，通過引入密度自適應距離使RNN-DPC 算法對流形數據集聚類時是有效的。然后，利用DPC 算法聚類初始聚類中心，并根據決策圖選擇最終的聚類中心。最后，將剩余的數據對象分配到距離其最近的初始聚類中心所在的簇中。通過在合成數據集和UCI 真實數據集上進行實驗，表明該算法較其他比較算法有較好的聚類準確性。