K—means算法研究综述

吴进宝

摘 要

K-means算法是硬聚类算法，是典型的基于原型的目标函数聚类方法的代表，它是数据点到原型的某种距离作为优化的目标函数，利用函数求极值的方法得到迭代运算的调整规则。本文主要阐述了K-means的基本算法流程，总结评述了改进的k-means算法的研究现状，以及和经典算法的比较。最后总结了k-means算法存在的一些问题，并指出了改进的方向。

【关键词】K-Means聚类算法 初始聚类中心

K-means聚类算法是由J.B.MacQueen在1967年提出的，之后迅速应用在不同的学科和领域。虽然K-means聚类算法被提出有50多年了，但目前还是被应用最广泛的算法之一。其容易实施、简单、高效的 特征，以及解决无数成功案例，仍然使其依旧是被研究的热点。

本人主要是在研究K-Means基本算法的基础上，总结阐述了改进的K-Means算法。基于向量语义相似度的K-means算法，针对传统的K-Means算法的不足，提出通过向量语义相似度的计算自动确定初始聚类中心，在聚类过程中，达到语义相似度阈值的网页才使用K-Means算法进行聚类；基于初始聚类中心优化的K-means算法，通过数据之间距离，计算密度参数，保留高密度区域，删除低密度区域，找出数据的真实分布。

1 K-Means算法简介

K-means算法，它是一种基于距离远近的聚类算法，同时也是一种无监督学习算法，对以后的算法改进具有很大的影响。该算法的优点是简单易行，容易理解，时间复杂性接近线性，对大规模数据挖掘具有高效性和可伸缩性，在科研以及实际应用中有着很重要的作用。

按照K-means的基本思想，可以将K-means聚类算法描述如下：

步骤：

输入：数据集中的n个数据对象，聚类个数为k；

输出：满足误差平方和准则函数最小的K个聚类；

算法流程：

（1）从n个数据对象中随机选取k个对象作为初始聚类中心；

（2）计算数据集中各个数据对象与聚类中心的距离，并根据最小距离对数据对象进行类群划分；

（3）在形成的子类群中，重新计算每个聚类中所包含的数据对象的平均值作为新的聚类中心；

（4）循环流程（2）到（3）直到前后两次迭代得到的每个类群的中心点不再高于某个阈值为止。

2 K-Means算法改进

2.1 基于向量语义相似度的K-means算法

针对传统的K-Means算法对网页处理的不足，以及其在文本聚类中存在的局限性，提出了基于网页向量语义相似度的改进K-Means算法。新算法通过向量语义相似度的计算确定初始聚类中心，在聚类过程中，达到语义相似度阈值的网页才使用K-Means算法进行聚类。新算法很好地克服了传统K-Means算法随机选取聚类中心以及无法处理语义信息的问题，提高了聚类的质量。

2.2 基于初始聚类中心优化的K-means算法

传统的算法对初始聚类中心特别敏感，聚类结果随不同的初始输入而波动，基于初始聚类中心优化的K-means算法通过计算对象相互之间的距离，产生密度参数，很好的排除了低密度区域的脏数据，从而也优化了传统K-Means算法对脏数据的敏感性。

3 K-means算法的其他改进

在K-means聚类算法中，每个数据点都被唯一的划分到一个类别中，这被称为硬聚类算法，它不易处理聚类不是致密而是壳型的情形。这对这一情况，Dunn等人于1973年提出了模糊K-means聚类算法。Kashima等人于2008年使用L1距离，最终聚类中心是每一类的中位向量。对于一维数据集X={x1，x2，x3，…，xi，…，xn}而言，中位数M比均值对异常数据有较强的抗干扰性，聚类结果受数据中异常值的影响较小。Mao & Jain[4]于1996年提出使用Mahalanobis距离，但计算代价太大。在应用中，Linde等于1980年提出使用Itakura-Saito距离。Banerjee等人2004年提出，如果使用Bregman差异作为距离度量，有许多突出优点，如克服局部最优、类别之间的线性分离、线性时间复杂度等。

4 与经典K-means算法的比较

基于向量语义相似度的K-means算法首先计算网易语义之间的相似度，只有达到一定阈值时，才进行聚类，新算法克服了传统K-Means算法无法处理语义信息的问题，提高了聚类的质量。基于初始聚类中心优化的K-means算法通过对象相互之间的距离，产生密度参数，很好的排出了低密度区域的脏数据，从而也优化了传统K-Means算法对脏数据的敏感性。

5 结束语

对于K-means算法，笔者比较感兴趣的是未来K-means算法对于稀疏数据的处理能力。大家都知道，随着大型互联网公司的发展，以及商品数量的增多，数据对象稀疏问题对聚类过程影响很大，现在已有的处理数据稀疏的技术，比如平均、平滑等，笔者不是很满意。我们可以假设数据对象的属性就好比一个人在不同成长阶段的性格，没必要刻意塑造，而在于它自己丰富。

参考文献

[1] Meng Jianliang， Shang Hai kun，Bian Ling. The application on intrusion detection based on K-means cluster algorithm [C].International Forum on InformationTechnology and Applications，2009：150-152.

[2]孙士保，秦克云.改进的k-Means聚类算法研究[J].计算机工程，2007（07）：200-202.

[3]Dunn JC.A fuzzy relative of the isodata process and itsuse in detecting compact well-separated clusters [J].Journal of Cybernetics，1973（3）：32-57.

[4]Mao J，Jain A K.A self-organizing network for hyper-ellipsoidal clustering.IEEE Transactions on neural net-works，1996（7）：16-29.

作者单位

北京航空航天大学软件学院 北京市 100083endprint