自动确定聚类中心的势能聚类算法*

于晓飞，葛洪伟,2+

1.江南大学 物联网工程学院，江苏 无锡 214122

2.江南大学 轻工过程先进控制教育部重点实验室，江苏 无锡 214122

1 引言

聚类算法是数据挖掘中的重要分支，是在没有关于潜在数据分布的先验知识情况下，通过某种相似性度量和聚类准则对数据进行聚集。聚类分析在许多领域有着重要的作用，包括生物学、人工智能、客户关系管理、信息检索、机器学习等[1-3]。

然而，现在有许多应用广泛的聚类算法无法自动确定聚类数目。如基于划分的K-means[4-5]，该算法需人工设定聚类数目而且对初始类簇中心有很大的依赖；基于层次的聚类方法如CURE（clustering using representatives）[6-7]、Chameleon[8]等，这些算法可以发现任意形状的簇，但均不能在无输入参数的条件下自动确定聚类数目；基于密度的聚类方法如DBSCAN（density-based spatial clustering of applications with noise）[9]、OPTICS（ordering points to identify the clustering structure）[10]等，这些算法虽有较好的聚类效果，但也不能自动确定聚类数目，在具体实践中影响了算法的应用效果。

目前，有许多学者针对自动确定聚类数目的问题进行了研究。如Rodriguze等人[11]于2014年提出的密度峰算法（density peaks clustering，DPC），该算法虽然无需提前设置聚类数目，但要通过决策图来人工选取聚类中心。针对这一缺陷，李涛等人[12]对密度峰算法进行了改进，改进后的算法虽然可以自动确定聚类数目，但在聚类中心点判断时，对参数dc（截断距离）的依赖很大。显然，如何使相关算法能在没有参数依赖的前提下自动确定聚类数目是颇具现实意义的研究课题。

Lu等人[13]提出一种基于势能的聚类算法（clustering by sorting potential values，CSPV），该算法虽提出了基于势能的相似性度量准则，但聚类效果完全依赖于对参数B的选取。针对这一问题，Lu等人于2013年[14]提出了一种基于势能的快速凝聚层次聚类方法（potential-based hierarchical agglomerative clustering，PHA）。该算法首先依据各点的势能和与父节点的距离构造边缘加权树，最后通过人为设定的聚类数目使用层次聚类算法得到最终的聚类结果。PHA算法使用基于势能的相似性度量准则，在时间上更快速，在过程上更便捷，在精度上可以得到更好的聚类效果。

然而PHA算法需要提前设定聚类数目，而且在确定数据点类别的机制上，使用了层次聚类方法，仅考虑距离的作用，忽视了势能的影响。针对上述问题，本文提出了一种自动确定聚类中心的势能聚类算法（automatically clustering based on potential metric，ACP）。首先，通过计算各数据点的势能和其到父节点距离的乘积，并通过区分聚类中心点和非聚类中心点，实现自动确定聚类数目的目的；其次，综合考虑势能和距离两个因素对非聚类中心点进行分类。在人工数据集和真实数据集上的实验证明，与PHA算法相比，本文ACP算法不仅可以自动准确地确定聚类数目，而且具有更优的聚类效果。

2 PHA算法及其缺陷分析

PHA算法[14]认为，数据点的势能大小与其概率密度分布是密切相关的。该算法首先根据重力势能的物理意义来计算每个数据点的势能。每两点之间的势能Φij定义如下：

其中，rij是点i与点j之间的欧式距离；δ用来避免分母为0的情况出现。δ计算方式为：

其中，MinDi是点i到其他各点的最短距离；S是一个尺度因子[14]，一般设为10；mean为求均值的函数；N是数据点的个数。计算了每两点之间的势能Φij后，每个点的势能Φi定义为：

文献[14]使用Parzen窗口函数[15]这一非参数估计方法来证明势能和概率密度分布的关系。在Parzen窗口函数中概率密度的定义如下：

文献[14]经过证明得到：

即势能和概率密度函数成反比。因此，势能可以反映数据点的分布情况，如势能越小的点的周围数据点分布越密集。

将势能从小到大排序，并以势能最小的点作为根节点，构造边缘加权树，其他数据点寻找自身的父节点。其中，父节点定义为：

即势能小于点i且与i距离最近的点为其父节点。点i到父节点parent[i]的距离ρi为：

对于势能最小的点i，其ρi=max(ri,j|j≠i)。在边缘加权树中，每个数据点与父节点之间的权值为两者的距离。在树构造完成后，使用凝聚层次聚类算法进行聚类，得到聚类结果。

