基于加權(quán)共享近鄰與累加序列的密度峰值算法

王芙銀，張德生，肖燕婷

（西安理工大學(xué) 理學(xué)院，西安 710054）

0 概述

聚類(lèi)作為一種無(wú)監(jiān)督學(xué)習(xí)方法，是數(shù)據(jù)挖掘領(lǐng)域［1］的重要技術(shù)之一。聚類(lèi)的主要目的是依照所定義的聚類(lèi)準(zhǔn)則，將一組雜亂的數(shù)據(jù)中具有相似特征的數(shù)據(jù)點(diǎn)劃歸為一個(gè)類(lèi)簇，同時(shí)使得不同類(lèi)簇之間具有顯著差異［2］。在如今萬(wàn)物互聯(lián)、大數(shù)據(jù)蓬勃發(fā)展的當(dāng)下，所產(chǎn)生的數(shù)據(jù)量也正在爆炸式增長(zhǎng)，因此，尋求一種高效的數(shù)據(jù)聚類(lèi)方法顯得尤為重要。近年來(lái)，許多學(xué)者相繼提出了多種不同的聚類(lèi)算法，按照不同的算法原理可將其分為基于劃分的聚類(lèi)、基于層次的聚類(lèi)、基于網(wǎng)格的聚類(lèi)、基于密度的聚類(lèi)、基于模型的聚類(lèi)這五大類(lèi)，這幾類(lèi)不同的聚類(lèi)算法各自都具有獨(dú)特的優(yōu)勢(shì)并得到了廣泛研究與應(yīng)用。

DBSCAN［3］作為一種典型的基于密度的聚類(lèi)算法，能夠有效識(shí)別任意形狀的數(shù)據(jù)，且具有較好的聚類(lèi)效果，但該算法在聚類(lèi)過(guò)程中易受鄰域參數(shù)的影響，其結(jié)果往往需要反復(fù)調(diào)參才能確保精確。RODRIGUEZ 等［4］于2014 年提出一種新的基于密度的聚類(lèi)（DPC）算法，該算法因具有原理簡(jiǎn)單、高效等優(yōu)點(diǎn)，自提出以來(lái)便引起許多學(xué)者的關(guān)注，且被廣泛應(yīng)用于圖像處理［5］、生物醫(yī)學(xué)［6］、文檔處理［7］等領(lǐng)域，但是，DPC 算法也存在一些缺陷，如聚類(lèi)結(jié)果受局部密度及其相對(duì)距離的影響、截?cái)嗑嚯x需要人為設(shè)定且參數(shù)的選取較為敏感、聚類(lèi)中心的選取需人為參與決策、算法難以處理密度分布差異較大和復(fù)雜的流形結(jié)構(gòu)數(shù)據(jù)，這些問(wèn)題提高了算法在聚類(lèi)過(guò)程中的主觀(guān)性與不穩(wěn)定性。

