最小化误差平方和k-means初始聚类中心优化方法

周本金，陶以政，纪 斌，谢永辉

中国工程物理研究院 计算机应用研究所，四川 绵阳 621900

1 引言

聚类是依照某种相似度度量标准，将数据集划分成多个簇的过程，其目的是最大化簇内相似度，最小化簇间相似度。目前聚类已经广泛应用于多个领域，包括商务智能、模式识别、异常检测、信息检索[1]等领域。聚类也可以作为其他算法的预处理步骤。

k-means作为聚类算法中的一种，自MacQueen于1967年提出以来，因为其实现简单、时间开销低并且适合于并行计算[2]，目前已经得到了广泛应用。传统的k-means算法是一种启发式的贪心算法，常常得到的是一个局部最优解，聚类效果很大程度取决于初始中心点的选择。鉴于上述不足，很多学者对其提出了优化方法。以PAM算法为代表的k-medoids聚类算法以及其改进算法[3]，尽管算法能够取得比较良好的聚类效果，但是时间开销过大，不适合大规模数据聚类。最近几年新兴的模拟退火算法[4]和遗传算法[5]，其目的是获取全局最优解，不过在实践中这些方法没有被广泛接受。本文主要针对k-means对初始聚类中心敏感进行优化。目前优化方法大体分为两种，一种是基于距离的，另一种是基于密度的方法。基于距离的方法主要优点是时间开销较小，不过无法反映数据点的分布信息，容易选取到孤立点。常见的有最大最小距离法[6]，该方法选取距离已有聚类中心距离之和最大的数据点作为下一个聚类中心，但是该方法对孤立点过于敏感。基于密度的方法通常能够比较准确地反应数据的分布情况，不过计算开销较大。……