基于局部引力和距離的聚類算法

杜潔，馬燕，黃慧

（上海師范大學(xué) 信息與機(jī)電工程學(xué)院，上海 201418）（?通信作者電子郵箱ma?yan@shnu.edu.cn）

基于局部引力和距離的聚類算法

杜潔，馬燕*，黃慧

（上海師范大學(xué) 信息與機(jī)電工程學(xué)院，上海 201418）（?通信作者電子郵箱ma?yan@shnu.edu.cn）

密度峰值聚類（DPC）算法對(duì)于密度多樣、形狀復(fù)雜的數(shù)據(jù)集不能準(zhǔn)確選擇聚類中心，同時(shí)基于局部引力的聚類（LGC）算法參數(shù)較多且需要手動(dòng)調(diào)參。針對(duì)這些問題，提出了一種基于局部引力和距離的聚類算法（LGDC）。首先，利用局部引力模型計(jì)算數(shù)據(jù)點(diǎn)的集中度（CE），根據(jù)集中度確定每個(gè)數(shù)據(jù)點(diǎn)與高集中度的點(diǎn)之間的距離；然后，選取具有高集中度值和高距離值的數(shù)據(jù)點(diǎn)作為聚類中心；最后，基于簇的內(nèi)部點(diǎn)集中度遠(yuǎn)高于邊界點(diǎn)的集中度的思想，分配其余數(shù)據(jù)點(diǎn)，并且利用平衡k近鄰實(shí)現(xiàn)參數(shù)的自動(dòng)調(diào)整。實(shí)驗(yàn)結(jié)果表明，LGDC在4個(gè)合成數(shù)據(jù)集上取得了更好的聚類效果；且在Wine、SCADI、Soybean等真實(shí)數(shù)據(jù)集上，LGDC的調(diào)整蘭德系數(shù)（ARI）指標(biāo)相較DPC、LGC等算法平均提高了0.144 7。

密度峰值聚類；引力聚類；局部引力模型；集中度；距離

0 引言

聚類的主要目的是對(duì)一組對(duì)象進(jìn)行分類，使得同一類的對(duì)象盡可能相似，不同類之間的對(duì)象盡量不相似［1］。聚類算法可以應(yīng)用于圖像分割［2］、社區(qū)發(fā)現(xiàn)［3］等領(lǐng)域。聚類算法一般可以分為：基于劃分的方法［4］、基于密度的方法［5］、基于層次的方法［6］、基于圖論的方法［7］和基于網(wǎng)格的方法［8］。K-means［9］是一種經(jīng)典的劃分聚類算法，該算法只適用于球狀簇，且聚類結(jié)果易受初始聚類中心的影響。基于密度的噪聲應(yīng)用空間聚類（Density-Based Spatial Clustering of Application with Noise， DBSCAN）算法［10］，可以找到任意形狀的簇，但其聚類結(jié)果易受閾值和鄰域半徑這兩個(gè)參數(shù)的影響。

2014年，Rodriguez等［11］提出了密度峰值聚類（Density Peak Clustering， DPC）算法，該算法認(rèn)為聚類中心的密度高于其周圍數(shù)據(jù)點(diǎn)的密度，且與其他高密度的點(diǎn)距離較遠(yuǎn)。但是該算法僅根據(jù)數(shù)據(jù)點(diǎn)之間的距離計(jì)算密度，不適用于形狀、密度復(fù)雜的數(shù)據(jù)集；在基于距離分配數(shù)據(jù)點(diǎn)時(shí)，算法魯棒性差，而且聚類結(jié)果對(duì)于截止距離的取值較敏感。

在基于引力的聚類算法方面，溫曉芳等［12］提出了一種密度引力聚類新算法，雖然該算法引入了引力的概念，但仍舊是在基于密度的基礎(chǔ)上進(jìn)行聚類，無(wú)法避免DPC存在的問題。Wang等［13］提出了一種基于局部引力的聚類（Clustering by Local Gravitation， LGC）算法，它根據(jù)局部引力模型推導(dǎo)出局部中心度量，以區(qū)分內(nèi)部點(diǎn)和邊界點(diǎn)。但這種方法需要確定多個(gè)參數(shù)，且對(duì)參數(shù)取值異常敏感。在此基礎(chǔ)上，Wang等［13］又提出了社團(tuán)聚類（Clustering by Community with Local Agents，CLA）算法，將參數(shù)減少到一個(gè)，但聚類效果有所下降。

