趙嘉 ,陳磊 ,吳潤(rùn)秀 ,張波 ,韓龍哲

(1.南昌工程學(xué)院信息工程學(xué)院,江西南昌 330099;2.全球能源互聯(lián)網(wǎng)研究院有限公司,江蘇南京 210003)

1 引言

聚類是數(shù)據(jù)挖掘和模式識(shí)別領(lǐng)域的熱門話題,它是一種無(wú)監(jiān)督學(xué)習(xí),能夠?qū)?shù)據(jù)按照一定規(guī)則劃分為類簇,使得同一類簇樣本是相似的,且與其他類簇的樣本不相似.目前,聚類分析已在不同的學(xué)科領(lǐng)域得到廣泛應(yīng)用,如模式識(shí)別[1]、圖像分析[2]、網(wǎng)絡(luò)安全[3]和生物信息[4]等.近年來(lái),人們從不同角度提出了許多聚類算法,主要包括基于劃分的聚類算法、基于模型的聚類算法、基于層次的聚類算法和基于密度的聚類算法等.

基于劃分的聚類算法將給定的數(shù)據(jù)集劃分為多個(gè)類簇,建立基于劃分規(guī)則的目標(biāo)函數(shù),并迭代尋優(yōu).雖然該方法簡(jiǎn)單有效,但它的聚類結(jié)果受噪聲點(diǎn)的影響,且在非球形數(shù)據(jù)集上的聚類效果不佳.K-means算法[5]是最常用的基于劃分的聚類算法.基于模型的聚類算法假設(shè)一個(gè)聚類的實(shí)例最可能來(lái)自于一個(gè)特別的概率模型,一般采用固定數(shù)量的模型來(lái)近似物體的分布.然而,這類算法在聚類之前,通常很難了解模型或描述數(shù)據(jù)分布.EM(expectation-maximization)算法[6]是這類算法的典型代表.基于層次的聚類算法通過自下而上或自上而下的方式遞歸地對(duì)數(shù)據(jù)進(jìn)行分類來(lái)構(gòu)建類簇,可以用樹狀圖來(lái)表示.然而,層次聚類方法的聚類復(fù)雜度高、魯棒性差,數(shù)據(jù)集小的改變就會(huì)導(dǎo)致層次樹狀圖結(jié)構(gòu)的較大變化.Chameleon算法[7]是一種典型的基于層次的聚類算法.基于密度的聚類算法旨在識(shí)別由較低密度區(qū)域分隔出的稠密區(qū)域,這些方法可以在特征空間中識(shí)別任意形狀的非球形類簇.DBSCAN(density based spatial clustering of applications with noise)[8]和OPTICS(ordering points to identify the clustering structure)[9]是兩個(gè)著名的基于密度的聚類算法.這些方法可以在特征空間識(shí)別出任意形狀的非球形類簇,不需要對(duì)數(shù)據(jù)的分布做任何假設(shè)就可以估計(jì)類簇的密度.但是,它們對(duì)參數(shù)非常敏感,參數(shù)值的很小變化,會(huì)產(chǎn)生完全不同的聚類結(jié)果.

本文研究的是一種基于密度的聚類算法,即快速搜索和尋找密度峰值聚類算法[10],簡(jiǎn)稱密度峰值聚類(density peaks clustering,DPC)算法.DPC算法由Rod-riguez和Laio于2014年在Science上提出,它通過樣本的局部密度和相對(duì)距離確定類簇中心,然后將剩余樣本分配給密度比它高且距離它最近的類簇.

