[聚类算法]K-means优缺点及其改进

rustum

写在前：本文参考了国内一些硕士论文以及一些期刊。笔者会在后面写上具体的参考文献。仅供学习，请勿抄袭。
K-means聚类小述

大家接触的第一个聚类方法，十有八九都是K-means聚类啦。该算法十分容易理解，也很容易实现。其实几乎所有的机器学习和数据挖掘算法都有其优点和缺点。那么K-means的缺点是什么呢?
总结为下：
(1)对于离群点和孤立点敏感；
(2)k值选择;
(3)初始聚类中心的选择；
(4)只能发现球状簇。
对于这4点呢的原因，读者可以自行思考下，不难理解。针对上述四个缺点，依次介绍改进措施。
改进1

首先针对（1），对于离群点和孤立点敏感，如何解决？笔者在前面的一篇博客中，提到过离群点检测的LOF算法，通过去除离群点后再聚类，可以减少离群点和孤立点对于聚类效果的影响。
改进2

k值的选择问题，在安徽大学李芳的硕士论文中提到了k-Means算法的k值自适应优化方法。下面将针对该方法进行总结。
首先该算法针对K-means算法的以下主要缺点进行了改进：
1）必须首先给出k（要生成的簇的数目），k值很难选择。事先并不知道给定的数据应该被分成什么类别才是最优的。
2)初始聚类中心的选择是K-means的一个问题。
李芳设计的算法思路是这样的：可以通过在一开始给定一个适合的数值给k，通过一次K-means算法得到一次聚类中心。对于得到的聚类中心，根据得到的k个聚类的距离情况，合并距离最近的类，因此聚类中心数减小，当将其用于下次聚类时，相应的聚类数目也减小了，最终得到合适数目的聚类数。可以通过一个评判值E来确定聚类数得到一个合适的位置停下来，而不继续合并聚类中心。重复上述循环，直至评判函数收敛为止，最终得到较优聚类数的聚类结果。
参考资料

李芳. K-Means算法的k值自适应优化方法研究[D]. 安徽大学, 2015.
改进3

对初始聚类中心的选择的优化。一句话概括为：选择批次距离尽可能远的K个点。具体选择步骤如下。

首先随机选择一个点作为第一个初始类簇中心点，然后选择距离该点最远的那个点作为第二个初始类簇中心点，然后再选择距离前两个点的最近距离最大的点作为第三个初始类簇的中心点，以此类推，直至选出K个初始类簇中心点。

对于该问题还有个解决方案。之前我也使用过。熟悉weka的同学应该知道weka中的聚类有一个算法叫Canopy算法。
选用层次聚类或者Canopy算法进行初始聚类，然后利用这些类簇的中心点作为KMeans算法初始类簇中心点。该方法对于k值的选择也是十分有效的。
点击获取参考资料
改进4

只能获取球状簇的根本原因在于，距离度量的方式。在李荟娆的硕士论文K_means聚类方法的改进及其应用中提到了基于2种测度的改进，改进后，可以去发现非负、类椭圆形的数据。但是对于这一改进，个人认为，并没有很好的解决K-means在这一缺点的问题，如果数据集中有不规则的数据，往往通过基于密度的聚类算法更加适合，比如DESCAN算法。
参考资料

李荟娆. K–means聚类方法的改进及其应用[D]. 东北农业大学, 2014.
笔者水平有限，难免有误，欢迎指出。当然也有其他的更好的方案，可以提出，我也想学习学习。