基于自適應(yīng)可達(dá)距離的密度峰值聚類(lèi)算法

章曼，張正軍，馮俊淇，嚴(yán)濤

基于自適應(yīng)可達(dá)距離的密度峰值聚類(lèi)算法

章曼*，張正軍，馮俊淇，嚴(yán)濤

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

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

聚類(lèi)算法；密度峰值；截?cái)嗑嚯x；非參數(shù)核密度估計(jì)；自適應(yīng)可達(dá)距離

0 引言

聚類(lèi)是數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)研究領(lǐng)域中最重要的數(shù)據(jù)預(yù)測(cè)和數(shù)據(jù)分析方法之一。聚類(lèi)是一種無(wú)監(jiān)督學(xué)習(xí)方法，目的是使得同一類(lèi)簇中的元素之間盡可能地相似，而不同類(lèi)簇中的元素之間盡可能地相異。聚類(lèi)分析已被廣泛用于許多學(xué)科領(lǐng)域，涵蓋天文學(xué)、生物信息學(xué)、文獻(xiàn)計(jì)量學(xué)以及模式識(shí)別。

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

2014年，Rodriguez等［7］提出了基于快速搜索和發(fā)現(xiàn)密度峰值的聚類(lèi)（Clustering by Fast Search and Find of Density Peaks， CFSFDP）算法。在算法聚類(lèi)過(guò)程中，聚類(lèi)的數(shù)目會(huì)直觀地產(chǎn)生，噪聲點(diǎn)會(huì)自動(dòng)地被發(fā)現(xiàn)并排除在分析之外，而且不管聚類(lèi)的形狀和嵌入空間的維數(shù)如何，聚類(lèi)都會(huì)被識(shí)別出來(lái)。

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

本文提出了一種基于自適應(yīng)可達(dá)距離的密度峰值聚類(lèi)（Density Peak Clustering based on Adaptive Reachable Distance， ARD-DPC）算法。該算法首先根據(jù)統(tǒng)計(jì)學(xué)原理推導(dǎo)出非參數(shù)核密度估計(jì)的公式，計(jì)算數(shù)據(jù)點(diǎn)的局部密度，避免截?cái)嗑嚯x的主觀選?。蝗缓罂紤]到不同密度的聚類(lèi)中心的可達(dá)距離不同，提出一種自適應(yīng)可達(dá)距離的方法分配數(shù)據(jù)點(diǎn)，有效改善最近鄰分配帶來(lái)的誤差問(wèn)題。在多個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文算法相比原算法具有更好的聚類(lèi)效果。

1 CFSFDP算法與分析

1.1 CFSFDP算法

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

圖1 CFSFDP算法的二維展示

1.2 CFSFDP算法的局限性

本文主要針對(duì)CFSFDP算法以下兩個(gè)局限進(jìn)行討論：

2）最近鄰分配導(dǎo)致的誤差問(wèn)題。CFSFDP算法中，在聚類(lèi)中心被找到后，將剩余的數(shù)據(jù)點(diǎn)分配到與聚類(lèi)中心最近的聚類(lèi)中。如圖2（d）所示，算法雖然正確識(shí)別出了3個(gè)聚類(lèi)中心，但是由于近鄰分配數(shù)據(jù)點(diǎn)，導(dǎo)致同一個(gè)簇被錯(cuò)誤分成3個(gè)簇。

圖2 CFSFDP算法在不同合成數(shù)據(jù)集上的聚類(lèi)結(jié)果

2 ARD?DPC算法

2.1 非參數(shù)核密度估計(jì)

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

將式（6）代入式（5）中，可以得到核密度估計(jì)函數(shù)為：

在實(shí)際聚類(lèi)分析的過(guò)程中，一般都是多元數(shù)據(jù)集，所以考慮多元數(shù)據(jù)集的非參數(shù)核密度估計(jì)。而多元的性質(zhì)一般都可以由一元推廣得到。

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

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

2.2 自適應(yīng)可達(dá)距離

接下來(lái)按照自適應(yīng)可達(dá)距離分配數(shù)據(jù)點(diǎn)，劃分簇類(lèi)，得到最終的聚類(lèi)結(jié)果。首先考慮密度較大的聚類(lèi)中心，相應(yīng)的自適應(yīng)可達(dá)距離較小。從第一個(gè)聚類(lèi)中心開(kāi)始，標(biāo)記為1，然后根據(jù)自適應(yīng)可達(dá)距離遍歷其他數(shù)據(jù)點(diǎn)，數(shù)據(jù)點(diǎn)在聚類(lèi)中心的可達(dá)距離范圍之內(nèi)，將數(shù)據(jù)點(diǎn)歸到與聚類(lèi)中心相同的簇中，得到第一個(gè)簇；然后再考慮第二個(gè)聚類(lèi)中心，標(biāo)記為2，根據(jù)自適應(yīng)可達(dá)距離遍歷剩余數(shù)據(jù)點(diǎn)，得到第二個(gè)簇，一直下去，直到得到最終的簇劃分。

