基于自適應可達距離的密度峰值聚類算法

章曼，張正軍，馮俊淇，嚴濤

基于自適應可達距離的密度峰值聚類算法

章曼*，張正軍，馮俊淇，嚴濤

（南京理工大學 理學院，南京 210094）（* 通信作者電子郵箱1277167538@qq.com）

針對基于快速搜索和發現密度峰值的聚類（CFSFDP）算法中截斷距離需要人工選取，以及最近鄰分配帶來的誤差導致的在具有不同密度簇的復雜數據集上的聚類效果不佳的問題，提出了一種基于自適應可達距離的密度峰值聚類（ARD-DPC）算法。該算法利用非參數核密度估計方法計算點的局部密度，根據決策圖選取聚類中心，并利用自適應可達距離分配數據點，從而得到最終的聚類結果。在4個合成數據集和6個UCI數據集上進行了仿真實驗，將所提算法ARD-DPC與基于快速搜索和發現密度峰值的聚類（CFSFDP）、基于密度的噪聲應用空間聚類（DBSCAN）、基于密度自適應距離的密度峰聚類（DADPC）算法進行了比較，實驗結果表明，相比其他三種算法，ARD-DPC算法在7個數據集上的標準化互信息（NMI）、蘭德指數（RI）和F1-measure取得了最大值，在2個數據集分別取得F1-measure和NMI的最大值，只對模糊度較高、聚類特征不明顯的Pima數據集聚類效果不佳；同時，ARD-DPC算法在合成數據集上能準確地識別出聚類數目和具有復雜密度的簇。

聚類算法；密度峰值；截斷距離；非參數核密度估計；自適應可達距離

0 引言

聚類是數據挖掘和機器學習研究領域中最重要的數據預測和數據分析方法之一。聚類是一種無監督學習方法，目的是使得同一類簇中的元素之間盡可能地相似，而不同類簇中的元素之間盡可能地相異。聚類分析已被廣泛用于許多學科領域，涵蓋天文學、生物信息學、文獻計量學以及模式識別。

隨著聚類分析技術的不斷發展，研究者們根據實際需要已經提出了許多聚類方法。比如：基于劃分的方法，有均值算法（-means）［1］和-中心點算法（-medoids）［2］；基于層次的方法，有利用層次方法的平衡迭代規約和聚類（Balanced Iterative Reducing and Clustering using Hierarchies， BIRCH）［3］和使用動態建模的層次聚類Chameleon［4］；基于密度的方法，有基于密度的噪聲應用空間聚類（Density-Based Spatial Clustering of Applications with Noise， DBSCAN）［5］和用于識別聚類的排序點（Ordering Points To identify the Clustering Structure ，OPTICS）［6］。不同的聚類算法能很好地解決某些特定的問題，但總體上仍然存在許多亟待解決的問題，比如聚類效果受數據分布影響較大、復雜度高、聚類數量需要人工干預、聚類效果難以評價等。

2014年，Rodriguez等［7］提出了基于快速搜索和發現密度峰值的聚類（Clustering by Fast Search and Find of Density Peaks， CFSFDP）算法。在算法聚類過程中，聚類的數目會直觀地產生，噪聲點會自動地被發現并排除在分析之外，而且不管聚類的形狀和嵌入空間的維數如何，聚類都會被識別出來。

為了克服這一局限性，已有不少改進算法被提出。如Hou等［8］提出了一種新的局部密度估計方法，該方法僅采用最近鄰來估計密度。Mehmood等［9］提出了通過熱擴散快速搜索和發現密度峰值聚類（Clustering by Fast Search and Find of Density Peaks via Heat Diffusion， CFSFDP-HD）算法。該算法結合了截斷距離選擇和核密度估計的邊界校正以便更好地估計密度，從而得到更精確的聚類效果，更有效地將聚類點的噪聲分離出來。謝國偉等［10］提出了基于非參數核密度估計的密度峰值聚類算法。該算法運用了非參數核密度估計方法來計算數據點的局部密度，避免了截斷距離的選取。李濤等［11］提出了基于密度自適應距離的密度峰聚類（Density Peaks Clustering based on Density Adaptive distance，DADPC）算法。該算法基于歐氏距離和自適應相似度，提出了密度自適應距離，能有效地處理簇內同時具有多個密度峰或簇內密度分布相對均勻的復雜結構數據集。

