聚类中K means算法综述讲解.doc

攻读硕士学位研究生试卷(作业)封面学年度第一学期)(2015至2016论文选读题目聚类分析中K-means算法综述科目王苑茹姓名专业计算机技术82015入学年月年月简短评语成绩:授课教师签字:1聚类分析中K-means算法综述:摘要是一个将数据划分成聚类分析是数据挖掘中一个极其重要的研究方向,搜索,生物学以及图像簇的方法或手段。聚类分析可广泛利用在商务智能,Web聚类算法,总结了模式识别等众多方面。本文主要叙述聚类分析中的K-means算法的相关改进做了综述。K-means聚类算法的研究现状,并针对K-meansK-means关键词:聚类算法;数据子集;聚类中心;相似性度量和距离矩阵OverviewofK-meansalgorithminclusteringanalysisAbstract:,biology,marketwaysinbusinessintelligence,Webclassicaltherules,Atclusteringthesametime,spatialintroducepaper,wetheK-meansalgorithmisdescribe,AndsomerelatedimprovementstoK-:K-meansclusteringalgorithm;numberofclustersK;clusterinitialization;distancemetric2、引言1&Ball、、1957年Lloyed1965年年由K-means聚类算法是1955Steinhaus分别在他们各自研究的不同的科学领域独立提出的。空McQueenHall、1967年是从海量数据中发现知间聚类分析方法是空间数据挖掘理论中一个重要的领域,算法是空间聚类算法中应用非常广泛的算法,同时识的一个重要手段。k-means日益丰富的空间和非空间数据收集存储于空间它也在聚类分析中起着重要作用。复杂性都在快速海量的空间数据的大小、数据库中,随着空间数据的不断膨胀,从这些空间数据中发现邻域知识迫切需求产远远超出了人们的解译能力,增长,生一个多学科、多邻域综合交叉的新兴研究邻域,空间数据挖掘技术应运而生。年了,但是目前仍然是应用最为广泛的聚类算法被提出已经快虽然k-means60][1。容易实施、简单、高效、成功的应用案例和经验是其仍然划分聚类算法之一流行的主要原因。聚类算法的研本文主要叙述聚类分析中的K-means聚类算法,总结了K-means究现状,并针对算法的相关改进做了综述。K-means算法、经典K--means算法是数据挖掘领域最为常用的k-means聚类算法是一种基于形心的划分技术,它的目标是划分整个样本空间为若干聚类方法之一,最初起源于信号处理领域。因此,每个子空间中的样本点距离该空间中心点平均距离最小。个子空间,k-means是划分聚类的一种。k-means算法接受输入量k;然后将n个数据对象划分为k个聚类以便使得所获得的聚类满足:同一聚类中的对象相似度较高;而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”(引力中心)来进行计算的。大体上说,k-means算法的工作过程说明如下:首先从n个数据对象任意选择k个对象作为初始聚类中心;而对于所剩下其它对象,则根据它们与这些聚类中心的相似度,分别将它们分配给与其最相似的聚类;然后再计算每个所获新聚类的聚类中心;不断重复这一过程直到标准测度函数开始收敛为止。一般都采3各聚类本身尽可能的紧凑,k个聚类具有以下特点:用均方差作为标准测度函数。而各聚类之间尽可能的分开。个簇中的对象分配到Kn个欧氏空间中的对象。划分方法把D假设数据集D包含??CC,...,C,一个目标函数用来评估划D且j1≦i,≤k,=?中,jj1ii分的质量,使得簇内对象相互相似,而与其他簇中的对象相异。也就是说,该目标函数以簇内高相似性和簇间低相似性为目标。?与该簇的代表s基于形心的划分技术使用簇的形心代表该簇。iii之差用dist(s,)度量,其中dist(x,y)=sqrt(∑()^2)这里i=1,2..n。cy?xi2ii1簇的质量可以用簇内变差度量,iii方和,k2),c??dist(s1)(α=icp?i?1i其中,α是数据集中所有对象的误差的平方和;s是空间中的点,表示给定的[2]。-means算法流程k-means算法流程,首先,随机的选择k个对象,每个对象初始地代表了一个聚类的平均值或中心,对剩下的各个对象,根据其与每个聚类中心