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

《K-MEANS(K均值聚类算法,C均值算法).ppt》由会员分享，可在线阅读，更多相关《K-MEANS(K均值聚类算法,C均值算法).ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、无忧无忧PPTPPT整理发布整理发布2.13.2The k-Means Algorithm(K-均值聚类算法）无忧无忧PPTPPT整理发布整理发布主讲内容主讲内容算法性能分析算法性能分析算法改进算法改进算法简介算法简介算法应用算法应用算法要点算法要点算法描述算法描述算法实例算法实例ISODATA算法算法gapstatistics无忧无忧PPTPPT整理发布整理发布算法简介算法简介 k-means算法，也被称为算法，也被称为k-平均或平均或k-均均值，是一种得到最广泛使用的聚类算法。值，是一种得到最广泛使用的聚类算法。它是将各个聚类子集内的所有数据样本的是将各个聚类子集内的所有数据样本的均值作为

2、该聚类的代表点，算法的主要思均值作为该聚类的代表点，算法的主要思想是通过迭代过程把数据集划分为不同的想是通过迭代过程把数据集划分为不同的类别，使得评价聚类性能的准则函数达到类别，使得评价聚类性能的准则函数达到最优，从而使生成的每个聚类内紧凑，类最优，从而使生成的每个聚类内紧凑，类间独立。这一算法不适合处理离散型属性，间独立。这一算法不适合处理离散型属性，但是对于连续型具有较好的聚类效果。但是对于连续型具有较好的聚类效果。无忧无忧PPTPPT整理发布整理发布算法描述算法描述1.为中心向量c1,c2,ck初始化k个种子2.分组:将样本分配给距离其最近的中心向量由这些样本构造不相交（non-over

3、lapping）的聚类3.确定中心:用各个聚类的中心向量作为新的中心4.重复分组和确定中心的步骤，直至算法收敛无忧无忧PPTPPT整理发布整理发布算法算法 k-means算法算法输入：簇的数目输入：簇的数目k和包含和包含n个对象的数据库。个对象的数据库。输出：输出：k个簇，使平方误差准则最小。个簇，使平方误差准则最小。算法步骤：1.为每个聚类确定一个初始聚类中心，这样就有K 个初始聚类中心。2.将样本集中的样本按照最小距离原则分配到最邻近聚类 3.使用每个聚类中的样本均值作为新的聚类中心。4.重复步骤2.3直到聚类中心不再变化。5.结束，得到K个聚类 无忧无忧PPTPPT整理发布整理发布202

4、2/11/19将样本分配给距离它们最近的中心向量，并使目标函数值减小更新簇平均值更新簇平均值计算准则函数计算准则函数E无忧无忧PPTPPT整理发布整理发布K-means聚类算法聚类算法无忧无忧PPTPPT整理发布整理发布 划分聚类方法对数据集进行聚类时包括如下划分聚类方法对数据集进行聚类时包括如下 三个要点：三个要点：（1 1）选定某种距离作为数据样本间的相似性度量）选定某种距离作为数据样本间的相似性度量 上面讲到，上面讲到，k-meansk-means聚类算法不适合处理离散型聚类算法不适合处理离散型 属性，对连续型属性比较适合。因此在计算数据样属性，对连续型属性比较适合。因此在计算数据样本之

5、间的距离时，可以根据实际需要选择欧式距离、本之间的距离时，可以根据实际需要选择欧式距离、曼哈顿距离或者明考斯距离中的一种来作为算法的曼哈顿距离或者明考斯距离中的一种来作为算法的相似性度量，其中最常用的是欧式距离。下面我给相似性度量，其中最常用的是欧式距离。下面我给大家具体介绍一下大家具体介绍一下欧式距离欧式距离。无忧无忧PPTPPT整理发布整理发布 假设给定的数据集假设给定的数据集 ，X X中的中的样本用样本用d d个描述属性个描述属性A A1 1,A,A2 2AAd d来表示，并且来表示，并且d d个描述个描述属性都是连续型属性。数据样本属性都是连续型属性。数据样本x xi i=(x=(xi

6、1i1,x,xi2i2,x,xidid),),x xj j=(x=(xj1j1,x,xj2j2,x,xjdjd)其中，其中，x xi1i1,x,xi2i2,x,xidid和和x xj1j1,x,xj2j2,x,xjdjd分别是样本分别是样本x xi i和和x xj j对应对应d d个描述属性个描述属性A A1 1,A,A2 2,A,Ad d的具体取值。样本的具体取值。样本xixi和和xjxj之间的相似度通之间的相似度通常用它们之间的距离常用它们之间的距离d(xd(xi i,x,xj j)来表示，距离越小，来表示，距离越小，样本样本x xi i和和x xj j越相似，差异度越小；距离越大，样本越

7、相似，差异度越小；距离越大，样本x xi i和和x xj j越不相似，差异度越大。越不相似，差异度越大。欧式距离公式如下：欧式距离公式如下：无忧无忧PPTPPT整理发布整理发布（2 2）选择评价聚类性能的准则函数）选择评价聚类性能的准则函数 k-meansk-means聚类算法使用聚类算法使用误差平方和准则函数误差平方和准则函数来来 评价聚类性能。给定数据集评价聚类性能。给定数据集X X，其中只包含描述属性，其中只包含描述属性，不包含类别属性。假设不包含类别属性。假设X X包含包含k k个聚类子集个聚类子集X X1 1,X,X2 2,X,XK K；各个聚类子集中的样本数量分别为；各个聚类子集中

8、的样本数量分别为n n1 1，n n2 2,n,nk k;各个聚类子集的均值代表点（也称聚类中心）分别各个聚类子集的均值代表点（也称聚类中心）分别为为m m1 1，m m2 2,m,mk k。则误差平方和准则函数公式为：。则误差平方和准则函数公式为：无忧无忧PPTPPT整理发布整理发布 （3）相似度的计算根据一个簇中对象的平均值相似度的计算根据一个簇中对象的平均值 来进行。来进行。（1 1）将所有对象随机分配到）将所有对象随机分配到k k个非空的簇中。个非空的簇中。（2 2）计算每个簇的平均值，并用该平均值代表相）计算每个簇的平均值，并用该平均值代表相应的簇。应的簇。（3 3）根据每个对象与各

9、个簇中心的距离，分配给）根据每个对象与各个簇中心的距离，分配给最近的簇。最近的簇。（4 4）然后转（）然后转（2 2），重新计算每个簇的平均值。），重新计算每个簇的平均值。这个过程不断重复直到满足某个准则函数才停止。这个过程不断重复直到满足某个准则函数才停止。无忧无忧PPTPPT整理发布整理发布Oxy10220031.50450552数据对象集合数据对象集合S见表见表1，作为一个聚类分析的二维，作为一个聚类分析的二维样本，要求的簇的数量样本，要求的簇的数量k=2。(1)选择选择 ，为初始的簇中心，即为初始的簇中心，即 ，。(2)对剩余的每个对象，根据其与各个簇中心的距对剩余的每个对象，根据其与

10、各个簇中心的距离，将它赋给最近的簇。离，将它赋给最近的簇。对对 ：显然显然 ，故将，故将 分配给分配给例子例子无忧无忧PPTPPT整理发布整理发布对于 ：因为 所以将 分配给 对于 ：因为 所以将 分配给更新，得到新簇 和计算平方误差准则，单个方差为Oxy10220031.50450552无忧无忧PPTPPT整理发布整理发布，。总体平均方差是：总体平均方差是：（3）计算新的簇的中心。）计算新的簇的中心。重复（重复（2）和（）和（3），得到），得到O1分配给分配给C1；O2分配给分配给C2，O3分配分配给给C2，O4分配给分配给C2，O5分配给分配给C1。更新，得到新簇。更新，得到新簇和和 。中

11、心为中心为 ，。单个方差分别为单个方差分别为总体平均误差是：总体平均误差是：由上可以看出，第一次迭代后，总体平均误差值由上可以看出，第一次迭代后，总体平均误差值52.2525.65，显著减小。由于在两次迭代中，簇中心不变，所以停止迭代过程显著减小。由于在两次迭代中，簇中心不变，所以停止迭代过程，算法停止算法停止。Oxy10220031.50450552无忧无忧PPTPPT整理发布整理发布k k-means-means算法的性能分析算法的性能分析n主要优点：主要优点：u是解决聚类问题的一种经典算法，简单、快速。是解决聚类问题的一种经典算法，简单、快速。u对处理大数据集，该算法是相对可伸缩和高效率

12、的。对处理大数据集，该算法是相对可伸缩和高效率的。因为它的复杂度是因为它的复杂度是0(n k t),其中其中,n 是所有对象的数目是所有对象的数目,k 是簇的数目是簇的数目,t 是迭代的次数。通是迭代的次数。通常常k n 且且t n。u当结果簇是密集的，而簇与簇之间区别明显时当结果簇是密集的，而簇与簇之间区别明显时,它的效果较好。它的效果较好。n主要缺点主要缺点u在簇的平均值被定义的情况下才能使用，在簇的平均值被定义的情况下才能使用，这对于处理符号属性的数据不这对于处理符号属性的数据不适用。适用。u必须事先给出必须事先给出k k（要生成的簇的数目），而且对初值敏感，对于不同的（要生成的簇的数目

13、），而且对初值敏感，对于不同的初始值，可能会导致不同结果。初始值，可能会导致不同结果。无忧无忧PPTPPT整理发布整理发布K-MeansK-Means算法对于不同的初始值，可能会导致不同结果。解算法对于不同的初始值，可能会导致不同结果。解决方法：决方法：1.1.多设置一些不同的初值，对比最后的运算结果）一直到结多设置一些不同的初值，对比最后的运算结果）一直到结果趋于稳定结束，比较耗时和浪费资源果趋于稳定结束，比较耗时和浪费资源2.很多时候，事先并不知道给定的数据集应该分成多少个类很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。这也是别才最合适。这也是 K-means 算法的一个不

14、足。有的算法算法的一个不足。有的算法是通过类的自动合并和分裂，得到较为合理的类型数目是通过类的自动合并和分裂，得到较为合理的类型数目 K，例如例如 ISODATA 算法算法。3.所谓的gapstatistics（Gap统计模型统计模型）u它对于它对于“躁声躁声”和孤立点数据是敏感的，和孤立点数据是敏感的，少量的该类数少量的该类数据能够对平均值产生极大的影响。据能够对平均值产生极大的影响。无忧无忧PPTPPT整理发布整理发布ISODATA算法算法与与K-均值算法的比较均值算法的比较K-均值算法通常适合于分类数目已知的聚类，而均值算法通常适合于分类数目已知的聚类，而ISODATA算法则更加灵活；算

15、法则更加灵活；从算法角度看，从算法角度看，ISODATA算法与算法与K-均值算法相似，聚均值算法相似，聚类中心都是通过样本均值的迭代运算来决定的；类中心都是通过样本均值的迭代运算来决定的；ISODATA算法加入了一些试探步骤，并且可以结合成算法加入了一些试探步骤，并且可以结合成人机交互的结构，使其能利用中间结果所取得的经验人机交互的结构，使其能利用中间结果所取得的经验更好地进行分类。更好地进行分类。主要是在选代过程中可将一类一分为二，亦可能二类主要是在选代过程中可将一类一分为二，亦可能二类合二为一，即合二为一，即“自组织自组织”，这种算法具有启发式的特，这种算法具有启发式的特点。点。无忧无忧P

16、PTPPT整理发布整理发布与与K-means相比在下列几方面有改进：相比在下列几方面有改进：1.考虑了类别的合并与分裂，因而有了自我调整类别数的考虑了类别的合并与分裂，因而有了自我调整类别数的能力。合并主要发生在某一类内样本个数太少的情况，或能力。合并主要发生在某一类内样本个数太少的情况，或两类聚类中心之间距离太小的情况。为此设有最小类内样两类聚类中心之间距离太小的情况。为此设有最小类内样本数限制本数限制 ，以及类间中心距离参数，以及类间中心距离参数 。若出现两类聚类。若出现两类聚类中心距离小于中心距离小于 的情况，可考虑将此两类合并。的情况，可考虑将此两类合并。分裂则主要发生在某一类别的某分

17、量出现类内方差过分裂则主要发生在某一类别的某分量出现类内方差过大的现象，因而宜分裂成两个类别，以维持合理的类内方大的现象，因而宜分裂成两个类别，以维持合理的类内方差。给出一个对类内分量方差的限制参数差。给出一个对类内分量方差的限制参数 ，用以决定是，用以决定是否需要将某一类分裂成两类。否需要将某一类分裂成两类。2.由于算法有自我调整的能力，因而需要设置若干个由于算法有自我调整的能力，因而需要设置若干个控制用参数，如聚类数期望值控制用参数，如聚类数期望值K、每次迭代允许合并的最、每次迭代允许合并的最大聚类对数大聚类对数L、及允许迭代次数、及允许迭代次数I等。等。无忧无忧PPTPPT整理发布整理发

18、布基本步骤和思路基本步骤和思路（1）选择某些初始值。可选不同的参数指标，也选择某些初始值。可选不同的参数指标，也可在迭代过程中人为修改，以将可在迭代过程中人为修改，以将N个模式样本个模式样本按指标分配到各个聚类中心中去。按指标分配到各个聚类中心中去。（2）计算各类中诸样本的距离指标函数。计算各类中诸样本的距离指标函数。（3）（5）按给定的要求，将前一次获得的聚类）按给定的要求，将前一次获得的聚类集进行分裂和合并处理（集进行分裂和合并处理（4）为分裂处理，）为分裂处理，（5）为合并处理），从而获得新的聚类中心。）为合并处理），从而获得新的聚类中心。（6）重新进行迭代运算，计算各项指标，判断聚重新

19、进行迭代运算，计算各项指标，判断聚类结果是否符合要求。经过多次迭代后，若类结果是否符合要求。经过多次迭代后，若结果收敛，则运算结束。结果收敛，则运算结束。无忧无忧PPTPPT整理发布整理发布2022/11/19初始中心的选取对算法的影响初始中心的选取对算法的影响棋盘格数据集(Checkerboard data set)仅使用其中486个正类数据，并将数据变换到-1,1之间，分布情况如下图所示：无忧无忧PPTPPT整理发布整理发布2022/11/19初始中心的选取对算法的影响初始中心的选取对算法的影响初始聚类中心均在中心附近无忧无忧PPTPPT整理发布整理发布2022/11/19初始中心的选取对

20、算法的影响初始中心的选取对算法的影响初始聚类中心在平面内随机选取无忧无忧PPTPPT整理发布整理发布uk-modes 算法：实现对离散数据的快速聚类，保留了算法：实现对离散数据的快速聚类，保留了k-means算法的效率同时将算法的效率同时将k-means的应用范围扩大到离散数据。的应用范围扩大到离散数据。uK-modes算法是按照算法是按照k-means算法的核心内容进行修改，针算法的核心内容进行修改，针对分类属性的度量和更新质心的问题而改进。对分类属性的度量和更新质心的问题而改进。具体如下具体如下:1.度量记录之间的相关性度量记录之间的相关性D的计算公式是比较两记录之间，属性的计算公式是比较

21、两记录之间，属性相同为相同为0，不同为，不同为1.并所有相加。因此并所有相加。因此D越大，即他的不相关程越大，即他的不相关程度越强（与欧式距离代表的意义是一样的）；度越强（与欧式距离代表的意义是一样的）；2.更新更新modes，使用一个簇的每个属性出现频率最大的那个属，使用一个簇的每个属性出现频率最大的那个属性值作为代表簇的属性值。性值作为代表簇的属性值。k-meansk-means算法的改进方法算法的改进方法k-mode k-mode 算法算法无忧无忧PPTPPT整理发布整理发布uk-Prototype算法：可以对离散与数值属性两种混合的数据算法：可以对离散与数值属性两种混合的数据进行聚类，

22、在进行聚类，在k-prototype中定义了一个对数值与离散属性都中定义了一个对数值与离散属性都计算的相异性度量标准。计算的相异性度量标准。uK-Prototype算法是结合算法是结合K-Means与与K-modes算法，针对算法，针对混合属性的，解决混合属性的，解决2个核心问题如下：个核心问题如下：1.度量具有混合属性的方法是，数值属性采用度量具有混合属性的方法是，数值属性采用K-means方法方法得到得到P1，分类属性采用，分类属性采用K-modes方法方法P2，那么，那么D=P1+a*P2，a是权重，如果觉得分类属性重要，则增加是权重，如果觉得分类属性重要，则增加a，否则减少，否则减少a

23、，a=0时即只有数值属性时即只有数值属性2.更新一个簇的中心的方法，方法是结合更新一个簇的中心的方法，方法是结合K-Means与与K-modes的更新方法。的更新方法。k-meansk-means算法的改进方法算法的改进方法k-prototypek-prototype算法算法无忧无忧PPTPPT整理发布整理发布k-中心点算法：中心点算法：k-means算法对于孤立点是敏感的。为算法对于孤立点是敏感的。为了解决这个问题，不采用簇中的平均值作为参照点，可以了解决这个问题，不采用簇中的平均值作为参照点，可以选用簇中位置最中心的对象，即中心点作为参照点。这样选用簇中位置最中心的对象，即中心点作为参照点

24、。这样划分方法仍然是基于最小化所有对象与其参照点之间的相划分方法仍然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的。异度之和的原则来执行的。k-meansk-means算法的改进方法算法的改进方法k-k-中心点算法中心点算法无忧无忧PPTPPT整理发布整理发布2022/11/19K-means算法在图像分割上的简单应用算法在图像分割上的简单应用例例1：1.图片：一只遥望大海的小狗；2.此图为100 x 100像素的JPG图片，每个像素可以表示为三维向量（分别对应JPEG图像中的红色、绿色和蓝色通道）；3.将图片分割为合适的背景区域（三个）和前景区域（小狗）；4.使用K-means

25、算法对图像进行分割。无忧无忧PPTPPT整理发布整理发布2022/11/19在图像分割上的简单应用在图像分割上的简单应用分割后的效果注：最大迭代次数为20次，需运行多次才有可能得到较好的效果。无忧无忧PPTPPT整理发布整理发布2022/11/19在图像分割上的简单应用在图像分割上的简单应用例例2：注：聚类中心个数为5，最大迭代次数为10。无忧无忧PPTPPT整理发布整理发布无忧无忧PPTPPT整理发布整理发布无忧无忧PPTPPT整理发布整理发布2022/11/19Matlab程序实现程序实现clcclearticRGB=imread(test5.jpg);%读入像img=rgb2gray(R

26、GB);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);无忧无忧PPTPPT整理发布整理发布 b=abs(img-c3(i);%计算各像素灰度与聚类中心的距离 r_g=r-g;g_b=g-b;r_b=r-b;n_r=find(r

27、_g=0&r_b0&g_b0&r_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);无忧无忧PPTPPT整理发布整理发布 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;endendR G Bimg=uint8(img);img(find(imgR&imgG)=255;tocsubplot(2,2,3),imshow(img);title(图三 聚类后的图像)subplot(2,2,4),imhist(img);title(图四 聚类后的图像直方图)无忧无忧PPTPPT整理发布整理发布结束 谢谢