混合的密度峰值聚類(lèi)算法

王軍 周凱 程勇

摘 要：密度峰值聚類(lèi)（DP）算法是一種新的基于密度的聚類(lèi)算法，當(dāng)它處理的單個(gè)聚類(lèi)包含多個(gè)密度峰值時(shí)，會(huì)將每個(gè)不同密度峰值視為潛在聚類(lèi)中心，以致難以在數(shù)據(jù)集中確定正確數(shù)量聚類(lèi)，為此，提出一種混合的密度峰值聚類(lèi)算法C-DP。首先，以密度峰值點(diǎn)為初始聚類(lèi)中心將數(shù)據(jù)集劃分為子簇;然后，借鑒代表點(diǎn)層次聚類(lèi)算法（CURE），從子簇中選取分散的代表點(diǎn)，將擁有最小距離的代表點(diǎn)對(duì)的類(lèi)進(jìn)行合并，引入?yún)?shù)收縮因子以控制類(lèi)的形狀。仿真實(shí)驗(yàn)結(jié)果表明，在4個(gè)合成數(shù)據(jù)集上C-DP算法比DP算法聚類(lèi)效果更好;在真實(shí)數(shù)據(jù)集上的Rand Index 指標(biāo)對(duì)比表明，在數(shù)據(jù)集S1上，C-DP算法比DP算法性能提高了2.32%，在數(shù)據(jù)集4k2_far上，C-DP算法比DP算法性能提高了1.13%。由此可見(jiàn)，C-DP算法在單個(gè)類(lèi)簇中包含多密度峰值的數(shù)據(jù)集中能提高聚類(lèi)的準(zhǔn)確性。

關(guān)鍵詞：密度峰值;層次聚類(lèi);類(lèi)合并;代表點(diǎn);收縮因子

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

文獻(xiàn)標(biāo)志碼：A

Abstract： As a new density-based clustering algorithm， clustering by fast search and find of Density Peaks （DP） algorithm regards each density peak as a potential clustering center when dealing with a single cluster with multiple density peaks， therefore it is difficult to determine the correct number of clusters in the data set. To solve this problem， a mixed density peak clustering algorithm namely C-DP was proposed. Firstly， the density peak points were considered as the initial clustering centers and the dataset was divided into sub-clusters. Then， learned from the Clustering Using Representatives algorithm （CURE）， the scattered representative points were selected from the sub-clusters， the clusters of the representative point pairs with the smallest distance were merged， and a parameter contraction factor was introduced to control the shape of the clusters. The experimental results show that the C-DP algorithm has better clustering effect than the DP algorithm on four synthetic datasets. The comparison of the Rand Index indicator on real datasets shows that on the dataset S1 and 4k2_far， the performance of C-DP is 2.32% and 1.13% higher than that of the DP. It can be seen that the C-DP algorithm improves the accuracy of clustering when datasets contain multiple density peaks in a single cluster.

Key words： density peak; hierarchical clustering; class merging; representative point; contraction factor

0 引言

聚類(lèi)是將數(shù)據(jù)組織到不同的類(lèi)中以尋找數(shù)據(jù)的固有隱藏模式的無(wú)監(jiān)督學(xué)習(xí)方法[1]。聚類(lèi)用途廣泛，可以應(yīng)用于圖像處理[2]、模式識(shí)別[3]、生物信息學(xué)[4]、微陣列分析[5]和社交網(wǎng)絡(luò)[6]等各個(gè)領(lǐng)域，聚類(lèi)算法可以將更多類(lèi)似的數(shù)據(jù)聚集到同一個(gè)類(lèi)中，而不同的數(shù)據(jù)被組織到不同的類(lèi)中，在數(shù)據(jù)挖掘領(lǐng)域應(yīng)用廣泛[7]。現(xiàn)如今已經(jīng)提出了許多基于不同特征的聚類(lèi)算法，并且可以進(jìn)一步分類(lèi)為基于劃分的聚類(lèi)算法、基于密度的聚類(lèi)算法、基于模型的聚類(lèi)算法、基于層次的聚類(lèi)算法和基于網(wǎng)格的聚類(lèi)算法[8]。

