（应用数学专业论文）基于改进em算法的混合模型参数估计及聚类分析.pdf

中文摘要 e m 算法山j 二在参数估计等领域的广泛应用，近年来发腱十分迅速。 但e m 算法也存在一然自身缺陷，诸如迭代公式推导复杂，收敛速度对迭代 初值选取依赖较大，以及如何将其改进用于混合分支数未知情况一f 的混合模型 参数估计润题，本文j l t 是慕1 3 二对上述闽题的解决加以展开的。 首先，在r 奉文第章大致介绍了e m 算法的产生背景及其原理、性质。 其次，在第二章中，通过具体的算法实施过程，向读者展示了e m 算法在混 合模型参数估计中原理简译、思路清晰的优越性，同时也让读者感受到推导 过程的复杂性，綦于此，本文采取将复杂问题拆解为简肇问题累加的处理思 路，给出九，女进的e m 算法在混合m 态参数彳士计中达代公式的推导过程，且 迭代公式与传统e m 算法一致，但推导过程相对简便。同寸，给f n 了一种基 于k m e a n s 聚类算法的迭代初值选取方法。在第三章中，由于用e m 算法在 混合模戮参数估计中涉及到运用后验概率密度实现数据分组，加大了计算的复 杂度，影响了算法的效率。本文参照常规k m e a n s 动态聚类法，在每次迭代 过程将参数修正和数据聚类交替完成，并引进示性函数，将复杂的带小数的数 据转化成m 1 离散型数据，降低了运算的复杂度。如何确定聚类个数一直是 聚类分析中一个难点本文在传统e m 算法的基础上引进了竞争惩罚权重囚 予，使多余的分支密度函数淘汰，而将真j f 的分支加以保留，从而确定模型的 分支个数，再用传统e m 算法求解模型参数，从而解决了分支个数未知情况 下混合模型的参数估计t 问题。在奉文结束部分给小的数据聚类和参数估汁的数 值模拟结果反映了上述改进算法的可行性。 关键词 混合模型，e m 算法，后验概率密度，参数估计，聚类分析，数值模拟 a b s t r a c t ( 英文摘要) e ma l g o r i t h m ( e x p e c t a t i o n - m a x i m i z a t i o n ) a l g o r i t h m ，a 8ab r e a k t h r o u g h d e v e l o p m e n to fm a x i m u ml i k e l i h o o de s t i m a t i o n ，w a sp r o p o s e di nt h ea r t i c l eo f t h em a x i m u ml i k e l i h o o df r o mi n c o m p l e t ed a t av i at h ee ma l g o r i t h mb yd e m l s t e ri n19 7 7 i th a sb e e nw i d e l ya p p l i e di nd a t am i n i n g ，i m a g ep r o c e s s i n g ，b i o - s t a t i s t i c sa n dr e l i a b i l i t ya n a l y s i sa n dt h eo t h e rf i e l d s ，p a r t i c u l a r l yi np a r a m e t e r e s t i m a t i o na n dc l u s t e ra n a l y s i su n d e rt h em o d e lo fm i x e dm u l t i - b r a n c h b u t ， e ma l g o r i t h ma l s oh a ss o m ed e f i c i e n c i e s ，s u c ha si t e r a t i v ef o r m u l ad e r i v e rc o r n p l e x ，t h ec o n v e r g e n c es p e e do ft h ea l g o r i t h mi sv e r ys e n s i t i v et oi t e r a t i v ei n i t i a l v a h l ea n dh o wt oi m p r o v ei tt os o l v et h ep r o b l e mo fp a r a m e t e re s t i m a t i o no f m i x t u r em o d e lw h e nt h et r u em i x t u r en u m b e ri su n k n o w n t h ep u r p o s eo ft h i s p a p e ri st ow i v et h ea b o v eq u e s t i o n f i r s to fa 1 1 i no r d e rt of a c i l i t a t et h er e a d e r su n d e r s t a n do ft h en e x ts e c t i o n ，t h ef i r s tc h a p t e rg e n e r a l l yi n t r o d u c e dt h eb a c k g r o u n d ，t h ep r i n c i p l ea n d t h ec h a r a c t e ro ft h ee ma l g o r i t h m s e c o n d l y , t h es e c o n dc h a p t e rs h o w st h es u - p e r i o r i t yo fp r i n c i p l es i m p l e ，i d e ac l e a ro ft h ee ma l g o r i t h mb ys e t t i n gm i x e d n o r m a ld i s t r i b u t i o nm o d e lp a r a m e t e re s t i m a t i o na sa ne x a m p l ea n dt h r o u g hs p e - c i f i ca l g o r i t h mi m p l e m e n t a t i o np r o c e s s m e a n w h i l e ，i tr e f l e c t e dt h ed i s a d v a n t a g e o fi t e r a t i v ef o r m u l ad e r i v e dc o m p l e x b a s e do nt h ea b o v e ，t h i sp a p e rg i v e sa m e t h o dt h a ti m p r o v e de m a l g o r i t h mt os i m p l i f yt h ep r o c e s so fi t e r a t i v ef o r m u l a d e r i v e d m e a n w h i l e ，i tp r o p o s e dam e t h o dw h a ti sh o wt os e l e c ti t e r a t i v ei n i t i a l v a h m i nc h a p t e rt h r e e ，b e c m m eo fn e e dd a t ap a c k e ti nt h ep r o c e s so fp a r a m e t e r e s t i m a t i o n ，b u tm s t e pi n v o l v e dt h ep o s t e r i o rp r o b a b i l i t yc a l c u l a t e ，i ti n c r e a s e s t h e c o m p u t i n gc o m p l e x i t ya n da f f e c t st h ee f f i c i e n c yo ft h ea l g o r i t h m t h i sp a p e r f i n i s h e sa l t e r n a t i v e l yp a r a m e t e rm o d i f i c a t i o na n dd a t ac l u s t e ra te a c hi t e r a t i v e p r o c e s sb yr e f e r r i n gd y n a m i ck - m e a n sc l u s t e ri no r d e rt or e d u c et h ec o m p u t i n g c o m p l e x i t ya n dc o n v e r tc o m p l e xd e c i m a li n t o0 - 1d i s c r e t ed a t ab yi n t r o d u c ei n d i - c a t o rf i m c t i o n h o wt od e t e r m i n et h em l m b e ro fc h m t e ri sa l w a y sa ni n t r a c t a b l e p r o b l e m i nt h i sp a p e r ，w ep r o p o s et h er i v a lp e n a l i z a t i o nm e c h a n i s mt h a te n - a b l e st h er e d u n d a n td e n s i t i e si nt h em i x t u r et ob eg r a d u a u yf a d e do u td u r i n gt h e l e a r n i n g i tc a l la u t o m a t i c a l l ys e l e c t8 2 1a p p r o p r i a t en u m b e ro fd e n s i t i e sm i x t u r e c h m t e r i n g t h ee x p e r i m e n t sh a v et h ep r o m i s i n gr e s u l t s k e y w o r d s m i x t u r em o d e l ，e ma l g o r i t h m ，p o s t e r i o rp r o b a b i l i t y , p a r a m e t e re s t i m a t i o n ， m l m e r i c a is i m u i a t i o n 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名龃考 指导教师签名：雹垒幽 k 7 年乡月日k 7 年么月e l 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研 究工作及取得的研究成果。据我所知，除了文中特别加以标注和 致谢的地方外，本论文不包含其他人已经发表或撰写过的研究成 果，也不包含为获得西北大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 嚣搿弘啄侈纠年z 月多日 婀：i 匕人学硕l 7 - 位论文 1 1 引言 第一章绪论 混合模型已j 泛应用到作物育种、图像处理、语音泌别、手写特征谚 别、 生物聚合物种中的基序发现，人脸谚5 别和跟踪等多个领域，但混合模型的参数 估计不像一般简蚺模型参数估i = 1 那样易：j ：处理，常规的极大似然估计、最小二 乘估汁等方法对混合模型的处理失去了效力。直到1 9 7 7 年，d e m s p t e r 等人提 出用e m 算法( e m 足e x p e c t a t i o n - m a x i m i z a t i o n 的缩写) 来估计混合分布的 参数【6 1 ，e m 算法通过引进潜变量的方法将不完全信息数据问题转化为宪全 数据问题期i 以处理，1 ；l 迭代方法便于计算机处理，给海量数据的处理带来便 利，它的出现给混合模型n ：根基的处理带米了发展的契机，但e m 算法自身也 存在些缺陷，如它属j ：局部收敛算法、阻迭代初值对收敛速度影响较大。 由于e m 算法简单、实用，及对海量数据处理的优越性，随着信息时代的到 来，数据处理的压力逐渐增加，对e m 算法的进一步探讨和发腱极为必要。 在e m 算法i j j 现之后，产生了一姥基于e m 算法的衍生e m 算法，如j j 予多维混合分布参数估计的g e m 算法( g e n e r a le x p e c t a t i o n m a x i m i z a t i o n ) ， 当期望解析表达式不易求得时，采用近似计算的m c e m 算法( m o n t ec a r l o e m ) ，以及f i g a m i r e d o 在 8 j 中提：n 了传统e m 算法依赖初值和可能收敛到参 数空间边界等弊端，并基于此给f j = ；了修改的e m 算法。随着数据挖掘和机器 学习等学科的深入发展，给e m 算法的发腱带来了更加j “阔的甲台。 本文的大体框架构成姐f ： 首先，通过极大似然估计引入e m 算法，并对其算法原理以及一些重要 性质加以介绍，最终得 i = ；了e m 算法住混合参数估计方面具有两大优势：一 方面在于它所涉及的理论简单易行，二是由f 在迭代过程中参数明照的不断更 粹优化儿结构循环封闭，所以便：f ：计算机编程运算，给海量数据的处理带来了 便利。 1 第一常绪论 其次，第一部分给出了e m 算法在混合模型参数估汁中的具体实施步 骤，以较为常见的混合形态模型为例，通过其参数估计过程米说明传统e m 算法在求取参数迭代公式时计算量大、推导过程复杂的问题，基。n 比，本文采 取将复杂b 习题拆解为简单0 ：d 题累加的处理思路，给m 了改进的e m 算法在混 合m 态参数估计中迭代公式的推导过程，j ；! l 迭代公式与传统e m 算法一致， 但推导过程相对简便。同时，对手e m 算法达代初值选取对迭代速度影响这 一问题，给出了一种基于k i i l e a i i s 聚类算法的迭代初值选取方法。最后介绍 了m c e m 及g e m 两种衍牛e m 算法。 再次，由二f ：用e m 算法实现混合模型参数估计时必然要经过数据分组， 所以，混合模型数据聚类便成了参数估计过程中有价值的剐产物，这就足e m 聚类法，但i 二述算法的m 步山。 一加入了后验概率的运算，加大了计算的复杂 度，影响了算法的效率，基于此，结合第二章从一般到特殊的问题转化思路， 并参照常规k m e a n s 动态聚类，将j 二述e m 算法加以改进，在改进算法巾， 每次迭代过程将参数修m 和数据聚类交替完成，并弓l 进示性函数，将复杂的带 小数的数据转化成0 - 1 离敞型数据，降低了运算的复杂度。而当聚类数闷未知 时，传统的e m 算法将无能为力，有序样本数据的聚类可以利用f i s h e r 聚类 法 5 6 l ，但来自混合模型数据( 分支个数未知情况卜) 的聚类一直得不到搬好 的解决，本文存传统e m 算法的基础f ：引进了竞争惩罚权熏因予，使多余的 分支密度函数淘汰，而将真正的分支加以保留，最终得到符合要求的模型参 数，实现数据聚类。 最后，在第四章我们对文中涉及的改进e m 算法以及慕于改进e m 算法 所产生的聚类方法做了数值试验，以便给上述算法的优越性一个直观的体现。 1 2 预备知识 e m 算法( e m 足e x p e c t a t i o n m a x i m i z a t i o n 的缩写) 作为极大似然估计 的继承和发腱，在e m 算法引入之前有必要简单介绍一下极大似然估汁的原 2 两：| 七人学颀i 二学位论文 理和方法。 极大似然估计足一种概率论在统计学上的应_ f l ，它是参数彳士讨的常用方法 之一。荇已知某个随机样本满足某种概率分布，但足其中具体的参数不清楚， 参数估计就是通过若干次试验，观察其结果，利用结果推出参数的大概值。极 大似然估计是建立在这样的思想一l 二：若某个参数能使这个样本出现的概率最 大，就把这个参数作为估汁的真实值。为方便沦文中有关部分理解，特给 f j 以 下引理【2 l ： 引理1 2 1 歧p ( z ；p ) ，口0 足( r n ，b w , ) 上的一族联合概率密度函数， 对给定的z ，称 l ( o ；z ) = k p ( z ；秒) 为口的似然函数，其中k 0 是不依赖：j f ：p 的景，常取七= 1 。进步，若 存在( 兄n ，b r 。) 到( 0 ，b o ) 的统汁量多( z ) 使 ( p ；z ) = s l l p ( 口；z ) 日 则否( z ) 称为秒的一个极大似然估计( m a x i m u ml i k e l i h o o de s t i m a t e ) ，简 称m l e 。 由于概率密度函数大多具有指数函数形式，采用似然函数的对数通常更为 简便，称 z ( p ；z ) = i n l ( p ；z ) 为口的对数似然函数。由二r 对数变换足严格单调增加的故z ( 口；z ) 与l ( o ；x ) 在寻求极大值时足等价的。 当m l e 存在时，寻找m l e 最常用的方法是求导数。如果毋0 ) 是o 的 内点，则百 ) 足下列似然方程 的解。 0 1 ( o ；x ) o o i = 0 i = 1 ，2 ，3 ，七 3 第一章绪论 而e m 算法的m 现把极大似然估计推，到一个新的领域，如今e m 算法 已经渗透到机器学习( m a c h i n el e a r n i n g ) 和数据挖掘( d a t am i n i n g ) 等学科 领域。卜面给出e m 算法的原理和具体推到过程 2 l 。 一：e m 算法原理 e m 算法足一种不完全数据参数竹计的迭代算法，最初山d e m p t e r 等人 提出，并主要用j j 二求后验分布的众数( 即极大似然估汁) ，它的每一次迭代由 两步组成：e 步( 求期望) 和m 步( 极大化) 。一般地，以p ( o l y ) 表示口的 基二! f ：观测数据的后验分布密度函数，称为观测后验分布，p ( o ly z ) 表示添加 数据z 后得到的关二l 二0 的后验分布密度函数，称为添加后验分布，p ( z l o ，y ) 表示在给定0 和观测数据y 下潜在数据z 的条件分布密度函数。它的主要思 想足：尚p ( o l y ) 的似然函数形式过r 复杂和难以极大化时，引入潜变量或未 知变量，与此同时，假砹潜变量是已知的，从而用形式简单的完全数据分布的 密度函数p ( o l kz ) 的极大化形式代替非完拿数据分布密度函p ( o i y ) 的极大化 形式，然后对p ( o i kz ) 关二| 二潜变最z 求期梁，从而e z p ( o i v , z ) 】变成了关 于p 的一元线性函数，对它极大化便可以得到0 的极大似然估计值口。一般由 于分布密度函数为指数形式，常用自然对数的似然形式e z 1 n p ( o i y , z ) 】o 二：e m 算法的估参过程 基本过程如下：假设有一组不完全的观测数据y = ( y l ，y 2 ，鲰) ， 希望使似然函数l ( o i y ) = p ( y i o ) 取值最大，但该似然函数形式相当复 杂，直接极大化不容易，放令x = ( y ，z ) 表示y = ( y l ，抛，y n ) 的完 全数据，其中z = ( z 1 ，2 ：2 ，) 表示不可观测数据。设x 的似然函数 为l ( o i x ) = l ( o i y , z ) ，吲其形式易：f 二极大化，给出参数空问0 一组初始 值e ( o ) ，并以此给m 潜变量z 的初始条件分布p ( z ly ，e ( o ) ) ，然后由f 面傅 步构成交精迭代过程。 记e ( ) 表示第t + 1 次迭代开始时的参数值，魁已知的，则第t + 1 次迭 代为： 4 两：i 匕人学f i j i i 二学住论文 e 步：将i n p ( o l y , z ) 关于z 的条件分布密度函数求期望，即 q ( o i o ( ，y ) = e z 1 n p ( o l y , z ) j o ( 扪，y 】 = l n p c o l y , z ) p 矧e ( ) ，y ) d z 目的在j ：通过秋分把潜变量z 秋掉，从而使上式变成一个关：于二e 的一元函 数，给m 步的极大化过程做准备。 m 步：将q ( o i o c 扪，y ) 极大化即求解e ( + 1 ) 使得 q ( o 件1 ) l e ( ，y ) _ m 廿a xq ( o i o c 0 , y ) 如此形成一次迭代e ( ) _ e ( f + 1 ) 。将i ：述e 步和m 步进行迭代：随至0 e ( 件1 ) 一e ( 。) 0 或l iq ( e ( 件1 i e ( 们，y ) 一q ( e ( 。l e ( 幻，y ) 0 允分小停止。 然而，有时要在m 步中找到最大的0 是不容易的，一个较简竹的方法是 找一个e ( 件1 ) ，使得 q ( o ( t + 1 ) 1 9 ( ，y ) q ( e ( l e ( ，y ) 这样的e m 算法称为广义e m 算法( g e n e r a le m ) 。 以- 卜的弓i 理及证明 兑明了e m 算法的收敛性【2 j 。 引理1 2 2e m 算法在每一次迭代后均提高( 观测) 后验密度函数值， 即： p ( e ( 件1 ) iy ) p ( e ( 。iy ) 证明：由全概率公式 p ( o l 互y ) = p ( z l o ，y ) p c o w ) = p ( o l kz ) p c z i y ) 对上式后面历项取自然对数有 l n p ( o i y ) = l n p ( o l y ，z ) 一l n p ( z l o ，y ) + i n p c z l y )( 1 2 1 ) 5 第一：擘绪论 设现在有估计e ( ) ，将上式对z 关于p ( z l o ( ，y ) 求期望，有 其中 l n p ( o y ) = 【i n p ( o l y , z ) 一l n p ( z l e ，) + l n p ( z i y ) 】p ( z 1 0 ( 0 , y ) d z = o ( o i o ( ，y ) 一日( e i e ( ，y ) + k ( e ( 扪，y )( 1 2 ，2 ) q ( o i o j ，y ) = e z 1 n p ( e ly z ) l e 廿j ，y 1 = l n p ( o l y , z ) p ( z l o ( y ) d z jz n ( e l o ( ，y ) = h ( z l o ，y ) p ( z i o ( 扪，y ) d z jz k ( o ，y ) = l n p ( z l y ) p ( z l o ，y ) d z jz i np ( o ( 件1 ) i v ) 一p ( e ( ) i f ) = q ( e ( + 1 i e ( ，y ) 一q ( e ( i e ( ，y ) 】一 h ( e ( t + 1 ) i e ( 扪，y ) 一日( e ( l e ( 扪，y ) 】 由j e n s e n 不等式， e z l o ( , ) , yi n ( 嬲) i n e z l o ( o , y ( 豁) _ 0 故 h ( e ( 件1 ) j e ( ，y ) 一日( e ( j e ( ，y ) 0 面e ( 件1 ) 是使q ( e ( t + 1 ) i e ( ，y ) 达到最大的，娃然 证毕。 q ( e ( 。+ 1 ) l e ( ，y ) 一q ( e ( ) i e ( f 1 ，y ) 20 引理1 2 3( 1 ) 如果v ( e l y ) 有上界，则l ( e ( ，y ) 收敛到某个+ ； ( 2 ) 如果q ( o i y ) 关| j = ：0 和y 都连续，则在关于l 的很一般的条件f ， 山e e l 算法得到的估汁序列e ( 2 ) 的收敛值e + 是三的稳定点。 6 两：i 匕久掌颀i 二学位论义 e m 算法的关键之处在于选择合适的“潜在数据”以简化计算。山以上的 分析过程可以看出，e m 算法作为一种迭代算法有着明娃的优势，主要表现在 一下两个方面：一方面在】。岂所涉及的理论简单易行：二二是山二j ：它在迭代过程 中参数明显的不断更祷优化n 结构循环封闭，所以便于计算机编程运算，给海 量数据的处理带- 柬了便利。鉴：l 二e m 算法的以j 二特点，e m 算法已广泛用j ： 混合模型的参数估计以及海量不完全数据的聚类分析近年来在基= ：神经网络 的数据挖掘方面备受重视。 7 第：二帝e m 算法_ ：混台分布参数估汁方面的心用 第二章e m 算法在混合分布参数估计方面的应用 2 1 混合模型的发展现状 h 前，混合模型的应用已经相当j “泛，主要包括以”f j l 个方面： 1 。作物育种：j a n s e n 和d e nn i j s ( 1 9 9 3 ) 1 1 】使用离斯混合模型模拟花粉粒大小 的分布。 2 图像处理：l u t t r e l l ( 1 9 9 4 ) 1 4 l 使用分区混合分布来进行底层图像的处理。 3 语音识别：j u a n gj f i ir a b i n e r ( 1 9 8 5 ) 1 2 1 描述了如何用隐马尔科夫模型方法进 行孤立数字识别，其中与马尔科夫的每个状态相关的概率密度函数足高斯混合 模型。 4 手写特征识别：r e v o w 等( 1 9 9 6 ) a 4 1 对传统的混合模型( 均值限 ：样本中) 进行了改进，弗将用：- j ：手写数字识别h a s i t e 和t i b s h i r a n i ( 1 9 9 6 ) 1 0 l 应用他们 的混合判别分析方法对手写的3 ，5 和8 进行了分类。 5 牛物聚合物中的基序发现：b a i l e y 和t i b s h i r a n i ( 1 9 9 5 ) 4 l 使用两分量混合模 型在一组未结盟的基囚或蛋口质序列中识别基序( 一组核或氨基酸序列的能承 担一魑生物属性的公约模式) 。 6 人脸识别和跟踪；在人脸识别研究中( m c k e n n a 等，1 9 9 8 ) 1 5 1 ，标识 每个对象脸部特征的数据( 2 0 维到4 0 维的特征向量) 用离斯混合模型 来模拟，其分量参数用e m 方法估汁，再用b a y e s 规则估计密度来进行分类。 2 2 基于e m 算法的混合模型参数估计 下面给出有限混合元模型的形式：设z = ( x l ，z 2 ，z n ) 足来 | 某混合 分布的n 个数据，1 i z i 服从以下分布 8 如 z p巧 仇似 i | ez p z 陌：i 匕夫学l i j i i 二学位论文 其中0 = ( 7 r 1 ，7 1 - 2 ，丌m ，口l ，如，) 表示待估汁的混合分布的参数，乃袭 m 示毛来自各分支分布纷( 甄i 易) 的可能性。且：丌j = 1 ，乃之0 ，m 足有限 j = l 混合模型的分支个数。 对二r 相互独立的n 个来自某混合模型分布的数据，给：“它的自然对数形 式的似然函数： n h l c o i x ) = i n p ( x 1 0 ) i = l 由于上式包含了和的对数形式，这样的形式给极大化带来了困难，如果我们 视z = ( z l ，z 2 ，z n ) 为非究全数据，同时引入潜变量y = ( y l ，抛，y n ) ，若 p ( 犰= j ) = 乃= m a ) 【乃i = l ，2 ，n j = 1 ，2 ，m 我们就认为x i 是来臼第j 个支分布的数据，即： z t 一巧( 甄i 乃) 假设我们知道潜变母y = ( y l , 耽，y n ) 的具体值，则包含y = ( y l ，y 2 ，) 的完全数据的极大化形式较之上面非完全数据的极大化形式就会大大简化，形 式如下： l i il c o i x ，y ) = l n p ( x ，u l o ) n = l n p ( z i i ! ，1 ) p ( 犰) i - - - - 1 遗憾的足我们并不知道y = ( y 1 ，y 2 ，) 的具体值，从而对- j ：上面 这个二元变量函数，无法通过极大似然估计来得到参数e 的显式 解，必须想办法消去潜变量爹= ( y l ，箩2 ，暑f n ) ，为此，我们随机给 出关于待估参数0 = ( f f l ：7 r 2 ，7 r m ，0 1 ，如，) 的一组初始值e ( o ) = 9 钐 甄 巧 丌 仇皿 n n ：i l i 玑 伊 z 陬班 丌 h 。斟 = 第_ 常e 算法n ：混台分布参数儒汁方面的心用 ( 7 r i 0 ，7 r ，7 r g ，p i 0 ，卵，嘏) ，对一二给定的e ( o ) = 何i 0 ，7 r 笋，7 r 震， 口( o ，p ，鹋) ，我们容易汁算乃( 以嘭。) ( 对于每个i 和j ) ，加之，我 们可以视面o 作为y i = 歹的先验概率，囚此，根据b a y e 8 定理有： 和 p ( 如e ) = 镨 p ( x l y , ，e ( o ) ) p ( 玑f e ( o ) ) = 一 p ( x i l o ( o ) ) 摆欺( & j 螋) 丌? p - 一c ( z “卵) k = l n p ( v l z ，e ( o ) = 1 1p c y i l x i ，e o ) t = l 有了关l j ：潜变量y = ( y 1 ，轭，y n ) 的后验分布函数，就可以对完全数据 的对数似然函数芙j ：潜变量可= ( y l ，抛，) 求期望，从而将其变成一个关 二1 ：待估参数e 的一元函数( 视待估参数为一个整体) ，具体过程如下【3 0 l ： q ( o ，e o ) = l n ( l ( o l z ，y ) ) p ( y i x ，e o ) 其中 玑掣 ff t 一一一l n ( t r 矾p u 。( 盈i 瓯) ) n p ( 黝i 巧，e o ) cj ，1 ， m ，y i2 i 【0 ， y i = l 时，l = 1 ，2 ，m 否则 1 0 、l ， t l -22 ，- 、 l=1 f l 欺 l = 妇 1 = iy 1 = l =l i n i - i p _ , 人学顾l 学位论文 我们注意到： 由r j mmmmi p l y l = 1 n 嚣i i ( 玑一l = ly i + t - - - - 1y n = lj = 1 ，j i m p ( 协l 巧，e ( o ) ) ) p ( z k ，e ( o ) ) p ( 珊i 勺，0 0 1 ) ) p ( i x i ，0 o ) j = l ，歹 y s = l 故( 2 2 2 ) 简化为： 代( 2 2 3 ) 入( 2 2 1 ) ，得 仇n q ( o ，e o ) = i = 1 m = 1 n m p ( y j l x j ，e o ) = 1 y i = l p ( t l x ，e ( o ) ) l n ( t r l 聊( z t l 0 1 ) ) p c l l x t ，e ( o ) ) m，| ( 2 2 2 ) ( 2 2 3 ) h , c 7 r + ) p ( t l x t ，e o ) + l n ( p z ( x , l o + ) ) p ( z l x , ，e o ) 1 = 1i = 1l = 1i = 1 ( 2 2 4 ) 山：f ：饥和侥足相互独立的，故可以对等式右边的眄部分分别极大化。首 m 先引入l a g r a n g e 乘予和约束条件 l = 1 化简得 矾= 1 极大化等式( 2 2 4 ) 的前半部分： 云【i n ( 喇z i e ) + a ( 丌l 1 ) 】= o ( 2 2 5 ) l = 1l = 1= 1 娄扣e ( o ) = 。 ( 2 2 6 ) m 将7 1 l = 1 代入( 2 2 6 ) 式使可得到入= 一n ，然后将其代入( 2 2 6 ) 式得 z = l 到： m = 1 ( e ( 。) 1 1 ( 2 2 7 ) 第- 常e m 算法n ：混行分布参数估计方面的埘用 对于某蝗参数易于分离的分布( 般指数簇的分布就满足) ，我们可 以得到它的解析表达式。下面以混合正态分布为例给出o t 的估计形式， 设0 1 = ( 肌，1 ) ，概率密度函数为： p 如i 扣丽高驴唧【习1z 呻) t r 1 ( x - # 1 ) 】 ( 2 2 8 ) 将( 2 2 8 ) 代入( 2 2 4 ) 式右端的后半部分，并忽略运算中的常数项，有： l n ( p ( z t l u l ，f 1 ) ) p ( 1 l z i ，o c o ) ) l = 1t = l ，n7 1 。 = ( 一去l n ( i l i ) 一吉( 墨一肌) t f 1 ( q i u l ) ) p c i l x t ，e o ) ( 2 2 9 2 ) i = 1i t = j 对等式( 2 2 9 ) 关于肌求偏导数并令其为0 ，得到： 容易解得： n 孔p c l l x t ，e o ) t = 1 胁。气一 p ( 1 l z i ，e o ) i = 1 为了求得l 的解析表达式，将( 2 2 9 ) 式变换成如下形式： ( 2 2 1 0 ) ( 2 2 1 1 ) 砉p ( z ke ( o ) 打( f 1 ( 黾一u 1 ) ( x i 一肌) 丁) 】 i = 1 石1 p ( f i 耽，e ( o 协( f 1 l ，i ) 】 ( 2 2 1 2 ) i = 1 记肭，i = ( 毛一u 1 ) ( x i 一肌) t ) ，为简化i 二式，特给f 列矩阵运算相关公式， 设a 为刘称矩阵，则： 掣：2 a 一d i a g ( a 一1 ) d 丝毫丢盟= b + 日t 一旅n 9 ( 召) ( 2 2 1 3 ) ( 2 2 1 4 ) 其中t r ( a b ) 是矩阵a b 的迹，d i a g ( a 1 ) 表示j = f ! 阵a 的逆翘i 阵a - 1 形成的 对角矩阵。 0 | | ez 仃rpp z 一； n 汹 一 一 0 0 e e z z p p n曲。：l 0 0 n n l 一2 1 2 m言m = 两：i 七人学硕i 二。学位论文 根据一l 述公式，并对( 2 2 1 2 ) 式关下f 1 求偏导数，得： p c t l o o ) ( 2 l d i a g ( e z ) ) 一；1 p ( 恤，o o ) ( 2 肭- d i a g ( u t ，i ) ) l = ll = 1 专砉p ( f 啪( o ) ) ( 2 嘶一酬删 = 2 s d i a g ( s )( 2 2 1 5 ) 记：尬。t = z t - a r t s = 吾p ( i l = i ，o 们) m z p 要使( 2 2 1 5 ) 式为零，则s = 0 ，即： n p ( 1 l = i ，o o ) ( l 一l ，1 ) = 0 i = 1 故 p c t l z i ，o c o ) m ，i l = 立l 一一 p ( l = i ，e o ) i = 1 n p ( z ko o ) ( 戤一胁) ( 黾- g z ) t = 三l 百一 ( 2 2 1 6 ) n 、一， p ( 1 x i ，e o ) 至此，使得到参数汛，弘z ，1 ) 的迭代更新公式： e 埘= 时鲫= 三p ( e ( o ) ) z 护( z k0 o ) 聍鲫= 三 一 p ( t l = l ，e o ) l = 1 n p ( z ke o ) ( 以一p ：l ) ( 玩一聍鲫) t i = 1 ( 2 2 1 7 ) ( 2 2 1 8 ) ( 2 2 1 9 ) ez p n 汹 第：一：常e m 算法n ! 混台分布参敖估汁方面的心用 2 3 基于e m 算法的迭代公式推导过程改进 从k 节求解混合m 态模型参数的过程中，我们明显感觉到虽然上述方法 思路清晰，但求解过程中山 ：牵扯到多层积分和矩阵导数等理论，使得求解 过程相! 复杂，给e m 算法的推广带来不便。赫二f ：此，本文给 = i ：j 以下求解思 路，日的在：i f ：简化迭代公式的推导过程，使得形式复杂的混合分布模型也能通 过e m 算法求解。为便于说明，下面仍以混合正态分布模型的参数估汁问题 为例讨论。 在现实问题处理中，人们往往将新问题转化成j j 已知方法能解决的形式。 对二：| 二不完全数据的自然对数形式的似然函数 n i nl ( o i x ) = i nn p ( z t i e ) i = l ( 2 3 1 ) 我们弓入示性函数蜥作为潜在变量，f l f1 ， 戤一p jc z , t o j ) 峨 i = 1 ，2 ，n j = 1 ，2 ，m y i , i2 气 10 ， 否则 则 p ( y , j l o ) = 栌 ( 2 3 2 3 ) p ( 甄i ，e ) = 1 - ip j ( x 1 1 0 j ) y j ( 2 3 3 ) i nl ( o i z ，y ) = l n p ( x ，i e ) n = i n p ( x i y o ，o ) p c y i j i o ) i = l 1 4 ( 2 3 4 ) 如扛 乃q m 纠 h n 河 = 易 现 纷 n + 巧畦 玑 m 硝 n 甜 1 婀：l 匕久学顶j 二掌他论文 假定的值是已知的，则我们就可以将样本数据x i 分成m 个类，分别 为：a ，仍，从而l 述完伞数据的似然函数可变为： n i nl ( o x ，y ) = i n p ( x l y i j ，e ) p ( i e ) i = l = ( i n7 r l + i n l d l ( x l l 0 1 ) ) + + ( 1 i i 乃+ 1 m c 戤l e j ) ) x e c l z t q 十+ ( 1 i l 丌仇+ l n p m ( z i i o 仇) ) ( 2 3 5 ) x i e g “ 这样对似然函数的极大化n ：d 题就变成对备分支分别极大化，而极大化 ( i n 吩+ l n p j ( ：r d 0 a ) ( 2 3 6 ) z 岛 实际就足一个簿支分布模型极大化的过程，关j 二用极大似然估计法求啦史分布 模型参数这一问题已形成了许多成熟的迭代公式以供我们使j f i ，下面仍以正态 分布为例：令o j = ( 纷，j ) ，则 l n 巧( q f 易) = l n 乃( 甄i 心，歹) = l n 两南唧卜互1 ( z 一助) t 孔z 一酬( 2 3 7 ) 极大化后，易得参数的一般表达式： 坳= 熹妻蚋 坳2 豸各妒 马= 去喜( ：r i - - # j ) ( x i - - p j ) t 吩= 物 n j2l 勺i j 而乃表示毛来自第歹个分支的概率， 不难得n j 1 5 ( 2 3 8 ) ( 2 3 9 ) ( 2 3 1 0 ) 当已知的具体值时 ( 2 3 1 1 ) l = 町 m 芦 h 一n l i 玑 n h l n = 巧 第二帝e m 算法柏：淀 分布参数估汁方由o g j ；v 用 此时，我们已解决j 简化问题的参数估汁问题，但实际上我 们往往不知道y 巧的具体值，为得到本文所讨论参数估计问题的 恩式解，我们用潜在变量物的期望e y i