基于局部引力和距离的聚类算法

杜洁，马燕，黄慧

（上海师范大学 信息与机电工程学院，上海 201418）（∗通信作者电子邮箱ma‑yan@shnu.edu.cn）

基于局部引力和距离的聚类算法

杜洁，马燕*，黄慧

（上海师范大学 信息与机电工程学院，上海 201418）（∗通信作者电子邮箱ma‑yan@shnu.edu.cn）

密度峰值聚类（DPC）算法对于密度多样、形状复杂的数据集不能准确选择聚类中心，同时基于局部引力的聚类（LGC）算法参数较多且需要手动调参。针对这些问题，提出了一种基于局部引力和距离的聚类算法（LGDC）。首先，利用局部引力模型计算数据点的集中度（CE），根据集中度确定每个数据点与高集中度的点之间的距离；然后，选取具有高集中度值和高距离值的数据点作为聚类中心；最后，基于簇的内部点集中度远高于边界点的集中度的思想，分配其余数据点，并且利用平衡k近邻实现参数的自动调整。实验结果表明，LGDC在4个合成数据集上取得了更好的聚类效果；且在Wine、SCADI、Soybean等真实数据集上，LGDC的调整兰德系数（ARI）指标相较DPC、LGC等算法平均提高了0.144 7。

密度峰值聚类；引力聚类；局部引力模型；集中度；距离

0 引言

聚类的主要目的是对一组对象进行分类，使得同一类的对象尽可能相似，不同类之间的对象尽量不相似［1］。聚类算法可以应用于图像分割［2］、社区发现［3］等领域。聚类算法一般可以分为：基于划分的方法［4］、基于密度的方法［5］、基于层次的方法［6］、基于图论的方法［7］和基于网格的方法［8］。K-means［9］是一种经典的划分聚类算法，该算法只适用于球状簇，且聚类结果易受初始聚类中心的影响。基于密度的噪声应用空间聚类（Density-Based Spatial Clustering of Application with Noise， DBSCAN）算法［10］，可以找到任意形状的簇，但其聚类结果易受阈值和邻域半径这两个参数的影响。

2014年，Rodriguez等［11］提出了密度峰值聚类（Density Peak Clustering， DPC）算法，该算法认为聚类中心的密度高于其周围数据点的密度，且与其他高密度的点距离较远。但是该算法仅根据数据点之间的距离计算密度，不适用于形状、密度复杂的数据集；在基于距离分配数据点时，算法鲁棒性差，而且聚类结果对于截止距离的取值较敏感。

在基于引力的聚类算法方面，温晓芳等［12］提出了一种密度引力聚类新算法，虽然该算法引入了引力的概念，但仍旧是在基于密度的基础上进行聚类，无法避免DPC存在的问题。Wang等［13］提出了一种基于局部引力的聚类（Clustering by Local Gravitation， LGC）算法，它根据局部引力模型推导出局部中心度量，以区分内部点和边界点。但这种方法需要确定多个参数，且对参数取值异常敏感。在此基础上，Wang等［13］又提出了社团聚类（Clustering by Community with Local Agents，CLA）算法，将参数减少到一个，但聚类效果有所下降。

针对DPC存在的问题，Liu等［14］基于共享最近邻计算数据点之间的局部密度和相对距离，可以对复杂密度的数据集有效聚类；吴斌等［15］提出了一种基于基尼系数自适应调整截止距离的算法，避免了聚类结果对截止距离敏感的问题；Jiang等［16］则在DPC的基础上引入了万有引力，用引力来类比距离，降低了数据集形状对聚类结果的影响。

为了解决DPC和LGC算法存在的问题，本文提出了一种基于局部引力和距离的聚类算法（Clustering algorithm based on Local Gravity and Distance， LGDC）。该算法通过局部引力模型计算数据点的集中度，从而确定聚类中心。相较基于密度选取聚类中心的方法，局部引力模型可以避免簇的密度和形状对聚类结果的影响，并且通过k平衡近邻对参数自动调整。同时，本文设计了一种基于集中度的数据点分配方法，使得算法鲁棒性更强。实验结果表明，本文所提LGDC优于DPC和LGC等算法。