本文提出了一種基于自適應可達距離的密度峰值聚類（Density Peak Clustering based on Adaptive Reachable Distance， ARD-DPC）算法。該算法首先根據統計學原理推導出非參數核密度估計的公式，計算數據點的局部密度，避免截斷距離的主觀選取；然后考慮到不同密度的聚類中心的可達距離不同，提出一種自適應可達距離的方法分配數據點，有效改善最近鄰分配帶來的誤差問題。在多個數據集上的實驗結果表明，本文算法相比原算法具有更好的聚類效果。

1 CFSFDP算法與分析

1.1 CFSFDP算法

第二種方法是利用Gaussian核，定義如下：

圖1 CFSFDP算法的二維展示

1.2 CFSFDP算法的局限性

本文主要針對CFSFDP算法以下兩個局限進行討論：

2）最近鄰分配導致的誤差問題。CFSFDP算法中，在聚類中心被找到后，將剩余的數據點分配到與聚類中心最近的聚類中。如圖2（d）所示，算法雖然正確識別出了3個聚類中心，但是由于近鄰分配數據點，導致同一個簇被錯誤分成3個簇。

圖2 CFSFDP算法在不同合成數據集上的聚類結果

2 ARD?DPC算法

2.1 非參數核密度估計

非參數核密度估計方法［12］不利用有關數據分布的先驗知識，對數據分布不附加任何假定，是一種從數據樣本本身出發研究數據分布特征的一種方法。在文獻［13］中提到，非參數核密度估計方法已被廣泛應用于聚類分析、非參數判別分析、模式識別等方面。在使用基于密度方法的聚類分析中，如果聚類中心被定義為是由這些點構造的密度估計中的模式或峰值，可采用非參數的方法計算局部密度。CFSFDP算法在聚類中心的定義符合上述情況，所以可采用非參數核密度估計的方法用于密度估計。

將式（6）代入式（5）中，可以得到核密度估計函數為：

在實際聚類分析的過程中，一般都是多元數據集，所以考慮多元數據集的非參數核密度估計。而多元的性質一般都可以由一元推廣得到。

根據文獻［13］，不同的核函數的選取也會影響核密度估計的效率。一般的，采用多元Epanechnikov核，此時核密度估計的計算效率最高。多元Epanechnikov核的定義如下：

將式（10）代入式（8）可得到多變量的核密度估計：

2.2 自適應可達距離

接下來按照自適應可達距離分配數據點，劃分簇類，得到最終的聚類結果。首先考慮密度較大的聚類中心，相應的自適應可達距離較小。從第一個聚類中心開始，標記為1，然后根據自適應可達距離遍歷其他數據點，數據點在聚類中心的可達距離范圍之內，將數據點歸到與聚類中心相同的簇中，得到第一個簇；然后再考慮第二個聚類中心，標記為2，根據自適應可達距離遍歷剩余數據點，得到第二個簇，一直下去，直到得到最終的簇劃分。

2.3 ARD-DPC算法的具體步驟

基于上述分析，ARD-DPC算法的具體步驟如下：

5）劃分數據點：

19） end if

20） end while

24） end while

3 實驗與結果分析

為了驗證本文算法的性能，在Matlab2018a上分別對合成數據集［15］和UCI真實數據集［16］進行了探究實驗。實驗環境為Windows 10系統，處理器為Intel Core i5-5200U CPU，內存為8.00 GB。

NMI通過將聚類結果與“真實”的類標簽對比衡量聚類效果，計算公式如下：

RI評價標準衡量了正確的聚類結果所占的比例，其值越大，劃分越佳。計算公式如下：

其中：（True Positive）表示應歸于同一類，且在結果中被正確地歸為同一類；（True Negative）表示應歸于不同類，且在結果中被正確地歸為不同類；（False Positive）表示應歸于不同類，但在結果中被歸為同一類；（False Negative）表示應歸于同一類，但在結果中被歸為不同類。