2.3 ARD-DPC算法的具體步驟

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

5）劃分?jǐn)?shù)據(jù)點(diǎn)：

19） end if

20） end while

24） end while

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

為了驗(yàn)證本文算法的性能，在Matlab2018a上分別對(duì)合成數(shù)據(jù)集［15］和UCI真實(shí)數(shù)據(jù)集［16］進(jìn)行了探究實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境為Windows 10系統(tǒng)，處理器為Intel Core i5-5200U CPU，內(nèi)存為8.00 GB。

NMI通過(guò)將聚類(lèi)結(jié)果與“真實(shí)”的類(lèi)標(biāo)簽對(duì)比衡量聚類(lèi)效果，計(jì)算公式如下：

RI評(píng)價(jià)標(biāo)準(zhǔn)衡量了正確的聚類(lèi)結(jié)果所占的比例，其值越大，劃分越佳。計(jì)算公式如下：

其中：（True Positive）表示應(yīng)歸于同一類(lèi)，且在結(jié)果中被正確地歸為同一類(lèi)；（True Negative）表示應(yīng)歸于不同類(lèi)，且在結(jié)果中被正確地歸為不同類(lèi)；（False Positive）表示應(yīng)歸于不同類(lèi)，但在結(jié)果中被歸為同一類(lèi)；（False Negative）表示應(yīng)歸于同一類(lèi)，但在結(jié)果中被歸為不同類(lèi)。

3.1 合成數(shù)據(jù)集

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

表1 實(shí)驗(yàn)中使用的合成數(shù)據(jù)集

如圖3（a）所示：CFSFDP算法沒(méi)有正確識(shí)別出ThreeCircles和Jain的聚類(lèi)中心，誤將聚類(lèi)的核心點(diǎn)當(dāng)成噪聲點(diǎn)，將屬于同一簇類(lèi)的數(shù)據(jù)點(diǎn)分成不同的簇，導(dǎo)致聚類(lèi)劃分錯(cuò)誤；CFSFDP算法也無(wú)法識(shí)別出具有不同密度的簇，如Compound，這些簇的形狀各不相同，有的高密度的簇被低密度的簇包圍，有的低密度簇被高密度的簇包圍；對(duì)Pathbased，CFSFDP算法雖然正確識(shí)別出了聚類(lèi)中心，但由于最近鄰分配，導(dǎo)致同一個(gè)簇被錯(cuò)誤劃分成三個(gè)簇。而圖3（b）的結(jié)果顯示，本文的ARD-DPC算法不僅能識(shí)別出正確的聚類(lèi)數(shù)，還能識(shí)別出任意形狀的、具有復(fù)雜密度的簇。

圖3 ARD-DPC算法與CFSFDP算法在合成數(shù)據(jù)集上的聚類(lèi)結(jié)果比較

表2列出了DBSCAN、CFSFDP、DADPC、ARD-DPC這4種算法在4個(gè)人工數(shù)據(jù)集上的聚類(lèi)性能指標(biāo)，加粗顯示的數(shù)據(jù)表示在當(dāng)前數(shù)據(jù)集中相對(duì)最優(yōu)的指標(biāo)數(shù)據(jù)，其中類(lèi)數(shù)比指標(biāo)代表的是算法最終聚類(lèi)數(shù)與真實(shí)聚類(lèi)數(shù)的比值。對(duì)比各算法的NMI、RI和F1-measure這三個(gè)指標(biāo)可以發(fā)現(xiàn)，ARD-DPC算法在各個(gè)數(shù)據(jù)集上都有著更好的聚類(lèi)效果。

3.2 UCI真實(shí)數(shù)據(jù)集

為了驗(yàn)證本文ARD-DPC算法在高維數(shù)據(jù)上的有效性，在6個(gè)高維的UCI真實(shí)數(shù)據(jù)集上與DBSCAN算法、CFSFDP算法以及DADPC算法進(jìn)行對(duì)比實(shí)驗(yàn)。測(cè)試數(shù)據(jù)集的基本信息如表3所示。由于高維數(shù)據(jù)難以在二維平面上可視化展示，所以采用NMI、RI和F1-measure評(píng)價(jià)指標(biāo)來(lái)度量算法的有效性。

表2 四種算法在合成數(shù)據(jù)集上的評(píng)價(jià)指標(biāo)對(duì)比

表3 實(shí)驗(yàn)中使用的UCI數(shù)據(jù)集