1 相关工作

1.1 经典DPC算法

密度峰值聚类算法选取密度比其邻域高，且与高密度点之间距离较大的点作为聚类中心。对数据集中的每一个点Xi，需要计算其密度和距离。

其中：dij是点Xi和点Xj之间的距离；dc是根据经验选取的截止距离，一般是对所有数据点之间的距离按降序排列，再将前1%～2%位置所对应的距离值看作dc值。距离表示点Xi与比它密度高的点之间的最小距离，计算如式（2）所示：

1.2 局部引力模型

受到牛顿万有引力定律的启发，在聚类过程中，数据点之间的局部引力可以反映数据点与其邻域点之间的关系。根据万有引力定律［17］，两个质点之间的引力可以定义为：

数据点Xi的k个近邻点对它产生的局部合力（Local Resultant Force， LRF）可以表示为：

其中：k表示点Xi的近邻点数目。由式（5）可得，Xi质量越大，对于邻域的影响也越大；同样地，质量越小，就越容易受到近邻点的影响。因此，对于LRF可以进行如式（6）的简化：

2 基于局部引力和距离的聚类算法

2.1 确定聚类中心

对于每个数据点Xi，需要计算两个量：该点的集中度CEi和它与高集中度的点之间的距离。本文利用LRF中包含的信息，计算点Xi的集中度CEi，定义如下：

图1 数据点位置与CE的关系Fig. 1 Relationship between data point location and CE

此外，聚类中心还存在集中度高且相互之间距离较大的特点。令δi表示点Xi与集中度更高的所有数据点之间的距离的最小值，计算式如下：

对于具有最高集中度的点，则定义为：

如果一个数据点具有较大的集中度CE和距离，即具有较大的值，那么该点很有可能是聚类中心，定义如下：

如图2所示，该数据集的簇间密度变化较大，白色空心点表示聚类中心。如图2（a）、（b）所示，DPC无法准确选取聚类中心；如图2（c）、（d）所示，本文利用CE和可以准确找到聚类中心。

图2 决策图和对应的聚类中心位置Fig. 2 Decision graph and corresponding cluster center locations

2.2 数据点分配方法

DPC算法的数据点分配策略采用一步分配归类，容错性和鲁棒性较差。因此，本文设计了一种新的数据点分配方法。

假设经过2.1节确定Nc个聚类中心，对聚类中心按集中度CE降序排序，表示为C1，C2，…，CN。对每个聚类中心，确定一个扫描半径，表示为R1，R2，…，RN，即Ci的扫描半径为Ri。Ri定义如下：

其中：Pk表示聚类中心点Ci的第k个近邻点；表示聚类中心Ci与第k个邻点Pk之间的距离。

对拥有Nc个聚类中心的数据集，需要进行Nc轮扫描。一般地，每一轮中包含多次扫描，首次均以Ci为圆心、Ri为半径开始。对扫描范围内的点进行标记，被标记的点会被作为下一次扫描的圆心，循环直至满足终止条件，进入到下一轮扫描。

终止条件设置如下：由2.1节可知，簇的内部数据点的集中度远大于边界点，即内部点的CE值大于边界点的CE值。所以，当某次扫描范围内数据点的CE总和远小于该轮次中以聚类中心进行首次扫描时的CE总和时，当前扫描范围内的数据点将不再被标记。扫描范围内数据点的CE总和计算如式（13）所示：

式（13）表示对于以Pi为圆心、Ri为半径的圆，对圆内的每个点Pj的集中度CEj进行求和。记每一轮中对聚类中心Ci首次扫描时的集中度总和为。当小于时（这里，α为阈值，2.4.2节讨论α的确定方法），当前扫描满足终止条件，不再对数据点进行标记。经大量实验可得，α取0.5时效果较好。

