十大经典算法（六）

七、K-means K均值（无监督算法，聚类算法，随机算法）

原理：将n个样本分为k个簇，使得相似的样本尽量被分到同一个聚簇。K-Means衡量相似度的计算方法为欧氏距离（Euclid Distance）。

1. 传统K-Means算法流程

算法步骤：

1.（随机）选择K个聚类的初始中心；

2.对任意一个样本点，求其到K个聚类中心的距离，将样本点归类到距离最小的中心的聚类，如此迭代n次；

3.每次迭代过程中，利用均值等方法更新各个聚类的中心点(质心)；

4.对K个聚类中心，利用2,3步迭代更新后，如果位置点变化很小(可以设置阈值)，则认为达到稳定状态，迭代结束，对不同的聚类块和聚类中心可选择不同的颜色标注。

优点 

1）原理比较简单，实现也是很容易，收敛速度快。 

2）聚类效果较优。 

3）算法的可解释度比较强。 

4）主要需要调参的参数仅仅是簇数k。

缺点:

1、需要确定K的值。K的取值需要事先确定，然而在无监督聚类任务上，由于并不知道数据集究竟有多少类别，所以很难确定K的取值。举例来说，利用K-Means做 彩色图像分割（Segmentation）任务，如果图像只有一个物体和背景，那么很容易确定将K设置为2，并且较容易得到比较好的分割效果，但是对于一副有更多物体的图像，K的设定就很难了，因为我们并不总能人工去判断这幅图像里面有几个类别。对于文档聚类更是如此，比如一批新闻 数据集，可以按照主题聚类，但是有多少主题呢，这个不能事先获得。

2、对异常点敏感。K-Means很容易受到异常点（outliers）的影响，由于K-Means在Update Step取得是簇内样本均值，那么就会很容易受到异常点的影响，比如某个簇内样本在某个维度上的值特别大，这就使得聚簇中心偏向于异常点，从而导致不太好的聚类效果。

3、凸形聚类。K-Means由于采用欧氏距离来衡量样本之间相似度，所以得到的聚簇都是凸的，就不能解决“S型”数据分布的聚类，这就使得K-Means的应用范围受限，难以发现数据集中一些非凸的性质。

4、聚簇中心初始化，收敛到局部最优，未考虑密度分布等等。

K-Means优化:

K-Medians。不同于K-Means使用欧式距离计算目标函数，K-Medians使用曼哈顿距离（Manhattan Distance），对应的则是 l1范数。在目标求解的Update过程中，用簇内样本每个维度的中位数来当作聚簇中心在该维度的值（K-Means使用的是平均值），K-Medians的Median就是这个意思；在Assignment过程中，使用曼哈顿距离将每个样本划归为最近的聚簇。K-Medians可以很好地解决异常点问题.不难发现，在异常点的影响下，K-Medians更鲁棒，能较好的代表聚类结果。

K-Medoids。在K-Means中，聚簇中心不一定是样本点，而是样本点的中心。但是在K-Medoids中，聚簇中心就是样本点。比如在初始化过程中，K-Means是随机初始化k个聚簇中心，K-Medoids是在样本集中选择k个作为聚簇中心。即便K-Means初始过程中也可以选择样本点，但是在后续Step中，K-Medoids一直保持聚簇中心为样本点，K-Means则不然。另外，K-Medoids使用的是和K-Medians一样的曼哈顿距离，更新聚簇中心时，在簇内选择一个使得簇内曼哈顿距离之和最小的样本点作为聚簇中心。选择样本点作为聚簇中心的一个好处是聚簇中心可能是稀疏的，比如在文本聚类中，文本向量大多数是稀疏向量，系数向量计算相似度或距离速度更快。

K-Means++。初始聚簇中心的选择是K-Means的一个重要难点，K-Means++使用了一种方法来寻找到一组比较好的初始聚簇中心。其主要思想是：首先，选择一个样本点作为第一个聚簇中心，然后再选择下一个聚簇中心时要尽量离第一个已经选择的簇中心远一些，选择的方法是根据一个概率分布，这个概率分布和样本到聚簇中心的距离有关，比如 ，即已选择的聚簇中心越远概率越大；对于第三个聚簇中心的选择，需要加权考虑到第一、第二个已选择聚簇中心的距离。重复上述过程直到选出k个聚簇中心。K-Means++可以很好地解决K-Means的初始化问题。

其他聚类方法。为了解决K-Means的K初始值选取的问题，可以采用层次聚类（Hierarchical Clustering）的方法；为了解决K-Means未考虑密度分布以及非凸聚类的缺陷，可以考虑使用密度聚类DBSCAN算法。此外还有很多聚类算法，比如混合高斯聚类。