基于二階k 近鄰的密度峰值聚類算法研究

王大剛，丁世飛，鐘 錦

1.中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116

2.合肥師范學(xué)院 計算機學(xué)院，合肥 230601

聚類分析是用于模式識別和數(shù)據(jù)挖掘領(lǐng)域研究中的一個重要方法。20 世紀60 年代，最早的層次聚類算法[1]誕生，隨后一大批聚類算法被相繼提出，Kmeans[2]、譜聚類[3]、DBSCAN（density-based spatial clustering of applications with noise）[4]等常用經(jīng)典算法一直沿用至今。根據(jù)文獻[5]中的研究觀點，現(xiàn)有的聚類算法大致可以分為[6-9]層次聚類、網(wǎng)格聚類、密度聚類、圖模型聚類、劃分聚類、代表點聚類、模型聚類共七大類方法。聚類算法在社交網(wǎng)絡(luò)、輿情研究、圖像識別、深度學(xué)習(xí)等領(lǐng)域有著廣泛應(yīng)用。

2014 年Rodriguez 等人[10]提出的密度峰值算法引起了學(xué)術(shù)界研究的一次新的研究熱潮，算法通過定義局部密度和相對距離快速定位聚類中心，能夠比較快速和高效地得到滿意的聚類結(jié)果。盡管如此，算法仍然存在比較明顯的缺點。DPC（clustering by fast search and find of density peaks）算法在計算局部密度時采用固定的截斷距離，對節(jié)點周圍的節(jié)點數(shù)據(jù)簡單計數(shù)，針對密度有很大差異的數(shù)據(jù)集很難做出準確識別，不具備很好的魯棒性。另外算法得到聚類中心后，通過單一的分配步驟，把非中心節(jié)點分配給相應(yīng)的聚類中心點，分配過程一旦出錯，會導(dǎo)致后續(xù)錯誤的層層傳遞。針對這些固有問題，學(xué)者們提出了一大批改進算法。

傳統(tǒng)DPC 算法利用歐幾里德距離計算節(jié)點之間相似度，對于非均勻和高維數(shù)據(jù)，無法得到滿意結(jié)果。丁世飛等人[11]提出基于不相似性度量優(yōu)化的密度峰值聚類，考慮節(jié)點周圍的分布情況，用概率塊重新度量節(jié)點的相似性，在不均勻數(shù)據(jù)和高維數(shù)據(jù)上有較好的識別精度。Du 等人[12]從提升算法魯棒性角度，將k近鄰（k-nearest neighbor，KNN）思想引入DPC，結(jié)合主成分分析，提出DPC-KNN 算法。該算法基于k近鄰的概念取代原始算法中固定的截斷距離，從對固定距離的計算轉(zhuǎn)化為節(jié)點周圍節(jié)點數(shù)的計算，對不同密度的數(shù)據(jù)集具有很好的魯棒性和精度提升。同樣基于近鄰思想，Liu 等人[13]結(jié)合增強版的SNN（shared-nearest-neighbor-based clustering）近鄰原理，結(jié)合兩步驟的分配方案，提出SNNDPC 算法。算法提出共享距離概念，把節(jié)點共享鄰居情況作為節(jié)點間相似性的度量方式，進而改進局部密度的計算方式。在此基礎(chǔ)上，又定義了兩種策略的非中心分配方案，算法對變化密度和分布不規(guī)則數(shù)據(jù)集有一定的優(yōu)越性。Xie 等人[14]提出FDPC（fuzzy weightedk-nearest neighbors density peak clustering）算法，算法用節(jié)點間的距離衡量節(jié)點間的相似性，然后利用相似性定義節(jié)點屬于某個簇的概率大小。利用這個概率，同樣結(jié)合多步驟的分配策略對節(jié)點進行聚類，算法取得了比較滿意的效果。文獻[15-16]結(jié)合近鄰和密度的概念，提出結(jié)合重力度量的密度聚類（clustering approach based on density peaks clustering and a modified gravitational search algorithm，GSA-DPC）算法。算法充分利用近鄰思想的優(yōu)點，結(jié)合密度指標，重新確定集群中心的候選者，取得比較好的準確性和計算效率。此外研究者還借鑒其他領(lǐng)域中的思想，比如生物進化、物理學(xué)優(yōu)化等概念結(jié)合密度峰值聚類，提出改進算法[17-18]。Yang等人[19]提出LDPC（Laplacian centrality peaks clustering algorithm）算法，把數(shù)據(jù)集用帶權(quán)重的有向圖進行刻畫，利用類似譜聚類中拉普拉斯矩陣的概念來度量原來的局部密度，算法消除了原始DPC 算法對固定參數(shù)的依賴，取得了比較高的魯棒性和正確率。上述算法在對原有算法改進的過程中，基本出發(fā)點就是對局部密度的度量引入其他更多的信息，試圖更加準確地表達節(jié)點的局部密度。從現(xiàn)有文獻來看，相當(dāng)數(shù)量的文獻都是把k近鄰思想引入原算法，從對原來固定距離的度量上升到對周圍節(jié)點個數(shù)多少的度量，一定程度上提高了算法的魯棒性，但都忽視了節(jié)點周圍的具體局部網(wǎng)絡(luò)分布結(jié)構(gòu)對節(jié)點密度的實際影響，導(dǎo)致仍然無法度量節(jié)點的實際密度。

