K-means算法概述

宋庆兰

随着经济、科技的发展产生了大量的数据和爆炸的信息，传统的处理方法已不能高效快速地对这庞大的数据进行分析，云计算和大数据应运而生。当前大数据已经渗透到了人们生活的各个领域，比如：金融行业，医学行业和管理行业等，其中以IT行业最为明显，大数据分析最常用的分析方法就是聚类分析。聚类分析的方法大部分可以应用于所有对象，簇内的对象相似度越高，聚类的效果就越好，聚类算法为了得到改进，试图将相似的对象归入同一簇，不相似的对象归到不同簇。很明显，我们需要一种合适的相似度计算方法，目前已经知道的相似度的计算方法有欧氏距离、余弦距离以及汉明距离等，在应用中要根据实际情况选择合适的相似度计算方法。当然，任何一种算法都存在一定的缺陷，K-means算法也有它的不足之处，但是可以通过一些方法处理后得到更好的聚类结果。

K-means算法

随机从样本数据中输入聚类个数，还有数据库，此数据库包含个数据对象，然后输出满足方差最小标准个聚类，就是K-means算法。K-means算法接受输入量；为了满足所获得的聚类，将个数据对象划分为个聚类：相似度较高的为同一聚类中的对象；而不同聚类中的对象相似度较小。

K-means聚类算法的具体流程：

（1）任意选取个对象作为初始聚类中心；

（2）计算各个对象与中心对象的距离；并根据最小距离对这些对象重新进行划分；

（3）计算那些重新划分的对象；

（4）计算标准测度函数，当满足一定条件时算法终止；否则返回到（2）。

K-means算法的研究现状和发展动态

传统的K-means算法存在的缺点有：对网页处理不足的；在文本聚类中有一定的局限性；中心值的个数难以确定、孤立点和噪声也会有较大影响等。传统K-means算法处理的数据仅限于数值型数据，但在实际生活中，我们要处理并非只有数值型数据，还有可能要处理类属型的数据，甚至是混合属性特征的数据。这时，传统的K-means算法不能够得到有效的结果，K-means算法可以对类属性和混合型属性的对象集进行聚类。

基于初始聚类中心优化的K-means算法，主要是通过计算对象相互之间的距离产生密度参数，非常好地优化了传统K-means算法的缺点。K-means动态聚类算法也考虑到聚类过程中的信息变化，在数据量庞大的情况下，通过假定终止条件来减少迭代次数，降低时间复杂度，删除冗余信息来减少聚类过程中的干扰等方法，K-means动态聚类算法聚类效果得到一定的提高，这就是传统K-means算法和K-means动态聚类算法的区别。此外，为了可以获得数据的基本情况，聚类分析被作为其他算法的预处理步骤，利用聚类对数据进行预处理，在此基础上，要想获得更深层次的、更有用的信息，還要进行特征抽取或分类以提高精确度和挖掘效率，或者对聚类结果做进一步分析，这也更加适应现代社会的需要。

针对K-means算法存在受初始值影响大的缺点，本文提出了一种新的K-means++算法。

K-means++算法的改进在于初始聚类中心的选择。K-means++算法选取初始聚类中心时，按照聚类中心之间的距离尽可能远的原则，选择个初始聚类中心。K-means++算法选择初始聚类中心的主要思想是：假如已经选择了（0< <）个初始聚类中心；再选择第+1个聚类中心时，距离个聚类中心越远的对象，越有可能被选作第1个聚类中心。

经过研究表明，虽然足够多的实验次数和足够大的迭代次数，都能使K-means算法和K-means++算法收敛至全局最小值，但K-means++算法的收敛速度更快、效果更好。也证明改进后的K-means++算法降低了初始聚类中心对K-means影响，提高了算法的效率和准确性。

本文主要对K-means算法的研究现状和发展状态进行了阐述，并分析了聚类算法中比较有代表性的K-means算法；如何对K-means算法的缺点进行改进；K-means算法的精简优化；以及如何选择合适的初始聚类中心，以减少初始值对K-means算法的影响，从而提高算法效率。