em算法与kmeans

1. EM Algorithm

EM算法和之前学的都不太一样，EM算法更多的是一种思想，所以后面用几个例子讲解，同时也会重点讲解GMM高斯混合模型。

极大似然估计这里面用的比较多。假设我们想要知道我们学生身高的分布，首先先假设这些学生都是符合高斯分布 我们要做的就是要估计这两个参数到底是多少。学生这么多，挨个挨个来肯定是不切实际的，所以自然就是抽样了。
为了统计学生身高，我们抽样200个人组成样本
我们需要估计的参数 首先估计一下抽到这两百人的概率一共是多少，抽到男生A的概率 抽到学生B的概率 所以同时抽到这两个学生的概率就是 那么同时抽到这200个学生的G概率
最后再取一个对数就好了：

似然函数的执行步骤：
1.得到似然函数
2.取对数整理
3.求导数，另导数为零
4.解方程得到解

首先引出凸函数的概念 那么就是凸函数，所以它的图像就是一个勾形的，看起来是一个凹函数，实际上是凸函数。

正常来看先是要引入一个最大似然函数： 但这样其实是和难求的，P(x|θ)完全混在了一起，根本求不出来，所以我们要引入一个辅助变量z。

所以我们引入隐变量的原因是为了转化成和这几个高斯模型相关的式子，否则无从下手。化简一下上式子： 既然z可以指定x，那么我们只需要求解出z就好了。
注意上面凸函数所提到的一个期望性质，这里就可以使用了。因为虽然优化了上面的式子，还是不能求出来，因为z变量实在是太抽象了，找不到一个合适的公式来表示它。EM的一个方法就是用优化下界函数的方法来达到优化目标函数的目的。
既然z很抽象，那么我们就需要一个转变一下。对于每一个样例x都会对应一个z，那么假设一个分布Q(z)是满足了z的分布的，而Q(z)满足的条件是 Qi意味着每一个x对应的z都会对应着一个Q了，这里有点复杂，再详细解释一下。一个x对应一组z，z是一个向量，但是每一个z又会分别对应一个一个分布Q。以为最后得到的z不会是一个数字，而是一个概率，也就是说Q(z)得到的是这个x样例属于这个类别的概率是多少。而z的数量，一个是当前有多少个分布混合在一起的数量。
再梳理一下：现在的样本是xi，那么每一个xi将会对应着一组的z，每一个xi同时也会对应着一个分布Qi，z其实就是反应了这个样本是来自于哪个分布的。比如这个x是A1分布做了3，A2分布做了5，那么z可能就是={3,5}。所以Qi(z)得到的是这个x属于这些个分布的概率，也就是说这些分布对x做了多少百分比的功，自然就是要等于1了。
还要注意的是，上面的 这个并不能得到Qi(z)就是分布对x做了多少功的结论，得到这个结论是后面下界函数与目标函数相等得到的。这里只是知道了总和等于1，因为是分布的总和嘛。
现在就到了公式的化简：
仔细看一下这个式子 这个式子其实就是求 的期望，假设 ，那么可以利用上面 。于是化简：
这个时候就得到了下界函数，上面也讲过了，想要相等，自然就是x要是常数，所以 既然 ，而且z也是一样的，因为一个样本嘛。所以上下加和（如果是离散的，那就sum一下，连续的那就积分，这里是离散的，所以就是sum一下）。于是有
于是有：

这就是整一个EM算法的框架了，可以看到其实没有比较具体的算法，大致上就是一个框架。那么问题来了，怎么样证明这东西是一个收敛的？？

可以直接把高斯混合模型代入EM框架里面。
存在多个高斯分布混合生成了一堆数据X，取各个高斯分布的概率是 ，第i个高斯分布的均值是 ，方差是 ，求法φ，μ，σ。
按照套路，第一个E-step求出Q，于是有：
意思就是求出第i个样本属于第j个分布的概率是多少。之后就是M-step了，就是化简了：

这里可能需要解释一下，根据 至于条件，因为很明显，z是隐变量，只是指明了x是属于哪个类别，和μ，Σ没有什么关系，所以直接忽略那两个参数了，所以P(z)是没有那两个参数的，z是代表了分布，所以每一个分布的概率肯定是包括了，所以就只有一个概率的参数。P(x|z)是本身的概率，就是已经知道分布是那个了，求属于这个分布的概率是多少，既然已经选定了分布那么自然就不需要再看φ了，因为φ是各个分布的概率。

现在有两个硬币AB，进行5次试验每一次投10次，并不知道是哪个硬币投的，求两种硬币的正面的概率。
首先E-step：
首先先初始化一下，
第一个试验选中A的概率：
同样求得
计算机出每一个试验的概率然后相加求均值。
之后就是M-step了：