考察到節(jié)點的鄰居和鄰居周圍節(jié)點間連接的綜合影響，本文提出一種折中的局部密度度量方法，稱為二階k近鄰密度峰值聚類。算法認為節(jié)點的綜合密度應(yīng)該由兩部分構(gòu)成，直觀上來看，一方面k近鄰提供直接密度，直接密度由節(jié)點周圍直接相連的節(jié)點數(shù)來直接反映，另一方面由次k近鄰與周圍的節(jié)點提供間接密度，間接密度衡量節(jié)點鄰居周圍的網(wǎng)絡(luò)拓撲分布，反映了鄰居間的相互影響和相互關(guān)系。二階k近鄰思想可以總結(jié)為從最近鄰居節(jié)點的范圍擴大到了最近鄰和次近鄰節(jié)點構(gòu)成的集合，其本質(zhì)是對節(jié)點中心性度量的進階，將節(jié)點的影響力在擴散中所發(fā)揮的作用進一步凝聚，對節(jié)點的影響力衡量更為準確，核心假設(shè)則是認為當(dāng)一個節(jié)點u所連接的鄰居與該鄰居節(jié)點所處的局部網(wǎng)絡(luò)中的其他節(jié)點連接更為緊密時，鄰居節(jié)點擴散信息的能力更強，將鄰居節(jié)點的擴散能力相疊加累計作為衡量節(jié)點u密度大小的重要因素。在此基礎(chǔ)上重新定義密度聚類算法。實驗驗證本文算法有效性，且在精度和正確性方面具有一定的優(yōu)勢。

1 密度峰值聚類算法的基本原理

密度峰值聚類基本思想基于兩個基本假設(shè)：聚類中心之間的相對距離較遠，聚類中心的局部密度大于其周圍非中心點的局部密度。算法定義數(shù)據(jù)集X={x1,x2,…,xn}，首先利用歐幾里德距離dij定義節(jié)點之間的相似度，然后構(gòu)造相似度矩陣D=[d1,d2,…,dn]T∈Rn×n，在此基礎(chǔ)上，利用式（1）、式（2）度量節(jié)點的局部密度。其中dc稱為截斷距離，該公式用于統(tǒng)計節(jié)點i周圍不超過截斷距離的節(jié)點個數(shù)。

當(dāng)數(shù)據(jù)集為小規(guī)模數(shù)據(jù)集時，可用高斯函數(shù)來計算：

與此同時，式（3）定義相對距離δi表示局部密度大于xi節(jié)點且距離最近點的距離，如果xi節(jié)點本身為密度最大節(jié)點，則定義為式（4）：