PHA算法虽然十分便捷快速，但由于需要提前设定聚类数目，而且在使用层次聚类方法来确定数据点的类别时，没有考虑势能的影响。因为人们关于数据集的先验知识的了解是有限的，人为确定聚类数目往往有较大的困难，所以如何使该算法能自动确定聚类数目且采用更好的分配机制是值得研究的课题。

3 自动确定聚类中心的势能聚类算法

3.1 聚类中心的自动确定

基于对重力势能物理意义的分析发现，势能在分布上表现出类似年轮的特点，即数据点的势能随着层数的增大而增大。中心数据点的势能最小，最外层数据点的势能最大。如图1所示。

Fig.1 Graph of potential field图1 势能分布图示例

A、B、C、D、E这5个点的势能最小，而且在每个单独的类簇中，沿着中心点向外，数据点所处层数越高势能越大。并且A、B、C、D、E这5个点作为类中心，相互之间的距离相对较大。

Fig.2 Analysis of determining cluster center by potential图2 势能确定聚类中心的分析

然而，仅以数据点的势能大小为依据不能确定聚类中心。以图2（a）所示的数据集为例，该数据集的势能分布如图2（b）所示。由图可见，各点势能大小的差异不足以直接区分聚类中心点与非聚类中心点。而且，有些数据点虽然势能很小，但与其他势能更小或势能相等的数据点的距离较小，因此在数据分布图上不是聚类中心点，而是距离聚类中心较近的数据点。可见，单独以势能的影响为依据无法直接确定聚类中心。

仅以与父节点的距离为依据同样无法确定聚类中心。如图3（a）所示，该图表示各点的ρ值分布。若以此来区分聚类中心点和非聚类中心点，直观来看，会得到A、B、C、D共4个聚类中心，但该数据集仅有A、B两个聚类中心，因此会导致错误的聚类结果。这是由于有些数据点与父节点的距离很大，但其势能也很大，在数据点分布图上其周围数据点的密度较小，则不能作为聚类中心点。可见，单独考虑距离的影响也无法准确地确定聚类中心。

Fig.3 Graph of distance andγidistribution图3 距离与γi值的分布图

通过上述分析得出结论，聚类中心点应具备两个特点：（1）相对较小的势能Φi；（2）较大的与父节点的距离ρi。基于以上发现，在确定聚类中心的过程中应同时考虑势能和与父节点的距离两个因素。

定义1γi是评价数据点为聚类中心可能性的指标：

由于势能Φi恒为负数，势能越小，其绝对值越大。故取势能的绝对值与距离的乘积作为评判聚类中心可能性的尺度。数据点的γi值越大，是聚类中心点的可能性越大。

图3（b）为图2（a）中数据集的各点γi值分布图，图中横坐标代表每个数据点的γi值，为了使数据点在图上处于中间位置方便观察，设置纵坐标为0。从图3（b）可以看出，聚类中心点与非聚类中心点的γi值具有明显差异：非聚类中心点的数目较多且其γi值集中分布在一个区间内，而聚类中心点的数目较少，且彼此分布得相对比较分散；另外，聚类中心的γi值也明显大于非聚类中心的γi值。

基于上述发现与分析，可以根据γi值的分布图明显地将聚类中心点和非聚类中心点区别开来，直接确定聚类中心：即根据γi值，使用简单高效的分类或聚类方法区分聚类中心点和非聚类中心点两类，如回归分析离群点检测、K-means算法或其他更好的方法。在此过程中，将数据点较少的那一类作为聚类中心点，如图3（b）中的A、B。至此ACP算法在没有人为设定聚类数目的条件下能够自动确定聚类中心。

聚类中心确定后，应根据算法的分配机制对剩余数据点进行类别确定。PHA算法仅依据数据点相互之间的距离大小来确定其类别，这会导致某一类中的边缘数据点由于与其他类的边缘数据点距离更近而错误地分配到了其他类中。这种情况在类似DS2的数据集中表现显著。而本文ACP算法综合考虑距离和势能两个因素，对于剩余样本j，将其归入势能比j小且距离j最近的样本所在类簇，即依次分配到与自身父节点相同的类别中去，直到所有数据点的类别都确定为止。由于增加势能的限制，在数据点的类别分配上就会更加严格。如图1所示，势能越小说明周围数据点越密集，那么在此基础上，距离这种势能相对小的点越近则越能确认两者为相同类。ACP算法在该数据集上的聚类结果见4.2.1节中介绍。

