基于類(lèi)簇合并的無(wú)參數(shù)密度峰值聚類(lèi)算法

摘 要： 密度峰值聚類(lèi)算法（DPC）通過(guò)決策圖直觀地找到類(lèi)簇中心進(jìn)而完成聚類(lèi)，是一種簡(jiǎn)單高效的聚類(lèi)算法。然而，DPC算法的截?cái)嗑嚯x和類(lèi)簇中心都是人為確定的，受主觀影響較大，具有不確定性。針對(duì)上述問(wèn)題，提出一種基于類(lèi)簇合并的無(wú)參數(shù)密度峰值聚類(lèi)算法（NDPCCM）。首先根據(jù)樣本點(diǎn)兩兩之間的相似度的分布特征將其分為類(lèi)內(nèi)相似度和類(lèi)間相似度兩種類(lèi)型，并利用類(lèi)內(nèi)相似度自動(dòng)確定截?cái)嘞嗨贫龋苊饬巳藶樵O(shè)置參數(shù)；接著根據(jù)簇中心權(quán)值的下降趨勢(shì)自動(dòng)選擇初始類(lèi)簇中心，得到初始類(lèi)簇；最后通過(guò)合并初始類(lèi)簇對(duì)初步聚類(lèi)結(jié)果進(jìn)行優(yōu)化，提高了聚類(lèi)的準(zhǔn)確性。在人工數(shù)據(jù)集和UCI真實(shí)數(shù)據(jù)集上，將所提算法與DPC、DBSCAN、K?means算法進(jìn)行對(duì)比實(shí)驗(yàn)。結(jié)果表明所提算法無(wú)需輸入?yún)?shù)就能夠自動(dòng)得到類(lèi)簇，且聚類(lèi)性能優(yōu)于其他算法。

關(guān)鍵詞： 聚類(lèi)分析； 密度峰值聚類(lèi)算法； 初始類(lèi)簇； 類(lèi)簇合并； 相似度； 聚類(lèi)性能

中圖分類(lèi)號(hào)： TN929.5?34； TP181" " " " " " " " "文獻(xiàn)標(biāo)識(shí)碼： A" " " " " " " " " " "文章編號(hào)： 1004?373X（2024）08?0001?08

Nonparametric density peak clustering algorithm based on clusters merging

LIU Tianjiao， WANG Shengjing， YUAN Yongsheng

（College of Mathematics， Hohai University， Nanjing 211100， China）

Abstract： The density peak clustering algorithm （DPC） is a simple and efficient clustering algorithm that can intuitively find the cluster centers by a decision graph and complete clustering. However， the cutoff distance and cluster centers of the DPC algorithm are both determined artificially and subject to significant subjective influence， resulting in uncertainty. To address the above issues， a nonparametric density peak clustering algorithm based on clusters merging （NDPCCM） is proposed. Based on the distribution characteristics of pairwise similarities among sample points， they are divided into intra?class similarity and inter?class similarity， and the cutoff similarity is determined automatically by means of intra?class similarity to avoid manually setting parameters. Based on the decreasing trend of the cluster center weights， the initial cluster centers are selected automatically to obtain the initial clusters. The initial clustering results are optimized by merging the initial clusters， which can improve the accuracy of clustering. The comparative experiments were conducted between the proposed algorithm and" DPC， DBSCAN， and K?means algorithms on both artificial and UCI real datasets. The results show that the proposed algorithm does not require input parameters and can automatically obtain clusters， with better clustering performance than other algorithms.

Keywords： cluster analysis; density peak clustering algorithm; initial cluster; cluster merging; similarity; clustering performance

0" 引" 言

聚類(lèi)分析是一種重要的無(wú)監(jiān)督學(xué)習(xí)方法，在生物信息學(xué)、模式識(shí)別、圖像處理等領(lǐng)域有著廣泛的應(yīng)用[1?4]。密度峰值聚類(lèi)（Density Peak Clustering， DPC）算法是2014年由A. Rodriguez等人提出的一種密度聚類(lèi)算法[5]。該算法能夠?qū)崿F(xiàn)任意形狀數(shù)據(jù)集的聚類(lèi)，根據(jù)決策圖直觀產(chǎn)生類(lèi)簇中心，從而確定簇的數(shù)量，并具有高效的樣本點(diǎn)分配策略。相較于傳統(tǒng)的聚類(lèi)算法，該算法使用簡(jiǎn)單、參數(shù)少且在許多數(shù)據(jù)集上表現(xiàn)良好，因而受到了廣泛關(guān)注。然而，DPC算法的截?cái)嗑嚯x依靠主觀經(jīng)驗(yàn)選取，類(lèi)簇中心根據(jù)決策圖人工選擇，這些主觀性因素給最終的聚類(lèi)結(jié)果帶來(lái)了不確定性。

