基于K近鄰的密度峰值聚類算法

摘 要：2014年6月發(fā)表在Science的密度峰值聚類算法（DPC）是基于密度的新型聚類算法，算法不需要迭代過(guò)程，具有更高效率。但是DPC算法計(jì)算密度時(shí)人為設(shè)定截?cái)嗑嚯x和人工選取簇類中心帶有主觀因素，因此本文提出一種基于K近鄰的密度峰值聚類算法。首先根據(jù)k近鄰思想計(jì)算截?cái)嗑嚯x和樣本點(diǎn)的局部密度值，然后通過(guò)綜合變量的排序選取簇類中心，最后將剩余的數(shù)據(jù)點(diǎn)劃分到適當(dāng)?shù)拇仡惒⑦M(jìn)行噪聲點(diǎn)檢測(cè)。在人工測(cè)試數(shù)據(jù)集和UCI真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)顯示，基于K近鄰的密度峰值聚類算法的聚類結(jié)果優(yōu)于DPC算法以及經(jīng)典算法K-means和DBSCAN。

關(guān)鍵詞：密度峰值；K近鄰；局部密度；截?cái)嗑嚯x；聚類

引言

聚類主要用作無(wú)監(jiān)督學(xué)習(xí)方法，是數(shù)據(jù)挖掘的一項(xiàng)主要技術(shù)。聚類方法包括劃分聚類、分層聚類、基于密度的聚類、基于網(wǎng)格的聚類、基于模型的聚類或這些方法的組合。K-means是一種經(jīng)典的劃分聚類方法，K-means無(wú)法識(shí)別任意形狀的簇。DBSCAN是一種基于密度的聚類方法，可以檢測(cè)任意形狀的聚類，但是閥值的選擇依賴經(jīng)驗(yàn)知識(shí)。

2014年Science發(fā)表了一種新的基于密度峰值聚類方法（DPC），簇類中心基于以下假設(shè)：簇類中心被鄰近局部密度較低的數(shù)據(jù)點(diǎn)所包圍，并且與任何具有較高局部密度的數(shù)據(jù)點(diǎn)相距較遠(yuǎn)。

DPC算法雖然簡(jiǎn)單高效，但是存在以下不足：截?cái)嗑嚯x的選取影響密度的計(jì)算和噪聲點(diǎn)的檢測(cè)，人為設(shè)定截?cái)嗑嚯x影響聚類結(jié)果；人工判斷簇類中心帶有主觀因素，降低算法的魯棒性。針對(duì)DPC算法的不足，本文提出基于K近鄰的密度峰值聚類算法（KNN-DPC），首先根據(jù)k近鄰思想計(jì)算截?cái)嗑嚯x和樣本點(diǎn)的局部密度值，然后通過(guò)綜合變量的排序選取簇類中心，最后將剩余的數(shù)據(jù)點(diǎn)劃分到適當(dāng)?shù)拇仡惒⑦M(jìn)行噪聲點(diǎn)檢測(cè)。實(shí)驗(yàn)證明本文算法較之DPC算法、K-means算法和DBSCAN具有更優(yōu)的聚類結(jié)果。

一、DPC算法

采用決策圖的方法選擇簇類中心，選擇局部密度和距離均較大的樣本點(diǎn)為簇類中心。

對(duì)于剩余數(shù)據(jù)樣本點(diǎn)，DPC算法將其歸并到密度比其大且距其最近的簇類。

雖然DPC算法能簡(jiǎn)單高效的處理聚類問(wèn)題，但是DPC算法中局部密度值的計(jì)算和噪聲點(diǎn)的判斷依賴截?cái)嗑嚯x，人為設(shè)定的截?cái)嗑嚯x使得聚類結(jié)果差異很大，而且人工選取簇類中心會(huì)出錯(cuò)的可能性。

二、基于K近鄰的密度峰值聚類算法

（一） K近鄰思想

對(duì)于基于k近鄰的局部密度計(jì)算，更容易區(qū)分核心區(qū)域中的點(diǎn)與其他領(lǐng)域的點(diǎn)，有助于聚類獲得更準(zhǔn)確的結(jié)果。因此本文將k近鄰思想與DPC聚類算法相結(jié)合，計(jì)算DPC算法中的局部密度值ρi以及截?cái)嗑嚯xdc。

（二）簇類中心的選擇

根據(jù)簇類中心的兩個(gè)基本特點(diǎn)，考慮構(gòu)建綜合變量ri從而選取簇類中心。

γi值越大表示數(shù)據(jù)點(diǎn)越有可能成為數(shù)據(jù)中心點(diǎn)。因此只需對(duì)γ值進(jìn)行降序排列，從前往后截取K個(gè)數(shù)據(jù)點(diǎn)作為簇類中心。

（三）算法描述

本文提出k近鄰密度峰值聚類算法，有效改進(jìn)了DPC算法的不足，以下是KNN-DPC算法的描述。

輸入：數(shù)據(jù)集D，聚類數(shù)K ，近鄰數(shù)k，敏感系數(shù)

輸出：數(shù)據(jù)點(diǎn)的類標(biāo)簽C

