丁志成，葛洪偉+

1.江南大學(xué) 江蘇省模式識(shí)別與計(jì)算智能工程實(shí)驗(yàn)室，江蘇 無(wú)錫 214122

2.江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無(wú)錫 214122

1 引言

聚類(lèi)作為一種無(wú)監(jiān)督的學(xué)習(xí)方法，是數(shù)據(jù)挖掘的重要分支，它通過(guò)將對(duì)象的屬性按照某種特定的標(biāo)準(zhǔn)進(jìn)行相似性劃分從而將數(shù)據(jù)集分割為若干不同的簇類(lèi)，最大化相同簇類(lèi)內(nèi)的數(shù)據(jù)屬性相似度，并最小化不同簇類(lèi)間的數(shù)據(jù)屬性相似度[1]。在信息全球化的背景下，對(duì)于挖掘潛在、有價(jià)值數(shù)據(jù)的要求與日俱增，因此聚類(lèi)在航天航空、市場(chǎng)分析、信息安全、人工智能、Web搜索等領(lǐng)域[2-3]得到了深入的研究與推廣。

由于聚類(lèi)分析有著極強(qiáng)的實(shí)用性與延展性，經(jīng)過(guò)學(xué)者們的多年研究和努力，眾多優(yōu)越的相關(guān)算法被相繼提出，其中較為經(jīng)典的算法有：基于劃分的Kmeans[4]、K-medoids[5]算法；基于網(wǎng)格的STING（statistical information grid）[6]、CLIQUE（clustering in quest）和WaveCluster[7]算法；基于層次的CURE（clustering using representatives）[8]、Chameleon[9]等聚類(lèi)算法；基于密度的DBSCAN（density-based spatial clustering of applications with noise）[10]、OPTICS（ordering points to identify the clustering structure）[11]算法。

Rodriguez、Laio 于2014 年在權(quán)威期刊Science中發(fā)表了一篇關(guān)于新型的基于密度的聚類(lèi)算法論文：快速搜索與發(fā)現(xiàn)密度峰值聚類(lèi)（clustering by fast search and find of density peaks，DPC）[12]算法。DPC 算法的關(guān)鍵點(diǎn)在于：利用決策圖手動(dòng)選擇密度峰值作為所需要的聚類(lèi)中心點(diǎn)，隨即將剩余點(diǎn)分配給與之距離最近的聚類(lèi)中心點(diǎn)所屬類(lèi)簇，最后對(duì)分配結(jié)果進(jìn)行噪聲識(shí)別從而完成聚類(lèi)。與大部分經(jīng)典的基于密度的算法相比，該算法簡(jiǎn)潔高效，無(wú)需迭代，只需一個(gè)截?cái)嗑嚯x參數(shù)dc，能夠發(fā)現(xiàn)數(shù)據(jù)集中所有任意形狀的簇類(lèi)并且可以有效消除離群點(diǎn)。盡管如此，DPC算法依然容易在分配復(fù)雜結(jié)構(gòu)數(shù)據(jù)集數(shù)據(jù)點(diǎn)時(shí)出現(xiàn)錯(cuò)誤，導(dǎo)致聚類(lèi)效果不理想。

針對(duì)DPC 算法存在的缺陷，Xu 等人提出了基于γ線性擬合的DenPEHC（density peak based efficient hierarchical clustering）密度峰值聚類(lèi)算法[13]，利用γ排序圖的變化趨勢(shì)產(chǎn)生了自適應(yīng)的聚類(lèi)中心并改進(jìn)了聚類(lèi)分配機(jī)制，但在高維數(shù)據(jù)處理上容易出現(xiàn)錯(cuò)誤聚類(lèi)。Xu 等人提出了分別基于網(wǎng)格劃分和圓劃分的密度峰值聚類(lèi)算法GDPC（density peaks clustering algorithm with gird-division strategy）和CDPC（density peaks clustering algorithm with circle-division strategy）算法[14]，兩者都優(yōu)化了密度峰值的聚類(lèi)分配。GDPC算法耗時(shí)更少而CPDC 算法在大型數(shù)據(jù)集上具有更高的準(zhǔn)確率，但在處理復(fù)雜結(jié)構(gòu)數(shù)據(jù)集時(shí)會(huì)出現(xiàn)分配錯(cuò)誤的情況。金輝等人提出了自然最近鄰優(yōu)化的