流形數(shù)據(jù)通常由一些包含條狀和環(huán)狀類簇的數(shù)據(jù)組成,密度分布不均數(shù)據(jù)由類簇間疏密程度不一的數(shù)據(jù)組成.流形及密度分布不均數(shù)據(jù)廣泛存在于人們的生產(chǎn)活動(dòng)中,如圖像分割、手寫數(shù)字識(shí)別和web分析等[11].DPC算法利用樣本的局部密度以及相對(duì)距離快速確定密度峰值,可以聚出任意形狀類簇[12],但DPC算法仍然存在以下不足:1)在聚類密度分布不均數(shù)據(jù)時(shí),算法的局部密度未考慮類簇間的樣本疏密程度差異,易在密集類簇中尋找到多個(gè)密度峰值,而稀疏類簇中無(wú)密度峰值;2)DPC算法的分配策略依據(jù)歐氏距離通過密度峰值進(jìn)行鏈?zhǔn)椒峙?而流形數(shù)據(jù)通常有較多樣本距離其密度峰值較遠(yuǎn),導(dǎo)致大量本應(yīng)屬于同一個(gè)類簇的樣本被錯(cuò)誤分配給其他類簇,致使聚類精度不高.

為解決DPC算法存在的上述問題,許多學(xué)者對(duì)其進(jìn)行了改進(jìn).針對(duì)局部密度定義的缺陷,Xu等人[13]提出了一種具有密度敏感相似性的穩(wěn)健密度峰值聚類算法.該算法引入密度敏感相似性代替歐氏距離,提高了流形數(shù)據(jù)的聚類效果,并消除了截?cái)嗑嚯x參數(shù)的選取對(duì)聚類結(jié)果的影響.陳俊芬等人[14]提出了一種復(fù)雜高維數(shù)據(jù)的密度峰值快速搜索聚類算法.該算法采用流行距離高斯核函數(shù)值的累加重新定義樣本的局部密度,使?jié)撛诿芏确逯党蔀樽畲笾迭c(diǎn),提高了同一類簇樣本間的緊密性和不同類簇樣本間的分離性.該算法在處理復(fù)雜高維數(shù)據(jù)時(shí)具有較好的魯棒性.Xie等人[15]提出了一種基于模糊加權(quán)K近鄰檢測(cè)密度峰值并分配剩余點(diǎn)的聚類算法.該局部密度計(jì)算方式將范圍從所有樣本縮減為樣本的K個(gè)近鄰,更能體現(xiàn)樣本的局部信息.以上算法均對(duì)DPC算法的局部密度進(jìn)行了改進(jìn),提高了聚類效果,但對(duì)疏密程度相差較大的數(shù)據(jù)集,它們?nèi)匀浑y以準(zhǔn)確找到密度峰值,致使聚類效果不佳.

針對(duì)分配策略設(shè)計(jì)的不足,趙嘉等人[16]提出了一種基于相互鄰近度的密度峰值聚類算法,該算法定義了一種新的樣本相互鄰近度的度量準(zhǔn)則,能夠準(zhǔn)確分配剩余樣本,對(duì)密集程度不一數(shù)據(jù)具有較好的聚類效果.丁志成等人[17]提出了一種優(yōu)化分配策略的密度峰值聚類算法.該算法參考萬(wàn)有引力公式,使用基于相似度的局部連通性對(duì)樣本進(jìn)行分配,提高了流形數(shù)據(jù)集上樣本分配的準(zhǔn)確度.胡恩祥等人[18]提出了一種基于密度峰值剪枝后的最短路徑聚類算法.針對(duì)剩余點(diǎn)的分配,該算法從不同的密度峰值出發(fā)選擇到達(dá)該點(diǎn)距離的最短路徑,由此確定剩余點(diǎn)所歸屬的密度峰值.該方法有效提升了算法執(zhí)行效率和聚類精度.然而,以上的DPC改進(jìn)算法分配剩余樣本時(shí)使用的樣本相似度只考慮了樣本間的距離,忽略了樣本實(shí)際分布,仍然會(huì)導(dǎo)致某些樣本被錯(cuò)誤分配.