針對(duì)DPC算法自身存在的一些局限性，一部分學(xué)者從局部密度的衡量方面展開(kāi)了相關(guān)研究。Du M J等人將K近鄰的思想引入到局部密度的計(jì)算中，優(yōu)化了樣本局部密度的度量，取得了較好的性能[6]。但是該算法需要輸入?yún)?shù)，并且仍然需要人工選擇類(lèi)簇中心。R. Mehmood等人通過(guò)熱擴(kuò)散方法使用核密度估計(jì)來(lái)計(jì)算樣本點(diǎn)的密度，同時(shí)考慮了截?cái)嗑嚯x的選擇和核密度估計(jì)的邊界修正，獲得了更精確的類(lèi)簇，具有魯棒性和有效性，但是仍需要人工參與來(lái)選擇簇的數(shù)目[7]。Liu R等人使用共享近鄰信息定義樣本之間的相似度，基于該相似度重新定義局部密度，并提出兩步分配策略來(lái)分配非聚類(lèi)中心，避免了一步分配策略帶來(lái)的連帶錯(cuò)誤，但是類(lèi)簇中心的選取仍然具有人為主觀性[8]。丁世飛等人利用基于塊的不相似性度量計(jì)算樣本之間的相似度，再根據(jù)樣本的K近鄰重新定義局部密度，可以更高效地處理復(fù)雜數(shù)據(jù)[9]，但是引入了新的參數(shù)K。章曼等人使用非參數(shù)核密度估計(jì)方法估計(jì)樣本局部密度，并計(jì)算自適應(yīng)可達(dá)距離來(lái)對(duì)非中心點(diǎn)進(jìn)行分配，提高了DPC算法的聚類(lèi)效果，但是引入了參數(shù)半徑調(diào)節(jié)系數(shù)[10]。位雅等人利用樣本自然最近鄰域內(nèi)的樣本信息來(lái)計(jì)算樣本局部密度以及相對(duì)密度，對(duì)選出的聚類(lèi)中心計(jì)算其聚類(lèi)距離，根據(jù)聚類(lèi)距離分配剩余點(diǎn)，能有效地處理密度不均勻數(shù)據(jù)集的聚類(lèi)問(wèn)題。但是該算法聚類(lèi)效果依賴(lài)于距離調(diào)節(jié)系數(shù)，并且仍需要人工選取類(lèi)簇中心[11]。

另有部分學(xué)者從類(lèi)簇中心的自適應(yīng)選取方面進(jìn)行了相關(guān)研究。R. F. Bie等人利用模糊規(guī)則自適應(yīng)地進(jìn)行聚類(lèi)中心的選擇，接著基于截?cái)嗑嚯x將部分類(lèi)簇合并得到最終類(lèi)簇。該算法對(duì)于靜態(tài)數(shù)據(jù)具有有效性和穩(wěn)健性，但是存在截?cái)嗑嚯x的合理選取問(wèn)題[12]。Liang Z等人基于分治策略和密度可達(dá)概念，遞歸地找到正確的類(lèi)簇?cái)?shù)量，但是仍然需要輸入?yún)?shù)截?cái)嗑嚯x[13]。馬春來(lái)等人將簇中心權(quán)值按降序排列，選擇下降趨勢(shì)由急變緩的“拐點(diǎn)”之前的點(diǎn)作為類(lèi)簇中心，自適應(yīng)地完成聚類(lèi)過(guò)程，但是仍需要根據(jù)主觀經(jīng)驗(yàn)確定截?cái)嗑嚯x[14]。王萬(wàn)良等人分別通過(guò)切比雪夫不等式和標(biāo)準(zhǔn)差確定歸一化后的密度和距離的閾值，以及簇中心權(quán)值的閾值，自動(dòng)選取相關(guān)指標(biāo)大于閾值的點(diǎn)作為簇中心，但是切比雪夫不等式中[ε]的選取會(huì)影響聚類(lèi)效果[15]。徐童童等人使用共享近鄰定義樣本之間的相似度以及局部密度，對(duì)簇中心權(quán)值進(jìn)行函數(shù)變換，然后根據(jù)決策函數(shù)自適應(yīng)地選取潛在聚類(lèi)中心，最后經(jīng)過(guò)篩選自動(dòng)得到最終聚類(lèi)中心，但是引入了樣本近鄰數(shù)[16]。Ding S F等人使用分層加權(quán)自然鄰域集來(lái)計(jì)算局部密度，并提出一個(gè)子簇合并策略自適應(yīng)地獲取最優(yōu)類(lèi)簇?cái)?shù)，有效地消除了截?cái)嗑嚯x對(duì)聚類(lèi)結(jié)果的影響，但是層數(shù)參數(shù)是人工直接選取的[17]。