為提高DPC 算法的適用性，很多學(xué)者都對(duì)其做了相應(yīng)的改進(jìn)。DU 等［8］提出一種基于KNN 的改進(jìn)密度峰值聚類(lèi)（DPC-KNN）算法，將KNN 與主成分分析法引入局部密度的計(jì)算過(guò)程，充分考慮數(shù)據(jù)的鄰域分布特征，從而更好地識(shí)別邊界點(diǎn)的類(lèi)別。PARMAR 等［9］采用殘差來(lái)測(cè)量鄰域內(nèi)的局部密度，提出一種基于殘差的密度峰值聚類(lèi)（REDPC）算法，其能夠更好地處理包含各種數(shù)據(jù)分布模式的數(shù)據(jù)集。LIU 等［10］指出DPC 算法中如局部密度及最短距離度量方法、剩余點(diǎn)分配策略等所存在的一些問(wèn)題，提出一種基于共享近鄰的聚類(lèi)方法，該方法通過(guò)共享近鄰重新定義密度及其距離的計(jì)算方式，最后設(shè)計(jì)兩步分配方式對(duì)剩余點(diǎn)進(jìn)行分配，其有效提高了算法的聚類(lèi)性能。XIE 等［11］提出一種基于模糊加權(quán)K 近鄰的改進(jìn)DPC（FKNN-DPC）算法，利用K個(gè)最近鄰個(gè)體之間的距離之和來(lái)衡量密度，并用一種新的分配方式對(duì)剩余點(diǎn)進(jìn)行分配。CHENG 等［12］提出一種新的基于自然鄰居優(yōu)化的DPC 算法，該改進(jìn)算法可以很好地反映數(shù)據(jù)的分布，且無(wú)需任何參數(shù)。HOU 等［13］提出僅基于相對(duì)密度關(guān)系的聚類(lèi)中心識(shí)別準(zhǔn)則，以增強(qiáng)密度峰值聚類(lèi)算法的聚類(lèi)效果。FLORES 等［14］通過(guò)檢測(cè)一維決策圖中數(shù)據(jù)點(diǎn)之間的間隙來(lái)自動(dòng)確定聚類(lèi)中心。LIANG 等［15］提出一種基于分治法的改進(jìn)DPC 算法，該算法在不需要任何先驗(yàn)條件的情況下能夠自動(dòng)尋得聚類(lèi)中心。QIAO等［16］引入一種新的不對(duì)稱(chēng)度量指標(biāo)，增強(qiáng)了算法查找邊界點(diǎn)的能力，解決了DPC 算法在分布不均的數(shù)據(jù)上聚類(lèi)效率不高的問(wèn)題。XU 等［17］提出一種具有密度敏感相似性的密度峰值聚類(lèi)（RDPC-DSS）算法，其有效提高了流形數(shù)據(jù)的聚類(lèi)精度。

本文提出一種基于加權(quán)共享近鄰與累加序列的密度峰值（DPC-WSNN）算法。定義一種新的基于加權(quán)共享近鄰的局部密度度量公式，替代DPC 中根據(jù)截?cái)嗑嚯xdc所定義的密度公式，避免因dc選取不當(dāng)而影響聚類(lèi)效果，同時(shí)，利用加權(quán)共享近鄰并進(jìn)一步考慮全局一致性，以有效處理不同類(lèi)簇?cái)?shù)據(jù)集分布不均的情況。在選取聚類(lèi)中心的過(guò)程中，在原有決策值γi=ρiδi的基礎(chǔ)上，重新定義γ的計(jì)算方式，借鑒ZHOU 等［18］在灰色預(yù)測(cè)模型中所定義的一階累加序列生成方式，產(chǎn)生一組γ的累加序列，根據(jù)所產(chǎn)生的累加序列數(shù)值變化情況來(lái)實(shí)現(xiàn)類(lèi)簇中心的自動(dòng)選取，從而避免手動(dòng)選取聚類(lèi)中心所帶來(lái)的誤差。

1 密度峰值聚類(lèi)算法

DPC 算法在實(shí)現(xiàn)過(guò)程中主要基于以下2 個(gè)假設(shè)：

1）聚類(lèi)中心被一群密度較低的點(diǎn)包圍。

2）聚類(lèi)中心與其他高密度點(diǎn)之間的最短距離足夠遠(yuǎn)。

基于上述2 個(gè)假設(shè)，選取一個(gè)合適的截?cái)嗑嚯x參數(shù)dc，用來(lái)求解數(shù)據(jù)點(diǎn)的局部密度ρ及其相對(duì)距離δ值，最后根據(jù)決策圖找出聚類(lèi)中心并分配剩余點(diǎn)。對(duì)于數(shù)據(jù)集X={x1,x2,…,xn}，dij表示數(shù)據(jù)點(diǎn)i與點(diǎn)j間的歐氏距離。數(shù)據(jù)點(diǎn)的局部密度有2 種不同的定義方式：

1）在截?cái)嗪说亩x下，點(diǎn)i的局部密度ρi定義為：

當(dāng)dij＜dc時(shí)，χ(dij-dc)=1；否則，χ(dij-dc)=0。

2）在高斯核的定義下，ρi如式（2）所示：

點(diǎn)i到其他高密度點(diǎn)間的最短距離δi定義為：

當(dāng)計(jì)算出所有點(diǎn)的局部密度ρi以及相對(duì)距離δi后，選擇ρi與δi均較大的點(diǎn)作為聚類(lèi)中心，將剩余點(diǎn)分配給與之較近的高密度點(diǎn)所在的類(lèi)簇中從而完成聚類(lèi)。

2 DPC 算法改進(jìn)

