混合的密度峰值聚類算法

王軍 周凱 程勇

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

關鍵詞：密度峰值;層次聚類;類合并;代表點;收縮因子

中圖分類號： TP301.6

文獻標志碼：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 引言

聚類是將數據組織到不同的類中以尋找數據的固有隱藏模式的無監督學習方法[1]。聚類用途廣泛，可以應用于圖像處理[2]、模式識別[3]、生物信息學[4]、微陣列分析[5]和社交網絡[6]等各個領域，聚類算法可以將更多類似的數據聚集到同一個類中，而不同的數據被組織到不同的類中，在數據挖掘領域應用廣泛[7]。現如今已經提出了許多基于不同特征的聚類算法，并且可以進一步分類為基于劃分的聚類算法、基于密度的聚類算法、基于模型的聚類算法、基于層次的聚類算法和基于網格的聚類算法[8]。

其中基于密度的聚類方法在研究人員中廣受歡迎。即使存在噪聲，基于密度的聚類算法也可以在大數據集中找到任意形狀的聚類[9]?；诿芏鹊脑肼晳每臻g聚類 （Density-Based Spatial Clustering of Applications with Noise，DBSCAN）算法[10]是一種先進的基于密度的聚類算法，它利用關于數據的最小鄰域來發現任意形狀的聚類;但是，DBSCAN的有效性受到輸入參數選擇的影響[11]。

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

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

1 相關工作

基于密度的聚類算法對孤立點和噪聲不敏感，可以處理具有不規則形狀的數據并發現具有任意形狀的聚類，聚類效果較好[13]。

文獻[12]提出的DP算法利用數據集的密度峰值來找到任意形狀數據集的類中心，并高效進行樣本點歸類和噪聲剔除，處理大規模數據集的性能良好。

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

4 結語

針對數據集中單個聚類中包含多個密度峰值，DP算法無法得到準確聚類結果的問題，本文提出了一種混合的密度峰值聚類算法C-DP：受CURE的啟發，在聚類過程中先用DP算法得到初始聚類中心進行初始聚類，然后從初始類中選取類的代表點，并引入收縮因子α，然后根據收縮因子來移動它們，可以很好地控制類的形狀。以最小距離度量方法作為類間相似性度量標準，不同類之間有最近距離代表點對的兩個類被合并。實驗結果表明，對于單個聚類包含多個密度峰值的數據集，C-DP算法與原始的DP算法相比可以更準確地進行聚類，而對于一些只有一個密度峰值的數據集，C-DP算法和原DP算法都能進行很好的聚類。

然而，C-DP算法與原始的DP算法，在獲取數據集的聚類中心時是由用戶選擇的，這很難準確判定聚類中心。 以后的工作是將C-DP算法擴展為完全自適應方法。

參考文獻：

[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] 周濤，陸惠玲.數據挖掘中聚類算法研究進展[J].計算機工程與應用，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] 張麗杰.具有穩定飽和度的DBSCAN算法[J].計算機應用研究，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] 沈潔，趙雷，楊季文，等.一種基于劃分的層次聚類算法[J].計算機工程與應用，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.