方差的求解就不玩了，主要就是迭代求解μ和φ的值了。
首先是生成数据，4个高斯分布，每一个高斯分布的sigma都是一样的，不一样的只有μ和α，也就是φ，习惯上把前面的一个参数叫做权值，所以用α来表示。

这四个模型的比例分别是1:2:3:4，使用EM来找到他们属于的类别。

其实如果用kmeans聚类的话更加快速，但是这里还是用EM。
E-step：

就是按照公式来求解w即可，求解每一个分布对样本点做了多少的功，之后求单个样本点求比例。
M-step：

直接按照公式优化即可。

运行函数。看看结果：

结果其实还是相差不大。达到预期。

上面所讲的其实只是一种理解方法，在李航老师的统计学习方法里面是另一种比较厉害的解法：
1.E-step：求出Q函数。
2.M-step：利用Q函数求极大值。
其实这两种方法是完全一样的，Q函数就是下界函数，

EM和Kmeans算法其实很类似，事实上步骤基本可以用EM框架来替换，但是Kmeans算法是硬分类，说一不二，但是EM算法不太一样，是软分类，百分之几是那个，百分之几是这个。

缺点也还是有的：初值敏感，局部最优。因为存在了隐变量，所以导致了直接对x做极大似然是不可行的，log已经在sum的外面了。所以EM算法就转向了下界函数，而这种方法本来就不保证找到局部最优解。

如果将样本看作观察值，潜在类别看作是隐藏变量，那么聚类问题也就是参数估计问题。如果一个目标函数存在多个变量，那么梯度下降牛顿法这些逼近方法就用不了了。但我们可以使用坐标上升方法，固定一个变量，对另外一个求导数，然后替换最后逐步逼近极值点。对应到EM算法也是一样，E步求隐含的z变量，Mstep求解其他参数。

2. kmeans算法原理

kmeans算法原理如下：

K-means算法是一种典型的基于划分的聚类算法该算法具有运算速度快，执行过程简单的优点，在很多大数据处理领域得到了广泛的应用。

利用相似性度量方法来衡量数据集中所有数据之间的关系,将关系比较密切的数据划分到一个集合中。K-means算法首先需要选择K个初始化聚类中，计算每个数据对象到K个初始化聚类中心的距离。

2、缺点：需要人工预先确定初始K值，该值与实际的类另数可能不吻合。tK均值只能收敛到局部最优。因为求解这个代价函数是个NP问题，采用的是贪心策略，所以只能通过多次迭代收敛到局部最优，而不是全局最优。

K<均值的效果受初始值和离群点的影响大。因为k均值本质上是基于距离度量来划分的，均值和差大的维度将对数据的聚类结帆山塌果产生决定性的影响，因此需要进行归-化处理:此外，离群点或噪声对均值会产生影响，导致中心偏移,因此需要进行预处理。

3. EM算法怎么用在聚类上

k-means -> probabilistic model mixtures -> infinite probabilistic model mixtures(DP) 或者 infinite k-means

1. EM为含隐变量的概率模型提供了一个通用的框架。

2. 而用于聚类的模型其实都是离散混合模型。有限混合或者无限混合（狄利克雷过程），离散混合模型一定是含有隐变量的。所以EM就可以用来求解了。你先选一个聚类模型。你的任务简单，就没得选GMM或者DPGMM。若任务复杂些，可以搞分层的，或者时序的。然后用EM求解即可，求解过程中还会用到采样或者变分，自己看想用哪个。

   
   

4. EM算法详解

作为N大机器学习方法的一员，EM算法在各种书籍、博客、网上视频上被描述或者介绍，每次看完总感觉很多地方含糊不清，不能让一个初学者（有一定统计概率基础）接受。最近再B站上，看到 徐亦达老师的课程 ，EM算法这块讲解易于理解和接受，再结合PRML一书的关于混合模型和EM章节内容，对整个EM算法从具体的原理上面有了更深入的理解。
在下文中，更多的是通过公式推导和一些文字说明来梳理EM算法，尽量做到大家一看就明白。

极大似然估计是概率统计中，估计模型参数的一种方法，如果对似然概念以及极大似然估计的概念不理解，可参考维基网络 https://zh.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E4%BC%BC%E7%84%B6%E4%BC%B0%E8%AE%A1

这里，我们给出一个一维高斯函数的例子。如图1所示，一维空间里面离散分布的样本点其分布特点可以看成是一种高斯分布。那这些样本的高斯分布函数参数怎么求解呢？可以通过极大似然估计获得。

假设我们获取图1中数据样本集合为 ，其分布函数假设为一维高斯分布，即：

那所有数据的联合概率,即似然函数为：

对等式两边求log，即log-likelihood：

分别对参数求导：

可以得到：

通过上述方法，就可以得到基于样本数据和假设分布函数模型情况下，得到样本数据的分布函数。

