1、算法简介算法简介 k-means算法，也被称为k-平均或k-均 值，是一种得到最广泛使用的聚类算法。 它是将各个聚类子集内的所有数据样本的 均值作为该聚类的代表点，算法的主要思 想是通过迭代过程把数据集划分为不同的 类别，使得评价聚类性能的准则函数达到 最优，从而使生成的每个聚类内紧凑，类 间独立。这一算法不适合处理离散型属性 ，但是对于连续型具有较好的聚类效果。 1 算法描述 1. 为中心向量c1, c2, , ck初始化k个种子 2. 分组: 将样本分配给距离其最近的中心向量 由这些样本构造不相交（ non-overlapping ） 的聚类 3. 确定中心: 用各个聚类的中心向量作为新的
2、中心 4. 重复分组和确定中心的步骤，直至算法收敛 2 算法 k-means算法 输入：簇的数目k和包含n个对象的数据库。 输出：k个簇，使平方误差准则最小。 算法步骤： 1.为每个聚类确定一个初始聚类中心，这样就有K 个 初始聚类中心。 2.将样本集中的样本按照最小距离原则分配到最邻 近聚类 3.使用每个聚类中的样本均值作为新的聚类中心。 4.重复步骤2.3直到聚类中心不再变化。 5.结束，得到K个聚类 3 2020/3/10 将样本分配给距离它们最近的中心向量，并使目 标函数值减小 更新簇平均值 计算准则函数E 4 无忧无忧无忧无忧PPTPPTPPTPPT整理发布整理发布整理发布整理发布
3、K-means聚类算法 5 划分聚类方法对数据集进行聚类时包括如下 三个要点： （1）选定某种距离作为数据样本间的相似性度量 上面讲到，k-means聚类算法不适合处理离散型 属性，对连续型属性比较适合。因此在计算数据样 本之间的距离时，可以根据实际需要选择欧式距离 、曼哈顿距离或者明考斯距离中的一种来作为算法 的相似性度量，其中最常用的是欧式距离。下面我 给大家具体介绍一下欧式距离。 6 假设给定的数据集 ，X中的 样本用d个描述属性A1,A2Ad来表示，并且d个描述 属性都是连续型属性。数据样本xi=(xi1,xi2,xid), xj=(xj1,xj2,xjd)其中， xi1,xi2,xi
4、d和 xj1,xj2,xjd分别是样本xi和xj对应d个描述属性 A1,A2,Ad的具体取值。样本xi和xj之间的相似度通 常用它们之间的距离d(xi,xj)来表示，距离越小， 样本xi和xj越相似，差异度越小；距离越大，样本xi 和xj越不相似，差异度越大。 欧式距离公式如下： 7 （2）选择评价聚类性能的准则函数 k-means聚类算法使用误差平方和准则函数来 评价聚类性能。给定数据集X，其中只包含描述属性 ，不包含类别属性。假设X包含k个聚类子集 X1,X2,XK；各个聚类子集中的样本数量分别为n1， n2,nk;各个聚类子集的均值代表点（也称聚类中 心）分别为m1，m2,mk。则误差平
5、方和准则函数公 式为： 8 （3）相似度的计算根据一个簇中对象的平均值 来进行。 （1）将所有对象随机分配到k个非空的簇中。 （2）计算每个簇的平均值，并用该平均值代表相 应的簇。 （3）根据每个对象与各个簇中心的距离，分配给 最近的簇。 （4）然后转（2），重新计算每个簇的平均值。 这个过程不断重复直到满足某个准则函数才停止 。 9 Oxy 102 200 31.50 450 552 数据对象集合S见表1，作为一个聚类分析的二维 样本，要求的簇的数量k=2。 (1)选择 ， 为初始的簇中心，即 ， 。 (2)对剩余的每个对象，根据其与各个簇中心的距 离，将它赋给最近的簇。 对 ： 显然 ，故
6、将 分配给 例子 10 对于 ： 因为 所以将 分配给 对于 ： 因为 所以将 分配给 更新，得到新簇 和 计算平方误差准则，单个方差为 Oxy 102 200 31.50 450 552 11 ， 。 总体平均方差是： （3）计算新的簇的中心。 重复（2）和（3），得到O1分配给C1；O2分配给C2，O3分配 给C2 ，O4分配给C2，O5分配给C1。更新，得到新簇 和 。 中心为 ， 。 单个方差分别为 总体平均误差是 ： 由上可以看出，第一次迭代后，总体平均误差值52.2525.65， 显著减小。由于在两次迭代中，簇中心不变，所以停止迭代过程 ，算法停止。 Oxy 102 200 31.
7、50 450 552 12 k-means算法的性能分析 n主要优点： u是解决聚类问题的一种经典算法，简单、快速。 u对处理大数据集，该算法是相对可伸缩和高效率的。因为它的复杂度 是0 (n k t ) , 其中, n 是所有对象的数目, k 是簇的数目, t 是迭代的次数。 通常k n 且t n 。 u当结果簇是密集的，而簇与簇之间区别明显时, 它的效果较好。 n主要缺点 u在簇的平均值被定义的情况下才能使用，这对于处理符号属性的数据 不适用。 u必须事先给出k（要生成的簇的数目），而且对初值敏感，对于不同的 初始值，可能会导致不同结果。 13 uk-Prototype算法：可以对离散与数
8、值属性两种混合的数据 进行聚类，在k-prototype中定义了一个对数值与离散属性都 计算的相异性度量标准。 uK-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算法 14 k-中心点算法：
9、k -means算法对于孤立点是敏感的。为 了解决这个问题，不采用簇中的平均值作为参照点，可以 选用簇中位置最中心的对象，即中心点作为参照点。这样 划分方法仍然是基于最小化所有对象与其参照点之间的相 异度之和的原则来执行的。 k-means算法的改进方法k-中心点算法 15 2020/3/10 K-means算法在图像分割上的简单应用 例1： 1.图片：一只遥望大海的小狗； 2.此图为100 x 100像素的JPG图片，每个像素可以表示为三维向量（分别对应 JPEG图像中的红色、绿色和蓝色通道） ； 3.将图片分割为合适的背景区域（三个）和前景区域（小狗）； 4.使用K-means算法对图像进行分割。 16 2020/3/10 在图像分割上的简单应用 分割后的效果 注：最大迭代次数为20次，需运行多次才有可能得到较好的效果。 17 2020/3/10 在图像分割上的简单应用 例2： 注：聚类中心个数为5，最大迭代次数为10。 18 19 20