針對(duì)DPC存在的問題，Liu等［14］基于共享最近鄰計(jì)算數(shù)據(jù)點(diǎn)之間的局部密度和相對(duì)距離，可以對(duì)復(fù)雜密度的數(shù)據(jù)集有效聚類；吳斌等［15］提出了一種基于基尼系數(shù)自適應(yīng)調(diào)整截止距離的算法，避免了聚類結(jié)果對(duì)截止距離敏感的問題；Jiang等［16］則在DPC的基礎(chǔ)上引入了萬(wàn)有引力，用引力來類比距離，降低了數(shù)據(jù)集形狀對(duì)聚類結(jié)果的影響。

為了解決DPC和LGC算法存在的問題，本文提出了一種基于局部引力和距離的聚類算法（Clustering algorithm based on Local Gravity and Distance， LGDC）。該算法通過局部引力模型計(jì)算數(shù)據(jù)點(diǎn)的集中度，從而確定聚類中心。相較基于密度選取聚類中心的方法，局部引力模型可以避免簇的密度和形狀對(duì)聚類結(jié)果的影響，并且通過k平衡近鄰對(duì)參數(shù)自動(dòng)調(diào)整。同時(shí)，本文設(shè)計(jì)了一種基于集中度的數(shù)據(jù)點(diǎn)分配方法，使得算法魯棒性更強(qiáng)。實(shí)驗(yàn)結(jié)果表明，本文所提LGDC優(yōu)于DPC和LGC等算法。

1 相關(guān)工作

1.1 經(jīng)典DPC算法

密度峰值聚類算法選取密度比其鄰域高，且與高密度點(diǎn)之間距離較大的點(diǎn)作為聚類中心。對(duì)數(shù)據(jù)集中的每一個(gè)點(diǎn)Xi，需要計(jì)算其密度和距離。

其中：dij是點(diǎn)Xi和點(diǎn)Xj之間的距離；dc是根據(jù)經(jīng)驗(yàn)選取的截止距離，一般是對(duì)所有數(shù)據(jù)點(diǎn)之間的距離按降序排列，再將前1%～2%位置所對(duì)應(yīng)的距離值看作dc值。距離表示點(diǎn)Xi與比它密度高的點(diǎn)之間的最小距離，計(jì)算如式（2）所示：

1.2 局部引力模型

受到牛頓萬(wàn)有引力定律的啟發(fā)，在聚類過程中，數(shù)據(jù)點(diǎn)之間的局部引力可以反映數(shù)據(jù)點(diǎn)與其鄰域點(diǎn)之間的關(guān)系。根據(jù)萬(wàn)有引力定律［17］，兩個(gè)質(zhì)點(diǎn)之間的引力可以定義為：

數(shù)據(jù)點(diǎn)Xi的k個(gè)近鄰點(diǎn)對(duì)它產(chǎn)生的局部合力（Local Resultant Force， LRF）可以表示為：

其中：k表示點(diǎn)Xi的近鄰點(diǎn)數(shù)目。由式（5）可得，Xi質(zhì)量越大，對(duì)于鄰域的影響也越大；同樣地，質(zhì)量越小，就越容易受到近鄰點(diǎn)的影響。因此，對(duì)于LRF可以進(jìn)行如式（6）的簡(jiǎn)化：

2 基于局部引力和距離的聚類算法

2.1 確定聚類中心

對(duì)于每個(gè)數(shù)據(jù)點(diǎn)Xi，需要計(jì)算兩個(gè)量：該點(diǎn)的集中度CEi和它與高集中度的點(diǎn)之間的距離。本文利用LRF中包含的信息，計(jì)算點(diǎn)Xi的集中度CEi，定義如下：

