自然反向最近鄰優(yōu)化的密度峰值聚類算法

劉 娟，萬 靜

哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150080

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

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

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

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

1 相關(guān)工作

1.1 DPC 算法

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

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

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

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

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

算法1DPC(ρ,d)

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

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

1.2 代表點(diǎn)選取方法

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

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

1.3 密度自適應(yīng)距離度量

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

Fig.1 Manifold data圖1 流形數(shù)據(jù)

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

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

其中，||vi-vj||表示數(shù)據(jù)對象vi和vj之間的歐式距離。ρ>1 是密度因子，這種方法縮小了高密度區(qū)域數(shù)據(jù)對象之間的距離，而擴(kuò)大了低密度區(qū)域數(shù)據(jù)對象之間的距離。這種方法能夠應(yīng)用到凸形數(shù)據(jù)集和非凸形數(shù)據(jù)集。因?yàn)樗粷M足三角不等式，所以它不能直接作為相似性度量方法。

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

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

1.4 自然鄰居

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

定義1（自然穩(wěn)定狀態(tài)[23]）自然鄰居搜索過程達(dá)到自然穩(wěn)定狀態(tài)，需要滿足式（7）所示的條件。

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

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

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

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

定義4（自然特征值[23]）當(dāng)自然鄰居搜索算法達(dá)到自然穩(wěn)定狀態(tài)時，搜索次數(shù)k為自然特征值，記作λ，λ的表達(dá)式如式（10）所示。

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

定義5（自然鄰居[24]）在達(dá)到自然穩(wěn)定狀態(tài)時，如果數(shù)據(jù)對象xi屬于數(shù)據(jù)對象xj的鄰居，而數(shù)據(jù)對象xj屬于數(shù)據(jù)對象xi的鄰居，那么數(shù)據(jù)對象xi和xj屬于彼此的自然鄰居。如式（12）所示。

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

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

算法2NaNe_Searching(X)

輸入：數(shù)據(jù)集X={x1,x2,…,xn}。

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

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

2 RNN-DPC 算法

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

2.1 篩選初始聚類中心

本文利用反向最近鄰計(jì)算數(shù)據(jù)對象的局部密度，反向最近鄰根據(jù)自然鄰居搜索算法自適應(yīng)得到，從而有效解決了密度峰值算法在計(jì)算局部密度時對截?cái)嗑嚯xdc敏感的問題。數(shù)據(jù)對象xi的局部密度表達(dá)式如式（13）所示。

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

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

排除數(shù)據(jù)集中的低密度數(shù)據(jù)對象之后，對數(shù)據(jù)集中剩余的數(shù)據(jù)對象通過代表點(diǎn)和密度相結(jié)合的方式選取初始聚類中心，進(jìn)而提出了選取初始聚類中心的目標(biāo)表達(dá)式，該表達(dá)式如式（14）所示。

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

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

算法3Acquire_IntCenter(X,α%)

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

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

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

2.2 分配數(shù)據(jù)對象

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

為了確保初始聚類中心具有良好的連通性，首先在原始數(shù)據(jù)集上構(gòu)建大值相互鄰域圖，然后計(jì)算兩個鄰接數(shù)據(jù)對象間的密度敏感線長度，最后應(yīng)用Dijkstra算法計(jì)算初始聚類中心之間的最短路徑。并且計(jì)算出來的最短路徑就是初始聚類中心之間的密度自適應(yīng)距離?；谖墨I(xiàn)[25]對局部核心點(diǎn)之間的距離計(jì)算方法，本文的相對距離的計(jì)算方式如式（16）所示。

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

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

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

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

算法4RNN_DPC(X)

輸入：數(shù)據(jù)集X={x1,x2,…,xn}。

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

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

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

為了證明RNN-DPC 算法的有效性，本章將采用不同的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，包括不同形狀和不同規(guī)模的合成數(shù)據(jù)集和UCI 真實(shí)數(shù)據(jù)集。合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集的基本屬性將在3.1 節(jié)和3.2 節(jié)給出。同時，通過與基于聚類中心的聚類算法K-means 算法、基于密度的聚類算法DBSCAN、DPC 算法、基于k近鄰優(yōu)化的DPC-KNN-PCA 算法和FKNN-DPC[27]算法進(jìn)行各項(xiàng)指標(biāo)的比較，從而驗(yàn)證RNN-DPC 算法的性能。

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

實(shí)驗(yàn)環(huán)境：系統(tǒng)環(huán)境為Win10 的64 位操作系統(tǒng)。硬件環(huán)境為Intel?CoreTMi5-8265U CPU@1.60 GHz 1.80 GHz 處理器，8.00 GB RAM，256 GB ROM。所有程序采用Java語言實(shí)現(xiàn)。

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

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

3.1 合成數(shù)據(jù)集實(shí)驗(yàn)結(jié)果分析

本節(jié)選取7 個合成數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，各數(shù)據(jù)集的基本屬性如表1 所示。

在合成數(shù)據(jù)集上分別計(jì)算F值、NMI、ACC。對上述對比算法進(jìn)行100 次聚類，取各算法的各指標(biāo)值的平均值作為其最終的結(jié)果值，如表2 所示。

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

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

3.2 真實(shí)UCI數(shù)據(jù)集實(shí)驗(yàn)結(jié)果分析

本節(jié)選取7 個UCI 真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，真實(shí)數(shù)據(jù)集的基本屬性如表3 所示。

Table 3 Real data sets from UCI表3 真實(shí)UCI數(shù)據(jù)集

在UCI真實(shí)數(shù)據(jù)集上分別計(jì)算F值、NMI、ACC。對上述對比算法進(jìn)行100 次聚類，取各算法的各指標(biāo)值的平均值作為其最終的結(jié)果值，如表4 所示。

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

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

Table 4 Comparison of evaluation criteria of clustering algorithms on real data sets from UCI表4 各聚類算法在真實(shí)UCI數(shù)據(jù)集上的評價指標(biāo)對比

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

3.3 密度閾值的魯棒性實(shí)驗(yàn)

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

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

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

4 結(jié)論

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