一种优化初始聚类中心的k-means算法

张明微, 吴海涛

(上海师范大学 信息与机电工程学院,上海 200234)



一种优化初始聚类中心的k-means算法

张明微, 吴海涛

(上海师范大学 信息与机电工程学院,上海 200234)

随机选择初始聚类中心的k-means算法易使聚类陷入局部最优解、聚类结果不稳定且受孤立点影响大等问题.针对这些问题,提出了一种优化初始聚类中心的方法及孤立点排除法.该算法首先选择距离最远的两点加入初始化中心,再根据这两点将原始簇分成两个聚簇,在这两个簇中挑选方差较大的簇按照一定的规则进行分裂直至找到k个中心,初始中心的选择过程中用到孤立点排除法.在UCI数据集及人造含一定比例的噪音数据集下,通过实验比较了改进算法与其他算法的优劣.实验表明,改进后的算法不仅受孤立点的影响小、稳定性好而且准确度也高.

初始聚类中心; 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-means算法描述如图1所示.

图1 k-means算法

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]及方差最大的簇可分裂成两个方差相对较小的簇,提出了初始化中心改进算法.除此之外,还提出了孤立点排除的方法.本算法的思想是首先找出样本点中距离最远的两个点为初始中心点,然后将其他样本点划分到距离最近的中心点所属的簇中,根据生成的簇内点的个数判定其对应的初始聚类中心是否为孤立点,最后根据簇内方差挑选下一个需要进行分裂的对象并按一定规则更新初始聚类中心,一直循环上面步骤直至聚类中心个数满足要求.

2.1 初始聚类中心选取算法

设数据集X={x1,x2,x3,…xn},共有n个对象.d(xi,xj)(i,j∈{1,2…n})表示数据点xi,xj之间的欧氏距离,ci(i∈{1,2…k})为聚类中心,W为待分裂的数据对象,S为聚类中心个数.

初始聚类中心选取算法如图2所示.

图2 初始聚类中心选取算法

2.2 改进后的k-means算法

数据集X={x1,x2,x3,…xn},共有n个对象.Cold,iCold,i表示上一轮的第i个簇中心,Cnew,i表示本次计算得到的新的第i个簇中心.

算法描述如图3所示.

图3 改进后的k-means算法

3 实验与分析

3.1 实验描述

实验中选取的数据集来自UCI数据库中的Iris、Balance-Scale、Wine以及人为添加噪音后的Iris数据集.实验环境为:Inter(R)Core(TM)i3-2330M,4G内存,250G硬盘,win7操作系统.

为了验证算法的稳定性、有效性,在Iris、Balance-Scale、Wine数据集下分别与原始k-means算法、文献[3]、文献[4]进行了分析比较,其中传统k-means算法的聚类结果是执行10次的平均值.为了进一步验证本算法在处理孤立点问题时的优越性,在人为添加噪音后的Iris数据集上将本算法与其他算法做比较.各算法聚类结果的评价采用了聚类误差平方和、聚类时间、聚类准确率等评价方法.

3.2 实验结果与分析

3.2.1 UCI数据集的聚类结果与分析

表1、表2、表3分别是在UCI数据集下的本算法与文献[3]、文献[4]及k-means算法在准确率、聚类误差及时间上的比较结果.

表1 各算法在UCI数据集的准确率比较

表2 各算法在UCI数据集的聚类误差比较

表3 各算法在人造数据集的聚类时间比较

由表1中各算法在UCI数据集上的准确率比较可见,由于传统k-means算法是随机选择初始聚类中心且其对聚类结果影响较大,所以运行10次的后的结果值具有不稳定性从而导致平均准确率比较低,本算法在UCI数据集上的准确率明显优于文献[3-4]的结果.由表2可知本算法的聚类误差明显优于传统k-means算法且不差于文献[3-4]中的算法.表3中关于各算法聚类时间的比较表明,传统k-means聚类算法的运行时间最快,本算法速度略低于文献[3-4]的结果.

3.2.2 人造数据集的聚类结果与分析

聚类的数据可能会存在孤立点.由于随机选取初始聚类中心可能会将孤立点选为初始聚类中心,这样会使聚类结果产生很大的偏差.通过在人造噪音数据集下做了算法之间的对比试验并验证了本算法的稳定性及有效性.

表4 各算法在人造数据集的准确率比较