TNDP（optimized density peak clustering algorithm by natural nearest neighbor）算法[15]，利用自然鄰居概念計(jì)算數(shù)據(jù)點(diǎn)的局部密度，再使用類(lèi)簇間相似度合并簇類(lèi)，算法雖然有較優(yōu)的聚類(lèi)效果，但無(wú)法很好地識(shí)別數(shù)據(jù)集噪聲。

因此，本文針對(duì)以上算法的缺陷，提出一種優(yōu)化分配策略的密度峰值聚類(lèi)算法（density peaks clustering with optimized allocation strategy，ODPC）。新算法利用相似度指標(biāo)MS分配對(duì)象數(shù)據(jù)集的數(shù)據(jù)點(diǎn)，然后通過(guò)dc近鄰法重新界定邊界區(qū)域中的噪聲點(diǎn)。實(shí)驗(yàn)證明，在數(shù)據(jù)集對(duì)象存在高維數(shù)據(jù)、復(fù)雜數(shù)據(jù)結(jié)構(gòu)、噪聲數(shù)據(jù)的情況下，新算法可以得到更優(yōu)的聚類(lèi)結(jié)果。

2 DPC 算法及其缺陷

DPC 算法將符合以下特征的數(shù)據(jù)點(diǎn)對(duì)象定義為密度峰值點(diǎn)即聚類(lèi)中心：被擁有相對(duì)較低局部密度的鄰居點(diǎn)所環(huán)繞并且此類(lèi)數(shù)據(jù)點(diǎn)和其余擁有相對(duì)較高密度的數(shù)據(jù)點(diǎn)間有較大的距離。算法僅需要截?cái)嗑嚯xdc這一個(gè)輸入?yún)?shù)，通過(guò)人工選取聚類(lèi)中心點(diǎn)，一步完成所有數(shù)據(jù)點(diǎn)的聚類(lèi)與分配。

對(duì)于任意數(shù)據(jù)點(diǎn)Xi，DPC 只需要計(jì)算其局部密度ρi以及距離具有更大密度的點(diǎn)的最短距離δi這兩個(gè)變量。

局部密度ρi為以dc為半徑的范圍內(nèi)其余數(shù)據(jù)點(diǎn)的數(shù)量：

式（2）中，di為所有點(diǎn)間的歐式距離的升序排列；N為數(shù)據(jù)總量；M=N(N-1)/2；round函數(shù)表示對(duì)M×P/100 四舍五入取整；P為可調(diào)參數(shù)，DPC 原文中選取P值為2。

δi為距離具有更大密度的點(diǎn)的最短距離：

式（3）中，對(duì)于數(shù)據(jù)集最高密度的數(shù)據(jù)點(diǎn)K，默認(rèn)它為數(shù)據(jù)集的聚類(lèi)中心點(diǎn)并令其δk為所有距離中的最大值，即δk=max(dij)。

在得到數(shù)據(jù)點(diǎn)的ρi和δi值后，DPC 算法首先生成相應(yīng)的決策圖并將同時(shí)具有較大ρ和δ值的點(diǎn)視作聚類(lèi)中心，然后將非聚類(lèi)中心點(diǎn)依次分配給最接近的聚類(lèi)中心點(diǎn)所在簇，最后對(duì)聚類(lèi)結(jié)果進(jìn)行噪聲識(shí)別，完成聚類(lèi)。DPC 算法為識(shí)別出聚類(lèi)結(jié)果中的噪聲點(diǎn)，引入邊界區(qū)域密度ρb的概念：在某簇內(nèi)卻與屬于其余簇的點(diǎn)距離小于截?cái)嗑嚯xdc的數(shù)據(jù)點(diǎn)中局部密度最大值。而在簇中局部密度ρi大于邊界區(qū)域密度ρb的數(shù)據(jù)點(diǎn)被認(rèn)為此簇的核心點(diǎn)，反之則視為該簇的噪聲點(diǎn)。

盡管DPC可以快速高效地完成聚類(lèi)，但是算法仍存在一些缺陷：只有當(dāng)數(shù)據(jù)點(diǎn)的ρ和δ值同時(shí)大的情況下，該數(shù)據(jù)點(diǎn)才有可能被選為聚類(lèi)中心點(diǎn)；對(duì)于復(fù)雜結(jié)構(gòu)的數(shù)據(jù)集來(lái)說(shuō)，僅僅通過(guò)將數(shù)據(jù)點(diǎn)分配給距離最近的聚類(lèi)中心點(diǎn)所屬簇類(lèi)容易出現(xiàn)錯(cuò)誤的聚類(lèi)結(jié)果；在噪聲識(shí)別階段，直接通過(guò)邊界區(qū)域密度對(duì)核心點(diǎn)及噪聲點(diǎn)進(jìn)行一次性的劃分也并不是較優(yōu)的方法。