其中基于密度的聚類(lèi)方法在研究人員中廣受歡迎。即使存在噪聲，基于密度的聚類(lèi)算法也可以在大數(shù)據(jù)集中找到任意形狀的聚類(lèi)[9]。基于密度的噪聲應(yīng)用空間聚類(lèi) （Density-Based Spatial Clustering of Applications with Noise，DBSCAN）算法[10]是一種先進(jìn)的基于密度的聚類(lèi)算法，它利用關(guān)于數(shù)據(jù)的最小鄰域來(lái)發(fā)現(xiàn)任意形狀的聚類(lèi);但是，DBSCAN的有效性受到輸入?yún)?shù)選擇的影響[11]。

文獻(xiàn)[12]提出了一種密度峰值聚類(lèi)（clustering by fast search and find of Density Peaks， DP）算法。DP算法以密度峰值來(lái)選擇聚類(lèi)中心，運(yùn)行高效，并且人工干預(yù)較少。DP算法使用了決策圖（Decision Graph）的啟發(fā)式方法來(lái)選擇聚類(lèi)中心。雖然DP算法簡(jiǎn)單高效，但其劣勢(shì)和難點(diǎn)不容小覷： 對(duì)于單個(gè)數(shù)據(jù)集中可能包含多個(gè)密度峰值，而在DP算法中將不同的密度峰值作為潛在的聚類(lèi)中心，這就將原本一個(gè)類(lèi)分成多個(gè)類(lèi)簇，導(dǎo)致聚類(lèi)效果不佳。

針對(duì)這一問(wèn)題，本文提出了一種新的基于密度的聚類(lèi)算法C-DP（mixed Density Peaks clustering algorithm）：先用DP算法對(duì)數(shù)據(jù)集進(jìn)行初始的聚類(lèi)，找到初始聚類(lèi)中心;然后借鑒代表點(diǎn)層次聚類(lèi)（Clustering Using REpresentatives， CURE）算法從初始聚類(lèi)中選取類(lèi)的代表點(diǎn)，對(duì)具有最小距離的代表點(diǎn)對(duì)的類(lèi)進(jìn)行合并，以提高聚類(lèi)質(zhì)量。仿真實(shí)驗(yàn)結(jié)果表明，該算法在合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上可以識(shí)別任意形狀的類(lèi)簇。

1 相關(guān)工作

基于密度的聚類(lèi)算法對(duì)孤立點(diǎn)和噪聲不敏感，可以處理具有不規(guī)則形狀的數(shù)據(jù)并發(fā)現(xiàn)具有任意形狀的聚類(lèi)，聚類(lèi)效果較好[13]。

文獻(xiàn)[12]提出的DP算法利用數(shù)據(jù)集的密度峰值來(lái)找到任意形狀數(shù)據(jù)集的類(lèi)中心，并高效進(jìn)行樣本點(diǎn)歸類(lèi)和噪聲剔除，處理大規(guī)模數(shù)據(jù)集的性能良好。