綜上所述，現(xiàn)有的改進(jìn)方法中，存在參數(shù)或者類(lèi)簇中心需要人工選擇的問(wèn)題，算法無(wú)法完全自適應(yīng)完成。為此，本文提出一種基于類(lèi)簇合并的無(wú)參數(shù)密度峰值聚類(lèi)算法（Nonparametric Density Peak Clustering Algorithm Based on Clusters Merging， NDPCCM）。NDPCCM算法首先根據(jù)樣本點(diǎn)兩兩之間相似度的分布特征自動(dòng)確定截?cái)嘞嗨贫龋苊饬巳藶樵O(shè)置參數(shù)影響聚類(lèi)結(jié)果；其次，為了避免人工漏選類(lèi)簇中心，根據(jù)簇中心權(quán)值的下降趨勢(shì)自動(dòng)選取初始類(lèi)簇中心，并完成分配得到初始類(lèi)簇；最后，為防止一個(gè)類(lèi)簇中的樣本點(diǎn)因選出多個(gè)類(lèi)簇中心而被分為多個(gè)類(lèi)簇，對(duì)初始聚類(lèi)結(jié)果進(jìn)行優(yōu)化，將初始類(lèi)簇合并得到最終類(lèi)簇。

1" DPC算法及其缺陷分析

DPC算法基于兩個(gè)基本假設(shè)確定類(lèi)簇中心：

1） 類(lèi)簇中心被局部密度更低的近鄰樣本點(diǎn)包圍；

2） 類(lèi)簇中心與局部密度更高的樣本點(diǎn)的距離相對(duì)較大。

設(shè)有數(shù)據(jù)集[X=x1，x2，…，xN]，其中[xi=xi1，xi2，…，xid，i=1，2，…，N]，表示一個(gè)樣本點(diǎn)，[N]為數(shù)據(jù)集樣本點(diǎn)總數(shù)，[d]為樣本點(diǎn)維數(shù)。對(duì)數(shù)據(jù)集中任意一個(gè)樣本點(diǎn)[xi]，DPC算法分別計(jì)算其局部密度[ρi]，以及與更高密度的最近點(diǎn)之間的距離[δi]。樣本點(diǎn)[xi]的局部密度[ρi]有兩種計(jì)算方法，一種使用截?cái)嗪擞?jì)算，結(jié)果為離散值，公式如下：

[ρi=i≠jχdij-dc] （1）

式中：[χx]是指示函數(shù)，當(dāng)[xlt;0]時(shí)，[χx=1]；否則[χx=0]。另一種使用高斯核計(jì)算，結(jié)果為連續(xù)值，公式為：

[ρi=i≠jexp-dijdc2] （2）

式中：[dij]為樣本點(diǎn)[xi]和[xj]之間的歐氏距離；[dc]為截?cái)嗑嚯x參數(shù)，一般取所有樣本點(diǎn)兩兩之間的距離值升序排列的1%～2%處的值[8]。

通過(guò)計(jì)算樣本點(diǎn)[xi]與其他局部密度更高的點(diǎn)之間的最小距離得到[δi]：

[δi=minj：ρjgt;ρidij] （3）

對(duì)于密度最高的點(diǎn)，一般取[δi=maxjdij]。

接著，DPC算法以[ρi]為橫坐標(biāo)，[δi]為縱坐標(biāo)繪制決策圖，根據(jù)決策圖直觀地選取[ρi]和[δi]值較大的樣本點(diǎn)作為類(lèi)簇中心；或者定義簇中心權(quán)值為[γi=ρi×δi]，選取[γ]值較大的樣本點(diǎn)作為類(lèi)簇中心。最后，將非類(lèi)簇中心樣本點(diǎn)分配到距離其最近的密度更高點(diǎn)所屬類(lèi)簇。

DPC算法不需要預(yù)先確定類(lèi)簇個(gè)數(shù)，在許多數(shù)據(jù)集上聚類(lèi)效果良好，但是截?cái)嗑嚯x的確定帶有主觀經(jīng)驗(yàn)， 影響類(lèi)簇中心的準(zhǔn)確選擇。若截?cái)嗑嚯x較大， 則可能選取到少于真實(shí)個(gè)數(shù)的類(lèi)簇中心；若截?cái)嗑嚯x較小，則可能選取到多于真實(shí)個(gè)數(shù)的類(lèi)簇中心。并且類(lèi)簇中心的選取不是自適應(yīng)的，而是根據(jù)決策圖人工選取的，可能會(huì)造成聚類(lèi)中心的誤選。

圖1所示為DPC算法在Aggregation數(shù)據(jù)集上的決策圖和簇中心權(quán)值降序排列圖。Aggregation數(shù)據(jù)集共有7個(gè)類(lèi)別，可以看出，在沒(méi)有任何先驗(yàn)信息的情況下，僅通過(guò)決策圖難以準(zhǔn)確地選出7個(gè)類(lèi)簇中心，可能會(huì)漏選或者多選，從而影響聚類(lèi)效果。

2" 基于類(lèi)簇合并的無(wú)參數(shù)密度峰值聚類(lèi)算法（NDPCCM）

