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

韩 海

（江汉大学 数学与计算机科学学院，湖北 武汉 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中元素的最大距离。……