资源描述：
《K_means聚类算法的研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第40卷第3期太原理工大学学报Vol.40No.32009年5月JOURNALOFTAIYUANUNIVERSITYOFTECHNOLOGYMay20093文章编号:100729432(2009)0320236204K2means聚类算法的研究韩晓红,胡彧(太原理工大学计算机与软件学院,山西太原030024)摘要:为解决原始K2means算法随机选取初始聚类中心对聚类结果的影响较大的不足,提出了改进算法。采取基于采样选取聚类中心距离的规则,进行多次选择决定最终的初始聚类中心,使得改进后的算法受初始聚类中心选择的影响达到最小;同时,在选取初始聚类中心后,对初值进行数据标准化处
2、理。将改进的K2means算法应用于销售行业,结果显示,改进后的算法比原始的算法在效率上得到了提高。关键词:数据挖掘;K2means算法;初始聚类中心;聚类分析中图分类号:TP30116文献标识码:A数据挖掘可以从大量有关数据中挖掘出隐含用一组不同的随机初始中心,然后选取具有最小的、先前未知的、对企业决策有潜在价值的知识和规SSE的簇集。该策略虽然简单,但是效果可能不好,则。作为数据挖掘技术中的一种重要的方法,K2这要依赖于数据集和寻找的簇的个数,在这种情况means聚类分析算法应用非常广泛,比如用于大量下,算法可能只能得到局部最优。也有文献采用这销售数据的划分。K2mea
3、ns算法对于大量数据集,样的方法:取一个样本,并使用层次聚类技术对它聚算法的可伸缩性好,时间复杂性为O(tkn)(其中,t类,从层次聚类中提取k个簇,并用这些簇的质心作是算法的迭代的次数,k是类的个数,n是数据集中为初始质心。该方法通常很有效,但仅对样本相对的数据点数,一般k≤n,t≤n)。但是,笔者在应用较少,且k相对于样本大小较小的情况,具有很大的中发现,该算法存在诸多不足。比如,在应用该算法局限性。因此,笔者提出了对数据集进行l次取样,时,需要用户随机选取初始聚类中心,并给出类的个然后再对取样的数据集采用K2means算法进行聚数,而这个信息通常是聚类之后才知道的;其
4、次是该类。将改进后的K2means算法应用于销售行业,结算法无法处理有分类属性(categoricalattribute)的果表明,改进算法较原算法在准确率上有较大提高,数据,且对孤立点敏感,不能发现非球形的类,或大并具有较好的稳定性。小差别很大的类;其三是经常陷入局部最优解,而无法得到全局最优解。而选择适当的初始质心是该算1聚类分析算法法运行过程的关键步骤,当质心随机初始化时,算法1.1K2means聚类算法思想及基本步骤的不同运行将产生不同的总的误差的平方和SSEK2means算法是一种聚类分析算法,该算法把(sumofthesquarederror)。SSE是作为度量
5、聚类n个样本点分为k个簇,各簇内的样本点具有较高质量的目标函数,更小的SSE意味着聚类的原型是的相似性,而各簇间的样本点相似程度较低,相似度簇中点的更好代表,随机的选取初始质心可能会出的计算是依据一个簇中样本点的平均值来进行的。现所有的初始质心都在一个自然簇中,却仍然找到算法的处理过程如下:了最小SSE聚类,而尽管初始质心的分布看上去较好,但是却得到了一个次最优聚类,具有较高的平方1)在样本数据集D中选择k个样本点,将k个-误差。样本点值分别赋给初始聚类中心mi(i=1,⋯,k);针对这个问题,笔者在研究中发现,处理选取初2)对样本点D中的所有pj(j=1,⋯,n),依次-
6、始中心问题一种最常用的技术是多次运行。每次使计算到各簇中心mi的距离3收稿日期:2008206218作者简介:韩晓红(1980-),女,山西永济市人,硕士生,主要从事计算机数据挖掘研究,(E2mail)jmghxh@163.com通讯联系人:胡彧,女,教授,(Tel)0351-6018249第3期韩晓红等:K2means聚类算法的研究237d(i,j)=
7、p-2输出:k个初始聚类中心。j-mi
8、;-1)定义一个初值为空存储l×k个聚类中心的3)找出pj关于mi的最小距离min(d(i,j)),-集合G=φ.将pj归入到和mi距离最小的簇中;2)进行l次取样,对每次样品采用原
9、始的K24)重新计算各簇的聚类中心means算法,随机选取初始聚类中心的方法进行聚ni-1类mi=pJi=1,⋯,k;,产生l×k个聚类中心,把这l×k个聚类中心放n∑iiJ=1i入G中。处理流程如图1所示。5)按式(1)计算数据集D中的所有点的平方误差E(t),并与前一次误差E(t-1)比较;6)若E(t)-E(t-1)<0转2),否则算法结束。1.2改进的K2means算法1.2.1初始聚类中心选择的改进在K2means原始的算法中,初始聚类中心的选择是随机的,不同的选取就会获得不同的聚类结果。所以,这个初始聚