2.1 基于加權(quán)共享近鄰的局部密度改進(jìn)

DPC 算法定義了2 種密度計(jì)算方式，2 種方式都是以歐幾里得距離來(lái)衡量數(shù)據(jù)點(diǎn)的密度，但是歐幾里得距離只考慮數(shù)據(jù)點(diǎn)之間的局部一致性特征，忽略了全局一致性特征，因此，當(dāng)數(shù)據(jù)樣本點(diǎn)分布不均時(shí)，基于歐幾里得距離得到的密度通常不能準(zhǔn)確地捕捉到固有的數(shù)據(jù)結(jié)構(gòu)，最終導(dǎo)致聚類(lèi)性能下降。為了適應(yīng)更多復(fù)雜且分布不均的數(shù)據(jù)集，本文將共享近鄰引入密度計(jì)算中，充分考慮樣本的整體分布，以更好地平衡樣本點(diǎn)的全局一致性與局部一致性。共享近鄰［10］與樣本間的相似度定義如下：

定義1（共享近鄰）對(duì)于數(shù)據(jù)集X中的樣本點(diǎn)xi與xj，點(diǎn)xi的K 近鄰記為Γ(xi)，點(diǎn)xj的K 近鄰記為Γ(xj)，則點(diǎn)xi與xj的共享近鄰S(chǎng)NN(xi,xj)定義為：

定義2（樣本間的相似度）根據(jù)共享近鄰的定義，樣本點(diǎn)xi與xj間的相似度sij定義為：

其中：ο為共享近鄰中所取的樣本點(diǎn)；|SNN(xi,xj)|表示屬于共享近鄰的樣本數(shù)目，其值越大，表明點(diǎn)i、j的相似度越大，(diο+djο)越小，點(diǎn)i、j之間的相似度也越大。當(dāng)2 組樣本的共享近鄰數(shù)目相等時(shí)，如圖1 所示，點(diǎn)i和j、點(diǎn)i和k的共享近鄰個(gè)數(shù) 都為1，且 此時(shí)dij=dik，根據(jù)三角形的三邊關(guān)系可知，有根據(jù)式（5）所定義的相似度，則認(rèn)為點(diǎn)i與點(diǎn)k間的相似度大于點(diǎn)i與點(diǎn)j間的相似度，這樣更能反映空間中樣本點(diǎn)的分布特征。

圖1 共享鄰居示意圖Fig.1 Schematic diagram of shared neighbors

此外，在面對(duì)不同密度和大小的類(lèi)簇時(shí)，位于數(shù)據(jù)密集區(qū)域的樣本點(diǎn)和位于數(shù)據(jù)稀疏區(qū)域的樣本點(diǎn)對(duì)聚類(lèi)中心選取的貢獻(xiàn)度不一樣，因此，在解決數(shù)據(jù)分布不均的問(wèn)題上，除對(duì)數(shù)據(jù)進(jìn)行過(guò)采樣和欠采樣調(diào)節(jié)外，對(duì)樣本點(diǎn)的貢獻(xiàn)度進(jìn)行加權(quán)處理也可以起到很好的平衡作用。本文以樣本點(diǎn)間的共享近鄰數(shù)作為密度的重要衡量指標(biāo)，以對(duì)每個(gè)樣本點(diǎn)所在的區(qū)域相似度進(jìn)行權(quán)重調(diào)整，為此，引入圖2 所示的sigmoid 函數(shù)，其定義如下：

圖2 sigmoid 函數(shù)圖像Fig.2 Image of the sigmoid function

