逼近法确定球形簇的球心与半径

韩 海

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

聚类在现实中有非常广泛的应用。聚类的结果是将多个对象划分成若干组，同组的对象具有相同或相近的性质。进一步地，聚类的目的之一是建立分类标准，并认为符合某个标准的对象应属于相应的类，通常会具有对应的性质。

设一个数据对象W包含n个分量，记作W=(w1，w2，…，wn)，一个对象就是 n 维空间的一个点。若X和Y是n维空间中的两个点，则X和Y之间的欧氏距离为

聚类是将由多个数据对象构成的集合划分成若干个互不相交的子集，使得每个子集内的元素“联系”紧密，而处于两个不同子集内的元素“联系”松散。划分出的每一个子集称为一个“簇”，而“联系”通常被理解为两个元素之间的欧氏距离。文献［1-3］使用这种方式表示“联系”，并在此基础上进行聚类。聚类得到的结果往往不易直接建立分类标准，因而通常都把结果近似地认为是球形簇，以下主要讨论如何确定每个球形簇的范围。

不妨设T是对集合S经过聚类后得到的一个球形簇，其中包含k个数据元素，即包含n维空间的k个点，并且大致均匀分布成球状。确定T的几何范围就是需要确定一个n维球（球心记作点P，半径记作r，由P和r确定的球记作球B），使得T中的所有元素均在球内，并且球的半径尽可能小。虽然从数学上精确地确定P和r非常困难，但可以从一个初始状态出发，通过逐步优化，最终得到一个满足精度要求的n维球。

1 确定初始参数

初始半径r取值为P到T中元素的最大距离。显然，这样的球包含了T的所有元素。对于球心移动的距离L，初始时可以取一个比较大的值，比如，从而使得球心能够比较快地向目标位置移动。另外，设精度要求为θ，即最终得到的球心位置及半径与准确值相差均不超过θ或者θ的若干倍。

2 逐步优化

逐步优化的过程是每次把球心移动L的距离，重新计算半径，并限制半径只能减小。如果已经不能进行这样的移动，则将移动距离参数L减半，然后重复上述移动。当L经过若干次减半后将会小于，此时的球心位置及半径即为最终结果。

2.1 确定球心的移动位置

对于当前的球心P，找出T中所有满足“到P的距离与r的差值小于L”的元素，即：对于元素 T(i)(i=1，2，…，k)，如果 T(i)满足则认为“T(i)在球面上”。由确定r的方式可知，满足该条件的点一定存在，于是可以对这些点求均值，得到点Q。

如果d(P，Q)＜L，则球心移动距离已经小于L，于是将L减半，重新找出满足（2）式的点并计算均值Q。反之，如果d(P，Q)≥L，则在PQ连线上取一点 P′，使得 d(P，P′)=L。

2.2 重新确定半径

对于2.1中得到的点 P′和T中所有元素T(i)(i=1，2，…，k)，计算 d(T(i)， P′)，并取最大值，记作 r′。如果 r′≤r，则将球心移动到 P′，并以 r′作为新的半径，即令P和r分别取值为P′和r′，然后按新的球心和半径重复上述方法处理。反之，如果r′＞r，则将球心移动到 P′是不合适的，此时将L减半，然后重复上述方法处理。

2.3 算法流程图

算法流程如图1所示。

图1 算法流程图

3 算法有效性

对于由k个点构成的簇T，显然，包裹T中所有点的最小n维球是唯一存在的，记作B0=(P0，r0)，球心在点 P0，半径为r0。记算法终止时以P和r为参数的球为B，以P为球心、r-θ为半径的球为B′。当T中元素大致均匀分布且r＞＞θ时，上述算法得到的P点相对P0点的偏差不超过2θ，r与r0的偏差不超过θ，即

图2中灰色环外层表示以P为球心、r为半径的球B，由算法中确定r的方式可知T中至少存在一点T(x)，使得d(P，T(x))=r。灰色环内层表示以P为球心、r-θ为半径的球B′，如果T中的点在灰色区域内则在算法中认为“该点在球面上”。灰色环的“厚度”为θ，虚线表示以P0为球心、以r0为半径的理论上的最小球B0。显然，T中所有元素必在球B内（含球面上），也必在球B0内（含球面上）。

由于r0是理论上包裹T的最小球的半径，显然有 r≥r0。

假设r＞r0+θ，不难看出图2所示3种位置关系都将导致矛盾：对于图2（a），算法决定了灰色环内必有元素，这与“所有元素必在球B0内”相矛盾；对于图2（b）和图2（c），由于算法中认定为“在球面上”的点只能出现在虚线球内的灰色区域，并且分布大致均匀，因而图2的两种位置关系应使得算法继续执行，这与“算法已终止”相矛盾。由此可知≤θ。

图2 r＞r0+θ时3个球的位置关系

假设 d(P，P0)＞2θ，由于 | |r-r0≤θ，3个球只可能出现如图3所示的位置关系。 A为球B′和球 B0交线上一点，d(P0，A)=r0，d(P，A)=r-θ。在r＞＞θ且数据大致均匀分布时，算法应继续执行，对球心P作一次合适的移动，这与算法已终止相矛盾。因此，假设 d(P，P0)＞2θ不成立。

图3 d(P，P0)＞2θ时的位置关系

4 结论

对包括IRIS鸢尾花数据在内的多组数据测试结果表明，上述算法都能稳定运行并产生理想的结果。在n=2时，该算法还可用于求覆盖多边形的最小圆［4］。笔者也对非均匀分布的簇（即非球形簇）进行了测试，算法能够得到有效输出，只是元素集中在球内某些位置。从多组数据的聚类结果可以看出，形成非球形簇的情况是更普遍现象，因此，尽管可以用本算法求得一个簇的最小球形范围，但用“如果一个元素在该范围内则属于相应的簇”对元素进行归类则不太合适。

［1］王德青，朱建平，谢邦昌.主成分聚类分析有效性的思考［J］.统计研究，2012，29（11）：84-87.

［2］Bai T，Kulikowski C A，Gong L G，et al.A Global K-modes algorithm for clustering categorical data［J］.Chinese Journal of Electronics，2012，21（3）：460-465.

［3］邱保志，王波.分类数据的聚类边界检测技术［J］.计算机应用，2012，32（6）：1654-1657.

［4］戴海鹏，唐厚君.求凸多边形直径的改进算法［J］.计算机工程与应用，2011，47（3）：44-46.