綜上所述，DPC 算法在面對(duì)以下三種情況時(shí)仍然會(huì)出現(xiàn)較大的誤差：

（1）由于DPC 算法分別單獨(dú)考察ρ和δ的大小，僅當(dāng)數(shù)據(jù)點(diǎn)在兩值上均大于所選點(diǎn)時(shí)才會(huì)被確定為聚類(lèi)中心點(diǎn)，而事實(shí)上仍存在部分ρ大δ小或者是ρ小δ大的數(shù)據(jù)點(diǎn)也為實(shí)際聚類(lèi)中心。如圖1 所示，DPC 算法僅識(shí)別到兩個(gè)團(tuán)狀簇的聚類(lèi)中心而沒(méi)有發(fā)現(xiàn)環(huán)形簇的聚類(lèi)中心。因此會(huì)導(dǎo)致數(shù)據(jù)集聚類(lèi)中心點(diǎn)的少選、漏選。

Fig.1 DPC gets less clusters by decision graph圖1 DPC 算法通過(guò)決策圖少選聚類(lèi)中心

（2）當(dāng)DPC 算法處理如流形數(shù)據(jù)集等具有復(fù)雜數(shù)據(jù)結(jié)構(gòu)的對(duì)象時(shí)，會(huì)因?yàn)橹豢紤]局部密度而無(wú)視整體結(jié)構(gòu)一致性以及數(shù)據(jù)點(diǎn)間的連通性而導(dǎo)致在分配數(shù)據(jù)點(diǎn)所屬類(lèi)簇時(shí)產(chǎn)生相應(yīng)的錯(cuò)誤。如圖2 所示，很明顯，區(qū)域C和區(qū)域D的數(shù)據(jù)點(diǎn)應(yīng)該歸屬于聚類(lèi)中心點(diǎn)a所屬類(lèi)簇A類(lèi)。而在DPC 算法中，由于C區(qū)域與D區(qū)域中的點(diǎn)距離B類(lèi)聚類(lèi)中心點(diǎn)b的距離比a更近因此都被分配到B類(lèi)中，因此出現(xiàn)了如圖2（b）的錯(cuò)誤聚類(lèi)。

（3）DPC 算法依據(jù)邊界區(qū)域密度ρb的定義對(duì)數(shù)據(jù)集劃分，從而實(shí)現(xiàn)聚類(lèi)結(jié)果的噪聲識(shí)別。算法會(huì)在噪聲點(diǎn)較為密集、局部密度ρ較大的情況下將其錯(cuò)誤地歸類(lèi)為核心點(diǎn)或是在核心點(diǎn)較為稀疏、ρ值較小時(shí)將核心點(diǎn)錯(cuò)誤地識(shí)別為噪聲點(diǎn)。如圖3 所示，大量的核心點(diǎn)因此被錯(cuò)誤地識(shí)別為噪聲點(diǎn)。

3 優(yōu)化分配策略的密度峰值聚類(lèi)算法

3.1 優(yōu)化的分配策略

定義1令γi作為判斷點(diǎn)i是否為密度峰值點(diǎn)，即聚類(lèi)中心點(diǎn)的參數(shù)指標(biāo)：

Fig.2 Wrong clustering results caused by allocation strategy of DPC圖2 DPC 分配策略導(dǎo)致的錯(cuò)誤的聚類(lèi)結(jié)果

Fig.3 Bad denoising result caused by DPC圖3 DPC 導(dǎo)致的不佳的去噪結(jié)果

對(duì)于擁有相對(duì)較大ρ或δ值的聚類(lèi)中心來(lái)說(shuō)，γ值同樣也會(huì)取得較大值，因此γ值具有判斷數(shù)據(jù)點(diǎn)能否為聚類(lèi)中心的作用。記對(duì)象數(shù)據(jù)集為U(x)，樣本數(shù)據(jù)點(diǎn)總量為N，對(duì)所有數(shù)據(jù)點(diǎn)進(jìn)行關(guān)于γ的降序排列γdes。在決策圖上，將數(shù)據(jù)點(diǎn)的參數(shù)積γi大于被選點(diǎn)γ值的點(diǎn)視作聚類(lèi)中心。