DPC算法的截?cái)嗑嚯x值直接影響樣本局部密度的度量，類(lèi)簇中心的選擇直接影響最終的聚類(lèi)結(jié)果，而截?cái)嗑嚯x和類(lèi)簇中心的選擇均受主觀影響較大，導(dǎo)致算法的魯棒性較差。

針對(duì)上述問(wèn)題，NDPCCM算法首先根據(jù)樣本點(diǎn)的類(lèi)內(nèi)相似度自動(dòng)確定截?cái)嘞嗨贫龋⒂?jì)算每個(gè)樣本點(diǎn)的簇中心權(quán)值；其次根據(jù)簇中心權(quán)值的斜率變化自動(dòng)選擇初始類(lèi)簇中心，得到初步聚類(lèi)結(jié)果；最后，合并初始類(lèi)簇得到更準(zhǔn)確的聚類(lèi)結(jié)果。

2.1" 截?cái)嘞嗨贫鹊淖詣?dòng)選取

樣本點(diǎn)之間的相似度可以根據(jù)兩個(gè)樣本是否屬于同一類(lèi)別分為類(lèi)內(nèi)相似度和類(lèi)間相似度兩種類(lèi)型。類(lèi)內(nèi)相似度值較大，而類(lèi)間相似度值較小。因此可以根據(jù)相似度的分布特征將其分為兩類(lèi)，并利用類(lèi)內(nèi)相似度來(lái)定義截?cái)嘞嗨贫龋詫?shí)現(xiàn)截?cái)嘞嗨贫鹊淖詣?dòng)選取。

NDPCCM算法首先對(duì)樣本點(diǎn)之間的歐氏距離進(jìn)行函數(shù)變換，得到樣本點(diǎn)之間的相似度；其次使用K?means算法將所有樣本點(diǎn)兩兩之間的相似度分為類(lèi)內(nèi)相似度和類(lèi)間相似度兩種類(lèi)型，定義截?cái)嘞嗨贫葹轭?lèi)內(nèi)相似度的均值；最后使用截?cái)嘞嗨贫扔?jì)算樣本點(diǎn)的局部密度、相對(duì)相似度以及簇中心權(quán)值，具體如下：

1） 對(duì)于數(shù)據(jù)集[X]，定義樣本點(diǎn)[xi]和[xj]之間的相似度[18]為：

[sij=11+d2ij] （4）

式中[dij=k=1dxik-xjk2]為樣本點(diǎn)[xi]和[xj]之間的歐氏距離。樣本點(diǎn)[xi]和[xj]之間的距離越小，相似度則越大。公式（4）運(yùn)用函數(shù)變換將距離值[dij]映射到區(qū)間[（0，1]]上。

2） 使用K?means聚類(lèi)算法將所有相似度值分為兩類(lèi)，其中均值較大的為類(lèi)內(nèi)相似度集合，記為[Sintra]。

定義1：截?cái)嘞嗨贫取㈩?lèi)內(nèi)相似度的均值作為截?cái)嘞嗨贫萚sc]，即：

[sc=1Sintrasij∈Sintrasij] （5）

式中[Sintra]表示集合[Sintra]中元素的個(gè)數(shù)。

3） 利用截?cái)嘞嗨贫扔?jì)算樣本點(diǎn)[xi]的局部密度[ρi]，公式如下：

[ρi=j≠iexpsijsc] （6）

該式表明，當(dāng)樣本點(diǎn)[xi]周?chē)c其相似度大于截?cái)嘞嗨贫萚sc]的點(diǎn)越多，局部密度則越大。

通過(guò)樣本點(diǎn)的局部密度和相似度計(jì)算樣本點(diǎn)的相對(duì)相似度，公式如下：

[δi=minsij，" i=argmaxmρmmaxρjgt;ρisij，" i≠argmaxmρm] " "（7）

式（7）即樣本點(diǎn)與局部密度更高的樣本點(diǎn)之間的最大相似度。當(dāng)樣本點(diǎn)局部密度最大時(shí)，其相對(duì)相似度為該樣本點(diǎn)與其他樣本點(diǎn)之間的最小相似度。

4） 計(jì)算樣本點(diǎn)的簇中心權(quán)值。根據(jù)DPC算法關(guān)于類(lèi)簇中心的假設(shè)，在NDPCCM算法中，具有較高的局部密度[ρ]和較小的相對(duì)相似度[δ]的樣本點(diǎn)更有可能被選為類(lèi)簇中心。

首先，為了和局部密度保持一致，利用對(duì)數(shù)函數(shù)對(duì)相對(duì)相似度進(jìn)行函數(shù)變換，公式如下：