圖1 數(shù)據(jù)點(diǎn)位置與CE的關(guān)系Fig. 1 Relationship between data point location and CE

此外，聚類中心還存在集中度高且相互之間距離較大的特點(diǎn)。令δi表示點(diǎn)Xi與集中度更高的所有數(shù)據(jù)點(diǎn)之間的距離的最小值，計(jì)算式如下：

對(duì)于具有最高集中度的點(diǎn)，則定義為：

如果一個(gè)數(shù)據(jù)點(diǎn)具有較大的集中度CE和距離，即具有較大的值，那么該點(diǎn)很有可能是聚類中心，定義如下：

如圖2所示，該數(shù)據(jù)集的簇間密度變化較大，白色空心點(diǎn)表示聚類中心。如圖2（a）、（b）所示，DPC無(wú)法準(zhǔn)確選取聚類中心；如圖2（c）、（d）所示，本文利用CE和可以準(zhǔn)確找到聚類中心。

圖2 決策圖和對(duì)應(yīng)的聚類中心位置Fig. 2 Decision graph and corresponding cluster center locations

2.2 數(shù)據(jù)點(diǎn)分配方法

DPC算法的數(shù)據(jù)點(diǎn)分配策略采用一步分配歸類，容錯(cuò)性和魯棒性較差。因此，本文設(shè)計(jì)了一種新的數(shù)據(jù)點(diǎn)分配方法。

假設(shè)經(jīng)過2.1節(jié)確定Nc個(gè)聚類中心，對(duì)聚類中心按集中度CE降序排序，表示為C1，C2，…，CN。對(duì)每個(gè)聚類中心，確定一個(gè)掃描半徑，表示為R1，R2，…，RN，即Ci的掃描半徑為Ri。Ri定義如下：

其中：Pk表示聚類中心點(diǎn)Ci的第k個(gè)近鄰點(diǎn)；表示聚類中心Ci與第k個(gè)鄰點(diǎn)Pk之間的距離。

對(duì)擁有Nc個(gè)聚類中心的數(shù)據(jù)集，需要進(jìn)行Nc輪掃描。一般地，每一輪中包含多次掃描，首次均以Ci為圓心、Ri為半徑開始。對(duì)掃描范圍內(nèi)的點(diǎn)進(jìn)行標(biāo)記，被標(biāo)記的點(diǎn)會(huì)被作為下一次掃描的圓心，循環(huán)直至滿足終止條件，進(jìn)入到下一輪掃描。

終止條件設(shè)置如下：由2.1節(jié)可知，簇的內(nèi)部數(shù)據(jù)點(diǎn)的集中度遠(yuǎn)大于邊界點(diǎn)，即內(nèi)部點(diǎn)的CE值大于邊界點(diǎn)的CE值。所以，當(dāng)某次掃描范圍內(nèi)數(shù)據(jù)點(diǎn)的CE總和遠(yuǎn)小于該輪次中以聚類中心進(jìn)行首次掃描時(shí)的CE總和時(shí)，當(dāng)前掃描范圍內(nèi)的數(shù)據(jù)點(diǎn)將不再被標(biāo)記。掃描范圍內(nèi)數(shù)據(jù)點(diǎn)的CE總和計(jì)算如式（13）所示：

式（13）表示對(duì)于以Pi為圓心、Ri為半徑的圓，對(duì)圓內(nèi)的每個(gè)點(diǎn)Pj的集中度CEj進(jìn)行求和。記每一輪中對(duì)聚類中心Ci首次掃描時(shí)的集中度總和為。當(dāng)小于時(shí)（這里，α為閾值，2.4.2節(jié)討論α的確定方法），當(dāng)前掃描滿足終止條件，不再對(duì)數(shù)據(jù)點(diǎn)進(jìn)行標(biāo)記。經(jīng)大量實(shí)驗(yàn)可得，α取0.5時(shí)效果較好。

