资源描述：
《一种改进的k—means聚类算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第16卷第1期电脑与信息技术Vol.16No.12008年2月ComputerandInformationTechnologyFeb.2008文章编号:1005-1228(2008)01-0038-03一种改进的K-means聚类算法连凤娜,吴锦林,唐琦(厦门大学信息科学与技术学院,福建厦门361005)摘要:K-means算法是最常用的聚类算法之一,有很多的优点,但也存在着不足。它不仅对样本的输入顺序敏感,可能产生局部最优解,而且受孤立点的影响很大。文章正是针对这些不足,提出了一种改进的K-mea
2、ns算法,主要从数据预处理、初始聚类中心的选择方面进行了改进,并做了改进前后算法的对比实验。结果表明,改进后的算法不但更具稳定性,准确度也高,受孤立点的影响也大大降低。关键词:K-means算法;聚类;孤立点中图分类号:TP311.13文献标识码:AAnImprovedAlgorithmofK-meansLIANFeng-na,WUJin-lin,TANGQi(CollegeofInformationScienceandTechnology,XiamenUniversity,Xiamen,Fujia
3、n361005,China)Abstract:K-meansalgorithmisoneofthemostwidespreadmethodsinclustering,includingbothstrongpointsandalsoshortages.Notonlyisitsensitivetotheorderofsampledata,butalsoitmaymakeoutthelocalexcellentandbeaffectedbytheoutliers.Giventheseshortages,a
4、nimprovedalgorithmisdiscussed,whichmakesimprovementsindatapreprocessingandselectionoforiginalclusteringcenter.Checkexperimentwasdone,whichindicatestheimprovedoneismorestable,moreaccurateandtheaffectionbytheoutliersisdowntoamuchlowfigure.Keywords:k-mean
5、s;clustering;outliers0引言1.1K-means的基本思想给定类的个数k,随机挑选k个对象为初始聚类聚类就是根据最大化类内的相似性、最小化类间中心,利用距离最近的原则,将其余数据集对象分到k的相似性原则对数据对象进行分组的一个过程。其结个类中去,聚类的结果由k个聚类中心来表达。算法采果就是一个个由数据对象组成的簇,每个簇内的对象用迭代更新的方法,通过判定给定的聚类目标函数,每之间具有很高的相似性,而簇间的对象则很不相似。聚一次迭代过程都向目标函数值减少的方向进行。在每[1]类的应
6、用越来越广泛,在经济学、生物学、气象学、医一轮中,依据k个参照点将其周围的点分别组成k个药学、信息工程和工程技术等许多领域都有着十分重类,而每个类的几何中心将被作为下一轮迭代的参照要的作用。因此,对聚类的要求也越来越高,提出准确点,迭代使得选取的参照点越来越接近真实的类几何且又高效的聚类算法刻不容缓。中心,使得类内对象的相似性最大,类间对象的相似性人们已经提出了很多聚类算法,比如有基于划分最小。[2]的K-MEANS算法、CLARANS算法;基于层次的K-means的伪代码描述如下:[3]BIRCH
7、算法、CURE算法;基于密度的DBSCAN算法、//输入:类的个数k,样本数n:OPTICS算法等。但是这些算法都存在着不足,比如随机选取k个对象,初始化k个聚类中心;DBSCAN算法,它的密度是一个核心对象的ε领域内设置迭代计数器t=0;数据对象的个数,所以就存在如何选择密度参数的问While(r≠0)题,不适当的选择将会大大影响算法的结果。本文主要把样本点分到距离最近的聚类中心所代表的是针对K-means算法的不足提出了改进算法。簇内;1相关工作计算聚类目标函数J(t);r=J(t)-J(t-1
8、);收稿日期:2007-09-30;作者简介:连凤娜(1983-),女,硕士研究生,研究方向:数据挖掘;吴锦林(1946-),男,教授,主要研究方向:网络与数据库应用;唐琦(1984-),女,硕士研究生,研究方向:系统结构。第16卷第1期连凤娜,等:一种改进的K-means聚类算法·39·重新计算各个聚类中心;取1,首先筛掉与其它样本的距离和最大的点a,然后t=t+1;从剩下的数据集{b,c,d,e,f,g,h,i,j,k}中选出距离最输出聚类中心。远的两个点i和d,