从图2所示中，如果样本数据分布式蓝色点和橙色点的集合，如果依然用高斯分布去进行最大似然估计，得到的分布模型自然是不合适的。很显然，样本数据分布存在两个密集区（蓝色点和橙色点），如果能通过一种方法，确认样本数据里面的蓝色点和橙色点，然后分别对蓝色点集合进行一个高斯估计，对橙色点集进行另外一个高斯估计，两个高斯混合到一起，是不是比单个高斯能更好的匹配样本数据的分布情况。这种情况下的分布函数就是高斯混合模型。

这里我们先直接给出高斯混合模型的分布函数(多维)：

在图2例子中，提到如果给每一个数据样本能够先进行分类，即确定属于哪一个集中的簇中，就能比较容易的进行混合模型的求解。这说明了什么呢？我们可以理解，原始样本数据是不完全的（incomplete），引入一个K维的二值随机变量 ，这个变量采用"1-of-K"的表示方法，即K维中，只有一维是1，其余所有元素等于0。那么每一个样本数据，即有数据特征 ，再匹配一个分配变量 ，就可以将图2过程完整描述，即我们认为 和 联合在一起才是完全的（complete）。

数学表示上，我们利用边缘概率分布 和条件概率分布 定义联合概率分布 .
的边缘概率分布根据混合系数 进行赋值，即 ,使得边缘概率分布是合法，那么：

类似的，在给定 的一个特定的值，即针对某一簇的情况， 的条件概率分布是一个高斯分布，即

那么根据贝叶斯公式得到高斯混合模型：

由于我们只能观察样本数据 ,无法直接获取每个数据的分配变量 ,可理解 为潜在变量（latent）
依据极大似然函数的求解方法，我们可以对高斯混合模型写出数据的对数似然函数：

由于对数函数内部出现求和，这种情况是没有办法通过求导等于0的方式获取估计参数的解析解的。这种情况下，就需要用到EM算法，通过迭代方式获取估计参数。下面我们先从一般性问题上进行EM算法的理论描述，然后再利用EM算法推导高斯混合模型的计算方法。

EM算法叫做期望最大化方法，首先我们给出EM算法一般性结论或者说步骤，其具体分为两步，即E-step和M-step。

EM算法的步骤，通过高斯混合模型可以直观理解记忆。 是什么意思呢，其含义是在给定数据样本的情况下，潜在变量的概率情况。也就是说在高斯混合模型中，给定样本数据，我们推测样本属于哪一个高斯簇的概率情况。在确定分配情况后，每一个簇都用高斯进行估计，衡量估计好还是不好，用期望形式表示。这样可以帮助理解和记忆Q的定义。那EM算法怎么证明其收敛性呢？

我们要保证：

这样每次迭代可以使得似然函数随着参数变大，一直到似然函数不再增大或满足其他终止条件止。

那怎么保证呢？首先，利用贝叶斯公式有：

两边同时取log

然后两边同时用 求期望，可以得：

等式左边 和 没有关系， 是概率密度函数，积分是1，所以等式左边依然是 .
等式右边第一项就是E-step里面的Q函数，第二项我们记做H函数，则：

要保证 ，首先 ，那么是不是保证 满足，就一定有 ？答案是肯定的。（说明一下，这里面的H和Q函数都是关于 的函数，每一次迭代 是已知的，他不是变量）

那下面只要证明 就可以了。

因此可以得到 ，则整个EM算法的收敛性证毕。

注：这里用到了Jessian不等式，如果函数是convex的，则有函数的期望大于期望的函数，即 .

上述EM算法的证明，有一些技巧性，而这些技巧性有没有一种是在已知结论基础上硬凑的感觉呢，尤其是用 去求期望，就是为了去构造Q函数。那有没有更好的解释或者更为直观的方式来得到相同的结论呢？答案是有的。

首先，仍然用到：

我们稍微变个型，假设一个概率密度函数 :

两边同时用 求期望：

其中等式右边第一项，我们记做 ，可以称为ELOB，EvidenceLowerBound，第二项是 和 的KL散度。

如图4所示，当我固定参数 时候，ELOB就是关于 的泛函（只听过没学过，可理解为函数的函数），那ELOB的上界是什么呢？那首先要理解KL散度，KL散度是衡量两个概率分布之间的差异性，如果两个分布没有差异，则KL散度等于0，如果有差异则大于0，所以KL散度的最小值就是0，那ELOB的上界就是此刻的似然函数。

在EM算法中，当前迭代时，参数 ，则对于E-step，我们需要使得ELOB最大，即KL散度为0，如图5所示，其中 为 。此时，

对于M-Step，我们是需要得到新的估计参数，这个时候，固定 ,重新获得ELOB的最大值，这个时候的ELOB是什么样的呢？

右边第二项没有参数 ，所以固定 最大化ELOB，就等于最大化第一项，而第一项是什么呢？就是 函数。