DPC 算法根據(jù)計算出的局部密度ρi和相對距離δi，繪制決策圖，如圖1 所示。根據(jù)二維決策圖標識具有較高ρi和δi的點作為簇中心，然后利用單步驟的分配策略對非中心點進行分配，最后篩選出離群點，得到劃分結(jié)果。

Fig.1 Decision diagram of density peak clustering algorithm圖1 密度峰值聚類算法決策圖

密度峰值聚類能夠?qū)Ω鞣N形狀的數(shù)據(jù)樣本進行聚類，得到滿意的效果，但是仍存在以下一些不足：

（1）截斷距離dc考慮的是數(shù)據(jù)的全局分布信息，忽略節(jié)點周圍的局部分布情況，針對密度變化較大的數(shù)據(jù)集有非常大的敏感性和較差的計算精度。如圖2 是采用不同截斷距離在完全相同數(shù)據(jù)集flame 上的表現(xiàn)，可以看到原始算法不具有較好的魯棒性。

（2）算法在得到簇中心節(jié)點后，非中心點分配采用標準統(tǒng)一的、單次的策略，對個別發(fā)生錯誤的節(jié)點很難有機會進行糾正，容錯性較差。

2 基于二階k 近鄰的密度峰值聚類算法

2.1 局部密度的定義

Fig.2 Performance of different dc on same data set圖2 不同的截斷距離dc 在相同數(shù)據(jù)集上的表現(xiàn)

通過上文分析知道局部密度的計算對確定聚類中心非常重要，為了提高局部密度的計算精度，本文考慮節(jié)點的二階k近鄰，從現(xiàn)有文獻中普遍采用的k近鄰度量擴大和擴展到由k近鄰和次k近鄰節(jié)點所構(gòu)成的節(jié)點集合，新的集合可以看作一個局部的網(wǎng)絡(luò)結(jié)構(gòu)，其本質(zhì)是節(jié)點中心性度量的進階，用周圍的節(jié)點和周圍節(jié)點所構(gòu)成的局部結(jié)構(gòu)關(guān)系來描述中心節(jié)點，從而使得節(jié)點的密度度量更為準確和接近實際。為了便于后面算法的展開說明，給出如下定義和描述：

定義1（二階k近鄰）用Γ1(u)表示節(jié)點u的k-近鄰，用Γ2(u)表示節(jié)點u的二階k近鄰，Γ2(u)={u′∈Γ1(v)|v∈Γ1(u)}，在此基礎(chǔ)上有式（5）、式（6）成立：

其中，Q(u)表示節(jié)點u的二階近鄰的數(shù)量；C(v)表示節(jié)點v的k近鄰數(shù)量；N(w)表示節(jié)點w集合的大小。

密度峰值聚類其中的一個基本假設(shè)就是用節(jié)點周圍一定范圍內(nèi)的節(jié)點數(shù)量來定義其密度，但這不足以表征足夠的信息。本文同時考察節(jié)點一定范圍內(nèi)節(jié)點數(shù)量和節(jié)點的分布質(zhì)量來綜合度量密度。為此將節(jié)點密度的度量分為兩部分：一部分由節(jié)點周圍的相似度較大的節(jié)點近鄰提供直接密度；另一部分由二階k近鄰節(jié)點集中不包含直接近鄰的部分來提供間接密度。

Fig.3 Data distribution diagram圖3 數(shù)據(jù)分布示意圖