如图3所示，是一个包含2个簇的二维数据集，假设该数据集近邻数k为12。数据点分配具体过程以图3为例：1）图3（a）中灰色数据点为聚类中心C1，以R1为半径进行扫描，扫描到的数据点被标记为白色；2）如图3（b）所示，白色数据点被作为扫描的圆心，扫描到的数据点同样被标记；3）如图3（c）所示，当前扫描满足终止条件，停止扫描；4）如图3（d）所示，结束左边簇的扫描后，对右边簇进行以R2为半径的第二轮扫描。由图3（d）可以看到，仍有数据点未被分配到任何一个簇，将这些点按照距离分配给离其最近的簇中。

图3 数据点分配过程示意图Fig. 3 Schematic diagram of data point allocation process

2.3 算法的主要步骤描述

LGDC的具体实现步骤如算法1所示。

算法1 LGDC。

输入 数据集D，聚类簇数Nc；

输出 聚类结果C。

步骤1 根据式（6）计算数据集D中各个点的局部合力。

步骤2 根据式（8）计算每个点的集中度CE，并按CE值对所有点降序排序。

步骤5 选择Nc个拥有最大值的点作为聚类中心，并对Nc个聚类中心按CE值从大到小排序。

步骤6 对每个聚类中心点，根据式（12）确定扫描半径Ri。

步骤8 对各聚类中心以Ri为半径进行扫描，标记扫描到的点。

步骤9 对标记的点继续以Ri为半径进行扫描，并根据式（13）计算。

步骤10 若不满足终止条件，标记扫描到的点，重复步骤9；否则，若还有未扫描的聚类中心点，转到步骤6，若中心点均已扫描，转到步骤11。

步骤11 将未分类的点按照距离分配给离其最近的簇中。

步骤12 返回聚类结果C。

2.4 参数的确定

2.4.1k近邻的确定

首先根据数据集的样本量初步确定近邻数k，通常初始k值可以设置为样本量的0.5%～1.5%。为了进一步提高聚类效果，在计算LRF时采用平衡k近邻［13］代替k近邻。对每个数据点，需要计算从第k个到第2k个邻点产生的所有LRF，然后选择LRF取得最小值时对应的近邻数的取值，并用其替换掉初始的k值，定义如下：

2.4.2 参数α的确定

聚类中心确定之后，其余数据点的分配从高集中度的簇开始，即按照降序进行扫描。值与扫描范围内数据点的CE值有关，而CE则与数据点的位置分布和距离有关，因此本文α的取值与扫描半径相关联。经过多次实验，对α取值定义如下：假设有Nc个簇，按照簇的初始集中度从高到低排序为C1，C2，…，CN，则对应的扫描半径为R1，R2，…，RN，α的值为：

2.5 算法复杂度分析

LGDC的时间复杂度包括三部分：1）对每个数据点，利用K-D（K-Dimension）树确定k近邻［18］，所需时间为，n表示数据集的样本量。2）确定聚类中心需要计算两个指标CE和。CE是在LRF的基础上计算的，因此计算LRF和CE所需时间为，其中k表示每个点的近邻数，计算的时间复杂度为。3）在数据点分配阶段，假设簇的数量为Nc，那么算法的时间复杂度为，其中，，。因此，LGDC的整体时间复杂度为。

3 实验与结果分析

选用人工数据集［19-21］和UCI（University of California Irvine）［22］真实数据集进行实验，数据集的详细信息如表1所示，并将本文算法与K-means［9］、DPC［11］、GDPC［16］、LGC［13］、CLA［13］算法进行比较。其中DPC和GDPC算法需要确定值，根据原文献的建议，实验中均设置为2%。LGC和CLA的参数取值需要根据聚类效果调整到最优；本文算法需要根据数据集样本量确定初始k值，之后算法会根据2.4.1节自动调整k的大小。各算法在数据集上的参数取值具体如表2所示。

实验开发环境为Matlab 2016a，硬件条件为：Intel Core i5-6500 CPU，主频3.20 GHz，内存8.00 GB。

3.1 人工数据集的实验结果分析

本文采用4个人工数据集DS1～DS4验证聚类效果，图4～7为各算法分别对DS1～DS4的聚类结果。

表1 数据集信息Tab. 1 Information of datasets