如图6所示，我们最大化 函数，也就是最大化此次迭代的ELOB。在新的参数下， ，此刻 不变，所以和新的 在没有达到局部（或者全局）极大值的情况下，是两个不同的概率分布，即二者KL散度是大于0的，那此刻的似然函数等于此刻的KL散度加上此刻的ELOB，自然是有 。

从ELOB和KL散度的层面可以更好的理解EM算法的迭代过程。

PRML一书中，有图7所示的示意图，能比较形象的说明，EM算法的迭代过程。

图7中，红色曲线表示(不完整数据)对数似然函数，它的最大值是我们想要得到的。我们首先选择某个初始的参数值 ,然后在第一个E步骤中,我们计算潜在变量上的后验概率分布,得到了 的一个更小的下界，它的值等于在 处的对数似然函数值，用蓝色曲线表示。注意，下界与对数似然函数在 处以切线的方式连接，因此两条曲线的梯度相同。这个界是一个凹函数，对于指数族分布的混合分布来说，有唯一的最大值。在M步骤中,下界被最大化，得到了新的值 ,这个值给出了比 处更大的对数似然函数值。接下来的E步骤构建了一个新的下界,它在 处与对数似然函数切线连接,用绿色曲线表示。以这样的方式不停迭代，直到满足条件。

了解了EM算法，我们来详细推导高斯混合模型的E步和M步的内容。这一部分内容来自徐亦达老师的课件。由于公式太多了，我就放一些截图，供大家一起学习和参考。

徐亦达老师的课件在： https://github.com/roboticcam/machine-learning-notes/blob/master/em.pdf

后续关于EM算法的应用会举例以下几方面内容
(1)Kmeans和高斯混合模型
(2)EM算法应用之贝叶斯线性回归
(3)EM算法应用之PLSA
(4)EM算法应用之缺失数据参数估计问题

5. Kmeans聚类算法简介

由于具有出色的速度和良好的可扩展性，Kmeans聚类算法算得上是最着名的聚类方法。Kmeans算法是一个重复移动类中心点的过程，把类的中心点，也称重心(centroids)，移动到其包含成员的平均位置，然后重新划分其内部成员。k是算法计算出的超参数，表示类的数量；Kmeans可以自动分配样本到不同的类，但是不能决定究竟要分几个类。k必须是一个比训练集样本数小的正整数。有时，类的数量是由问题内容指定的。例如，一个鞋厂有三种新款式，它想知道每种新款式都有哪些潜在客户，于是它调研客户，然后从数据里找出三类。也有一些问题没有指定聚类的数量，最优的聚类数量是不确定的。后面我将会详细介绍一些方法来估计最优聚类数量。

Kmeans的参数是类的重心位置和其内部观测值的位置。与广义线性模型和决策树类似，Kmeans参数的最优解也是以成本函数最小化为目标。Kmeans成本函数公式如下：

μiμi是第kk个类的重心位置。成本函数是各个类畸变程度(distortions)之和。每个类的畸变程度等于该类重心与其内部成员位置距离的平方和。若类内部的成员彼此间越紧凑则类的畸变程度越小，反之，若类内部的成员彼此间越分散则类的畸变程度越大。求解成本函数最小化的参数就是一个重复配置每个类包含的观测值，并不断移动类重心的过程。首先，类的重心是随机确定的位置。实际上，重心位置等于随机选择的观测值的位置。每次迭代的时候，Kmeans会把观测值分配到离它们最近的类，然后把重心移动到该类全部成员位置的平均值那里。

2.1 根据问题内容确定

这种方法就不多讲了，文章开篇就举了一个例子。

2.2 肘部法则

如果问题中没有指定kk的值，可以通过肘部法则这一技术来估计聚类数量。肘部法则会把不同kk值的成本函数值画出来。随着kk值的增大，平均畸变程度会减小；每个类包含的样本数会减少，于是样本离其重心会更近。但是，随着kk值继续增大，平均畸变程度的改善效果会不断减低。kk值增大过程中，畸变程度的改善效果下降幅度最大的位置对应的kk值就是肘部。为了让读者看的更加明白，下面让我们通过一张图用肘部法则来确定最佳的kk值。下图数据明显可分成两类：

从图中可以看出，k值从1到2时，平均畸变程度变化最大。超过2以后，平均畸变程度变化显着降低。因此最佳的k是2。

2.3 与层次聚类结合

经常会产生较好的聚类结果的一个有趣策略是，首先采用层次凝聚算法决定结果粗的数目，并找到一个初始聚类，然后用迭代重定位来改进该聚类。

2.4 稳定性方法

稳定性方法对一个数据集进行2次重采样产生2个数据子集，再用相同的聚类算法对2个数据子集进行聚类，产生2个具有kk个聚类的聚类结果，计算2个聚类结果的相似度的分布情况。2个聚类结果具有高的相似度说明kk个聚类反映了稳定的聚类结构，其相似度可以用来估计聚类个数。采用次方法试探多个kk，找到合适的k值。

