K-Means

0. 引言

K-Means算法是无监督的聚类算法，它实现起来比较简单，聚类效果也不错，因此应用很广泛。K-Means算法有大量的变体，本文就从最传统的K-Means算法讲起，在其基础上讲述K-Means的优化变体方法。包括初始化优化K-Means++, 距离计算优化elkan K-Means算法和大数据情况下的优化Mini Batch K-Means算法。

1. K-Means原理

K-Means算法的思想很简单，对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。
如果用数据表达式表示，假设簇划分为 $(C1,C2,...Ck)$ ，则我们的目标是最小化平方误差 $E$ ：
$E=∑i=\sum_{i=1}^k\sum_{x∈Ci}||x−μ_i||^2_2$
其中 $μ_i$ 是簇 $C_i$ 的均值向量，有时也称为质心，表达式为：
$μi=\frac{1}{|Ci|}\sum_{x∈C_i}x$
如果我们想直接求上式的最小值并不容易，这是一个NP难的问题，因此只能采用启发式的迭代方法。
K-Means采用的启发式方式很简单，用下面一组图就可以形象的描述。

k-means实现方法简介

上图a表达了初始的数据集，假设k=2。在图b中，我们随机选择了两个k类所对应的类别质心，即图中的红色质心和蓝色质心，然后分别求样本中所有点到这两个质心的距离，并标记每个样本的类别为和该样本距离最小的质心的类别，如图c所示，经过计算样本和红色质心和蓝色质心的距离，我们得到了所有样本点的第一轮迭代后的类别。此时我们对我们当前标记为红色和蓝色的点分别求其新的质心，如图4所示，新的红色质心和蓝色质心的位置已经发生了变动。图e和图f重复了我们在图c和图d的过程，即将所有点的类别标记为距离最近的质心的类别并求新的质心。最终我们得到的两个类别如图f。

当然在实际K-Mean算法中，我们一般会多次运行图c和图d，才能达到最终的比较优的类别。

2. 传统K-Means算法流程

对于K-Means算法，首先要注意的是k值的选择，一般来说，我们会根据对数据的先验经验选择一个合适的k值，如果没有什么先验知识，则可以通过交叉验证选择一个合适的k值。
在确定了k的个数后，我们需要选择k个初始化的质心，就像上图b中的随机质心。由于我们是启发式方法，k个初始化的质心的位置选择对最后的聚类结果和运行时间都有很大的影响，因此需要选择合适的k个质心，最好这些质心不能太近。

好了，现在我们来总结下传统的K-Means算法流程。

输入是样本集 $D=\{x_1,x_2,...,x_m\}$ ，聚类的簇树 $k$ ,最大迭代次数 $N$ 。
输出是簇划分 $C=\{C_1,C_2,...,C_k\}$

从数据集 $D$ 中随机选择 $k$ 个样本作为初始的 $k$ 个质心向量： $\{ μ_1,μ_2,...,μ_k \}$
对于 $n=1,2,...,N$
a. 将簇划分 $C$ 初始化为 $C_t=\varnothing,t=1,2...k$
b. 对于 $i=1,2...m$ ,计算样本 $x_i$ 和各个质心向量 $μ_j(j=1,2,...k)$ 的距离： $d_{ij}=||x_i−μ_j||^2_2$ ，将 $x_i$ 标记最小的为 $d_{ij}$ 所对应的类别 $λ_i$ 。此时更新 $C_{λ_i}=C_{λ_i}\cup{x_i}$
c. 对于 $j=1,2,...,k$ ,对 $C_j$ 中所有的样本点重新计算新的质心 $μ_j=\frac{1}{|Cj|}\sum_{x∈C_j}x$
d. 如果所有的k个质心向量都没有发生变化，则转到步骤3
输出簇划分 $C={C_1,C_2,...,C_k}$

3. K-Means算法优化

K-Means算法的优化主要在于两个方面：

k的选择，因为到底把k设置为多少才合适，一直都没有一个明确的结论，全凭感觉而言。
k个初始化的质心的位置选择对最后的聚类结果和运行时间都有很大的影响，因此需要选择合适的k个质心。如果仅仅是完全随机的选择，有可能导致算法收敛很慢并且收敛效果不佳。
而针对第一个问题并没有太好的解决办法，K-Means算法的优化主要在于对第二个问题的优化。

3.1 K-Means++

K-Means++算法就是对K-Means随机初始化质心的方法的优化。
K-Means++的对于初始化质心的优化策略也很简单，如下：

从输入的数据点集合中随机选择一个点作为第一个聚类中心 $μ_1$
对于数据集中的每一个点 $x_i$ ，计算它与已选择的聚类中心中最近聚类中心的距离 $D(x_i)=argmin||x_i−μ_r||^2_2 , r=1,2,...k_{selected}$
选择一个新的数据点作为新的聚类中心，选择的原则是： $D(x)$ 较大的点，被选取作为聚类中心的概率较大
重复b和c直到选择出k个聚类质心(k-1次)
利用这k个质心来作为初始化质心去运行标准的K-Means算法

