k-means算法.docx

目录1. 算法简介 12. 算法原理及实现 -means算法描述 -means算法流程 33. 算法性能分析 k-means算法优缺点分析 -means算法优点 -means算法缺点 54. k-means算法的改进算法 k-mode算法 -prototype算法 -中心点算法 85. 实验结果 86. 总结 12算法简介k-means算法,也被称为k-平均或k-均值,是一种得到最广泛使用的聚类算法。它是将各个聚类子集内的所有数据样本的均值作为该聚类的代表点,算法的主要思想是通过迭代过程把数据集划分为不同的类别,使得评价聚类性能的准则函数达到最优,从而使生成的每个聚类内紧凑,类间独立。这一算法不适合处理离散型属性,但是对于连续型具有较好的聚类效果。(1)选定某种距离作为数据样本间的相似性度量 k-means聚类算法不适合处理离散型属性,对连续型属性比较适合。因此在计算数据样本之间的距离时,可以根据实际需要选择欧式距离、曼哈顿距离或者明考斯距离中的一种来作为算法的相似性度量,其中最常用的是欧式距离。下面我给大家具体介绍一下欧式距离。假设给定的数据集X=xmm=1,2,…,total,X中的样本用d个描述属性A1,A2,…,Ad来表示,并且d个描述属性都是连续型属性。数据样本xi=xi1,xi2,…,xid, xj=xj1,xj2,…,xjd其中,xi1,xi2,…,xid和xj1,xj2,…,xjd分别是样本xi和xj对应d个描述属性A1,A2,…,Ad的具体取值。样本xi和xj之间的相似度通常用它们之间的距离dxi,xj来表示,距离越小,样本xi和xj越相似,差异度越小;距离越大,样本xi和xj越不相似,差异度越大。欧式距离公式如下:dxi,xj=k=1dxik-xjk2。(2)选择评价聚类性能的准则函数 k-means聚类算法使用误差平方和准则函数来评价聚类性能。给定数据集X,其中只包含描述属性,不包含类别属性。假设X包含k个聚类子集X1,X2,…,Xk;各个聚类子集中的样本数量分别为n1,n2,…,nk;各个聚类子集的均值代表点(也称聚类中心)分别为m1,m2,…,mk。误差平方和准则函数公式为:E=i=1kp∈Xip-mi2。(3)相似度的计算根据一个簇中对象的平均值来进行。a)将所有对象随机分配到k个非空的簇中;b)计算每个簇的平均值,并用该平均值代表相应的簇;c)根据每个对象与各个簇中心的距离,分配给最近的簇;d)然后转b),重新计算每个簇的平均值。这个过程不断重复直到满足某个准则函数才停止。-means算法描述(1)为中心向量c1,c2,..,ck初始化k个种子;(2)分组:a) 将样本分配给距离其最近的中心向量;b) 由这些样本构造不相交(non-overlapping)的聚类;(3)确定中心:a) 用各个聚类的中心向量作为新的中心;(4)重复分组和确定中心的步骤,直至算法收敛;-means算法流程输入:簇的数目k和包含n个对象的数据库。输出:k个簇,使平方误差准则最小。算法步骤:(1)为每个聚类确定一个初始聚类中心,这样就有K 个初始聚类中心。(2)将样本集中的样本按照最小距离原则分配到最邻近聚类。(3)使用每个聚类中的样本均值作为新的聚类中心。(4)重复步骤(2),(3)步直到聚类中心不再变化。算法性能分析k--means算法优点k-means算法作为使用最为广泛的聚类算法,其优点自然是显而易见的,它在解决聚类问题上,通常可以快速、有效的得到一个不错的结果。同时,对处理大数据集,该算法是相对可伸缩和高效率的。因为它的复杂度是0(n k t)。其中n是所有对象的数目,k是簇的数目, t是迭代的次数。通常k<<n且t<<n。而且,当结果簇是密集的,而簇与簇之间区别明显时, 它的效果较好。-means算法缺点k-means算法只是一种快速对数据进行简单聚类的算法,所以该算法在聚类方面也存在着很多的不足之处,其主要的缺点有三点:(1)在 k-means 算法中k是事先给定的,这个k值的选定是非常难以估计的。很多时候,事先并不知道给定的数据集应该分成多少个类别才最合适。这也是 k-means 算法的一个不足。有的算法是通过类的自动合并和分裂,得到较为合理的类型数目 k,例如 ISODATA 算法。关于k-means算法中聚类数目k值的确定,有一种思想是根据方差分析理论,应用混合 F 统计量来确定最佳分类数,并应用模糊划分熵来验证最佳分类数的正确性。另外一种思想使用了一种结合全协方差