$k$ 均值聚类 k-Means Clustering Algorithm

在聚类问题中，给定训练集 $\{x^{(1)},\cdots,x^{(m)}\}$，算法试图将数据集分为若干组紧密结合的簇。这里，$x^{(i)} \in \mathbb{R}^n$，但数据不包含标签 $y^{(i)}$。所以聚类是一个非监督学习问题。

$k$ 均值聚类的算法过程如下：

1. 随机初始化聚类质心 cluster centroids $\mu_1,\mu_2,\cdots,\mu_k \in \mathbb{R}^n$
2. 重复以下步骤直至收敛：1）对每一个 $i$，令 $c^{(i)}=arg\min_j||x^{(i)}-\mu_j||^2$；2）对每一个 $j$，令 $\mu_j=\frac{\sum_{i=1}^m 1\{c^{(i)}=j\}x^{(i)}}{\sum_{i=1}^m 1\{c^{(i)}=j\}}$

在上面的算法中，$k$ 作为算法的一个参数，代表我们所需要找到的聚类数量；聚类质心 $\mu_j$ 代表当时算法对每一个聚类中心点位置的猜测；在算法的第一步初始化聚类质心时，可以随机选择 $k$ 个训练样本作为各自聚类的质心。（也可以选用其它随机方法）

算法最内层的循环包含两步：1）将训练样本 $x^{(i)}$ 分配到距离它最近的质心 $\mu_j$；2）将质心 $\mu_j$ 重新设置为分配到该聚类的所有点的均值位置。

$k$ 均值聚类算法能否保证收敛呢？从某种意义上是可以的。定义畸变函数distortion function $$ J(c,\mu)=\sum_{i=1}^m ||x^{(i)}-\mu_{c^{(i)}}||^2 $$ 这里 $J$ 衡量的是所有训练样本 $x^{(i)}$ 距其聚类质心 $\mu_{c^{(i)}}$ 距离的平方和。可以证实，k均值聚类就是针对 $J$ 的坐标下降法。具体来说，算法最里层的循环，重复地先锁定 $\mu$ 不变，针对 $c$ 来最小化 $J$，之后再锁定 $c$ 不变，针对 $\mu$ 来最小化 $J$。所以整个过程中，$J$ 是单调下降的，$J$ 的值肯定会收敛。（通常来说，这意味着 $c, \mu$ 也会收敛。理论上，k均值聚类可能会在少数不同的聚类结果之间震荡，即不同的 $c,\mu$ 值，但 $J$ 的值相同。但实际中，这种情况几乎不会从不出现）

畸变函数 $J$ 是一个非凸函数，所以针对 $J$ 的坐标下降法并不能保证收敛于全局最小值，也就是说，$k$ 均值聚类易受到局部最小值问题的影响。但实际中 $k$ 均值聚类会给出非常好的聚类结果。如果实在担心收敛于比较糟糕的局部最小值，一个常见的策略是多执行几次 $k$ 均值聚类过程，每次使用不同的随机初始值，然后在所有的聚类结果中，挑选 $J(c,\mu)$ 最小的结果。