1. Kmeans算法原理

Kmeans算法思想：按照样本间距离大小，划分为K个簇，使得每个簇内部的样本点尽量紧密，簇之间的样本点离得尽量远。

假设簇的划分为$(C_1,C_2,\dots,C_K)$，Kmeans的目标是最小化平方误差$\sum\limits_{i=1}^n\sum\limits_{x_i\in C_k}||x_i-\mu_k||_2^2$，其中$\mu_k=\frac{1}{|C_k|}\sum\limits_{x\in C_k}x$为$C_k$的质心。

Kmeans算法流程：（类别数K已经选定）

初始化簇的划分$C={C_1,C_2,\dots,C_K}$和质心${\mu_1,\mu_2,\dots,\mu_K}$
对于每一轮迭代：
1. 每个计算样本$x_i$与$\mu_k$之间的距离$d_{ik}=||x_i-\mu_k||^2_2$，假如$d_{ij} = \min\limits_{k}||x_i-\mu_k||$，将样本归为$C_j=C_j\cup{x_i}$
2. 得到了新的划分C，重新计算每个簇的质心$\mu_k=\frac{1}{|C_k|}\sum\limits_{x\in C_k}x$
质心不再发生变化了，说明算法已经收敛，输出最终的划分C

2. Kmeans与GMM、EM算法的关系

最直观的感受是Kmeans算法也是迭代的求解最优的参数（质心）。事实上，Kmeans可以看作是GMM的特殊情况。

回顾一下GMM（详见GMM博客），引入隐变量Z服从一个离散的分布$p_k$， $k=1,\dots,K$，当Z属于第k个取值时，X服从高斯分布$N(\mu_k,\Sigma_k)$，GMM就是找到参数$p_k,\mu_k,\Sigma_k$使得X的log-likelihood$\sum\limits_{i}\log p(x|p,\mu,\Sigma)$达到最大。

2.1. GMM如何变成Kmeans？

将GMM里面每个component的协方差矩阵$\Sigma_k$都变为$\epsilon I$，这样高斯分布的协方差就固定了，不需要再参数估计。

将$\Sigma_k=\epsilon I$固定之后，会有什么影响？样本点$x_i$的后验概率为

$\begin{array}{rl} p(z_i=C_k|x_i) & = \frac{p(x_i,z_i=C_k)}{p(x_i)}\\ & = \frac{p_kN(x_i|\mu_k,\Sigma_k)}{\sum\limits_{j=1}^Kp_jN(x_i|\mu_j,\Sigma_j)}\\ & = \frac{p_k\exp\{-||x_i-\mu_k||^2/2\epsilon\}}{\sum\limits_{j=1}^Kp_j\exp\{-||x_i-\mu_j||^2/2\epsilon\}} \end{array}$

当$\epsilon\rightarrow0$，上式分母中最小的一项为$||x_i-\mu_j||^2$，最慢的趋向于0. 所以当$\epsilon\rightarrow0$时，$p(z_i=C_k|x_i)$中其他项都趋近于0，只有$|||x_i-\mu_j||^2$那一项比较大，所以

$p(z_i=C_k|x_i)=\begin{cases} 0,~~if~~k\neq j\\ 1,~~if ~~k=j\\ \end{cases}$

所以，我们得到了样本点分配到簇的hard assignment，正如Kmeans算法，每个样本点会被分配到离它最近的簇。

[2] Means algorithm performs hard assignment of data points to cluster, in which each data point is associated uniquely with one cluster, the EM algorithm makes a soft assignment based on the posterior probabilities.

2.2. Kmeans的E-step

GMM中的E-step是最大化Q函数

$\begin{array}{rl} Q(\theta,\theta^{(t)}) & = \sum\limits_{i=1}^n\sum\limits_{k=1}^{K}\log p_{k}N(x_i|p_{k},\Sigma_k)\cdot p(z_i=C_k|x_i)\\ & = \sum\limits_{i=1}^n\sum\limits_{k=1}^K(\log p_k + \log N(x_i|p_k,\Sigma_k))\cdot p(z_i=C_k|x_i) \end{array}$

当$\epsilon\rightarrow 0$时，如果只考虑参数$\mu$（不考虑参数$p$），把化简之后的后验概率$p(z_i=C_k|x_i)$代入Q函数，得到

$Q(\mu,\mu^{(t)}) = -\frac{1}{2}\sum\limits_{i=1}^n\sum\limits_{k=1}^{K}||x_i-\mu_k||^2+const$

因此，经过化简之后的GMM的最大化Q函数，实际上就是最小化每个点到最近质心的距离之和，与Kmeans的算法一致。

2.3. Kmeans的M-step

GMM中参数$\mu$和$p$迭代的公式为：

$\begin{array}{rl} \mu_k^{(t+1)} & = \frac{\sum\limits_{i=1}^np(z_i=C_k|x_i,\theta^{(t)})x_i}{\sum\limits_{i=1}^np(z_i=C_k|x_i,\theta^{(t)})}\\ p^{(t+1)}_k & = \frac{1}{n}\sum\limits_{i=1}^np(z_i=C_k|x_i,\theta^{(t)}) \end{array}$

经过化简之后

$\mu_k^{(t+1)} = \sum\limits_{i\in C_k}\frac{x_i}{|C_k|}$，即为属于第k个簇的样本均值，与Kmeans算法一致；
$p_k^{(t+1)} = \frac{|C_k|}{n}$，即为每个簇占总样本的比例，不过在Kmeans算法里，这个参数不再重要。

2.4. 图解

下面2幅图是一维GMM和Kmeans的比较，当$\epsilon\rightarrow0$时，$\epsilon I$表示高斯分布几乎没有variance，GMM从上图变成下图的样子。

从混合模型的角度出发，GMM的点（例如图中的黄色星星）有一定的概率三种不同的高斯分布，但是Kmeans只有一种选择，那就是离这个点最近的$\mu$.

GMM的目标是确定三个高斯分布的参数，使得样本点的log-likelihood达到最大；而Kmeans的目标是确定$\mu_1,\mu_2,\mu_3$的值，使得样本点到最近$\mu$值的距离之和最小。从图容易理解，Kmeans里面参数$p$不再重要，只需要找到最佳的参数$\mu$.

GMM v.s. K-means

如果是样本是三维的话，Kmeans由于是GMM的协方差矩阵取$\epsilon I$的特殊情况，所以Kmeans是在球形范围内寻找样本点，GMM是椭球形范围内寻找。

因为Kmeans是简化之后的GMM，Kmeans的收敛速度更快。