综上所述，ACP算法不仅可以自动确定聚类中心，而且在分配机制上同时考虑了势能和距离两个因素，在一定程度上改进了PHA算法需人为设定聚类数目和分配机制上仅考虑距离的两个缺陷。

3.2 ACP算法步骤

ACP算法流程简单描述如下：

步骤1由式（1）到式（4）求出每个数据点的势能Φi，由式（7）找出每个数据点的父节点parent[i]，并由式（8）计算数据点到父节点的距离ρi。

步骤2根据式（9）计算各点的γi值。

步骤3根据步骤2中各点的γi值，在一维特征空间中，使用K-means算法对数据点进行分类，K值恒为2，并选取数据点少的一类作为聚类中心集。

步骤4确定聚类中心后，每个聚类中心各代表一类，标记为{1,2,…,C}，C表示数据集的类别总数。

步骤5将剩余数据点归入势能比其小且与其距离最近的样本所在类簇，即与自身的父节点划为一类，并标记相同的类标签，直到所有数据点的类别都确定为止。

3.3 算法复杂度分析

假设聚类对象有n个数据，本文ACP算法的时间复杂度主要是由计算势能和距离及对γi值分类时产生的。ACP算法在计算势能时的时间复杂度为O(n2)，计算距离时的时间复杂度为O(n)，在对γi值分类时的时间复杂度为O(n)，因此ACP算法的时间复杂度为O(n2)。文献[14]指出，PHA算法的时间复杂度主要是由构建边缘加权树以及通过树状图进行层次聚类所产生的。其中，构建边缘加权树时的时间复杂度为O(n2)，通过树状图层次聚类时的时间复杂度为O(n2)，因此PHA算法的时间复杂度为O(n2)[14]。可见，本文在没有提升算法复杂度的同时，不仅解决了PHA算法如何自动确定聚类数目的问题，而且完善了样本分配机制，提高了聚类效果。

4 实验分析

4.1 聚类结果评价

实验中使用Fowlkes-Mallows index（FMIndex）[16]、F1-measure[17]和 ARI（adjusted Rand index）[18]3 个聚类评价指标来对算法进行对比。其中FMIndex的定义如下：

假设给定两个不同的聚类结果R1和R2，TP表示在R1、R2中都为相同类的数据点个数；FP表示在R1中是相同类在R2中不是相同类的数据点个数；FN表示在R2中是相同类在R1中不是相同类的数据点个数。FM值介于0~1之间，越接近0聚类效果越差，越接近1聚类效果越好。F1-measure和ARI为两个常用的聚类评价指标，这里不再详细介绍。

4.2 实验结果与分析

为了验证ACP算法的性能，分别在人工数据集和UCI[19]数据集上进行实验。

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

表1中DS1由3组服从标准正态分布的随机数构成，各组的中心数据点分别为（0,0）、（3,5）和（6,0），每组有300个数据。DS2由4组服从正态分布且期望值均为0的随机数构成，第一组是200个数据点，标准差为2，中心在（0,0）；第二组是400个数据点，标准差为3，中心在（6,13）；第三组是800个数据点，标准差为4，中心在（12,0）；第四组是200个数据点，标准差为2，中心在（16,11）。DS3由两组服从二元正态分布的随机数构成，每组有500个数据点，且x的标准差均为1，y的标准差均为5，期望均为0，协方差均为0。第一组数据点中心是（0,0），第二组数据点中心为（5,0）。

Table 1 4 artificial data sets表1 4个人工数据集信息

基于欧氏距离测度，分别使用CSPV、PHA、ACP和DPC算法在表1中的人工数据集上进行实验，其中图4为ACP算法在各数据集上得到的γi值分布图，图上的A、B、C、D字母表示该算法在各数据集上得到的聚类中心。图5、图6、图7分别为ACP、PHA和CSPV算法得到的实验结果（由于DPC算法得到的实验结果图与PHA算法相似，在此不一一列出）。实验后4种算法得到的3种聚类评价指标值对比如表2~表4所示。

图4、图5表明，ACP算法在上述4个人工数据集上均可准确地确定聚类数目并得到理想的聚类结果。表2~表4表明，在DS2、DS3两个数据集上，ACP算法的FM聚类评价指标值均高于PHA算法，F1-measure、ARI两个聚类评价指标值与PHA算法相等；在DS1、Spiral两个数据集上，虽然两种算法的精确度相等，如Spiral数据集的精确值均达到了1，但ACP算法可以自动确定出正确的聚类数目并得到上述的聚类结果，而PHA算法需在人工设定正确的聚类数目前提下，才能够得到与ACP算法相等的聚类精确度。

