13 聚类

13.1 无监督学习简介

在无监督学习中，我们的训练样本不包含任何标签$y$。算法将从训练样本中找到一些隐含在数据中的结构。

13.2 K-Means算法

在聚类算法中，算法将无标签的数据划分成有紧密关系的簇。

K-Means算法是最热门的聚类算法，K-Means算法接收2个输入，分别是K（要划分的簇的个数）、无标签的训练数据集。算法过程如下：
1)随机初始化聚类中心：随机选取K个点，称为聚类中心。
2)分配到簇：对于m个训练样本，计算到K个中心点的距离，然后将其划分到距离最近的中心点对应的簇中。即$c^{(i)}:=\underset{k}{min}||x^{(i)}-u_k||^2,k\in[1,K]$
3)移动聚类中心：对于K个簇，分别计算每一个簇中的点的平均值，将该簇所关联的中心点移动到平均值的位置。这里的$u_k$是一个n维向量。(对于没有点的簇，可以直接删除该中心点或者重新初始化中心点)
4)重复2-3步骤，直至中心点不再变化。

下面是一个K-Means算法的示例：

初始化随机的中心点，计算距离后分类，然后移动中心点

多次迭代后，最终的聚类结果如下：

在没有非常明显组群的情况下，也可以使用K-Means：对于右图是不同人的身高体重，我们想要设计S、M、L三种型号的衬衫，那么就可以将数据划分成3类，每类就对应一种衬衫型号。

13.3 优化目标

了解K-Means算法的代价函数有助于理解算法过程，也可以借助它帮助K-Means算法找到更好的簇，并且避免局部最优解。

K-Means的代价函数为：$J(c^{(1)},…,c^{(m)},u_1,…,u_K)=\frac{1}{m}\sum_{i=1}^{m}||x^{(i)}-u_{c^{(i)}}||^2$.我们要找到参数$c^{(1)},…,c^{(m)}$, $u_1,…,u_K$使得代价函数$J$最小。即要最小化所有数据点与其所关联的聚类中心点之间的距离之和。该代价函数也称为失真代价函数（distortion cost function）

可以证明：K-Means算法中分配到簇的步骤就是在最小化$J$关于变量$c$的代价，移动聚类中心就是在最小化$J$关于变量$u$的代价。

13.4 随机初始化

随机初始化聚类中心点的方法：1.选择K<m，即聚类中心点的个数要小于训练样本的数量 2.随机选择K个训练样本作为聚类中心。

随机初始化的状态不同，K-Means最终可能会得到不同的结果。如果初始化不好，有可能会停留在一个局部最优处（如下图右下角两种局部最优的情况）。

为了避免算法陷入局部最优解，我们可以运行多次K-Means算法（通常运行501000次），每一次都重新随机初始化，最后比较多次运行 K-Means的结果，选择代价函数最小的结果。这种方法在K较小的时候(K=210)可行，如果K较大可能不会有明显地改善。

13.5 选择聚类数量

没有最好的选择聚类数的方法，通常是需要根据不同的问题人工选择。需要思考运用 K-Means算法的动机，然后选择能最好服务于该目的的聚类数。

方法一：肘部法则。通过改变聚类数K，画出代价函数$J$随K值变化的曲线，可能会得到一条类似肘部的曲线。如左图，在$K=3$的左侧代价函数$J$下降较快，而在$K=3$的右侧代价函数$J$下降缓慢。$K=3$这个点就是肘点，在此之后，代价函数$J$就下降的非常慢，那么我们就选K = 3。

但有时也会出现右图的情况，代价函数曲线比较平滑，没有肘点。这时就需要人工选择。

方法二：考虑下游任务的目的。通常聚类算法服务于下游任务，可以根据下游任务的目的，看哪个参数K能更好地应用于下游任务。例如：是生产5种尺寸的衬衫让衬衫更合身，还是生产3种尺寸的衬衫让衬衫价格更便宜。