根據(jù)上述分析,本文提出了一種K近鄰和加權(quán)相似性的密度峰值聚類算法(density peaks clustering algorithm with K-nearest neighbors and weighted similarity,DPC–KWS).DPC–KWS算法的主要?jiǎng)?chuàng)新包括:1)使用樣本的K近鄰信息重新定義局部密度,它計(jì)算的局部密度為樣本局部范圍內(nèi)的相對(duì)密度,能夠調(diào)節(jié)不同分布類簇中樣本的局部密度大小,使得稀疏類簇樣本的局部密度升高,密集類簇樣本的局部密度降低.新的局部密度定義方式能準(zhǔn)確找到疏密程度相差較大數(shù)據(jù)集中的密度峰值;2) 使用樣本的共享最近鄰及自然最近鄰信息定義樣本間的相似性,摒棄了歐氏距離對(duì)分配策略的影響,以此確定的樣本相似性更符合樣本的實(shí)際分布,利用該相似性矩陣分配剩余樣本,避免了樣本分配策略產(chǎn)生的分配錯(cuò)誤連帶效應(yīng),提高了流形數(shù)據(jù)集的聚類效果.實(shí)驗(yàn)表明,本文算法對(duì)密度分布不均和流形數(shù)據(jù)集均能獲得滿意的聚類結(jié)果.

2 DPC算法

DPC算法的基本思想如下:1)密度峰值的局部密度較大,并且被密度均不超過它的鄰居包圍;2)各密度峰值間的距離相對(duì)較遠(yuǎn)[19].因此,DPC算法提出了局部密度ρi和到最近更高局部密度樣本的相對(duì)距離δi兩個(gè)概念.截?cái)嗪说木植棵芏扔?jì)算公式為

其中:dij為樣本i與j之間的歐氏距離,dc為截?cái)嗑嚯x.

當(dāng)數(shù)據(jù)集規(guī)模較小時(shí),局部密度采用高斯核函數(shù)計(jì)算,計(jì)算公式為

樣本i到較高局部密度樣本的最近距離由δi表示,δi的計(jì)算公式如下:

從式(3)可以看出,如果樣本i具有最大的局部密度,則其對(duì)應(yīng)的相對(duì)距離也是最大的.

DPC算法將ρi和δi均較大的樣本作為密度峰值.為發(fā)現(xiàn)密度峰值,DPC算法繪制以ρi為橫坐標(biāo),δi為縱坐標(biāo)的決策圖來(lái)選擇密度峰值.為更好地表示密度峰值,DPC算法定義了一個(gè)決策值參數(shù)γi,即

DPC算法認(rèn)為局部密度大且距離遠(yuǎn)的樣本為密度峰值,即選擇γi值大的點(diǎn)作為密度峰值.找到密度峰值后,剩余的樣本被分配給比其密度高的最近樣本所在類簇.

3 DPC–KWS算法

由前文的分析得知,DPC算法在局部密度定義和分配策略設(shè)計(jì)方面存在不足.針對(duì)上述不足,DPC–KWS算法從局部密度定義和分配策略設(shè)計(jì)兩方面對(duì)DPC算法進(jìn)行改進(jìn).

3.1 K近鄰的局部密度

DPC算法的高斯核和截?cái)嗪说木植棵芏榷x方式均與截?cái)嗑嚯x相關(guān),且不同數(shù)據(jù)集的最佳截?cái)嗑嚯x取值存在較大差異[20];此外,DPC算法的局部密度主要由截?cái)嗑嚯x范圍內(nèi)的樣本決定,截?cái)嗑嚯x范圍外的樣本對(duì)局部密度的貢獻(xiàn)非常低,導(dǎo)致局部密度大的區(qū)域內(nèi)會(huì)有更大概率出現(xiàn)密度峰值,對(duì)密度分布不均數(shù)據(jù)而言,就會(huì)使類簇中心集中在稠密區(qū)域,稀疏區(qū)域沒有類簇中心.經(jīng)過分析可知,一個(gè)樣本與其K個(gè)近鄰點(diǎn)的相對(duì)密度能更真實(shí)反映該樣本是否為密度峰值.

定義1K近鄰的局部密度定義為

