em算法的例子
1. EM算法和混合高斯模型（一）
EM（Expectation Maximization）算法是一种迭代算法，用于含有隐变量的概率模型参数的极大似然估计，或极大后验估计。EM算法的每次迭代由两步组成：E步，求期望（expectation）；M步，求极大值，因而被称为期望极大算法，简称EM算法。
本文从EM算法的引入说起，简单介绍EM算法的推导过程，以及其在高斯混合模型中的应用。更多的关于EM算法的推导细节，可参见 人人都懂EM算法 。
假设我们需要调查我们学校学生的身高分布。我们先假设学校所有学生的身高服从正态分布 。( 注意：极大似然估计的前提一定是要假设数据总体的分布，如果不知道数据分布，是无法使用极大似然估计的 )，这个分布的均值μ和标准差为σ 未知，如果我们估计出这两个参数，那我们就得到了最终的结果。那么怎样估计这两个参数呢？
学校的学生这么多，我们不可能挨个统计吧？这时候我们需要用到概率统计的思想，也就是抽样，根据样本估算总体。假设我们随机抽到了 200 个人（也就是 200 个身高的样本数据，为了方便表示，下面“人”的意思就是对应的身高）。然后统计抽样这 200 个人的身高。根据这 200 个人的身高估计均值 μ和方差σ 。例子来自 人人都懂EM算法 。
现在我们假设这200个人的身高服从一个正态分布N(μ，σ)，因此可以直接使用极大似然估计方法估计出这个分布的参数μ和σ。
但是，这200个人的身高真的是服从同一个正态分布吗？实际情况并不是这样的，男生和女生分别服从两种不同的正态分布，即男生 女生各服从一个正态分布 ，( 注意：EM算法和极大似然估计的前提是一样的，都要假设数据总体的分布，如果不知道数据分布，是无法使用EM算法的 )，而且假设我们现在只有身高数据，丢失了性别数据，那么该怎样评估学生的身高分布呢？
这个时候，对于每一个样本或者你抽取到的人，就有两个问题需要估计了，一是这个人是男的还是女的，二是男生和女生对应的身高的正态分布的参数是多少。这两个问题是相互依赖的：
但是现在我们既不知道每个学生是男生还是女生，也不知道男生和女生的身高分布。这就成了一个先有鸡还是先有蛋的问题了。鸡说，没有我，谁把你生出来的啊。蛋不服，说，没有我，你从哪蹦出来啊。为了解决这个你依赖我，我依赖你的循环依赖问题，总得有一方要先打破僵局，不管了，我先随便整一个值出来，看你怎么变，然后我再根据你的变化调整我的变化，然后如此迭代着不断互相推导，最终就会收敛到一个解（草原上的狼和羊，相生相克）。这就是EM算法的基本思想了。
EM的意思是“Expectation Maximization”，具体方法为：
上面的学生属于男生还是女生我们称之为隐含参数，女生和男生的身高分布参数称为模型参数。
EM 算法解决这个的思路是使用启发式的迭代方法，既然我们无法直接求出模型分布参数，那么我们可以先猜想隐含参数（EM 算法的 E 步），接着基于观察数据和猜测的隐含参数一起来极大化对数似然，求解我们的模型参数（EM算法的M步)。由于我们之前的隐含参数是猜测的，所以此时得到的模型参数一般还不是我们想要的结果。我们基于当前得到的模型参数，继续猜测隐含参数（EM算法的 E 步），然后继续极大化对数似然，求解我们的模型参数（EM算法的M步)。以此类推，不断的迭代下去，直到模型分布参数基本无变化，算法收敛，找到合适的模型参数。
在开始介绍EM算法之前，让我们先来了解一个重要的定理——Jensen不等式。
如下图，如果函数f(x)是凸函数，x是随机变量，有 0.5 的概率是 a，有 0.5 的概率是 b， x的期望值就是 a 和 b 的中值了，那么：
对于m个相互独立的样本:
假如没有隐含变量z， 我们仅需要找到合适的θ极大化对数似然函数即可:
现在我们给定一个θ值（初始化θ），那么logL(θ)的值就取决于Q i (z)和P(x (i) ,z (i) )。我们可以通过调整这两个概率使下届逼近logL(θ)的真实值，当不等式变为等式时，说明我们调整后的下届就等于logL(θ)了。由Jeson不等式可知，等式成立的条件是随机变量是常数，则有：
如果Q i (z (i) ) = P(z (i) |x (i) , θ)，则（2）式使我们包含隐藏数据的对数似然函数的一个下届。如果我们能极大化这个下届，则也在尝试极大化我们的对数似然函数。即我们需要极大化下式：
由于对logaf(x)求导的结果与f(x)的系数无关（(ln(ax))'= (lna + lnx)'=1/x），因此对θ求极大似然时，可以去掉式中的常数部分Q i (z (i) )：
现在，让我们来总结一下EM算法的流程。
输入：观察数据x = (x (1) , x (2) , ... , x (m) ), 联合分布P(x, z|θ)，条件分布P(z|x,θ)，极大迭代次数J。
（1）随机初始化模型参数θ值；
（2）迭代求解各个分布模型的参数以及各个模型的概率：
for j from 1 to J:
输出：模型参数θ
图中的直线式迭代优化的路径，可以看到每一步都会向最优值前进一步，而且前进路线是平行于坐标轴的，因为每一步只优化一个变量。
这犹如在x-y坐标系中找一个曲线的极值，然而曲线函数不能直接求导，因此什么梯度下降方法就不适用了。但固定一个变量后，另外一个可以通过求导得到，因此可以使用坐标上升法，一次固定一个变量，对另外的求极值，最后逐步逼近极值。对应到EM上，E步：固定 θ，优化Q；M步：固定 Q，优化 θ；交替将极值推向极大。
E步 ：初始化θ A =0.6和θ B =0.5（θ A 和θ B 分别表示两个硬币出现正面的概率），计算每次掷硬币选择A和B的概率，例如第一个实验中选择A的概率为：
M步 ：求出似然函数下届Q(θ，θ i ), y i 代表第j次试验正面朝上的个数，μ j 代表第j次试验选择硬币A的概率，1-μ j 代表第j次试验选择硬币B的概率。
参考：
人人都懂EM算法
《统计学习方法》. 李航
2. EM算法深度解析
最近在做文本挖掘的时候遇到了EM算法，虽然读书的时候简单地接触过，但当时并没有深入地去了解，导致现在只记得算法的名字。既然EM算法被列为数据挖掘的十大算法之一，正好借这个机会，重新学习一下这个经典的算法。学习的过程中，我发现网上的资料大多讲解地不够细致，很多地方解释得并不明了。因此我决定抛开别人的想法，仅从数学推导本身出发，尽力理解每一个公式的含义，并将其对应到实际的实验过程当中。这篇博客记录了我对与EM算法的思考与理解，也是我人生中的第一篇博客，希望能够对于想要学习EM算法的同学有所帮助。
前面谈到我在做文本挖掘的时候遇到了EM算法，EM算法用于估计模型中的参数。提到参数估计，最常见的方法莫过于极大似然估计——在所有的候选参数中，我们选择的参数应该让样本出现的概率最大。相信看到这篇笔记的同学一定对极大似然估计非常熟悉，而EM算法可以看作是极大似然估计的一个扩充，这里就让我们用极大似然估计来解决一个简单的例子，来开始正式的讨论。
有A，B，C三枚硬币，我们想要估计A，B，C三枚硬币抛出正面的概率 , , 。我们按如下流程进行实验100次：
记录100次实验的结果如下：
我们将上面的实验结果表述如下：
表示第i次实验中，硬币A的结果，1代表正面，0代表反面； 表示第i次实验中，硬币B或硬币C抛出正面的个数，则参数 的极大似然估计分别为：
即硬币A，B，C各自抛出正面的次数占总次数的比例，其中 为指示函数。
实验流程与1相同，但是我们不慎遗失了硬币A的记录结果，导致我们只知道随后十次抛出了多少次正面，多少次反面，却不知道实验结果来自于硬币B还是硬币C。在这种情况下，我们是否还能估计出 , , 的值呢？
这时候利用极大似然估计似乎行不通了， 因为这种情况下，我们不但缺失了硬币A产生的观测值，同时也不知道哪些观测值属于硬币B，哪些观测值属于硬币C。
有些同学可能会提出，虽然我们无法得到三个硬币各自产生的样本，但是我们依然可以得到每个观测值出现的概率。比如在第一次实验中， 我们抛出了5次正面5次反面，我们可以做如下思考：
假设这5次正面由硬币B得到，那么概率应该为 ，而这次观测值来自于硬币B，也就是硬币A抛出正面的概率为
假设这5次正面由硬币C得到，那么概率应该为 ，而这次观测值来自于硬币C，也就是硬币A抛出反面的概率为
综合起来，利用条件概率公式，这个观测值出现的概率就是
因此我们可以将样本整体的概率和似然函数利用 , , 表示出来，通过对似然函数求导，令其关于 的偏导数等于0，我们可以求出三个参数的值。
这个思路听上去十分合理，我们可以顺着这个思路进行数学推导，看看可以得到什么样的结果。首先我们计算样本的概率:
对应的似然函数为
其中 关于 的条件分布为
的分布为
因此我们可以得到
至此，我们成功地得到了似然函数。然而观察可以发现，这个函数是由100项对数函数相加组成，每个对数函数内部包含一个求和，想通过求导并解出导数的零点几乎是不可能的。当然我们可以通过梯度下降来极小化这个函数，借助深度学习库的自动微分系统在实现上也非常容易。但是这种做法过于简单粗暴，有没有办法来优雅地解决这个问题呢？在继续讨论之前，我们先将这类问题进行一般化表述：
我们观测到随机变量 产生的m个相互独立的样本 , 的分布由联合分布 决定， 是缺失数据或无法在实验中被直接观测到，称为 隐变量 ，我们想要从样本中估计出模型参数 的值。在接下来的讨论中，我们假定 的取值是离散的，于是可以得到似然函数如下:
接下来，我们就探讨一下，如何利用EM算法解决这个问题。
这一部分的数学推导，主要参考了吴恩达CS229n的笔记，并且根据个人的思考和理解，尽力对公式的每一步进行详细的解释。我们先简单地介绍一下琴生不等式。
琴生不等式有多种形式，下面给出其离散形式的表述和概率论中的表述:
1.若 为严格凹函数， 为定义域内的n个点， 是n个正实数，且满足 , 则下述不等式成立:
当且仅当 时，不等式取等号。
2.若 为严格凹函数， 为实值随机变量，且期望存在，则下述不等式成立:
当且仅当 ，即 为常数时，不等式取等号。
注： 这里将函数上方为凹集的函数称为凹函数， 例如 函数就是凹函数。
相信大家对琴生不等式都十分熟悉，因此这里就不做过多的说明。接下来，我们将琴生不等式应用到我们的问题中。
回到我们之前的问题上， 我们想要极大化下面这个函数:
但是我们无法对这个函数直接求导，因此我们借助琴生不等式，对这个函数进行变换。为了让过程看上去简洁，下面只对求和中的第 项进行计算。
令 满足 ，且 ，则根据琴生不等式，可以得到：
当且仅当 为常数时，上述不等式取等号。也就是说，对于任意 ， 是一个与 无关的量。设对于任意 ，我们可以得到：
因此当 时，不等式 取等号，容易验证此时 , 与 无关。将 综合一下，我们可以得到以下结论:
到这里为止，我们已经拥有了推导出EM算法的全部数学基础，基于 我们可以构建出E步和M步。上面的数学推导虽然看上去略为复杂，但实际上只用到了三个知识点：
1.琴生不等式:
2.条件概率:
3.联合分布求和等于边缘分布:
对上面的数学推导有疑问的同学，可以结合上面这三点，再将整个推导过程耐心地看一遍。
大部分关于EM算法的资料，只是在数学形式上引入了 函数，即 ，以满足琴生不等式的使用条件，却没有过多地解释 函数本身。这导致了很多人完全看懂了算法的推导，却还是不理解这些数学公式究竟在做什么，甚至不明白EM算法为什么叫做EM算法。所以在给出E步和M步之前，我想先谈一谈 函数。
我们回顾一下 函数所满足的条件（暂时不考虑琴生不等式取等号的限制），
在 所有可能的取值处有定义。可以看出， 是 的样本空间上任意的一个概率分布。因此，我们可以对不等式 进行改写。首先我们可以将含有 的求和写成期望的形式:
这里 指的是在概率分布 下，求随机变量 和 的期望。有同学会问，为什么我们平时求期望的时候只要写 ，并没有指明是在哪个概率分布下的期望。这是因为一般情况下，我们都清楚地知道随机变量 所服从的分布 ，并且默认在分布 下求期望。
举个例子，我手上有一个硬币，抛了10次，问抛出正面次数的期望。这种情况下，大部分人会默认硬币是均匀的，也就是说抛出正面的次数 服从二项分布 ，期望 。这时有人提出了质疑，他说我认为你这个硬币有问题，抛出正面的概率只有0.3，那么在他眼里， 期望 。
回到正题，我们利用等式 改写不等式 ，可以得到:
这正是琴生不等式在概率论中的形式。我们可以将不等式倒过来理解：
首先，假定随机变量 服从概率分布 ， 是 的样本空间上的任意一个概率分布。这里 可以是一组定值，也可以是关于参数 的函数。
显然，当我们取不同的 时，随机变量 的期望也会随之改变。需要注意的是，由于 与 相关，所以这里的期望不是一个数值，而是关于 的函数。
当我们令 为 的后验分布 时，上面的期望最大。这里有两点需要注意，1. 后验分布 也是一个关于参数 的函数。2. 由于期望是关于 的函数，所以这里的最大指的并非是最大值，而是最大的函数。
若对于每一个 ，我们都令 为 的后验分布 ，则上述期望之和等于我们要极大化的似然函数，即
通过上述分析，我们为寻找似然函数的极大值点 提供了一个思路。我们不去极大化似然函数本身，而是去极大化 。至于如何将这个思路实际应用，就要利用到EM算法中的E-step和M-step。
这一节中，我们先给出E-step和M-step的数学形式，随后在结合抛硬币的例子来解释这两步究竟在做什么。下面进入算法的流程，首先我们任意初始化 ，按下述过程进行迭代直至收敛：
在第 次迭代中，
(E-step)对于每个 ，令
(M-step)更新 的估计值，令
EM算法从任意一点 出发，依次利用E-step优化 ，M-step优化 ，重复上述过程从而逐渐逼近极大值点。而这个过程究竟是怎样的呢，就让我们一步步地揭开EM算法的面纱。
假设我们现在随机初始化了 ，进入第一轮迭代：
(E-step)
由于我们已经假定模型参数为 ，所以此时 不再是与 有关的函数，而是由一组常数构成的概率分布。结合抛硬币的例子来看，这一步是在我们已知模型参数 的基础上(虽然这是我们瞎猜的)，去推测每一次的观测值是由哪个硬币产生的，或者说我们对每一次观测值做一个软分类。比如我们根据初始化的参数，计算出 ， 。可以解释为第 个观测值有20%的概率来自于硬币B，80%的概率来自于硬币C；或者说硬币A抛出了0.2个正面，0.8个反面。
(M-step)
考虑到 是一组常数，我们可以舍弃常数项，进一步简化上面这个要极大化的函数
由于 不再与 相关，因此上面的函数变成了对数函数求和的形式，这个函数通常来说是容易求导的，令导数等于0，我们可以求出新的参数 。我们仍旧以抛硬币为例进行解释，
令 , 可以得到，
这三个参数的解释是显而易见的。我们在E-step中对每个观测值进行了软分类， 可以看成是硬币A抛出正面的次数，所以 是 的极大似然估计； 是我们抛硬币B的次数， 是硬币B抛出正面的次数，所以 是 的极大似然估计；对于 我们有相同的解释。
我们将这个结果与抛硬币1中极大似然估计的结果相比较可以发现，之前结果中的指示函数 变成了这里的 ，在指示函数下，某个观测值要么来自于硬币B，要么来自于硬币C，因此也称为硬分类。而在 函数下，某个观测值可以一部分来自于硬币B，一部分来自于硬币C，因此也称作软分类。
将上述两步综合起来，EM算法可以总结如下：我们首先初始化模型的参数，我们基于这个参数对每一个隐变量进行分类，此时相当于我们观测到了隐变量。有了隐变量的观测值之后，原来含有隐变量的模型变成了不含隐变量的模型，因此我们可以直接使用极大似然估计来更新模型的参数，再基于新的参数开始新一轮的迭代，直到参数收敛。接来下我们就讨论为什么参数一定会收敛。
前面写了太多的公式，但是这一部分我不打算给出收敛性的数学推导。其实数学上证明EM算法的收敛性很容易，只需要证明每一轮迭代之后，参数的似然函数递增，即
3. 怎么通俗易懂地解释EM算法并且举个例子
你知道一些东西（观察的到的数据），你不知道一些东西（观察不到的），你很好奇，想知道点那些不了解的东西。怎么办呢，你就根据一些假设（parameter）先猜（E-step），把那些不知道的东西都猜出来，假装你全都知道了;然后有了这些猜出来的数据，你反思一下，更新一下你的假设（parameter）,让你观察到的数据更加可能(Maximize likelihood;M-stemp);然后再猜，在反思，最后，你就得到了一个可以解释整个数据的假设了。1.注意，你猜的时候，要尽可能的猜遍所有情况，然后求期望（Expected）；就是你不能仅仅猜一个个例，而是要猜出来整个宇宙；2.为什么要猜，因为反思的时候，知道全部的东西比较好。（就是P(X,Z)要比P(X)好优化一些。Z是hidden states）3.最后你得到什么了？你得到了一个可以解释数据的假设，可能有好多假设都能解释数据，可能别的假设更好。不过没关系，有总比没有强，知足吧。（你陷入到local minimum了）
公司有很多领导=[A总，刘总，C总]，同时有很多漂亮的女职员=[小甲，小章，小乙]。（请勿对号入座）你迫切的怀疑这些老总跟这些女职员有问题。为了科学的验证你的猜想，你进行了细致的观察。于是，观察数据：1）A总，小甲，小乙一起出门了；2）刘总，小甲，小章一起出门了；3）刘总，小章，小乙一起出门了；4）C总，小乙一起出门了；收集到了数据，你开始了神秘的EM计算：初始化，你觉得三个老总一样帅，一样有钱，三个美女一样漂亮，每个人都可能跟每个人有关系。所以，每个老总跟每个女职员“有问题”的概率都是1/3;这样，（E step）1）A总跟小甲出去过了1/2*1/3=1/6次，跟小乙也出去了1/6次；（所谓的fractional count）2）刘总跟小甲，小章也都出去了1/6次3）刘总跟小乙，小章又出去了1/6次4）C总跟小乙出去了1/3次
4. 怎么通俗易懂地解释EM算法并且举个例子
在统计计算中，最大期望（EM）算法是在概率（probabilistic）模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variable）。最大期望经常用在机器学习和计算机视觉的数据聚类（Data Clustering）领域。
最大期望算法经过两个步骤交替进行计算：
第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；
第二步是最大化（M），最大化在 E 步上求得的最大似然值来计算参数的值。
M 步上找到的参数估计值被用于下一个 E 步计算中，这个过程不断交替进行。
总体来说，EM的算法流程如下：
初始化分布参数
2.重复直到收敛：
E步骤：估计未知参数的期望值，给出当前的参数估计。
M步骤：重新估计分布参数，以使得数据的似然性最大，给出未知变量的期望估计。
5. 数据分析中缺失值的处理
数据缺失在许多研究领域都是一个复杂的问题，对数据挖掘来说，缺失值的存在，造成了以下影响：
1.系统丢失了大量的有用信息
2.系统中所表现出的不确定性更加显着，系统中蕴涵的确定性成分更难把握
3.包含空值的数据会使挖掘过程陷入混乱，导致不可靠的输出
数据挖掘算法本身更致力于避免数据过分拟合所建的模型，这一特性使得它难以通过自身的算法去很好地处理不完整数据。因此，缺失值需要通过专门的方法进行推导、填充等，以减少数据挖掘算法与实际应用之间的差距。
1.列表显示缺失值 mice包 md.pattern( )
2.图形探究缺失值 VIM包
3.用相关性探索缺失值
1.人工填写
由于最了解数据的还是用户自己，因此这个方法产生数据偏离最小，可能是填充效果最好的一种。然而一般来说，该方法很费时，当数据规模很大、空值很多的时候，该方法是不可行的。
2.特殊值填充
将空值作为一种特殊的属性值来处理，它不同于其他的任何属性值。如所有的空值都用“unknown”填充。这样将形成另一个有趣的概念，可能导致严重的数据偏离，一般不推荐使用。
3.平均值填充
将信息表中的属性分为数值属性和非数值属性来分别进行处理。如果空值是数值型的，就根据该属性在其他所有对象的取值的平均值来填充该缺失的属性值；如果空值是非数值型的，就根据统计学中的众数原理，用该属性在其他所有对象的取值次数最多的值(即出现频率最高的值)来补齐该缺失的属性值。另外有一种与其相似的方法叫条件平均值填充法（Conditional Mean Completer）。在该方法中，缺失属性值的补齐同样是靠该属性在其他对象中的取值求平均得到，但不同的是用于求平均的值并不是从信息表所有对象中取，而是从与该对象具有相同决策属性值的对象中取得。这两种数据的补齐方法，其基本的出发点都是一样的，以最大概率可能的取值来补充缺失的属性值，只是在具体方法上有一点不同。与其他方法相比，它是用现存数据的多数信息来推测缺失值。
4.热卡填充
对于一个包含空值的对象，热卡填充法在完整数据中找到一个与它最相似的对象，然后用这个相似对象的值来进行填充。不同的问题可能会选用不同的标准来对相似进行判定。该方法概念上很简单，且利用了数据间的关系来进行空值估计。这个方法的缺点在于难以定义相似标准，主观因素较多。
5.K最近距离邻法
先根据欧式距离或相关分析来确定距离具有缺失数据样本最近的K个样本，将这K个值加权平均来估计该样本的缺失数据。
同均值插补的方法都属于单值插补，不同的是，它用层次聚类模型预测缺失变量的类型，再以该类型的均值插补。假设X=(X1,X2…Xp)为信息完全的变量，Y为存在缺失值的变量，那么首先对X或其子集行聚类，然后按缺失个案所属类来插补不同类的均值。如果在以后统计分析中还需以引入的解释变量和Y做分析，那么这种插补方法将在模型中引入自相关，给分析造成障碍。
6.使用所有可能的值填充
用空缺属性值的所有可能的属性取值来填充，能够得到较好的补齐效果。但是，当数据量很大或者遗漏的属性值较多时，其计算的代价很大，可能的测试方案很多。
7.组合完整化方法
用空缺属性值的所有可能的属性取值来试，并从最终属性的约简结果中选择最好的一个作为填补的属性值。这是以约简为目的的数据补齐方法，能够得到好的约简结果；但是，当数据量很大或者遗漏的属性值较多时，其计算的代价很大。
8.回归
基于完整的数据集，建立回归方程（模型）。对于包含空值的对象，将已知属性值代入方程来估计未知属性值，以此估计值来进行填充，当变量不是线性相关或预测变量高度相关时会导致有偏差的估计（SPSS菜单里有这种方法）
9.期望值最大化方法
EM算法是一种在不完全数据情况下计算极大似然估计或者后验分布的迭代算法。在每一迭代循环过程中交替执行两个步骤：E步（Excepctaion step,期望步），在给定完全数据和前一次迭代所得到的参数估计的情况下计算完全数据对应的对数似然函数的条件期望；M步（Maximzation step，极大化步），用极大化对数似然函数以确定参数的值，并用于下步的迭代。算法在E步和M步之间不断迭代直至收敛，即两次迭代之间的参数变化小于一个预先给定的阈值时结束。该方法可能会陷入局部极值，收敛速度也不是很快，并且计算很复杂。（SPSS菜单里有这种方法）
10.1多重插补原理
多值插补的思想来源于贝叶斯估计，认为待插补的值是随机的，它的值来自于已观测到的值。具体实践上通常是估计出待插补的值，然后再加上不同的噪声，形成多组可选插补值。根据某种选择依据，选取最合适的插补值。
10.2多重填补在SPSS中的实现
10.2.1缺失模式分析
分析>多重归因>分析模式
10.2.2缺失值的多重填充
分析>多重归因>归因缺失数据值
10.2.3采用填充后的数据建模
10.3多重填补在R中的实现（基于mice包）
实例：
11.C4.5方法
通过寻找属性间的关系来对遗失值填充。它寻找之间具有最大相关性的两个属性，其中没有遗失值的一个称为代理属性，另一个称为原始属性，用代理属性决定原始属性中的遗失值。这种基于规则归纳的方法只能处理基数较小的名词型属性。
就几种基于统计的方法而言，删除元组法和平均值填充法差于热卡填充法、期望值最大化方法和多重填充法；回归是比较好的一种方法，但仍比不上热卡填充和期望值最大化方法；期望值最大化方法缺少多重填补包含的不确定成分。值得注意的是，这些方法直接处理的是模型参数的估计而不是空缺值预测本身。它们合适于处理无监督学习的问题，而对有监督学习来说，情况就不尽相同了。譬如，你可以删除包含空值的对象用完整的数据集来进行训练，但预测时你却不能忽略包含空值的对象。另外，C4.5和使用所有可能的值填充方法也有较好的补齐效果，人工填写和特殊值填充则是一般不推荐使用的。
补齐处理只是将未知值补以我们的主观估计值，不一定完全符合客观事实，在对不完备信息进行补齐处理的同时，我们或多或少地改变了原始的信息系统。而且，对空值不正确的填充往往将新的噪声引入数据中，使挖掘任务产生错误的结果。因此，在许多情况下，我们还是希望在保持原始信息不发生变化的前提下对信息系统进行处理。
直接在包含空值的数据上进行数据挖掘，这类方法包括贝叶斯网络和人工神经网络等。
贝叶斯网络是用来表示变量间连接概率的图形模式，它提供了一种自然的表示因果信息的方法，用来发现数据间的潜在关系。在这个网络中，用节点表示变量，有向边表示变量间的依赖关系。贝叶斯网络仅适合于对领域知识具有一定了解的情况，至少对变量间的依赖关系较清楚的情况。否则直接从数据中学习贝叶斯网的结构不但复杂性较高（随着变量的增加，指数级增加），网络维护代价昂贵，而且它的估计参数较多，为系统带来了高方差，影响了它的预测精度。当在任何一个对象中的缺失值数量很大时，存在指数爆炸的危险。人工神经网络可以有效的对付空值，但人工神经网络在这方面的研究还有待进一步深入展开。人工神经网络方法在数据挖掘应用中的局限性。
多数统计方法都假设输入数据是完整的且不包含缺失值，但现实生活中大多数数据集都包含了缺失值。因此，在进行下一步分析前，你要么删除，要么用合理的数值代理它们，SPSS、R、Python、SAS等统计软件都会提供一些默认的处理缺失值方法，但这些方法可能不是最优的，因此，学习各种各样的方法和他们的分支就显得非常重要。Little和Rubin的《Sstatistical Analysis With Missing Data 》是缺失值领域里经典的读本，值得一看。
6. 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求解其他参数。
7. 数据挖掘十大经典算法之EM
EM（Expectation-Maximum）算法也称期望最大化算法，它是最常见的隐变量估计方法，在机器学习中有极为广泛的用途，例如常被用来学习高斯混合模型（Gaussian mixture model，简称GMM）的参数；隐式马尔科夫算法（HMM）、LDA主题模型的变分推断等等。
EM算法是一种迭代优化策略，由于它的计算方法中每一次迭代都分两步，其中一个为期望步（E步），另一个为极大步（M步），一轮轮迭代更新隐含数据和模型分布参数，直到收敛，即得到我们需要的模型参数。
1. EM算法推导过程
补充知识：Jensen不等式：
如果f是凸函数，函数的期望 大于等于 期望的函数。当且仅当下式中X是常量时，该式取等号。（应用于凹函数时，不等号方向相反）
2. EM算法流程
3. EM算法的其他问题
上面介绍的传统EM算法对初始值敏感，聚类结果随不同的初始值而波动较大。总的来说，EM算法收敛的优劣很大程度上取决于其初始参数。
EM算法可以保证收敛到一个稳定点，即EM算法是一定收敛的。
EM算法可以保证收敛到一个稳定点，但是却不能保证收敛到全局的极大值点，因此它是局部最优的算法，当然，如果我们的优化目标是凸的，则EM算法可以保证收敛到全局最大值，这点和梯度下降法这样的迭代算法相同。
EM算法的简单实例： https://zhuanlan.hu.com/p/40991784
参考：
https://zhuanlan.hu.com/p/40991784
https://blog.csdn.net/u011067360/article/details/24368085
8. 数据分析中的缺失值处理
数据分析中的缺失值处理
没有高质量的数据，就没有高质量的数据挖掘结果，数据值缺失是数据分析中经常遇到的问题之一。当缺失比例很小时，可直接对缺失记录进行舍弃或进行手工处理。但在实际数据中，往往缺失数据占有相当的比重。这时如果手工处理非常低效，如果舍弃缺失记录，则会丢失大量信息，使不完全观测数据与完全观测数据间产生系统差异，对这样的数据进行分析，你很可能会得出错误的结论。
造成数据缺失的原因
现实世界中的数据异常杂乱，属性值缺失的情况经常发全甚至是不可避免的。造成数据缺失的原因是多方面的：
信息暂时无法获取。例如在医疗数据库中，并非所有病人的所有临床检验结果都能在给定的时间内得到，就致使一部分属性值空缺出来。
信息被遗漏。可能是因为输入时认为不重要、忘记填写了或对数据理解错误而遗漏，也可能是由于数据采集设备的故障、存储介质的故障、传输媒体的故障、一些人为因素等原因而丢失。
有些对象的某个或某些属性是不可用的。如一个未婚者的配偶姓名、一个儿童的固定收入状况等。
有些信息（被认为）是不重要的。如一个属性的取值与给定语境是无关。
获取这些信息的代价太大。
系统实时性能要求较高。即要求得到这些信息前迅速做出判断或决策。
对缺失值的处理要具体问题具体分析，为什么要具体问题具体分析呢？因为属性缺失有时并不意味着数据缺失，缺失本身是包含信息的，所以需要根据不同应用场景下缺失值可能包含的信息进行合理填充。下面通过一些例子来说明如何具体问题具体分析，仁者见仁智者见智，仅供参考：
“年收入”：商品推荐场景下填充平均值，借贷额度场景下填充最小值；
“行为时间点”：填充众数；
“价格”：商品推荐场景下填充最小值，商品匹配场景下填充平均值；
“人体寿命”：保险费用估计场景下填充最大值，人口估计场景下填充平均值；
“驾龄”：没有填写这一项的用户可能是没有车，为它填充为0较为合理；
”本科毕业时间”：没有填写这一项的用户可能是没有上大学，为它填充正无穷比较合理；
“婚姻状态”：没有填写这一项的用户可能对自己的隐私比较敏感，应单独设为一个分类，如已婚1、未婚0、未填-1。
缺失的类型
在对缺失数据进行处理前，了解数据缺失的机制和形式是十分必要的。将数据集中不含缺失值的变量称为完全变量，数据集中含有缺失值的变量称为不完全变量。从缺失的分布来将缺失可以分为完全随机缺失，随机缺失和完全非随机缺失。
完全随机缺失（missing completely at random,MCAR）：指的是数据的缺失是完全随机的，不依赖于任何不完全变量或完全变量，不影响样本的无偏性。如家庭地址缺失。
随机缺失(missing at random,MAR)：指的是数据的缺失不是完全随机的，即该类数据的缺失依赖于其他完全变量。例如财务数据缺失情况与企业的大小有关。
非随机缺失(missing not at random,MNAR)：指的是数据的缺失与不完全变量自身的取值有关。如高收入人群的不原意提供家庭收入。
对于随机缺失和非随机缺失,删除记录是不合适的,随机缺失可以通过已知变量对缺失值进行估计；而非随机缺失还没有很好的解决办法。
说明:对于分类问题，可以分析缺失的样本中，类别之间的比例和整体数据集中，类别的比例
缺失值处理的必要性
数据缺失在许多研究领域都是一个复杂的问题。对数据挖掘来说，缺省值的存在，造成了以下影响：
系统丢失了大量的有用信息；
系统中所表现出的不确定性更加显着，系统中蕴涵的确定性成分更难把握；
包含空值的数据会使挖掘过程陷入混乱，导致不可靠的输出。
数据挖掘算法本身更致力于避免数据过分拟合所建的模型，这一特性使得它难以通过自身的算法去很好地处理不完整数据。因此，缺省值需要通过专门的方法进行推导、填充等，以减少数据挖掘算法与实际应用之间的差距。
缺失值处理方法的分析与比较
处理不完整数据集的方法主要有三大类：删除元组、数据补齐、不处理。
删除元组
也就是将存在遗漏信息属性值的对象（元组，记录）删除，从而得到一个完备的信息表。这种方法简单易行，在对象有多个属性缺失值、被删除的含缺失值的对象与初始数据集的数据量相比非常小的情况下非常有效，类标号缺失时通常使用该方法。
然而，这种方法却有很大的局限性。它以减少历史数据来换取信息的完备，会丢弃大量隐藏在这些对象中的信息。在初始数据集包含的对象很少的情况下，删除少量对象足以严重影响信息的客观性和结果的正确性；因此，当缺失数据所占比例较大，特别当遗漏数据非随机分布时，这种方法可能导致数据发生偏离，从而引出错误的结论。
说明:删除元组，或者直接删除该列特征，有时候会导致性能下降。
数据补齐
这类方法是用一定的值去填充空值，从而使信息表完备化。通常基于统计学原理，根据初始数据集中其余对象取值的分布情况来对一个缺失值进行填充。数据挖掘中常用的有以下几种补齐方法：
人工填写（filling manually）
由于最了解数据的还是用户自己，因此这个方法产生数据偏离最小，可能是填充效果最好的一种。然而一般来说，该方法很费时，当数据规模很大、空值很多的时候，该方法是不可行的。
特殊值填充（Treating Missing Attribute values as Special values）
将空值作为一种特殊的属性值来处理，它不同于其他的任何属性值。如所有的空值都用“unknown”填充。这样将形成另一个有趣的概念，可能导致严重的数据偏离，一般不推荐使用。
平均值填充（Mean/Mode Completer）
将初始数据集中的属性分为数值属性和非数值属性来分别进行处理。
如果空值是数值型的，就根据该属性在其他所有对象的取值的平均值来填充该缺失的属性值；
如果空值是非数值型的，就根据统计学中的众数原理，用该属性在其他所有对象的取值次数最多的值(即出现频率最高的值)来补齐该缺失的属性值。与其相似的另一种方法叫条件平均值填充法（Conditional Mean Completer）。在该方法中，用于求平均的值并不是从数据集的所有对象中取，而是从与该对象具有相同决策属性值的对象中取得。
这两种数据的补齐方法，其基本的出发点都是一样的，以最大概率可能的取值来补充缺失的属性值，只是在具体方法上有一点不同。与其他方法相比，它是用现存数据的多数信息来推测缺失值。
热卡填充（Hot deck imputation，或就近补齐）
对于一个包含空值的对象，热卡填充法在完整数据中找到一个与它最相似的对象，然后用这个相似对象的值来进行填充。不同的问题可能会选用不同的标准来对相似进行判定。该方法概念上很简单，且利用了数据间的关系来进行空值估计。这个方法的缺点在于难以定义相似标准，主观因素较多。
K最近距离邻法（K-means clustering）
先根据欧式距离或相关分析来确定距离具有缺失数据样本最近的K个样本，将这K个值加权平均来估计该样本的缺失数据。
使用所有可能的值填充（Assigning All Possible values of the Attribute）
用空缺属性值的所有可能的属性取值来填充，能够得到较好的补齐效果。但是，当数据量很大或者遗漏的属性值较多时，其计算的代价很大，可能的测试方案很多。
组合完整化方法（Combinatorial Completer）
用空缺属性值的所有可能的属性取值来试，并从最终属性的约简结果中选择最好的一个作为填补的属性值。这是以约简为目的的数据补齐方法，能够得到好的约简结果；但是，当数据量很大或者遗漏的属性值较多时，其计算的代价很大。
回归（Regression）
基于完整的数据集，建立回归方程。对于包含空值的对象，将已知属性值代入方程来估计未知属性值，以此估计值来进行填充。当变量不是线性相关时会导致有偏差的估计。
期望值最大化方法（Expectation maximization，EM）
EM算法是一种在不完全数据情况下计算极大似然估计或者后验分布的迭代算法。在每一迭代循环过程中交替执行两个步骤：E步（Excepctaion step,期望步），在给定完全数据和前一次迭代所得到的参数估计的情况下计算完全数据对应的对数似然函数的条件期望；M步（Maximzation step，极大化步），用极大化对数似然函数以确定参数的值，并用于下步的迭代。算法在E步和M步之间不断迭代直至收敛，即两次迭代之间的参数变化小于一个预先给定的阈值时结束。该方法可能会陷入局部极值，收敛速度也不是很快，并且计算很复杂。
多重填补（Multiple Imputation，MI）
多重填补方法分为三个步骤：
为每个空值产生一套可能的填补值，这些值反映了无响应模型的不确定性；每个值都被用来填补数据集中的缺失值，产生若干个完整数据集合。
每个填补数据集合都用针对完整数据集的统计方法进行统计分析。
对来自各个填补数据集的结果进行综合，产生最终的统计推断，这一推断考虑到了由于数据填补而产生的不确定性。该方法将空缺值视为随机样本，这样计算出来的统计推断可能受到空缺值的不确定性的影响。该方法的计算也很复杂。
C4.5方法
通过寻找属性间的关系来对遗失值填充。它寻找之间具有最大相关性的两个属性，其中没有遗失值的一个称为代理属性，另一个称为原始属性，用代理属性决定原始属性中的遗失值。这种基于规则归纳的方法只能处理基数较小的名词型属性。
就几种基于统计的方法而言，删除元组法和平均值法差于热卡填充法、期望值最大化方法和多重填充法；回归是比较好的一种方法，但仍比不上hot deck和EM；EM缺少MI包含的不确定成分。值得注意的是，这些方法直接处理的是模型参数的估计而不是空缺值预测本身。它们合适于处理无监督学习的问题，而对有监督学习来说，情况就不尽相同了。譬如，你可以删除包含空值的对象用完整的数据集来进行训练，但预测时你却不能忽略包含空值的对象。另外，C4.5和使用所有可能的值填充方法也有较好的补齐效果，人工填写和特殊值填充则是一般不推荐使用的。
不处理
补齐处理只是将未知值补以我们的主观估计值，不一定完全符合客观事实，在对不完备信息进行补齐处理的同时，我们或多或少地改变了原始的信息系统。而且，对空值不正确的填充往往将新的噪声引入数据中，使挖掘任务产生错误的结果。因此，在许多情况下，我们还是希望在保持原始信息不发生变化的前提下对信息系统进行处理。
不处理缺失值，直接在包含空值的数据上进行数据挖掘的方法包括贝叶斯网络和人工神经网络等。
贝叶斯网络提供了一种自然的表示变量间因果信息的方法，用来发现数据间的潜在关系。在这个网络中，用节点表示变量，有向边表示变量间的依赖关系。贝叶斯网络仅适合于对领域知识具有一定了解的情况，至少对变量间的依赖关系较清楚的情况。否则直接从数据中学习贝叶斯网的结构不但复杂性较高（随着变量的增加，指数级增加），网络维护代价昂贵，而且它的估计参数较多，为系统带来了高方差，影响了它的预测精度。
人工神经网络可以有效的对付缺失值，但人工神经网络在这方面的研究还有待进一步深入展开。
知乎上的一种方案：
4.把变量映射到高维空间。比如性别，有男、女、缺失三种情况，则映射成3个变量：是否男、是否女、是否缺失。连续型变量也可以这样处理。比如Google、网络的CTR预估模型，预处理时会把所有变量都这样处理，达到几亿维。这样做的好处是完整保留了原始数据的全部信息、不用考虑缺失值、不用考虑线性不可分之类的问题。缺点是计算量大大提升。
而且只有在样本量非常大的时候效果才好，否则会因为过于稀疏，效果很差。
总结
大多数数据挖掘系统都是在数据挖掘之前的数据预处理阶段采用第一、第二类方法来对空缺数据进行处理。并不存在一种处理空值的方法可以适合于任何问题。无论哪种方式填充，都无法避免主观因素对原系统的影响，并且在空值过多的情形下将系统完备化是不可行的。从理论上来说，贝叶斯考虑了一切，但是只有当数据集较小或满足某些条件（如多元正态分布）时完全贝叶斯分析才是可行的。而现阶段人工神经网络方法在数据挖掘中的应用仍很有限。值得一提的是，采用不精确信息处理数据的不完备性已得到了广泛的研究。不完备数据的表达方法所依据的理论主要有可信度理论、概率论、模糊集合论、可能性理论，D-S的证据理论等。
9. C语言中0.5f代表啥,和0.5F有区别么
f指float型，c中的实数默认为double，除非后面跟着f的才指float。若把它赋给一个float型变量则会有精度损失的编译警告提示，0.5f的意思是告诉编译器将这个0.5按float型处理。这里的0.5f和0.5F没有区别。例如0xa5、0Xa5、0xA5、0XA5完全相同。
(9)em算法的例子扩展阅读：
单精度浮点型（float ）专指占用32位存储空间的单精度（single-precision ）值。单精度在一些处理器上比双精度更快而且只占用双精度一半的空间，但是当值很大或很小的时候，它将变得不精确。当你需要小数部分并且对精度的要求不高时，单精度浮点型的变量是有用的。
双精度型，正如它的关键字“double ”表示的，占用64位的存储空间。在一些现代的被优化用来进行高速数学计算的处理器上双精度型实际上比单精度的快。所有超出人类经验的数学函数，如sin( )，cos( ) ，tan()和sqrt( )均返回双精度的值。