韩 海

（江汉大学 人工智能学院，湖北 武汉 430056）

人工智能在20 世纪90 年代进入了低谷期，新世纪以来，随着计算能力的提高和算法研究的深入，人工智能重新成为科学研究的热门领域。聚类是一种无监督的机器学习方法，是人工智能的基础之一，在统计、图像处理、自然语言理解、经营决策等方面都有广泛应用。聚类是把样本划分成若干个互不相交的子集，每一个子集称为一个“簇”（cluster），使得同一簇内的个体相似度尽可能高，而不同簇内的个体相似度尽可能低。

1 确定簇数的聚类

从实际问题中采集信息，经预处理、规范化之后得到m维空间的测量样本X。设X中共有n个个体，记作每个个体包含m个属性，是一个m维向量，记作对于其中任意两个个体之间的距离表示两者的相似度，通常用欧氏距离表示：

记P是对X进行一次聚类的结果，P把X划分成k个簇，定义每个簇的中心、簇内距离di如下（该定义目前被广泛采用［1−3］）：

式中，Ni表示第i个簇的容量，x表示第i个簇中的各个个体，1 ≤i≤k。

目前常用的聚类算法有基于均值的K−means 算法、基于密度的DBSCAN 算法等，这些算法在其适用场合都能够对样本进行划分。如K−means 算法就是在预先确定簇数的前提下搜索最佳划分。对于给定的整数k，K−means 算法试图把X聚类成k个簇，使得以下目标函数F(P)的值最小：

文献［2−3］主要是在搜索的覆盖面上进行改进，调整了选择初始簇心的策略，使得算法能够更好地搜索解空间。对于给定的整数k，K−means 算法及K−means++算法给出的结果往往已接近甚至就是最优解。……