3.2 elkan K-Means(距离计算优化)

在传统的K-Means算法中，我们在每轮迭代时，要计算所有的样本点到所有的质心的距离，这样会比较的耗时。那么，对于距离的计算有没有能够简化的地方呢？elkan K-Means算法就是从这块入手加以改进。它的目标是减少不必要的距离的计算。
elkan K-Means利用了两边之和大于等于第三边,以及两边之差小于第三边的三角形性质，来减少距离的计算。

第一种规律是对于一个样本点x和两个质心 $μ_{j_1}$ , $μ_{j_2}$ 。如果我们预先计算出了这两个质心之间的距离 $D(j_1,j_2)$ ，则如果计算发现 $2D(x,j_1)≤D(j_1,j_2)$ ,我们立即就可以知道 $D(x,j_1)≤D(x,j_2)$ 。此时我们不需要再计算 $D(x,j_2)$ ,也就是说省了一步距离计算。

第二种规律是对于一个样本点 $x$ 和两个质心 $μ_{j_1}$ , $μ_{j_2}$ 。我们可以得到 $D(x,j_2)≥max\{0,D(x,j_1)−D(j_1,j_2)\}$ 。这个从三角形的性质也很容易得到。

利用上边的两个规律，elkan K-Means比起传统的K-Means迭代速度有很大的提高。但是如果我们的样本的特征是稀疏的，有缺失值的话，这个方法就不使用了，此时某些距离无法计算，则不能使用该算法。

3.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算法，用得到不同的随机采样集来得到聚类簇，选择其中最优的聚类簇。

3.4 二分 (bisecting) k-means

二分 (bisecting) k-means，其主要思想：一个大cluster进行分裂后可以得到两个小的cluster；为了得到k个cluster，可进行k-1次分裂。算法流程如下：

初始只有一个cluster包含所有样本点；
repeat:
从待分裂的clusters中选择一个进行二元分裂，所选的cluster应使得SSE最小；
until:
有k个cluster

上述算法流程中，为从待分裂的clusters中求得局部最优解，可以采取暴力方法：依次对每个待分裂的cluster进行二元分裂（bisect）以求得最优分裂。二分k-means算法聚类过程如图：

bisecting k-means.png

3.5 K值的优化

轮廓系数（Silhouette Coefficient）结合了聚类的凝聚度（Cohesion）和分离度（Separation），用于评估聚类的效果。该值处于-1~1之间，值越大，表示聚类效果越好。具体计算方法如下：

对于每个样本点i，计算点i与其同一个簇内的所有其他元素距离的平均值，记作a(i)，用于量化簇内的凝聚度。
选取i外的一个簇b，计算i与b中所有点的平均距离，遍历所有其他簇，找到最近的这个平均距离,记作b(i)，即为i的邻居类，用于量化簇之间分离度。
对于样本点i，轮廓系数 $s(i) = \frac{b(i)-a(i)}{max\{a(i),b(i)\}}$
计算所有i的轮廓系数，求出平均值即为当前聚类的整体轮廓系数，度量数据聚类的紧密程度

从上面的公式，不难发现若s(i)小于0，说明i与其簇内元素的平均距离小于最近的其他簇，表示聚类效果不好。如果a(i)趋于0，或者b(i)足够大，即a(i)<<b(i)，那么s(i)趋近与1，说明聚类效果比较好。

在实际应用中，由于Kmean一般作为数据预处理，或者用于辅助分聚类贴标签。所以k一般不会设置很大。可以通过枚举，令k从2到一个固定值如10，在每个k值上重复运行数次kmeans(避免局部最优解)，并计算当前k的平均轮廓系数，最后选取轮廓系数最大的值对应的k作为最终的集群数目。

4. K-Means与KNN

K-Means是无监督学习的聚类算法，没有样本输出；而KNN是监督学习的分类算法，有对应的类别输出。KNN基本不需要训练，对测试集里面的点，只需要找到在训练集中最近的k个点，用这最近的k个点的类别来决定测试点的类别。而K-Means则有明显的训练过程，找到k个类别的最佳质心，从而决定样本的簇类别。

当然，两者也有一些相似点，两个算法都包含一个过程，即找出和某一个点最近的点。两者都利用了最近邻(nearest neighbors)的思想。

5. K-Means小结

K-Means的主要优点有：

原理比较简单，实现也是很容易，收敛速度快。
聚类效果较优。
算法的可解释度比较强。
主要需要调参的参数仅仅是簇数k。

K-Means的主要缺点有：

K值的选取不好把握
对于不是凸的数据集比较难收敛
如果各隐含类别的数据不平衡，比如各隐含类别的数据量严重失衡，或者各隐含类别的方差不同，则聚类效果不佳
采用迭代方法，得到的结果只是局部最优。
对噪音和异常点比较的敏感。