转 https://zhuanlan.zhihu.com/p/78798251
KMeans - 图3

K-means 是我们最常用的基于欧式距离的聚类算法，其认为两个目标的距离越近，相似度越大。
本文大致思路为：先介绍经典的牧师-村名模型来引入 K-means 算法，然后介绍算法步骤和时间复杂度，通过介绍其优缺点来引入算法的调优与改进，最后我们利用之前学的 EM 算法，对其进行收敛证明。

1. 算法

1.1 牧师-村民模型

K-means 有一个著名的解释：牧师—村民模型： 有四个牧师去郊区布道，一开始牧师们随意选了几个布道点，并且把这几个布道点的情况公告给了郊区所有的村民，于是每个村民到离自己家最近的布道点去听课。听课之后，大家觉得距离太远了，于是每个牧师统计了一下自己的课上所有的村民的地址，搬到了所有地址的中心地带，并且在海报上更新了自己的布道点的位置。牧师每一次移动不可能离所有人都更近，有的人发现A牧师移动以后自己还不如去B牧师处听课更近，于是每个村民又去了离自己最近的布道点……就这样，牧师每个礼拜更新自己的位置，村民根据自己的情况选择布道点，最终稳定了下来。 我们可以看到该牧师的目的是为了让每个村民到其最近中心点的距离和最小。

1.2 算法步骤

所以 K-means 的算法步骤为：

  1. 选择初始化的 k 个样本作为初始聚类中心 KMeans - 图4 ；
  2. 针对数据集中每个样本 KMeans - 图5 计算它到 k 个聚类中心的距离并将其分到距离最小的聚类中心所对应的类中；
  3. 针对每个类别 KMeans - 图6 ，重新计算它的聚类中心 KMeans - 图7 （即属于该类的所有样本的质心）；
  4. 重复上面 2 3 两步操作，直到达到某个中止条件（迭代次数、最小误差变化等）。

    1.3 复杂度

    我们先看下伪代码：
    1. 获取数据 n 个 m 维的数据
    2. 随机生成 K 个 m 维的点
    3. while(t)
    4.  for(int i=0;i < n;i++)
    5.      for(int j=0;j < k;j++)
    6.          计算点 i 到类 j 的距离
    7.  for(int i=0;i < k;i++)
    8.      1. 找出所有属于自己这一类的所有数据点
    9.      2. 把自己的坐标修改为这些数据点的中心点坐标
    10. end
    时间复杂度： KMeans - 图8 ，其中，t 为迭代次数，k 为簇的数目，n 为样本点数，m 为样本点维度。
    空间复杂度： KMeans - 图9 ，其中，k 为簇的数目，m 为样本点维度，n 为样本点数。

    2. 优缺点

    2.1 优点

  • 容易理解，聚类效果不错，虽然是局部最优， 但往往局部最优就够了；
  • 处理大数据集的时候，该算法可以保证较好的伸缩性；
  • 当簇近似高斯分布的时候，效果非常不错；

  • 算法复杂度低。

    2.2 缺点

  • K 值需要人为设定，不同 K 值得到的结果不一样；

  • 对初始的簇中心敏感，不同选取方式会得到不同结果；
  • 对异常值敏感；
  • 样本只能归为一类，不适合多分类任务；
  • 不适合太离散的分类、样本类别不平衡的分类、非凸形状的分类。

    3. 算法调优与改进

    针对 K-means 算法的缺点，我们可以有很多种调优方式：如数据预处理（去除异常点），合理选择 K 值，高维映射等。以下将简单介绍：

    3.1 数据预处理

    K-means 的本质是基于欧式距离的数据划分算法，均值和方差大的维度将对数据的聚类产生决定性影响。所以未做归一化处理和统一单位的数据是无法直接参与运算和比较的。常见的数据预处理方式有：数据归一化，数据标准化。
    此外，离群点或者噪声数据会对均值产生较大的影响，导致中心偏移，因此我们还需要对数据进行异常点检测。

    3.2 合理选择 K 值

    K 值的选取对 K-means 影响很大，这也是 K-means 最大的缺点，常见的选取 K 值的方法有：手肘法、Gap statistic 方法。
    手肘法：

KMeans - 图10

