李丰兵

摘  要：K均值算法是以随机的方式选择初始聚类中心，这使得K均值算法容易陷入局部最优，收敛性能不稳定。针对这一缺陷，该文对K均值算法进行改进，提出一种逐步选择距离差异极大的个体作为初始聚类中心的算法。实验结果表明，改进后的算法收敛性能确实比K均值算法优越。

关键词：K均值算法  聚类中心  局部最优  收敛性

中图分类号：TP311.13   文献标识码：A             文章编号：1672-3791（2019）05（c）-0185-03

Abstract： K-means algorithm chooses initial clustering centers randomly， which makes K-means algorithm easy to fall into local optimum and its convergence performance unstable. In order to overcome this shortcoming， an improved K-means algorithm has been proposed in this paper， which chooses gradually individuals with great distance difference as the initial clustering center. The experimental results show that the improved algorithm has better convergence performance than K-means algorithm.

Key Words： K-means algorithm; Clustering center; Local optimum; Convergence

K均值算法是21世紀十大机器学习算法之一，是1967年由麦奎因（MacQueen）提出并命名的一种简单、高效的快速聚类算法，广泛地应用于数据挖掘、模式识别及计算机视觉等领域[1-3]。目前，K均值算法仍然是人工智能及机器学习领域的一个研究热点，国内外已存在诸多与K均值算法密切相关的研究工作，其中，有部分研究工作集中在K均值算法的改进问题上[4-8]。众所周知，K均值算法存在两个主要的缺陷，其中一个缺陷就是以随机的方式选择初始聚类中心，而不同的初始聚类中心可能会导致不同的聚类结果，即K均值算法容易陷入局部最优，聚类效果依赖于初始聚类中心的选择，这种情况如图1所示。

在图1中，左上图和左下图分别表示两种不同的初始聚类中心的选择，这里所用的数据集是相同的，划分类别数均为3，右上图和右下图则分别表示对应的聚类结果。显然，由图1可直观地看出，选择不同初始聚类中心导致K均值算法聚类结果不同。因此，K均值算法是一种局部收敛算法，稳定性及精确性都有待于进一步提高和完善。……