吳辰文 蔣雨璠 馬寧

摘要：密度峰值聚類算法（DPC）是一種基于密度的高效聚類算法，該算法指定參數(shù)少、聚類速度快、能發(fā)現(xiàn)非球形簇狀等優(yōu)點(diǎn)，但傳統(tǒng)DPC算法截?cái)嗑嚯x參數(shù)的選取需要人工干預(yù)，且剩余數(shù)據(jù)點(diǎn)的標(biāo)簽分配易受“多米諾”連鎖效應(yīng)影響。針對(duì)這些問題，提出了結(jié)合KNN和圖標(biāo)簽傳播的密度峰值聚類算法（DPC-NNLP），該方法在KNN思想的基礎(chǔ)上來計(jì)算各樣本數(shù)據(jù)點(diǎn)的局部密度值，通過KNN算法形成的最近鄰點(diǎn)構(gòu)造局部密度主干區(qū)域，并運(yùn)用基于密度的KNN圖將標(biāo)簽分配給剩余的點(diǎn)以形成最終的簇。該算法考慮了各數(shù)據(jù)點(diǎn)間的相關(guān)性，可以有效地對(duì)各種形狀和密度差異性較大的數(shù)據(jù)進(jìn)行聚類。在多個(gè)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)仿真，經(jīng)過對(duì)比驗(yàn)證，該文提出的密度峰值聚類算法在多數(shù)情況下聚類效果要優(yōu)于其他的算法。

關(guān)鍵詞：數(shù)據(jù)聚類;密度峰值;KNN算法;標(biāo)簽傳播

中圖分類號(hào)：TP301.6

DOI：10.16152/j.cnki.xdxbzr.2020-06-014

Density peak clustering algorithm combinedwith KNN and label propagation

WU Chenwen， JIANG Yufan， MA Ning

（School of Electronic and Information Engineering， Lanzhou Jiaotong University， Lanzhou 730070， China）

Abstract： The density peak clustering algorithm （clustering by fast search and find of density peaks， DPC） is an efficient density-based clustering algorithm， which owns the advantages of less specific parameters， fast clustering speed， and can find non-spherical clusters. However， all the traditional DPC algorithms have the defects that the selection of truncated distance parameters needs manual intervention， and the label allocation of the remaining data points is vulnerable to the "Domino" linkage effect and so on. To solve these problems，? a density peak clustering algorithm （density peak clustering algorithm combined with KNN and label propagation， DPC-NNLP） that combines KNN and graph label propagation is proposed. This method calculates the local density values of each sample data point on the basis of the idea. The local density backbone region is constructed by the nearest neighbor points formed by the KNN algorithm. The label is assigned to the remaining points to form the final cluster by using the density-based KNN graph. This algorithm considers the correlation between the data points and can effectively cluster the data with different shapes and densities. Experimental simulation is carried out on multiple data sets. The results show that the density peak clustering algorithm is better than other algorithms in most cases.

Key words： data clustering; density peak; KNN algorithm; label propagation

聚類算法作為數(shù)據(jù)挖掘技術(shù)的一項(xiàng)重要的技術(shù)手段， 應(yīng)用十分廣泛。 因其算法無需任何先驗(yàn)知識(shí)， 即可將數(shù)據(jù)組織、 聚集為多個(gè)組， 且各組組內(nèi)具有相同特性、 組間又具有不同特性。 由于其特有的優(yōu)勢(shì)及高效的計(jì)算能力， 現(xiàn)在已成功運(yùn)用在多個(gè)系統(tǒng)領(lǐng)域， 如生物信息學(xué)［1-2］、 工業(yè)發(fā)展［3］、 網(wǎng)絡(luò)安全［4］、 圖像處理［5］、 醫(yī)學(xué)診斷［6］等。

