基于万有引力的簇间距离表示法

韩海

（江汉大学数学与计算机科学学院，湖北武汉430056）

基于万有引力的簇间距离表示法

韩海

（江汉大学数学与计算机科学学院，湖北武汉430056）

分析了几种现有聚类算法中簇间距离表示法的优缺点，并在此基础上提出了一种基于万有引力模型的簇间距离计算方法。该方法模仿物理学中力的合成原理，是对把各质点间引力数值直接相加的重要改进。理论分析及数据计算的结果都表明，该方法比引力直接相加有更广的适应性。

聚类；簇间距离；引力；积分

0 引言

随着大数据时代的到来，聚类越来越受到人们的重视，也在越来越多的领域发挥作用。实际应用表明，运用聚类方法对已有的统计数据进行分析，相应地采取不同的措施，可以使得工作有针对性，从而提高工作效率。

聚类是重要的数据分析方法。针对大量的数据样本，聚类就是根据样本之间的联系紧密程度对它们进行分组，使得同一组内的样本联系紧密而不同组的样本之间联系松散。聚类得到的每一个分组称为一个簇。聚类的目的在于确定分组的标准，并分析各个簇的特点，从而对新的数据估计它可能属于哪一个簇，相应地制定有针对性的处理方案。

聚类总是需要在若干种分组结果中选取人们认为最优的分组方案。为了能对各种分组方案进行比较，通常都需要建立一个聚类有效性函数。在常用的聚类处理方法中，绝大多数都综合考虑两项指标，即用于表示分组内部联系紧密程度的指标和用于表示不同分组之间的联系紧密程度的指标，两个指标分别称为“簇内距离”和“簇间距离”。

目前，大家对于描述簇内距离的指标相对比较认可，但是对簇间距离的表示仍然存在较大争议，也因此提出了各种各样的簇间距离计算方法。关于簇间距离的简单处理方法是计算簇外样本到本簇中心点的距离，比如计算两个簇中样本的最小距离、最大距离，或者计算簇的中心到簇外样本的最小距离等，这类方法由于计算比较简单因而被较多地采用。在文献［1-3］提出的有效性计算函数中，簇间距离的计算都采用了这类方法。这类方法要求簇中样本应围绕簇中心点成球状分布，且离球心越近样本越多，离球心越远样本越少，即高斯分布，但这个要求往往与样本的实际分布有一定差距。文献［4-5］提出了类似于万有引力的“凝聚力”计算式，并以此作为簇内距离及簇间距离的评价指标，该方法明显地考虑了簇中样本分布对簇内距离及簇间距离的影响，但从力学角度来看，不同方向的力不能简单地以数值相加。本文正是在万有引力或者说“凝聚力”的基础上，加进了关于引力方向的考虑，从而确定一种新的簇间距离计算方案。

1 定义簇间距离

图1是一个二维数据样本分布示例，每个“○”代表一个数据样本。一般会考虑把这个样本集合分成3个簇，即左上、右上和下半部分各一个簇。但是，按图1中的虚线把样本数据划分成4部分之后，可以看出位于左上角的簇与位于左下角的样本都是由31个数据构成，把左上的簇旋转90°后与左下方的样本结构相同。正是这个旋转，导致了上方的62个数据被分成两个簇，而下方同样是62个数据却分在一个簇内。这一现象显然应该通过簇间距离的不同来说明。本文下面提出的方法能较好地描述这个旋转导致的簇间距离差异。

图1 样本数据Fig.1Sample data

根据万有引力定律，两个质点P1和P2之间的引力大小相等、方向相反，并且力的方向在同一条直线上，其引力数值F（P1，P2）的计算公式为

数学上已经证明，如图2所示的两个匀质球体间的万有引力也符合上述公式。其中m1、m2是两个质点（或者匀质球体）的质量，r=d(P1，P2)是两个质点（或者两个匀质球体的中心）之间的距离，G为万有引力常量。但是，对于非匀质球形物体，其引力的计算就需要用到多重积分。如果两个物体初始时处于静止状态，在不考虑其他外力的情况下，两个物体之间的万有引力将造成两个物体相向运动，并可能存在某种角度的旋转。尽管聚类问题中的簇并不是自然界中的物体，但可以借用以积分方式求万有引力的思想来描述两个簇之间的联系紧密程度，从而能更好地描述簇内样本分布不均匀情况下的簇间距离。

图2 万有引力模型Fig.2Model of gravitation

设X、Y是两个簇，X={x1，x2，…，xn}，Y={y1，y2，…，ym}，以xˉ表示X的中心，yˉ表示Y的中心，

定义X、Y的簇间距离d(X，Y)为

其中F(xi，yj)是样本数据xi和yj按（1）式计算得到的引力值，其中的引力常量G取1，θij是通过xi和yj的直线与通过xˉ和yˉ的直线所形成的夹角，如图3所示。