Fig.4 Graph ofγidistribution on artificial data sets图4 人工数据集的γi值分布图

Fig.5 Clustering result on artificial data sets byACP图5ACP在人工数据集的聚类结果

Fig.6 Clustering result on artificial data sets by PHA图6 PHA在人工数据集的聚类结果

Fig.7 Clustering result on artificial data sets by CSPV图7 CSPV在人工数据集的聚类结果

Table 2 FM index values of 4 methods on artificial data sets表2 4种算法在人工数据集上的FM值

Table 3 F1-measure index values of 4 methodson artificial data sets表3 4种算法在人工数据集上的F1-measure值

Table 4 ARI index values of 4 methods on artificial data sets表4 4种算法在人工数据集上的ARI值

在DS2、Spiral两个数据集上，ACP算法的3个评价指标值均高于CSPV算法，其余两个数据集上二者相等。DPC算法在DS3、Spiral两个数据集上的评价指标值与ACP算法相等；在DS1、DS2两个数据集上的评价指标值虽然略高于ACP算法，但该算法需多次实验并选择最优的dc值才可得到理想的实验结果，而ACP算法不需任何输入参数，且对参数没有依赖，在任何情况下得到的实验结果都是相同的。

整体而言，ACP算法不仅可以自动确定聚类数目，而且更为有效的分配机制使得算法能够得到更优的聚类效果。

4.2.2 真实数据集的实验结果分析

为了进一步验证ACP算法性能，基于欧式距离，分别用CSPV、PHA、ACP和DPC算法对表5中来自UCI[19]的真实数据集进行实验，并用3个聚类评价指标FM、F1-measure、ARI对4种算法的聚类结果进行评价，实验结果如表6~表8所示。由于DPC算法对dc值有依赖，表6~表8所列的各评价指标值均取DPC算法多次实验的最优值。

Table 5 4 real data sets表5 4个真实数据集信息

Table 6 FM index values of 4 methods on real data sets表6 4种算法在真实数据集上的FM值

Table 7 F1-measure index values of 4 methods on real data sets表7 4种算法在真实数据集上的F1-measure值

Table 8 ARI index values of 4 methods on real data sets表8 4种算法在真实数据集上的ARI值

从表6~表8可以看出，在iris和letter数据集上，ACP算法的3个聚类评价指标值均高于PHA算法；在seeds数据集上，虽然两者的3个聚类评价指标值相等，但ACP算法能够自动确定3个类别，而PHA算法需人为设定聚类数目；而在vehicle数据集上，虽然PHA的F1-measure值高于ACP算法，但在FM和ARI两个评价指标上，ACP算法要高于PHA算法。

在iris数据集上，ACP算法的3个聚类评价指标值均高于CSPV算法，与DPC算法相等；在letter数据集上，3种算法取得的3个指标值相同；在seeds数据集上，ACP算法的FM值最大，F1-measure值略低于DPC算法但高于CSPV算法，ARI值略低于DPC算法；在vehicle数据集上，ACP算法的FM值最大，F1-measure值略低于CSPV算法，ARI值略低于CSPV算法但高于DPC算法。

上述结果表明，整体而言，在真实数据集上，当取得相似聚类结果时，ACP算法有效避免了PHA算法需要人工指定聚类数目的缺陷，也不存在CSPV、DPC两种算法对参数具有依赖性的问题；另外，ACP算法改善的样本分配机制使得其能够取得比PHA算法更优的聚类结果。

5 结束语

针对PHA算法不能自动确定聚类数目以及分配样本时仅考虑单一变量的两个缺陷，本文提出了一种自动确定聚类中心的势能聚类算法。与PHA算法相比，ACP算法在保留算法思想新颖及性能高效的同时，可以在没有任何参数依赖的前提下自动确定聚类数目，而且在人工数据集和真实数据集上能够取得更好的聚类效果。

然而，ACP算法采用欧式距离测度度量样本之间相似度，在一些维数相对较低的数据集中可以得到较好的效果。但欧式距离在度量高维数据对象之间的相似度时存在不足：随着数据维数的增加，它会导致数据点之间的最大距离与最小距离的差异不明显，即欧式距离测度在高维数据中会失效。因此，如何使ACP算法能够有效处理高维数据集，将是下一步的研究内容。