如圖3所示，是一個(gè)包含2個(gè)簇的二維數(shù)據(jù)集，假設(shè)該數(shù)據(jù)集近鄰數(shù)k為12。數(shù)據(jù)點(diǎn)分配具體過程以圖3為例：1）圖3（a）中灰色數(shù)據(jù)點(diǎn)為聚類中心C1，以R1為半徑進(jìn)行掃描，掃描到的數(shù)據(jù)點(diǎn)被標(biāo)記為白色；2）如圖3（b）所示，白色數(shù)據(jù)點(diǎn)被作為掃描的圓心，掃描到的數(shù)據(jù)點(diǎn)同樣被標(biāo)記；3）如圖3（c）所示，當(dāng)前掃描滿足終止條件，停止掃描；4）如圖3（d）所示，結(jié)束左邊簇的掃描后，對(duì)右邊簇進(jìn)行以R2為半徑的第二輪掃描。由圖3（d）可以看到，仍有數(shù)據(jù)點(diǎn)未被分配到任何一個(gè)簇，將這些點(diǎn)按照距離分配給離其最近的簇中。

圖3 數(shù)據(jù)點(diǎn)分配過程示意圖Fig. 3 Schematic diagram of data point allocation process

2.3 算法的主要步驟描述

LGDC的具體實(shí)現(xiàn)步驟如算法1所示。

算法1 LGDC。

輸入 數(shù)據(jù)集D，聚類簇?cái)?shù)Nc；

輸出 聚類結(jié)果C。

步驟1 根據(jù)式（6）計(jì)算數(shù)據(jù)集D中各個(gè)點(diǎn)的局部合力。

步驟2 根據(jù)式（8）計(jì)算每個(gè)點(diǎn)的集中度CE，并按CE值對(duì)所有點(diǎn)降序排序。

步驟5 選擇Nc個(gè)擁有最大值的點(diǎn)作為聚類中心，并對(duì)Nc個(gè)聚類中心按CE值從大到小排序。

步驟6 對(duì)每個(gè)聚類中心點(diǎn)，根據(jù)式（12）確定掃描半徑Ri。

步驟8 對(duì)各聚類中心以Ri為半徑進(jìn)行掃描，標(biāo)記掃描到的點(diǎn)。

步驟9 對(duì)標(biāo)記的點(diǎn)繼續(xù)以Ri為半徑進(jìn)行掃描，并根據(jù)式（13）計(jì)算。

步驟10 若不滿足終止條件，標(biāo)記掃描到的點(diǎn)，重復(fù)步驟9；否則，若還有未掃描的聚類中心點(diǎn)，轉(zhuǎn)到步驟6，若中心點(diǎn)均已掃描，轉(zhuǎn)到步驟11。

步驟11 將未分類的點(diǎn)按照距離分配給離其最近的簇中。

步驟12 返回聚類結(jié)果C。

2.4 參數(shù)的確定

2.4.1k近鄰的確定

首先根據(jù)數(shù)據(jù)集的樣本量初步確定近鄰數(shù)k，通常初始k值可以設(shè)置為樣本量的0.5%～1.5%。為了進(jìn)一步提高聚類效果，在計(jì)算LRF時(shí)采用平衡k近鄰［13］代替k近鄰。對(duì)每個(gè)數(shù)據(jù)點(diǎn)，需要計(jì)算從第k個(gè)到第2k個(gè)鄰點(diǎn)產(chǎn)生的所有LRF，然后選擇LRF取得最小值時(shí)對(duì)應(yīng)的近鄰數(shù)的取值，并用其替換掉初始的k值，定義如下：

2.4.2 參數(shù)α的確定

聚類中心確定之后，其余數(shù)據(jù)點(diǎn)的分配從高集中度的簇開始，即按照降序進(jìn)行掃描。值與掃描范圍內(nèi)數(shù)據(jù)點(diǎn)的CE值有關(guān)，而CE則與數(shù)據(jù)點(diǎn)的位置分布和距離有關(guān)，因此本文α的取值與掃描半徑相關(guān)聯(lián)。經(jīng)過多次實(shí)驗(yàn)，對(duì)α取值定義如下：假設(shè)有Nc個(gè)簇，按照簇的初始集中度從高到低排序?yàn)镃1，C2，…，CN，則對(duì)應(yīng)的掃描半徑為R1，R2，…，RN，α的值為：

