EM算法主要思想.ppt

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