到目前為止，已經(jīng)有多種聚類算法被提出，其中在2014年Rodriguez和Laiozai在Science上提出的一種基于密度的聚類算法（clustering by fast search and find of density peaks，DPC）［7］，由于該算法具有原理簡單、能夠快速發(fā)現(xiàn)任意形狀的簇、且無需迭代的優(yōu)點(diǎn)，在近幾年一直是熱門研究課題。雖然密度峰值聚類算法具有很多的優(yōu)點(diǎn)，但該算法的缺點(diǎn)也很突出。DPC算法主要存在以下幾個(gè)方面的不足：①算法中一項(xiàng)重要參數(shù)截?cái)嗑嚯x的取值難以確定，一般主要依靠人工進(jìn)行選取，缺乏客觀的選擇依據(jù);②聚類中心的選取也依靠主觀經(jīng)驗(yàn)人為干預(yù)，導(dǎo)致主觀性較強(qiáng)，且聚類結(jié)果的準(zhǔn)確性得不到保障;③在算法識(shí)別出數(shù)據(jù)的密度峰值點(diǎn)后，即將每個(gè)剩余點(diǎn)分配給密度較高且相近的點(diǎn)，這樣的分配策略會(huì)導(dǎo)致數(shù)據(jù)點(diǎn)一旦錯(cuò)誤分配后誤差的傳播，產(chǎn)生“多米諾效應(yīng)”。

基于上述背景，本文提出了結(jié)合KNN和圖標(biāo)簽傳播的密度峰值聚類算法（density peak clustering algorithm combined with KNN and label propagation，DPC-NNLP），算法主要結(jié)合K最近鄰算法［8］（K-nearest neighbor， KNN）加以圖標(biāo)簽傳播的聚類算法，旨在解決上述所提到的DPC算法的相關(guān)缺陷與不足，通過KNN算法構(gòu)建數(shù)據(jù)樣本間的聯(lián)系，形成數(shù)據(jù)點(diǎn)之間的鄰居網(wǎng)絡(luò)，提高結(jié)點(diǎn)間的關(guān)聯(lián)性，準(zhǔn)確計(jì)算各數(shù)據(jù)點(diǎn)的局部密度，并通過使用圖標(biāo)簽傳播進(jìn)行剩余點(diǎn)的精準(zhǔn)分配形成最終的簇。

1 相關(guān)工作

近年來將K近鄰的思想引入到DPC算法中是一個(gè)研究重心，在2015年Lan［9］等人開發(fā)了一種基于查找密度峰值的新算法，以優(yōu)化K均值的初始中心證明DPC算法是用于選擇初始中心的一種有價(jià)值的方法;2016年謝娟英［10］等人為了克服傳統(tǒng)DPC算法中樣本局部密度定義及在分配策略中的缺陷，提出了一種K近鄰優(yōu)化密度峰值聚類算法，該算法在DPC中引入了K近鄰的思想，利用數(shù)據(jù)樣本點(diǎn)的K近鄰信息定義樣本的局部密度進(jìn)行樣本密度峰值的搜索;同年，Du［11］等人為了克服傳統(tǒng)DPC算法未考慮數(shù)據(jù)的局部結(jié)構(gòu)的問題，提出了一種K最近鄰的密度峰值聚類算法，該算法在DPC中引入了K最近鄰的思想，并在此基礎(chǔ)上引入了主成分分析實(shí)現(xiàn)了對(duì)高維數(shù)據(jù)的準(zhǔn)確聚類，增強(qiáng)了算法精度;2017年Yao［12］等人提出了一種自適應(yīng)聚類算法，引入K最近鄰的思想來計(jì)算截?cái)嗑嚯x參數(shù)和局部密度，算法僅需要一個(gè)參數(shù)，整體的聚類過程避免了主觀因素;2018年杜沛［13］等人提出了一種基于K近鄰的比較密度峰值聚類算法，該算法重新定義了截?cái)嗑嚯x和樣本局部密度的度量方式，改進(jìn)后的計(jì)算方式更貼合數(shù)據(jù)的真實(shí)分布，在準(zhǔn)確率上得到有效提高。大部分論文均應(yīng)用截?cái)嗑嚯x參數(shù)來進(jìn)行密度估計(jì)，對(duì)此，本文采用文獻(xiàn)［11］引入的局部密度度量方法來進(jìn)行密度的計(jì)算，該方法可以有效、準(zhǔn)確地識(shí)別聚類中心。

