K-means算法及在图像分割中的简单应用

1、1主要内容算法简介算法简介算法要点算法要点实例实例性能分析性能分析算法改进算法改进在图像分割中的简单应用在图像分割中的简单应用2算法简介k-means算法：一种得到最广泛使用的聚类算法算法：一种得到最广泛使用的聚类算法 算法的主要思想：算法的主要思想：u将各个聚类子集内的所有数据样本的均值作为该将各个聚类子集内的所有数据样本的均值作为该聚类的代表点聚类的代表点u通过迭代过程把数据集划分为不同的类别通过迭代过程把数据集划分为不同的类别u使得评价聚类性能的准则函数达到最优，从而使使得评价聚类性能的准则函数达到最优，从而使生成的每个聚类内紧凑，类间独立。生成的每个聚类内紧凑，类间独立。使用范围：不适

2、合处理离散型属性，但是对于使用范围：不适合处理离散型属性，但是对于连连续型续型具有较好的聚类效果。具有较好的聚类效果。3 k-means算法算法输入：簇的数目输入：簇的数目k和包含和包含n个对象的数据库。个对象的数据库。输出：输出：k个簇，使平方误差准则最小。个簇，使平方误差准则最小。算法步骤：算法步骤： 1.为每个聚类确定一个初始聚类中心，这样就有为每个聚类确定一个初始聚类中心，这样就有K 个初始聚类中心。个初始聚类中心。 2.将样本集中的样本按照最小距离原则分配到最将样本集中的样本按照最小距离原则分配到最邻近聚类邻近聚类 3.使用每个聚类中的样本均值作为新的聚类中心。使用每个聚类中的样本均

3、值作为新的聚类中心。 4.重复步骤重复步骤2.3直到聚类中心不再变化。直到聚类中心不再变化。 5.结束，得到结束，得到K个聚类个聚类4 将样本分配给距离它们最近的中心向量，并使将样本分配给距离它们最近的中心向量，并使目标函数值减小目标函数值减小21,.,2,1|min jniikjpxiCxiixCx1更新簇平均值更新簇平均值21 kiCxiixxE计算准则函数计算准则函数E5算法要点1 1）选定某种距离作为数据样本间的相似性度量）选定某种距离作为数据样本间的相似性度量 在计算数据样本之间的距离时，可以根据实际在计算数据样本之间的距离时，可以根据实际需要选择欧式距离、曼哈顿距离或者明考斯距离需

4、要选择欧式距离、曼哈顿距离或者明考斯距离中的一种来作为算法的相似性度量，其中最常用中的一种来作为算法的相似性度量，其中最常用的是的是欧式距离欧式距离。6dkjkikjixxxxd12,距离越小，样本距离越小，样本x xi i和和x xj j越相似，差异度越小；越相似，差异度越小；距离越大，样本距离越大，样本x xi i和和x xj j越不相似，差异度越大。越不相似，差异度越大。（2 2）选择评价聚类性能的准则函数）选择评价聚类性能的准则函数: :误差平方和准则函数误差平方和准则函数 给定数据集给定数据集X X，假设，假设X X包含包含k k个聚类子集个聚类子集X X1 1,X,X2 2,X,X

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

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

7、近离，将它赋给最近的类。的类。 对对 ： 显然显然 ，故将故将 分配给分配给3132,OMdOMd2 , 01O0 , 02O2 , 011OM0 , 022 OM5 . 2025 . 10,2231OMd5 . 1005 . 10,2232OMd3O3O2C例子例子9 对于对于 ： 因为因为 ，所以将，所以将 分配给分配给 对于对于 ：因为因为 ，所以将，所以将 分配给分配给更新，得到新类更新，得到新类 和和计算平方误差准则，单个方差为计算平方误差准则，单个方差为4O2214,052029d MO2224,05005dMO2414,d MOd MO4O2c5O2215,05225dMO222

8、5,050229dMO1525,d M Od MO5O1C511,OOC 252250220022221E25.272E2234,CO O OOxy10220031.504505522 , 011OM0 , 022OM10，。总体平均方差是：总体平均方差是：（3）计算新）计算新的聚类的的聚类的中心。中心。 25.5225.272521EEE 2 , 5 . 2222, 2501M0 ,17. 23000, 355 . 102M重复（重复（2）和（）和（3），得到），得到O1分配给分配给C1；O2分配给分配给C2，O3分配给分配给C2 ，O4分配给分配给C2，O5分配给分配给C1。更新，得到。更

