Clustering – Probabilistic Model-Based Methods (1)

我们在这一节会介绍基于概率模型的分类方法。这种算法的思想是将数据划分为几种概率分布的混合模型，并且估计出参数，从而完成聚类。举例来说，假如现在有男生数名，女生数名，我们想要统计不同性别的身高分布。但是我们仅仅只是知道这些人的身高，不知道这些人的性别。我们先验地知道，身高分布会遵循高斯分布。那么我们就可以用这种方法来完成聚类，找到高斯分布所对应的均值和方差参数。

高斯混合模型

我们高中时候就知道对于当变量的数据只有一个维度时，高斯分布公式是对于 $x\in \mathbb{R}$$x\in \mathbb{R}$，我们有：

其中$\mu \in \mathbb{R}$$\mu\in\mathbb{R}$表示平均值，${\sigma }^2$$\sigma^2$表示方差。

那么对于一个高维的变量，假设变量$\mathbf{x}$$\mathbf{x}$有$d$$d$个维度，那么其对应的高斯分布的公式是：

推广过程如下：

对于一个一维标准正态分布。我们有：

那么对于两个独立的一维标准正态分布随机变量的联合分布，也就是二维标准正态分布：

那么我们把两个随机变量$x,y$$x,y$组合成一个向量$\mathbf{v}=[x,y{]}^T$$\mathbf{v}=[x,y]^T$,有

再推广到一般正态分布，我们令$\mathbf{v}=A(\mathbf{x}-\mu )$$\mathbf{v}=A(\mathbf x-\mu)$,则

可以证明这个分布的均值为$\mu$$\mu$，协方差是$(A^{T}A{)}^{-1}$$(A^TA)^{-1}$,同时我们的系数增加了$A$$A$的行列式的值。

由于$\mathbf{v}$$\mathbf{v}$服从标准正态分布，所以$\mathbf{v}$$\mathbf{v}$内元素的方差为1，$\mathbf{v}$$\mathbf v$的协方差是$E(\mathbf{v}{\mathbf{v}}^T)=I$$E(\mathbf{v}\mathbf v^T)=I$，$I$$I$是单位矩阵。

因为$x=A^{-1}\mathbf{v}+\mu$$x=A^{-1}\mathbf v+\mu$,加上$\mu$$\mu$也不影响协方差，所以$x$$x$的协方差为$E(A^{-1}\mathbf{v}{\mathbf{v}}^T{A^{-1}}^T)=A^{-1}E(\mathbf{v}{\mathbf{v}}^T){A^{-1}}^T=(A^{T}A{)}^{-1}$$E(A^{-1}\mathbf{v}\mathbf v^T {A^{-1}}^T) = A^{-1} E(\mathbf v\mathbf v^T) {A^{-1}}^T =(A^T A)^{-1}$

故我们令$\mathrm{\Sigma }=(A^{T}A{)}^{-1}$$\Sigma=(A^TA)^{-1}$,公式可以写成是

假设现在有$k$$k$个高斯分布，将他们放到一个坐标轴里叠加起来，每个高斯分布都乘上一个系数${\pi }_k$$\pi_k$，那么就有

其中$\sum _I{\pi }_I=1,{\pi }_I\in \mathbb{R},0\le {\pi }_I\le 1$$\sum_I{\pi_I}=1,\pi_I\in\mathbb{R},0\leq\pi_I\leq 1$

上面这个式子就是高斯混合模型，简单来说就是k个高斯的加权平均，权值是${\pi }_k$$\pi_k$。

EM算法

本节主要讨论高斯混合模型下的EM算法，参考 Pattern Recognition and Machine Learning。

首先我们引入一个隐变量$\mathbf{z}$$\mathbf{z}$，用来表示当前是哪一个分布。具体来说，$\mathbf{z}$$\mathbf{z}$是一个长度为$K$$K$的量，在某一个位置$\mathbf{z}$$\mathbf{z}$的值是1，其他位置的值都是0。用数学语言来表达就是,

其中$z_k$$z_k$表示第$k$$k$个位置，我们称这种表达方法是"1-of-K"的表达方法。

所以一个隐变量$\mathbf{z}$$\mathbf{z}$就有$K$$K$个状态。在这里我们就假设我们有$K$$K$个高斯分布，这样一个隐变量就可以对应一个高斯分布了。

我们再用${\pi }_k$$\pi_k$为$\mathbf{z}$$\mathbf{z}$赋值，表示取得某个隐变量$\mathbf{z}$$\mathbf{z}$的第$k$$k$个位置的值为1的概率。即:

很明显$0\le {\pi }_k\le 1，\sum _{k=1}^K{\pi }_k=1$$0\leq\pi_k\leq1，\sum_{k=1}^{K}\pi_k=1$。

可以列一个表格帮助理解，假设现在有5个高斯分布，那么我们可以设置五个长度为5的隐变量$\mathbf{z}$$\mathbf{z}$，分别在隐变量的不同位置设值为1，

下面表格里，为了简洁，这里暂时规定${\mathbf{z}}_k$$\mathbf{z}_k$表示$\mathbf{z}$$\mathbf{z}$的第k个位置的值为1，即${\mathbf{z}}_1=(1,0,0,0,0)$$\mathbf{z}_1=(1,0,0,0,0)$，

其中$\sum _{k=1}^5{\pi }_k=1$$\sum_{k=1}^{5}\pi_k=1$，其实这个表格就已经是一个概率分布了。

我们也可以把这个概率分布写成式子的形式:

表示隐变量$\mathbf{z}$$\mathbf{z}$的概率。

那么如何表达高斯混合模型里的某个高斯分布呢？可以用条件概率:

$p(\mathbf{x}|z_k=1)$$p(\mathbf{x}|z_k=1)$意思也就是高斯混合模型里多个高斯分布中的第$k$$k$个，或者是

用向量的方式表达。

根据联合概率分布的公式,我们可以知道$p(\mathbf{z},\mathbf{x})=p(\mathbf{z})p(\mathbf{x}|\mathbf{z})$$p(\mathbf{z},\mathbf{x})=p(\mathbf{z})p(\mathbf{x}|\mathbf{z})$,把公式(12)(14)带入可以得到

现在我们想要表达出$p(\mathbf{x})$$p(\mathbf{x})$,根据边缘分布，可以得到

对于公式(14)，一个隐变量只有一个位置是等于1的，也就是只有一个位置是有效的。对于公式(15),我们省略了指数，因为连加的变量$k$$k$将直接指向对应的高斯分布。

公式(15)的结果就是高斯混合模型的公式。但是推导的过程，我们同样得到了隐变量和变量的联合概率分布。这将会简化EM公式的推导。

另外我们还需要准备一下给定$\mathbf{x}$$\mathbf{x}$的条件下,$\mathbf{z}$$\mathbf{z}$的概率,我们使用贝叶斯公式:

这个式子表达了当我们在一个高斯混合模型中观察到$\mathbf{x}$$\mathbf{x}$以后，对应到第$k$$k$个高斯分布的概率。我们令:

$\gamma (z_k)$$\gamma(z_k)$可以理解为第$k$$k$个高斯分布对生成数据$\mathbf{x}$$\mathbf{x}$付出的贡献，或者是"责任"。

推荐阅读：

Clustering – Partitioning Methods