這樣設(shè)計(jì)局部密度的優(yōu)勢(shì)在于,它使樣本的局部密度僅與其K個(gè)近鄰點(diǎn)有關(guān),排除了遠(yuǎn)處無(wú)關(guān)點(diǎn)的干擾,而且它計(jì)算的局部密度為該點(diǎn)與其K個(gè)近鄰點(diǎn)的相對(duì)密度,能夠調(diào)節(jié)不同分布類簇中樣本的局部密度大小,使得稀疏類簇樣本的局部密度升高,密集類簇樣本的局部密度降低,更有利于找到稀疏類簇中的密度峰值,從而提高對(duì)疏密程度相差較大數(shù)據(jù)集的聚類效果.

為驗(yàn)證本算法的局部密度定義方式能準(zhǔn)確找到疏密程度相差較大數(shù)據(jù)集的聚類中心.對(duì)Jain數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),圖1為采用高斯核函數(shù)計(jì)算局部密度得到的類簇中心,圖2為采用截?cái)嗪撕瘮?shù)計(jì)算局部密度得到的類簇中心,圖3為采用K近鄰的局部密度得到的類簇中心,圖中用“六角星”表示類簇中心.

圖1 高斯核的局部密度獲得的密度峰值Fig.1 The density peaks obtained by the local density of the Gaussian nucleus

圖2 截?cái)嗪说木植棵芏全@得的密度峰值Fig.2 The density peaks obtained by the local density of the cutoff kernel

圖3 K近鄰的局部密度獲得的密度峰值Fig.3 The density peaks obtained by the local density of the K-nearest neighbors

從圖1和圖2可以看出,DPC算法的兩種局部密度定義方式?jīng)]有考慮兩類簇的樣本疏密程度差異,使得密度峰值均落在密集類簇中,稀疏類簇中沒有密度峰值.圖3中,K近鄰的局部密度定義方法可以準(zhǔn)確找到密集和稀疏類簇中的密度峰值.由此可見,K近鄰的局部密度定義方式可以增強(qiáng)疏密程度相差較大數(shù)據(jù)集的密度峰值識(shí)別度.

3.2 加權(quán)相似性的分配策略

在分配剩余樣本時(shí),DPC算法只考慮了樣本間密度與距離之間的關(guān)系,使得DPC算法雖然能在一些簡(jiǎn)單的數(shù)據(jù)集上獲得較好的聚類結(jié)果,但對(duì)于流形數(shù)據(jù)集,易出現(xiàn)本應(yīng)屬于同一個(gè)類簇的樣本被錯(cuò)誤分配給其他類簇,導(dǎo)致發(fā)生分配錯(cuò)誤連帶效應(yīng),致使聚類精度不高.本文采用樣本的共享最近鄰及自然最近鄰信息,重新定義了樣本間相似性,該相似性充分考慮了樣本所處的局部環(huán)境,使樣本相似性更符合樣本的實(shí)際分布,進(jìn)而避免樣本分配錯(cuò)誤連帶效應(yīng).

定義2共享最近鄰(shared nearest neighbors,SNN).樣本i的K個(gè)最近鄰樣本和樣本j的K個(gè)最近鄰樣本的交集稱為樣本i和j的共享最近鄰集合.用公式表示為

定義3自然最近鄰(natural nearest neighbors,NNN).如果樣本i的K個(gè)最近鄰樣本包含樣本j,且樣本j的K個(gè)最近鄰樣本包含樣本i,則稱樣本i和j為自然最近鄰,取值為1,否則不為自然最近鄰,取值為0.用公式表示為

為將剩余樣本正確分配,本文設(shè)計(jì)了一種加權(quán)相似性的分配策略:首先依式(8)計(jì)算樣本i與樣本j的相似性ω(i,j),若兩點(diǎn)距離越近,則其相似性越高.

其中ω(i,j)為僅從歐氏距離方面度量樣本i和j之間的相似性.

僅通過歐氏距離考慮樣本間的相似性會(huì)忽略樣本的周圍環(huán)境,不能準(zhǔn)確反映樣本的實(shí)際分布,而更準(zhǔn)確定義樣本間的相似度需考慮樣本的共享最近鄰和自然最近鄰,所以同時(shí)使用共享最近鄰與自然最近鄰對(duì)其進(jìn)行加權(quán)處理,這樣得到的樣本相似性充分考慮了樣本所處的環(huán)境,避免了樣本分配錯(cuò)誤連帶效應(yīng).

