K均值聚类算法的研究与优化

陶 莹，杨 锋，刘 洋，戴 兵

(广西大学 计算机与电子信息学院，广西 南宁 530004)

0 引 言

数据挖掘在实际应用中的主要任务之一是聚类分析，其是数据挖掘中一个很热门的研究领域，同时与其他学科的研究方向有很大的交叉性[1]。聚类分析可以发现数据隐含的结构，对数据进行自动归类，从而得到数据的大致分布，在诸多领域为决策提供支持信息[2]。

K均值聚类算法是聚类分析方法中一种基本的划分式方法[3]。由于该算法简便易懂，且计算速度较快，通常被作为大样本聚类分析的首选算法[4]。

但是一般的K均值聚类算法初始聚类中心的选择是随机的，这样会导致聚类结果的不稳定。而且算法中k的值需要人为提前设定，k值设定的合理与否会直接影响聚类的效果[5]。此外，噪声和离群点也会对聚类效果产生影响，使得聚类中心偏离主要数据区域[6]。因此，文中针对K均值聚类算法的随机性较强的特点进行改进。

1 K均值聚类算法

1.1 算法基本思想

首先在整个数据集中任意选择k个数据作为初始聚类中心，然后计算其他数据对象与k个聚类中心的距离，将数据对象划分到距离最近的聚类中心所在的聚类域。所有数据划分好后，重新计算k个聚类中每个聚类的全部数据对象的平均值，该平均值所在的数据点成为新的聚类中心。最后进行多次迭代，直到连续两次的聚类中心相同，说明此时数据对象类别划分完毕，即得到k个聚类[7]。

1.2 算法评价准则—误差平方和

评价聚类效果，可以定义一个数据对象和其所在聚类域的目标函数。……