一種基于k近鄰的密度峰值聚類算法

羅軍鋒 鎖志海 郭倩

摘? 要： 密度峰值聚類算法（DPC算法）雖然具有簡單高效的優(yōu)點，但存在著需要人為確定截斷距離的不足，從而造成聚類結(jié)果出現(xiàn)不準確。為解決這一問題，本文提出了一種基于K近鄰的改進算法。該算法引入信息熵，采用屬性加權(quán)的距離公式進行聚類，這樣就解決了不同屬性的權(quán)重影響問題;在聚類過程中通過計算數(shù)據(jù)點的近鄰密度，再利用KNN近鄰算法實現(xiàn)自動求解截斷距離，據(jù)此得到聚類中心再進行聚類，通過實驗證明，該算法在準確性、運行效率上均有不同程度的提升。

關(guān)鍵詞： 聚類;密度峰值;局部密度;聚類中心;信息熵;K近鄰;截斷距離;相對距離

中圖分類號： TP311 ???文獻標識碼： A??? DOI：10.3969/j.issn.1003-6970.2020.07.037

本文著錄格式：羅軍鋒，鎖志海，郭倩. 一種基于k近鄰的密度峰值聚類算法[J]. 軟件，2020，41（07）：185-188

A Peak Density Clustering Algorithm Based on K-nearest Neighbor

LUO Jun-feng， SUO Zhi-hai， GOU Qian^*

（Net&Information center， xian jiaotong University， Xian 710049， China）

【Abstract】： Although DPC algorithm is simple and efficient， it needs to determine the truncation distance manually， which results in inaccurate clustering results. To solve this problem， an improved algorithm based on K-nearest neighbor is proposed. In this algorithm， information entropy is introduced， and attribute weighted distance formula is used to cluster， which solves the problem of weight influence of different attributes. In the process of clustering， the nearest neighbor density of data points is calculated， and then KNN algorithm is used to automatically solve the truncation distance， and then clustering is obtaine.

【Key words】： Clustering; Density peak; Local density; Clustering center; Information entropy; K-nearest-neighbor; Truncation distance; Relative distance

0? 引言

聚類是數(shù)據(jù)挖掘中重要的課題之一。它是將目標數(shù)據(jù)對象分組為由類似的對象組成的多個族的過程。其目標是同一個族的對象是最大可能的相似，不同族的對象最大可能的不相似。

2014年6月，ARodriguez 和Laio等提出了一種新型密度峰值聚類算法（Density Peaks Clustering，DPC）^[1]，這個算法的主要優(yōu)勢在于其的算法簡單又高效、所需參數(shù)少、能解決各種形狀的簇聚合等。因此該算法得到研究者廣泛關(guān)注，已經(jīng)在多個領(lǐng)域 得到成功應(yīng)用，但DPC算法還存在某些缺點：如需要人工輸入截斷距離、需要依據(jù)決策圖人工選取聚類中心這兩個關(guān)鍵不足。

針對DPC算法的改進，研究者提出了許多的改進方法：賈培靈等^[2]針對某個類存在多個密度峰值導致聚類不理想問題，提出一種基于簇邊界劃分的 DPC 算法，來解決多個密度峰值問題導致的聚類不理想問題;薛小娜等^[3]提出了結(jié)合k近鄰來改進密度峰值聚類算法;WangSL等^[4]提出了一種利用數(shù)據(jù)場的潛在熵來自動提取最優(yōu)值的新方法;Mehmood R等^[5]提出了一種采用非參數(shù)估計給定數(shù)據(jù)集的概率分布，對截斷距離的選擇進行校正。

目前，DPC算法研究雖取得了一定的成效，但截斷距離需要人工輸入、簇心選取及未分配點分配準確率仍然不高，針對這些問題，因此本文提出一種基于K近鄰的密度峰值聚類算法，引入距離信息熵，自動計算截斷距離，優(yōu)化了聚類中心點的選擇算法. 通過實驗證明，該算法具有更好的聚類效果和聚類準確率.

1 ?DPC算法

密度峰值聚類算法^[6-11]是基于以下兩個重要原理：（1）其聚類中心的密度高于其鄰近的樣本點密度;（2）聚類中心與比其密度高的數(shù)據(jù)點的距離相對較遠。

DPC算法的具體步驟描述如下：

步驟1 根據(jù)上述公式和輸入的參數(shù)截斷距離分別計算所有數(shù)據(jù)點的局部密度和相對距離;生成關(guān)系決策圖;

步驟2 根據(jù)關(guān)系決策圖手動選取聚類中心點。

步驟3 將其他數(shù)據(jù)點按照距離最近原則分配到對應(yīng)的聚類中心點。。

步驟4 對聚類結(jié)果進行除噪處理，最后完成聚類。