Sim(i,j)為考慮樣本所處環(huán)境時(shí),樣本i和j之間的相似性.Sim(i,j)的計(jì)算公式如下:

為驗(yàn)證本算法分配策略的優(yōu)勢(shì),采用Pathbased數(shù)據(jù)集進(jìn)行實(shí)驗(yàn).圖4–5為采用高斯核局部密度定義方式,不同的分配策略得到的聚類結(jié)果.圖4為采用DPC算法的分配策略獲得的聚類結(jié)果,圖5為采用加權(quán)相似性的分配策略得到的聚類結(jié)果.

圖4 DPC算法的分配策略獲得的聚類結(jié)果Fig.4 The clustering results obtained by the allocation strategy of DPC algorithm

圖5 加權(quán)相似性的分配策略獲得的聚類結(jié)果Fig.5 The clustering results obtained by the weighted similarity allocation strategy

從圖4可以看出,DPC算法能夠準(zhǔn)確找到3個(gè)密度峰值,但是由于中間兩類簇與外圍流形類簇中部分樣本距離較近,導(dǎo)致分配剩余點(diǎn)產(chǎn)生連帶錯(cuò)誤,把流形類簇部分樣本分配給了中間兩類簇.圖5中,加權(quán)相似性的分配策略能夠顯著提升外圍流形類簇樣本的分配準(zhǔn)確度,證明了本算法分配策略的有效性.

新的樣本分配策略執(zhí)行流程如下:如式(9)計(jì)算樣本的加權(quán)相似性Sim(i,j);通過樣本相似性矩陣尋找與已分配樣本相似性最高的未分配樣本,并將未分配樣本分配給已分配樣本所在類簇;循環(huán)該操作直至所有剩余樣本分配完畢.

3.3 算法步驟

DPC–KWS算法的聚類過程如下:

輸入:數(shù)據(jù)集X={x1,x2,···,xn},樣本近鄰數(shù)K.

輸出:聚類結(jié)果C={c1,c2,···,cm},m為類簇個(gè)數(shù).

步驟1數(shù)據(jù)預(yù)處理,對(duì)數(shù)據(jù)進(jìn)行歸一化處理;

步驟2計(jì)算樣本間的歐氏距離;

步驟3根據(jù)式(5)計(jì)算樣本的局部密度;

步驟4根據(jù)式(3)計(jì)算樣本的相對(duì)距離,根據(jù)式(4)計(jì)算樣本的決策值γi并畫出決策圖,選取類簇中心集合;

步驟5根據(jù)式(8)–(9)計(jì)算樣本的加權(quán)相似性Sim(i,j);

步驟6對(duì)所有已分配的樣本尋找相似性最高的未分配樣本,將未分配樣本分配給已分配樣本所在類簇,循環(huán)該操作直至所有樣本分配完畢.

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

4.1 實(shí)驗(yàn)設(shè)置

本實(shí)驗(yàn)采用的數(shù)據(jù)集如表1–2所示.Jain,Pathbased,Lineblob和S2是密度分布不均數(shù)據(jù)集,其中Jain,Pathbased和Lineblob也是流形數(shù)據(jù)集;Spiral,Twomoons,Flame和Sticks是流形數(shù)據(jù)集.它們的樣本數(shù)量和分布各不相同,用于測(cè)試本算法對(duì)疏密程度相差較大和流形數(shù)據(jù)集的聚類效果.8個(gè)UCI數(shù)據(jù)集的樣本數(shù)量、密度峰值個(gè)數(shù)和數(shù)據(jù)維數(shù)差異較大,對(duì)其進(jìn)行實(shí)驗(yàn),可測(cè)試各算法對(duì)問題的普適性.實(shí)驗(yàn)部分將DPC–KWS算法與DPC[10],FKNN–DPC[15],DPCSA[21],DPC–DBFN[22]以及IDPC–FA[23]進(jìn)行比較.所有聚類算法的實(shí)驗(yàn)環(huán)境均為Intel(R)Core(TM)i5–7300 CPU@2.50 GHz 2.50 GHz,8 GB內(nèi)存,Windows 10 64bit操作系統(tǒng)和MATLAB 2019b編程環(huán)境.