2.5 算法復(fù)雜度分析

LGDC的時(shí)間復(fù)雜度包括三部分：1）對(duì)每個(gè)數(shù)據(jù)點(diǎn)，利用K-D（K-Dimension）樹確定k近鄰［18］，所需時(shí)間為，n表示數(shù)據(jù)集的樣本量。2）確定聚類中心需要計(jì)算兩個(gè)指標(biāo)CE和。CE是在LRF的基礎(chǔ)上計(jì)算的，因此計(jì)算LRF和CE所需時(shí)間為，其中k表示每個(gè)點(diǎn)的近鄰數(shù)，計(jì)算的時(shí)間復(fù)雜度為。3）在數(shù)據(jù)點(diǎn)分配階段，假設(shè)簇的數(shù)量為Nc，那么算法的時(shí)間復(fù)雜度為，其中，，。因此，LGDC的整體時(shí)間復(fù)雜度為。

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

選用人工數(shù)據(jù)集［19-21］和UCI（University of California Irvine）［22］真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)集的詳細(xì)信息如表1所示，并將本文算法與K-means［9］、DPC［11］、GDPC［16］、LGC［13］、CLA［13］算法進(jìn)行比較。其中DPC和GDPC算法需要確定值，根據(jù)原文獻(xiàn)的建議，實(shí)驗(yàn)中均設(shè)置為2%。LGC和CLA的參數(shù)取值需要根據(jù)聚類效果調(diào)整到最優(yōu)；本文算法需要根據(jù)數(shù)據(jù)集樣本量確定初始k值，之后算法會(huì)根據(jù)2.4.1節(jié)自動(dòng)調(diào)整k的大小。各算法在數(shù)據(jù)集上的參數(shù)取值具體如表2所示。

實(shí)驗(yàn)開發(fā)環(huán)境為Matlab 2016a，硬件條件為：Intel Core i5-6500 CPU，主頻3.20 GHz，內(nèi)存8.00 GB。

3.1 人工數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果分析

本文采用4個(gè)人工數(shù)據(jù)集DS1～DS4驗(yàn)證聚類效果，圖4～7為各算法分別對(duì)DS1～DS4的聚類結(jié)果。

表1 數(shù)據(jù)集信息Tab. 1 Information of datasets

圖4為DS1上六種算法得到的聚類結(jié)果。GDPC、CLA、LGC和LGDC都可以準(zhǔn)確確定聚類個(gè)數(shù)且聚類效果都很好，K-means和DPC不能對(duì)形狀復(fù)雜的數(shù)據(jù)集DS1正確劃分簇類。

圖5為DS2上六種算法得到的聚類結(jié)果。六種算法都對(duì)DS2做了較好的聚類，其中GDPC、CLA和LGDC的結(jié)果更為準(zhǔn)確，其余三種算法沒有很好地劃分邊界點(diǎn)。

圖6為DS3上六種算法得到的聚類結(jié)果。LGC和LGDC的聚類效果都很好。K-means、DPC、GDPC和CLA算法都不能很好地對(duì)長(zhǎng)條狀數(shù)據(jù)簇進(jìn)行劃分，長(zhǎng)條狀數(shù)據(jù)簇被分為多個(gè)類。

圖7為DS4上六種算法得到的聚類結(jié)果。K-means、CLA和LGDC可以在密度變化大的數(shù)據(jù)集上準(zhǔn)確聚類。DPC、GDPC和LGC無(wú)法找到正確的聚類中心導(dǎo)致聚類效果較差。

實(shí)驗(yàn)結(jié)果表明，LGDC在密度、形狀復(fù)雜的二維數(shù)據(jù)集上都可以獲得較好的聚類效果。

表2 不同算法在不同數(shù)據(jù)集上的參數(shù)取值Tab. 2 Parameter settings of different algorithms on different datasets

3.2 UCI數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果分析