從上述算法描述中可以看到，參數(shù)對算法的聚類效果影響很大，同時算法在聚類過程中，沒有考慮到數(shù)據(jù)點屬性間的權(quán)重問題，這樣會造成聚類效果出現(xiàn)偏差，本文就是試圖改進DPC算法中的距離公式，同時引入基于k近鄰的的計算方法，以達到改善聚類效果的目的。

2? 基于K近鄰的密度峰值聚類算法（KDPC）

本文針對DPC算法的改進主要包括：引入距離熵，改善距離計算公式;借鑒文獻^[11]中的思想引入K近鄰，來計算截斷距離。下面從算法的基本概念，思想，步驟等分別加以描述。

2.1? 算法基本概念

定義1 對象p的k距離

對于任意一個正整數(shù)k，數(shù)據(jù)對象p的k距離我們記作k-distance （p）.

在數(shù)據(jù)集D中， 數(shù)據(jù)對象o距離數(shù)據(jù)對象p之間的距離，我們記為：d（p，o）。

當同時滿足以下條件時，k-dist（p）等于d（p，o）：

（1）至少存在k個數(shù)據(jù)對象滿足

（2）至多存在k-1個數(shù)據(jù)對象滿足

定義2 對象p的k近鄰鄰居

如果已知數(shù)據(jù)對象p的k距離，那么，數(shù)據(jù)對象p的k近鄰鄰居則就為數(shù)據(jù)集中所有到p的距離小于等于k的數(shù)據(jù)對象的集合，定義如下：

定義3 對象p關(guān)于對象o的近鄰距離

假設(shè)d（p，o）表示數(shù)據(jù)對象d和數(shù)據(jù)對象o之間的距離，那么對象p關(guān)于對象o的近鄰距離計表示為：

定義4基于k近鄰的截斷距離如下：

2.2 ?算法的思想

首先為提高算法聚類的效果，我們對數(shù)據(jù)集中計算數(shù)據(jù)對象距離時采用加權(quán)距離，權(quán)重值的計算使用信息熵來確定。

其次，我們引入K近鄰以此來計選截斷距離，以防止認為指定的不足。

下面是算法的詳細介紹。

一般來說，數(shù)據(jù)集中的各維屬性對聚類結(jié)果的影響程度肯定不同。于是，本文借鑒文獻^[12]，引入信息熵的概念以度量屬性權(quán)重的大小，并進一步求得數(shù)據(jù)對象之間的權(quán)重系數(shù)，最終得到基于熵權(quán)重的距離計算公式。

具體步驟如下：

（1）假設(shè)某個數(shù)據(jù)集X有以下屬性值矩陣，不失一般性，其具有n個對象，m維屬性：

（2）構(gòu)造屬性對應(yīng)的比重矩陣

由于屬性值單位的不同無法直接比較，為了方便比較，我們對屬性值進行了歸一化處理。處理方法如下：

從上述公式中可以得出，相鄰數(shù)據(jù)對象的權(quán)重系數(shù)取決于該對象的所有屬性，由其所有鄰居的屬性共同決定的，因此，在接下來計算數(shù)據(jù)對象間的距離時就盡最大可能、最大限度的考慮了相鄰數(shù)據(jù)對象之間的相互影響及其自身所有屬性的影響。

根據(jù)以上分析，最終不難得出，基于信息熵的加權(quán)距離計算公式為：

利用改進的距離計算公式可以更為準確的計算出各個數(shù)據(jù)對象之間的差距程度，在一定程度上提高了聚類的精確度。

2.3 ?算法步驟

改進后的算法分三大步驟：

（1）根據(jù)公式3的加權(quán)距離公式來計算所有數(shù)據(jù)點的近鄰密度距離矩陣;

（2）根據(jù)公式1計算截斷距離;

（3）計算局部密度和相對距離，同時進行歸一化處理后生成關(guān)系決策圖;

（4）確定聚類中心數(shù)量及聚類中心;

（5）按密度的降序?qū)ζ溆鄶?shù)據(jù)點進行分配。

3? 實驗結(jié)果與分析

為了驗證本算法的性能，我們分別在人工數(shù)據(jù)集和UCI數(shù)據(jù)集上進行了對比實驗。

3.1 ?人工數(shù)據(jù)集實驗結(jié)果分析

在我們的仿真實驗中，使用的數(shù)據(jù)集為如表1所示，實驗的最終效果如圖1所示。

圖1為DPC算法在人工數(shù)據(jù)集上的聚類結(jié)果，圖2為KDPC 算法在人工數(shù)據(jù)集上的聚類結(jié)果。從結(jié)果上看，DPC 算法要得到理想狀態(tài)下的聚類結(jié)果，需要人工的多次嘗試，這是因為截斷距離的合適與否直接影響聚類的效果，因此算法不夠穩(wěn)定。而KDPC算法，自動解決截斷距離的計算問題，能夠較快的得到理想的聚類效果。

