人工智能算法与实践-第11章 K-Means算法

11.4算法总结11.1算法概述11.2算法原理11.3算法案例目录第十一章K-Means算法人工智能算法与实践—1

—

01算法概述PartTHREE—2

—

K-Means算法是一种基于距离的聚类算法。因为该算法具有分类速度快、分类准确率高等优点，至今仍有许多人使用和改进它，K-Means算法在聚类算法中始终占据着非常重要的地位。K-Means算法是一种聚类算法。提到聚类，首先想到的是一个与之相似的概念，那就是分类。那么分类和聚类是否为同一个概念呢？答案显然是否定的。聚类是指事先没有“标签”而通过某种分析找出事物之间存在聚集性原因的过程，而分类是按照某种标准给对象贴标签，再根据标签来区分归类。通俗地讲，聚类就是将相似的事物放在一起，而分类更像是给事物分配标签。11.1算法概述—3

—

11.1算法概述—4

—

分类和聚类的区别02算法原理PartTWO—5

—

K-Means算法中的K代表的是K个簇，Means意为均值，即代表着每个簇中都选取各个数据的均值作为该簇的质心，代表着整个簇。该算法的思想就是输入簇数K和包含n个数据对象的数据集，最终输出结果为K个簇，每个簇都满足方差最小标准。划分后的每个簇内各个数据的相似性较高，而不同簇的各个数据之间的相似性较低。算法的定义如下：给定样本集D={x1,x2,…,xi,…,xn}，xi代表一个数据样本，其中每个数据样本由m个属性构成。聚类就是为了将所有样本集划分为一定数量的簇，簇用字母G表示，簇的个数用K表示。每个簇都有一个中心点即质心，用μk表示。因此K-Means算法的原理就是将D={x1,x2,...xi,…,xn}通过聚类划分为G={G1,G2,…,Gu,…,Gk}的过程。11.2算法原理—6

—

误差平方和（SumofSquaredError,SSE）是簇内样本相似性大小的代表，划分好的某个簇Gu的误差平方和越小，说明该簇内的样本相似性越大；相反，Gu的误差平方和越大，说明该簇内的样本相似性越小。误差平方和的计算公式如下：评价指标—7

—

11.2算法原理（1）选择合适的K值。（2）在样本集D中随机地选择K个数据点，作为K个簇各自的质心。（3）计算D中每个样本到步骤（2）中选取的各个质心的距离，选出每个样本和所有质心的距离中的最小值，并将该样本归类到该质心所代表的簇中去。（4）根据步骤（3）中所得的聚类结果，重新计算K个簇各自的质心，计算方法是计算每个簇中所有元素的平均值。（5）比较前后两次SSE的差值和设定的阈值，若大于阈值，则重复步骤（3）和步骤（4）。（6）如果前后两次的SSE的差值小于设定的阈值，则说明聚类完成。算法流程—8

—

11.2算法原理K值的选取—9

—

1经验法根据经验选择代表点，然后根据问题的性质和数值的分布以直观的方式寻找较为合适的K值。2手肘法手肘法的核心指标就是SSE的值，思想就是逐步增大K的值，每个簇内的聚合程度也会大幅度增加，即SSE的值会大幅度减少。当K值逐渐取接近合适的值时，SSE值的减小幅度会越来越小，逐渐趋于平缓。11.2算法原理质心的选择—10

—

1随机法多次运行，每次运行都使用一组不同的随机样本作为初始质心，然后选择具有最小SSE值的簇集。2层次聚类法取一个样本，并使用层次聚类方法对其进行聚类。从层次聚类中提取K个簇，并用这些簇的质心作为初始的质心。3取最远点法取所有点的质心作为第一个质心。然后，每个后继质心都选择离已经选择过的初始质心最远的点。11.2算法原理距离的选择—11

—

1欧式距离2曼哈顿距离3余弦相似度11.2算法原理03算法案例PartTHREE—12

—

数据集的选择—13

—

本实验采用的数据集来自Python的sklearn包中自带的Iris数据集。Iris数据集是常用的分类实验数据集，由Fisher，1936收集整理。Iris也称鸢尾花卉数据集，是一类多重变量分析的数据集。数据集包含150个数据样本，分为3类，每类50个数据，每个数据包含4个属性。可通过花萼长度、花萼宽度、花瓣长度、花瓣宽度4个属性预测鸢尾花卉属于3个种类（Setosa、Versicolour、Virginica）中的哪一类。11.3算法案例核心代码—14

—

11.3算法案例1.计算距离（距离通常使用欧几里得距离）2.初始化质心3．K-Means算法实现过程—15

—

观察图11-6可以看到聚类效果明显。当聚类效果不佳时，可以通过改变K值的选取方式，如手肘法、轮廓系数法等，或者改变初始质心的选择方式来使聚类效果更佳，也可以使用二分K-Means聚类算法来加强聚类效果11.3算法案例04算法总结PartFOUR—16

—

11.4算法总结—17

—

K-Means算法有着原理简单、容易实现、分类速度快和分类准确率高等优点，但同时该算法也有如下缺点。（1）K值很难确定。通常需要靠经验来估计一个大概的K值，K值的选择直接决定了聚类的结果。（2）对噪声和异常点敏感。K-Means算法很容易受到噪声以及孤立点的影响，导致下一