DP算法屬于密度聚類(lèi)算法中性能較好的，但仍有改善空間，研究人員已經(jīng)針對(duì)DP算法進(jìn)行了大量的優(yōu)化改進(jìn)工作。文獻(xiàn)[14]中結(jié)合DP算法和變色龍（ChAmeleon，CA）算法，提出了一種擴(kuò)展的快速搜索聚類(lèi)算法（Extended fast search clustering algorithm： widely density clusters， no Density Peaks，E-DP），解決了DP算法無(wú)法處理一個(gè)類(lèi)中有多個(gè)密度峰值點(diǎn)的問(wèn)題;雖然與原DP算法相比，該改進(jìn)算法的時(shí)間復(fù)雜度并未增加，但它的運(yùn)算時(shí)間更長(zhǎng)。文獻(xiàn)[15]提出了一種基于支持向量機(jī)（Support Vector Machine，SVM）的新型合并策略算法。該策略首先利用SVM計(jì)算DP算法聚類(lèi)后每?jī)蓚€(gè)類(lèi)之間的反饋值;然后，以反饋值為依據(jù)合并聚類(lèi)，以遞歸方式獲得準(zhǔn)確的聚類(lèi)結(jié)果。該算法的時(shí)間復(fù)雜度較高。文獻(xiàn)[16]提出了一種用于自適應(yīng)選擇聚類(lèi)中心的通過(guò)快速搜索和查找密度峰值的模糊聚類(lèi) （Fuzzy Clustering by Fast Search and Find of Density Peaks， Fuzzy-CFSFDP） 算法，它在DP算法基礎(chǔ)上通過(guò)使用模糊規(guī)則來(lái)確定聚類(lèi)中心點(diǎn)，能提高類(lèi)中心點(diǎn)選取的準(zhǔn)確率，從而提升算法的性能;然而該算法的實(shí)現(xiàn)條件是數(shù)據(jù)集中的每個(gè)類(lèi)有且僅有一個(gè)密度峰值，算法具有局限性。文獻(xiàn)[17]提出了一種具有新的分配策略的領(lǐng)導(dǎo)密度峰值聚類(lèi) （Leading clustering with Density peaks， L-DP）算法，在原有DP算法獲得聚類(lèi)中心后，運(yùn)用一種改進(jìn)的領(lǐng)導(dǎo)聚類(lèi)方法（Leader clustering）作為點(diǎn)分配策略，以此獲得正確的聚類(lèi);然而，該方法沒(méi)有考慮一個(gè)類(lèi)中心有多個(gè)密度峰值的情況，而且該方法假設(shè)聚類(lèi)中心更靠近高密度區(qū)域，實(shí)際上，聚類(lèi)中心也可能靠近低密度區(qū)域。

4 結(jié)語(yǔ)

針對(duì)數(shù)據(jù)集中單個(gè)聚類(lèi)中包含多個(gè)密度峰值，DP算法無(wú)法得到準(zhǔn)確聚類(lèi)結(jié)果的問(wèn)題，本文提出了一種混合的密度峰值聚類(lèi)算法C-DP：受CURE的啟發(fā)，在聚類(lèi)過(guò)程中先用DP算法得到初始聚類(lèi)中心進(jìn)行初始聚類(lèi)，然后從初始類(lèi)中選取類(lèi)的代表點(diǎn)，并引入收縮因子α，然后根據(jù)收縮因子來(lái)移動(dòng)它們，可以很好地控制類(lèi)的形狀。以最小距離度量方法作為類(lèi)間相似性度量標(biāo)準(zhǔn)，不同類(lèi)之間有最近距離代表點(diǎn)對(duì)的兩個(gè)類(lèi)被合并。實(shí)驗(yàn)結(jié)果表明，對(duì)于單個(gè)聚類(lèi)包含多個(gè)密度峰值的數(shù)據(jù)集，C-DP算法與原始的DP算法相比可以更準(zhǔn)確地進(jìn)行聚類(lèi)，而對(duì)于一些只有一個(gè)密度峰值的數(shù)據(jù)集，C-DP算法和原DP算法都能進(jìn)行很好的聚類(lèi)。

然而，C-DP算法與原始的DP算法，在獲取數(shù)據(jù)集的聚類(lèi)中心時(shí)是由用戶(hù)選擇的，這很難準(zhǔn)確判定聚類(lèi)中心。 以后的工作是將C-DP算法擴(kuò)展為完全自適應(yīng)方法。

參考文獻(xiàn)：

[1] CASSISI C， FERRO A， GIUGNO R， et al. Enhancing density-based clustering： Parameter reduction and outlier detection [J]. Information Systems， 2013， 38（3）： 317-330.

