,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2020/6/3,#,K-means,算法及在图像分割中的简单应用,1,K-means算法及在图像分割中的简单应用1,主要内容,算法简介,算法要点,实例,性能分析,算法改进,在图像分割中的简单应用,2,主要内容算法简介2,算法简介,k,-means,算法：一种得到最广泛使用的聚类算法,算法的主要思想：,将各个聚类子集内的所有数据样本的均值作为该聚类的代表点,通过迭代过程把数据集划分为不同的类别,使得评价聚类性能的准则函数达到最优，从而使生成的每个聚类内紧凑，类间独立。,使用范围：不适合处理离散型属性，但是对于,连续型,具有较好的聚类效果。,3,算法简介k-means算法：一种得到最广泛使用的聚类算法 3,k,-means,算法,输入：簇的数目,k,和包含,n,个对象的数据库。,输出：,k,个簇，使平方误差准则最小。,算法步骤：,1.,为每个聚类确定一个初始聚类中心，这样就有,K,个初始聚类中心。,2.,将样本集中的样本按照最小距离原则分配到最邻近聚类,3.,使用每个聚类中的样本均值作为新的聚类中心。,4.,重复步骤,2.3,直到聚类中心不再变化。,5.,结束，得到,K,个聚类,4,k-means算法输入：簇的数目k和包含n个对象的数据库。,将样本分配给距离它们最近的中心向量，并使目标函数值减小,更新簇平均值,计算准则函数,E,5,将样本分配给距离它们最近的中心向量，并使目标函数值减小,算法要点,1,）选定某种距离作为数据样本间的相似性度量,在计算数据样本之间的距离时，可以根据实际需要选择欧式距离、曼哈顿距离或者明考斯距离中的一种来作为算法的相似性度量，其中最常用的是,欧式距离,。,6,距离越小，样本,x,i,和,x,j,越相似，差异度越小；,距离越大，样本,x,i,和,x,j,越不相似，差异度越大。,算法要点1）选定某种距离作为数据样本间的相似性度量,（,2,）选择评价聚类性能的准则函数,:,误差平方和准则函数,给定数据集,X,，假设,X,包含,k,个聚类子集,X,1,X,2,X,K,；各个聚类子集中的样本数量分别为,n,1,，,n,2,n,k,;,各个聚类子集的均值代表点（也称聚类中心）分别为,m,1,，,m,2,m,k,。则误差平方和准则函数公式为：,7,（2）选择评价聚类性能的准则函数:7,（,3,）,相似度的计算根据一个类中对象的平均值 来进行。,将所有对象随机分配到,k,个非空的类中。,计算每个类的平均值，并用该平均值代表相应的类。,根据每个对象与各个类中心的距离，分配给最近的类。,然后转（,2,），重新计算每个类的平均值。这个过程不断重复直到满足某个准则函数才停止。,8,（3）相似度的计算根据一个类中对象的平均值,O,x,y,1,0,2,2,0,0,3,1.5,0,4,5,0,5,5,2,数据对象集合,S,如表所示，作为一个聚类分析的二维样本，要求聚类的数量,k=2,。,(1),选择 ，为初始的类中心，即 ，。,(2),对剩余的每个对象，根据其与各个类中心的距离，将它赋给最近的类。,对 ：,显然 ，故将 分配给,例子,9,Oxy10220031.50450552 数据,对于 ：,因为,，所以将 分配给,对于 ：,因为 ，所以将 分配给,更新，得到新类 和,计算平方误差准则，单个方差为,O,x,y,1,0,2,2,0,0,3,1.5,0,4,5,0,5,5,2,10,对于 ：Oxy10220031.50450,，,。,总体平均方差是：,（,3,）计算新的聚类的中心。,重复（,2,）和（,3,），得到,O,1,分配给,C,1,；,O,2,分配给,C,2,，,O,3,分配给,C,2,，,O,4,分配给,C,2,，,O,5,分配给,C,1,。更新，得到新类,和 。中心为 ，。,单个方差分别为,总体平均误差是：,由上可以看出，第一次迭代后，总体平均误差值,52.25,降到,25.65,，显著减小。由于在这次迭代中，类中心不变，所以停止迭代过程,，,算法停止,。,O,x,y,1,0,2,2,0,0,3,1.5,0,4,5,0,5,5,2,11,，。总体平均方差是：重复（2）和（3），得到O1分配给C1；,性能分析,主要优点：,是解决聚类问题的一种经典算法，简单、快速。,对处理大数据集，该算法是相对可伸缩和高效率的。,当结果类是密集的，而类与类之间区别明显时,它的效果较好。,主要缺点,在类的平均值被定义的情况下才能使用，,这对于处理符号属性的数据不适用。,必须事先给出,k,（要生成的类的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。,它对于“躁声”和孤立点数据是敏感的，,少量的该类数据能够对平均值产生极大的影响。,12,性能分析主要优点：12,针对,K-means,算法缺点的改进方法,1.,对于不同的初始值，可能会导致不同结果：多设置一些不同的初值，但比较耗时和浪费资源。,2.,分类数目,K,不确定：通过类的自动合并和分裂，得到较为合理的类型数目,K,，例如,ISODATA,算法。相同点：聚类中心都是通过样本均值的迭代运算来决定的；,不同点：主要是在选代过程中可将一类一分为二，亦可能二类合二为一，即“自组织”，这种算法具有启发式的特点。,由于算法有自我调整的能力，因而需要设置若干个控制用参数，如聚类数期望值,K,、最小类内样本数、类间中心距离参数、每次迭代允许合并的最大聚类对数,L,及允许迭代次数,I,等。,13,针对K-means算法缺点的改进方法1.对于不同的初始值，可,k-,center,算法：解决,k,-means,算法对于孤立点是敏感的问题,不采用簇中的平均值作为参照点，可以选用类中位置最中心的对象，即中心点作为参照点。,划分方法仍然是基于,最小化,所有对象与其参照点之间的相异度之和的原则来执行的。,k-means,算法的改进方法,k-,center,算法,14,k-center算法：解决k-means算法对于孤立点是,k-modes,算法：实现对,离散数据,的快速聚类，处理分类属性型数据，例如：姓名、性别、年龄等。,采用差异度,D,来代替,k-means,算法中的距离，差异度越小，则表示距离越小。一个样本和一个聚类中心的差异度就是它们各个属性不相同的个数，,属性相同为,0,，不同为,1,，并计算,1,的总和。因此,D,越大，即他的不相关程度越强。,k-means,算法的改进方法,k-mode s,算法,15,k-modes 算法：实现对离散数据的快速聚类，处理分类属性,16,K-means,算法在图像分割上的简单应用,图为,384,x,256,像素的,JPG,图片，使用,K-means,算法将图片分割为,4,个区域，背景用黑色表示。,设置聚类数目为,4,。,原图 聚类后效果,16K-means算法在图像分割上的简单应用图为384 x,17,分割结果,17分割结果,18,Thank you!,18Thank you!,谢谢观看！,2020,谢谢观看！,