如圖3 所示，在k近鄰取值為5 的情況下，節(jié)點1的Γ1(1)={2,3,4,5,6}共5 個節(jié)點，而Γ2(1)={1,4,12,13,3,2,6,7,16,14,15,5,7,17,}共14 個節(jié)點，在考慮衡量節(jié)點1 的密度時，可以看到節(jié)點5 周圍的密度比其他節(jié)點的密度要高，但是距離節(jié)點1 較遠，節(jié)點1 和節(jié)點5在k=5 的情況下并不互為k近鄰，其周圍的密度無法為節(jié)點1 提供直接的聚類密度，在考慮近鄰用直接距離度量的算法中可能會被忽略。但同時可以關(guān)注到節(jié)點1 和節(jié)點5 在k=5 的情況下互為二階k近鄰。通過二階k近鄰和計算出來的節(jié)點一部分是包含在k近鄰節(jié)點當(dāng)中，這部分節(jié)點反映了鄰居的鄰居節(jié)點也是鄰居的現(xiàn)象，說明這部分節(jié)點緊密圍繞在節(jié)點周圍，為節(jié)點貢獻了直接的密度度量，而其余節(jié)點則提供某種程度的間接度量，相當(dāng)于動態(tài)引入了一個截斷距離，根據(jù)實際的數(shù)據(jù)點的分布情況來衡量。社交網(wǎng)絡(luò)中使用節(jié)點的度[20-21]作為衡量節(jié)點之間相互影響力大小的指標，借鑒相關(guān)的概念，本文中節(jié)點對其他節(jié)點的密度的影響認為可以通過距離來產(chǎn)生，因此為了衡量節(jié)點對其他節(jié)點密度的影響力大小，本文給出如下定義：

定義2（直接密度）提供直接密度的節(jié)點屬于中心節(jié)點的k近鄰節(jié)點，且連接較為緊密的節(jié)點，定義集合C1(u)，有C1(u)=Γ1(u)?Γ2(u)，直觀上理解，提供直接密度的是這樣一些節(jié)點：是自己的鄰居，同時鄰居的鄰居也是自己的鄰居。在此基礎(chǔ)上定義直接密度計算公式（7），表示為d(u)，該公式用節(jié)點的C1集合中節(jié)點集的距離和的倒數(shù)來表達節(jié)點的直接密度。

定義3（間接密度）對于某數(shù)據(jù)集的節(jié)點，屬于某個節(jié)點的k近鄰節(jié)點和二階k近鄰節(jié)點集合，但是計算節(jié)點連接不夠緊密的集合定義為C2(u)，對那些節(jié)點鄰居的鄰居并不是自己的鄰居的節(jié)點，有定義C2(u)=Γ1(u)?Γ2(u)-C1(u)，用C2集合來計算間接密度，在此基礎(chǔ)上定義間接密度公式（8），公式用C2集合中距離的平方和的倒數(shù)與C2集合數(shù)量的乘積表達，計為i(u)。

在上述定義的基礎(chǔ)上，本文為直接密度節(jié)點和間接密度節(jié)點分配一個比例系數(shù)α，根據(jù)文獻[20]中實驗的建議，實驗中α取0.7 是一個適中的取值，那么可以定義節(jié)點的混合密度度量公式用于取代原始的密度公式ρ(u)。

從直觀上解釋，綜合考慮直接密度和間接密度關(guān)系的局部密度公式在近鄰數(shù)k確定的情況下，不增加其他多余的參數(shù)，既考慮到了近鄰的數(shù)量，又考慮到了近鄰周圍的分布情況對密度的影響，使得算法適應(yīng)數(shù)據(jù)集不同密度和形狀的變化，具備很好的魯棒性，后面通過實驗驗證算法的有效性。

2.2 粗調(diào)與細調(diào)結(jié)合的分配策略

工程上最常用的復(fù)雜系統(tǒng)的調(diào)優(yōu)策略就是一種粗調(diào)到細調(diào)的過程性多步驟思路，即先大再小，先粗再細。傳統(tǒng)的密度峰值聚類算法在計算相對距離的同時，根據(jù)局部密度大小從高到低排序，一邊計算相對距離，一邊在密度已排序的基礎(chǔ)上根據(jù)相對距離更新簇標記。本質(zhì)上是一種單步的分配策略，最大的問題就是如果有個別節(jié)點分配出錯，導(dǎo)致錯誤會一步一步傳遞下去，從而影響相關(guān)節(jié)點分配的正確性。本文在二階k近鄰概念的基礎(chǔ)上提出多步驟且逐步細化的分配策略。其特點是原算法的連續(xù)分配過程分解成在迭代過程中多階段完成，一個節(jié)點的分配結(jié)果對另外節(jié)點歸屬關(guān)系造成的影響的可能性被降低。一個距離中心點較遠或者密度較弱的節(jié)點會經(jīng)歷粗調(diào)、細調(diào)和最后判斷三個階段才會最終確定，最大程度上調(diào)高算法的容錯性和準確性。主要步驟包括首先確定中心節(jié)點周圍的連接比較緊密的非中心點，然后分配次要的非中心點，在前面兩個步驟的基礎(chǔ)上不斷遞歸迭代，最后利用傳統(tǒng)的密度峰值聚類分配策略確定剩下的所有節(jié)點的歸屬關(guān)系。