:

[1]von Luxburg U,Williamson R C,Guyon I.Clustering:science or art?[C]//Proceedings of the 2011 International Conference on Unsupervised and Transfer Learning Workshop,Bellevue,Jul 2,2011:65-80.

[2]Guang Junye,Liu Mingxia,Zhang Daoqiang.Spectral clustering algorithm based on effective distance[J].Journal of Frontiers of Computer Science and Technology,2014,8(11):1365-1372.

[3]Yang Jing,Gao Jiawei,Liang Jiye,et al.An improved DBSCAN clustering algorithm based on data field[J].Journal of Frontiers of Computer Science and Technology,2012,6(10):903-911.

[4]Jain A K.Data clustering:50 years beyondk-means[J].Pattern Recognition Letters,2010,31(8):651-666.

[5]Xu Rui,Wunsch D.Survey of clustering algorithms[J].IEEE Transactions on Neural Networks,2005,16(3):645-678.

[6]Guha S,Rastogi R,Shim K.CURE:an efficient clustering algorithm for large databases[C]//Proceeding of the 1998 ACM SIGMOD International Conference on Management of Data,Seattle,Jun 1-4,1998.NewYork:ACM,1998:73-84.

[7]Przybyla T,Pander T,Czabański R.Deep data fuzzy clustering[C]//Proceedings of the 7th Joint International Information Technology and Artificial Intelligence Conference,Chongqing,Dec 20-21,2014.Piscataway:IEEE,2014:130-134.

[8]Wilcox H,Nichol R C,Zhao Gongbo,et al.Simulation tests of galaxy cluster constraints on chameleon gravity[J].Monthly Notices of the royal astronomical society,2016,462(1):715-725.

[9]Kumar K M,Reddy A R M.A fast DBSCAN clustering algorithm by accelerating neighbor searching using groups method[J].Pattern Recognition,2016,28:39-48.

[10]Kalita H K,Bhattacharya D K,Kar A.A new algorithm for ordering of points to identify clustering structure based on perimeter of triangle:OPTICS(BOPT)[C]//Proceedings of the 18th International Conference on Advanced Computing and Communications,Guwahati,Dec 18-21,2007.Washington:IEEE Computer Society,2007:523-528.

[11]Rodriguez A,Laio A.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.

[12]Li Tao,Ge Hongwei,Su Shuzhi.Density peaks clustering by automatic determination of cluster centers[J].Journal of Frontiers of Computer Science and Technology,2016,10(11):1614-1622.

[13]Lu Yonggang,Wan Yi.Clustering by sorting potential values(CSPV):a novel potential-based clustering method[J].Pattern Recognition,2012,45(9):3512-3522.

[14]Lu Yonggang,Wan Yi.PHA:a fast potential-based hierarchical agglomerative clustering method[J].Pattern Recognition,2013,46(5):1227-1239.

[15]Parzen E.On estimation of a probability density function and mode[J].Annals of Mathematical Statistic,1962,33(3):1065-1076.

[16]Fowlkes E B,Mallows C L.A method for comparing two hierarchical clusterings[J].Journal of the American StatisticalAssociation,1983,78(383):553-569.

[17]Yang Yan,Jin Fan,Mohamed K.Survey of clustering validity evaluation[J].Application Research of Computers,2008,25(6):1630-1632.

[18]Nguyen X V,Epps J,Bailey J.Information theoretic measures for clusterings comparison:is a correction for chance necessary?[C]//Proceedings of the 26th Annual International Conference on Machine Learning,Montreal,Jun 14-18,2009.New York:ACM,2009:1073-1080.

[19]Lichman M.UCI machine learning repository[EB/OL].http://archive.ics.uci.edu/ml.Irvine:University of California,2013.

附中文参考文献：

[2]光俊叶,刘明霞,张道强.基于有效距离的谱聚类算法[J].计算机科学与探索,2014,8(11):1365-1372.

[3]杨静,高嘉伟,梁吉业.基于数据场的改进DBSCAN聚类算法[J].计算机科学与探索,2012,6(10):903-911.

[12]李涛,葛洪伟,苏树智.自动确定聚类中心的密度峰聚类[J].计算机科学与探索,2016,10(11):1614-1622.

[17]杨燕,靳蕃,Mohamed K.聚类有效性评价综述[J].计算机应用研究,2008,25(6):1630-1632.