定義2令MS為衡量數(shù)據(jù)點(diǎn)間相似度的參數(shù)指標(biāo)，稱為相似度指標(biāo)，其公式為：

本文借鑒牛頓萬(wàn)有引力定律[16]對(duì)數(shù)據(jù)點(diǎn)進(jìn)行基于相似度的局部連通性分配。萬(wàn)有引力公式為F=，公式中M和m表示兩個(gè)差異個(gè)體的各自質(zhì)量，G為萬(wàn)有引力常量，r為個(gè)體間的距離，反映的是存在于力場(chǎng)中的任意兩個(gè)不同個(gè)體間都存在著互相吸引的力，這個(gè)力與它們的質(zhì)量成正比而和它們間距離的平方成反比，其本質(zhì)是物體將力通過(guò)空間向四周傳遞，距離越長(zhǎng)則傳遞的力越小。

參照自然界中物體間的吸引力作用，將之引申到數(shù)據(jù)結(jié)構(gòu)空間中，可以發(fā)現(xiàn)數(shù)據(jù)空間中也有類(lèi)似“場(chǎng)”的存在，其表現(xiàn)為：數(shù)據(jù)集中距離越近，密度越大，局部密度越相似的兩點(diǎn)，其相互作用力越大，同樣其相似度也越高。因此本文利用萬(wàn)有引力公式的變式來(lái)描述數(shù)據(jù)點(diǎn)間的相似度，式（5）中的G為相似度參數(shù)，ρi、ρj分別為數(shù)據(jù)集中任意兩點(diǎn)的局部密度，而dist(i,j)則表示任意兩點(diǎn)間的歐式距離。

在數(shù)據(jù)空間中，數(shù)據(jù)點(diǎn)默認(rèn)體積一致，將其視作單位1，則質(zhì)量M、m分別轉(zhuǎn)化為局部密度ρi、ρj。由路網(wǎng)模型及其應(yīng)用[17]可知，數(shù)據(jù)點(diǎn)所處區(qū)域的局部密度密切影響著點(diǎn)間相似度，并且在兩點(diǎn)的局部密度越接近時(shí)，其相似度也越高，因此使用相似度參數(shù)G用以表示空間數(shù)據(jù)集的局部連通性。公式G=中，|ρi-ρj|用以表示不同數(shù)據(jù)點(diǎn)的局部密度差異，與其對(duì)應(yīng)的相似度成反比，因此對(duì)公式的指數(shù)取反；引入ρmax-ρmin并使用e為底的指數(shù)函數(shù)以限制G的取值范圍，因此式（6）最終為取值在[1/e,1]區(qū)間的相似度參數(shù)，其參數(shù)值與點(diǎn)間相似度成正比。相似度指標(biāo)也最終根據(jù)萬(wàn)有引力公式變式為式（5）。

Fig.4 Clustering results caused by different allocation strategies of algorithms圖4 不同的算法分配策略導(dǎo)致的聚類(lèi)結(jié)果

DPC 算法中，利用數(shù)據(jù)局部密度ρi和該點(diǎn)到具有更大局部密度的點(diǎn)的最短距離δi兩值確定聚類(lèi)中心點(diǎn)后，直接依照距離簇中心的距離，將數(shù)據(jù)點(diǎn)歸類(lèi)為最接近的聚類(lèi)中心點(diǎn)所屬簇。而ODPC 算法使用優(yōu)化的分配策略如下：首先通過(guò)式（4）計(jì)算所有點(diǎn)的γi值，將參數(shù)積γi大于選中點(diǎn)γ值的點(diǎn)作為聚類(lèi)中心點(diǎn)；然后按照降序排列γdes的順序，依次將γ值漸小的點(diǎn)分配給在已被分配簇類(lèi)的數(shù)據(jù)點(diǎn)中，與其相似度最大的點(diǎn)所在的類(lèi)簇，完成聚類(lèi)。

