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

算法简介算法简介• k-means算法，也被称为算法，也被称为k-平均或平均或k-均值，是均值，是一种得到最广泛使用的聚类算法一种得到最广泛使用的聚类算法 它是将各个是将各个聚类子集内的所有数据样本的均值作为该聚类聚类子集内的所有数据样本的均值作为该聚类的代表点，算法的主要思想是通过迭代过程把的代表点，算法的主要思想是通过迭代过程把数据集划分为不同的类别，使得评价聚类性能数据集划分为不同的类别，使得评价聚类性能的准则函数达到最优，从而使生成的每个聚类的准则函数达到最优，从而使生成的每个聚类内紧凑，类间独立这一算法不适合处理离散内紧凑，类间独立这一算法不适合处理离散型属性，但是对于连续型具有较好的聚类效果型属性，但是对于连续型具有较好的聚类效果•算法描述算法描述1.为中心向量c1, c2, …, ck初始化k个种子2.分组:ü将样本分配给距离其最近的中心向量ü由这些样本构造不相交（ non-overlapping ）的聚类3.确定中心:ü用各个聚类的中心向量作为新的中心4.重复分组和确定中心的步骤，直至算法收敛算法算法 k-means算法算法输入：簇的数目输入：簇的数目k和包含和包含n个对象的数据库。

个对象的数据库输出：输出：k个簇，使平方误差准则最小个簇，使平方误差准则最小算法步骤： 1.为每个聚类确定一个初始聚类中心，这样就有K 个初始聚类中心 2.将样本集中的样本按照最小距离原则分配到最邻近聚类 3.使用每个聚类中的样本均值作为新的聚类中心 4.重复步骤直到聚类中心不再变化 5.结束，得到K个聚类 将样本分配给距离它们最近的中心向量，并使目标函数值减小更新簇平均值更新簇平均值计算准则函数计算准则函数E9/7/2024K-means聚类算法聚类算法 划分聚类方法对数据集进行聚类时包括如下划分聚类方法对数据集进行聚类时包括如下 三个要点：三个要点：• （（1 1）选定某种距离作为数据样本间的相似性度量）选定某种距离作为数据样本间的相似性度量 上面讲到，上面讲到，k-meansk-means聚类算法不适合处理离散型聚类算法不适合处理离散型 属性，对连续型属性比较适合因此在计算数据样属性，对连续型属性比较适合。

因此在计算数据样本之间的距离时，可以根据实际需要选择欧式距离、本之间的距离时，可以根据实际需要选择欧式距离、曼哈顿距离或者明考斯距离中的一种来作为算法的曼哈顿距离或者明考斯距离中的一种来作为算法的相似性度量，其中最常用的是欧式距离下面我给相似性度量，其中最常用的是欧式距离下面我给大家具体介绍一下大家具体介绍一下欧式距离欧式距离 假设给定的数据集假设给定的数据集 ，，X X中的中的样本用样本用d d个描述属性个描述属性A A1 1,A,A2 2…A…Ad d来表示，并且来表示，并且d d个描述个描述属性都是连续型属性数据样本属性都是连续型属性数据样本x xi i=(x=(xi1i1,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越相似，差异度越小；距离越大，样本越相似，差异度越小；距离越大，样本x xi i和和x xj j越不相似，差异度越大越不相似，差异度越大 欧式距离公式如下：欧式距离公式如下：•（（2 2）选择评价聚类性能的准则函数）选择评价聚类性能的准则函数 k-meansk-means聚类算法使用聚类算法使用误差平方和准则函数误差平方和准则函数来来 评价聚类性能给定数据集评价聚类性能给定数据集X X，其中只包含描述属性，，其中只包含描述属性，不包含类别属性假设不包含类别属性假设X X包含包含k k个聚类子集个聚类子集X X1 1,X,X2 2,…X,…XK K；各个聚类子集中的样本数量分别为；各个聚类子集中的样本数量分别为n n1 1，，n n2 2,…,n,…,nk k; ;各个聚类子集的均值代表点（也称聚类中心）分别各个聚类子集的均值代表点（也称聚类中心）分别为为m m1 1，，m m2 2,…,m,…,mk k。

则误差平方和准则函数公式为：则误差平方和准则函数公式为：• （（3））相似度的计算根据一个簇中对象的平均值相似度的计算根据一个簇中对象的平均值 来进行•（（1 1）将所有对象随机分配到）将所有对象随机分配到k k个非空的簇中个非空的簇中•（（2 2）计算每个簇的平均值，并用该平均值代表相）计算每个簇的平均值，并用该平均值代表相应的簇•（（3 3）根据每个对象与各个簇中心的距离，分配给）根据每个对象与各个簇中心的距离，分配给最近的簇最近的簇•（（4 4）然后转（）然后转（2 2），重新计算每个簇的平均值重新计算每个簇的平均值这个过程不断重复直到满足某个准则函数才停止这个过程不断重复直到满足某个准则函数才停止Oxy10220031.50450552数据对象集合数据对象集合S见表见表1，作为一个聚类分析的二维，作为一个聚类分析的二维样本，要求的簇的数量样本，要求的簇的数量k=21)选择选择 ，， 为初始的簇中心，即为初始的簇中心，即 ，， 。

2)对剩余的每个对象，根据其与各个簇中心的距对剩余的每个对象，根据其与各个簇中心的距离，将它赋给最近的簇离，将它赋给最近的簇 对对 ：： 显然显然 ，故将，故将 分配给分配给例子例子•对于 ：•因为 所以将 分配给• 对于 ：•因为 所以将 分配给•更新，得到新簇 和•计算平方误差准则，单个方差为Oxy10220031.50450552，总体平均方差是：总体平均方差是：（（3）计算新的簇的中心计算新的簇的中心 重复（重复（2）和（）和（3），得到），得到O1分配给分配给C1；；O2分配给分配给C2，，O3分配分配给给C2 ，，O4分配给分配给C2，，O5分配给分配给C1更新，得到新簇更新，得到新簇和和 中心为中心为 ，， 。