图4为DS1上六种算法得到的聚类结果。GDPC、CLA、LGC和LGDC都可以准确确定聚类个数且聚类效果都很好，K-means和DPC不能对形状复杂的数据集DS1正确划分簇类。

图5为DS2上六种算法得到的聚类结果。六种算法都对DS2做了较好的聚类，其中GDPC、CLA和LGDC的结果更为准确，其余三种算法没有很好地划分边界点。

图6为DS3上六种算法得到的聚类结果。LGC和LGDC的聚类效果都很好。K-means、DPC、GDPC和CLA算法都不能很好地对长条状数据簇进行划分，长条状数据簇被分为多个类。

图7为DS4上六种算法得到的聚类结果。K-means、CLA和LGDC可以在密度变化大的数据集上准确聚类。DPC、GDPC和LGC无法找到正确的聚类中心导致聚类效果较差。

实验结果表明，LGDC在密度、形状复杂的二维数据集上都可以获得较好的聚类效果。

表2 不同算法在不同数据集上的参数取值Tab. 2 Parameter settings of different algorithms on different datasets

3.2 UCI数据集的实验结果分析

为了进一步验证LGDC的性能，采用了三种常用的内部聚类验证指标，包括：兰德系数（Rand Index， RI）［23］、调整兰德系数（Adjustable Rand Index， ARI）［23］和F指标（F Measure， FM）［24］来评估聚类算法的效果。

图4 六种算法在DS1上的聚类结果Fig. 4 Clustering results of six algorithms on DS1

在已知数据集标签的基础上，可以得到真正例（True Positive，TP）、假正例（False Positive，FP）、假负例（False Negative，FN）、真负例（True Negative，TN）［25］，根据这4个数据可以计算RI、ARI和FM，具体计算式分别如式（16）、（17）和（18）所示：

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

RI的取值范围为［0，1］，0代表聚类效果非常差；ARI的取值范围为，该指标能够去掉随机标签对于RI评估结果的影响；FM的取值范围为［0，1］。这三种评价指标的值越大，代表聚类效果越好。

表3中，评价指标结果保留小数点后四位，加粗值表示较好的实验结果。由表3可知，在ARI评价指标值上，LGDC都要优于其他对比算法，平均提升了0.144 7，最高提升了0.346 3；在FM指标上，LGDC除了在Waveform和Statlog数据集上效果差一些，在其他数据集上都达到了最优。虽然LGC算法聚类效果较好，但是需要设置三个参数，而且实验结果对于参数取值过于敏感，需要不断调参达到最优聚类效果。综合三种指标来看，LGDC优于K-means、DPC、GDPC、LGC和CLA算法。

图5 六种算法在DS2上的聚类结果Fig. 5 Clustering results of six algorithms on DS2

图6 六种算法在DS3上的聚类结果Fig. 6 Clustering results of six algorithms on DS3

图7 六种算法在DS4上的聚类结果Fig. 7 Clustering results of six algorithms on DS4

表3 六种聚类算法在真实数据集上的结果对比Tab. 3 Result comparison of six clustering algorithms on real datasets

4 结语

针对DPC和LGC聚类算法的效果易受数据集分布和参数影响的问题，本文提出了一种基于局部引力和距离的聚类算法。该算法基于局部引力模型，考虑数据点的集中度和距离，而不是原始DPC算法中根据密度峰值决定聚类中心，这能够有效避免密度变化给聚类结果带来的影响；另外，根据数据点的集中度，设计了一种新的数据点分配方法，这种分配方式能够适用于形状复杂的数据集。本文进行了多次实验，在4个合成数据集和6个真实数据集上，将K-means、DPC、GDPC、LGC、CLA和LGDC进行实验对比，实验结果表明LGDC在多个数据集上的聚类效果都优于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] 温晓芳，杨志翀，陈梅.数据点的密度引力聚类新算法［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] 孙伟鹏.基于密度峰值聚类算法的研究与实现［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] 蒋礼青，张明新，郑金龙，等.快速搜索与发现密度峰值聚类算法的优化研究［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—），女，山东日照人，副教授，博士，主要研究方向：模式识别、医学图像处理。

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.