K-MEANS(K均值聚类算法-C均值算法).pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,无忧,PPT,整理发布,2.13.2,The k-Means Algorithm,(K-,均值聚类算法）,主讲内容,算法性能分析,算法改进,算法简介,算法应用,算法要点,算法描述,算法实例,ISODATA,算法,gapstatistics,算法简介,k,-means,算法，也被称为,k,-,平均或,k,-,均值，是一种得到最广泛使用的聚类算法。,它,是将各个聚类子集内的所有数据样本的均值作为该聚类的代表点，算法的主要思想是通过迭代过程把数据集划分为不同的类别，使得评价聚类性能的准则函数达到最优，从而使生成的每个聚类内紧凑，类间独立。这一算法不适合处理离散型属性，但是对于连续型具有较好的聚类效果。,算法描述,为中心向量,c,1,c,2,c,k,初始化,k,个种子,分组,:,将样本分配给距离其最近的中心向量,由这些样本构造不相交（,non-overlapping,）的聚类,确定中心,:,用各个聚类的中心向量作为新的中心,重复分组和确定中心的步骤，直至算法收敛,算法,k,-means,算法,输入：簇的数目,k,和包含,n,个对象的数据库。,输出：,k,个簇，使平方误差准则最小。,算法步骤：,1.,为每个聚类确定一个初始聚类中心，这样就有,K,个初始聚类中心。,2.,将样本集中的样本按照最小距离原则分配到最邻近聚类,3.,使用每个聚类中的样本均值作为新的聚类中心。,4.,重复步骤,2.3,直到聚类中心不再变化。,5.,结束，得到,K,个聚类,2025/9/27 周六,将样本分配给距离它们最近的中心向量，并使目标函数值减小,更新簇平均值,计算准则函数,E,假设给定的数据集 ，,X,中的样本用,d,个描述属性,A,1,A,2,A,d,来表示，并且,d,个描述属性都是连续型属性。数据样本,x,i,=(x,i1,x,i2,x,id,),x,j,=(x,j1,x,j2,x,jd,),其中，,x,i1,x,i2,x,id,和,x,j1,x,j2,x,jd,分别是样本,x,i,和,x,j,对应,d,个描述属性,A,1,A,2,A,d,的具体取值。样本,xi,和,xj,之间的相似度通常用它们之间的距离,d(x,i,x,j,),来表示，距离越小，样本,x,i,和,x,j,越相似，差异度越小；距离越大，样本,x,i,和,x,j,越不相似，差异度越大。,欧式距离公式如下：,（,2,）选择评价聚类性能的准则函数,k-means,聚类算法使用,误差平方和准则函数,来 评价聚类性能。给定数据集,X,，其中只包含描述属性，不包含类别属性。假设,X,包含,k,个聚类子集,X,1,X,2,X,K,；各个聚类子集中的样本数量分别为,n,1,，,n,2,n,k,;,各个聚类子集的均值代表点（也称聚类中心）分别为,m,1,，,m,2,m,k,。则误差平方和准则函数公式为：,（,3,）,相似度的计算根据一个簇中对象的平均值 来进行。,（,1,）将所有对象随机分配到,k,个非空的簇中。,（,2,）计算每个簇的平均值，并用该平均值代表相应的簇。,（,3,）根据每个对象与各个簇中心的距离，分配给最近的簇。,（,4,）然后转（,2,），重新计算每个簇的平均值。这个过程不断重复直到满足某个准则函数才停止。,O,x,y,1,0,2,2,0,0,3,1.5,0,4,5,0,5,5,2,数据对象集合,S,见表,1,，作为一个聚类分析的二维样本，要求的簇的数量,k=2,。,(1),选择 ，为初始的簇中心，即 ，。,(2),对剩余的每个对象，根据其与各个簇中心的距离，将它赋给最近的簇。,对 ：,显然 ，故将 分配给,例子,对于,：,因为 所以将 分配给,对于 ：,因为 所以将 分配给,更新，得到新簇 和,计算平方误差准则，单个方差为,O,x,y,1,0,2,2,0,0,3,1.5,0,4,5,0,5,5,2,，,。,总体平均方差是：,（,3,）计算新的簇的中心。,重复（,2,）和（,3,），得到,O,1,分配给,C,1,；,O,2,分配给,C,2,，,O,3,分配给,C,2,，,O,4,分配给,C,2,，,O,5,分配给,C,1,。更新，得到新簇,和 。中心为 ，。,单个方差分别为,总体平均误差是：,由上可以看出，第一次迭代后，总体平均误差值,52.2525.65,，显著减小。由于在两次迭代中，簇中心不变，所以停止迭代过程,，,算法停止,。,O,x,y,1,0,2,2,0,0,3,1.5,0,4,5,0,5,5,2,k,-means,算法的性能分析,主要优点：,是解决聚类问题的一种经典算法，简单、快速。,对处理大数据集，该算法是相对可伸缩和高效率的。,因为它的复杂度是,0(n k t),其中,n,是所有对象的数目,k,是簇的数目,t,是迭代的次数。通常,k n,且,t n,。,当结果簇是密集的，而簇与簇之间区别明显时,它的效果较好。,主要缺点,在簇的平均值被定义的情况下才能使用，,这对于处理符号属性的数据不适用。,必须事先给出,k,（要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。,K-Means,算法对于不同的初始值，可能会导致不同结果。解决方法：,1.,多设置一些不同的初值，对比最后的运算结果）一直到结果趋于稳定结束，比较耗时和浪费资源,2.,很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。这也是,K-means,算法的一个不足。有的算法是通过类的自动合并和分裂，得到较为合理的类型数目,K,，例如,ISODATA,算法,。,3.,所谓的,gapstatistics,（,Gap,统计模型,）,它对于“躁声”和孤立点数据是敏感的，,少量的该类数据能够对平均值产生极大的影响。,ISODATA,算法,与,K-,均值算法的比较,K-,均值算法通常适合于分类数目已知的聚类，而,ISODATA,算法则更加灵活；,从算法角度看，,ISODATA,算法与,K-,均值算法相似，聚类中心都是通过样本均值的迭代运算来决定的；,ISODATA,算法加入了一些试探步骤，并且可以结合成人机交互的结构，使其能利用中间结果所取得的经验更好地进行分类。,主要是在选代过程中可将一类一分为二，亦可能二类合二为一，即“自组织”，这种算法具有启发式的特点。,与,K-means,相比在下列几方面有改进：,1.,考虑了类别的合并与分裂，因而有了自我调整类别数的能力。合并主要发生在某一类内样本个数太少的情况，或两类聚类中心之间距离太小的情况。为此设有最小类内样本数限制,，以及类间中心距离参数,。若出现两类聚类中心距离小于,的情况，可考虑将此两类合并。,分裂则主要发生在某一类别的某分量出现类内方差过大的现象，因而宜分裂成两个类别，以维持合理的类内方差。给出一个对类内分量方差的限制参数,，用以决定是否需要将某一类分裂成两类。,2.,由于算法有自我调整的能力，因而需要设置若干个控制用参数，如聚类数期望值,K,、每次迭代允许合并的最大聚类对数,L,、及允许迭代次数,I,等。,基本步骤和思路,（,1,）选择某些初始值。可选不同的参数指标，也可在迭代过程中人为修改，以将,N,个模式样本按指标分配到各个聚类中心中去。,（,2,）计算各类中诸样本的距离指标函数。,（,3,）,（,5,）按给定的要求，将前一次获得的聚类集进行分裂和合并处理（,4,）为分裂处理，（,5,）为合并处理），从而获得新的聚类中心。,（,6,）重新进行迭代运算，计算各项指标，判断聚类结果是否符合要求。经过多次迭代后，若结果收敛，则运算结束。,2025/9/27 周六,初始中心的选取对算法的影响,棋盘格数据集,(Checkerboard data set),仅使用其中,486,个正类数据，并将数据变换到,-1,1,之间，分布情况如下图所示：,2025/9/27 周六,初始中心的选取对算法的影响,初始聚类中心均在中心附近,2025/9/27 周六,初始中心的选取对算法的影响,初始聚类中心在平面内随机选取,k-modes,算法：实现对离散数据的快速聚类，保留了,k-means,算法的效率同时将,k-means,的应用范围扩大到离散数据。,K-modes,算法是按照,k-means,算法的核心内容进行修改，针对分类属性的度量和更新质心的问题而改进。,具体如下,:,1.,度量记录之间的相关性,D,的计算公式是比较两记录之间，属性相同为,0,，不同为,1.,并所有相加。因此,D,越大，即他的不相关程度越强（与欧式距离代表的意义是一样的）；,2.,更新,modes,，使用一个簇的每个属性出现频率最大的那个属性值作为代表簇的属性值。,k-means,算法的改进方法,k-mode,算法,k,-Prototype,算法：可以对离散与数值属性两种混合的数据进行聚类，在,k,-prototype,中定义了一个对数值与离散属性都计算的相异性度量标准。,K-Prototype,算法是结合,K-Means,与,K-modes,算法，针对混合属性的，解决,2,个核心问题如下：,1.,度量具有混合属性的方法是，数值属性采用,K-means,方法得到,P1,，分类属性采用,K-modes,方法,P2,，那么,D=P1+a*P2,，,a,是权重，如果觉得分类属性重要，则增加,a,，否则减少,a,，,a=0,时即只有数值属性,2.,更新一个簇的中心的方法，方法是结合,K-Means,与,K-modes,的更新方法。,k-means,算法的改进方法,k-prototype,算法,k,-,中心点算法：,k,-means,算法对于孤立点是敏感的。为了解决这个问题，不采用簇中的平均值作为参照点，可以选用簇中位置最中心的对象，即中心点作为参照点。这样划分方法仍然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的。,k-means,算法的改进方法,k-,中心点算法,2025/9/27 周六,K-means,算法在图像分割上的简单应用,例,1,：,图片：一只遥望大海的小狗；,此图为,100 x 100,像素的,JPG,图片，每个像素可以表示为三维向量（分别对应,JPEG,图像中的红色、绿色和蓝色通道）,；,将图片分割为合适的背景区域（三个）和前景区域（小狗）；,使用,K-means,算法对图像进行分割。,2025/9/27 周六,在图像分割上的简单应用,分割后的效果,注：最大迭代次数为,20,次，需运行多次才有可能得到较好的效果。,2025/9/27 周六,在图像分割上的简单应用,例,2,：,注：聚类中心个数为,5,，最大迭代次数为,10,。,2025/9/27 周六,Matlab,程序实现,clc,clear,tic,RGB=imread(test5.jpg);%,读入像,img=rgb2gray(RGB);,m,n=size(img);,subplot(2,2,1),imshow(img);title(,图一 原图像,),subplot(2,2,2),imhist(img);title(,图二 原图像的灰度直方图,),hold off;,img=double(img);,for i=1:200,c1(1)=25;,c2(1)=125;,c3(1)=200;%,选择三个初始聚类中心,r=abs(img-c1(i);,g=abs(img-c2(i);,b=abs(img-c3(i);%,计算各像素灰度与聚类中心的距离,r_g=r-g;,g_b=g-b;,r_b=r-b;,n_r=find(r_g0%,寻找中间的一个聚类中心,n_b=find(g_b0%,寻找最大的聚类中心,i=i+1;,c1(i)=sum(img(n_r)/length(n_r);%,将所有低灰度求和取平均，作为下一个低灰度中心,c2(i)=sum(img(n_g)/length(n_g);%,将所有中间灰度求和取平均，作为下一个中间灰度中心,c3(i)=sum(img(n_b)/length(n_b);%,将所有高灰度求和取平均，作为下一个高灰度中心,d1(i)=abs(c1(i)-c1(i-1);,d2(i)=abs(c2(i)-c2(i-1);,d3(i)=abs(c3(i)-c3(i-1);,if d1(i)=0.001&d2(i)=0.001&d3(i)=0.001,R=c1(i);,G=c2(i);,B=c3(i);,k=i;,break;,end,end,R,G,B,img=uint8(img);,img(find(imgR,img(find(imgG)=255;,toc,subplot(2,2,3),imshow(img);title(,图三 聚类后的图像,),subplot(2,2,4),imhist(img);title(,图四 聚类后的图像直方图,),结束 谢谢,