以數(shù)據(jù)集Compound 為例，如圖4（a）所示的DPC算法在數(shù)據(jù)集Compound 上的聚類(lèi)結(jié)果，點(diǎn)1 和點(diǎn)2分別為兩簇的聚類(lèi)中心點(diǎn)，DPC 算法通過(guò)最近聚類(lèi)中心點(diǎn)分配的方法將點(diǎn)3 與點(diǎn)2 錯(cuò)誤地歸于同一類(lèi)。而在新算法ODPC 中，如圖4（b）所示，點(diǎn)4 在已被分配類(lèi)簇的數(shù)據(jù)點(diǎn)集合中與點(diǎn)1 的相似度指標(biāo)MS值最大，因此兩點(diǎn)被分為同一類(lèi)。同理，點(diǎn)5 與點(diǎn)4，點(diǎn)6 與點(diǎn)5，點(diǎn)7 與點(diǎn)6，點(diǎn)8 與點(diǎn)7，點(diǎn)9 與點(diǎn)8，點(diǎn)10與點(diǎn)9，直到點(diǎn)3 與點(diǎn)10 都通過(guò)相似度指標(biāo)MS歸為同一類(lèi)，因而點(diǎn)1 與點(diǎn)3 屬于一類(lèi)。依此類(lèi)推，整個(gè)環(huán)狀流形區(qū)域均被劃分為一類(lèi)，而中間的團(tuán)狀簇則被劃分為另一類(lèi)，因此ODPC 算法得到如圖4（b）所示的正確聚類(lèi)效果圖。

3.2 優(yōu)化識(shí)別噪聲點(diǎn)

DPC 算法中，使用邊界區(qū)域密度的概念對(duì)所有數(shù)據(jù)點(diǎn)進(jìn)行統(tǒng)一識(shí)別，大于邊界區(qū)域密度的點(diǎn)定義為核心點(diǎn)，反之則視作噪聲點(diǎn)。這一策略容易導(dǎo)致分布較為稀疏的核心點(diǎn)或是分布較為稠密的噪聲點(diǎn)被錯(cuò)誤識(shí)別，如圖5（a）所示，大量的核心點(diǎn)被錯(cuò)誤識(shí)別從而降低了算法的魯棒性。

分布較為稀疏的核心點(diǎn)與分布較為稠密的噪聲點(diǎn)多出現(xiàn)于簇類(lèi)的邊緣區(qū)域，而這塊區(qū)域與DPC 定義的邊界區(qū)域極為相似。因此為了更好地識(shí)別數(shù)據(jù)集的噪聲點(diǎn)與核心點(diǎn)，新算法對(duì)邊界區(qū)域的數(shù)據(jù)點(diǎn)進(jìn)行二次識(shí)別，有助于從健壯性角度提升ODPC 算法的聚類(lèi)質(zhì)量。由于初次識(shí)別后所有數(shù)據(jù)點(diǎn)都已經(jīng)被劃分為相應(yīng)的核心點(diǎn)或是噪聲點(diǎn)，本文參照K近鄰算法[18]，使用新的dc近鄰法優(yōu)化噪聲識(shí)別。

Fig.5 Effect of different noise recognition methods圖5 不同噪聲識(shí)別方法的效果

定義3（dc近鄰法）對(duì)以邊界區(qū)域數(shù)據(jù)點(diǎn)i為核心，dc為半徑的區(qū)域進(jìn)行考察，若范圍內(nèi)噪聲點(diǎn)更多則識(shí)別該點(diǎn)為噪聲點(diǎn)，反之則識(shí)別為核心點(diǎn)。

根據(jù)DPC 中局部密度ρi的定義，本文通過(guò)dc近鄰法引入邊界區(qū)域噪聲密度ρi′的概念，對(duì)邊界區(qū)域的數(shù)據(jù)點(diǎn)重新識(shí)別噪聲。

定義4定義邊界區(qū)域i點(diǎn)的區(qū)域噪聲密度ρi′為，以i點(diǎn)為核心，dc為半徑的區(qū)域內(nèi)噪聲點(diǎn)比核心點(diǎn)多的數(shù)量，其計(jì)算公式為：