1.計(jì)算數(shù)據(jù)集D的距離矩陣，根據(jù)距離遠(yuǎn)近篩選出每個(gè)數(shù)據(jù)點(diǎn)的k個(gè)最近鄰并計(jì)算截?cái)嗑嚯xdc

2. 計(jì)算D中每個(gè)數(shù)據(jù)點(diǎn)的局部密度ρi和距離δi

3. 計(jì)算綜合變量γi并進(jìn)行降序排序，選擇前K個(gè)數(shù)據(jù)點(diǎn)作為聚類中心

4.對(duì)K個(gè)類中心進(jìn)行標(biāo)簽和對(duì)非聚類中心數(shù)據(jù)點(diǎn)歸類

5.判斷噪聲點(diǎn)，為每個(gè)類計(jì)算平均局部密度上界，若該類的邊界點(diǎn)密度低于平均局部密度上界，則判斷為噪聲點(diǎn)。

三、實(shí)驗(yàn)結(jié)果分析

為了驗(yàn)證本文算法的性能，分別使用人工數(shù)據(jù)集和UCI數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。

（一）人工數(shù)據(jù)集

本文選取了Spiral、Compoud、D31和S1四類人工測(cè)試數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，每個(gè)數(shù)據(jù)集的前兩個(gè)實(shí)驗(yàn)是DPC算法不同的p值取得的聚類結(jié)果，后一個(gè)實(shí)驗(yàn)是本文算法取得的聚類結(jié)果，黑色點(diǎn)表示噪聲點(diǎn)。

從圖1結(jié)果顯示，本文算法能得出符合數(shù)據(jù)集分布和直觀判斷的聚類結(jié)果，能有效識(shí)別任意形狀的數(shù)據(jù)集。對(duì)于Spiral、D31、S1三個(gè)數(shù)據(jù)集，DPC算法能取得準(zhǔn)確的簇類中心，且p值越小，噪聲污染越小，聚類效果越好。但是p值并非越小越好，p值越小則決策圖中簇類中心點(diǎn)與其他中心點(diǎn)越難區(qū)分。而對(duì)于Compound數(shù)據(jù)集，DPC算法無(wú)法識(shí)別圓環(huán)中的簇類，而本文算法能準(zhǔn)確識(shí)別圓環(huán)中的簇類。人工數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果顯示，本文算法有效避免DPC算法中截?cái)嗑嚯x難以選取和決策圖中人工選取簇類中心出錯(cuò)的情況，具有更好的聚類效果。

（二）UCI數(shù)據(jù)集

為了驗(yàn)證本文算法在真實(shí)數(shù)據(jù)集上的聚類效果，將本文算法與DPC、K-means和DBSACN算法分別在UCI數(shù)據(jù)集的Iris、Wine、Pima和Sonar四個(gè)UCI數(shù)據(jù)集上進(jìn)行測(cè)試，最后采用F-measure和Purity指標(biāo)進(jìn)行聚類評(píng)價(jià)。

如圖2實(shí)驗(yàn)結(jié)果所示，本文算法較之DPC、K-means和DBSACN算法，在F-measure值和Purity值對(duì)比上，在四個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)效果均優(yōu)于比較算法。綜上所述，本文算法在人工數(shù)據(jù)集上優(yōu)于DPC算法，在真實(shí)數(shù)據(jù)集上的聚類效果均優(yōu)于DPC、K-means和DBSACN，具有更高的聚類精度。

四、結(jié)束語(yǔ)

本文提出一種基于K近鄰的密度峰值聚類算法，使用K近鄰思想計(jì)算局部密度，克服了截?cái)嗑嚯x對(duì)密度計(jì)算的影響。其次截?cái)嗑嚯x通過(guò)k近鄰值計(jì)算得出，避免了人為設(shè)定的缺陷，最后通過(guò)綜合變量來(lái)選取簇類中心，避免了決策圖人工選取簇類中心的主觀性。人工數(shù)據(jù)集和UCI真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明，KNN-DPC算法能準(zhǔn)確識(shí)別簇類中心，能發(fā)現(xiàn)任意形狀的簇類，具有更高的聚類精度。然而如何合理確定KNN-DPC算法中近鄰樣本數(shù)需要更進(jìn)一步的研究。

參考文獻(xiàn)：

[1]R.Xu，I.Wunsch D，Survey of clustering algorithms[J]，Neur. Netw.IEE Trans.2005，16（3）：645-678

[2]A.K.Jain.Data clustering：50 years beyond k-means[J]，Pattern Recognit.Lett.2010，31（8）：651-666

[3]A.Rodriguez，A.Laio.Clustering by fast search and find of densitypeaks[J]，Science.2014，344（6191）：1496

[4] Liu Yaohui，Ma Zhengming，Yu Fang.Adaptive density peak clustering based on K-nearest neighbors with aggregating strategy.[J]， Knowledge-Based Systems.2017.133：208-220

[5] Vidar V.Vikjord，Robert Jenssen.Information theroretic clustering using a k-nearest neighbors approach[J]，Pattern Recognition.2014，47（9）：3070-3081

作者簡(jiǎn)介：

曾嘉豪（1992-），男，籍貫：廣東， 學(xué)歷：碩士研究生，研究方向：聚類分析。