图3 质点间引力的效果Fig.3Effect of gravitation between particles

按照如上方式定义两个簇之间的距离，实际上是把X和Y视作两个非匀质物体，借用积分思想求引力的合力，准确地说是求万有引力造成两物体相向运动的引力分量，并用该分量的数值作为X和Y的簇间距离。从力的合成的角度考虑，两物体间的万有引力是其中所有质点对(xi，yj)之间的引力的合力，其造成物体相向运动的引力分量是这些质点对之间的引力在xˉ和yˉ连线上的投影之和，而F(xi，yj)cosθij正是求质点对(xi，yj)之间的引力在物体中心点连线上的投影。记和分别是xi和yj在与连线（或者其延长线）上的投影，则

其中d(xi，yj)和是两点间的欧氏距离。

2不同簇间距离计算方法的对比

将图1中的样本沿居中的“+”划分成4个簇，上方的两个簇记作A和B，左下方的簇记作C，右下方的簇记作D。为了更好地说明计算方法上的差异，添加图4中的样本数据作为对比。记图4上方的簇为E，下方的簇为F。可以看到，每个簇均包含31个数据，A与B的中心点之间距离为7，C与D的中心点之间距离也为7，E与F的中心点之间距离接近于5。设水平相邻和垂直相邻的两个“○”之间的距离均为1，表1是不同的簇间距离表示法针对d（A，B）、d（C，D）及d（E，F）的计算结果。

图4 非球形簇样本数据Fig.4Nonspherical cluster sample data

表1 不同簇间距离计算方法对比Tab.1Comparison of different methods for calculating distance of clusters

前4种簇间距离表示方法都以数值越小表示簇间联系越紧密，后两种表示法则相反。后3种方法均能将簇的内部结构反映在簇间距离上，并且都认为C、D的簇间距离最小。第四种方法和本文所述的方法均认为E、F的簇间距离最大，而第五种方法认为A、B的簇间距离最大。第四种方法虽然能够体现簇的内部结构，但数据计算结果的敏感度较差，比如A、B的簇间距离与C、D的簇间距离差别明显，但该方法的计算结果差别不大。可以看到，本文提出的以合成引力表示簇间距离可以较好地表现簇的内部结构对簇间距离的影响。

3 结语

聚类问题最终是要研究对类似于图1的样本进行分组的最优解。一个有趣的现象是，稍稍调整样本的分布，答案就可能不同。在此，仅以本文所述簇间距离之和作为聚类标准。在本文依据引力模型提出的距离定义之下，簇间距离表现为簇间的引力，数值越大则簇间分离度越差。据此对图1的样本进行聚类处理，则应该分成3个簇，如图5（b）所示，其中圆的半径是簇中样本到簇中心点的平均距离。如果加大图1样本数据的上下间隔，把中间的3个空行加为5行，则此时应分为两个簇，见图5（a）；反之如果将空行缩减为1行，则应分为4个簇，见图5（c）。当然，不同的聚类标准将导致不同的结果。可见，聚类问题的解与方法及样本分布都有关。

图5 聚类效果Fig.5Result of clustering

综上所述，本文的方法更符合自然界中的物理学有关规律，对簇间距离的描述也不依赖于高斯分布或者球形分布，因而具有更广泛的适用性。

（References）

［1］张大庆，徐再花.一种新的模糊聚类有效性指标［J］.沈阳农业大学学报，2012，43（5）：636-639.

［2］李双虎，张风海.一个新的聚类有效性分析指标［J］.计算机工程与设计，2007，28（8）：1772-1774.

［3］季铎，王智超，蔡东风，等.基于高斯分布的簇间距离计算方法［J］.中文信息学报，2008，22（3）：50-55.

［4］刘启亮，邓敏，彭东亮，等.基于力学思想的空间聚类有效性评价［J］.武汉大学学报：信息科学版，2011，36（8）：982-986，990.

［5］于勇前，赵相国，陈衡岳，等.基于引力概念的聚类质量评估算法［J］.东北大学学报：自然科学版，2007，28（8）：1109-1112.

（责任编辑：曾婷）

Description of Distance Between Clusters Based on Gravitation

HAN Hai
（School of Mathematics and Computer Science，Jianghan University，Wuhan 430056，Hubei，China）

Analyses the advantages and disadvantages of several existing methods for description of distance between clusters，based on it，presents a calculation method for distance between clusters based on gravitation model.This method is an important improvement for direct addition of gravita⁃tion value between each particle，which simulates the synthetic principle of force in physics.Theoreti⁃cal analysis and computing results show the presented method is more applicable than direct addition of gravitation.

clustering；distance between clusters；gravitation；integral

TP301.6

：A

：1673-0143（2014）05-0036-04

2014-08-13

韩海（1968—），男，副教授，研究方向：图形图像处理及模式识别。