其中，對(duì)象數(shù)據(jù)集為U(x)，噪聲點(diǎn)集合為Ni，核心點(diǎn)集合為Co，j∈U(x)。對(duì)邊界區(qū)域的數(shù)據(jù)點(diǎn)按照γ值降序排列的順序進(jìn)行重新分配，若ρi′≥0，i點(diǎn)的dc近鄰中噪聲點(diǎn)較多，將其劃分到噪聲點(diǎn)集合Ni中；若ρi′＜0，則其dc近鄰中有更多核心點(diǎn)，因此將i點(diǎn)劃分到核心點(diǎn)集合Co中。將識(shí)別過(guò)程中未改變所屬集合的點(diǎn)的集合作為新的邊界區(qū)域，遞歸該識(shí)別過(guò)程直到邊界區(qū)域不再發(fā)生變化，至此完成對(duì)邊界區(qū)域所有數(shù)據(jù)點(diǎn)的噪聲識(shí)別。以圖5（b）中數(shù)據(jù)集Flame 的聚類(lèi)效果為例，經(jīng)過(guò)ODPC 的dc近鄰法對(duì)邊界區(qū)域噪聲點(diǎn)的重新識(shí)別，流形簇和團(tuán)狀簇中均有更多分布較為稀疏的核心點(diǎn)被正確識(shí)別。不同于DPC 算法將噪聲識(shí)別與算法聚類(lèi)效果割裂開(kāi)，ODPC 算法則是將數(shù)據(jù)對(duì)象中的噪聲去除后再進(jìn)行聚類(lèi)效果分析，消除了數(shù)據(jù)集噪聲點(diǎn)對(duì)聚類(lèi)效果的負(fù)面影響，因此新算法在Flame 數(shù)據(jù)集上的兩個(gè)聚類(lèi)評(píng)價(jià)指標(biāo)均為1，得到了完全正確的聚類(lèi)結(jié)果。實(shí)驗(yàn)證明優(yōu)化的噪聲識(shí)別有著更好的準(zhǔn)確性和抗干擾性。

3.3 算法步驟分析

輸入：實(shí)驗(yàn)數(shù)據(jù)集U(x)={x1,x2,…,xn}，數(shù)據(jù)點(diǎn)的鄰居點(diǎn)數(shù)目占數(shù)據(jù)總數(shù)的比例P。

輸出：聚類(lèi)結(jié)果C={C1,C2,…,Ch}，h為總簇類(lèi)數(shù)量。

步驟1選取P值為2，根據(jù)式（2）計(jì)算出截?cái)嗑嚯xdc。

步驟2根據(jù)式（1）、式（3）分別計(jì)算數(shù)據(jù)集中所有點(diǎn)的局部密度ρi以及最短距離δi。

步驟3生成有關(guān)ρi和δi的決策圖，根據(jù)式（4）得到的γ值在決策圖上選取聚類(lèi)中心。

步驟4根據(jù)式（5）、式（6）引入相似度指標(biāo)MS，對(duì)關(guān)于γ的降序排列γdes中的非聚類(lèi)中心點(diǎn)，進(jìn)行依次分配：將未劃分簇類(lèi)的數(shù)據(jù)點(diǎn)分配到已歸類(lèi)并且相似度指標(biāo)MS最高的點(diǎn)所在簇。

步驟5根據(jù)式（7）計(jì)算數(shù)據(jù)集邊界區(qū)域點(diǎn)的邊界區(qū)域噪聲密度ρi′，若ρi′≥0，將i點(diǎn)識(shí)別為噪聲點(diǎn)；若ρi′＜0，則識(shí)別該點(diǎn)為核心點(diǎn)。

步驟6將識(shí)別過(guò)程中未改變所屬集合的點(diǎn)作為新的邊界區(qū)域，重復(fù)步驟5。

步驟7邊界區(qū)域不再發(fā)生變化，完成噪聲識(shí)別。

3.4 時(shí)間復(fù)雜度分析

假設(shè)聚類(lèi)實(shí)驗(yàn)的數(shù)據(jù)集共有n個(gè)數(shù)據(jù)，由第2 章DPC 算法及其缺陷的描述可知，DPC 算法的時(shí)間復(fù)雜度主要由計(jì)算歐式距離(O(n2))、對(duì)歐式距離降序排列(O(lbn2))、計(jì) 算ρ和δ(O(n2)) 和去噪處理(O(n)) 組成。因此，DPC 的時(shí)間復(fù)雜度為O(n2)。而DenPEHC算法相較于DPC 算法，不同點(diǎn)在于：對(duì)γ降序排列(O(nlbn))和改進(jìn)的分配機(jī)制(O(n2))，因此DenPEHC的時(shí)間復(fù)雜度為O(n2)。GDPC 算法的時(shí)間復(fù)雜度主要由網(wǎng)格化數(shù)據(jù)點(diǎn)(O(n))、快速排序移除稀疏網(wǎng)格(O(nlbn))、利用決策圖聚類(lèi)數(shù)據(jù)點(diǎn)(O(h2))、分配其余數(shù)據(jù)點(diǎn)至K個(gè)聚類(lèi)中心(O(k(n-h)))組成，其中h為經(jīng)過(guò)篩選的數(shù)據(jù)點(diǎn)(h＜n)，因此GDPC 算法的時(shí)間復(fù)雜度為O(n)+O(nlbn)+O(h2)+O(k(n-h))。而根據(jù)3.1節(jié)、3.2 節(jié)的描述，ODPC 相較于DPC 算法，不一樣的步驟在于優(yōu)化的分配策略(O(n2))和改進(jìn)的噪聲識(shí)別方法(O(n)+O(m2))，其中m為邊界區(qū)域數(shù)據(jù)點(diǎn)數(shù)量，數(shù)值遠(yuǎn)小于n。因此，ODPC 的算法時(shí)間復(fù)雜度與DPC 算法一致，也為O(n2)。