表1 流形及密度分布不均數(shù)據(jù)集Table 1 Manifold and uneven density datasets

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

本文選擇3個(gè)獨(dú)立于標(biāo)簽絕對(duì)值的評(píng)價(jià)指標(biāo)評(píng)價(jià)聚類性能.這些評(píng)價(jià)指標(biāo)包括:調(diào)整互信息(adjusted mutual information,AMI)[24]、調(diào)整蘭德系數(shù)(adjusted rand index,ARI)[24]和Fowlkes–Mallows指數(shù)(Fowlkes–Mallows index,FMI)[25].這3個(gè)指標(biāo)的上限均為1,該值越接近1表示聚類效果越好.本文對(duì)比的5種算法中,DPCSA,IDPC–FA,DPC–DBFN和DPC算法代碼由原作者提供,FKNN–DPC 算法為參考原文獻(xiàn)編程實(shí)現(xiàn).為準(zhǔn)確體現(xiàn)各算法性能,本實(shí)驗(yàn)對(duì)各算法進(jìn)行參數(shù)調(diào)優(yōu),DPC–KWS,FKNN–DPC和DPC–DB-FN算法需要定義近鄰數(shù)K,該值在1～100 之間選取;DPC算法需要設(shè)定截?cái)嗑嚯x,該值在0.01%～5%之間選取;IDPC–FA和DPCSA 算法無(wú)需參數(shù)調(diào)優(yōu),所有實(shí)驗(yàn)參數(shù)均為對(duì)各算法調(diào)優(yōu)后的最優(yōu)結(jié)果.

4.2 流形及密度分布不均數(shù)據(jù)實(shí)驗(yàn)結(jié)果分析

表3展示了表1中列出的所有流形及密度分布不均數(shù)據(jù)在6種算法上的AMI,ARI和FMI指標(biāo)的聚類結(jié)果.表3中的每種算法最好的聚類結(jié)果加粗加黑表示,各聚類算法的最優(yōu)參數(shù)用Arg-表示,“–”表示沒有對(duì)應(yīng)值.

從表3中可以看出,DPC–KWS算法對(duì)8個(gè)流形及密度分布不均數(shù)據(jù)集在每個(gè)評(píng)價(jià)指標(biāo)上的取值都在0.93以上,表明DPC–KWS算法在流形及密度分布不均數(shù)據(jù)上均能取得較好的聚類結(jié)果.其他對(duì)比的聚類算法,均存在對(duì)一些數(shù)據(jù)集的聚類效果不佳.如DPC–DBFN 算法在Spiral 數(shù)據(jù)集上的效果非常不理想;F-KNN–DPC算法在處理Jain數(shù)據(jù)集時(shí)效果較差;DPC-SA和DPC算法對(duì)Jain和Pathbased數(shù)據(jù)集的聚類效果不理想.

表3 6種聚類算法在8個(gè)流形及密度分布不均數(shù)據(jù)上的聚類性能Table 3 Clustering performance of the six algorithms on eight manifold and uneven density datasets

受論文篇幅所限,圖6–7僅展示各聚類算法對(duì)Pathbased和Jain數(shù)據(jù)集的聚類結(jié)果.圖中不同顏色的點(diǎn)代表不同的類簇,“六角星”表示密度峰值.

