EM算法主要思想.ppt

EM算法韩旭东2010.6.181.内容概述1、背景简介2、问题描述3、EM算法原理4、结论与讨论2.1、背景简介EM是一种聚类算法聚类：将数据集中的数据分成若干类（簇），使类内相似度尽可能大，类间相似度尽可能小。聚类算法：基于划分的方法（K均值）、层次聚类、基于密度的方法、基于网格的方法、基于模型的方法。3.2、问题描述EM算法是基于模型的聚类方法，假设样本分布符合高斯混合模型，算法目的是确定各个高斯部件的参数，充分拟合给定数据，并得到一个模糊聚类，即每个样本以不同概率属于每个高斯分布，概率数值将由以上各个参数计算得到。4.2、问题描述（续）高斯混合模型被定义为M个高斯密度函数的线性组合：其中 为均值为 ，协方差为 的高斯分布，是混合参数，看做第i个高斯分布的权重，表征先验概率。且5.2、问题描述（续）的概率密度函数为参数估计的最常用方法是最大似然估计，通过使似然函数达到最大值得到参数的估计值。将高斯混合密度函数中所有待定的参数记为 ，则似然函数为：6.2、问题描述（续）为了使问题简化，我们求的最大值。这里由于有和的对数，求导后形式复杂，因此不能使用一般的求偏导并令导数为零的方法。7.3、EM算法原理简化的问题：某混合高斯分布一共有k个分布，并且对于每一个观察到的x，如果我们同时还知道它是属于k中哪一个分布的，则求各个参数并不是件难事。比如用z来表示每一个高斯分布，那么我们的观察集不仅仅是x1,x2,x3,而是(x1,z2),(x2,z3),(x3,z1)而现实往往是：我们不知道每个x属于哪个分布，也就是说z是我们观察不到的，z是隐藏变量。8.3、EM算法原理（续）假定可以观察到Z，问题变为求下式最大值但是Z是观察不到的，因此EM算法假设Z的分布依据上一轮的估计参数确定，求取上式期望的最大值。定义：9.10.对上式使用拉格朗日乘数法可得求偏导并令值为零分别得：11.其中，可由下式求得。12.EM算法的具体流程为重复执行以下两个步骤直到收敛:第一步称为E步骤，是根据参数初始值或上一次迭代所得结果值来计算似然函数 关于条件分布 的期望：第二步称为M步骤，是将似然函数最大化以获得新的参数值，用 更新 使 最大化。13.4、结论与讨论1）EM算法比K-means算法计算复杂，收敛也较慢，不适于大规模数据集和高维数据，但比K-means算法计算结果稳定、准确。（数学手段加快收敛）2）需要已知样本聚类数目（？）3）对初值敏感（可以多运行几次解决/密度/最大最小原则/模糊/）4）爬山技术，局部最优解（可以多运行几次解决?）5）对孤立点敏感，有噪音时效果差（可能性聚类？）14.我的想法：1）运用模糊的思想2）可否以下式为目标函数：(效果较k均值差）15.