相比于一元一次函數(shù)，sigmoid 函數(shù)在一定程度上可以對(duì)數(shù)據(jù)相似度進(jìn)行權(quán)重調(diào)整，減少了因數(shù)據(jù)分布不均而帶來(lái)的誤差。本文將sigmoid 函數(shù)引入密度計(jì)算中，以互近鄰點(diǎn)的數(shù)目作為變量x值，分析可知，在式（6）中，當(dāng)共享近鄰數(shù)目較多時(shí)，表明2 個(gè)樣本點(diǎn)間的相似度較高，有較大的可能性會(huì)被聚為一類(lèi)，通過(guò)圖2 函數(shù)變化圖像可知，當(dāng)互近鄰點(diǎn)的數(shù)目足夠多時(shí)，其函數(shù)值為1，這表明在處理高密度區(qū)域的點(diǎn)時(shí)，所加權(quán)重接近1，對(duì)于高密度樣本點(diǎn)而言，其本身就有較大概率被選作聚類(lèi)中心，此時(shí)可令其相似度的權(quán)重為1，當(dāng)互近鄰點(diǎn)的數(shù)目不斷減少或?yàn)? 時(shí)，其權(quán)重則由1 非線(xiàn)性遞減到0.5，這時(shí)非聚類(lèi)中心點(diǎn)與聚類(lèi)中心有了更加明顯的區(qū)分，能夠使得式（5）所定義的相似度更具合理性和準(zhǔn)確性。經(jīng)過(guò)加權(quán)后，局部密度ρi如定義3 所示。

定義3（局部密度）對(duì)于樣本點(diǎn)i，根據(jù)其相似度定義密度ρi為：

通過(guò)定義3 所給出的密度度量公式，可計(jì)算出數(shù)據(jù)集中所有點(diǎn)的局部密度及相對(duì)距離。

為了進(jìn)一步說(shuō)明所改進(jìn)的密度在處理分布不均數(shù)據(jù)集時(shí)的有效性，以Pathbased 數(shù)據(jù)集為例，DPC算法與加權(quán)共享近鄰的改進(jìn)DPC 算法的決策圖如圖3 所示。從圖3（a）可以看出，DPC 的決策圖在確定聚類(lèi)中心時(shí)很容易將第3 個(gè)聚類(lèi)點(diǎn)處理為噪聲點(diǎn)，從而導(dǎo)致最終聚類(lèi)結(jié)果出現(xiàn)偏差；從圖3（b）可以看出，對(duì)密度進(jìn)行改進(jìn)后，決策圖中聚類(lèi)中心分布在右上角，均位于高密度區(qū)域，通過(guò)該決策圖可以準(zhǔn)確選出目標(biāo)聚類(lèi)中心。實(shí)驗(yàn)結(jié)果表明，改進(jìn)DPC 可以對(duì)數(shù)據(jù)進(jìn)行全局考慮，解決數(shù)據(jù)集中的分布不均問(wèn)題，從而確定正確的聚類(lèi)中心。

圖3 2 種算法的決策圖對(duì)比Fig.3 Comparison of decision diagrams of two algorithms

2.2 聚類(lèi)中心選取方法改進(jìn)

DPC 算法在選取聚類(lèi)中心時(shí)，需要人為參與決策，通過(guò)決策圖來(lái)選取ρ與δ均較大的點(diǎn)，但對(duì)于聚類(lèi)中心較多的數(shù)據(jù)集，這種方法顯得復(fù)雜低效，而且出現(xiàn)錯(cuò)選的概率較大。本文提出一種新的聚類(lèi)中心選取方法，首先定義決策值γi如下：

為消除ρi與δi量綱不同而造成的誤差，對(duì)ρi與δi進(jìn)行歸一化處理，將歸一化后結(jié)果的乘積作為決策值γi。本文將γi進(jìn)行降序排列得到一組降序值，將其記為γ′，根據(jù)聚類(lèi)中心的性質(zhì)可知，在γ′=[γ1,γ2,…,γn]中，只有前面幾個(gè)較大值所對(duì)應(yīng)的點(diǎn)應(yīng)被選作聚類(lèi)中心。對(duì)此，本文參考文獻(xiàn)［18］所定義的一種新的非負(fù)序列累加生成方法，對(duì)于非負(fù)序列定義其累加序列為其中：

觀(guān)察式（9）可知，由于λ∈(0,1)，因此該序列在累加過(guò)程中，靠前位置信息的影響權(quán)重在不斷降低，而信息越靠后，權(quán)值越大。

對(duì)于γ′而言，需要保留前面一部分較大的值，因此，本文對(duì)式（9）進(jìn)行調(diào)整，使其在累加過(guò)程中不斷降低序列靠后位置信息的權(quán)值，而增大靠前位置信息的權(quán)重，使其更好地滿(mǎn)足本文的需求。修改后的累加定義如下：

由于γ′為降序排列的序列，因此在逐步累加的過(guò)程中，累加序列的值也越來(lái)越接近，最終大量的點(diǎn)會(huì)不斷地集中在一起。在累加序列γ(t)中，定義均值μ為：