2.5 系统演化方法

系统演化方法将一个数据集视为伪热力学系统，当数据集被划分为kk个聚类时称系统处于状态kk。系统由初始状态k=1k=1出发，经过分裂过程和合并过程，系统将演化到它的稳定平衡状态 kiki ，其所对应的聚类结构决定了最优类数 kiki 。系统演化方法能提供关于所有聚类之间的相对边界距离或可分程度，它适用于明显分离的聚类结构和轻微重叠的聚类结构。

2.6 使用canopy算法进行初始划分

基于Canopy Method的聚类算法将聚类过程分为两个阶段

(1) 聚类最耗费计算的地方是计算对象相似性的时候，Canopy Method在第一阶段选择简单、计算代价较低的方法计算对象相似性，将相似的对象放在一个子集中，这个子集被叫做Canopy，通过一系列计算得到若干Canopy，Canopy之间可以是重叠的，但不会存在某个对象不属于任何Canopy的情况，可以把这一阶段看做数据预处理；

(2) 在各个Canopy内使用传统的聚类方法(如Kmeans)，不属于同一Canopy的对象之间不进行相似性计算。

从这个方法起码可以看出两点好处：首先，Canopy不要太大且Canopy之间重叠的不要太多的话会大大减少后续需要计算相似性的对象的个数；其次，类似于Kmeans这样的聚类方法是需要人为指出K的值的，通过(1)得到的Canopy个数完全可以作为这个k值，一定程度上减少了选择k的盲目性。

其他方法如贝叶斯信息准则方法(BIC)可参看文献[4]。

选择适当的初始质心是基本kmeans算法的关键步骤。常见的方法是随机的选取初始中心，但是这样簇的质量常常很差。处理选取初始质心问题的一种常用技术是：多次运行，每次使用一组不同的随机初始质心，然后选取具有最小SSE(误差的平方和)的簇集。这种策略简单，但是效果可能不好，这取决于数据集和寻找的簇的个数。

第二种有效的方法是，取一个样本，并使用层次聚类技术对它聚类。从层次聚类中提取kk个簇，并用这些簇的质心作为初始质心。该方法通常很有效，但仅对下列情况有效：(1)样本相对较小，例如数百到数千(层次聚类开销较大)；(2) kk相对于样本大小较小。

第三种选择初始质心的方法，随机地选择第一个点，或取所有点的质心作为第一个点。然后，对于每个后继初始质心，选择离已经选取过的初始质心最远的点。使用这种方法，确保了选择的初始质心不仅是随机的，而且是散开的。但是，这种方法可能选中离群点。此外，求离当前初始质心集最远的点开销也非常大。为了克服这个问题，通常该方法用于点样本。由于离群点很少(多了就不是离群点了)，它们多半不会在随机样本中出现。计算量也大幅减少。

第四种方法就是上面提到的canopy算法。

常用的距离度量方法包括：欧几里得距离和余弦相似度。两者都是评定个体间差异的大小的。

欧氏距离是最常见的距离度量，而余弦相似度则是最常见的相似度度量，很多的距离度量和相似度度量都是基于这两者的变形和衍生，所以下面重点比较下两者在衡量个体差异时实现方式和应用环境上的区别。

借助三维坐标系来看下欧氏距离和余弦相似度的区别：

从图上可以看出距离度量衡量的是空间各点间的绝对距离，跟各个点所在的位置坐标(即个体特征维度的数值)直接相关；而余弦相似度衡量的是空间向量的夹角，更加的是体现在方向上的差异，而不是位置。如果保持A点的位置不变，B点朝原方向远离坐标轴原点，那么这个时候余弦相似cosθ是保持不变的，因为夹角不变，而A、B两点的距离显然在发生改变，这就是欧氏距离和余弦相似度的不同之处。

根据欧氏距离和余弦相似度各自的计算方式和衡量特征，分别适用于不同的数据分析模型：欧氏距离能够体现个体数值特征的绝对差异，所以更多的用于需要从维度的数值大小中体现差异的分析，如使用用户行为指标分析用户价值的相似度或差异；而余弦相似度更多的是从方向上区分差异，而对绝对的数值不敏感，更多的用于使用用户对内容评分来区分用户兴趣的相似度和差异，同时修正了用户间可能存在的度量标准不统一的问题(因为余弦相似度对绝对数值不敏感)。

因为欧几里得距离度量会受指标不同单位刻度的影响，所以一般需要先进行标准化，同时距离越大，个体间差异越大；空间向量余弦夹角的相似度度量不会受指标刻度的影响，余弦值落于区间[-1,1]，值越大，差异越小。但是针对具体应用，什么情况下使用欧氏距离，什么情况下使用余弦相似度？

