4.2　数据聚类——K-均值算法

4.2.1　K-均值算法概述

K-均值算法是Mac Queen J.在 1967 年提出来的一种经典的聚类算法。该算法属于基于距离的聚类算法，由于该算法的效率较高，所以在科学和工业领域中，需要对大规模数据进行聚类时被广泛应用，是一种极有影响力的技术。

K-均值算法是先随机选取k个对象作为初始聚类中心。然后计算每个对象与各个初始聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。聚类中心及分配给它们的对象就代表一个聚类。一旦全部对象都被分配了，每个聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件为止。终止条件可以是没有(或最小数目)对象被重新分配给不同的聚类，没有(或最小数目)聚类中心再发生变化，或者误差平方和局部最小。

4.2.2　K-均值算法的主要流程

K-均值算法在进行聚类之前需要用户给定类的个数和数据样本等参数，然后根据特定的算法对数据集进行聚类。当满足收敛条件时，算法处理结束，输出最终的聚类结果。其具体过程如下。

K-均值算法使用的聚类准则函数是误差平方和准则JK。

(4-7)

为了使聚类结果优化，应该使准则JK最小化。

K-均值算法的主要流程为：

输入:初始数据集DATA和类的数目k。

输出:k个类，满足聚类准则函数收敛。

(1)任意选择k个数据对象作为初始聚类中心；

(2)根据类中对象的平均值，将每个对象赋给最类似的类；

(3)更新类的平均值，即计算每个对象类中对象的平均值；

(4)计算聚类准则函数JK，重复进行(2)～(4)；

(5) 直到准则函数JK值不再进行变化(收敛)。

K-均值算法的流程如图4-1所示。

4.2.3　K-均值算法的特点

K-均值算法是一种基于划分的聚类算法，其尝试找出使得聚类准则函数值最小的k个划分，当类与类之间的特征区别比较明显的时候，并且结果类是密集的，K-均值算法聚类结果的效果较好。K-均值算法的优点主要集中在：算法快速、简单;对大数据集有较高的效率并且是可伸缩的;时间复杂度近似于线性，而且适合挖掘大规模数据集。K-均值算法的时间复杂度是O(nkt),其中n代表数据集中对象的数量，t代表着算法迭代的次数，k代表着类的数目。但是，目前为止，K-均值算法也存在着许多缺点，在应用中面临着许多问题，有待于进一步的优化。

(1)K-均值算法的收敛中心随着初始点选取的不同而变化，迄今还没有统一有效的方法来确定初始划分和聚类数目k。

(2)K-均值算法的迭代最优化不能保证收敛到全局最优点。基于随机优化技术的K-均值算法虽然能较好地找到全局最优解，但这是以耗费计算量为代价的。

(3)“均值”的定义将算法限制在只能处理数值变量。而K-中心点算法是一种自然的解决方案，当计算均值没有意义时，中心不需要计算并且总是存在的。

(4)K-均值算法对孤立点和噪声敏感。即使对于一个远离聚类中心的目标，算法也强行将其划分到一个类中，从而扭曲了聚类的形状。

4.2.4　K-均值算法的MATLAB实现

其中，data为要聚类的数据集合，每一行为一个样本；IDX为聚类结果；C为聚类中心；SUMD为每一个样本到该聚类中心的距离和；D为每一个样本到各个聚类中心的距离；K为分类的个数。

如果使用命令[IDX,C,SUMD,D]=kmeans(data,4)进行聚类，要想画出4个聚类的图形，可用如下程序：

为了提高图形的区分度，添加如下命令：

完整的K-均值算法的代码如下：

K-均值算法的聚类仿真结果如图4-2所示。

K-均值算法主要通过迭代搜索获得聚类的划分结果，虽然K-均值算法运算速度快，占用内存小，比较适合大样本量的情况，但是聚类结果受初始聚类点的影响很大，不同的初始聚类点选择会导致截然不同的结果。并且当按最近邻归类时，如果遇到两个聚类点距离相等的情况，那么不同的选择也会造成不同的结果。因此，K-均值算法具有因初始聚类点的不确定性而存在较大偏差的情况。

K-均值算法使用的聚类准则是误差平方和准则。在算法迭代过程中，样本分类不断调整，因此误差平方和JK也在逐步减小，直到没有样本调整为止，此时JK不再变化，聚类达到最优。但是，此算法中没有计算JK值，也就是说JK不是算法结束的明显依据。因此，有待进一步对K-均值算法进行改进，以优化K-均值算法。