在選取聚類(lèi)中心時(shí)，只需在γ(t)序列中挑選比均值μ小的點(diǎn)，將其作為聚類(lèi)中心。以類(lèi)別數(shù)為7 的Aggregation 數(shù)據(jù)集為例，圖4 展示了其γ′的累加序列分布情況（彩色效果見(jiàn)《計(jì)算機(jī)工程》官網(wǎng)HTML版），圖4（b）是圖4（a）中方框線(xiàn)內(nèi)的局部放大圖，以便更好地觀(guān)察均值μ的位置分布。從圖4（b）可以看出，在累加過(guò)程中，大量的點(diǎn)不斷地集中在一起，紅色點(diǎn)u表示這組序列的均值μ，其也位于堆積點(diǎn)附近，而聚類(lèi)中心點(diǎn)對(duì)應(yīng)的累加值則位于均值的前方，此時(shí)只需選取那些累加值小于均值的點(diǎn)作為中心進(jìn)行聚類(lèi)即可，即將前7 個(gè)γ′所對(duì)應(yīng)的點(diǎn)選取為聚類(lèi)中心。因此，將累加序列γ(t)的均值作為聚類(lèi)中心和非聚類(lèi)中心的臨界點(diǎn)，可以準(zhǔn)確選取聚類(lèi)中心，從而實(shí)現(xiàn)聚類(lèi)中心的自適應(yīng)。

圖4 Aggregation 數(shù)據(jù)集的γ(t)序列分布Fig.4 γ(t)sequence distribution of Aggregation dataset

綜上，聚類(lèi)中心選取策略步驟為：

1）根據(jù)式（8）和式（11）得到累加序列γ(t)，并求得其均值μ，將小于均值μ的γ′個(gè)數(shù)作為聚類(lèi)中心數(shù)目m。

2）將前m個(gè)γ′值所對(duì)應(yīng)的點(diǎn)選取為聚類(lèi)中心。

2.3 算法描述

改進(jìn)DPC 算法描述如算法1 所示：首先，計(jì)算樣本點(diǎn)間的距離矩陣；然后，根據(jù)式（3）、式（7）分別計(jì)算相對(duì)距離與局部密度，在求得每個(gè)點(diǎn)的距離與密度后，根據(jù)式（11）、式（12）自動(dòng)選擇聚類(lèi)中心；最后，按照DPC 的分配策略對(duì)剩余點(diǎn)進(jìn)行分配聚類(lèi)。

算法1DPC-WSNN 算法

2.4 算法復(fù)雜度分析

對(duì)于含有N個(gè)樣本點(diǎn)的數(shù)據(jù)集，DPC 算法的時(shí)間復(fù)雜度為O(N2)。對(duì)于本文所提的DPC-WSNN 算法，設(shè)近鄰數(shù)為K，其計(jì)算局部密度ρi是基于共享近鄰的，時(shí)間復(fù)雜度為O(KN)；在選取聚類(lèi)中心時(shí)，需多計(jì)算一個(gè)決策值γi，其時(shí)間復(fù)雜度為O(N)。綜上，本文所提DPC-WSNN 算法的時(shí)間復(fù)雜度為（O(N2)+O(KN)+O(N))～O(N2)。因此，相較于DPC 算法，DPC-WSNN算法的時(shí)間復(fù)雜度并未增加。此外，在相關(guān)算法中，F(xiàn)KNN-DPC 算法的時(shí)間復(fù)雜度為O(N2)，DBSCAN 算法的時(shí)間復(fù)雜度為O(N2)，AP 算法與K-Means 算法的時(shí)間復(fù)雜度分別為O(N2lbN)與O(N)。

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

3.1 實(shí)驗(yàn)數(shù)據(jù)集

為了評(píng)估本文所提算法的有效性，采用如表1、表2 所示的8 個(gè)合成數(shù)據(jù)集和8 個(gè)UCI 數(shù)據(jù)集對(duì)其進(jìn)行驗(yàn)證。

表1 合成數(shù)據(jù)集Table 1 Synthetic datasets

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

3.2 評(píng)價(jià)指標(biāo)

