EM算法

时间 2021-05-31 标签算法

EM最大期望算法（Expectation Maximum）只要给出一些训练数据，再定义一个最大化函数，就能通过计算机的多次迭代，得到所需要的模型。

迭代步骤：

初始化k个中心 $C_{1}，C_{2},C_{3}...C_{k}$ , $C_{2}$ , $C_{3}$ ... $C_{k}$

E:计算各个点到k个中心的距离，并归到最近的类，并算出每个类中点的平均距离d以及各个类中心的平均距离D；

M:根据分好的类，重新计算各个中心的位置 $C_{1}，C_{2},C_{3}...C_{k}$ , $C_{2}$ , $C_{3}$ ... $C_{k}$ ；

假如某一个分类有点 $V_{1}，V_{2},V_{3}...V_{k}$ , $V_{2}$ , $V_{3}$ ... $V_{m}$ ，那么其中心点位置等于w= $\frac{V_{1}+V_{2}+V_{3}+...+V_{m}}{m}$

重复上述步骤。

通过判断平均距离d最小化和D最大化，做为迭代停止条件。

即各个类内的平均距离下一步小于上一步 $d_{i+1}<d_{i}$ ，并且各个类中心的距离 $D_{i+1}>D_{i}$ ,就可以继续迭代；

故最大化函数是：-d和D

各个类中心平均距离D的计算公式：

$D=\frac{\sum_{i,j}D_{ij} }{k*(k-1)}$

因为各个类中的点数不一，加权后的距离是

$D=\frac{\sum_{i,j}D_{ij}*n_{i} *n_{j}}{n*(n-1)}$

首先要明确一点，我们的距离函数要足够好，保证同一类相对距离较近，不同类之间中心的相对距离较远，我们希望达到的目的是：相近的点被聚集到同一类，这样同一类点到中心的平均距离d较近，不同类中心之间的平均距离D大，我们希望通过每一次迭代，d比以前更小，而D变大。

假设有k个类 $C_{1}，C_{2},C_{3}...C_{k}$ , $C_{2}$ , $C_{3}$ ... $C_{k}$ ，每类的点数为n1、n2、n3....nk， $C_{1}，C_{2},C_{3}...C_{k}$ 的内部有m个点为V1、V2、V3...Vm，那么 $C_{1}，C_{2},C_{3}...C_{k}$ 内部的平均距离为d= $\frac{V1+V2+V3...+Vm}{m}$ ，

各个类之间的平均距离 $D=\frac{\sum_{i,j}D_{ij} }{k*(k-1)}$ ，考虑到各个类之间的点数不一样，加权平均距离为 $D=\frac{\sum_{i,j}D_{ij}*n_{i} *n_{j}}{n*(n-1)}$ ，我们计算完d和D后，重新将各个点归类，那么就有 $d_{i}>d_{i+1}$ ， $D_{i}<D_{i+1}$

资料来源：吴军《数学之美》