28丨EM聚类（上）：如何将一份菜等分给两个人？

Feb 15, 2019

28丨EM聚类（上）：如何将一份菜等分给两个人？-极客时间



下载APP





关闭

讲堂部落提薪训练营云原生训练营架构实战营企业版极客商城兑换中心 App下载浏览器插件

渠道合作

推荐作者

28丨EM聚类（上）：如何将一份菜等分给两个人？

2019-02-15 陈旸来自北京

《数据分析实战45讲》

课程介绍



讲述：陈旸

时长08:47大小8.05M



今天我来带你学习 EM 聚类。EM 的英文是 Expectation Maximization，所以 EM 算法也叫最大期望算法。
我们先看一个简单的场景：假设你炒了一份菜，想要把它平均分到两个碟子里，该怎么分？
很少有人用称对菜进行称重，再计算一半的分量进行平分。大部分人的方法是先分一部分到碟子 A 中，然后再把剩余的分到碟子 B 中，再来观察碟子 A 和 B 里的菜是否一样多，哪个多就匀一些到少的那个碟子里，然后再观察碟子 A 和 B 里的是否一样多……整个过程一直重复下去，直到份量不发生变化为止。
你能从这个例子中看到三个主要的步骤：初始化参数、观察预期、重新估计。首先是先给每个碟子初始化一些菜量，然后再观察预期，这两个步骤实际上就是期望步骤（Expectation）。如果结果存在偏差就需要重新估计参数，这个就是最大化步骤（Maximization）。这两个步骤加起来也就是 EM 算法的过程。
EM 算法的工作原理说到 EM 算法，我们先来看一个概念“最大似然”，英文是 Maximum Likelihood，Likelihood 代表可能性，所以最大似然也就是最大可能性的意思。
什么是最大似然呢？举个例子，有一男一女两个同学，现在要对他俩进行身高的比较，谁会更高呢？根据我们的经验，相同年龄下男性的平均身高比女性的高一些，所以男同学高的可能性会很大。这里运用的就是最大似然的概念。
最大似然估计是什么呢？它指的就是一件事情已经发生了，然后反推更有可能是什么因素造成的。还是用一男一女比较身高为例，假设有一个人比另一个人高，反推他可能是男性。最大似然估计是一种通过已知结果，估计参数的方法。
那么 EM 算法是什么？它和最大似然估计又有什么关系呢？EM 算法是一种求解最大似然估计的方法，通过观测样本，来找出样本的模型参数。
再回过来看下开头我给你举的分菜的这个例子，实际上最终我们想要的是碟子 A 和碟子 B 中菜的份量，你可以把它们理解为想要求得的模型参数。然后我们通过 EM 算法中的 E 步来进行观察，然后通过 M 步来进行调整 A 和 B 的参数，最后让碟子 A 和碟子 B 的参数不再发生变化为止。
实际我们遇到的问题，比分菜复杂。我再给你举个一个投掷硬币的例子，假设我们有 A 和 B 两枚硬币，我们做了 5 组实验，每组实验投掷 10 次，然后统计出现正面的次数，实验结果如下：
投掷硬币这个过程中存在隐含的数据，即我们事先并不知道每次投掷的硬币是 A 还是 B。假设我们知道这个隐含的数据，并将它完善，可以得到下面的结果：
我们现在想要求得硬币 A 和 B 出现正面次数的概率，可以直接求得：
而实际情况是我不知道每次投掷的硬币是 A 还是 B，那么如何求得硬币 A 和硬币 B 出现正面的概率呢？
这里就需要采用 EM 算法的思想。
1. 初始化参数。我们假设硬币 A 和 B 的正面概率（随机指定）是θA=0.5 和θB=0.9。
2. 计算期望值。假设实验 1 投掷的是硬币 A，那么正面次数为 5 的概率为：
公式中的 C(10,5) 代表的是 10 个里面取 5 个的组合方式，也就是排列组合公式，0.5 的 5 次方乘以 0.5 的 5 次方代表的是其中一次为 5 次为正面，5 次为反面的概率，然后再乘以 C(10,5) 等于正面次数为 5 的概率。
假设实验 1 是投掷的硬币 B ，那么正面次数为 5 的概率为：
所以实验 1 更有可能投掷的是硬币 A。
然后我们对实验 2~5 重复上面的计算过程，可以推理出来硬币顺序应该是{A，A，B，B，A}。
这个过程实际上是通过假设的参数来估计未知参数，即“每次投掷是哪枚硬币”。
3. 通过猜测的结果{A, A, B, B, A}来完善初始化的参数θA 和θB。
然后一直重复第二步和第三步，直到参数不再发生变化。
简单总结下上面的步骤，你能看出 EM 算法中的 E 步骤就是通过旧的参数来计算隐藏变量。然后在 M 步骤中，通过得到的隐藏变量的结果来重新估计参数。直到参数不再发生变化，得到我们想要的结果。
EM 聚类的工作原理上面你能看到 EM 算法最直接的应用就是求参数估计。如果我们把潜在类别当做隐藏变量，样本看做观察值，就可以把聚类问题转化为参数估计问题。这也就是 EM 聚类的原理。
相比于 K-Means 算法，EM 聚类更加灵活，比如下面这两种情况，K-Means 会得到下面的聚类结果。
因为 K-Means 是通过距离来区分样本之间的差别的，且每个样本在计算的时候只能属于一个分类，称之为是硬聚类算法。而 EM 聚类在求解的过程中，实际上每个样本都有一定的概率和每个聚类相关，叫做软聚类算法。
你可以把 EM 算法理解成为是一个框架，在这个框架中可以采用不同的模型来用 EM 进行求解。常用的 EM 聚类有 GMM 高斯混合模型和 HMM 隐马尔科夫模型。GMM（高斯混合模型）聚类就是 EM 聚类的一种。比如上面这两个图，可以采用 GMM 来进行聚类。
和 K-Means 一样，我们事先知道聚类的个数，但是不知道每个样本分别属于哪一类。通常，我们可以假设样本是符合高斯分布的（也就是正态分布）。每个高斯分布都属于这个模型的组成部分（component），要分成 K 类就相当于是 K 个组成部分。这样我们可以先初始化每个组成部分的高斯分布的参数，然后再看来每个样本是属于哪个组成部分。这也就是 E 步骤。
再通过得到的这些隐含变量结果，反过来求每个组成部分高斯分布的参数，即 M 步骤。反复 EM 步骤，直到每个组成部分的高斯分布参数不变为止。
这样也就相当于将样本按照 GMM 模型进行了 EM 聚类。
总结EM 算法相当于一个框架，你可以采用不同的模型来进行聚类，比如 GMM（高斯混合模型），或者 HMM（隐马尔科夫模型）来进行聚类。GMM 是通过概率密度来进行聚类，聚成的类符合高斯分布（正态分布）。而 HMM 用到了马尔可夫过程，在这个过程中，我们通过状态转移矩阵来计算状态转移的概率。HMM 在自然语言处理和语音识别领域中有广泛的应用。
在 EM 这个框架中，E 步骤相当于是通过初始化的参数来估计隐含变量。M 步骤就是通过隐含变量反推来优化参数。最后通过 EM 步骤的迭代得到模型参数。
在这个过程里用到的一些数学公式这节课不进行展开。你需要重点理解 EM 算法的原理。通过上面举的炒菜的例子，你可以知道 EM 算法是一个不断观察和调整的过程。
通过求硬币正面概率的例子，你可以理解如何通过初始化参数来求隐含数据的过程，以及再通过求得的隐含数据来优化参数。
通过上面 GMM 图像聚类的例子，你可以知道很多 K-Means 解决不了的问题，EM 聚类是可以解决的。在 EM 框架中，我们将潜在类别当做隐藏变量，样本看做观察值，把聚类问题转化为参数估计问题，最终把样本进行聚类。
最后给你留两道思考题吧，你能用自己的话说一下 EM 算法的原理吗？EM 聚类和 K-Means 聚类的相同和不同之处又有哪些？
欢迎你在评论区与我分享你的答案，也欢迎点击“请朋友读”，把这篇文章分享给你的朋友或者同事，一起来交流。

