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

摘 要：2014年6月發表在Science的密度峰值聚類算法（DPC）是基于密度的新型聚類算法，算法不需要迭代過程，具有更高效率。但是DPC算法計算密度時人為設定截斷距離和人工選取簇類中心帶有主觀因素，因此本文提出一種基于K近鄰的密度峰值聚類算法。首先根據k近鄰思想計算截斷距離和樣本點的局部密度值，然后通過綜合變量的排序選取簇類中心，最后將剩余的數據點劃分到適當的簇類并進行噪聲點檢測。在人工測試數據集和UCI真實數據集的實驗顯示，基于K近鄰的密度峰值聚類算法的聚類結果優于DPC算法以及經典算法K-means和DBSCAN。

關鍵詞：密度峰值；K近鄰；局部密度；截斷距離；聚類

引言

聚類主要用作無監督學習方法，是數據挖掘的一項主要技術。聚類方法包括劃分聚類、分層聚類、基于密度的聚類、基于網格的聚類、基于模型的聚類或這些方法的組合。K-means是一種經典的劃分聚類方法，K-means無法識別任意形狀的簇。DBSCAN是一種基于密度的聚類方法，可以檢測任意形狀的聚類，但是閥值的選擇依賴經驗知識。

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

DPC算法雖然簡單高效，但是存在以下不足：截斷距離的選取影響密度的計算和噪聲點的檢測，人為設定截斷距離影響聚類結果；人工判斷簇類中心帶有主觀因素，降低算法的魯棒性。針對DPC算法的不足，本文提出基于K近鄰的密度峰值聚類算法（KNN-DPC），首先根據k近鄰思想計算截斷距離和樣本點的局部密度值，然后通過綜合變量的排序選取簇類中心，最后將剩余的數據點劃分到適當的簇類并進行噪聲點檢測。實驗證明本文算法較之DPC算法、K-means算法和DBSCAN具有更優的聚類結果。

一、DPC算法

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

對于剩余數據樣本點，DPC算法將其歸并到密度比其大且距其最近的簇類。

雖然DPC算法能簡單高效的處理聚類問題，但是DPC算法中局部密度值的計算和噪聲點的判斷依賴截斷距離，人為設定的截斷距離使得聚類結果差異很大，而且人工選取簇類中心會出錯的可能性。

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

（一） K近鄰思想

對于基于k近鄰的局部密度計算，更容易區分核心區域中的點與其他領域的點，有助于聚類獲得更準確的結果。因此本文將k近鄰思想與DPC聚類算法相結合，計算DPC算法中的局部密度值ρi以及截斷距離dc。

（二）簇類中心的選擇

根據簇類中心的兩個基本特點，考慮構建綜合變量ri從而選取簇類中心。

γi值越大表示數據點越有可能成為數據中心點。因此只需對γ值進行降序排列，從前往后截取K個數據點作為簇類中心。

（三）算法描述

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

輸入：數據集D，聚類數K ，近鄰數k，敏感系數

輸出：數據點的類標簽C

1.計算數據集D的距離矩陣，根據距離遠近篩選出每個數據點的k個最近鄰并計算截斷距離dc

2. 計算D中每個數據點的局部密度ρi和距離δi

3. 計算綜合變量γi并進行降序排序，選擇前K個數據點作為聚類中心

4.對K個類中心進行標簽和對非聚類中心數據點歸類

5.判斷噪聲點，為每個類計算平均局部密度上界，若該類的邊界點密度低于平均局部密度上界，則判斷為噪聲點。

三、實驗結果分析

為了驗證本文算法的性能，分別使用人工數據集和UCI數據集進行實驗。

（一）人工數據集

本文選取了Spiral、Compoud、D31和S1四類人工測試數據進行實驗，每個數據集的前兩個實驗是DPC算法不同的p值取得的聚類結果，后一個實驗是本文算法取得的聚類結果，黑色點表示噪聲點。

從圖1結果顯示，本文算法能得出符合數據集分布和直觀判斷的聚類結果，能有效識別任意形狀的數據集。對于Spiral、D31、S1三個數據集，DPC算法能取得準確的簇類中心，且p值越小，噪聲污染越小，聚類效果越好。但是p值并非越小越好，p值越小則決策圖中簇類中心點與其他中心點越難區分。而對于Compound數據集，DPC算法無法識別圓環中的簇類，而本文算法能準確識別圓環中的簇類。人工數據集的實驗結果顯示，本文算法有效避免DPC算法中截斷距離難以選取和決策圖中人工選取簇類中心出錯的情況，具有更好的聚類效果。

（二）UCI數據集

為了驗證本文算法在真實數據集上的聚類效果，將本文算法與DPC、K-means和DBSACN算法分別在UCI數據集的Iris、Wine、Pima和Sonar四個UCI數據集上進行測試，最后采用F-measure和Purity指標進行聚類評價。

如圖2實驗結果所示，本文算法較之DPC、K-means和DBSACN算法，在F-measure值和Purity值對比上，在四個數據集上的實驗效果均優于比較算法。綜上所述，本文算法在人工數據集上優于DPC算法，在真實數據集上的聚類效果均優于DPC、K-means和DBSACN，具有更高的聚類精度。

四、結束語

本文提出一種基于K近鄰的密度峰值聚類算法，使用K近鄰思想計算局部密度，克服了截斷距離對密度計算的影響。其次截斷距離通過k近鄰值計算得出，避免了人為設定的缺陷，最后通過綜合變量來選取簇類中心，避免了決策圖人工選取簇類中心的主觀性。人工數據集和UCI真實數據集的實驗結果表明，KNN-DPC算法能準確識別簇類中心，能發現任意形狀的簇類，具有更高的聚類精度。然而如何合理確定KNN-DPC算法中近鄰樣本數需要更進一步的研究。

參考文獻：

[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

作者簡介：

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