从几何意义上来说，n维向量空间的一条线段作为底边和原点组成的三角形，其顶角大小是不确定的。也就是说对于两条空间向量，即使两点距离一定，他们的夹角余弦值也可以随意变化。感性的认识，当两用户评分趋势一致时，但是评分值差距很大，余弦相似度倾向给出更优解。举个极端的例子，两用户只对两件商品评分，向量分别为(3,3)和(5,5)，这两位用户的认知其实是一样的，但是欧式距离给出的解显然没有余弦值合理。

我们把机器学习定义为对系统的设计和学习，通过对经验数据的学习，将任务效果的不断改善作为一个度量标准。Kmeans是一种非监督学习，没有标签和其他信息来比较聚类结果。但是，我们还是有一些指标可以评估算法的性能。我们已经介绍过类的畸变程度的度量方法。本节为将介绍另一种聚类算法效果评估方法称为轮廓系数(Silhouette Coefficient)。轮廓系数是类的密集与分散程度的评价指标。它会随着类的规模增大而增大。彼此相距很远，本身很密集的类，其轮廓系数较大，彼此集中，本身很大的类，其轮廓系数较小。轮廓系数是通过所有样本计算出来的，计算每个样本分数的均值，计算公式如下：

aa是每一个类中样本彼此距离的均值，bb是一个类中样本与其最近的那个类的所有样本的距离的均值。

输入：聚类个数k，数据集XmxnXmxn。

输出：满足方差最小标准的k个聚类。

(1) 选择k个初始中心点，例如c[0]=X[0] , … , c[k-1]=X[k-1]；

(2) 对于X[0]….X[n]，分别与c[0]…c[k-1]比较，假定与c[i]差值最少，就标记为i；

(3) 对于所有标记为i点，重新计算c[i]={ 所有标记为i的样本的每个特征的均值}；

(4) 重复(2)(3)，直到所有c[i]值的变化小于给定阈值或者达到最大迭代次数。

Kmeans的时间复杂度：O(tkmn)，空间复杂度：O((m+k)n)。其中，t为迭代次数，k为簇的数目，m为样本数，n为特征数。

7.1 优点

(1). 算法原理简单。需要调节的超参数就是一个k。

(2). 由具有出色的速度和良好的可扩展性。

7.2 缺点

(1). 在 Kmeans 算法中 kk 需要事先确定，这个 kk 值的选定有时候是比较难确定。

(2). 在 Kmeans 算法中，首先需要初始k个聚类中心，然后以此来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果。多设置一些不同的初值，对比最后的运算结果，一直到结果趋于稳定结束。

(3). 该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。

(4). 对离群点很敏感。

(5). 从数据表示角度来说，在 Kmeans 中,我们用单个点来对 cluster 进行建模，这实际上是一种最简化的数据建模形式。这种用点来对 cluster 进行建模实际上就已经假设了各 cluster的数据是呈圆形(或者高维球形)或者方形等分布的。不能发现非凸形状的簇。但在实际生活中，很少能有这种情况。所以在 GMM 中，使用了一种更加一般的数据表示，也就是高斯分布。

(6). 从数据先验的角度来说，在 Kmeans 中,我们假设各个 cluster 的先验概率是一样的,但是各个 cluster 的数据量可能是不均匀的。举个例子,cluster A 中包含了10000个样本,cluster B 中只包含了100个。那么对于一个新的样本,在不考虑其与A cluster、 B cluster 相似度的情况,其属于 cluster A 的概率肯定是要大于 cluster B的。

(7). 在 Kmeans 中，通常采用欧氏距离来衡量样本与各个 cluster 的相似度。这种距离实际上假设了数据的各个维度对于相似度的衡量作用是一样的。但在 GMM 中，相似度的衡量使用的是后验概率 αcG(x|μc,∑c)αcG(x|μc,∑c) ，通过引入协方差矩阵,我们就可以对各维度数据的不同重要性进行建模。

(8). 在 Kmeans 中，各个样本点只属于与其相似度最高的那个 cluster ，这实际上是一种 hard clustering 。

针对Kmeans算法的缺点，很多前辈提出了一些改进的算法。例如 K-modes 算法，实现对离散数据的快速聚类，保留了Kmeans算法的效率同时将Kmeans的应用范围扩大到离散数据。还有K-Prototype算法，可以对离散与数值属性两种混合的数据进行聚类，在K-prototype中定义了一个对数值与离散属性都计算的相异性度量标准。当然还有其它的一些算法，这里我 就不一一列举了。

Kmeans 与 GMM 更像是一种 top-down 的思想，它们首先要解决的问题是，确定 cluster 数量，也就是 k 的取值。在确定了 k 后,再来进行数据的聚类。而 hierarchical clustering 则是一种 bottom-up 的形式，先有数据，然后通过不断选取最相似的数据进行聚类。

6. 如何正确选择聚类算法

作者 | Josh Thompson

来源 | 数据派THU