3.1 合成數據集

為了將本文ARD-DPC算法與原CFSFDP算法在具有不同形狀簇的復雜數據集上的聚類效果可視化，本文選取了4個二維的具有代表性的合成數據集進行對比實驗（圖3）。合成數據集的基本信息如表1所示。這些合成數據集的簇的形狀各不相同，比如有環狀的、流形狀的、球狀的、塊狀的等。圖3中不同灰度和形狀的圖形表示不同的類別，算法識別出來的噪聲點用黑色圓點表示。

表1 實驗中使用的合成數據集

如圖3（a）所示：CFSFDP算法沒有正確識別出ThreeCircles和Jain的聚類中心，誤將聚類的核心點當成噪聲點，將屬于同一簇類的數據點分成不同的簇，導致聚類劃分錯誤；CFSFDP算法也無法識別出具有不同密度的簇，如Compound，這些簇的形狀各不相同，有的高密度的簇被低密度的簇包圍，有的低密度簇被高密度的簇包圍；對Pathbased，CFSFDP算法雖然正確識別出了聚類中心，但由于最近鄰分配，導致同一個簇被錯誤劃分成三個簇。而圖3（b）的結果顯示，本文的ARD-DPC算法不僅能識別出正確的聚類數，還能識別出任意形狀的、具有復雜密度的簇。

圖3 ARD-DPC算法與CFSFDP算法在合成數據集上的聚類結果比較

表2列出了DBSCAN、CFSFDP、DADPC、ARD-DPC這4種算法在4個人工數據集上的聚類性能指標，加粗顯示的數據表示在當前數據集中相對最優的指標數據，其中類數比指標代表的是算法最終聚類數與真實聚類數的比值。對比各算法的NMI、RI和F1-measure這三個指標可以發現，ARD-DPC算法在各個數據集上都有著更好的聚類效果。

3.2 UCI真實數據集

為了驗證本文ARD-DPC算法在高維數據上的有效性，在6個高維的UCI真實數據集上與DBSCAN算法、CFSFDP算法以及DADPC算法進行對比實驗。測試數據集的基本信息如表3所示。由于高維數據難以在二維平面上可視化展示，所以采用NMI、RI和F1-measure評價指標來度量算法的有效性。

表2 四種算法在合成數據集上的評價指標對比

表3 實驗中使用的UCI數據集

表4列出了DBSCAN、CFSFDP、DADPC、ARD-DPC這4種算法在6個UCI數據集上的聚類性能指標。對于Wine、Glass和Iris這三個數據集，ARD-DPC算法的三個評價指標均要優于對比算法。這是因為ARD-DPC算法采用了非參數核密度的方法計算數據點的局部密度，避免了截斷距離的選取，能夠根據聚類中心的密度不同，利用自適應可達距離分配數據點，得到更好的聚類效果。對于Heart數據集，雖然ARD-DPC算法的NMI和RI指標比CFSFDP算法的低，但是F1-measure指標高于CFSFDP算法。可能原因是在Heart數據集中，利用決策圖選取的兩個聚類中心的密度差不多，所以ARD-DPC算法的聚類效果和CFSFDP算法的效果相差不大。對于Breast數據集，雖然ARD-DPC算法的RI和F1-measure指標略低于DADPC算法，但NMI指標數值約為DADPC算法的兩倍。這說明利用ARD-DPC算法得到的聚類結果與真實結果的關聯程度更大，可能原因在于采用DADPC算法中的自適應密度距離改變了原數據集的空間分布結構，所以聚類結果與真實結果關聯程度不高。對于Pima數據集，ARD-DPC算法的三個評價指標雖然都低于DBSCAN算法，但是高于CFSFDP和DADPC算法。這說明對于Pima這樣模糊度較高、聚類特征不明顯的數據集，采用密度峰值聚類的算法效果不太好；也有可能是對于高維數據，采用歐氏距離來度量數據之間的相似性不太合理，導致利用決策圖無法正確地選擇出聚類中心，從而聚類效果不佳。