圖6為6種算法對(duì)Path-based數(shù)據(jù)集的聚類結(jié)果.Pathbased數(shù)據(jù)集一共有300個(gè)樣本,包含兩個(gè)團(tuán)狀類簇和一個(gè)流形類簇,其中流形類簇包圍了兩個(gè)團(tuán)狀類簇,由于3個(gè)類簇之間聯(lián)系緊密,樣本的分配很容易發(fā)生連帶錯(cuò)誤.對(duì)該數(shù)據(jù)集,DPC–KWS和FKNN–DPC算法聚類效果明顯優(yōu)于其余算法,僅個(gè)別邊緣樣本被分配錯(cuò)誤.其余算法均能正確找到密度峰值,但是由于團(tuán)狀類簇與流形類簇中部分樣本距離較近,致使分配剩余點(diǎn)產(chǎn)生連帶錯(cuò)誤,所以聚類效果不理想.

圖6 6種聚類算法對(duì)Pathbased數(shù)據(jù)集的聚類結(jié)果Fig.6 Clustering results of six algorithms on Pathbased dataset

圖7為6種算法對(duì)Jain數(shù)據(jù)集的聚類結(jié)果.該數(shù)據(jù)集由兩個(gè)月牙狀類簇組成,上面的類簇較為稀疏,下面的類簇較為密集,是典型的疏密程度不一的流形數(shù)據(jù)集.對(duì)該數(shù)據(jù)集,6種算法中IDPC–FA和DPC–KWS算法能夠準(zhǔn)確聚類,DPC和DPCSA算法沒有準(zhǔn)確找到密度峰值,兩個(gè)密度峰值均在密集類簇中,使得分配剩余點(diǎn)發(fā)生連帶錯(cuò)誤.其余算法雖然能夠準(zhǔn)確找到密度峰值,但錯(cuò)誤地把密集類簇中較多的樣本分配給稀疏類簇,使得聚類效果較差.

圖7 6種聚類算法對(duì)Jain數(shù)據(jù)集的聚類結(jié)果Fig.7 Clustering results of six algorithms on Jain dataset

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

為進(jìn)一步驗(yàn)證DPC–KWS算法的有效性,將6種聚類算法在8個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn).表4給出了8個(gè)真實(shí)數(shù)據(jù)集在AMI,ARI和FMI指標(biāo)的聚類結(jié)果.從表4可以看出,DPC–KWS算法整體性能最優(yōu),在Seeds數(shù)據(jù)集上,DPC–KWS算法的聚類效果不如FKNN–DPC算法;在Dermatology數(shù)據(jù)集上,DPC–KWS算法的聚類效果不如IDPC–FA算法;在Iris數(shù)據(jù)集上DPC–KWS聚類效果與FKNN–DPC和DPC-SA聚類效果相同;剩余的Ecoli,Libras,Wdbc,Wine 和Inonsphere數(shù)據(jù)集上,聚類性能最好的算法均為DPC–KWS算法.

表4 6種聚類算法在8個(gè)UCI數(shù)據(jù)集上的聚類性能Table 4 Clustering performance of the six algorithms on eight UCI datasets

5 總結(jié)

針對(duì)DPC算法聚類密度分布不均數(shù)據(jù)集易誤選類簇中心和流形數(shù)據(jù)集易錯(cuò)誤分配樣本的問題,本文提出了一種K近鄰和加權(quán)相似性的密度峰值聚類算法.DPC–KWS算法使用樣本的K近鄰信息重新定義了樣本的局部密度,新的局部密度為樣本局部范圍內(nèi)的相對(duì)密度,能準(zhǔn)確找到密度分布不均數(shù)據(jù)中的密度峰值;使用共享最近鄰及自然最近鄰定義樣本間的相似性,摒棄了歐氏距離對(duì)分配策略的影響,新的樣本相似性更加符合樣本的實(shí)際分布,利用該相似性矩陣分配剩余樣本,避免了樣本分配策略產(chǎn)生的錯(cuò)誤連帶效應(yīng),提高了流形數(shù)據(jù)的聚類效果.實(shí)驗(yàn)結(jié)果表明,本文算法對(duì)密度分布不均和流形數(shù)據(jù)集均能得到滿意的聚類結(jié)果.如何自動(dòng)確定算法的最佳參數(shù)K與提高算法在高維數(shù)據(jù)集上的聚類效果將是下一步的研究重點(diǎn).