4 仿真實(shí)驗(yàn)與性能分析

為驗(yàn)證ODPC 算法的效果與性能，本文分別在人工數(shù)據(jù)集以及真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)分析。

4.1 人工數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果與分析

仿真實(shí)驗(yàn)中使用到四個(gè)人工數(shù)據(jù)集，相關(guān)信息見(jiàn)表1。分別運(yùn)行DPC 算法、ODPC 算法、同樣優(yōu)化分配機(jī)制的DenPEHC[13]和GDPC[14]算法，對(duì)表1 中數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖6～圖9 所示。

對(duì)于線狀簇的數(shù)據(jù)集Spiral，如圖6 所示，四種算法均能得到正確的聚類(lèi)結(jié)果。對(duì)于Aggregation 數(shù)據(jù)集，由圖7 可知，DenPEHC 算法利用γ線性擬合中出現(xiàn)的第一個(gè)異常增幅點(diǎn)，將數(shù)據(jù)集錯(cuò)誤地分為八類(lèi)；GDPC 將數(shù)據(jù)集錯(cuò)分為十類(lèi)；DPC 與ODPC 算法則可以得到正確的聚類(lèi)結(jié)果。而對(duì)于復(fù)雜數(shù)據(jù)集結(jié)構(gòu)的Compound 數(shù)據(jù)集，如圖8 所示，DenPEHC 與DPC 算法雖然得到了正確的六個(gè)聚類(lèi)中心點(diǎn)，卻在環(huán)形簇的分割上出現(xiàn)了錯(cuò)誤，將其分成了兩類(lèi)；GDPC 算法則錯(cuò)誤地將其分為七個(gè)類(lèi)簇；而ODPC 算法由于使用了基于相似度指標(biāo)MS的優(yōu)化分配策略，使得算法能夠在流形簇等復(fù)雜的數(shù)據(jù)集結(jié)構(gòu)中通過(guò)局部連通使得聚類(lèi)能夠反映數(shù)據(jù)集的全局一致性，從而得到正確的簇類(lèi)，并且提高了聚類(lèi)準(zhǔn)確度。在Flame 數(shù)據(jù)集上，DPC 算法則將流形簇兩端的區(qū)域錯(cuò)誤地分配給了團(tuán)狀簇，如圖9（a）所示；而DenPEHC 算法通過(guò)基于γ線性擬合，ODPC 算法通過(guò)對(duì)數(shù)據(jù)點(diǎn)進(jìn)行相似度連通分配，GDPC 算法通過(guò)對(duì)數(shù)據(jù)點(diǎn)的網(wǎng)格單元映射分別可以取得如圖9（b）～圖9（d）所示的正確聚類(lèi)效果。綜上所述，在人工數(shù)據(jù)集上，ODPC 算法較之DPC、DenPEHC 和GDPC 算法，可以提高密度峰值聚類(lèi)算法的準(zhǔn)確度，得到更優(yōu)的聚類(lèi)結(jié)果。

Table 1 Four synthetic data sets表1 四個(gè)人工數(shù)據(jù)集信息

Fig.6 Clustering results of Spiral by four algorithms圖6 四種算法在數(shù)據(jù)集Spiral上的聚類(lèi)結(jié)果

Fig.7 Clustering results of Aggregation by four algorithms圖7 四種算法在數(shù)據(jù)集Aggregation 上的聚類(lèi)結(jié)果

Fig.8 Clustering results of Compound by four algorithms圖8 四種算法在數(shù)據(jù)集Compound 上的聚類(lèi)結(jié)果