為了進(jìn)一步驗(yàn)證LGDC的性能，采用了三種常用的內(nèi)部聚類驗(yàn)證指標(biāo)，包括：蘭德系數(shù)（Rand Index， RI）［23］、調(diào)整蘭德系數(shù)（Adjustable Rand Index， ARI）［23］和F指標(biāo)（F Measure， FM）［24］來評(píng)估聚類算法的效果。

圖4 六種算法在DS1上的聚類結(jié)果Fig. 4 Clustering results of six algorithms on DS1

在已知數(shù)據(jù)集標(biāo)簽的基礎(chǔ)上，可以得到真正例（True Positive，TP）、假正例（False Positive，F(xiàn)P）、假負(fù)例（False Negative，F(xiàn)N）、真負(fù)例（True Negative，TN）［25］，根據(jù)這4個(gè)數(shù)據(jù)可以計(jì)算RI、ARI和FM，具體計(jì)算式分別如式（16）、（17）和（18）所示：

其中：E（?）表示取期望值；max（?）表示取最大值。召回率（REcall，RE）和準(zhǔn)確率（PRecision， PR）［26］的具體計(jì)算方法如式（19）、（20）所示：

RI的取值范圍為［0，1］，0代表聚類效果非常差；ARI的取值范圍為，該指標(biāo)能夠去掉隨機(jī)標(biāo)簽對(duì)于RI評(píng)估結(jié)果的影響；FM的取值范圍為［0，1］。這三種評(píng)價(jià)指標(biāo)的值越大，代表聚類效果越好。

表3中，評(píng)價(jià)指標(biāo)結(jié)果保留小數(shù)點(diǎn)后四位，加粗值表示較好的實(shí)驗(yàn)結(jié)果。由表3可知，在ARI評(píng)價(jià)指標(biāo)值上，LGDC都要優(yōu)于其他對(duì)比算法，平均提升了0.144 7，最高提升了0.346 3；在FM指標(biāo)上，LGDC除了在Waveform和Statlog數(shù)據(jù)集上效果差一些，在其他數(shù)據(jù)集上都達(dá)到了最優(yōu)。雖然LGC算法聚類效果較好，但是需要設(shè)置三個(gè)參數(shù)，而且實(shí)驗(yàn)結(jié)果對(duì)于參數(shù)取值過于敏感，需要不斷調(diào)參達(dá)到最優(yōu)聚類效果。綜合三種指標(biāo)來看，LGDC優(yōu)于K-means、DPC、GDPC、LGC和CLA算法。

圖5 六種算法在DS2上的聚類結(jié)果Fig. 5 Clustering results of six algorithms on DS2

圖6 六種算法在DS3上的聚類結(jié)果Fig. 6 Clustering results of six algorithms on DS3

圖7 六種算法在DS4上的聚類結(jié)果Fig. 7 Clustering results of six algorithms on DS4

表3 六種聚類算法在真實(shí)數(shù)據(jù)集上的結(jié)果對(duì)比Tab. 3 Result comparison of six clustering algorithms on real datasets

4 結(jié)語(yǔ)

針對(duì)DPC和LGC聚類算法的效果易受數(shù)據(jù)集分布和參數(shù)影響的問題，本文提出了一種基于局部引力和距離的聚類算法。該算法基于局部引力模型，考慮數(shù)據(jù)點(diǎn)的集中度和距離，而不是原始DPC算法中根據(jù)密度峰值決定聚類中心，這能夠有效避免密度變化給聚類結(jié)果帶來的影響；另外，根據(jù)數(shù)據(jù)點(diǎn)的集中度，設(shè)計(jì)了一種新的數(shù)據(jù)點(diǎn)分配方法，這種分配方式能夠適用于形狀復(fù)雜的數(shù)據(jù)集。本文進(jìn)行了多次實(shí)驗(yàn)，在4個(gè)合成數(shù)據(jù)集和6個(gè)真實(shí)數(shù)據(jù)集上，將K-means、DPC、GDPC、LGC、CLA和LGDC進(jìn)行實(shí)驗(yàn)對(duì)比，實(shí)驗(yàn)結(jié)果表明LGDC在多個(gè)數(shù)據(jù)集上的聚類效果都優(yōu)于DPC、LGC等對(duì)比算法。

