6.1 原理介绍

高斯混合聚类算法是假设训练数据服从不同的正态分布组合的一种算法。基于这一核心假设，本节推导了该算法的参数收敛过程，主要是各个正态分布的均值、方差以及每一个正态分布的权重，最后比较了K-Means聚类算法和GMM算法的区别和联系。

6.1.1 算法思想

现实中，有大量的随机变量服从高斯分布，如男性与女性的身高分布。男女身高是两个变量，分别服从不同参数的高斯分布（μ_k、δ_k，k=1,2），且两者相互独立。在这种情况下，可用GMM表示整个变量总体（两个变量的混合）的分布情况。

已知一维高斯概率密度函数为：

GMM的概率密度函数为：

其中K为高斯分布的个数，系数Q_k为某变量的分布服从第k个高斯分布的概率（即男、女身高混合样本中男性与女性的样本量占比），GMM的概率密度函数混合示意图如图6-1所示。为了使GMM的概率密度函数合规，其概率密度函数必须具有正则性， 因此有约束条件= 1。

为了从混合样本中聚类出服从不同高斯分布的样本， 可以利用EM算法对各个高斯概率密度函数的参数 （ Q_k、 μ_k与δ_k） 进行似然函数极大化迭代求解。 通过限制迭代次数或设立参数变化率收敛条件得到参数结果， 进而完成聚类。

6.1.2 算法流程

高斯混合聚类算法的流程中最重要的步骤是EM算法，GMM算法大致流程如图6-2所示。大致可以归结为以下几个步骤。

第1步：设定Q_k、μ_k与δ_k的初值。

第2步：建立对数似然函数，并结合Q_k等约束条件求解似然函数的极大值。

第3步：求解隐变量γ_nk，γ_nk为第n个样本x_n所服从的概率密度函数为第k个概率密度Q_kN（x_n,μ_k,δ_k）的可能性，即x_n属于第k个聚类结果的概率。该步骤为EM算法的E步。

第4步：给定γ_nk求解各个参数Q_k、μ_k与δ_k，这一步是M步。

第5步：迭代更新γ_nk，然后再一次求解各个参数Q_k、μ_k与δ_k，直至达到收敛条件。

6.1.3 EM算法理论与GMM参数推导

由GMM概率密度可得， 其对数似然函数为：

结合Q_k的约束条件，给出拉格朗日乘数法的求极大值目标函数：

对μ_k（k=1,2,…）求导得：

由求导链式法则得：

因为中每一项只有一种μ_k， 异名求导为0， 所以有：

为求极大值，令该导函数为0，则：

即：

令， γ_nk为第n个样本x_n所服从的概率密度函数为第k个概率密度Q_kN（x_n，μ_k，δ_k）的可能性， 即x_n属于第 k 个聚类结果的概率 （一般把γ_nk的计算称作 E 步）。则有：

故：

再将原目标函数对δ_k求导得：

因为中每一项只有一种δ_k， 异名求导为0， 所以有：

为求极大值，令该导函数为0，则：

代入，得

即：

故：

再将原目标函数对Q_k求导， 因为中每一项只有一种Q_k， 异名求导为0， 所以得：

为求极大值， 令该导函数为0， 则：= 0， 即：

两边同乘Q_k得：

代入

则：

将=-λQ_k两边对k求和得：

即：

式（6-20）因为k与n相互无关，故可交换求和顺序得：

即：-λ=N

因此：

经此求得的与是符合约束条件的， 在似然函数达到极大时估计得到的参数值 （一般把极大似然参数估计称作M步）。 因此， 每一次迭代求得的μ_k、 δ_k与Q_k都是这一次 （ t+1时刻） 在上一次 （ t时刻） 的基础上对该三项参数的更新， 即严格地写：

故在第一次迭代之前，需要人为给出各参数的初始值，同时也给定了聚类的个数。当某次迭代后参数的变化量小于一定程度时，认为当前参数为GMM参数的极大似然估计结果，也可以预先设定迭代次数，迭代完毕后的参数即估计结果。最后，根据γ_nk得到每个样本点的聚类结果。

另外， 根据可知每一次迭代后参数的变化由且只由γ_nk的变化引起。 参数的收敛意味着γ_nk的稳定， 而γ_nk表示第n个样本点x_n属于第k个聚类结果的概率。 因此， 最终某样本点x_n的类别应为{k｜γ_nk=max{γ_nk，k=1，2，…，K}}。

6.1.4 EM聚类与K-Means聚类的对比

在算法思想上，EM与K-Means具有较高的相似性，我们通过表格来进行对比，如表6-1所示。

另外，传统的K-Means将样本点与类中心点的欧式距离作为样本点聚类的评判标准。这必然使得聚类结果中每个类的范围呈圆形（三维是球状），这样的设定不一定是合理的。

在图6-3中，两个圈是K-Means的分类方法，但是右上条块的部分点就会被划分到左下的圈中，因为它与左下的类中心在距离上更接近，按理应该被分为左下类，但这明显不符合样本总体的视觉感受。如果知道这些样本所服从的概率密度函数形式，则可以利用EM算法进行更合理地聚类。