[δ'i=-lg δi] （8）

由[δi]的定義可知，[δi∈0，1]，從而[δ'i∈0，+∞]，并且當(dāng)[δi]越小時(shí)，[δ'i]越大。因此，[ρi]和[δ'i]都較大的樣本點(diǎn)是類(lèi)簇中心的可能性更大。

其次，為了避免[ρ]和[δ']因量綱不同而對(duì)聚類(lèi)結(jié)果產(chǎn)生影響，對(duì)[ρ]和[δ']進(jìn)行歸一化處理，分別得到[ρ?i]和[δ?i]。最后定義樣本點(diǎn)的簇中心權(quán)值。

定義2：簇中心權(quán)值。計(jì)算樣本的簇中心權(quán)值的公式如下：

[γi=ρ?i·δ?i] （9）

根據(jù)前文的分析，類(lèi)簇中心的[γ]值應(yīng)該相對(duì)較大。

2.2" 自動(dòng)選擇初始類(lèi)簇中心

圖2是NDPCCM在Aggregation數(shù)據(jù)集上的樣本[γ]值分割示意圖，利用[γ]值的分段線性回歸，將樣本點(diǎn)分為初始類(lèi)簇中心和非類(lèi)簇中心兩類(lèi)。其中空心圓點(diǎn)表示初始類(lèi)簇中心的[γ]值；空心三角形表示非類(lèi)簇中心的[γ]值；虛線是對(duì)初始類(lèi)簇中心[γ]值的擬合直線；實(shí)線是對(duì)非類(lèi)簇中心[γ]值的擬合直線。根據(jù)[γ]值的下降趨勢(shì)可以將其分為兩部分：左邊[γ]值較大，下降速度較快；右邊[γ]值較小，下降速度較慢。前后兩側(cè)[γ]值下降趨勢(shì)具有明顯差異的分界點(diǎn)稱(chēng)為變點(diǎn)，記為[γt]。因此，NDPCCM算法使用分段線性回歸分析尋找變點(diǎn)，自動(dòng)選擇初始類(lèi)簇中心，避免人工選擇類(lèi)簇中心帶來(lái)的不確定性。

NDPCCM算法首先將[γ]值降序排列得到序列[γ1gt;γ2gt;…gt;γk-1gt;γkgt;γk+1gt;…gt;γN]。依次將每一點(diǎn)[γk（2≤k≤N-1）]作為分界點(diǎn)，得到兩個(gè)[γ]值序列，即[γ1，γ2，…，γk]和[γk+1，γk+2，…，γN]。

其次，取這兩個(gè)序列為因變量，對(duì)應(yīng)的自變量分別取[0，1，2，…，k-1]和[k，k+1，…，N-1]，分別進(jìn)行一元線性回歸分析，得到兩個(gè)[γ]值預(yù)測(cè)序列，即[γ1，γ2，…，γk]和[γ'k+1，γ'k+2，…，γ'N]。

最后計(jì)算誤差平方和[Ek=i=1kγi-γi2+i=k+1Nγ'i-γi2]，于是變點(diǎn)[γt]可以由下式得到：

[t=argmin2≤k≤N-1Ek] （10）

將變點(diǎn)及其之前的點(diǎn)選出作為初始類(lèi)簇中心。得到初始類(lèi)簇中心后，根據(jù)DPC算法的分配策略，將非類(lèi)簇中心點(diǎn)分配給與其相似度最大的密度更高點(diǎn)所屬類(lèi)簇，得到初始類(lèi)簇[P=P1，P2，…，Pt]。

2.3" 初始類(lèi)簇合并

樣本密度不均勻可能會(huì)導(dǎo)致同一類(lèi)簇中出現(xiàn)多個(gè)密度峰，進(jìn)而影響聚類(lèi)結(jié)果。圖3是NDPCCM算法在Aggregation數(shù)據(jù)集上獲取的初始類(lèi)簇，相同數(shù)字代表一類(lèi)。部分原本屬于同一類(lèi)簇的樣本點(diǎn)被劃分成了幾類(lèi)。因此需要對(duì)初始類(lèi)簇進(jìn)行合并，優(yōu)化初始聚類(lèi)結(jié)果，以提高聚類(lèi)的準(zhǔn)確性。

NDPCCM算法將所有的樣本點(diǎn)分為邊界點(diǎn)和核心點(diǎn)兩類(lèi)，若兩個(gè)初始類(lèi)簇之間相似度較大且相似度最大的兩個(gè)樣本點(diǎn)都是核心點(diǎn)，則將這兩個(gè)初始類(lèi)簇合并。

首先，NDPCCM算法根據(jù)樣本點(diǎn)鄰居數(shù)的多少將其分為核心點(diǎn)和邊界點(diǎn)兩類(lèi)。固定一個(gè)相似度半徑[r]，對(duì)于每一個(gè)樣本點(diǎn)，周?chē)c其相似度大于等于[r]的樣本點(diǎn)則被稱(chēng)為該樣本點(diǎn)的鄰居。顯然，邊界點(diǎn)的鄰居數(shù)較少，而核心點(diǎn)的鄰居數(shù)較多。因此可以使用K?means算法將樣本鄰居數(shù)降序排列截成兩段，截?cái)嗵幖礊榕R界鄰居數(shù)。鄰居數(shù)小于該臨界值的樣本點(diǎn)是邊界點(diǎn)，集合記為[Xboundary]，反之則為核心點(diǎn)，集合記為[Xcore]。NDPCCM算法在Aggregation上聚類(lèi)分析圖如圖4所示。

圖4a）所示為Aggregation數(shù)據(jù)集中邊界點(diǎn)示意圖，圖中一個(gè)數(shù)字代表一個(gè)初始類(lèi)簇，加粗的為邊界點(diǎn)。其中，相似度半徑[r]取所有樣本點(diǎn)到其他樣本點(diǎn)的最大相似度的最小值。并且，為了避免離群點(diǎn)的影響，在計(jì)算[r]之前先去除樣本中的離群點(diǎn)。定義滿(mǎn)足如下條件的點(diǎn)[xi]為離群點(diǎn)[19]：

[ρ?ilt;μρ?-σρ?]

[δ?igt;μδ?+σδ?]

式中：[μ·]和[σ·]分別表示數(shù)據(jù)的均值和標(biāo)準(zhǔn)差。將離群點(diǎn)的集合記為[Xoutlier]，則[r=minxi∈X＼Xoutliermaxj≠isij]。

其次，對(duì)于初始類(lèi)簇[Pi]和[Pj]，計(jì)算兩個(gè)類(lèi)簇之間的最大相似度，判斷是否需要合并。記兩個(gè)類(lèi)簇之間相似度最大的樣本分別為[xmi]和[xmj]，即[smi，mj=maxsuvxu∈Pi，xv∈Pj]。若最大相似度大于相似度半徑[r]且[xmi]和[xmj]均為核心點(diǎn)，則將[Pi]和[Pj]合并，即若滿(mǎn)足式（11）， 則將這兩個(gè)初始類(lèi)簇合并。

[smi，mjgt;r，" xmi∈Xcore，" xmj∈Xcore] （11）

重復(fù)進(jìn)行上述步驟，直至任意兩個(gè)類(lèi)簇都不滿(mǎn)足上述條件，得到最終類(lèi)簇[C=C1，C2，…，Cnc]，其中[nc]表示最終類(lèi)簇個(gè)數(shù)。圖4b）是Aggregation數(shù)據(jù)集初始類(lèi)簇合并后的最終聚類(lèi)結(jié)果，一個(gè)數(shù)字代表一類(lèi)。可見(jiàn)，初始類(lèi)簇正確地合并為一個(gè)類(lèi)簇，初始聚類(lèi)結(jié)果得到了優(yōu)化。

2.4" NDPCCM算法的具體步驟

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

輸入：數(shù)據(jù)集[X=x1，x2，…，xN]；

輸出：聚類(lèi)結(jié)果[C=C1，C2，…，Cnc]。

1） 根據(jù)式（4）計(jì)算樣本點(diǎn)之間的相似度[sij]，構(gòu)造相似度矩陣[S=sij]；

2） 將所有的相似度值降序排列，使用K?means聚類(lèi)算法將所有的相似度值分為兩類(lèi)，得到類(lèi)內(nèi)相似度集合[Sintra]；

3） 根據(jù)式（5）～式（7）、式（9）計(jì)算截?cái)嘞嗨贫萚sc]、局部密度[ρi]、相對(duì)相似度[δ]和簇中心權(quán)值[γi]；