Choosing the Right Clustering Algorithm for your Dataset - KDnuggets

聚类算法十分容易上手，但是选择恰当的聚类算法并不是一件容易的事。

数据聚类是搭建一个正确数据模型的重要步骤。数据分析应当根据数据的共同点整理信息。然而主要问题是，什么通用性参数可以给出最佳结果，以及什么才能称为“最佳”。

本文适用于菜鸟数据科学家或想提升聚类算法能力的专家。下文包括最广泛使用的聚类算法及其概况。根据每种方法的特殊性，本文针对其应用提出了建议。

四种基本算法以及如何选择

聚类模型可以分为四种常见的算法类别。尽管零零散散的聚类算法不少于100种，但是其中大部分的流行程度以及应用领域相对有限。

基于整个数据集对象间距离计算的聚类方法，称为基于连通性的聚类（connectivity-based）或层次聚类。根据算法的“方向”，它可以组合或反过来分解信息——聚集和分解的名称正是源于这种方向的区别。最流行和合理的类型是聚集型，你可以从输入所有数据开始，然后将这些数据点组合成越来越大的簇，直到达到极限。

层次聚类的一个典型案例是植物的分类。数据集的“树”从具体物种开始，以一些植物王国结束，每个植物王国都由更小的簇组成（门、类、阶等）。

层次聚类算法将返回树状图数据，该树状图展示了信息的结构，而不是集群上的具体分类。这样的特点既有好处，也有一些问题：算法会变得很复杂，且不适用于几乎没有层次的数据集。这种算法的性能也较差：由于存在大量的迭代，因此整个处理过程浪费了很多不必要的时间。最重要的是，这种分层算法并不能得到精确的结构。

同时，从预设的类别一直分解到所有的数据点，类别的个数不会对最终结果产生实质性影响，也不会影响预设的距离度量，该距离度量粗略测量和近似估计得到的。

根据我的经验，由于简单易操作，基于质心的聚类（Centroid-based）是最常出现的模型。 该模型旨在将数据集的每个对象划分为特定的类别。 簇数（k）是随机选择的，这可能是该方法的最大问题。 由于与k最近邻居（kNN）相似，该k均值算法在机器学习中特别受欢迎。

计算过程包括多个步骤。首先，输入数据集的目标类别数。聚类的中心应当尽可能分散，这有助于提高结果的准确性。

其次，该算法找到数据集的每个对象与每个聚类中心之间的距离。最小坐标距离（若使用图形表示）确定了将对象移动到哪个群集。

之后，将根据类别中所有点的坐标平均值重新计算聚类的中心。重复算法的上一步，但是计算中要使用簇的新中心点。除非达到某些条件，否则此类迭代将继续。例如，当簇的中心距上次迭代没有移动或移动不明显时，聚类将结束。

尽管数学和代码都很简单，但k均值仍有一些缺点，因此我们无法在所有情景中使用它。缺点包括：

因为优先级设置在集群的中心，而不是边界，所以每个集群的边界容易被疏忽。 无法创建数据集结构，其对象可以按等量的方式分类到多个群集中。 需要猜测最佳类别数（k），或者需要进行初步计算以指定此量规。

相比之下，期望最大化算法可以避免那些复杂情况，同时提供更高的准确性。简而言之，它计算每个数据集点与我们指定的所有聚类的关联概率。用于该聚类模型的主要工具是高斯混合模型（GMM）–假设数据集的点服从高斯分布。

k-means算法可以算是EM原理的简化版本。它们都需要手动输入簇数，这是此类方法要面对的主要问题。除此之外，计算原理（对于GMM或k均值）很简单：簇的近似范围是在每次新迭代中逐渐更新的。

与基于质心的模型不同，EM算法允许对两个或多个聚类的点进行分类-它仅展示每个事件的可能性，你可以使用该事件进行进一步的分析。更重要的是，每个聚类的边界组成了不同度量的椭球体。这与k均值聚类不同，k均值聚类方法用圆形表示。但是，该算法对于不服从高斯分布的数据集根本不起作用。这也是该方法的主要缺点：它更适用于理论问题，而不是实际的测量或观察。

最后，基于数据密度的聚类成为数据科学家心中的最爱。

这个名字已经包括了模型的要点——将数据集划分为聚类，计数器会输入ε参数，即“邻居”距离。因此，如果目标点位于半径为ε的圆（球）内，则它属于该集群。

具有噪声的基于密度的聚类方法（DBSCAN）将逐步检查每个对象，将其状态更改为“已查看”，将其划分到具体的类别或噪声中，直到最终处理整个数据集。用DBSCAN确定的簇可以具有任意形状，因此非常精确。此外，该算法无需人为地设定簇数 —— 算法可以自动决定。

尽管如此，DBSCAN也有一些缺点。如果数据集由可变密度簇组成，则该方法的结果较差；如果对象的位置太近，并且无法轻易估算出ε参数，那么这也不是一个很好的选择。

