1. 什么是Kmeans
Kmeans是一个聚类算法，设定一个K，Kmeans算法可以将数据样本划分为K类。
2. Kmeans算法流程
(1) 每个样本对应一个坐标，按照某种初始化方法初始化K个中心点。
(2) 每个样本计算到K个中心点的距离，选择距离最小的点，假设是第$i$号中心点，将该样本归类到$i$。
(3) 计算每类样本的中心点，更新中心点的坐标
(4) 重复(2)(3)步，直到每一类的中心点收敛
(5) 每个样本的类别取决于和该样本距离最近的类别中心点
3. Kmeans算法原理
Kmeans算法很多人都觉得容易，但是鲜有人思考为什么可以这么做，为什么这么做最后收敛的结果就是好的。本质上Kmeans算法可以看作是EM算法。我们现在从EM算法的角度求解聚类问题。首先我们有一个数据集，数据集有一些样本。然后我们假设有$K$个高斯分布$P(x|\mu_k,\sigma_k)$，第$k$个高斯分布的先验为$P(k)$。我们现在想要求出这$K$个高斯分布的参数使得数据集的似然函数达到最大。我们先列出似然函数：
这个式子中$\theta$代表$K$个高斯分布的参数，$P(x_i,k|\theta)$表示样本$x_i$是从第$k$个高斯分布抽样出来的联合概率。我们对这个式子取对数并套用Jensen不等式，可以得到：
EM算法的E步是固定一个$\theta$，求出$Q_i(k)$使得不等式变成等式，可以求得：
EM算法的M步，就是固定$Q_i(k)$，选择一个$\theta$使$\ln L(X,\theta)$达到最大。迭代E步和M步直到收敛。看到这里有人也许能发现这其实是一个混合高斯模型，没错，这就是混合高斯模型。那么Kmeans算法和混合高斯模型有什么地方不同呢？在求解过程中，Kmeans算法求出$Q_i(k)$后并不是直接将$Q_i(k)$代入似然函数求最大值，而是从$Q_i(k)$选择值最大的类别$k$作为自己的类别重新求似然函数。本质上Kmeans算法的似然函数是：
其中上式的$k$是样本的类别，这个类别是从样本类别的后验分布$Q_i(k)$中选择最大的$k$。这样我们就可以直接对求$\mu_k$和$\sigma_k$了。通过求极值点得到$\mu_k$是所有类别是$k$的样本的中心。综上，Kmeans算法本质上就是使用EM算法，在E步求样本类别的后验分布，在M步使用后验概率最大的类别代入似然函数求最大似然，迭代这个过程直到收敛。
4. 杂谈
感觉这篇文章写得逻辑有点乱，不过一路梳理下来感觉对Kmeans算法，EM算法，混合高斯模型都有了更深刻的理解，也算是一种收获了。然后还有一点要说的，就是EM算法和Kmeans算法对于初值的设置都非常重要，初始参数的设置会影响最终的收敛结果。