上述實驗證明， KDPC算法避免了 DPC 算法需要手動經(jīng)驗選取合適的截斷距離的不足， 能夠更準確地選取數(shù)據(jù)集的聚類中心。

3.2 ?UCI數(shù)據(jù)集實驗結(jié)果分析

實驗二選取UCI機器學習數(shù)據(jù)庫中的Test，Wine，Seeds作為實驗數(shù)據(jù)。

實驗方法：分別采用DPC算法，本文算法進行實驗。

實驗指標：采用調(diào)整蘭德系數(shù)（adjusted rand index）ARI聚類評價指標^[13-14]，該指標結(jié)果值在[-1，1]之間，值越大說明聚類效果越好，其計算公式為：

3.3? RI表示蘭德系數(shù)

實驗結(jié)果：由于傳統(tǒng)的k-means算法對初始點的選取比較敏感，初始聚類中心的隨機性導致聚類準確率不穩(wěn)定，因此采用運算8次后所求的平均準確率來判斷，實驗結(jié)果的精確度如表2所示。

從表中可以看到，改進后的DPC算法準確度比傳統(tǒng)算法提高了接近10個百分點。

4 ?結(jié)束語

本文針對DPC算法的不足，引入信息熵，采用屬性加權(quán)的距離公式進行聚類，這樣就解決了不同屬性的權(quán)重影響問題;在聚類過程中通過計算數(shù)據(jù)點的近鄰密度，再利用KNN近鄰算法實現(xiàn)自動求解截斷距離，據(jù)此得到聚類中心再進行聚類，通過實驗證明，該算法在準確性、運行效率上均有不同程度的提升。

參考文獻

1. Rodriguez A， Laio A. Clustering by fast search and find of density peaks[J]. Science， 2014， 344（6191）： 492-1496.

2. 賈培靈， 樊建聰， 彭延軍. 一種基于簇邊界的密度峰值點快速搜索聚類算法[J]. 南京大學學報（自然科學）， 2017， 53（2）： 368-377 .

3. 薛小娜， 高淑萍， 彭弘銘， 等. 結(jié)合K近鄰的改進密度峰值聚類算法[J]. 計算機工程與應(yīng)用， 2018， 54（7）： 36-43.

4. Wang S L， Wang D K， Li CY et al. Clustering by fast search and find of density peaks with data field[J]. chinese Journal of Elec-tronics， 2015， 25（3）： 397-402.

5. Mehmood R， Bie R， Dawood H， et al. Fuzzy clustering by fast search and find of density peaks[C]//International Conference on Identification， Information and Knowledge in the Internet of Things（ IIKI）， Beijing， China， 2016： 258-261.

6. 趙燕偉， 朱芬， 桂方志， 等. 融合可拓關(guān)聯(lián)函數(shù)的密度峰值聚類算法[J]. 小型微型計算機系統(tǒng)， 2019， 12（12）： 2512-2518.

7. 丁志成， 葛洪偉， 周競. 基于KL散度的密度峰值聚類算法[J]. 重慶郵電大學學報， 2019， 31（3）： 367-374.

8. 王萬良， 吳菲， 呂闖。自動確定聚類中心的快速搜索和發(fā)現(xiàn)密度峰值的聚類算法[J]. 模式識別與人工智能， 2019， 32（11）： 1032-1041.

9. 王軍華， 李建軍， 李俊山， 等. 自適應(yīng)快速搜索密度峰值聚類算法[J]. 計算機工程與應(yīng)用. 2019， 55（24）： 122-127.

10. 王洋， 張桂珠. 自動確定聚類中心的密度峰值算法[J]. 計算機工程與應(yīng)用， 2018， 54（8）： 137-142.

11. 伏坤， 王珣， 劉勇， 等. 基于K近鄰改進密度峰值聚類分析法的巖體結(jié)構(gòu)面產(chǎn)狀優(yōu)勢分組[J]. 水利水電技術(shù)， 2019， 50（11）： 124-130.

12. 唐波. 改進的K-means 聚類算法及應(yīng)用[J]. 軟件， 2012， 3： 036.

13. Vinh N X.Epps J.Bailey J.Information theoretic measures for? clusterings comparison： Is a correction for chance necessary[C]// Proc of the 26th Annual International Conference on Machine Learning. New York： ACM Press， 2009： 1073-1080.

14. Vinh N X.Epps J， Bailey J.Information theoretic measures for clusterings comparison： Variants， properties， normalization and correction for chance[J]. Journal of Machine Learning Research， 2010， 11（1）： 2837-2854.