表5 各算法在人造数据集的聚类误差比较

表6 各算法在人造数据集的聚类时间比较

由于本算法在处理孤立点问题时是将孤立点直接从样本集中删除,所以在处理含有噪音的Iris数据集时准确率及聚类误差与不含噪音时相比基本不变.由表4、5可知本算法比其他三种算法能够更好处理孤立点问题.由表6可见本算法在时间上高于k-means算法、文献[3-4],但是差距不是很明显.

4 结 语

针对传统k-means 算法初始聚类中心随机选取带来的聚类结果不稳定,以及孤立点对聚类结果影响的问题,本文作者根据“距离大的样本点分到同一簇的可能性小及方差最大的簇可分裂成两个方差相对较小的簇”这一事实,提出了一种优化初始聚类中心的k-means 聚类算法.在UCI数据集以及带有同比例噪音的人工数据集下的仿真实验表明,本算法与传统k-means 算法以及其他两种优化初始中心算法相比,在准确率及聚类误差上有所提高.但是本算法初始化中心算法有点繁杂,在选取中心问题上耗时过多.在今后的工作中,将进一步完善,试使其在各方面都优于其他算法.

[1] Zhou A W,Yu Y F.The research about clustering algorithm of K-Means [J].Computer Technology and Development,2011,21(2):62-65.

[2] Lei X F,Xie K Q,Lin F,et al.An effidient clustering algorithm based on local optimality of K-Means [J].Journal of Software,2008,19(7):1683-1692.

[3] Duan G Q.Auto generation cloud optimization based on genetic algorithm [J].Computer and Digital Engineering,2015,43(3):379-382.

[4] Zhai D H,Yu J,Gao F,et al.k-means text clustering algorithm based oninitial cluster centers selection according to maximum distance [J].Application Research of Computers,2014,31(3):379-382.

[5] Xie J Y,Wang Y E.k-means Algorithm based on minimum deviation initialized clustering centers [J].Computer Engineering,2014,40(8):205-211.

[6] Liu J X,Zhu G H,Xi M.A k-means Algorithm based on the radius [J].Journal of Guilin University of Electronic Technology,2013,33(2):134-138.

[7] Habibpour R,Khalipour K.A new hybrid k-means and K-nearest-neighbor algorithms for text document clustering [J].International Journal of Academic Reserch Part A,2014,6(3):79-84.

[8] Wang C L,Zhang J X.Improved k-means algorithm based on latent Dirichlet allocation for text clustering [J].Journal of Computer Applications,2014,34(1):249-254.

[9] Ren J T,Sun J H.An effidient clustering algorithm based on local optimality of K-Means [J].Journal of Computer Applications,2006,26:73-75.

[10] Zhang W M,Wu J,Yuan X J.k-means text clustering algorithm based on density and nearestneighbor [J].Journal of Computer Applications,2010,30(7):1932-1935.

[11] Zhu M.Data mining [M].Hefei:University of Science and Technology of China Press,2002.

(责任编辑：包震宇,冯珍珍)

A k-means algorithm to optimize the initial cluster centers

ZHANG Mingwei, WU Haitao

(College of Information,Mechanical and Electrical Engineering,Shanghai Normal University,Shanghai 200234,China)

k-means algorithm,when its initial center is dependent on to be chosen randomly,can incur the local optimum of the clustering and the instability of the clustering results which may be affected much by isolated points.Aiming at solving those problems,a kind of k-means algorithm to be able to optimize initial cluster center and eliminate isolated points are put forward.Firstly,the farthest two points are chosen to join the cluster set.Then according to those two points,the original cluster is divided into two clusters.Find one of the clusters which has the largest variance and then split it according to certain rules until k centers are found.Isolated points elimination is also put forward in the process of choosing the initial center.The proposed k-means algorithm is tested on UCI data sets and on synthetic data sets with some proportional noises．The experimental results show that the proposed novel k-means algorithm can not only achieve a very promising and stable clustering,but also obtain a small influence of isolated points.

initialization center; k-means algorithm; isolated points elimination; clustering; UCI database

2015-09-14

吴海涛,中国上海市徐汇区桂林路100号,上海师范大学信息与机电工程学院,邮编:200234,E-mail:ht.wu@163.com

TP 301

A

1000-5137(2016)05-0599-05

10.3969/J.ISSN.1000-5137.2016.05.014