同時(shí)， 針對(duì)于密度峰值聚類算法的密度度量標(biāo)準(zhǔn)也是各研究學(xué)者的重心， 在2017年Ding［14］等人提出了一種基于模糊熵概念的密度峰聚類算法， 針對(duì)數(shù)據(jù)類別或數(shù)值相關(guān)屬性， 提出了一種新的相似性度量標(biāo)準(zhǔn)， 并且為了避免分類和數(shù)值之間的特征轉(zhuǎn)換和參數(shù)調(diào)整， 提出了一種新的相似性度量， 以重新定義數(shù)據(jù)點(diǎn)的局部密度， 提高了算法的魯棒性;同年， 王飛［15］等人針對(duì)于DPC算法大型數(shù)據(jù)集有效聚類的問題， 提出了一種基于網(wǎng)格的新算法， 稱為基于網(wǎng)格的密度峰值聚類算法。 在計(jì)算局部密度時(shí)， 引入網(wǎng)格劃分的思想以減少算法的計(jì)算量， 有效地解決了算法運(yùn)行效率問題。

2 結(jié)合KNN和圖標(biāo)簽傳播的密度峰值聚類

本文所提DPC-NNLP算法主要包含3個(gè)步驟：①確定聚類中心;②構(gòu)造局部密度主干;③標(biāo)簽傳播分配剩余點(diǎn)。在第一步中，傳統(tǒng)的DPC算法是通過假設(shè)當(dāng)點(diǎn)i的局部密度ρi以及與較高密度點(diǎn)的最小距離均較大的時(shí)候，點(diǎn)i才有可能被識(shí)別為聚類中心［16］。與傳統(tǒng)的DPC算法不同的是，本文算法主要將KNN的思想引入到局部密度的計(jì)算中，并使用對(duì)參數(shù)不敏感的指數(shù)核來計(jì)算局部密度值。第二步，主要使用一種基于平均密度的閾值控制策略來構(gòu)造局部密度主干區(qū)域。在第三步中，使用一種基于圖標(biāo)簽傳播的方法來分配剩余點(diǎn)，以形成最終的聚類結(jié)果。

3 實(shí)驗(yàn)與分析

本文仿真實(shí)驗(yàn)所使用的計(jì)算硬件配置為Intel Core i7-9750H處理器、 16GB內(nèi)存; 實(shí)驗(yàn)的軟件環(huán)境為Windows 10 64bit操作系統(tǒng)， 采用Matlab R2018a編程環(huán)境。

將本文提出的DPC-NNLP算法與相關(guān)的聚類方法進(jìn)行了對(duì)比，這些算法包括：標(biāo)準(zhǔn)DPC算法、DBSCAN算法和IDPC算法［20］。所用到的數(shù)據(jù)集主要包括D31，R15，F(xiàn)lame和Aggregation 4個(gè)人工數(shù)據(jù)集以及Spectf Heart，Abalone，Wine 3個(gè)實(shí)際數(shù)據(jù)集，數(shù)據(jù)集屬性如表1所示。其中，R15，Aggregation和D31均為二維數(shù)據(jù)集，D31和Abalone數(shù)據(jù)集樣本數(shù)量較多，Spectf Heart，Abalone和Wine均為多維數(shù)據(jù)集。

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

為了對(duì)比聚類結(jié)果，本文使用幾種著名的評(píng)價(jià)指標(biāo)來評(píng)價(jià)各種聚類算法的性能，這些評(píng)價(jià)指標(biāo)包括調(diào)整Rand系數(shù)［21］（adjusted rand index，ARI）和調(diào)整互信息指標(biāo)［22］（adjusted mutual information， AMI）。

