GMM 和 K-means

GMM Gaussian Mixture Model 高斯混合模型

每个GMM由K个Gaussian分布组成，每个Gaussian称为一个“Component”，这些Component 线性加成在一起就组成了GMM 的概率密度函数：

根据上面的式子，如果我们要从 GMM 的分布中随机地取一个点的话，实际上可以分为两步：首先随机地在这 K个Gaussian Component 之中选一个，每个 Component 被选中的概率实际上就是它的系数 pi(k) ，选中了 Component 之后，再单独地考虑从这个 Component 的分布中选取一个点就可以了──这里已经回到了普通的 Gaussian 分布，转化为了已知的问题。

那么如何用 GMM 来做 clustering 呢？其实很简单，现在我们有了数据，假定它们是由 GMM 生成出来的，那么我们只要根据数据推出 GMM 的概率分布来就可以了，然后 GMM 的 K 个 Component 实际上就对应了 K 个 cluster 了。根据数据来推算概率密度通常被称作 density estimation ，特别地，当我们在已知（或假定）了概率密度函数的形式，而要估计其中的参数的过程被称作“参数估计”。

参数与似然函数

现在假设我们有 N 个数据点，并假设它们服从某个分布（记作 p(x)），现在要确定里面的一些参数的值，例如，在 GMM 中，我们就需要确定 影响因子pi(k)、各类均值pMiu(k) 和 各类协方差pSigma(k) 这些参数。 我们的想法是，找到这样一组参数，它所确定的概率分布生成这些给定的数据点的概率最大，而这个概率实际上就等于 ，我们把这个乘积称作似然函数 (Likelihood Function)。通常单个点的概率都很小，许多很小的数字相乘起来在计算机里很容易造成浮点数下溢，因此我们通常会对其取对数，把乘积变成加和∑Ni=1logp(xi)，得到log-likelihood function 。接下来我们只要将这个函数最大化（通常的做法是求导并令导数等于零，然后解方程），亦即找到这样一组参数值，它让似然函数取得最大值，我们就认为这是最合适的参数，这样就完成了参数估计的过程。

下面让我们来看一看 GMM 的 log-likelihood function ：

由于在对数函数里面又有加和，我们没法直接用求导解方程的办法直接求得最大值。为了解决这个问题，我们采取之前从 GMM 中随机选点的办法：分成两步，实际上也就类似于K-means 的两步。

算法

1、估计数据由每个 Component 生成的概率（并不是每个 Component 被选中的概率）：对于每个数据 xi 来说，它由第 k 个 Component 生成的概率为

由于式子里的 和 也是需要我们估计的值，我们采用迭代法，在计算 的时候我们假定 和 均已知，我们将取上一次迭代所得的值（或者初始值）。

其中N（xi|μk,Σk）就是后验概率

2、估计每个 Component 的参数：现在我们假设上一步中得到的 就是正确的“数据 由 Component 生成的概率”，亦可以当做该 Component 在生成这个数据上所做的贡献，或者说，我们可以看作 这个值其中有 这部分是由 Component 所生成的。集中考虑所有的数据点，现在实际上可以看作 Component 生成了 这些点。由于每个 Component 都是一个标准的 Gaussian 分布，可以很容易分布求出最大似然所对应的参数值：

通过极大似然估计可以通过求到令参数=0得到参数pMiu，pSigma的值。

其中 Nk=∑N i=1 γ(i,k) ，并且 πk也顺理成章地可以估计为 Nk/N(这里的顺理成章要考证起来有很多要说)

3、重复迭代前面两步，直到似然函数的值收敛为止。

声明：这里完全可以对照EM算法的两步走，对应关系如下：

• 均值和方差对应θ
• Component 生成的概率为隐藏变量

• 最大似然函数

  

K-means

基本思想

聚类指事先并不知道任何样本的类别标号，希望通过某种算法来把一组未知类别的样本划分成若干类别，这在机器学习中被称作 unsupervised learning （无监督学习）。在本文中，我们关注其中一个比较简单的聚类算法：k-means算法。

通过迭代寻找k个聚类的一种划分方案，使得用这k个聚类的均值来代表相应各类样本时所得的总体误差最小。

k-means算法的基础是最小误差平方和准则。其代价函数是：

式中，μc(i)表示第i个聚类的均值。我们希望代价函数最小，直观的来说，各类内的样本越相似，其与该类均值间的误差平方越小，对所有类所得到的误差平方求和，即可验证分为k类时，各聚类是否是最优的。

算法