表4 四種算法在UCI數據集上的評價指標對比

綜合以上分析可知，與DBSCAN、CFSFDP和DADPC算法相比，ARD-DPC算法在各個數據集上的評價指標都有較大的優勢，能更好地識別出實際的聚類數。

3.3 輸入參數分析

圖4 ARD-DPC在合成數據集上的聚類結果

圖5 不同adR值時ARD-DPC算法在UCI數據集上的F1-measure

4 結語

本文針對CFSFDP算法中截斷距離的難以選取以及最近鄰分配誤差問題，提出了基于自適應可達距離的密度峰值聚類算法ARD-DPC。實驗結果表明，與CFSFDP算法相比，本文提出的ARD-DPC算法具有更好的聚類效果。但是在該算法中，在利用自適應可達距離劃分簇類時，需要利用決策圖正確識別聚類中心，而自適應可達距離的定義依賴于半徑調節參數的選取，以及利用非參數核密度估計數據點的局部密度時，是直接利用固定的帶寬值，不能動態地展示每一點的局部密度的變化。因此，下一步要研究如何正確選擇聚類中心，定義合理的自適應可達距離的計算方法，以及自適應選擇帶寬的算法。

[1] MAcQUEEN J. Some methods for classification and analysis of multivariate observations［C］// Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. Berkeley： University of California Press， 1967： 281-297.

[2] KAUFMAN L， ROUSSEEUW P. Clustering by means of medoids［M］// DOGEE Y. Statistical Data Analysis Based on the L1-norm and Related Methods. Amsterdam： Elsevier Science Publishing Company， 1987： 405-416.

[3] ZHANG T， RAMAKRISHNAN R， LIVNY M. BIRCH： an efficient data clustering method for very large databases［C］// Proceedings of the 1996 ACM SIGMOID International Conference on Management of Data. New York： ACM， 1996： 103-114.

[4] KARPIS G， HAN E H， KUMAR V. Chameleon： hierarchical clustering using dynamic modeling［J］. Computer， 1999， 32（8）：68-75.

[5] ESTER M， KRIEGEL H P， SANDER J， et al. A density-based algorithm for discovering clusters in large spatial databases with noise［C］// Proceedings of the 2nd International Conference on Knowledge Discovery and Data Ming. Menlo Park， CA： AAAI， 1996： 226-231.

[6] ANKERST M， BREUNING M M， KRIEGEL H P， et al. OPTICS： ordering points to identify the clustering structure［C］// Proceedings of the 1999 ACM SGMOD International Conference on Management of Data. New York： ACM， 1999： 49-60.

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

[8] HOU J， PELILLO M. A new density kernel in density peak based clustering［C］// Proceedings of the 23rd International Conference on Pattern Recognition. Piscataway： IEEE， 2016： 468-473.

[9] MEHMOOD R， ZHANG G Z， BIE R F， et al. Clustering by fast search and find of density peaks via heat diffusion［J］. Neurocomputing， 2016， 208： 210-217.

[10] 謝國偉，錢雪忠，周世兵. 基于非參數核密度估計的密度峰值聚類算法［J］. 計算機應用研究， 2018， 35（10）：2956-2959.（XIE G W， QIAN X Z， ZHOU S B. Density peak clustering algorithm based on non-parametric kernel density estimation［J］. Application Research of Computers， 2018， 35（10）： 2956-2959.）

[11] 李濤，葛洪偉，蘇樹智. 基于密度自適應距離的密度峰聚類［J］. 小型微型計算機系統， 2017， 38（6）：1347-1352. （LI T， GE H W， SU S Z. Density peaks clustering based on density adaptive distance［J］. Journal of Chinese Computer Systems. 2017， 38（6）： 1347-1352.）

[12] PARZEN E. On estimation of a probability density function and mode［J］. The Annals of Mathematical Statistics， 1962， 33（3）： 1065-1076.

[13] SILVERMAN B W. Density Estimation for Statistics and Data Analysis［M］. Boca Raton： Chapman and Hall， 1986： 34-117.