[2] LI K， ZHU C Y， LYU Q， et al. Personalized multi-modality image management and search for mobile devices [J]. Personal and Ubiquitous Computing， 2013， 17（8）： 1817-1834.

[3] AHN C-S， OH S-Y. Robust vocabulary recognition clustering model using an average estimator least mean square filter in noisy environments [J]. Personal and Ubiquitous Computing， 2014， 18（6）： 1295-1301.

[4] NICOVICH P R， TABARIN T， STIEGLER J， et al. Analysis of nanoscale protein clustering with quantitative localization microscopy [J]. Biophysical Journal， 2015， 108（2）： 475a.

[5] YEGANOVA L， KIM W， KIM S， et al. Retro： concept-based clustering of biomedical topical sets [J]. Bioinformatics， 2014， 30（22）： 3240-3248.

[6] CHANG M-S， CHEN L-H， HUNG L-J， et al. Exact algorithms for problems related to the densest k-set problem [J]. Information Processing Letters， 2014， 114（9）： 510-513.

[7] JAIN A K， MURTY M N， FLYNN P J. Data clustering： a review [J]. ACM Computing Surveys，1999， 31 （3）： 264-323.

[8] 周濤，陸惠玲.數(shù)據(jù)挖掘中聚類(lèi)算法研究進(jìn)展[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（12）：100-111. （ZHOU T， LU H L. Research progress of clustering algorithms in data mining [J]. Computer Engineering and Applications， 2012， 48（12）： 100-111.）

[9] GENG Y-A， LI Q， ZHENG R， et al. RECOME：a new density-based clustering algorithm using relative KNN kernel density [J]. Information Sciences， 2016， 436/437： 13-30.

[10] 張麗杰.具有穩(wěn)定飽和度的DBSCAN算法[J].計(jì)算機(jī)應(yīng)用研究，2014，31（7）：1972-1975. （ZHANG L J. Stable saturation density of DBSCAN algorithm [J]. Applications Research of Computers， 2014， 31（7）： 1972-1975.）

[11] ZHOU A Y， ZHOU S G， CAO J， et al. Approaches for scaling DBSCAN algorithm to large spatial databases [J]. Journal of Computer Science and Technology， 2000， 15（6）： 509-526.

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

[13] XU J， WANG G， DENG W. DenPEHC： density peak based efficient hierarchical clustering [J]. Information Sciences， 2016， 373： 200-218.

[14] ZHANG W， LI J. Extended fast search clustering algorithm： widely density clusters， no density peaks [EB/OL]. [2018-04-06]. https：//arxiv.org/ftp/arxiv/papers/1505/1505.05610.pdf.

[15]XU X， DING S， XU H， et al. A feasible density peaks clustering algorithm with a merging strategy [J/OL]. Soft Computing， 2018 [2018-03-06]. https：//doi.org/10.1007/s00500-018-3183-0.

[16] MEHMOOD R， BIE R， DAWOOD H， et al. Fuzzy clustering by fast search and find of density peaks [C]// Proceedings of the 2015 International Conference on Identification， Information， and Knowledge in the Internet of Things. Washington， DC： IEEE Computer Society， 2015： 258-261.

[17] DU M， DING S. L-DP： A hybrid density peaks clustering method [C]// DMBD 2017：Proceedings of the 2017 International Conference on Data Mining and Big Data， LNCS 10387. Cham： Springer， 2017： 74-80.

[18] 沈潔，趙雷，楊季文，等.一種基于劃分的層次聚類(lèi)算法[J].計(jì)算機(jī)工程與應(yīng)用，2007，43（31）： 175-177. （SHEN J， ZHAO L， YANG J W， et al. Hierarchical clustering algorithm based on partition [J]. Computer Engineering and Applications， 2007，43（31）：175-177.）

[19] WIWIE C， BAUMBACH J， RTTGER R. Comparing the performance of biomedical clustering methods [J]. Nature Methods， 2015， 12： 1033-1038.