• 1) 上式的代价函数无法用解析的方法最小化，只能有迭代的方法。k-means算法是将样本聚类成 k个簇（cluster），其中k是用户给定的，其求解过程非常直观简单，具体算法描述如下：

  1、随机选取 k个聚类质心点

  2、重复下面过程直到收敛 {
  对于每一个样例 i，计算其应该属于的类：

  

  对于每一个类 j，重新计算该类的质心：

  

  时间复杂度：O(tKmn)，其中，t为迭代次数，K为簇的数目，m为记录数，n为维数

  空间复杂度：O((m+K)n)，其中，K为簇的数目，m为记录数，n为维数

• 2)具体过程

  2.0 k值选取

  k的值是用户指定的，表示需要得到的簇的数目。在运用Kmeans算法时，我们一般不知道数据的分布情况，不可能知道数据的集群数目，所以一般通过枚举来确定k的值。另外，在实际应用中，由于Kmean一般作为数据预处理，或者用于辅助分类贴标签，所以k一般不会设置很大。
  

  2.1 初始质心的选取

  Kmeans算法对初始质心的选取比较敏感，选取不同的质心，往往会得到不同的结果。初始质心的选取方法，常用以下两种的简单方法：一种是随机选取，一种是用户指定。 
  
  需要注意的是，无论是随机选取还是用户指定，质心都尽量不要超过原始数据的边界，即质心每一维度上的值要落在原始数据集每一维度的最小与最大值之间。
  

  2.2 质心的计算

  在Kmeans算法中，将簇中所有样本的均值作为该簇的质心。这也是Kmeans名字的由来吧。
  

  2.3 算法停止条件

  在两种情况下算法应该停止：一种是达到了指定的最大迭代次数，一种是算法已经收敛，即各个簇的质心不再发生变化。
  

例子

下图展示了对n个样本点进行K-means聚类的效果，这里k取2。

其伪代码如下：

创建k个点作为初始的质心点（随机选择）

当任意一个点的簇分配结果发生改变时

       对数据集中的每一个数据点

              对每一个质心

                     计算质心与数据点的距离

              将数据点分配到距离最近的簇

       对每一个簇，计算簇中所有点的均值，并将均值作为质心

算法分析

k-means算法比较简单，但也有几个比较大的缺点：

（1）k值的选择是用户指定的，不同的k得到的结果会有挺大的不同，如下图所示，左边是k=3的结果，这个就太稀疏了，蓝色的那个簇其实是可以再划分成两个簇的。而右图是k=5的结果，可以看到红色菱形和蓝色菱形这两个簇应该是可以合并成一个簇的：

（2）对k个初始质心的选择比较敏感，容易陷入局部最小值。例如，我们上面的算法运行的时候，有可能会得到不同的结果，如下面这两种情况。K-means也是收敛了，只是收敛到了局部最小值：

（3）存在局限性，如下面这种非球状的数据分布就搞不定了：

（4）数据库比较大的时候，收敛会比较慢。

解决

   k-means老早就出现在江湖了。所以以上的这些不足也被世人的目光敏锐的捕捉到，并融入世人的智慧进行了某种程度上的改良。例如问题（1）对k的选择可以先用一些算法分析数据的分布，如重心和密度等，然后选择合适的k。而对问题（2）有人提出了另一个成为二分k均值（bisecting k-means）算法，它对初始的k个质心的选择就不太敏感。

二分Kmeans算法

二分Kmeans算法（bisecting Kmeans）是为了克服Kmeans算法收敛于局部最小值的问题而提出的。该算法首先将所有点作为一个簇，然后将该簇一分为二。之后选择其中一个簇继续划分，选择哪一个簇进行划分取决于对其划分是否可以最大程度降低SSE的值，上述过程不断迭代，直到得到用户指定的簇数目为止。算法步骤如下：

将所有数据点看成一个簇

当簇数目小于k时

       对每一个簇

              计算总误差(sse_origin)

              在给定的簇上面进行k-均值聚类（k=2）

              计算将该簇一分为二后的总误差(sse_new)

       选择使得误差(sse_new)最小的那个簇进行划分操作

GMM与KMeans区别

1）从上面的分析中我们可以看到 GMM 和 K-means 的迭代求解法其实非常相似（都可以追溯到 EM 算法，下一次会详细介绍），因此也有和 K-means 同样的问题──并不能保证总是能取到全局最优，如果运气比较差，取到不好的初始值，就有可能得到很差的结果。对于 K-means 的情况，我们通常是重复一定次数然后取最好的结果，不过 GMM 每一次迭代的计算量比 K-means 要大许多，一个更流行的做法是先用 K-means （已经重复并取最优值了）得到一个粗略的结果，然后将其作为初值（只要将 K-means 所得的 centroids 传入 gmm 函数即可），再用 GMM 进行细致迭代。

2)k-means 的结果是每个数据点被 assign 到其中某一个 cluster 了，而 GMM 则给出这些数据点被 assign 到每个 cluster 的概率，又称作 soft assignment 。

如果大家想要代码的话，请看我的下一篇博客～