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

2.13.2Thek-MeansAlgorithm(K-均值聚类算法）主讲内容算法性能分析算法改进算法简介算法应用算法要点算法描述算法实例ISODATA算法gapstatistics算法简介•k-means算法，也被称为k-平均或k-均值，是一种得到最广泛使用的聚类算法。它是将各个聚类子集内的所有数据样本的均值作为该聚类的代表点，算法的主要思想是通过迭代过程把数据集划分为不同的类别，使得评价聚类性能的准则函数达到最优，从而使生成的每个聚类内紧凑，类间独立。这一算法不适合处理离散型属性，但是对于连续型具有较好的聚类效果。•算法描述1.为中心向量c1,c2,…,ck初始化k个种子2.分组:将样本分配给距离其最近的中心向量由这些样本构造不相交（non-overlapping）的聚类3.确定中心:用各个聚类的中心向量作为新的中心4.重复分组和确定中心的步骤，直至算法收敛算法k-means算法输入：簇的数目k和包含n个对象的数据库。输出：k个簇，使平方误差准则最小。算法步骤：1.为每个聚类确定一个初始聚类中心，这样就有K个初始聚类中心。2.将样本集中的样本按照最小距离原则分配到最邻近聚类3.使用每个聚类中的样本均值作为新的聚类中心。4.重复步骤2.3直到聚类中心不再变化。5.结束，得到K个聚类2020/11/23将样本分配给距离它们最近的中心向量，并使目标函数值减小21},...,2,1{||||minjniikjpxiCxiixCx1更新簇平均值21kiCxiixxE计算准则函数EK-means聚类算法划分聚类方法对数据集进行聚类时包括如下三个要点：•（1）选定某种距离作为数据样本间的相似性度量上面讲到，k-means聚类算法不适合处理离散型属性，对连续型属性比较适合。因此在计算数据样本之间的距离时，可以根据实际需要选择欧式距离、曼哈顿距离或者明考斯距离中的一种来作为算法的相似性度量，其中最常用的是欧式距离。下面我给大家具体介绍一下欧式距离。假设给定的数据集，X中的样本用d个描述属性A1,A2…Ad来表示，并且d个描述属性都是连续型属性。数据样本xi=(xi1,xi2,…xid),xj=(xj1,xj2,…xjd)其中，xi1,xi2,…xid和xj1,xj2,…xjd分别是样本xi和xj对应d个描述属性A1,A2,…Ad的具体取值。样本xi和xj之间的相似度通常用它们之间的距离d(xi,xj)来表示，距离越小，样本xi和xj越相似，差异度越小；距离越大，样本xi和xj越不相似，差异度越大。欧式距离公式如下：dkjkikjixxxxd12,totalmxXm,...,2,1|•（2）选择评价聚类性能的准则函数k-means聚类算法使用误差平方和准则函数来评价聚类性能。给定数据集X，其中只包含描述属性，不包含类别属性。假设X包含k个聚类子集X1,X2,…XK；各个聚类子集中的样本数量分别为n1，n2,…,nk;各个聚类子集的均值代表点（也称聚类中心）分别为m1，m2,…,mk。则误差平方和准则函数公式为：21kiXpiimpE•（3）相似度的计算根据一个簇中对象的平均值来进行。•（1）将所有对象随机分配到k个非空的簇中。•（2）计算每个簇的平均值，并用该平均值代表相应的簇。•（3）根据每个对象与各个簇中心的距离，分配给最近的簇。•（4）然后转（2），重新计算每个簇的平均值。这个过程不断重复直到满足某个准则函数才停止。Oxy10220031.50450552数据对象集合S见表1，作为一个聚类分析的二维样本，要求的簇的数量k=2。(1)选择，为初始的簇中心，即，。(2)对剩余的每个对象，根据其与各个簇中心的距离，将它赋给最近的簇。对：显然，故将分配给2,01O0,02O2,011OM0,022OM5.2025.10,2231OMd5.1005.10,2232OMd3132,,OMdOMd3O3O2C例子•对于：•因为所以将分配给•对于：•因为所以将分配给•更新，得到新簇和•计算平方误差准则，单个方差为4O2214,052029dMO2224,05005dMO2414,,dMOdMO4O2c5O2215,05225dMO2225,050229dMO1525,,dMOdMO5O1C511,OOC252250220022221E25.272E2234,,COOOOxy10220031.504505522,011OM0,022OM，。总体平均方差是：（3）计算新的簇的中心。25.5225.272521EEE2,5.2222,2501M0,17.23000,355.102M重复（2）和（3），得到O1分配给C1；O2分配给C2，O3分配给C2，O4分配给C2，O5分配给C1。更新，得到新簇和。中心为，。单个方差分别为511,OOC4322,,OOOC2,5.21M0,17.22M5.122255.2225.2022221E15.132E总体平均误差是：65.2515.135.1221EEE由上可以看出，第一次迭代后，总体平均误差值52.25~25.65，显著减小。由于在两次迭代中，簇中心不变，所以停止迭代过程，算法停止。Oxy10220031.50450552k-means算法的性能分析主要优点：是解决聚类问题的一种经典算法，简单、快速。对处理大数据集，该算法是相对可伸缩和高效率的。因为它的复杂度是0(nkt),其中,n是所有对象的数目,k是簇的数目,t是迭代的次数。通常kn且tn。当结果簇是密集的，而簇与簇之间区别明显时,它的效果较好。主要缺点在簇的平均值被定义的情况下才能使用，这对于处理符号属性的数据不适用。必须事先给出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）重新进行迭代运算，计算各项指标，判断聚类结果是否符合要求。经过多次迭代后，若结果收敛，则运算结束。2020/11/23初始中心的选取对算法的影响•棋盘格数据集(Checkerboarddataset)–仅使用其中486个正类数据，并将数据变换到[-1,1]之间，分布情况如下图所示：-1-0.500.51-1-0.500.512020/11/23初始中心的选取对算法的影响•初始聚类中心均在中心附近-1-0.500.51-1-0.500.51PointsInitialCentersClusterCenters2020/11/23初始中心的选取对算法的影响•初始聚类中心在平面内随机选取-1-0.500.51-1-0.500.51PointsInitialCentersClusterCenters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-中心点算法2020/11/23K-means算法在图像分割上的简单应用例1：1.图片：一只遥望大海的小狗；2.此图为100x100像素的JPG图片，每个像素可以表示为三维向量（分别对应JPEG图像中的红色、绿色和蓝色通道）；3.将图片分割为合适的背景区域（三个）和前景区域（小狗）；4.使用K-means算法对图像进行分割。2020/11/23在图像分割上的简单应用分割后的效果注：最大迭代次数为20次，需运行多次才有可能得到较好的效果。2020/11/23在图像分割上的简单应用例2：注：聚类中心个数为5，最大迭代次数为10。2020/11/23Matlab程序实现clcclearticRGB=imread('test5.jpg');%读入像img=rgb2gray(RGB);[m,n]=size(img);subplot(2,2,1),imshow(img);title('图一原图像')subplot(2,2,2),imhist(img);title('