Rand系數(shù)［23］（rand index， RI）和調(diào)整Rand系數(shù)都經(jīng)常作為聚類模型的評(píng)價(jià)指標(biāo)。假設(shè)C為實(shí)際類別信息，K為聚類結(jié)果，則RI系數(shù)的定義如下：

RI=a+bCn2 。（8）

其中：a表示在C和K中都屬于同一類別的點(diǎn)對(duì)數(shù)，b表示在C和K中都不屬于同一類別的點(diǎn)對(duì)數(shù);n代表數(shù)據(jù)樣本點(diǎn)的總個(gè)數(shù)，由于Rand系數(shù)的取值范圍只在［0，1］之間，當(dāng)聚類結(jié)果完美匹配時(shí)RI的值為1。為了使RI系數(shù)具有更高的區(qū)分度，本文運(yùn)用了ARI系數(shù)。定義如下：

ARI=RI-E（RI）max（RI）-E（RI）。（9）

其中：ARI的取值范圍為［-1，1］，當(dāng)ARI的值趨近于1的時(shí)候，聚類結(jié)果越接近數(shù)據(jù)集的原始標(biāo)簽。

AMI指標(biāo)是基于互信息MI（mutual information based scores）的一個(gè)概念，同時(shí)也是評(píng)價(jià)聚類方法的一個(gè)著名且廣泛使用的指標(biāo)，通過給定的聚類效果使用信息論來量化其數(shù)據(jù)集真實(shí)標(biāo)簽之間的差異，估計(jì)聚類的質(zhì)量，其定義如下：

AMI=MI-E（MI）max（H（A），H（B）-E（MI）），? （10）

MI（A，B）=∑i∈A，j∈Bp（i，j）logp（i，j）p（i）p（j）。? （11）

其中，A和B分別為同一個(gè)數(shù)據(jù)集使用兩種不同聚類方法得到的類別標(biāo)簽，AMI的取值范圍為［-1，1］，E（MI）為MI的數(shù)學(xué)期望，在當(dāng)AMI的值趨近于1的時(shí)候，聚類效果越好，若完全不同的情況下，AMI值等于-1。

3.2 聚類結(jié)果與分析

將本文所提DPC-NNLP算法及DBSCAN、DPC、IDPC 3種算法在4個(gè)數(shù)據(jù)集上進(jìn)行了聚類效果可視化，其中包括Aggregation，D31，F(xiàn)lame以及Wine數(shù)據(jù)集，效果如圖3所示。對(duì)于Aggregation和Flame兩個(gè)二維數(shù)據(jù)集，由于其類簇間隔較大，樣本的數(shù)據(jù)量較少，聚類相對(duì)簡單，對(duì)于二維的D31數(shù)據(jù)集，由于各簇之間的間隔較緊密，數(shù)據(jù)集的數(shù)據(jù)量較大，易出現(xiàn)錯(cuò)誤聚類的情況。但通過圖3可以看出，對(duì)于D31數(shù)據(jù)集，本文所提出的DPC-NNLP算法的效果均優(yōu)于其他3種算法。

各算法所使用的AMI及ARI指標(biāo)如表3所示。圖4和圖5分別表示了AMI和ARI指標(biāo)的對(duì)比情況。

在Wine數(shù)據(jù)集中共有3個(gè)類簇，除了一個(gè)密度相對(duì)較大的簇，其余兩個(gè)類簇的樣本點(diǎn)分布均比較分散，樣本數(shù)據(jù)點(diǎn)間的密度比較接近，對(duì)于DBSCAN算法由于其算法自身的缺陷出現(xiàn)了數(shù)據(jù)點(diǎn)錯(cuò)誤聚類的情況。同時(shí)，由于傳統(tǒng)DPC算法比較容易形成多個(gè)類簇中心，進(jìn)而影響對(duì)Wine數(shù)據(jù)集的聚類效果。但從圖3可以看出DPC-NNLP算法對(duì)于Wine數(shù)據(jù)集的聚類較明顯，可以準(zhǔn)確選出正確的類簇中心點(diǎn)，聚類效果明顯優(yōu)于其他算法。對(duì)于維度較高的Spectf Heart數(shù)據(jù)集，DPC-NNLP算法聚類效果略有下降，同時(shí)DPC算法以及DBSCAN算法出現(xiàn)了明顯的下滑，該算法還是明顯優(yōu)于其余3種算法。