总而言之，我们并不能说选择了错误的算法，只能说其中有些算法会更适合特定的数据集结构。为了采用最佳的（看起来更恰当的）算法，你需要全面了解它们的优缺点。

例如，如果某些算法不符合数据集规范，则可以从一开始就将其排除在外。为避免繁琐的工作，你可以花一些时间来记住这些信息，而无需反复试验并从自己的错误中学习。

我们希望本文能帮助你在初始阶段选择最好的算法。继续这了不起的工作吧！

7. EM算法及其应用GMM/pLSA/LDA

从样本观察数据（显性特征x）中，找出样本的模型参数（ ）。 最常用的方法就是极大化模型分布的对数似然函数。

是样本特征和label的联合分布， ，为了使得估计的结果泛化能力更好，我们将 分解为 ， 就是隐变量。

这类问题有：

以上问题，主要是通过引入隐变量，把样本表述为隐变量的分布，从而简化每个样本点表述。对于此问题通用的数学描述为：

给定一个样本集 ，我们假设观察到的 还对应着隐含变量的概率分布 ，记 。则该模型 的对数似然函数为：

而 根据具体的问题来定义。

目标是求得参数 ，使得对数似然函数最大：

这时候，交叉熵为：

优化目标为：

它的梯度是

都是概率分布，即大于0且满足：

直接梯度下降是行不通的，这就需要借助EM算法。

对于最大似然函数的参数求解：

是隐变量，观测不到，为了求解上式，假设我们知道 的概率分布 ：

根据 Jensen 不等式 [1]，对于任意分布 都有：

且上面的不等式在 为常数时取等号。

（备注：关键的点就是Jensen不等式在x为常数时取等号（x的所有值重叠，等于1个值）。这里正好对应隐变量的分布的确定，即E步求解的隐变量的分布）

于是我们就得到了 的一个下界函数。我们要想套用上面的算法，还要让这个不等式在 处取等号，这就这要求在 时 为常数，即 。由于 是一个概率分布，必须满足 ，所以这样的 只能是 。那我们就把 代入上式，得到：

最大化这个下界函数：

其中倒数第二步是因为 这一项与 无关，所以就直接扔掉了。这样就得到了本文第二节 EM 算法中的形式——它就是这么来的。

以上就是 EM 了。至于独立同分布的情况推导也类似。

[1]
Jensen 不等式：

对于凸函数 ，其函数的期望大于等于期望的函数

若 是严格凸的，则上式取等号当前仅当 为常数。

在这里 函数是严格 凹 的，所以要把上面的不等号方向

假设某个数据分布是由K个高斯分布加权叠加而来：

目标是，求出这K个高斯分布及其权重。

换一种说法，也就是，用K个高斯分布的加权和来拟合数据分布

相比于K-means，只是把原本样本一定属于某一类改成了一个样本属于某类的概率。K-means的结果是把每个数据点assign到其中某一个cluster,而GMM则是给出每个数据点被assign到每一个cluster的概率，又称作soft assignment。

pLSA 模型有两个 基本的设定：

即：

而我们感兴趣的正是其中的 和 ，即文章的主题分布，和主题的词分布。记 ， 表示我们希望估计的模型参数（模型中共有 个参数）。

根据最大log似然估计法，我们要求的就是

这里由于 这一项与 无关，在 中可以被直接扔掉。 [1]

因此

这里出现了 套 的形式，导致很难直接拿它做最大似然。但假如能观察到 ，问题就很简单了。于是我们想到根据 EM 算法 ，可以用下式迭代逼近 ：

其中

在 E-step 中，我们需要求出 中除 外的其它未知量，也就是说对于每组 我们都需要求出 。 根据贝叶斯定理贝叶斯定理，我们知道：

而 和 就是上轮迭代求出的 。这样就完成了 E-step。

接下来 M-step 就是要求 了。利用基本的微积分工具 [2]，可以分别对每对 和 求出：

以上就是 pLSA 算法了。

EM求解方法：

E-step:

M-step:

在pLSA中用极大似然估计的思想去推断参数（文档的主题分布和主题的词分布），而LDA把这两参数视为概率分布，其先验信息为dirichlet分布。因此，在数据量不大的时候，LDA能缓解过拟合问题，而在数据量很大的时候，pLSA是比较好的选择。

LDA中，估计Φ、Θ这两未知参数可以用变分(Variational inference)-EM算法，也可以用gibbs采样，前者的思想是最大后验估计MAP，后者的思想是贝叶斯估计。

https://spaces.ac.cn/archives/4277

EM算法原理总结

Probabilistic latent semantic analysis (pLSA)

A Note on EM Algorithm and PLSA --- Xinyan Lu

李航-统计机器学习第一版

高斯混合模型

github
推荐我的开源项目 exFM c++ deepFM