聚类模型

1、层次聚类

2、原型聚类-K-means

3、模型聚类-GMM

4、EM算法-LDA主题模型

5、密度聚类-DBSCAN

6、图聚类-谱聚类

四、EM算法

一、EM算法

​ EM算法是一种迭代算法，用于带隐变量的概率模型参数的极大似然估计，是无监督学习中一大类算法求解的算法。EM算法每次迭代由两步组成，E步：假设隐变量和特征变量的联合分布P(x,z;θ)$P(x,z;\theta )$，求解样本关于隐变量z$z$的概率函数（使Jensen不等式等号成立），M步：在已知样本(x,z)$(x,z)$的联合分布（确定样本特征和类标），采用极大似然估计最大化似然函数求解参数θ$\theta$。

在讨论EM算法之前，先介绍Jensen inequality（由凸函数性质导出）

假设f是定义在实数上的凸函数，由凸函数的定义有：

严格凸函数则严格大于，凸函数的判定是其二阶可微的话，其Hesse矩阵半正定。对凸函数的性质推广有：

当λi${\lambda }_i$表示f(x(i)),x(i)$f(x^{(i)}),x^{(i)}$的概率时，那么有：

当且仅当：p(f(x)=c)=1$p(f(x)=c)=1$，即f(x)$f(x)$为常数函数，等号成立。

反之，对于凹函数不等式方向相反。

现在来看EM算法，给定训练样本{x(1),x(2),..x(m)}$\{x^{(1)},x^{(2)},..x^{(m)}\}$，引入隐含的类别标签z(i)$z^{(i)}$，在有监督方法中，最大对数似然函数L=p(z|x;θ)$L=p(z|x;\theta )$，同样这里最大化对数似然函数的L=(x(i);θ)$L=(x^{(i)};\theta )$在隐变量z(i)$z^{(i)}$的全期望：

其中Qi(z(i))$Q_i(z^{(i)})$为样本的隐变量z(i)$z^{(i)}$的概率分布，∑zQi(z(i))=1,Qi(z(i))≥0$\sum _z{Q}_i(z^{(i)})=1,Q_i(z^{(i)})\ge 0$。不同Q(z)$Q(z)$选择，会得到EM在不同情况下的模型，比如高斯混合，朴素贝叶斯混，LDA等。

因为log$log$函数是一个严格凹函数，由Jessen不等式有：

其中g(x)=P(x(i),z(i)|θ)Qi(z(i))$g(x)=\frac{P(x^{(i)},z^{(i)}|\theta )}{Q_i(z^{(i)})}$，因此当且仅当，g(x)=c$g(x)=c$，等号成立。

因为∑zQi(z(i))=1,Qi(z(i))≥0$\sum _z{Q}_i(z^{(i)})=1,Q_i(z^{(i)})\ge 0$，所以Qi(z(i))$Q_i(z^{(i)})$可以看做是样本关于隐变量z$z$的概率分布，等于x,z$x,z$联合概率归一化，即比上联合概率对z$z$的全期望：

因此，EM算法的第一步就是计算在给定θ$\theta$下隐变量z$z$的条件概率。

当已知Q(z)$Q_{(}z)$之后，且Jessen不等式等号成立，回过头来再最大化似然函数：

因此，EM算法的极大似然估计可以看作是坐标上升过程，第一步在给定的参数θ$\theta$下最大化似然函数L(Q(z);θ)$L(Q(z);\theta )$，第二步则是在当前的Q(z)$Q(z)$下最大化似然函数L(θ;Q(z))$L(\theta ;Q(z))$。

收敛性：

下面的第一个不等号由由最大似然估计得到θ(i+1)${\theta }^{(i+1)}$，第二个不等号Jessen不等式得到Q∗(z)=p(z(i)|x(i);θ)$Q^{\ast }(z)=p(z^{(i)}|x^{(i)};\theta )$，但是求解过程是先由Jessen不等式确定似然函数的下界，后最大似然函数下界。

EM算法的一般流程：

E-step：（固定参数下，求隐变量条件分布）

M-step：（最大化似然函数下界）

EM求解的过程大致如图所示，是否能收敛到全局最优，取决于目标函数是否为凸函数：

从上图可以看出，EM算法的思想也是坐标上升的思想，即固定一组变量求解另一组变量，不断地迭代。比较特殊的，EM算法针对于带隐变量的概率模型参数的极大似然估计，求解过程又称“期望最大化”，第一步求期望，第二步最大化，这是带隐变量的概率模型特有的，不是EM算法的特点。

二、EM算法例子-高斯混合，朴素贝叶斯混合

高斯混合模型

​ 为什么采用EM算法求解高斯混合模型，回顾高斯混合模型的目标函数，我们发现log$log$函数在求和外面。特别的情况是当类标签已知，像高斯判别模型那么进行参数估计，然而在混合高斯模型中。而隐变量却是未知，所以我们很难直接优化，采用EM算法的Jessen不等式，我们将log$log$函数放到里面，并使等号成立，对目标函数进行转化：

其中Qi(z(i))$Q_i(z^{(i)})$条件概率分布P(z|x;θ)$P(z|x;\theta )$。

下面从EM思想来看高斯混合模型，给出高斯混合模型最大似然估计计算出参数的推导过程：

E-step:（固定参数下，求隐变量条件分布）

其中p(x|z)$p(x|z)$服从高斯分布，p(z)$p(z)$服从伯努利分布。

M-step:（最大化似然函数下界）

对μ,Σ,ϕ$\mu ,\mathrm{\Sigma },\varphi$求导：

令导数为0，有：

对目标函数求解参数ϕ$\varphi$，去掉无关项，有：

由∑kj=1ϕj=1$\sum _{j=1}^k{\varphi }_j=1$，对其拉格朗日函数求导：

令其导数为0，有：

所以，ϕj∝∑mi=1w(i)j${\varphi }_j\propto \sum _{i=1}^m{w}_j^{(i)}$，又∑jϕj=1$\sum _j{\varphi }_j=1$，所以得−β=∑mi=1∑kj=1w(i)j=m$-\beta =\sum _{i=1}^m\sum _{j=1}^k{w}_j^{(i)}=m$

所以：