表4列出了DBSCAN、CFSFDP、DADPC、ARD-DPC這4種算法在6個(gè)UCI數(shù)據(jù)集上的聚類(lèi)性能指標(biāo)。對(duì)于Wine、Glass和Iris這三個(gè)數(shù)據(jù)集，ARD-DPC算法的三個(gè)評(píng)價(jià)指標(biāo)均要優(yōu)于對(duì)比算法。這是因?yàn)锳RD-DPC算法采用了非參數(shù)核密度的方法計(jì)算數(shù)據(jù)點(diǎn)的局部密度，避免了截?cái)嗑嚯x的選取，能夠根據(jù)聚類(lèi)中心的密度不同，利用自適應(yīng)可達(dá)距離分配數(shù)據(jù)點(diǎn)，得到更好的聚類(lèi)效果。對(duì)于Heart數(shù)據(jù)集，雖然ARD-DPC算法的NMI和RI指標(biāo)比CFSFDP算法的低，但是F1-measure指標(biāo)高于CFSFDP算法?？赡茉蚴窃贖eart數(shù)據(jù)集中，利用決策圖選取的兩個(gè)聚類(lèi)中心的密度差不多，所以ARD-DPC算法的聚類(lèi)效果和CFSFDP算法的效果相差不大。對(duì)于Breast數(shù)據(jù)集，雖然ARD-DPC算法的RI和F1-measure指標(biāo)略低于DADPC算法，但NMI指標(biāo)數(shù)值約為DADPC算法的兩倍。這說(shuō)明利用ARD-DPC算法得到的聚類(lèi)結(jié)果與真實(shí)結(jié)果的關(guān)聯(lián)程度更大，可能原因在于采用DADPC算法中的自適應(yīng)密度距離改變了原數(shù)據(jù)集的空間分布結(jié)構(gòu)，所以聚類(lèi)結(jié)果與真實(shí)結(jié)果關(guān)聯(lián)程度不高。對(duì)于Pima數(shù)據(jù)集，ARD-DPC算法的三個(gè)評(píng)價(jià)指標(biāo)雖然都低于DBSCAN算法，但是高于CFSFDP和DADPC算法。這說(shuō)明對(duì)于Pima這樣模糊度較高、聚類(lèi)特征不明顯的數(shù)據(jù)集，采用密度峰值聚類(lèi)的算法效果不太好；也有可能是對(duì)于高維數(shù)據(jù)，采用歐氏距離來(lái)度量數(shù)據(jù)之間的相似性不太合理，導(dǎo)致利用決策圖無(wú)法正確地選擇出聚類(lèi)中心，從而聚類(lèi)效果不佳。

表4 四種算法在UCI數(shù)據(jù)集上的評(píng)價(jià)指標(biāo)對(duì)比

綜合以上分析可知，與DBSCAN、CFSFDP和DADPC算法相比，ARD-DPC算法在各個(gè)數(shù)據(jù)集上的評(píng)價(jià)指標(biāo)都有較大的優(yōu)勢(shì)，能更好地識(shí)別出實(shí)際的聚類(lèi)數(shù)。

3.3 輸入?yún)?shù)分析

圖4 ARD-DPC在合成數(shù)據(jù)集上的聚類(lèi)結(jié)果

圖5 不同adR值時(shí)ARD-DPC算法在UCI數(shù)據(jù)集上的F1-measure

4 結(jié)語(yǔ)

本文針對(duì)CFSFDP算法中截?cái)嗑嚯x的難以選取以及最近鄰分配誤差問(wèn)題，提出了基于自適應(yīng)可達(dá)距離的密度峰值聚類(lèi)算法ARD-DPC。實(shí)驗(yàn)結(jié)果表明，與CFSFDP算法相比，本文提出的ARD-DPC算法具有更好的聚類(lèi)效果。但是在該算法中，在利用自適應(yīng)可達(dá)距離劃分簇類(lèi)時(shí)，需要利用決策圖正確識(shí)別聚類(lèi)中心，而自適應(yīng)可達(dá)距離的定義依賴(lài)于半徑調(diào)節(jié)參數(shù)的選取，以及利用非參數(shù)核密度估計(jì)數(shù)據(jù)點(diǎn)的局部密度時(shí)，是直接利用固定的帶寬值，不能動(dòng)態(tài)地展示每一點(diǎn)的局部密度的變化。因此，下一步要研究如何正確選擇聚類(lèi)中心，定義合理的自適應(yīng)可達(dá)距離的計(jì)算方法，以及自適應(yīng)選擇帶寬的算法。

[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] 謝國(guó)偉，錢(qián)雪忠，周世兵. 基于非參數(shù)核密度估計(jì)的密度峰值聚類(lèi)算法［J］. 計(jì)算機(jī)應(yīng)用研究， 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] 李濤，葛洪偉，蘇樹(shù)智. 基于密度自適應(yīng)距離的密度峰聚類(lèi)［J］. 小型微型計(jì)算機(jī)系統(tǒng)， 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] 宋宇辰，宋飛燕，孟海東. 基于密度復(fù)雜簇聚類(lèi)算法研究與實(shí)現(xiàn)［J］. 計(jì)算機(jī)工程與應(yīng)用， 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。

國(guó)家自然科學(xué)基金資助項(xiàng)目（11671205）

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