劉 娟，萬 靜

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

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

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

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

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

1 相關(guān)工作

1.1 DPC 算法

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

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

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

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

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

算法1DPC(ρ,d)

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

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

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

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

其中，xi、xj為數(shù)據(jù)集X={x1,x2,…,xn} 中的數(shù)據(jù)對(duì)象；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)距離度量

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

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

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

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

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

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

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

1.4 自然鄰居

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

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

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

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

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

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

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

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

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

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

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

算法2NaNe_Searching(X)

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

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

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

2 RNN-DPC 算法

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

2.1 篩選初始聚類中心

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

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

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

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

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

基于以上分析，進(jìn)一步給出選取初始聚類中心的基本思想：首先，根據(jù)式（13）計(jì)算數(shù)據(jù)對(duì)象xi的局部密度，并采用快速排序的方法將這些數(shù)據(jù)對(duì)象按照局部密度的高低進(jìn)行遞減排序。然后，選取具有密度最大值的數(shù)據(jù)對(duì)象作為初始聚類中心，并根據(jù)式（14）計(jì)算初始目標(biāo)函數(shù)J的值。最后，選取前α%的數(shù)據(jù)對(duì)象按降序排列加入到初始聚類中心集合IntCenter中，并通過式（14）計(jì)算目標(biāo)函數(shù)J的值，若小于上次所計(jì)算的目標(biāo)函數(shù)J的值，則在聚類中心集合中保留該數(shù)據(jù)對(duì)象，否則將其從聚類中心集合中刪除。循環(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 的時(shí)間復(fù)雜度分析：假設(shè)數(shù)據(jù)集中的數(shù)據(jù)對(duì)象的個(gè)數(shù)為n，假設(shè)從數(shù)據(jù)集中舍棄α%的數(shù)據(jù)對(duì)象后，數(shù)據(jù)集中的數(shù)據(jù)對(duì)象的個(gè)數(shù)為m，因此篩選初始聚類中心的時(shí)間復(fù)雜度為O(m)，由于m的個(gè)數(shù)是有限的，此步驟是可終止的。因此算法3 的時(shí)間復(fù)雜度為O(m)。

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

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

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

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

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

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

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

算法4RNN_DPC(X)

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

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

算法4 的時(shí)間復(fù)雜度分析：假設(shè)數(shù)據(jù)集的數(shù)據(jù)對(duì)象個(gè)數(shù)為n，調(diào)用算法2 的時(shí)間復(fù)雜度為O(nlbn)，調(diào)用算法3 的時(shí)間復(fù)雜度為O(m)。在使用DPC 算法前，需要計(jì)算初始聚類中心之間的最短路徑，其主要的時(shí)間消耗為Dijkstra 算法的時(shí)間復(fù)雜度為O(n2)。假設(shè)初始聚類中心的個(gè)數(shù)為u(u?n)，因此計(jì)算最短路徑的時(shí)間復(fù)雜度為O(un2) 。通過利用堆優(yōu)化，Dijkstra 算法的時(shí)間復(fù)雜度可以減少到O((n+e)lbn)，e為圖中邊的個(gè)數(shù)。大值相互鄰域圖是一個(gè)稀疏圖，其邊的數(shù)量少于n(max_nb/2)（max_nb是一個(gè)常量），那么計(jì)算最短路徑的時(shí)間復(fù)雜度為O(unlbn)，因此算法4 的時(shí)間復(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é)給出。同時(shí)，通過與基于聚類中心的聚類算法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）這三個(gè)指標(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)之前，需要對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理，以消除缺失值的影響以及不同維度范圍的差異。數(shù)據(jù)集的預(yù)處理包括處理缺失數(shù)據(jù)和對(duì)數(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)化，不僅消除了不同量綱對(duì)實(shí)驗(yàn)結(jié)果的影響，而且降低了算法運(yùn)行時(shí)間開銷。

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

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

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

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

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

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

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

本節(jié)選取7 個(gè)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。對(duì)上述對(duì)比算法進(jìn)行100 次聚類，取各算法的各指標(biāo)值的平均值作為其最終的結(jié)果值，如表4 所示。

真實(shí)數(shù)據(jù)集的聚類結(jié)果采用3 個(gè)聚類指標(biāo)F值、NMI、ACC，表4 給出了本文提出RNN-DPC 算法與上述對(duì)比算法在7 個(gè)UCI 真實(shí)數(shù)據(jù)集上的聚類結(jié)果。從表4 中的3 個(gè)指標(biāo)上的聚類結(jié)果可以看出，本文的RNN-DPC 算法在各個(gè)數(shù)據(jù)集上的聚類結(jié)果皆高于其他對(duì)比算法。在Iris 數(shù)據(jù)集上，RNN-DPC 算法的各評(píng)價(jià)指標(biāo)高于其他對(duì)比算法，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 算法的各評(píng)價(jià)指標(biāo)最高，K-means算法的性能最差。在Cancer數(shù)據(jù)集上，RNNDPC 算法的各個(gè)聚類評(píng)價(jià)指標(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 算法在各個(gè)指標(biāo)上的聚類結(jié)果優(yōu)于其他算法，DBSCAN 算法和DPC-KNN-PCA 算法在各個(gè)指標(biāo)上的聚類結(jié)果最差。

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

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

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

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 可以看出，針對(duì)不同的α值，RNN-DPC算法都能得到正確的聚類結(jié)果。從而表明RNNDPC 算法對(duì)設(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ù)對(duì)象的局部密度，不用輸入任何參數(shù)，避免了截?cái)嗑嚯x參數(shù)敏感的問題。其次，通過代表點(diǎn)和密度相結(jié)合的方式選取初始聚類中心并應(yīng)用密度自適應(yīng)距離計(jì)算初始聚類中心之間的距離，通過引入密度自適應(yīng)距離使RNN-DPC 算法對(duì)流形數(shù)據(jù)集聚類時(shí)是有效的。然后，利用DPC 算法聚類初始聚類中心，并根據(jù)決策圖選擇最終的聚類中心。最后，將剩余的數(shù)據(jù)對(duì)象分配到距離其最近的初始聚類中心所在的簇中。通過在合成數(shù)據(jù)集和UCI 真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，表明該算法較其他比較算法有較好的聚類準(zhǔn)確性。