在實(shí)驗(yàn)中，本文將DPC-WSNN 算法的聚類(lèi)結(jié)果與FKNN-DPC、DPC、DBSCAN、AP、K-Means 的聚類(lèi)結(jié)果進(jìn)行比較，評(píng)價(jià)指標(biāo)選取FM 指數(shù)（FMI）［19］、調(diào)整蘭德指數(shù)（Adjusted Rand Index，ARI）［20］和調(diào)整互信息（Adjusted Mutual Information，AMI）［21］。各指標(biāo)具體如下：

1）FMI 指標(biāo)。FMI 是成對(duì)精度與召回率的幾何均值，定義如下：

其中：a表示在C和C*中都屬于同一類(lèi)的數(shù)據(jù)點(diǎn)對(duì)數(shù)；b表示在C中屬于同一類(lèi)但在C*中不屬于同一類(lèi)的數(shù)據(jù)點(diǎn)對(duì)數(shù)；c表示在C*中屬于不同類(lèi)但在C中屬于同一類(lèi)的數(shù)據(jù)點(diǎn)對(duì)數(shù)。FMI 指標(biāo)的取值范圍是[0,1]，數(shù)值越大表示聚類(lèi)效果越好。

2）ARI 指標(biāo)。蘭德指數(shù)（RI）的定義式為：

其中：a代表在C和C*中都屬于同一類(lèi)的數(shù)據(jù)點(diǎn)對(duì)數(shù)；b代表在C*中屬于不同類(lèi)但在C中屬于同一類(lèi)的數(shù)據(jù)點(diǎn)對(duì)數(shù)代表數(shù)據(jù)集中可組成總元素的對(duì)數(shù)。在使用RI 指標(biāo)時(shí)，不能保證類(lèi)別標(biāo)簽在隨機(jī)分配的情況下其值接近0。因此，本文引入ARI［20］來(lái)解決這一問(wèn)題，ARI 指標(biāo)的定義式為：

其中：E(RRI)表示RI 的數(shù)學(xué)期望。ARI 的取值范圍為[-1,1]，值越大表示聚類(lèi)結(jié)果越精確。

3）AMI 指標(biāo)。與ARI 相似，AMI 也是一種常見(jiàn)的聚類(lèi)評(píng)價(jià)指標(biāo)，其定義式為：

其中：H(A)、H(B)表示2 個(gè)類(lèi)別標(biāo)簽的熵。AMI 是基于互信息（MI）來(lái)衡量聚類(lèi)效果的類(lèi)別信息，E(MMI)表示MI 的數(shù)學(xué)期望。AMI 的取值范圍是[-1,1]，值越接近1 表示聚類(lèi)結(jié)果越好，即與真實(shí)結(jié)果越吻合。

3.3 算法參數(shù)設(shè)置

為了更好地測(cè)試算法的聚類(lèi)效果，對(duì)各對(duì)比算法進(jìn)行參數(shù)調(diào)優(yōu)。DPC-WSNN 算法和FKNN-DPC算法需要設(shè)定樣本近鄰數(shù)K，該參數(shù)可根據(jù)不同數(shù)據(jù)集在5～30 之間擇優(yōu)選取。DBSCAN 算法需要設(shè)定鄰域半徑ε和鄰域內(nèi)包含的最少樣本數(shù)Minpts，其中，鄰域半徑ε以0.01 為步長(zhǎng)，在0.01～1 之間選取，鄰域內(nèi)包含的最少樣本數(shù)Minpts 在5～30 之間選取。AP 算法沒(méi)有通用的規(guī)則來(lái)選取參數(shù)，本文考慮將參數(shù)搜索上限設(shè)置為最大相似度的幾倍，逐漸縮小搜索范圍［10］。由于K-Means 算法中類(lèi)簇中心的選取對(duì)聚類(lèi)結(jié)果有較大影響，因此對(duì)每個(gè)數(shù)據(jù)集進(jìn)行30 次重復(fù)實(shí)驗(yàn)，取最優(yōu)結(jié)果。

3.4 結(jié)果分析