本文提出的DPC-NNLP算法具備對(duì)初始參數(shù)并不敏感、剩余點(diǎn)的分配較為準(zhǔn)確的特性，而其余算法在其運(yùn)行過程中，總會(huì)有部分參數(shù)需要人工進(jìn)行干預(yù)選取，所以會(huì)出現(xiàn)聚類效果低于本文提出算法的情況。因此，DPC-NNLP算法在聚類質(zhì)量上相較于其他同類算法明顯提升。

4 結(jié)語

本文主要針對(duì)密度峰值聚類算法中無法自動(dòng)確定截?cái)嗑嚯x參數(shù)的問題，以及算法在剩余數(shù)據(jù)點(diǎn)標(biāo)簽分配時(shí)的缺陷，提出了一種結(jié)合KNN和圖標(biāo)簽傳播的密度峰值聚類算法，該算法通過結(jié)合KNN算法并運(yùn)用KNN圖來改進(jìn)密度峰值聚類算法。通過采用DPC-NNLP、IDPC、DPC和DBSCAN算法分別對(duì)UCI數(shù)據(jù)集及人工數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)驗(yàn)證，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比分析，結(jié)果表明本文提出的結(jié)合KNN和圖標(biāo)簽傳播的聚類算法明顯優(yōu)于IDPC、DPC和DBSCAN算法，該算法可以更加準(zhǔn)確的發(fā)現(xiàn)聚類中心點(diǎn)，將非聚類中心點(diǎn)精準(zhǔn)、快速地分配到相應(yīng)的類簇，對(duì)結(jié)構(gòu)復(fù)雜的大規(guī)模數(shù)據(jù)處理性能更好，下一步的研究目標(biāo)是如何剔除噪聲點(diǎn)及異常點(diǎn)的檢測。

參考文獻(xiàn)：

［1］ WEI D， JIANG Q S， WEI Y J， et al. A novel hierarchical clustering algorithm for gene sequences［J］. BMC Bioinformatics， 2012， 13：174.

［2］ WANG F， ZHOU J Y， TIAN Y， et al. Intradialytic blood pressure pattern recognition based on density peak clustering［J］. Journal of Biomedical Informatics， 2018， 83： 33-39.

［3］ 程啟明， 張強(qiáng)， 程尹曼，等. 基于密度峰值層次聚類的短期光伏功率預(yù)測模型［J］. 高電壓技術(shù)， 2017， 43（4）： 1214-1222.

CHENG Q M， ZHANG Q， CHENG Y M， et al. A short-term photovoltaic power prediction model based on density peak hierarchy clustering［J］.High Voltage Techology，2017，43（4）：1214-1222.

［4］ LI T，WANG J W. Research on network intrusion detection systembasedonimproved K-means clustering algorithm［C］∥2009 International Forum on Computer Science-Technology and Applications. IEEE， 2009：76-79.

［5］ SULAIMAN S N， ISA N A M. Adaptive fuzzy-K-means clustering algorithm for image segmentation［J］.IEEE Transactions on Consumer Electronics， 2010， 56（4）： 2661-2668.

［6］ 張宜， 謝娟英， 李靜， 等. 紅斑鱗狀皮膚病的聚類分析［J］.濟(jì)南大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2017，31（3）：181-187.

ZHANG Y， XIE J Y， LI J， et al. Clustering analysis of erythematous scaly skin diseases ［J］.Journal of Jinan University： Natural Science Edition，2017，31（3）：181-187.