第一步粗調(diào)，從篩選密度較大節(jié)點開始，首先在k近鄰內(nèi)考慮為節(jié)點提供直接密度的集合C1(u)，算法迭代首次從中心節(jié)點開始對每個中心節(jié)點的所有直接密度節(jié)點集合直接標記所屬簇中心的簇標記，同時將所有的中心點的周圍直接密度節(jié)點放入隊列p中，分配策略接著進行細調(diào)，通過計算平均距離du，考慮每個中心點的二階k近鄰集合，定義式（10）：

對二階k近鄰集合中所有距離不超過平均距離du的節(jié)點標注簇標記，同時將集合C2(u)中的相應(yīng)節(jié)點也放入p隊列的末尾，廣度優(yōu)先搜索遍歷隊列p，對p中元素完成從粗調(diào)到細調(diào)的步驟，直到數(shù)據(jù)集中所有數(shù)據(jù)遍歷結(jié)束。最后把所有未標注節(jié)點歸于密度高于當(dāng)前點的最近一類，完成所有節(jié)點標注。非中心點的分配的算法的偽代碼描述如下。

算法1非中心點分配偽代碼

輸入：數(shù)據(jù)中心點集合C{c1,c2,…,cm},k，距離矩陣D。

2.3 SODPC算法整體描述和時間復(fù)雜度分析

原始DPC 算法在計算相對距離時，同時判斷節(jié)點的歸屬關(guān)系，本文算法把歸屬關(guān)系步驟放到算法的后期進行，在算法1 的基礎(chǔ)上，結(jié)合原始的密度峰值聚類算法，通過多步驟的分配方案對非中心節(jié)點聚類。SODPC（optimized density peaks clustering algorithm based on second-orderkneighbors）算法的偽代碼如算法2 描述。

算法2SODPC 聚類算法

輸入：數(shù)據(jù)集X,近鄰數(shù)k，比例系數(shù)α。

輸出：聚類結(jié)果C′{C1,C2,…,Cm}。

1.初始化數(shù)據(jù)集X={x1,x2,…,xn}。

2.對X中每個節(jié)點分別利用式（7）和式（8）計算直接密度和間接密度，在此基礎(chǔ)上利用式（9）計算局部密度ρi，利用式（3）計算相對距離δi。

3.根據(jù)γi=ρi×δi計算決策圖，定義γi大值作為聚類中心，所選中心集合構(gòu)成C{c1,c2,…,cm}。

4.調(diào)用算法1 完成非中心分配。

5.把所有未標注節(jié)點歸于密度高于當(dāng)前點的最近一類，完成所有節(jié)點標注。

6.輸出數(shù)據(jù)劃分結(jié)果。

