uniform机器学习极简入门3—KMeans

1 kmeans算法概述

往往在实际数据分析中，我们需要发现数据的一些内在规律，但是数据一般都是未标注，因此希望通过某个算法来揭示数据的内在性质和规律，其中最常用的算法就是聚类。

kmeans就是聚类算法中最常用的一种，是无监督的算法，目标是通过数据分布来发现其中存在的类簇。
如下图，我们可以直观的看出数据可能存在两个类簇，但是如何通过算法来发现？

kmeans1

2 kmeans算法流程

我们的目标就是希望找到类别的中心使得类内点到中心的距离尽可能近，这个距离可以表示如下：
$E = \sum_{i=1}^{k}\sum_{x^{(j)}\in{C_i}}||x^{(j)}-c_i||^2 \ \ \ \ (1)$
目标就是最小化E，但是这是个NP问题，kmeans采用贪心算法来迭代找到最优。

kmeans的大致算法思想如下

先假设数据可以分为k类

随机从数据集中选择k个点作为中心点

分别计算所有点与这k个中心点的距离，选择最近的中心点所在的类别作为类别标签，这样就把所有点都分配了类标

然后根据k个类别的样本重新计算各个类别的中心点，得到新的k个类中心点。

重复步骤3、步骤4，直至中心点不再发生改变，结束。

这是一个循环迭代的过程，通过反复迭代直至找到中心点。看起来比较简单，但其实背后有很多需要注意的地方。

2.1 k值选择

公式(1)很直观，只要能够最小化E即可，但是k是一个超参数（不是通过数据迭代得来，是我们初始化指定），我们发现，

如果k选择越大，那么这个E可以最小化到0，即如果类别十分细，细到每个样本作为一个单独的类，那么E=0，但这不是我们希望看到的。

如果k选择较小，那么类别较粗，可能类内的距离就比较大。

因此如何选择k将直接影响聚类的结果。
我们做个直观的图，还是最开始的数据图，我们可以发现E和k的关系如下:

k_E_relation

基于曲率判断
有种确定k的方法，即看上图中曲率变化最大的点，我们可以看到k=2的时候曲率变化最大，那么最优的k应该就选2。

2.2 初始中心点选择

初始中心点的选择如果不当，可能会陷入局部最优的。
下面列种改进方法
kmeans++

初始化中心点集合:C = {}

从输入的数据点集合中随机选择一个点c_k作为中心点，加入到中心点集合C= C +c_k

数据集中每个点x计算与中心点集合中最近的中心点的距离d(x)

在d(x)中选择距离较大的点作为新的中心点，加入到中心点集合

重复步骤2、步骤3、步骤4，直至找到k个中心点，然后再采用kmeans算法来进行聚类。

另一种确定中心点的方法就是通过层次聚类或者Canopy方法先得到k个类别，把他们的中心点作为初始化中心点。

2.3 距离度量

既然涉及到空间距离，自然离不开距离度量函数的定义，这点往往容易被忽视，我们在实际实践中，默认采用都是欧式距离来表示，但是这个距离合理性的前提是我们的特征向量表征一定也是符合欧式空间特征才行，否则出来的结果会较差。

距离定义首先需要满足一些基本性质：

非负性: d(x, y)>=0
同一性：d(x, y)=0 当且仅当x=y
对称性：x(x, y)=d(y, x)
直递性（三角不等式）：d(x, y)<=d(x,z) + d(z, y)

闵可夫斯基距离
我们常用的就是闵可夫斯基距离
$d(x, y) = [\sum_{i=1}^{n}(x_i-y_i)^p]^{\frac{1}{p}}$
$x=(x_1, x_2, ..., x_n)$
$y=(y_1, y_2, ..., y_n)$

当p=1，表示曼哈顿距离
当p=2，表示欧式距离

但是，在实践中，我们的特征向量未必都是连续性变量，上述距离度量函数使用与连续变量空间，对于离散变量，一般采用其他的方法来衡量距离，例如VDM。
另外我们常用的距离衡量还有余弦距离等，这里推荐一个python库，支持较多的距离衡量

Biopython为k-means聚类提供了各种距离函数，包括余弦距离、皮尔逊相似度量、欧式距离等。

3 kmeans算法不足

kmeans算法由于距离度量采用的是点-点的距离，对于球状的空间分布是可以正确聚类的，但是非球状的则无法正确聚类，解决方案一般是通过特征变换来达到高维空间或者另一个特征空间的可分（可聚类）

ball_cluster
如果特征空间高维，数据量较大，kmeans运算速度较慢

4 二分k-means算法

层次聚类算法是从底向上，逐步聚类，而二分kmeans算法则是从顶向下，逐步分裂，最终得到我们要的k个类。
算法描述如下

先将整个样本集合作为一个簇，该簇中心点即等于所有向量平均，计算此时的SSE（公式1）

对每个类簇都进行二分类（采用kmeans算法），然后计算拆分后的总的SSE，选择变化最大的那个分类簇进行二分裂

重复上述步骤，直至类别数等于k，结束。

这个分类算法有点类似决策树的分裂思想，在决策树分裂的过程中，我们希望的是找到熵减少（熵增益）最大的特征分裂点，而这里是找到SSE减少最大的类别。分类算法和聚类算法目标都是希望能够找到让类内样本越纯的方法。后续我们讲到决策树的时候会再阐开这块内容。