［7］ RODRIGUEZ A， LAIO A. Clustering by fast search and find of density peaks［J］.Science， 2014， 344（6191）： 1492-1496.

［8］ LAAKSONEN J， OJA E. Classification with learning k-nearest neighbors［C］∥Proceedings of International Conference on Neural Networks.IEEE， 1996：1480-1483.

［9］ LAN X， LI Q， ZHENG Y. Density K-means： A new algorithm for centersinitializationfor K-means［C］∥IEEE International Conference on Software Engineering and Service Science （ICSESS）. IEEE， 2015： 958-961.

［10］謝娟英， 高紅超， 謝維信. K 近鄰優(yōu)化的密度峰值快速搜索聚類算法［J］.中國科學(xué)： 信息科學(xué)， 2016， 46（2）： 258-280.

XIE J Y， GAO H C， XIE W X. Quick search clustering algorithm for kneighbor optimization of density peak ［J］.Science of China： Information Science，2016，46（2）：258-280.

［11］DU M J， DING S F， JIA H J. Study on density peaks clustering based on K-nearest neighbors and principal component analysis［J］.Knowledge-Based Systems， 2016， 99： 135-145.

［12］LIU Y H，MA Z M，YU F. Adaptive density peak clustering based on K-nearest neighbors with aggregating strategy［J］.Knowledge-Based Systems， 2017， 133： 208-220.

［13］杜沛， 程曉榮. 一種基于 K 近鄰的比較密度峰值聚類算法［J］.計(jì)算機(jī)工程與應(yīng)用， 2019， 55（10）： 161-168.

DU P， CHENG X R . A comparison density peak clustering algorithm based on K-nearest neighbors［J］.Computer Engineering and Applications，2019，55（10）：161-168.

［14］DING S F， DU M J， SUN T F， et al. An entropy-based density peaks clustering algorithm for mixed type data employing fuzzy neighborhood［J］.Knowledge-Based Systems， 2017， 133： 294-313.

［15］王飛， 王國胤， 李智星， 等. 一種基于網(wǎng)格的密度峰值聚類算法［J］. 小型微型計(jì)算機(jī)系統(tǒng)， 2017，38（5）： 1034-1038.

WANG F， WANG G Y， LI Z X， et al. A grid-based density peak clustering algorithm［J］.Journal of Chinese Computer Systems，2017，38（5）：1034-1038.

［16］XU X， DING S F， SHI Z Z. An improved density peaks clustering algorithm with fast finding cluster centers［J］.Knowledge-Based Systems， 2018， 158： 65-74.

［17］SRIVASTAV N， HINTON G， KRIZHEVSKY A， et al. Dropout： A simple way to prevent neural networks from overfitting［J］.Journal of Machine Learning Research， 2014，15（1）：1929-1958.

［18］ HINTON G E， SRIVASTAVA N， KRIZHEVSKY A， et al. Improving neural networks by preventing co-adaptation of feature detectors［EB／OL］.2012：arXiv：1207.0580［cs.NE］.https：∥arxiv.org／abs／1207.0580.

［19］JEBARA T， WANG J， CHANG S F. Graph construction and b-matching for semi-supervised learning［C］∥Proceedings of the 26th Annual International Conference on Machine Learning.New York：ACM，2009：441-448.

［20］LOTFI A， SEYEDI S A， MORADI P. An improved density peaks method for data clustering［C］∥2016 6th International Conference on Computer and Knowledge Engineering （ICCKE）. IEEE， 2016： 263-268.

［21］HUBERT L， ARABIE P. Comparing partitions［J］.Journal of Classification， 1985， 2（1）： 193-218.

［22］PFITZNER D， LEIBBRANDT R， POWERS D. Characterization and evaluation of similarity measures for pairs of clusterings［J］.Knowledge and Information Systems， 2009， 19（3）： 361-394.

［23］RAND W M. Objective criteria for the evaluation of clustering methods［J］.Journal of the American Statistical Association， 1971， 66（336）： 846-850.

（編 輯 李 靜）