分享给需要的人，Ta购买本课程，你将得18元

生成海报并分享

赞 13

提建议

27丨K-Means（下）：如何使用K-Means对图像进行分割？

29丨EM聚类（下）：用EM算法对王者荣耀英雄进行划分

 写留言

精选留言(28)

third
2019-02-19
想起了一个故事，摘叶子要找到最大的叶子 1.先心里大概有一个叶子大小的概念（初始化模型） 2.在三分之一的的路程上，观察叶子大小，并修改对大小的评估（观察预期，并修改参数） 3.在三分之二的路程上，验证自己对叶子大小模型的的评估（重复1,2过程） 4.在最后的路程上，选择最大的叶子（重复1.2，直到参数不再改变）相同点 1.EM，KMEANS，都是随机生成预期值，然后经过反复调整，获得最佳结果 2.聚类个数清晰不同点 1.EM是计算概率，KMeans是计算距离。计算概率，概率只要不为0，都有可能即样本是每一个类别都有可能计算距离，只有近的的票高，才有可能，即样本只能属于一个类别
展开
编辑回复: 例子举的不错，相同和不同之处理解也很到位，大家都可以看看。
50
黄智荣
2019-02-24
“”通过猜测的结果{A, A, B, B, A}来完善初始化的θA 和θB“” 这个步骤是怎样的？ A 5 A 7 B 8 B 9 A 4 θA=(5+7+4)/(10+10+10) θB=(8+9)/(10+10)
展开
21
Python
2019-02-15
em聚类和K均值的区别就是一个软一个硬，软的输出概率，硬的要给出答案。我理解的em聚类的过程是一个翻来覆去决策的过程，这种聚类方式是先确定一个初始化的参数，再反过来推算结果，看和自己期望的差距，又在翻回去调整。好就好在，你想要一个什么样的结果他都能慢慢给你调整出来
编辑回复: 一软一硬这个说的很恰当！一个输出概率，一个输出明确的答案。
17
梁林松
2019-02-15
EM 就好像炒菜，做汤，盐多了放水，味淡了再放盐，直到合适为止。然后，就能得出放盐和水的比例（参数）
作者回复: 对的很形象
12
松花皮蛋me
2019-02-18
有同学说:核心是初始参数啊。如果一开始就错那就完了。这完全是错的，只不过增加了更新次数而已。
编辑回复: EM有自我更新的机制，就像K-Means一样，所以不用担心初始化参数，即使初始化参数不正确也会逐渐迭代出来结果。区别是在于迭代的次数，也就是运行的时间。这就好比把菜分到两个盘子中，一开始A盘很少，B盘非常多。这时候初始化参数并不理想，但是没有关系，EM机制通过参数估计，最终通过迭代会让两个盘子的分量一样多。只是迭代次数会略多一些。
11
mickey
2019-02-28
文中抛硬币的例子，应该还要说明“5组实验，每组实验投掷10次，每组中只能抛同一枚硬币”。
作者回复: 对的
共 2 条评论
10
FORWARD―MOUNT
2019-03-28
请问：通过猜测的结果{A, A, B, B, A}来完善初始化的参数θA 和θB。然后一直重复第二步和第三步，直到参数不再发生变化。怎么完善初始化参数？，急需解答。
展开
共 3 条评论
7
mickey
2019-02-28
to third：吴军老师说过，这种找最大叶子的问题，最优解最大概率会在37%的时候，而不是最后。
7
白夜
2019-02-15
EM，聚类的个数是已知的，首先，预设初始化的参数，然后获得对应的结果，再通过结果计算参数，不断循环以上两步，直到收敛。属于软分类，每个样本有一定概率和一个聚类相关。 K-Means，聚类的个数也是已知的，首先选定一个中心点，然后计算距离，获得新的中心点，重复，直到结果收敛。属于硬分类，每个样本都只有一个分类。
作者回复: 对的
7
滨滨
2019-04-05
em算法是假定一个样本分布概率，然后根据最大似然估计进行聚类，然后根据聚类结果修正参数，直到结果不在变化，而kmeans算法则是根据随机确定初始点，根据欧式距离等算法来计算和初始点的距离，完成初始聚类，然后迭代直到聚类结果不发生变化。kmeans是计算硬聚类，em是软聚类。
5
滨滨
2019-04-05
说的通俗一点啊，最大似然估计，就是利用已知的样本结果，反推最有可能（最大概率）导致这样结果的参数值。例如：一个麻袋里有白球与黑球，但是我不知道它们之间的比例，那我就有放回的抽取10次，结果我发现我抽到了8次黑球2次白球，我要求最有可能的黑白球之间的比例时，就采取最大似然估计法：我假设我抽到黑球的概率为p,那得出8次黑球2次白球这个结果的概率为： P(黑=8)=p^8*（1-p）^2,现在我想要得出p是多少啊，很简单，使得P(黑=8)最大的p就是我要求的结果，接下来求导的的过程就是求极值的过程啦。可能你会有疑问，为什么要ln一下呢，这是因为ln把乘法变成加法了，且不会改变极值的位置（单调性保持一致嘛）这样求导会方便很多~
展开
共 1 条评论
4
JustDoDT
2020-04-06
EM算法法第一次接触，要多看两遍。
作者回复: 加油！！！
3
对三要不起
2019-05-19
TO FORWARD―MOUNT 【通过猜测的结果{A, A, B, B, A}来完善初始化的参数θA 和θB。然后一直重复第二步和第三步，直到参数不再发生变化。】这个步骤就是通过第一次随机，我们一直知道了顺序了可能是{A A B B A}，然后就可以算出A和B投正面的概率，再通过算出来的这个新概率（之前是随即指定的），再去模拟一遍五组硬币，可能这次模拟出来的就不是{A A B B A}了，重复这个步骤直到模拟出来的五枚硬币不再改变。此时的概率就是A和B 投正面的概率。
展开
1
老师冯
2019-02-19
“”通过猜测的结果{A, A, B, B, A}来完善初始化的θA 和θB“” 这个步骤是怎样的？跪求解答
1
明亮
2022-12-19 来自福建
不讲清楚具体实验规则，要读者猜，真是服了
烟雨平生
2021-12-24
老师您好，请问有什么书对于数学原理讲的比较透彻的，个人人为机器学习算法就难在数学，像西瓜书数学推导少，为什么用这样的统计学方法也没有解释，求推荐，可以英文
进击的矮子
2021-06-06
给2个K-means失效的例子。第一个：交错半圆 import matplotlib.pyplot as plt %matplotlib inline from sklearn.cluster import KMeans from sklearn import datasets x,y=datasets.make_moons(n_samples=500, shuffle=True, noise=None, random_state=None) km=KMeans(n_clusters=2, init='k-means++', n_init=10, max_iter=300, tol=0.0001, precompute_distances='deprecated', verbose=0, random_state=None, copy_x=True, n_jobs='deprecated', algorithm='auto',) label=km.fit_predict(x) fig=plt.figure() axes = fig.add_subplot(121) for idx,lab in enumerate(y): if lab==0: axes.scatter(x[idx][0],x[idx][1],color='r') else: axes.scatter(x[idx][0],x[idx][1],color='g') ax2=fig.add_subplot(122) for idx,lab in enumerate(label): if lab==0: ax2.scatter(x[idx][0],x[idx][1],color='r') else: ax2.scatter(x[idx][0],x[idx][1],color='g') plt.show() 第二个：大小圆 import matplotlib.pyplot as plt %matplotlib inline from sklearn.cluster import KMeans from sklearn import datasets x,y=datasets.make_circles(n_samples=200, shuffle=True, noise=None, random_state=None, factor=.8) km=KMeans(n_clusters=2, init='k-means++', n_init=10, max_iter=300, tol=0.0001, precompute_distances='deprecated', verbose=0, random_state=None, copy_x=True, n_jobs='deprecated', algorithm='auto',) label=km.fit_predict(x) fig=plt.figure() axes = fig.add_subplot(121) for idx,lab in enumerate(y): if lab==0: axes.scatter(x[idx][0],x[idx][1],color='r') else: axes.scatter(x[idx][0],x[idx][1],color='g') ax2=fig.add_subplot(122) for idx,lab in enumerate(label): if lab==0: ax2.scatter(x[idx][0],x[idx][1],color='r') else: ax2.scatter(x[idx][0],x[idx][1],color='g') plt.show()
展开
完美坚持
2021-04-15
EM聚类，首先给每个样本点人为设定一个类别，设定好之后就可以计算每个类别的样本点分布的特征参数（E-step）。根据得到的特诊参数决定的分布，可以将样本点重新归类（相当于重新设定参数，M-step），至此又可以根据新的类别划分重复上述步骤，直到每个样本点的类别划分不再有大的变化
McKee Chen
2021-01-09
EM聚类：对参数进行初始化，以此估计隐含变量，然后再反推初始参数，如果参数有变化，就不断重复上述过程，知道参数不变为止，此时也能得到隐含变量，即样本的聚类情况。 EM聚类和K-Means聚类的区别： K-Means聚类是预先给定中心点个数，然后计算样本与中心点之间的距离来进行分类，通过不断迭代优化中心点，直至中心点不再发生变换，最后确定聚类情况。这种过程也称之为硬聚类算法。有一个疑问，对于掷硬币的五次实验，每次实验都是只选择A或B其中一个么？
展开
作者回复: 是的，抛硬币的试验，一般会假设只会出现正反2面的结果，默认不会出现硬币垂直的情况。
追梦
2019-10-22
想起了一个故事，摘叶子要找到最大的叶子 1.先心里大概有一个叶子大小的概念（初始化模型） 2.在三分之一的的路程上，观察叶子大小，并修改对大小的评估（观察预期，并修改参数） 3.在三分之二的路程上，验证自己对叶子大小模型的的评估（重复1,2过程） 4.在最后的路程上，选择最大的叶子（重复1.2，直到参数不再改变）相同点 1.EM，KMEANS，都是随机生成预期值，然后经过反复调整，获得最佳结果 2.聚类个数清晰不同点 1.EM是计算概率，KMeans是计算距离。计算概率，概率只要不为0，都有可能即样本是每一个类别都有可能计算距离，只有近的的票高，才有可能，即样本只能属于一个类别 “”通过猜测的结果{A, A, B, B, A}来完善初始化的θA 和θB“” 这个步骤是怎样的？ A 5 A 7 B 8 B 9 A 4 θA=(5+7+4)/(10+10+10) θB=(8+9)/(10+10) 以留言方式暂时记录一下
展开
作者回复: 很好的总结整理