当 K < 3 时，曲线急速下降；当 K > 3 时，曲线趋于平稳，通过手肘法我们认为拐点 3 为 K 的最佳值。
手肘法的缺点在于需要人工看不够自动化，所以我们又有了 Gap statistic 方法，这个方法出自斯坦福大学的几个学者的论文：Estimating the number of clusters in a data set via the gap statistic
KMeans - 图11
其中 KMeans - 图12 为损失函数，这里 KMeans - 图13 指的是 KMeans - 图14 的期望。这个数值通常通过蒙特卡洛模拟产生，我们在样本里所在的区域中按照均匀分布随机产生和原始样本数一样多的随机样本，并对这个随机样本做 K-Means，从而得到一个 KMeans - 图15 。如此往复多次，通常 20 次，我们可以得到 20 个 KMeans - 图16 。对这 20 个数值求平均值，就得到了 KMeans - 图17 的近似值。最终可以计算 Gap Statisitc。而 Gap statistic 取得最大值所对应的 K 就是最佳的 K。

KMeans - 图18

由图可见，当 K=3 时，Gap(K) 取值最大，所以最佳的簇数是 K=3。
Github 上一个项目叫 gap_statistic ，可以更方便的获取建议的类簇个数。

3.3 采用核函数

基于欧式距离的 K-means 假设了了各个数据簇的数据具有一样的的先验概率并呈现球形分布，但这种分布在实际生活中并不常见。面对非凸的数据分布形状时我们可以引入核函数来优化，这时算法又称为核 K-means 算法，是核聚类方法的一种。核聚类方法的主要思想是通过一个非线性映射，将输入空间中的数据点映射到高位的特征空间中，并在新的特征空间中进行聚类。非线性映射增加了数据点线性可分的概率，从而在经典的聚类算法失效的情况下，通过引入核函数可以达到更为准确的聚类结果。

3.4 K-means++

我们知道初始值的选取对结果的影响很大，对初始值选择的改进是很重要的一部分。在所有的改进算法中，K-means++ 最有名。
K-means++ 算法步骤如下所示：

  1. 随机选取一个中心点 KMeans - 图19 ；
  2. 计算数据到之前 n 个聚类中心最远的距离 KMeans - 图20 ，并以一定概率 KMeans - 图21 选择新中心点 KMeans - 图22 ；
  3. 重复第二步。

简单的来说，就是 K-means++ 就是选择离已选中心点最远的点。这也比较符合常理，聚类中心当然是互相离得越远越好。
但是这个算法的缺点在于，难以并行化。所以 k-means II 改变取样策略，并非按照 k-means++ 那样每次遍历只取样一个样本，而是每次遍历取样 k 个，重复该取样过程 KMeans - 图23 次，则得到 KMeans - 图24 个样本点组成的集合，然后从这些点中选取 k 个。当然一般也不需要 KMeans - 图25 次取样，5 次即可。

3.5 ISODATA

ISODATA 的全称是迭代自组织数据分析法。它解决了 K 的值需要预先人为的确定这一缺点。而当遇到高维度、海量的数据集时，人们往往很难准确地估计出 K 的大小。ISODATA 就是针对这个问题进行了改进，它的思想也很直观：当属于某个类别的样本数过少时把这个类别去除，当属于某个类别的样本数过多、分散程度较大时把这个类别分为两个子类别。

4. 收敛证明

我们先来看一下 K-means 算法的步骤：先随机选择初始节点，然后计算每个样本所属类别，然后通过类别再跟新初始化节点。这个过程有没有想到之前介绍的 EM 算法 。
我们需要知道的是 K-means 聚类的迭代算法实际上是 EM 算法。EM 算法解决的是在概率模型中含有无法观测的隐含变量情况下的参数估计问题。在 K-means 中的隐变量是每个类别所属类别。K-means 算法迭代步骤中的 每次确认中心点以后重新进行标记 对应 EM 算法中的 E 步 求当前参数条件下的 Expectation 。而 根据标记重新求中心点 对应 EM 算法中的 M 步 求似然函数最大化时（损失函数最小时）对应的参数 。
首先我们看一下损失函数的形式：
KMeans - 图26
其中：
KMeans - 图27
为了求极值，我们令损失函数求偏导数且等于 0：
KMeans - 图28
k 是指第 k 个中心点，于是我们有：
KMeans - 图29
可以看出，新的中心点就是所有该类的质心。
EM 算法的缺点就是，容易陷入局部极小值，这也是 K-means 有时会得到局部最优解的原因。

