四、EM 算法与 kmeans 模型

1. kmeans算法：给定样本集 ， 针对聚类所得簇划分 ， 最小化平方误差：

   

   其中 是簇 的均值向量。

2. 定义观测随机变量为 ，观测数据为 。定义隐变量为 ，它表示 所属的簇的编号。设参数 ， 则考虑如下的生成模型：

   

   其中 表示距离 最近的中心点所在的簇编号。即：

   • 若 最近的簇就是 代表的簇，则生成概率为 。
   • 若 最近的簇不是 代表的簇，则生成概率等于 0 。

3. 计算后验概率：

   

   即：

   • 若 最近的簇就是 代表的簇，则后验概率为 1 。
   • 若 最近的簇不是 代表的簇，则后验概率为 0 。

4. 计算 函数：

   

   设距离 最近的聚类中心为 ，即它属于簇 ，则有：

   

   则有：

   

   定义集合 ，它表示属于簇 的样本的下标集合。则有：

   

   则有：

   

   这刚好就是 k-means 算法的目标：最小化平方误差。

5. 由于求和的每一项都是非负的，则当每一个内层求和 都最小时，总和最小。即：

   

   得到：，其中 表示集合 的大小。

   这就是求平均值来更新簇中心。