SODPC 算法幾個主要部分的時間復(fù)雜度如下：（1）算法2 計算每個數(shù)據(jù)點之間的距離矩陣需要O(n2)，排序需要O(n2)時間復(fù)雜度。這部分開銷與原始DPC 是相同的。（2）算法1 中局部密度的計算，需要搜索k近鄰和二階k近鄰,需要遍歷節(jié)點隊列p的時間為O(n)，每個節(jié)點需要在二階k近鄰內(nèi)比較距離和分配，總時間復(fù)雜度為O(2kn2)。原始DPC 是在密度排序的基礎(chǔ)上，邊計算距離，邊分配節(jié)點，總復(fù)雜度是O(n2)。（3）剩下節(jié)點的歸屬操作總時間復(fù)雜度為O(n) 。由上述分析看出SODPC 總時間復(fù)雜度為O(2kn2)，而原始DPC 算法的時間復(fù)雜度為O(n2)。由于實驗中采用的節(jié)點的近鄰數(shù)k都在個位，而n是數(shù)據(jù)集節(jié)點個數(shù)，k?n,在實際的數(shù)據(jù)集上運行并沒有非常明顯的時間差距。

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

3.1 實驗數(shù)據(jù)集與評價指標

實驗選擇6 個人工合成數(shù)據(jù)集和6 個來自UCI上的真實數(shù)據(jù)集進行實驗，數(shù)據(jù)集的具體屬性分別如表1 和表2 所示。

Table 1 Artificial data sets表1 人工數(shù)據(jù)集

Table 2 UCI data sets表2 UCI數(shù)據(jù)集

在所有基準數(shù)據(jù)集上比較聚類算法的ACC（accuracy）、NMI（normalized mutual information）和F-M（F-measure）的相應(yīng)參數(shù)和實驗結(jié)果。評價指標值越大，聚類結(jié)果的質(zhì)量越好。聚類精度ACC 代表正確的聚類樣本數(shù)與總樣本數(shù)之比，表示聚類結(jié)果的質(zhì)量。F-M 度量是精度和召回率的加權(quán)諧波均值，它表示聚類解決方案與數(shù)據(jù)集的真實分類標簽之間的匹配程度。NMI 量化了聚類結(jié)果和已知類別標簽之間的匹配程度，從而衡量了聚類算法的魯棒性。

3.2 算法實驗結(jié)果分析

分別在上述數(shù)據(jù)集上選擇DPC、SNNDPC、LDPC和本文的SODPC 進行比較。SNNDPC 基于k近鄰思想，同時考慮更新局部密度和分配策略，LDPC 把數(shù)據(jù)集轉(zhuǎn)化為有向圖，利用圖論知識，對局部密度重新定義。根據(jù)相應(yīng)原文中對算法的描述信息，相關(guān)參數(shù)分別設(shè)置為：原始DPC 參數(shù)設(shè)置為2.0 到3.8 取值；SNNDPC算法的k值從3到10手動取值，重復(fù)實驗。

根據(jù)實驗結(jié)果有如下結(jié)論:針對fourlines 和Gauss_data 數(shù)據(jù)集，數(shù)據(jù)的分布密度均勻，數(shù)據(jù)分布規(guī)則且簡單，從圖4 和圖5 可以看出除了DPC 算法，本文算法和其他兩種算法都有比較好的識別結(jié)果。針對multiscale 數(shù)據(jù)集，從圖6 上可以看出，本文算法、LDPC 有正確的結(jié)果，但是原始的DPC 利用統(tǒng)一的截斷距離，且采用單一的分配原則，不能對密度不均勻和不規(guī)則數(shù)據(jù)集識別。另外，雖然LDPC 能夠給出正確的識別，但是從算法的執(zhí)行效率上來看，在本文的人工小數(shù)據(jù)規(guī)模上，平均執(zhí)行時間都在1 s 以上，算法復(fù)雜度高于其他所有對比算法，因此并不適合大規(guī)模聚類識別。從圖6 上看出，DPC 算法未能給出multiscale 數(shù)據(jù)集較好的識別結(jié)果。圖7 和圖8 分別給出了算法針對數(shù)據(jù)集twocircles 和twomoons 的識別情況，可以看出本文算法和SNNDPC（twocircles 和twomoons 數(shù)據(jù)集上k值分別為3 和7 時為最佳結(jié)果）能夠做出正確識別，而LDPC 以及DCP 算法未能給出較好的聚類，針對twocircles 和twomoons 這種不規(guī)則的數(shù)據(jù)，識別情況不盡如人意。最后從圖9 上看出，本文和LDPC 能夠?qū)wospirals 數(shù)據(jù)做出正確識別，而其他兩種算法未能給出正確結(jié)果。從上述分析看出，本文算法考慮到從密度和分配策略兩個角度同時改進，能夠在各種形狀不規(guī)則、不均勻的數(shù)據(jù)集上有比較好的識別結(jié)果，而且本文算法相比原始的DPC 算法有更好的魯棒性。進一步通過具體指標做分析，需要手動調(diào)試，多次運行，計算并統(tǒng)計ACC、NMI 和F-M 指標和平均執(zhí)行時間，利用所有結(jié)果的平均值表示最終結(jié)果，如表3 和表4 所示。