4） 將簇中心權(quán)值[γi]降序排列，從左向右對(duì)每個(gè)點(diǎn)的左側(cè)和右側(cè)的[γi]值分別進(jìn)行線性回歸分析，根據(jù)式（10）得到變點(diǎn)[γt]；

5） 將變點(diǎn)及其之前的點(diǎn)選出得到初始類(lèi)簇中心，并分配非類(lèi)簇中心點(diǎn)，得到初始類(lèi)簇[P=P1，P2，…，Pcp]；

6） 對(duì)任意兩個(gè)初始類(lèi)簇[Pi]和[Pj]，若滿(mǎn)足式（11），則將這兩個(gè)類(lèi)簇合并，更新聚類(lèi)結(jié)果；

7） 重復(fù)步驟6），直至任意兩個(gè)類(lèi)簇都不滿(mǎn)足式（11），得到最終類(lèi)簇[C=C1，C2，…，Cnc]。

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

3.1" 數(shù)據(jù)集及實(shí)驗(yàn)參數(shù)設(shè)置

為了驗(yàn)證本文提出的NDPCCM算法的性能，在人工數(shù)據(jù)集和UCI真實(shí)數(shù)據(jù)集上將本文算法與DPC算法、DBSCAN算法以及K?means算法進(jìn)行對(duì)比實(shí)驗(yàn)。數(shù)據(jù)集詳細(xì)信息如表1和表2所示。實(shí)驗(yàn)環(huán)境為Windows 11 64位操作系統(tǒng)，Intel[?] CoreTM i7?1360P CPU @ 2.20 GHz處理器，16.0 GB內(nèi)存，使用Jupyter Notebook編程。