[1] WANG Y， MA Y， HUANG H. A neighborhood-based three-stage hierarchical clustering algorithm ［J］. Multimedia Tools and Applications， 2021， 80： 32379-32407.

[2] LV X B， MA Y， HE X F， et al. CciMST： a clustering algorithm based on minimum spanning tree and cluster centers. mathematical problems in engineering ［J］. Mathematical Problems in Engineering， 2018， 2018： Article No.8451796.

[3] XIE W B， LEE Y L， WANG C， et al. Hierarchical clustering supported by reciprocal nearest neighbors ［J］. Information Sciences， 2020， 527： 279-292.

[4] FELDMAN D， SCHMIDT M， SOHLER C. Turning big data into tiny data：constant-size core sets fork-means， PCA and projective clustering ［C］// Proceedings of the 2013 24th Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia： SIAM， 2013：1434-1453.

[5] MA Y， LIN H R， WANG Y， et al. A multi-stage hierarchical clustering algorithm based on centroid of tree and cut edge constraint ［J］. Information Sciences， 2021， 557： 194-219.

[6] YANG J， MA Y， ZHANG X F， et al. An initialization method based on hybrid distance fork-means algorithm ［J］. Neural Computation， 2017， 29（11）： 3094-3117.

[7] NG A Y， JORDAN M I， WEISS Y. On spectral clustering： analysis and an algorithm ［C］// Proceedings of the 2001 14th International Conference on Neural Information Processing Systems. Cambridge： MIT Press， 2001： 849-856.

[8] SHEIKHOLESLAMI G，CHATTERJEE S， ZHANG A D. WaveCluster： a wavelet-based clustering approach for spatial data in very large databases ［J］. The VLDB Journal， 2000， 8（3/4）： 289-304.

[9] 郭佳，韓李濤，孫憲龍，等.自動(dòng)確定聚類中心的比較密度峰值聚類算法［J］.計(jì)算機(jī)應(yīng)用，2021，41（3）：738-744.（GUO J， HAN L T， SUN X L， et al. Comparative density peaks clustering algorithm with automatic determination of clustering center ［J］. Journal of Computer Applications， 2021， 41（3）： 738-744.）

[10] 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 1996 2nd International Conference on Knowledge Discovery and Data Mining. Palo Alto： AAAI Press， 1996：226-231.

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

[12] 溫曉芳，楊志翀，陳梅.數(shù)據(jù)點(diǎn)的密度引力聚類新算法［J］.計(jì)算機(jī)科學(xué)與探索，2018，12（12）：1996-2006.（WEN X F， YANG Z C，CHEN M. Density attraction clustering algorithm between data points ［J］. Journal of Frontiers of Computer Science and Technology， 2018， 12（12）： 1996-2006.）

[13] WANG Z Q， YU Z W， CHEN C L P， et al. Clustering by local gravitation ［J］. IEEE Transactions on Cybernetics， 2018， 48（5）： 1383-1396.

[14] 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.

[15] 吳斌，盧紅麗，江惠君.自適應(yīng)密度峰值聚類算法［J］.計(jì)算機(jī)應(yīng)用，2020，40（6）：1654-1661.（WU B， LU H L， JIANG H J. Adaptive density peaks clustering algorithm ［J］. Journal of Computer Applications， 2020， 40（6）： 1654-1661.）

[16] JIANG J H， HAO D H， CHEN Y J， et al. GDPC： Gravitation-based Density Peaks Clustering algorithm ［J］. Physica A：Statistical Mechanics and its Applications， 2018， 502： 345-355.

[17] WRIGHT W E. Gravitational clustering ［J］. Pattern Recognition， 1977， 9（3）： 151-166.

[18] WANG X X， ZHANG Y F， XIE J， et al. A density-core-based clustering algorithm with local resultant force ［J］. Soft Computing， 2020， 24（9）：6571-6590.