单个方差分别为单个方差分别为总体平均误差是：总体平均误差是： 由上可以看出，第一次迭代后，总体平均误差值，显著减小由由上可以看出，第一次迭代后，总体平均误差值，显著减小由于在两次迭代中，簇中心不变，所以停止迭代过程于在两次迭代中，簇中心不变，所以停止迭代过程，算法停止算法停止 Oxy10220031.50450552k k-means-means算法的性能分析算法的性能分析n主要优点：主要优点：u是解决聚类问题的一种经典算法，简单、快速是解决聚类问题的一种经典算法，简单、快速u对处理大数据集，该算法是相对可伸缩和高效率的对处理大数据集，该算法是相对可伸缩和高效率的因为它的复杂度是因为它的复杂度是0 (n k t ) , 其中其中, n 是所有对象的数目是所有对象的数目, k 是簇的数目是簇的数目, t 是迭代的次数通是迭代的次数通常常k <

适用u必须事先给出必须事先给出k k（要生成的簇的数目），而且对初值敏感，对于不同的（要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果初始值，可能会导致不同结果uk-Prototype算法：可以对离散与数值属性两种混合的数据算法：可以对离散与数值属性两种混合的数据进行聚类，在进行聚类，在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-meansk-means算法的改进方法算法的改进方法——k-prototypek-prototype算法算法k-中心点算法：中心点算法：k -means算法对于孤立点是敏感的为算法对于孤立点是敏感的为了解决这个问题，不采用簇中的平均值作为参照点，可以了解决这个问题，不采用簇中的平均值作为参照点，可以选用簇中位置最中心的对象，即中心点作为参照点这样选用簇中位置最中心的对象，即中心点作为参照点这样划分方法仍然是基于最小化所有对象与其参照点之间的相划分方法仍然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的异度之和的原则来执行的 k-meansk-means算法的改进方法算法的改进方法——k-k-中心点算法中心点算法K-means算法在图像分割上的简单应用算法在图像分割上的简单应用例例1：：1.图片：一只遥望大海的小狗；2.此图为100 x 100像素的JPG图片，每个像素可以表示为三维向量（分别对应JPEG图像中的红色、绿色和蓝色通道） ；3.将图片分割为合适的背景区域（三个）和前景区域（小狗）；4.使用K-means算法对图像进行分割9/7/2024在图像分割上的简单应用在图像分割上的简单应用分割后的效果注：最大迭代次数为20次，需运行多次才有可能得到较好的效果。

9/7/2024在图像分割上的简单应用在图像分割上的简单应用例例2：：注：聚类中心个数为5，最大迭代次数为109/7/2024。