本文采用常用的調(diào)整蘭德指數(shù)（Adjusted Rand Index， ARI）[20]、調(diào)整互信息（Adjusted Mutual Information， AMI）[20]以及FM指數(shù)（Fowlkes and Mallows Index， FMI）[21]這3個(gè)外部評(píng)價(jià)指標(biāo)來(lái)衡量實(shí)驗(yàn)中所使用的聚類(lèi)算法的聚類(lèi)性能。ARI的取值范圍為[[-1，1]]，AMI的取值范圍為[[-1，1]]，F(xiàn)MI的取值范圍為[[0，1]]。3個(gè)指標(biāo)的值越大，表示聚類(lèi)效果越好。

本文的實(shí)驗(yàn)參數(shù)設(shè)置為：NDPCCM算法無(wú)需設(shè)置參數(shù)；DPC算法的參數(shù)[p=2]；DBSCAN算法參數(shù)為鄰域半徑[（Eps）∈[0.1，1]]，以及最少樣本數(shù)[（MinPts）∈[2，20]]，采用網(wǎng)格搜索方法選取最優(yōu)值作為最終的實(shí)驗(yàn)結(jié)果；K?means算法的參數(shù)[k∈2，35]，通過(guò)輪廓系數(shù)選擇參數(shù)。

3.2" 實(shí)驗(yàn)結(jié)果分析

表3給出了NDPCCM算法、DPC算法、DBSCAN算法以及K?means算法在6個(gè)人工數(shù)據(jù)集上的3個(gè)評(píng)價(jià)指標(biāo)（ARI、AMI、FMI）的值以及參數(shù)設(shè)置，其中加粗字體表示性能最好的實(shí)驗(yàn)結(jié)果。表4給出了NDPCCM算法、DPC算法、DBSCAN算法以及K?means算法在4個(gè)真實(shí)數(shù)據(jù)集上的3個(gè)評(píng)價(jià)指標(biāo)（ARI、AMI、FMI）的值以及參數(shù)設(shè)置，其中加粗字體表示性能最好的實(shí)驗(yàn)結(jié)果。

從表中的實(shí)驗(yàn)結(jié)果可以看出，與其他算法相比，NDPCCM算法在除了Spiral和Breast之外的其他數(shù)據(jù)集上3個(gè)聚類(lèi)指標(biāo)都達(dá)到了最優(yōu)。在Spiral數(shù)據(jù)集上，NDPCCM算法性能僅次于DPC算法；在Breast數(shù)據(jù)集上，NDPCCM算法AMI和FMI值都達(dá)到了最大，ARI值僅次于DBSCAN算法。

通過(guò)在人工數(shù)據(jù)集和UCI真實(shí)數(shù)據(jù)集上的對(duì)比實(shí)驗(yàn)可以體現(xiàn)本文提出算法的優(yōu)越性。DPC算法需要人為選擇參數(shù)和聚類(lèi)中心；DBSCAN算法對(duì)參數(shù)敏感；K?means算法對(duì)于非凸數(shù)據(jù)的聚類(lèi)效果較差，并且需要預(yù)先確定參數(shù)的范圍；而NDPCCM算法無(wú)需輸入?yún)?shù)，自動(dòng)完成聚類(lèi)，并且聚類(lèi)性能更好。

4" 結(jié)" 語(yǔ)

本文針對(duì)DPC算法中截?cái)嗑嚯x和聚類(lèi)中心的人為選擇問(wèn)題， 對(duì)DPC算法進(jìn)行改進(jìn)， 提出一種基于類(lèi)簇合并的無(wú)參數(shù)密度峰值聚類(lèi)算法（NDPCCM）。該算法首先根據(jù)類(lèi)內(nèi)相似度自動(dòng)確定截?cái)嘞嗨贫龋⒂?jì)算局部密度、相對(duì)相似度和簇中心權(quán)值；其次根據(jù)簇中心權(quán)值的下降趨勢(shì)自動(dòng)選取初始類(lèi)簇中心；最后對(duì)初始類(lèi)簇進(jìn)行優(yōu)化，得到最終的聚類(lèi)結(jié)果。NDPCCM算法無(wú)需輸入任何參數(shù)， 并且整個(gè)聚類(lèi)過(guò)程都是自動(dòng)完成的。在人工數(shù)據(jù)集和UCI真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，NDPCCM算法取得了優(yōu)于其他算法的聚類(lèi)效果，性能穩(wěn)定，適用于不同類(lèi)型的數(shù)據(jù)集。但是在NDPCCM算法中，仍然利用歐氏距離度量相似度，在處理大量數(shù)據(jù)時(shí)，計(jì)算復(fù)雜度高；面對(duì)真實(shí)的高維數(shù)據(jù)集時(shí)，性能較差。因此，改進(jìn)相似度度量和提升NDPCCM對(duì)真實(shí)復(fù)雜的數(shù)據(jù)集的聚類(lèi)性能是下一步的研究重點(diǎn)。

