资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,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）对孤立点敏感，有噪音时效果差（可能性聚类？）,我的想法：,1）运用模糊的思想,2）可否以下式为目标函数：(效果较k均值差）,
展开阅读全文