杜潔，馬燕，黃慧

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

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

杜潔，馬燕*，黃慧

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

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

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

0 引言

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

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

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

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

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

1 相關(guān)工作

1.1 經(jīng)典DPC算法

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

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

1.2 局部引力模型

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

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

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

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

2.1 確定聚類中心

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

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

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

對于具有最高集中度的點，則定義為：

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

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

圖2 決策圖和對應的聚類中心位置Fig. 2 Decision graph and corresponding cluster center locations

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

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

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

其中：Pk表示聚類中心點Ci的第k個近鄰點；表示聚類中心Ci與第k個鄰點Pk之間的距離。

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

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

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

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

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

2.3 算法的主要步驟描述

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

算法1 LGDC。

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

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

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

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

步驟5 選擇Nc個擁有最大值的點作為聚類中心，并對Nc個聚類中心按CE值從大到小排序。

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

步驟8 對各聚類中心以Ri為半徑進行掃描，標記掃描到的點。

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

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

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

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

2.4 參數(shù)的確定

2.4.1k近鄰的確定

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

2.4.2 參數(shù)α的確定

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

2.5 算法復雜度分析

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

3 實驗與結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表3中，評價指標結(jié)果保留小數(shù)點后四位，加粗值表示較好的實驗結(jié)果。由表3可知，在ARI評價指標值上，LGDC都要優(yōu)于其他對比算法，平均提升了0.144 7，最高提升了0.346 3；在FM指標上，LGDC除了在Waveform和Statlog數(shù)據(jù)集上效果差一些，在其他數(shù)據(jù)集上都達到了最優(yōu)。雖然LGC算法聚類效果較好，但是需要設置三個參數(shù)，而且實驗結(jié)果對于參數(shù)取值過于敏感，需要不斷調(diào)參達到最優(yōu)聚類效果。綜合三種指標來看，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ù)據(jù)集上的結(jié)果對比Tab. 3 Result comparison of six clustering algorithms on real datasets

4 結(jié)語

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

[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] 郭佳，韓李濤，孫憲龍，等.自動確定聚類中心的比較密度峰值聚類算法［J］.計算機應用，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ù)點的密度引力聚類新算法［J］.計算機科學與探索，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] 吳斌，盧紅麗，江惠君.自適應密度峰值聚類算法［J］.計算機應用，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] 魏康園，何慶，徐欽帥.基于改進引力搜索算法的K-means聚類［J］.計算機應用研究，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] 孫偉鵬.基于密度峰值聚類算法的研究與實現(xiàn)［D］.無錫：江南大學，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］.計算機應用研究，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。

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

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

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.