5. k-means改进

改进从 初始化点选择、距离计算次数、批处理 入手。

5.1 K-Means初始化优化K-Means++

在上节我们提到，k个初始化的质心的位置选择对最后的聚类结果和运行时间都有很大的影响，因此需要选择合适的k个质心。如果仅仅是完全随机的选择，有可能导致算法收敛很慢。K-Means++算法就是对K-Means随机初始化质心的方法的优化。
K-Means++的对于初始化质心的优化策略也很简单，如下：
a) 从输入的数据点集合中随机选择一个点作为第一个聚类中心μ1
b) 对于数据集中的每一个点xi，计算它与已选择的聚类中心中最近聚类中心的距离D(xi)=argmin||xi−μr||22r=1,2,…kselected
c) 选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大
d) 重复b和c直到选择出k个聚类质心
e) 利用这k个质心来作为初始化质心去运行标准的K-Means算法

5.2 K-Means距离计算优化elkan K-Means

  1. 在传统的K-Means算法中，我们在每轮迭代时，要计算所有的样本点到所有的质心的距离，这样会比较的耗时。那么，对于距离的计算有没有能够简化的地方呢？elkan K-Means算法就是从这块入手加以改进。它的目标是减少不必要的距离的计算。那么哪些距离不需要计算呢？<br />    elkan K-Means利用了两边之和大于等于第三边,以及两边之差小于第三边的三角形性质，来减少距离的计算。<br />    第一种规律是对于一个样本点x和两个质心μj1,μj2。如果我们预先计算出了这两个质心之间的距离D(j1,j2)，则如果计算发现2D(x,j1)≤D(j1,j2),我们立即就可以知道D(x,j1)≤D(x,j2)。此时我们不需要再计算D(x,j2),也就是说省了一步距离计算。<br />    第二种规律是对于一个样本点x和两个质心μj1,μj2。我们可以得到D(x,j2)≥max{0,D(x,j1)−D(j1,j2)}。这个从三角形的性质也很容易得到。<br />    利用上边的两个规律，elkan K-Means比起传统的K-Means迭代速度有很大的提高。但是如果我们的样本的特征是稀疏的，有缺失值的话，这个方法就不使用了，此时某些距离无法计算，则不能使用该算法。

5.3 大样本优化Mini Batch K-Means

在统的K-Means算法中，要计算所有的样本点到所有的质心的距离。如果样本量非常大，比如达到10万以上，特征有100以上，此时用传统的K-Means算法非常的耗时，就算加上elkan K-Means优化也依旧。在大数据时代，这样的场景越来越多。此时Mini Batch K-Means应运而生。
顾名思义，Mini Batch，也就是用样本集中的一部分的样本来做传统的K-Means，这样可以避免样本量太大时的计算难题，算法收敛速度大大加快。当然此时的代价就是我们的聚类的精确度也会有一些降低。一般来说这个降低的幅度在可以接受的范围之内。
在Mini Batch K-Means中，我们会选择一个合适的批样本大小batch size，我们仅仅用batch size个样本来做K-Means聚类。那么这batch size个样本怎么来的？一般是通过无放回的随机采样得到的。
为了增加算法的准确性，我们一般会多跑几次Mini Batch K-Means算法，用得到不同的随机采样集来得到聚类簇，选择其中最优的聚类簇。

6. K-Means与KNN

  1. 初学者很容易把K-Means和KNN搞混，两者其实差别还是很大的。<br />    K-Means是无监督学习的聚类算法，没有样本输出；而KNN是监督学习的分类算法，有对应的类别输出。KNN基本不需要训练，对测试集里面的点，只需要找到在训练集中最近的k个点，用这最近的k个点的类别来决定测试点的类别。而K-Means则有明显的训练过程，找到k个类别的最佳质心，从而决定样本的簇类别。<br />    当然，两者也有一些相似点，两个算法都包含一个过程，即找出和某一个点最近的点。两者都利用了最近邻(nearest neighbors)的思想。

7. 参考

  1. 《机器学习》周志华
  2. K-means 笔记（三）数学原理
  3. K-means 怎么选 K?
  4. https://www.cnblogs.com/pinard/p/6164214.html