4.2 数据聚类——K均值聚类
4.2.1 K均值聚类简介
K均值聚类发明于1956年，该算法最常见的形式是采用被称为劳埃得算法（Lloyd algorithm）的迭代式改进探索法。劳埃得算法首先把输入点分至K个初始化分组，可以使用随机或者一些启发式数据，然后计算每组的中心点，根据中心点的位置把样本分到离它最近的中心，重新确定分组，再继续重复不断地计算中心并重新分组，直到收敛，即样本不再改变分组（中心点位置不再改变）。
4.2.2 K均值聚类原理
动态聚类方法是模式识别中一种普遍采用的方法，它具有以下3个要点：
（1）选定某种距离度量作为样本间的相似性度量。
（2）确定某个评价聚类结果质量的准则函数。
（3）给定某个初始分类，然后用迭代算法找出使准则函数取极值的最好的聚类结果。
K均值算法是基于质心的技术，K均值算法以K为输入参数，把n个对象集合分为K个簇，使得簇内的相似度高，簇之间的相似度低。簇的相似度是关于簇中对象的均值度量，可以看作是簇的质心。
K均值聚类算法使用的聚类准则函数是误差平方和准则JK
为了使聚类结果优化，应该使准则JK最小化。
（1）给出n个混合样本，令I=1，表示迭代次数，选取K个初始聚合中心Zj（I），j=1，2，…，K。
（2）计算每个样本与聚合中心的距离D［xk，Zj（I）］（k=1，2，…，n；j=1，2，…，K）。
若
，则xk∈ωi。
（3）计算K个新的集合中心：
）。
（4）判断：若Zj（I+1）≠Zj（I）（j=1，2，…，K），则I=I+1，返回（2）；否则，算法结束。
K均值算法的执行过程如图4-1所示。
图4-1 K均值聚类算法执行过程
接下来介绍初始分类的选取和调整的方法。
（1）代表点也就是聚类中心。选取一批代表点，计算其他样本到聚类中心的距离，把所有样本归于最近的聚类中心点，形成初始分类，再重新计算各聚类中心，称为成批处理法（本书采用此法）。
（2）选取一批代表点后，依次计算其他样本的归类。当计算完第1个样本时，把它归于最近的一类，形成新的分类。然后计算新的聚类中心，再计算第2个样本到新的聚类中心的距离，对第2个样本进行归类，即每个样本的归类都改变1次聚类中心。此法称为逐个处理法。
（3）直接用样本进行初始分类，先规定距离d，把第1个样本作为第一类的聚类中心。考察第2个样本，若第2个样本距第一个聚类中心的距离小于d，就把第2个样本归于第一类；否则，第2个样本就成为第二类的聚类中心。再考虑其他样本，根据样本到聚类中心的距离大于还是小于d，决定是分裂还是合并。
（4）最佳初始分类。
如图4-2所示，随着初始分类K的增大，准则函数下降很快，经过拐点A后，下降速度减慢。拐点A就是最佳初始分类。
图4-2 最佳初始分类
4.2.3 K均值算法的优缺点
K均值聚类算法在实际生活中非常实用，也非常方便，它不仅能够使得烦琐的数据在计算当中简单化，而且使用范围也比较广。例如，它在对交通事故多发地带的分析方面尤为突出。下面是关于K均值算法的几个优点：
（1）如果变量很大，K均值比层次聚类的计算速度更快。
（2）与层次聚类相比，K均值可以得到更紧密的簇，尤其是对于球状簇。
（3）大数据集合，效率比较高。
（4）算法尝试找出使平方误差函数最小的K个划分。当结果簇是密集的，而簇与簇之间区别明显的时候，效果较好。
任何事情都不是完美的，虽然K均值算法在实际生活中非常实用，但是它也有不足的一面。下面是关于K均值算法的几点不足：
（1）没有指明初始化均值的方法。常用的方法是随机地选取K个样本作为均值。
（2）产生的结果依赖于均值的初始值，经常发生得到次优划分的情况。解决方法是多次尝试不同的初始值。
（3）可能发生距离簇中心mj最近的样本集为空的情况，因此mj将得不到更新。
（4）不适合发现非凸面形状的簇，并且对噪声和离群点数据是比较敏感的，因为少量的这类数据能够对均值产生极大的影响。
4.2.4 K均值聚类的MATLAB实现
以表1-2所示的样本数据为例，说明K均值聚类的MATLAB实现。其中，前29组数据已确定类别；后30组数据为待确定类别。
在MATLAB中，直接调用如下程序即可实现K均值聚类。
其中，data：要聚类的数据集合，每一行为一个样本；IDX：聚类结果；C：聚类中心；SUMD：每一个样本到该聚类中心的距离和；D：每一个样本到各个聚类中心的距离；K：分类的个数。
如果使用命令［IDX, C, SUMD, D］=kmeans（data, 4）进行聚类，要想画出4个聚类的图形，可用如下程序代码：
为了提高图形的区分度，添加如下命令：
（1）初始分类的选取和调整。
K均值算法的类型数目假定已知为K。对于K未知时，可以令K逐渐增加。使用K均值算法，误差平方和JK随K的增加而单调减少。最初，由于K较小，类型的分裂会使JK迅速减小，但当K增加到一定数值时，JK的减小速度会减慢，即随着初始分类K的增大，准则函数下降很快，经过拐点后，下降速度减慢。拐点处的K值就是最佳初始分类。
（2）当分类的数目K=2时，调用如下程序实现K均值聚类：
（3）当分类的数目K=3时，调用如下程序实现K均值聚类：
（4）当分类的数目K=4时，调用如下程序实现K均值聚类：
（5）当分类的数目K=5时，调用如下程序实现K均值聚类：
（6）当分类的数目K=6时，调用如下程序实现K均值聚类：
（7）当分类的数目K=7时，调用如下程序实现K均值聚类：
如图4-3所示，随着初始分类K的增大，准则函数下降很快，经过拐点后，下降速度减慢。拐点就是最佳初始分类，即K=4时为最佳初始分类。
图4-3 最佳初始分类图
完整分类的MATLAB源程序代码如下：
4.2.5 待聚类样本的分类结果
待聚类样本按下述步骤分类。
（1）所分4类的聚类中心C，实现代码如下：
（2）所分的4类，实现代码如下：
执行上述代码后，待分类样本K均值聚类MATLAB分类图界面如图4-4所示。
图4-4 待分类样本K均值聚类MATLAB分类图界面
4.2.6 结论
对30个样本进行分类的MATLAB程序代码运行结果如下：
其中，D为每个样本与聚合中心的最小距离。
分类结果如下：
通过对分类结果的验证表明，该算法能很好地对样本进行分类。使用该算法得到的结果显示全部样本分类结果与正确样本的分类结果完全符合。
在K均值聚类算法中，Kmeans算法主要通过迭代搜索获得聚类的划分结果。虽然Kmeans算法运算速度快，占用内存小，比较适合于大样本量的情况，但是聚类结果受初始凝聚点的影响很大，不同的初始点选择会导致截然不同的结果。并且当按最近邻归类时，如果遇到与两个聚类中心距离相等的情况，不同的选择也会造成不同的结果。因此，K均值动态聚类法具有因初始聚类中心的不确定性而存在较大偏差的情况。
K均值算法使用的聚类准则函数是误差平方和准则。在算法迭代过程中，样本分类不断调整，因此误差平方和JK也在逐步减小，直到没有样本调整为止，此时JK不再变化，聚类达到最优。但是，此算法中没有计算JK值，也就是说JK不是算法结束的明显依据。因此，有待进一步对K均值算法进行改进，以优化K均值聚类算法。