Fig.4 Renderings of fourlines data set圖4 fourlines數(shù)據(jù)集的效果圖

Fig.5 Renderings of Gauss_data data set圖5 Gauss_data 數(shù)據(jù)集的效果圖

Fig.6 Renderings of multiscale data set圖6 multiscale數(shù)據(jù)集的效果圖

Fig.7 Renderings of twomoons data set圖7 twomoons數(shù)據(jù)集的效果圖

Fig.8 Renderings of twocircles data set圖8 twocircles數(shù)據(jù)集的效果圖

Fig.9 Renderings of twospirals data set圖9 twospirals數(shù)據(jù)集的效果圖

Table 3 Performance on synthetic data set表3 人工數(shù)據(jù)集上的性能表現(xiàn)

Table 4 Performance on UCI data set表4 UCI數(shù)據(jù)集上的性能表現(xiàn)

從表3 和表4 的結(jié)果可以看出，算法在人工數(shù)據(jù)和實際數(shù)據(jù)上的運行結(jié)果和執(zhí)行時間大體是吻合的，LDPC 在人工和實際數(shù)據(jù)上運行時間最慢。在Sonar和Segmentation 數(shù)據(jù)集上，在整體表現(xiàn)都欠佳情況下，SODPC 算法仍然能夠給出比較理想的結(jié)果。在人工數(shù)據(jù)集twospirals 和實際數(shù)據(jù)集Pen-Based 上，在各個性能上的表現(xiàn)都是最好的，可以看出算法能夠適應(yīng)復(fù)雜的數(shù)據(jù)分布和多屬性大數(shù)據(jù)量情況下的聚類任務(wù)。整體來看，SODPC 在不同數(shù)據(jù)集上的運行能夠保持在一個比較理想的性能表現(xiàn)。為了測試本文算法對于k值的敏感性，本文算法k值分別從3 取到7，DPC 的截斷參數(shù)從2.0%到4.0%，測試并對比兩算法在相同數(shù)據(jù)集Iris上的聚類準確度。

從表5 可以看出，本文算法在Iris 上的平均準確率達到0.94 左右，而且不同的k值對算法的影響較小，算法結(jié)果的波動不大，具備較好的魯棒性。

4 結(jié)束語

本文提出了一種基于節(jié)點二階k近鄰的密度峰值聚類算法，引入節(jié)點的二階k近鄰，計算直接密度和間接密度，并重新定義局部密度的計算方式。在此基礎(chǔ)上，定義非中心節(jié)點的分配策略。算法利用統(tǒng)一的度量值，避免了參數(shù)的選擇問題，提高了算法的魯棒性，二階k近鄰的計算同時考慮了節(jié)點近鄰的數(shù)量和近鄰之間的關(guān)系，提高了算法的精度，從理論和實驗上證明了本文算法在同類算法中有較好的表現(xiàn)。下一步工作需要研究針對各種空間下復(fù)雜形狀數(shù)據(jù)集聚類，以及探索如何保證算法有效性的情況下讓算法的復(fù)雜度進一步降低，以便用于在大數(shù)據(jù)環(huán)境下的實際應(yīng)用場合。

Table 5 Clustering accuracy of algorithms withdifferent parameters on Iris data set表5 不同參數(shù)的算法在Iris數(shù)據(jù)集上的聚類準確度