6.2.高斯混合聚类

EM算法

期望极大算法.它是一种迭代算法,用于含有隐变量的概率模型参数估计.EM算法的每次迭代由两步组成：E步求期望,M步求极大.
三硬币模型：已知三枚硬币A,B,C.这些硬币正面出现的概率分别为 $\pi,p,q$ ,现进行如下的实验

graph TD
x-->A
A-->|p|B
A-->|n|C
B-->|p|D[1]
B-->|n|E[0]
C-->|p|D[1]
C-->|n|E[0]
D-->y
E-->y

独立重复地n次试验,观测结果为：1,1,0,1,0,...,0,1.
y是观测变量,表示一次试验观察到的结果是1或者0.z是隐变量,表示未观测到的投掷硬币A的结果. $\theta=(\pi,p,q)$ 是模型参数.观测数据表示为
$Y_{seq}=(y_1,y_2,...,y_n)$
$P(y;\theta)=\sum_{Z}P(y,z;\theta)=\sum_{Z}P(z;\theta)P(y|z;\theta)=\pi p^y(1-p)^{1-y}+(1-\pi)q^y(1-q)^{1-y}$
$P(Y_{seq};\theta)=\prod_{j=1}^nP(y_j;\theta)=\prod_{j=1}^n(\pi p^{y_j}(1-p)^{1-y_j}+(1-\pi)q^{y_j}(1-q)^{1-y_j})$
$\hat{\theta}=\mathop{\arg\max}\limits_{\theta}\log{P(Y_{seq};\theta)}$
EM算法先给出参数的初值： $\theta^{<0>}=(\pi^{<0>},p^{<0>},q^{<0>})$ .设第i次迭代参数的估计值为 $\theta^{}=(\pi^{},p^{},q^{})$ ,则第i+1次迭代如下
- E步：计算模型在参数 $\theta^{}$ 下,观察数据 $y_i$ 来自于投掷硬币B的概率
$\pi_j^{<i+1>}=P(z=1|y=y_j)=\frac{\pi p^{y_j}(1-p)^{1-y_j}}{\pi p^{y_j}(1-p)^{1-y_j}+(1-\pi)q^{y_j}(1-q)^{1-y_j}}$
- M步：更新模型参数的新估计值如下
$\pi^{<i+1>}=\frac{1}{n}\sum_{j=1}^{n}\pi_j^{<i+1>}$
$p^{<i+1>}=\frac{\sum_{j=1}^{n}\pi_j^{<i+1>}y_i}{\sum_{j=1}^{n}\pi_j^{<i+1>}}$
$q^{<i+1>}=\frac{\sum_{j=1}^{n}(1-\pi_j^{<i+1>})y_i}{\sum_{j=1}^{n}(1-\pi_j^{<i+1>})}$

高斯混合模型

$p(\overrightarrow{x})=\sum_{k=1}^{K}\alpha _kp(\overrightarrow{x};\overrightarrow{\mu}_k,\Sigma_k)$
$\overrightarrow{x}\in{R}^n$
$p(Z=k)=\alpha_k$
$Z\in\{1,2,...,K\};\alpha_k>0;\sum_{k=1}^{K}\alpha_k=1$
$\overrightarrow{\mu}_k$ 为n维均值向量, $\Sigma_k$ 是 $n\times{n}$ 的协方差矩阵,是第k个成分对应的高斯分布的参数.
$D=\{\overrightarrow{x}_1,\overrightarrow{x}_2,...,\overrightarrow{x}_N\}$
$p(Z=k|\overrightarrow{x}_i)=\frac{p(Z=k)p(\overrightarrow{x}_i|Z=k)}{p(\overrightarrow{x}_i)}=\frac{\alpha _kp(\overrightarrow{x}_i;\overrightarrow{\mu}_k,\Sigma_k)}{\sum_{l=1}^{K}\alpha _lp(\overrightarrow{x}_i;\overrightarrow{\mu}_l,\Sigma_l)}$
$\lambda_i=\mathop{\arg\max}\limits_{k}p(Z=k|\overrightarrow{x}_i)$
$\lambda_i$ 为簇标记.

输入

1. 样本集
$D=\{\overrightarrow{x}_1,\overrightarrow{x}_2,...,\overrightarrow{x}_N\}$
$\overrightarrow{x}_i=(x_{i}^{(1)},x_{i}^{(2)},...,x_{i}^{(n)})^T$
$i=1,2,...,N$
2. 高斯混合成分个数
$K$

输出

高斯混合模型参数.

算法步骤

1. 取参数的初始值
$\theta^{<0>}=(\alpha_1^{<0>},...,\alpha_K^{<0>},\mu_1^{<0>},...,\mu_K^{<0>},\Sigma_1^{<0>},...,\Sigma_K^{<0>})$
2. 迭代直至算法收敛
- E步：根据当前模型参数,计算分模型k对观测数据 $\overrightarrow{x}_j$ 的响应度
$\hat\gamma_{jk}=\frac{\alpha _k^{}p(\overrightarrow{x}_j\overrightarrow{\mu}_k^{},\Sigma_k^{})}{\sum_{l=1}^{K}\alpha _l^{}p(\overrightarrow{x}_j;\overrightarrow{\mu}_l^{},\Sigma_l^{})}$
$j=1,2,...,N;k=1,2,...,K$
- M步：计算新一轮迭代的模型参数
$\alpha_k^{<i+1>}=\frac{1}{N}\sum_{j=1}^N\hat\gamma_{jk}$
$\overrightarrow{\mu}_k^{<i+1>}=\frac{\sum_{j=1}^N\hat\gamma_{jk}\overrightarrow{x}_j}{\sum_{j=1}^N\hat\gamma_{jk}}$
$\Sigma_k^{<i+1>}=\frac{\sum_{j=1}^N\hat\gamma_{jk}(\overrightarrow{x}_j-\overrightarrow{\mu}_k^{<i+1>})(\overrightarrow{x}_j-\overrightarrow{\mu}_k^{<i+1>})^T}{\sum_{j=1}^N\hat\gamma_{jk}}$
$k=1,2,...,K$