一种优化初始聚类中心的k-means算法
张明微, 吴海涛
【摘 要】随机选择初始聚类中心的k-means算法易使聚类陷入局部最优解、聚类结果不稳定且受孤立点影响大等问题.针对这些问题,提出了一种优化初始聚类中心的方法及孤立点排除法.该算法首先选择距离最远的两点加入初始化中心,再根据这两点将原始簇分成两个聚簇,在这两个簇中挑选方差较大的簇按照一定的规则进行分裂直至找到k个中心,初始中心的选择过程中用到孤立点排除法.在UCI数据集及人造含一定比例的噪音数据集下,通过实验比较了改进算法与其他算法的优劣.实验表明,改进后的算法不仅受孤立点的影响小、稳定性好而且准确度也高.
【期刊名称】上海师范大学学报（自然科学版） 【年(卷),期】2016(045)005 【总页数】5
【关键词】初始聚类中心; k-means算法; 孤立点排除法; 聚簇; UCI数据集
0 引 言
聚类分析是数据挖掘研究的一项重要技术,它的诞生为从大量的数据中获取有价值的知识提供了一种有效的方法.它广泛地应用于文本搜索、模式识别人工智能、图像分析等领域[1].常用的聚类分析方法包括基于划分、基于层次、基于密度、基于网格和基于模型等算法[2].k-means是划分方法中一种应用较为广泛的算法,它有很多优点也存在许多不足.针对k-means算法的不足的研究分为两个分支:1) 初始聚类中心的个数k;2) 初始聚类中心的选择.本文作者针对后者进行了研究,提出了一种新的初始聚类中心算法.实验结果表明本算法在准确性与稳定性
方面比传统的聚类效果好,实验结果也更接近实际数据分布.
1 k-means算法介绍及研究现状
1.1 k-means算法介绍
设有样本X={x1,x2,x3,…xn},n为样本数.k-means算法的思想:首先从样本集x中随机选择k个数据对象作为初始聚类中心,其次根据每个数据对象与k个聚类中心的相似程度将其分配到最相似的簇中,然后重新计算每个新簇的平均值并将其作为下次迭代的聚类中心,不断重复该过程直到更新后的簇中心与更新前一致,也就是准则函数E收敛.目标是使类内对象相似性最大,类间对象相似性最小[3].数据之间的相似程度可以通过计算数据两两之间的距离来确定.常用的距离测度是欧氏距离.对于n维实数向量空间中两点的欧氏距离定义为: .
其中,xi和yi分别是x和y的第i个属性值.准则函数定义为: .
其中:k为簇的总数,为簇ci的中心. k-means算法描述如图1所示. 1.2 研究现状
针对k-means算法初始聚类中心点的选取问题,众多学者从不同角度进行了研究.段桂芹[4]采用基于均值与最大距离乘积的方法来优化初始聚类中心,该算法首先选择距离样本集均值最远的数据对象加入聚类中心集合,再依次将与样本集均值和当前聚类中心乘积最大的数据对象加入聚类中心集合,从而提高了准确率.翟东海等[5]基于距离最远的样本点最不可能分到同一个簇中的思想,提出了最大距离法选取初始簇中心的k-means文本聚类算法,同时,也重新构造了迭代中的
簇中心计算公式和测度函数.谢娟英等[6]根据样本空间分布紧密度信息,提出利用最小方差优化初始聚类中心的k-means算法,该算法选择方差最小且相距一定距离的样本作为初始聚类中心.刘家星等[7]提出一种基于半径的k-means+λ算法,在选择簇的初始中心点时,根据λ参数计算各点间距离比例,并以某个特定的距离为半径作圆,在圆内根据距离比例选择一个初始化中心点,该算法在错误率和运算时间上具有更高的性能.Habibpour,Khalipour[8]提出k-means和k-近邻混合算法并用于文本聚类,该算法与传统k-means算法相比有更好的效率和聚类有效性.王春龙[9]提出一种基于隐含狄利克雷分布主题概率模型的初始聚类中心选择算法,该算法选择蕴含在文本集中影响程度最大的前m个主题,并在这m个主题所在的维度上对文本集进行初步聚类,从而找到聚类中心.任江涛[10]提出了一种面向文本聚类的改进的K均算法,通过运用特征选择及降维、稀疏向量筛除,基于密度及散布的初始中心点搜索等方法进行改进,该算法在聚类精度、稳定性等方面都有提高.张文明[11]根据密度和最近邻思想提出了一种优化初始中心算法,得到了更好的应用于文本聚类的DN-k-means算法.
2 k-means算法改进
k-means算法对初始化中心非常敏感,随机选择的初始聚类中心很容易使聚类结果陷入局部最优及受孤立点影响大等问题.本算法基于距离大的样本点分到同一簇的可能性小[5]及方差最大的簇可分裂成两个方差相对较小的簇,提出了初始化中心改进算法.除此之外,还提出了孤立点排除的方法.本算法的思想是首先找出样本点中距离最远的两个点为初始中心点,然后将其他样本点划分到距离最近的中心点所属的簇中,根据生成的簇内点的个数判定其对应的初始聚类中心是否为孤立点,最后根据簇内方差挑选下一个需要进行分裂的对象并按一定规则更新初
一种优化初始聚类中心的k-means算法