9、新，得到新类新类和和 。 中心为中心为 ， 。单个方差分别为单个方差分别为511,OOC 4322,OOOC 2 , 5 . 21M0 ,17. 22M5 .122255 . 2225 . 2022221E15.132E总体平均误差是：总体平均误差是： 65.2515.135 .1221EEE由上可以看出，第一次迭代后，总体平均误差值由上可以看出，第一次迭代后，总体平均误差值52.2552.25降到降到25.6525.65，显著减小。由于显著减小。由于在这次在这次迭代中迭代中，类中心，类中心不变，所以停止迭代过程不变，所以停止迭代过程，算法停止算法停止。 Oxy10220031.5045055

10、211性能分析性能分析n主要优点：主要优点：u是解决聚类问题的一种经典算法，简单、快速。是解决聚类问题的一种经典算法，简单、快速。u对处理大数据集，该算法是相对可伸缩和高效率的。对处理大数据集，该算法是相对可伸缩和高效率的。u当结果类是密集的，而类与类之间区别明显时当结果类是密集的，而类与类之间区别明显时, , 它的它的效果较好。效果较好。n主要缺点主要缺点u在类的平均值被定义的情况下才能使用，在类的平均值被定义的情况下才能使用，这对于处理这对于处理符号属性的数据不适用。符号属性的数据不适用。u必须事先给出必须事先给出k k（要生成的类的数目），而且对初值（要生成的类的数目），而且对初值敏感，

11、对于不同的初始值，可能会导致不同结果。敏感，对于不同的初始值，可能会导致不同结果。u它对于它对于“躁声躁声”和孤立点数据是敏感的，和孤立点数据是敏感的，少量的该类少量的该类数据能够对平均值产生极大的影响。数据能够对平均值产生极大的影响。12针对K-means算法缺点的改进方法1.1.对于不同的初始值，可能会导致不同结果：多设置对于不同的初始值，可能会导致不同结果：多设置一些不同的初值，但比较耗时和浪费资源。一些不同的初值，但比较耗时和浪费资源。2.分类数目分类数目K不确定：通过类的自动合并和分裂，得不确定：通过类的自动合并和分裂，得到较为合理的类型数目到较为合理的类型数目K，例如，例如ISOD

12、ATA算法。相同算法。相同点：聚类中心都是通过样本均值的迭代运算来决定的；点：聚类中心都是通过样本均值的迭代运算来决定的；不同点：主要是在选代过程中可将一类一分为二，亦不同点：主要是在选代过程中可将一类一分为二，亦可能二类合二为一，即可能二类合二为一，即“自组织自组织”，这种算法具有启，这种算法具有启发式的特点。发式的特点。由于算法有自我调整的能力，因而需要设置若干个控由于算法有自我调整的能力，因而需要设置若干个控制用参数，如聚类数期望值制用参数，如聚类数期望值K、最小类内样本数、类、最小类内样本数、类间中心距离参数、每次迭代允许合并的最大聚类对数间中心距离参数、每次迭代允许合并的最大聚类对数

13、L及允许迭代次数及允许迭代次数I等。等。13k-k- center center算法：解决算法：解决k -means算法对于孤立点是算法对于孤立点是敏感敏感的问题的问题l 不不采用簇中的平均值作为参照点，可以采用簇中的平均值作为参照点，可以选用类选用类中中位置最中心的对象，即中心点作为参照点位置最中心的对象，即中心点作为参照点。l划分划分方法仍然是基于方法仍然是基于最小化最小化所有对象与其参照所有对象与其参照点之间的相异度之和的原则来执行的。点之间的相异度之和的原则来执行的。 k-meansk-means算法的改进方法算法的改进方法k-k- center center算法算法14uk-mode

14、s 算法：实现对算法：实现对离散数据离散数据的快速的快速聚类，处理聚类，处理分类属性型数据，例如：姓名、性别、年龄等。分类属性型数据，例如：姓名、性别、年龄等。u采用差异度采用差异度D来代替来代替k-means算法中的距离，差异算法中的距离，差异度越小，则表示距离越小。一个样本和一个聚类中心度越小，则表示距离越小。一个样本和一个聚类中心的差异度就是它们各个属性不相同的个数，的差异度就是它们各个属性不相同的个数，属性属性相同相同为为0，不同为不同为1，并计算，并计算1的总和。的总和。因此因此D越大，即他的越大，即他的不相关程度越不相关程度越强。强。k-meansk-means算法的改进方法算法的改进方法k-mode k-mode s s算法算法1516K-meansK-mea