[19] BRYANT A， CIOS K. RNN-DBSCAN： a density-based clustering algorithm using reverse nearest neighbor density estimates ［J］. IEEE Transactions on Knowledge and Data Engineering， 2018， 30（6）： 1109-1121.

[20] 魏康園，何慶，徐欽帥.基于改進(jìn)引力搜索算法的K-means聚類［J］.計(jì)算機(jī)應(yīng)用研究，2019，36（11）：3240-3244.（WEI K Y， HE Q， XU Q S. NovelK-means clustering algorithm based on improved gravitational search algorithm ［J］. Application Research of Computers， 2019， 36（11）： 3240-3244.）

[21] 孫偉鵬.基于密度峰值聚類算法的研究與實(shí)現(xiàn)［D］.無(wú)錫：江南大學(xué)，2018：39-50.（SUN W P. Research and implementation of density peaks clustering algorithm ［D］. Wuxi： Jiangnan University， 2018： 39-50.）

[22] DUA D， GRAFF C. UCI machine learning repository ［DS/OL］. ［2020-11-05］. http：//archive.ics.uci.edu/ml.

[23] YEUNG K Y， RUZZO W L. Principal component analysis for clustering gene expression data ［J］. Bioinformatics，2001， 17（9）： 763-774.

[24] HUANG Y P J， POWERS R， MONTELIONE G T. Protein NMR Recall，Precision andF-measure Scores （RPF Scores）： structure quality assessment measures based on information retrieval statistics ［J］. Journal of the American Chemical Society， 2005， 127（6）： 1665-1674.

[25] 蔣禮青，張明新，鄭金龍，等.快速搜索與發(fā)現(xiàn)密度峰值聚類算法的優(yōu)化研究［J］.計(jì)算機(jī)應(yīng)用研究，2016，33（11）：3251-3254.（JIANG L Q， ZHANG M X， ZHENG J L， et al. Optimization of clustering by fast search and find of density peaks ［J］. Application Research of Computers， 2016， 33（11）： 3251- 3254.）

[26] 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.

Clustering algorithm based on local gravity and distance

DU Jie， MA Yan*， HUANG Hui

（College of Information，Mechanical and Electrical Engineering，Shanghai Normal University，Shanghai201418，China）

The Density Peak Clustering （DPC） algorithm cannot accurately select the cluster centers for the datasets with various density and complex shape. The Clustering by Local Gravitation （LGC） algorithm has many parameters which need manual adjustment. To address these issues， a new Clustering algorithm based on Local Gravity and Distance （LGDC） was proposed. Firstly， the local gravity model was used to calculate the ConcEntration （CE） of data points， and the distance between each point and the point with higher CE value was determined according to CE. Then， the data points with high CE and high distance were selected as cluster centers. Finally， the remaining data points were allocated based on the idea that the CE of internal points of the cluster was much higher than that of the boundary points. At the same time， the balancedknearest neighbor was used to adjust the parameters automatically. Experimental results show that， LGDC achieves better clustering effect on four synthetic datasets. Compared with algorithms such as DPC and LGC， LGDC has the index of Adjustable Rand Index （ARI） improved by 0.144 7 on average on the real datasets such as Wine， SCADI and Soybean.

density peak clustering; gravity clustering; local gravity model; concentration; distance

TP181

A

1001-9081（2022）05-1472-08

10.11772/j.issn.1001-9081.2021030515

2021?04?06；

2021?07?09；

2021?07?14。

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

杜潔（1996—），女，浙江湖州人，碩士研究生，主要研究方向：模式識(shí)別、圖像處理； 馬燕（1970—），女，浙江海寧人，教授，博士，CCF會(huì)員，主要研究方向：模式識(shí)別、圖像處理； 黃慧（1981—），女，山東日照人，副教授，博士，主要研究方向：模式識(shí)別、醫(yī)學(xué)圖像處理。

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

DU Jie， born in 1996， M. S. candidate. Her research interests include pattern recognition， image processing.

MA Yan， born in 1970， Ph. D.， professor. Her research interests include pattern recognition， image processing.

HUANG Hui， born in 1981， Ph. D.， associate professor. Her research interests include pattern recognition， medical image processing.