大家都知道K-mean是无监督学习的经典算法。那为什么K-mean是无监督学习呢？可能有人觉得：这也要证明？
其实这是一个值得思考的问题……仔细思考这个问题，你会觉得自己似乎不太懂K-mean了？
哈哈，不要多想，本文意在剖析K-mean算法的本质：
K-mean算法是一种隐变量模型；隐变量模型可以用EM算法计算参数；无监督EM算法的其他应用。
本文单纯分享我自己的理解，如有不准确的地方欢迎讨论，互相进步～
隐变量模型
隐变量模型指的是：已知的可观测到变量$\mathbf x$可以由一个或多个未知变量$\mathbf z$以一定的方式生成，并且这个隐变量是我们假定的。可能有人觉得：为什么那么麻烦要定义隐变量增加模型复杂度呢？
我觉得隐变量模是有现实意义的。比如一张图片是由颜色，亮度，对比度，分辨率等等决定；一句话的意思是由文字，语气，标点决定；一个人是由DNA里的信息决定……这些实际例子可以说明隐变量模型的合理性。
比较经典的隐变量模型有：HMM, GAN, VAE, LDA…我就不多做赘述。聪明的同学应该发现这些模型都是生成式模型（Generative model）。如果不知道生成式模型是什么的同学可以自我拓展一下。
K-mean
K-mean算法很简单，就是给一堆数据$\mathcal D$，这些都是观测到的。训练好的模型将数据氛围K个子集，各个聚类子集内的所有数据样本的均值作为该聚类的代表点。预测一个新的数据$x^*$时，计算$x^*$ 和K个中心点的“距离”，选择“距离”最近的中心，并把$x^*$归为该中心所在的类簇。
这个算法的不太标准的比喻：模型把一堆图片分成了2类，我拿到一看，诶，模型真聪明正巧一堆是猫的图片，另一堆是狗的图片。然后我随机丢给模型一张小老虎的照片，模型把该图片和两堆图片比较了一下，觉得和 “猫” 的那堆图片相似度高。于是模型就把该图片分到了“猫”那一类。
这时候你要说了，这明明是老虎怎么能分给猫呢？但在2分类的情况下，分到猫并没有错误。更关键的是这里的“猫” 和 “狗”的定义是人给的。模型只是认为这张小老虎的照片和猫堆的照片是同一类。所以也许应该定义为“猫科”和“犬科”哈哈哈哈……
所以其实K-means算法有很多问题:但这不是我们今天的重点。最后提一下吧
K-mean算法是一种隐变量模型
那么为什么K-mean算法是一种隐变量模型呢？判断一个模型是不是隐变量模型，比较关键的一点是：找出隐变量。
所以问题就转化成了K-mean算法的隐变量是什么？是K吗？对了一半，我觉得是K个中心点。
也就是说K-mean算法认为：所有观测数据可以用K个中心点表达。比如刚才图片的例子中，我觉得所有图片就分成两堆。
K-mean算法怎么求
其实刚才举的猫狗图片例子中，我非常“狡猾”地直接跳过了训练的步骤，直接说模型把一堆图片分成了2类。所以模型是怎么把图片分成这样的两类呢？是不是有可能分成别的两类，比如浅色动物和深色动物？那要怎么样才能认为模型的分类是我们想要的呢？我们来探讨一下…
K-mean算法的cost function
机器学习算法必然需要一个目标函数（objective function），那么K-mean算法的目标函数是如何表示的呢？
首先，K-mean的目标是：所有点到自己所属类的中心点“距离”的均值最小。数学表达式（“距离”用欧几里得距离表达）：
$J = \sum\limits_{n=1}^N \sum \limits_{k=1}^K \lambda_{nk} || x_n - \mu_k||^2$
其中$\lambda_{nk}$取值为1 或者 0，表示 第n个点是否是第k个类。$\mu_k$是第k个类的中心点，$x_n$是第n个点的位置。
K-mean的求解过程，和隐变量模型的EM算法的关系。
K-mean的求解过程：
- 随机选取k个点充当各个类的中心点$\{\mu_{1},\mu_{2},…,\mu_{K}\}$；
- 计算所有样本点与各个类中心之间的距离$dist(x_{n},\mu_{k})$，然后把样本点划入最近的类$k_j$中$dist(x_n,\mu_j) > dist(x_n,\mu_k \ \ \forall k \in K$；
- 根据重新归类的点，重新计算类的中心$\{\mu_{1},\mu_{2},…,\mu_{K}\}$；
- 重复 2-3，直至收敛。
以上过程代码展示可以参考 K-mean_demo.ipynb
注意到K-mean的收敛条件有很多：所有点的归属类不再改变，迭代m次后停止，目标函数$J$ 的变动$\Delta J < \delta$……
实际应用过程中K-mean对于初始化的依赖性非常强，也就是对于初始化参数非常敏感。
EM算法
由于篇幅有限，EM算法在这里不多做展开。指出三点：
- EM算法的核心是：E-step 和 M-step 顺序迭代直至达到收敛条件:
- E-step: 利用对隐藏变量的现有估计值，计算其最大似然估计值；
- M-step: 最大化在E-tep上求得的最大似然值来计算参数的值。
- M-step上找到的参数估计值被用于下一个E-step计算中，这个过程不断交替进行。
- 隐变量模型可以由EM算法解决。
- EM算法得到的是全局最优解。
我们知道K-mean是一种隐变量模型，而且上述步骤2和3，其实和EM算法的核心 E-step 和 M-step是一一对应的，其中的最大似然估计对应的是K-mean的目标函数 $J$。
注意到由于EM算法得到的是全局最优解，因此K-mean是可能得到全局最优解。为什么是可能
总结
由此，我们知道了在K-mean算法的无监督学习，其实就是隐变量模型上利用基于最大似然估计的EM算法计算参数。
如果优化目标（最大似然）是凸函数，那么EM算法得到的是全局最优解，因此K-mean是可能得到全局最优解的。不过在在非凸数据上难以收敛。
补充一下k-mean的缺点：
- 对初始状态敏感：初始状态不同，模型最后形成的clustering不一定相同。
- k是个先验的数字，或者说是个超参数，而且对模型的结果有很大影响，比较难把握
- 非凸数据，类型不平衡数据 难收敛或者效果不好，局部最优。