K-means聚类算法研究浅析

苏州高等职业技术学校 李志伟

K-means聚类算法研究浅析

苏州高等职业技术学校 李志伟

K-means算法是聚类方法中使用度较高的一种划分方法，具有明显的特点及使用优势。本文主要对K-means算法工作原理及实现的一般步骤进行简介，并分析算法的特点、优缺点。希望能够在清楚算法思想基础上，能够对其进行针对性学习、研究和改进。

K-means；聚类

1.简介

K-means算法于1967年由J.B. Mac Queen提出，在聚类分析广泛使用。该算法是一种典型的基于距离划分的聚类算法，它使用距离的评价指标作为样本的相似性度量。K-means算法求解对应某一初始聚类中心向量最优分类使得评价指标最小，距离越近其相似度越大。且该算法利用目标函数求极值的方法作为迭代运算的调整规则。它采用误差平方和准则函数作为聚类准则函数。K-means算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。它把n个对象根据他们的属性分为k个聚类，以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。

然而初始类聚类中心的选取对聚类结果影响很大，原因在于实现算法的第一步是随机选取k个对象作为初始聚类的中心，这些初始中心象征性地代表了各个簇。K-means算法的每次迭代都要对数据集中剩余的每个对象重新判归至最近的簇。当数据集中所有数据对象都有自己的归属簇（或类），一次迭代运算就算完成，而新的聚类中心将会被再次计算出来。如果在一次迭代前后，聚类结果不再发生变化，说明算法已经收敛。

到目前为止，K-means算法在科学和工业应用中影响很大。它广泛应用于模式识别、图像处理、机器学习、数据解压缩等领域。除此之外，goole、百度、搜狗等搜索引擎及校内的一些数据库进行相关内容的检索算法也是使用的K-means算法。

2.K-means算法原理及流程

K-means算法的工作原理：首先从n个数据对象（或数据集）中任意选取 k个点作为初始聚类中心，然后计算各个样本到这k个聚类中心的距离得出相似度，将各样本点归化到离它最近（或最相似）的聚类中心所在的类。最后，计算新形成每个类的数据对象的平均值来得到新的聚类中心，如果相邻两次的聚类中心没有任何变化，说明样本调整结束，聚类准则函数已经收敛。不断重复这一过程直到标准测度函数收敛为止。值得说明的是一般采用均方差作为标准测度函数。本算法的一个特点是在每次迭代中都要考察每个样本的分类情况是否有变化。若前后没有发生改变，就需要继续调整，待全部样本调整完之后，再修改聚类中心，进入下一轮迭代。使得最终得到的k个聚类类内紧凑，类间尽可能分散的目的。具体来讲，K-means聚类算法实现的一般步骤如下：（1）选取初始聚类中心：从待划分数据集中任意选择得出；（2）计算距离得出相似度：根据每个聚类对象的均值，及距离，归判类属划分；（3）重新计算尚有变化聚类的均值；（4）循环第（2）-（3）步直到各聚类不再发生变化完成聚类。

由此可知，K-means 算法的输入量是k，输出的是满足方差最小标准的k个聚类。然而在将数据对象进行聚类的时候，需满足条件：类内相似度越高越好；类间相似度则越低越好；而聚类的相似度是利用各聚类的中心对象的均值所获得一个中心点（或称引力中心）来进行计算的。尽管K-means算法过程比较简单，但算法中求点群中心的公式对聚类来讲很重要。一般来说，可以使用 X/Y坐标的平均值来计算，也可以用欧氏距离、曼哈顿距离、切比雪夫距离、闵可夫斯基距离、标准化欧氏距离、夹角余弦、相关系数或相关距离中的一种来求。

3.K-means算法优缺点分析

由于K-means聚类算法是一种自下而上的聚类方法，通过原理及实现方法不难得知算法本身的特点和优缺点。首先其特点是：（1）指定聚类，即确定聚类数目条件下，将数据 对象归化至某一个聚类，使得它与这个聚类中心的距离比它到其它聚类中心的距离要近；（2）选定某种距离度量作为样本（或对象）间的相似性度量；（3）动态修改聚类中心。在确定评价聚类结果质量的好坏的准则函数下，用迭代算法找出使准则函数取极值的最好的聚类结果。

K-Means算法的优点主要表现出：（1）是一种解决聚类问题的经典算法，具有实现简单、计算速度快的优点；（2）对大数据集表现出较高的实现效率，且伸缩性好；（3）时间复杂度为O（nkt），接近于线性，适合大规模数据集。其中n代表数据集中对象的数量或个数，t代表着算法迭代次数，k代表聚类数目。一般来说，k＜＜n，t＜＜n 。（4）.k个聚类划分具有平方误差最小的特点。算法适用于用密集型数据集，且类间区别明显时的情况。

K-means算法的缺陷主要表现为：（1）聚类数目或聚类中心个数k需要事先给定，但在实际中k 值的选定是非常难以估计的，很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。这对本条缺陷，可以选择hierarchical或mean shift算法聚类。（2）聚类结果对初值敏感，不同的初始聚类中心可能导致完全不同的聚类结果。初值选择不好，可能得不到满意理想的聚类结果。有的时候挑选优化的初值，不仅耗时而且浪费系统资源。对本条缺陷可以使用K-means++算法来改善。（3）在聚类的平均值被定义的情况下才能使用。对于符号属性数据集不适用。另外，算法对含有“噪声”和孤立点的数据集敏感。

4.结束语

K-means算法作为一种使用度较高的划分方法，广泛应用于数据挖掘、机器学习和模式识别领域中。本文简要介绍K-means算法实现原理及流程，并小结其特点和优缺点。目前，针对K-means算法的缺点先后提出多种改进算法，这将是我们以后研究的方向。