選取8 種合成數(shù)據(jù)集和8 種UCI數(shù)據(jù)集，對(duì)本文所提算法進(jìn)行測(cè)試和評(píng)價(jià)，并將其實(shí)驗(yàn)結(jié)果與FKNN-DPC、DPC、DBSCAN、AP、K-Means 進(jìn)行對(duì)比，各算法的3 種評(píng)價(jià)指標(biāo)值如表3～表6 所示，其中，加粗值表示最好的聚類(lèi)結(jié)果。從表3、表4可以看出，本文所提DPC-WSNN算法相比其他對(duì)比算法具有更好的聚類(lèi)表現(xiàn)，尤其對(duì)于Jain 數(shù)據(jù)集，本文算法的聚類(lèi)準(zhǔn)確率較對(duì)比算法具有大幅提升。從表5、表6 可以看出：對(duì)于維度高且樣本點(diǎn)密度變化大的數(shù)據(jù)集，DPC、DBSCAN、AP、K-Means的聚類(lèi)效果都不理想，無(wú)法得到較高的聚類(lèi)指標(biāo)值；FKNN-DPC 算法在Wine 數(shù)據(jù)集上達(dá)到最優(yōu)，而在其他數(shù)據(jù)集上的聚類(lèi)效果略差于DPC-WSNN 算法，由于DPC-WSNN 算法在DPC 的基礎(chǔ)上引入SNN 來(lái)對(duì)密度公式進(jìn)行改進(jìn)，充分考慮了數(shù)據(jù)分布稀疏的情況，進(jìn)而可以得到更準(zhǔn)確的密度。DPC-WSNN 在UCI 數(shù)據(jù)集上的聚類(lèi)指標(biāo)值整體更高，在所有對(duì)比算法中，其聚類(lèi)表現(xiàn)最優(yōu)，在其他數(shù)據(jù)集上也能達(dá)到較好的聚類(lèi)效果。相比DPC 算法和其他幾種對(duì)比算法，DPC-WSNN 算法在處理大部分問(wèn)題上均能達(dá)到較好的效果。

表3 6 種算法在前4 個(gè)合成數(shù)據(jù)集上的聚類(lèi)結(jié)果比較Table 3 Comparison of clustering results of six algorithms on first four synthetic datasets

表4 6 種算法在后4 個(gè)合成數(shù)據(jù)集上的聚類(lèi)結(jié)果比較Table 4 Comparison of clustering results of six algorithms on last four synthetic datasets

表5 6 種算法在前4 個(gè)UCI 數(shù)據(jù)集上的聚類(lèi)結(jié)果比較Table 5 Comparison of clustering results of six algorithms on first four UCI datasets

圖5～圖7分別為DPC-WSNN、FKNN-DPC、DPC、DBSCAN、AP、K-Means 這6 種對(duì)比算法在Jain 數(shù)據(jù)集、Flame 數(shù)據(jù)集、Pathbased 數(shù)據(jù)集上的聚類(lèi)效果（彩色效果見(jiàn)《計(jì)算機(jī)工程》官網(wǎng)HTML 版），圖中不同顏色的點(diǎn)被分配到不同的類(lèi)簇中，其中，藍(lán)色星形代表聚類(lèi)中心點(diǎn)，叉形代表噪聲點(diǎn)。

圖5 6 種算法在Jain 數(shù)據(jù)集上的聚類(lèi)效果Fig.5 Clustering effects of six algorithms on Jain dataset

圖6 6 種算法在Flame 數(shù)據(jù)集上的聚類(lèi)效果Fig.6 Clustering effect of six algorithms on Flame dataset

圖7 6 種算法在Pathbased 數(shù)據(jù)集上的聚類(lèi)效果Fig.7 Clustering effects of six algorithms on Pathbased dataset

從圖5 可以看出：本文DPC-WSNN 算法不僅可以找到正確的聚類(lèi)中心，而且聚類(lèi)結(jié)果也完全正確；DPC-KNN 算法、DPC 算法、AP 算法、K-Means 算法都將本該屬于下半部分的類(lèi)簇錯(cuò)誤地分配到了上半部分，從而出現(xiàn)了錯(cuò)誤的聚類(lèi)結(jié)果；DBSCAN 算法下半部分類(lèi)簇的聚類(lèi)結(jié)果正確，但上半部分左端幾個(gè)數(shù)據(jù)點(diǎn)被錯(cuò)誤分配。

