羅軍鋒 鎖志海 郭倩

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

關(guān)鍵詞： 聚類(lèi);密度峰值;局部密度;聚類(lèi)中心;信息熵;K近鄰;截?cái)嗑嚯x;相對(duì)距離

中圖分類(lèi)號(hào)： TP311 ???文獻(xiàn)標(biāo)識(shí)碼： A??? DOI：10.3969/j.issn.1003-6970.2020.07.037

本文著錄格式：羅軍鋒，鎖志海，郭倩. 一種基于k近鄰的密度峰值聚類(lèi)算法[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? 引言

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

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

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

目前，DPC算法研究雖取得了一定的成效，但截?cái)嗑嚯x需要人工輸入、簇心選取及未分配點(diǎn)分配準(zhǔn)確率仍然不高，針對(duì)這些問(wèn)題，因此本文提出一種基于K近鄰的密度峰值聚類(lèi)算法，引入距離信息熵，自動(dòng)計(jì)算截?cái)嗑嚯x，優(yōu)化了聚類(lèi)中心點(diǎn)的選擇算法. 通過(guò)實(shí)驗(yàn)證明，該算法具有更好的聚類(lèi)效果和聚類(lèi)準(zhǔn)確率.

1 ?DPC算法

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

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

步驟1 根據(jù)上述公式和輸入的參數(shù)截?cái)嗑嚯x分別計(jì)算所有數(shù)據(jù)點(diǎn)的局部密度和相對(duì)距離;生成關(guān)系決策圖;

步驟2 根據(jù)關(guān)系決策圖手動(dòng)選取聚類(lèi)中心點(diǎn)。

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

步驟4 對(duì)聚類(lèi)結(jié)果進(jìn)行除噪處理，最后完成聚類(lèi)。

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

2? 基于K近鄰的密度峰值聚類(lèi)算法（KDPC）

本文針對(duì)DPC算法的改進(jìn)主要包括：引入距離熵，改善距離計(jì)算公式;借鑒文獻(xiàn)^[11]中的思想引入K近鄰，來(lái)計(jì)算截?cái)嗑嚯x。下面從算法的基本概念，思想，步驟等分別加以描述。

2.1? 算法基本概念

定義1 對(duì)象p的k距離

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

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

當(dāng)同時(shí)滿(mǎn)足以下條件時(shí)，k-dist（p）等于d（p，o）：

（1）至少存在k個(gè)數(shù)據(jù)對(duì)象滿(mǎn)足

（2）至多存在k-1個(gè)數(shù)據(jù)對(duì)象滿(mǎn)足

定義2 對(duì)象p的k近鄰鄰居

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

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

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

定義4基于k近鄰的截?cái)嗑嚯x如下：

2.2 ?算法的思想

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

其次，我們引入K近鄰以此來(lái)計(jì)選截?cái)嗑嚯x，以防止認(rèn)為指定的不足。

下面是算法的詳細(xì)介紹。

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

具體步驟如下：

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

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

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

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

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

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

2.3 ?算法步驟

改進(jìn)后的算法分三大步驟：

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

（2）根據(jù)公式1計(jì)算截?cái)嗑嚯x;

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

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

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

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

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

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

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

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

上述實(shí)驗(yàn)證明， KDPC算法避免了 DPC 算法需要手動(dòng)經(jīng)驗(yàn)選取合適的截?cái)嗑嚯x的不足， 能夠更準(zhǔn)確地選取數(shù)據(jù)集的聚類(lèi)中心。

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

實(shí)驗(yàn)二選取UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的Test，Wine，Seeds作為實(shí)驗(yàn)數(shù)據(jù)。

實(shí)驗(yàn)方法：分別采用DPC算法，本文算法進(jìn)行實(shí)驗(yàn)。

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

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

實(shí)驗(yàn)結(jié)果：由于傳統(tǒng)的k-means算法對(duì)初始點(diǎn)的選取比較敏感，初始聚類(lèi)中心的隨機(jī)性導(dǎo)致聚類(lèi)準(zhǔn)確率不穩(wěn)定，因此采用運(yùn)算8次后所求的平均準(zhǔn)確率來(lái)判斷，實(shí)驗(yàn)結(jié)果的精確度如表2所示。

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

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

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

參考文獻(xiàn)

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

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

3. 薛小娜， 高淑萍， 彭弘銘， 等. 結(jié)合K近鄰的改進(jìn)密度峰值聚類(lèi)算法[J]. 計(jì)算機(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ù)的密度峰值聚類(lèi)算法[J]. 小型微型計(jì)算機(jī)系統(tǒng)， 2019， 12（12）： 2512-2518.

7. 丁志成， 葛洪偉， 周競(jìng). 基于KL散度的密度峰值聚類(lèi)算法[J]. 重慶郵電大學(xué)學(xué)報(bào)， 2019， 31（3）： 367-374.

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

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

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

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

12. 唐波. 改進(jìn)的K-means 聚類(lèi)算法及應(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.