关于聚类算法K—means的研究与多种实现

汪美

【摘 要】随着大数据算法的广泛应用与社会反响越来越大、应用领域越来越广泛，随之而来的将是算法的逐步研究优化与多种实现。本文将从聚类算法K-means的理论知识为基准，讨论其优缺点并给出不同实现方式的呈现结果与差异产生的原因。

【关键词】大数据；K-means；R语言

1、K-means聚类算法简介

根据资料表明，聚类可以认为是：一个类簇内的实体是相似的，不同类簇的实体是不相似的；一个类簇是测试空间中点的会聚，同一类簇的任意两个点间的距离小于不同类簇的任意两个点间的距离；类簇可以描述为一个包含密度相对较高的点集的多维空间中的连通区域，它们借助包含密度相对较低的点集的区域与其他区域（类簇）相分离。[1]简而言之，聚类是一个根据某些数据集中程度进行分组的构造过程，将在某些方面相似的数据成员进行分类与组织，聚类技术经常被称为无监督学习。k均值聚类算法是一种著名的聚类算法，因其简单、便捷和高效率的特点令其成为最广泛使用的聚类算法。

k均值聚类算法（k-means clustering algorithm）是一种迭代求解的聚类分析算法，其步骤是随机选取K个对象作为初始的聚类中心，然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。每分配一个样本，聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是没有（或最小数目）对象被重新分配给不同的聚类，没有（或最小数目）聚类中心再发生变化，误差平方和局部最小。

2、K-means的基本思想

K-means算法属于一种经典的聚类算法，一般以欧氏距离作为2 个样本相似程度的评价指标，基本思想如下：

在数据集中任意选择若干个点作为初始聚类中心点，数据集中其他样本到这些数据中心点之间距离，将其归到距离最小的类中，再通过计算得到所有归到各个类中的样本的平均值，然后再更新各个类的中心，直到平方误差准则函数稳定在最小值范围内为止[2]。也就是对于已给定的样本集，根据样本之间的距离差异区分样本集为K个簇，并且让簇内部的点之间尽量紧密连接，而让簇间的距离尽量的变大。K-means算法设计过程.首先，由用户确定所要聚类的准确数目k，并随机选择k个对象 （样本） ，每个对象称为一个种子，代表一个簇 （类） 的均值或中心，对剩余的每个对象，根据其与各簇中心的距离将它赋给最近的簇.然后重新计算每个簇内对象的平均值形成新的聚类中心，这个过程重复进行，直到准则函数收敛为止。[3]

3、K-means的优缺点

3.1优点

K-means算法的原理比较简单，实现也很容易，并且收敛速度快，聚类效果较优，算法的可解释度也比较强。主要需要的参数只有是簇数k。它的计算复杂度也相对低，为O（Nmq），其中N是数据总量，q是迭代次数，m是类别（即k）。一般来讲m、q会比N小很多，那么，此时的复杂度相当于O（N），与其它类似的算法相比算是很小的。当然也就意味着它能够在短时间内处理非常多的数据，这种特点在如今这个数据爆炸的时代是非常重要的。为此，k-means目前仍然被各个企业广泛使用。

3.2缺点

聚类分析是数据挖掘中的重要分支，其原理是根据数据的相似性将数据分配到有差异的类中。聚类分析的应用广泛，为机器学习、人工智能、医学、网络安全等领域提供了重要的技术支持。基于划分的聚类是聚类算法中较为常见的算法，由于其简单高效的特点得到了各领域广泛应用。其中，较为常见的是K-means聚类算法，其实现原理简单，而且算法效率较高。但是由于K-means算法易受限于初始聚类中心，其应用也受到了很多限制。[4]除此之外，K值的选取也不好把握，对于区别步兵师很明显的数据集来说比较难以收敛。如果各隐含类别的数据不平衡、严重失衡或者各类别的方差不同，那么，聚类效果将会不佳。采用迭代方法，得到的结果只是局部最优。此外，对噪音和异常点比较的敏感。分类结果依赖于分类中心的初始化。对类别规模差异大的数据效果不友好。K-means对于距离非常近的类别的分类效果也不好。不适用于categorical的分类。科学家、工程师等也一直在研究不同的方法去克服k-means的缺点。

4、两种实现方式及结果对比展示

对于K-means算法，最先要注意的就是k值的选择。一般来说，我们对k值的选择可以依据对数据的先验经验，如果没有相应的先验经验知识，还可以通过交叉验证选择一个相对合适的k值。在确定了k的个数后，我们需要选择k个初始化的随机质心，这k个初始化质心的位置数据对最后的聚类分析的结果和运行时间的长短以及效率都会有很大的影响，因此需要选择合适的k个质心，这些质心最好不能距离太近。实现过程为：

（a）选择k个聚类中心点作为初始值

（b）分别计算数据点与这k个中心各自的距离，按照最小距离原则将其分配到最邻近聚类

（c）使用每个聚类中的样本均值作为新的聚类中心

（d）重复执行步骤（b）和（c），直到聚类中心收敛，不再发生变化

（e）执行结束，得到k个聚类

根据以上步骤绘制mahout聚类点，以及通过R语言实现聚类点的可视化，结果如图。

从图中可以看到有黑、蓝、绿三种颜色的空心点，这些空心点代表原始的数据。图中的3个红色实点，是R语言kmeans后生成的3个中心。3个紫色实点，是Mahout的kmeans后生成的3个中心。R语言和Mahout生成的点，并不是重合的，原因可能有：距离算法不一样，Mahout中，利用的是 “欧氏距离（EuclideanDistanceMeasure）”，而R语言中，默认是”Hartigan and Wong”。此外，初始化的中心、迭代次数不一样，点合并时，判断的”阈值（threshold）”是不一样的。

5、结语

本文从对K-means聚类算法的理论入手，通过总结、研究并给出本算法的基本思想，并通过图示表示出来。紧接着，作者对K-means算法的优缺点进行了详细的分析与鲜明的对比，本算法虽然存在若干缺点但仍在各个领域充分应用，是因为算法的复杂度低，也就意味著它能够在短时间内处理非常多的数据，这在如今这个大数据时代是非常重要的。本文还提供了mahout聚类点的绘制和通过R语言实现，并介绍了二者得出不同结果的原因，也体现了不同算法只能得出在一定范围内相对正确的结果。

【参考文献】

[1]孙吉贵，刘杰，赵连宇.聚类算法研究[J].软件学报，2008（01）：48-61.

[2]张建辉. K-means 聚类算法研究及应用[D]. 武汉理工大 学， 2007.

[3]杨善林，李永森，胡笑旋，潘若愚.K-MEANS算法中的K值优化问题研究[J].系统工程理论与实践，2006（02）：97-101.

[4]胡威. 一种改进的 K-means 算法在网络入侵检测中的应用研究[D]. 合肥工业大学， 2017.