從圖6 可以看出：DPC-WSNN 算法、DPC-KNN算法、DPC 算法、DBSCAN 算法均得到了正確的類(lèi)簇?cái)?shù)目，其中，DBSCAN 算法將左上角的2 個(gè)點(diǎn)識(shí)別為噪聲點(diǎn)，導(dǎo)致聚類(lèi)準(zhǔn)確率有所降低，AP 算法錯(cuò)誤地識(shí)別類(lèi)簇?cái)?shù)目，導(dǎo)致將聚類(lèi)結(jié)果分為了3 類(lèi)，而K-Means 算法將本該屬于紅色類(lèi)簇的點(diǎn)錯(cuò)誤地分配給了藍(lán)色類(lèi)簇。

從圖7 可以看出：本文DPC-WSNN 算法聚類(lèi)準(zhǔn)確度較高；AP 算法不能準(zhǔn)確識(shí)別出類(lèi)簇中心，導(dǎo)致聚類(lèi)結(jié)果出現(xiàn)明顯偏差；DPC-KNN 算法、DPC 算法和K-Means 算法雖能正確識(shí)別類(lèi)簇中心，但將半環(huán)部分的類(lèi)簇點(diǎn)進(jìn)行了錯(cuò)誤分配；在DBSCAN 算法中，雖然2 個(gè)類(lèi)簇被正確分配，但半環(huán)部分被識(shí)別為噪聲點(diǎn)，導(dǎo)致聚類(lèi)準(zhǔn)確率大幅降低。

3.5 參數(shù)敏感性分析

DPC-WSNN 算法在運(yùn)行過(guò)程中，需要人為設(shè)置參數(shù)K值，為了驗(yàn)證該參數(shù)對(duì)算法聚類(lèi)結(jié)果的影響，通過(guò)改變參數(shù)K值大小來(lái)探索DPC-WSNN 算法在不同數(shù)據(jù)集上的聚類(lèi)結(jié)果變化。實(shí)驗(yàn)選取3 個(gè)合成數(shù)據(jù)集和3 個(gè)UCI 數(shù)據(jù)集，以AMI 值作為穩(wěn)定性衡量指標(biāo)，K在5～30之間取值，所得的AMI指標(biāo)值結(jié)果如圖8所示。從圖8 可以看出：對(duì)于合成數(shù)據(jù)集而言，不同的K值所得到的結(jié)果較為穩(wěn)定，波動(dòng)較小，具有很好的魯棒性；對(duì)于UCI 數(shù)據(jù)集，前期當(dāng)K取值較小時(shí)，聚類(lèi)值有一定的波動(dòng)，但隨著K的不斷增大，其波動(dòng)逐漸減小，結(jié)果趨于穩(wěn)定，這意味著當(dāng)K近鄰個(gè)數(shù)增大時(shí)，所設(shè)計(jì)的加權(quán)共享近鄰的密度度量具有更好的優(yōu)勢(shì)，因此，聚類(lèi)實(shí)驗(yàn)驗(yàn)證了DPC-WSNN 算法對(duì)參數(shù)K的敏感性較低，算法具有較強(qiáng)的魯棒性。

圖8 K 值對(duì)DPC-WSNN 算法聚類(lèi)效果的影響Fig.8 Influence of K values on clustering effect of DPC-WSNN algorithm

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

本文對(duì)DPC 算法進(jìn)行改進(jìn)，提出一種基于加權(quán)共享近鄰與累加序列的密度峰值算法DPCWSNN。該算法考慮各數(shù)據(jù)點(diǎn)的鄰域分布情況，利用加權(quán)共享近鄰重新定義局部密度的度量方式，同時(shí)使用γ的累加序列來(lái)實(shí)現(xiàn)聚類(lèi)中心的自動(dòng)選取。實(shí)驗(yàn)結(jié)果表明，相比DPC、AP 等算法，DPC-WSNN算法具有較高的聚類(lèi)準(zhǔn)確度。本文算法執(zhí)行過(guò)程中涉及參數(shù)K，雖然參數(shù)K相較截?cái)嗑嚯xdc更容易確定，但其仍然需要人為決策。此外，DPC 算法對(duì)剩余點(diǎn)的分配方法也可能會(huì)影響DPC-WSNN 的聚類(lèi)效果。因此，實(shí)現(xiàn)參數(shù)K的自適應(yīng)以及對(duì)DPC 算法中剩余點(diǎn)分配策略進(jìn)行改進(jìn)，將是下一步的研究方向。