注：本文通訊作者為袁永生。

參考文獻(xiàn)

[1] BHATTACHARJEE P， MITRA P. A survey of density based clustering algorithms [J]. Frontiers of computer science， 2021， 15（1）： 151308.

[2] SI Y Q， LIU P， LI P H， et al. Model?based clustering for RNA?seq data [J]. Bioinformatics， 2014， 30（2）： 197?205.

[3] DUCOURNAU A， BRETTO A， RITAL S， et al. A reductive approach to hypergraph clustering： an application to image segmentation [J]. Pattern recognition， 2012， 45（7）： 2788?2803.

[4] CHAUDHARY C， GOYAL P， TULI S， et al. A novel multi?modal clustering framework for images with diverse associ?ated text [J]. Multimedia tools and applications， 2019， 78（13）： 17623?17652.

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

[6] DU M J， DING S F， JIA H J. Study on density peaks clus?tering based on K?nearest neighbors and principal component analysis [J]. Knowledge?based systems， 2016， 99： 135?145.

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

[8] LIU R， WANG H， YU X M. Shared?nearest?neighbor?based clustering by fast search and find of density peaks [J]. Information sciences， 2018， 450： 200?226.

[9] 丁世飛，徐曉，王艷茹.基于不相似性度量?jī)?yōu)化的密度峰值聚類(lèi)算法[J].軟件學(xué)報(bào)，2020，31（11）：3321?3333.

[10] 章曼，張正軍，馮俊淇，等.基于自適應(yīng)可達(dá)距離的密度峰值聚類(lèi)算法[J].計(jì)算機(jī)應(yīng)用，2022，42（6）：1914?1921.

[11] 位雅，張正軍，何凱琳，等.基于相對(duì)密度的密度峰值聚類(lèi)算法[J].計(jì)算機(jī)工程，2023，49（6）：53?61.

[12] BIE R F， MEHMOOD R， RUAN S S， et al. Adaptive fuzzy clustering by fast search and find of density peaks [J]. Personal and ubiquitous computing， 2016， 20（5）： 785?793.

[13] LIANG Z， CHEN P. Delta?density based clustering with a divide?and?conquer strategy： 3DC clustering [J]. Pattern recognition letters， 2016， 73： 52?59.

[14] 馬春來(lái)，單洪，馬濤.一種基于簇中心點(diǎn)自動(dòng)選擇策略的密度峰值聚類(lèi)算法[J].計(jì)算機(jī)科學(xué)，2016，43（7）：255?258.

[15] 王萬(wàn)良，吳菲，呂闖.自動(dòng)確定聚類(lèi)中心的快速搜索和發(fā)現(xiàn)密度峰值的聚類(lèi)算法[J].模式識(shí)別與人工智能，2019，32（11）：1032?1041.

[16] 徐童童，解濱，張喜梅，等.自適應(yīng)聚類(lèi)中心策略?xún)?yōu)化的密度峰值聚類(lèi)算法[J].計(jì)算機(jī)工程與應(yīng)用，2023，59（21）：91?101.

[17] DING S F， DU W， XU X， et al. An improved density peaks clustering algorithm based on natural neighbor with a merging strategy [J]. Information sciences， 2023， 624： 252?276.

[18] 吳潤(rùn)秀，尹士豪，趙嘉，等.基于相對(duì)密度估計(jì)和多簇合并的密度峰值聚類(lèi)算法[J].控制與決策，2023，38（4）：1047?1055.

[19] TONG W N， WANG Y P， LIU D L. An adaptive clustering algorithm based on local?density peaks for imbalanced data without parameters [J]. IEEE transactions on knowledge and data engineering， 2023， 35（4）： 3419?3432.

[20] VINH N X， EPPS J， BAILEY J. Information theoretic measures for clusterings comparison： variants， properties， normalization and correction for chance [J]. The journal of machine learning research， 2010， 11： 2837?2854.

[21] FOWLKES E B， MALLOWS C L. A method for comparing two hierarchical clusterings [J]. Journal of the American statistical association， 1983， 78（383）： 553?569.

作者簡(jiǎn)介：劉天嬌（1998—），女，江蘇南通人，碩士研究生，研究方向?yàn)榻y(tǒng)計(jì)學(xué)習(xí)、應(yīng)用統(tǒng)計(jì)。

王勝景（1999—），女，河南駐馬店人，碩士研究生，研究方向?yàn)榻y(tǒng)計(jì)學(xué)習(xí)、應(yīng)用統(tǒng)計(jì)。

袁永生（1964—），男，江蘇南通人，博士，教授，主要研究方向?yàn)閿?shù)理統(tǒng)計(jì)、應(yīng)用統(tǒng)計(jì)。