[14] 宋宇辰，宋飛燕，孟海東. 基于密度復雜簇聚類算法研究與實現［J］. 計算機工程與應用， 2007， 43（35）：162-165.（SONG Y C， SONG F Y， MENG H D. Research and implementation of density based clustering algorithm for complex clusters［J］. Computer Engineering and Applications， 2007， 43（35）： 162-165.）

[15] DETONE D， MALISIEWICZ T， RABINOVICH A. SuperPoint： self-supervised interest point detection and description［C］//Proceedings of the 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops. Piscataway： IEEE， 2018： 337-349.

[16] DUA D， GRAFF C. UCI machine learning repository［DS/OL］. ［2021-02-20］.http：//archive.ics.uci.edu/ml.

[17] NGUYEN T P Q， KUO R J. Partition-and-merge based fuzzy genetic clustering algorithm for categorical data［J］. Applied Soft Computing， 2019， 75： 254-264.

[18] MANNING C D， RAGHAVAN P， SCHüTZE H. Introduction to Information Retrieval［M］. Cambridge： Cambridge University Press， 2008： 356-360.

Density peak clustering algorithm based on adaptive reachable distance

ZHANG Man*， ZHANG Zhengjun， FENG Junqi， YAN Tao

（，，210094，）

Concerning the problem that the cutoff distance needs to be selected manually in Clustering by Fast Search and Find of Density Peaks （CFSFDP） algorithm， as well as the poor clustering effect on complex datasets with different density clusters due to the error caused by nearest neighbor assignment， a Density Peak Clustering algorithm based on Adaptive Reachable Distance （ARD-DPC） was proposed. In this algorithm， a non-parametric kernel density estimation method was used to calculate the local density of points， and the clustering centers were selected by the decision graph. Then， an adaptive reachable distance was used to assign the data points and obtain the final clustering result. Simulation experiments were conducted on 4 synthetic datasets and 6 UCI datasets， and the proposed algorithm was compared with CFSFDP （Clustering by Fast Search and Find of Density Peaks）， DBSCAN （Density-Based Spatial Clustering of Applications with Noise） and DADPC （Density Peaks Clustering based on Density Adaptive distance）. Experimental results show that compared to the three other algorithms， the proposed ARD-DPC algorithm achieves the all highest Normalized Mutual Information （NMI）， Rand Index （RI） and F1-measure on 4 synthetic datasets and 3 UCI datasets， the only highest NMI on UCI Breast dataset， the only highest F1-measure on UCI Heart dataset， but does not cluster UCI Pima dataset well， which has high fuzzyness and unclear clustering feature. At the same time， ARD-DPC algorithm can accurately identify the number of clusters and clusters with complex density on the synthetic datasets.

clustering algorithm; density peak; cutoff distance; non-parametric kernel density estimation; adaptive reachable distance

This work is partially supported by National Natural Science Foundation of China （11671205）.

ZHANG Man， born in 1998， M. S. candidate. Her research interests include machine learning， data mining.

ZHANG Zhengjun， born in 1965， Ph. D.， associate professor. His research interests include data mining， graphics technology， image processing.

FENG Junqi， born in 1997， M. S. candidate. His research interests include machine learning， data mining.

YAN Tao， born in 1977， Ph. D.， associate professor. His research interests include linear and nonlinear programming， optimization models and algorithms in application problems， complementarity problems， programming with equilibrium constraints.

TP301.6

A

1001-9081（2022）06-1914-08

10.11772/j.issn.1001-9081.2021040551

2021?04?12；

2021?07?22；

2021?08?05。

國家自然科學基金資助項目（11671205）

章曼（1998—），女，安徽太湖人，碩士研究生，主要研究方向：機器學習、數據挖掘；張正軍（1965—），男，江蘇阜寧人，副教授，博士，主要研究方向：數據挖掘、圖形技術、圖像處理；馮俊淇（1997—），男，遼寧沈陽人，碩士研究生，主要研究方向：機器學習、數據挖掘；嚴濤（1977—），江蘇泰興人，副教授，博士，主要研究方向：線性與非線性規劃、應用問題中的優化模型及算法、互補問題、均衡約束規劃。