Fig.9 Clustering results of Flame by four algorithms圖9 四種算法在數(shù)據(jù)集Flame上的聚類(lèi)結(jié)果

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

為進(jìn)一步驗(yàn)證ODPC 算法的性能與效果，本文采用F-measure[19]與ARI[20]兩類(lèi)聚類(lèi)評(píng)價(jià)指標(biāo)并利用表2中的五個(gè)真實(shí)數(shù)據(jù)集對(duì)DPC算法、基于γ線性擬合的密度峰值算法DenPEHC、基于網(wǎng)格劃分優(yōu)化的密度峰值算法GDPC 和本文的ODPC 算法進(jìn)行對(duì)比實(shí)驗(yàn)。

Table 2 Five real data sets表2 五個(gè)真實(shí)數(shù)據(jù)集信息

兩類(lèi)評(píng)價(jià)指標(biāo)F-measure 的取值在0 到1 之間，而ARI 的取值范圍為-1 到1，在取值范圍內(nèi)評(píng)價(jià)指標(biāo)值越接近1 則表明聚類(lèi)效果越佳。實(shí)驗(yàn)結(jié)果如表3、表4 所示。

Table 3 F-measure index value of four algorithms on real data sets表3 四種算法在真實(shí)數(shù)據(jù)集上的F-measure值

Table 4 ARI index value of four algorithms on real data sets表4 四種算法在真實(shí)數(shù)據(jù)集上的ARI值

由表3、表4 的聚類(lèi)實(shí)驗(yàn)結(jié)果可知，在兩類(lèi)聚類(lèi)指標(biāo)值上，ODPC 算法在所有五個(gè)真實(shí)數(shù)據(jù)集上均能取得四種算法中的最大值。DPC、DenPEHC、GDPC 算法盡管在部分?jǐn)?shù)據(jù)集上的聚類(lèi)結(jié)果較好，但在面對(duì)具有復(fù)雜結(jié)構(gòu)的數(shù)據(jù)集時(shí)，數(shù)據(jù)點(diǎn)更容易被錯(cuò)誤分配，聚類(lèi)效果不如ODPC 算法。因此整體來(lái)看，ODPC 算法是其中最優(yōu)的算法。

綜上，ODPC 算法對(duì)DPC 算法進(jìn)行了成功的優(yōu)化改進(jìn)，在人工以及真實(shí)數(shù)據(jù)集上的仿真實(shí)驗(yàn)可以有效說(shuō)明算法能夠獲得更好的聚類(lèi)分配效果。

5 結(jié)束語(yǔ)

為了解決DPC 算法在面對(duì)復(fù)雜結(jié)構(gòu)數(shù)據(jù)集時(shí)容易出現(xiàn)分配錯(cuò)誤的問(wèn)題，本文提出了一種優(yōu)化分配策略的ODPC 算法。新算法參考萬(wàn)有引力公式，利用基于相似度指標(biāo)的MS值對(duì)數(shù)據(jù)集數(shù)據(jù)點(diǎn)進(jìn)行更加科學(xué)合理的連通性分配；使用dc近鄰法對(duì)邊界區(qū)域的數(shù)據(jù)點(diǎn)進(jìn)行優(yōu)化的噪聲識(shí)別。通過(guò)實(shí)驗(yàn)證明，新算法在保留原DPC 算法簡(jiǎn)單高效的同時(shí)，能夠獲得更好的聚類(lèi)分配和更優(yōu)的噪聲識(shí)別效果。

由于ODPC 算法沒(méi)有實(shí)現(xiàn)對(duì)聚類(lèi)中心的自動(dòng)選擇，在實(shí)際運(yùn)用時(shí)會(huì)造成額外的時(shí)間成本。但是算法引入γ擴(kuò)大了聚類(lèi)中心的范圍以避免漏選潛在的密度峰值點(diǎn)，通過(guò)算法的多次運(yùn)行來(lái)確保聚類(lèi)中心選取的正確性和有效性。盡管如此，在實(shí)際應(yīng)用時(shí)辨別數(shù)據(jù)對(duì)象是否被正確劃分依然會(huì)受到人為判斷和經(jīng)驗(yàn)值的影響。因此，如何使ODPC 算法在保證準(zhǔn)確率的同時(shí)自動(dòng)選取聚類(lèi)中心，將會(huì)是下一步的研究方向。