（计算机应用技术专业论文）数据缺失下学习贝叶斯网的研究.pdf

数据缺失下学习贝叶斯网的研究 摘要 摘要 本文对数据缺失和网络结构未知情况下学习贝叶斯网问题进行了相关研究，并 提出了几个有趣有效的解决方案。 首先，利用并行策略下的p a c o b 算法提供良好候选网络结构，并借此构造新的 s g s p a c o b 和s e m p a c o b 算法。实验数据显示，在良好候选网络结构支持下，两 算法学习到的贝叶斯网质量有质的提高。 其次，建立了一种行之有效的改进s e m 算法( d s e m p a c o b 算法) 。该算法， 在估计结点变量缺失值时，不再像s e m 算法一样，依赖于当前最优网络所有可能参 与决策的结点变量，而是从当前最优网络中采用合理策略选择与待估结点变量紧密 相关的若干结点变量集合直接参与估计。实验证明，d s e m p a c o b 算法较之先前的 s e m 类似算法，不仅在最终学习到的贝叶斯网的质量上有质的提高，而且在算法的 稳定性上也有较大改进。 再次，基于s e m p a c o b 和d s e m p a c o b 等相关算法，选择具有代表性的网 络作为初始网络，并对初始网络在数据缺失情况下学习贝叶斯网整个过程中所扮演 的角色进行了实验性的探讨。充分实验数据显示，初始网络对整个算法的收敛速度有 很大影响，而且在训练数据集规模不充分和缺失率较高时，选择与训练数据集相关性 越高的初始网络，算法越能得到较好结果。 最后，提出了混合启发的思想，并具体建立了一种混合启发方法：d s e m - g s p a c o b 算法。它巧妙地利用a c o 算法的优良特性，把d s e m p a c o b 和s g 孓 p a c o b 算法通过相应数据补全策略得到的两种统计因子联合起来作为其本身 p a c o b 算法的启发因子。实验证明，d s e m g s p a c o b 算法充分保留d s e m p a c o b 和s g s p a c o b 算法两者的优点，促使算法能够平稳地收敛到理想结果。相 对于只具有单一数据补全策略的算法，该算法不仅在度量数据拟合程度的l 凹l o s s 值 上保持稳定，而且在学习到的贝叶斯网络结构上也有所改进。 关键词：学习贝叶斯网；数据补全策略；p a c o b 算法；新决策网络；初始网络；混合 启发策略 作者：廖学清 指导教师：吕强 数据缺失下学习贝叶斯网的研究 a b s t r a c t a b s t r a c t t h i st h e s i si sa b o u ts t u d yo nl e a r n i n gb a y e s i a nn e t w o r kw i t hm i s s i n gv a l u e s ，a n d t h e r e b y , p r e s e n t ss e v e r a lc r e a t i v ea n de f f i c i e n ts o l u t i o n s f i r s t l y , n e ws e m - p a c o ba n ds g s p a c o ba l g o r i t h mi sp r e s e n t e db a s e d o nt h e v a l u a b l en e t w o r ks t r u c t u r ec a n d i d a t e sf o u n db yap a r a l l e la c o bs o l u t i o n e x p e r i - m e n t ss h o wt h a t ，t h et w oa l g o r i t h m sm a k ea t t r a c t i v ei m p r o v e m e n t so nt h eq u a l i t yo f t h el e a r n e db a y e s i a nn e t w o r k s s e c o n d l y , ad s e m p a c o ba l g o r i t h m a ne f f i c i e n ta p p r o a c hb a s e do ns e ma l g o - r i t h m ，i sp r o p o s e d t h i sa l g o r i t h mu s e sr a t i o n a lt a c t i c st oc h o o s es e v e r a ln o d ev a r i - a b l e s ，w h i c hh a v ec l o s ec o r r e l a t i o n sw i t ht h ee s t i m a t e dn o d ev a r i a b l e ，a n dt oe s t i m a t e m i s s i n gv a l u e s t h ee x p e r i m e n t ss h o wt h a t ，c o m p a r i n gw i t hs e ma n ds e m p a c o b a l g o r i t h m ，d s e m p a c o ba l g o r i t h mg e t sq u a l i t a t i v ei m p r o v e m e n t so nt h eq u a l i t yo f t h ef i n a ll e a r n e db a y e s i a nn e t w o r k ，a n da l s om a k e st h ea l g o r i t h mc o n v e r g et oi d e a l r e s u l t sq u i t es m o o t h l y t h i r d l y , m a i n l ys e r v i n gf o rs e m - p a c o ba n d d s e m p a c o ba l g o r i t h m ，h o wt o s e l e c ta ni n i t i a ln e t w o r ki ss t u d i e d s u f f i c i e n te x p e r i m e n t a lr e s u l t ss h o wt h a tt h ei n i t i a l n e t w o r kp l a y sai m p o r t a n tr o l eo nc o n v e r g e n c es p e e do ft h el e a r n i n ga l g o r i t h m s i ti s c o n c l u d e dt h a ti ft h ed a t a s e t s c a l ei ss m a l la n dm i s s i n gv a l u e sp r o b a b i l i t yi sh i g h t h e c l o s e rm a t c h i n gb e t w e e ni n i t i a ln e t w o r ka n dt r a i n i n gd a t a s e t ，t h eb e t t e rf i n a lr e s u l t s a r e l a s t ah y b r i dh e u r i s t i ci d e ai si n t r o d u c e dt od s e m g s - p a c o ba l g o r i t h m t h e a l g o r i t h ms k i l l f u l l yu s e sc h a r a c t e r i s t i c so fa c oa l g o r i t h m a n dc o m b i n e st w os t a t i s t i c i n f o r m a t i o no ft h es g s - p a c o ba n dd s e m - p a c o ba l g o r i t h ma si t sp a c o ba l g o - r i t h m sh e u r i s t i ci n f o r m a t i o n t h ee x p e r i m e n t ss h o wd s e m g s p a c o ba l g o r i t h m f u l l yo u t p e r f o r m sb o t hs g s p a c o ba n dd s e m p a c o ba l g o r i t h m ，a n dm a k e st h e a l g o r i t h mc o n v e r g et oi d e a lr e s u l t ss m o o t h l y c o m p a r i n gw i t ht h o s ea l g o r i t h m sh a v - i n go n l yo n ed a t ac o m p l e t i o np o l i c y , d s e m g s - - p a c o ba l g o r i t h mn o to n l ya c h i e v e sa s t a b l el o g l o s sv a l u e ，a n da l s om a k e si m p r o v e m e n t so nt h el e a r n e db a y e s i a nn e t w o r k s t r u c t u r e k e y w o r d s ：l e a r i n gb a y e s i a nn e t w o r k ；d a t ac o m p l e t i o np o l i c y ；p a c o ba l g o r i t h m ； a b s t r a c t数据缺失下学习贝叶斯网的研究 n e wd e c i d i n gn e t w o r k ；i n i t i a ln e t w o r k ；h y b r i dh e u r i s t i c l v w r i t t e nb y ：x u e q i n gl i a o s u p e r v i s e db y ：q i a n gl i i 数据缺失下学习贝叶斯网的研究 插图 插图 2 1 数据缺失下学习贝叶斯网的一般流程 1 2 3 1p a c o b 算法主题框架图 1 9 3 2 哈希链表互斥机制图。1 9 3 3 a l a r m 数据集各算法m a x l o s s 的比较2 2 3 4 i n s u r a n c e 数据集各算法m a x l o s s 的比较2 2 4 1 4 2 4 3 4 4 4 5 当前最优网络中结点变量k 附近局部图 2 5 新决策网络中结点变量咒附近局部图 2 6 a l a r m 数据集d s e m - p a c o b ( d p a n u m = 4 ) ，s e m - p a c o b 和s g s - p a c o b 算法l o g l o s s 的情况比较2 9 i n s u r a n c e 数据集d s e m - p a c o b ( d p a n u m = 4 ) ，s e m - p a c o b 和s g s p a c o b 算法l o g l o s s 的情况比较。2 9 a l a r m 数据集中s e m - p a c o b 算法和d p a n u m 不同取值时的d s e m p a c o b 算法打分效率比较3 l 6 1a l a r m 数据集中s g s p a c o b ，d s e m p a c o b 和d s e m g s p a c o b 算法m a x l o s s 的比较4 3 6 2a l a r m 数据集中s g s p a c o b ，d s e m p a c o b 和d s e m - g s - p a c o b 算法i n t e r v a l 的比较。4 3 数据缺失下学习贝叶斯网的研究表格 表格 1 1 学习贝叶斯网问题的分类。1 3 1s g p a c o b 和s e m p a c o b 算法执行后的统计数据2 3 4 1 4 2 5 1 5 2 6 1 6 2 6 3 6 4 s g s p a c o b ，s e m - p a c o b 和d s e m - p a c o b ( d p a n u m = 4 ) 算法执 行后s a 统计数据。3 0 a l a r m2 0 缺失率数据集d p a n u ? 7 z 不同取值给算法带来的影响3 1 s e m p a c o b 算法各初始网络方案的相关统计数据 3 4 d s e m - p a c o b 算法各初始网络方案的相关统计数据 3 5 s g s p a c o b ，s e m p a c o b 和d s e m - p a c o b 算法i n t e r v a l 和s t d l o s s 的 统计数据 3 9 a l a r m 的2 0 缺失率数据中s g s - p a c o b ，s e m p a c o b 和d s e m p a c o b 算法主要边出现次数的统计数据。 4 0 a l a r m 的2 0 缺失率数据中d s e m g 孓p a c o b 算法主要相应边边出 现次数的统计数据，4 4 s g s p a c o b ，d s e m g s p a c o b 和d s e m p a c o b 算法执行后s a 统 计数据 4 4 数据缺失下学习贝叶斯网的研究算 法 算法 s e m 算法 a n t b 算法 p a c o b 算法 s e m p a c o b 算法 d s e m - p a c o b 算法。 d s e m _ g 孓p a c o b 算法 1 0 1 8 2 0 2 1 2 8 4 2 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名：亟望亟日 学位论文使用授权声明 期：卫麟堋1 8 同 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名：亟墨鱼 日期：二碑胡j 8 日 导师签名： 毳虢 日期：旦麟硼f 8 闩 数据缺失下学习贝叶斯网的研究第一章引言 第一章引言 贝叶斯网，由于能够充分结合图形表达方式和概率知识，较好展示联合概率分布 与因果关系的合理对应性，巧妙刻画对象之间和对象内部之间的形象联系，业已成为 在不确定情况下进行推理与决策的具有代表性的可计算的主流方式 1 】。 1 1 研究背景 由于贝叶斯网的完美优越性，仅靠专家知识通过非常繁杂的途径构造出不准确 贝叶斯网已经满足不了现实的需要。因此，如何从现实世界大量数据集中学习贝叶斯 网显得至关重要。现实世界大量容易获得的数据集以及现今计算机超强的计算能力 都为学习贝叶斯网提供了有利条件。 习惯上，众多学者把学习贝叶斯网问题按照数据集是否完备以及网络结构是否 已知分为如表1 1 所示的4 种情形【2 】。 网络结构已知 网络结构未知 数据完备1 概率参数学习：简单统计估计、2 找最优网络结构：以m d l 、b d e 等 m l e 方法、b a y e s i a n 方法为评分标准的启发式搜索等打分一搜 索算法以及c i 测试 数据不完备 3 找最优概率参数：e m 算法、基于梯4 既要找最佳结构，又要找最优参数： 度方法、蒙特卡洛法、高斯算法等有s e m 算法、混合模型、b n 。g s 算法 等 通过国内外学者多年研究，网络结构已知和数据完备，网络结构已知和数据不完 备以及网络结构未知和数据完备等3 种情形的解决方案已经相当成熟。但第4 种，也就 是网络结构未知和数据不完备的情形仍然存在着诸多疑难问题，大多数现有的方案 具有不稳定性，易收敛性，最优解不理想的情况。因此急待有更为普遍适用并且行之 有效的解决方案。 1 2 研究内容 数据不完备两大情形之一就是数据缺失问题【3 - - - - 1 1 练数据集中某一些数据记 录某些结点变量的具体属性值因某种原因缺失。l i t t l e 和r u b i n 把数据缺失问题又 分为非随机缺失问题和随机缺失问题【4 ，5 】。张连文等指出数据非随机缺失问题可以 第一章引言 数据缺失下学习贝叶斯网的研究 通过引入隐藏变量转化为随机缺失问题f 6 】。因此，本文的主要研究围绕着数据缺失 和网络结构未知情况下学习贝叶斯网的问题而展开。 详细研究内容包括： 1 提供更优候选网络 本文利用改进的a c o b 算法【7 以及采用多蚁群并行策略构建的p a c o b 算 法f 8 ，9 1 为数据缺失情况下学习贝叶斯网提供更丰富更优秀的候选网络结构，以 求取得良好效果。 2 构造新的决策网络 现今流行的学习算法在得到统计因子时会涉及到数据补全策略。可是许多算法 的数据补全策略具体估计变量取值时参与估计的其它变量数目极其不均衡。本 文根据s e m 算法【1 0 1 ，通过较为合理的选择策略构建新的决策网络，让参与估 计的结点变量的数目分布均匀，并且与待估结点变量关系密切，来求得更优解。 3 探索初始网络的角色 在目前有关文献中关于数据缺失下学习贝叶斯网问题都会涉及到初始网络。这 个初始网络到底如何给出? 它在整个学习贝叶斯网整个过程中所扮演的角色又 是如何? 诸多文献并没有给出统一意见。本文通过尝试选择各种具有代表性的 初始网络对此进行了实验性研究，以求得出重要结论。 4 混合启发策略 本文发现通过p a c o b 算法提供更优秀网络结构以及利用新决策网络代替当前 最佳网络参与估计的策略，虽然一定程度上改善了解的质量以及算法本身的稳 定性，但仍然存在着解质量波动性大，较易收敛的诸多问题。因此，本文利用 a c o 算法f 1 1 1 的特点，采用将两种或多种数据补全策略合并混合启发的策略， 来改善解的质量和提高算法的稳定性。 1 3 研究意义 数据缺失和网络结构未知情况下学习贝叶斯网问题本身就存在重要的现实意义。 如不能很好地解决，那么就说明贝叶斯网距离广泛的应用还有很大的距离。 数据缺失，这是一种很正常的现象。现实训练数据集在采集时难免会因为技术 等问题存在着数据记录中具体变量的具体属性值缺失的现象。 网络结构未知。这点很显然，正如前面提到的，仅靠专家知识确定的网络结构 费时，困难，而且不可靠，没有太多的说服力。所以，我们从庞大的现有的数据 集中学习到网络结构更能贴近实际。 2 数据缺失下学习贝叶斯网的研究 第一章引言 本文所采用的混合启发思想和多蚁群并行策略为今后对学习贝叶斯网问题的研 究方法提供了一个全新视角。 多蚁群并行的p a c o b 算法充分展现了计算机超强的计算能力，大大地加大了 搜索空问地同时，由于a c o 算法的天然优越性，还能够提供更优秀的候选网 络。 混合启发思想把两种或者多种不稳定算法结合a c o 算法的特点巧妙地结合在 一起，相互启发，互相制约，相互推进。该混合启发思想为未来算法发展方向提 供了一条重要思路。 1 4 本文的组织结构 本文的主要章节安排如下： 第一章主要介绍本文的研究背景、研究内容和研究意义。 第二章主要概述了学习贝叶斯网问题以及数据缺失与网络未知情况下学习贝叶 斯网的难点，主要研究方法，目前存在问题，主要实验训练数据集以及评价标准； 第三章简单陈述了a c o 算法和p a c o b 算法以及本文对上述两方法的创新点， 详细阐述了利用a c o b 算法和p a c o b 算法分别结合g s 补全策略【1 2 ，1 3 】和e m 补 全策略【1 4 】进行实验并对有关实验数据进行合理分析。 第四章提出了更为合理的数据补全策略d s e m ，并构建了d s e m - p a c o b 算 法： 第五章详细探讨多种初始网络对其在整个学习过程中所扮演的角色； 第六章介绍了混合启发的思想，并具体建立了一种混合启发方法一一d s e m - g s p a c o b 算法。 第七章本文的工作总结与展望。 3 数据缺失下学习贝叶斯网的研究第二章数据缺失下学习贝叶斯网概述 第二章数据缺失下学习贝叶斯网概述 2 1学习贝叶斯网概述 本章从定义相关符号和贝叶斯网开始。设u = 墨，x 2 ，k ) 为离散随机变量 集合，其中任意变量五可取有限属性值。我们定义大写字母，如x ，】厂，z ，为随机 变量名以及小写字母，如x ，y ，z ，为相应变量具体取值。变量集合用加粗大写字 母x ，y ，z 表示，其相应变量集合取值用加粗小写字母z ，y ，名表示。 贝叶斯网为一含有关于【厂联合概率分布的有向无环图。通常，关于u 的贝叶斯 网用b = ( g ，p ) 表示。j e i 中第一部分，也就是g ，是一张有向无环图。图g 的结点变量 对应于随机变量五，恐，。图g 的边表示各结点变量之间的条件独立假设：任意 结点变量直接依赖于它的父亲结点变量集，而与其它结点变量无关。b 中0 为网络参 数集合，即c p t 表。它包含所有结点变量五取鼢，在相应父亲结点变量集合咒取 值z ；时的概率p ( x l 霉。) 。贝叶斯网b 定义的联合概率分布即可表示为： b 隅，弼，) = i i 岛( 觑i 飘) i = l ( 2 1 ) 定义1 学习贝叶斯网b 即可表示为：给定训练数据集d = x l ，x 2 ，z ) ，找出最大匹配数 据集d 的贝叶斯网b 学习贝叶斯网有多种方法 1 5 】，其中最常见的是基于打分一搜索的方法【1 6 】。它 引入一打分函数来评定在给定数据集下任意贝叶斯网络的打分值，并通过搜索策略 找出打分值最好的贝叶斯网络。因本文采用m d l 打分机制【1 7 】，就以m d l 打分陈 述学习贝叶斯网问题。 给定贝叶斯网b = ( g ，日) 和数据集d = a 3 1 ，x 2 ，2 ) ，b 在d 下的m d l 打分即 可表示为： 1 n 口h f m d l ( b d ) = l ( b d ) 一：竿( b )( 2 2 ) 二 上式中( b ) 为网络b 的参数总数，它使打分函数偏向更为简单网络。而式2 2 中右边 第一部分为给定数据集d 下网络b 的对数似然函数，即为： n 己( b f d ) = 1 0 9 ( p b ( 兢) ) ( 2 3 ) i = l 5 第二章数据缺失下学习贝叶斯网概述数据缺失下学习贝叶斯网的研究 该似然函数富有统计意义：似然函数值越大，b 中的概率分布越拟合数据集d 。 当数据集d 中所有记录翰完备，也就是结点变量集合u 中任意结点变量都有具体 取值时，似然函数可以分解。设d 中x = z 的记录数为幌( z ) 。似然函数可分解为： l ( b i d ) = n ( x i ，h 戤) l o g ( p ( x t n 戤) ) ( 2 4 ) 瓤，l i z 从上式中可以看出当p ( 甄f 。；) = 丛n 型( n j 时似然函数最大。此外，z ，( j e 7 ) 不依赖于参 数的选择。因为此时m d l ( j e 7 d ) 就是相应模型的g 的m d l 打分。 其中 i m d l ( g p ) = f m d l ( b t d ( 2 5 ) 利用打分函数的可分解性原理，对于任意网络b ，打分值可分解为： f m d l ( b i d ) = 加砒 ( ，0 i d ) ( 2 6 ) 知。“( 托，吼i d ) = ( 甄，双) l 。g ( p ( 兢t n z 。”一t l o g n ( 五，x )( 2 7 ) 戤，n q y ( 五，i i 墨) 为表示p ( x l 置) 的参数总数。这种可分解性对于基于打分一搜索算法是 至关重要的。例如，当试图把结点变量玛加入到结点变量五的父亲恐中时，原贝叶 斯网打分值只需如公式2 8 修改即可。 f m d l ( b d ) = f m d l ( b d ) 一知d 工( x i 置) + f m d l ( x i i i i x , u 墨) ) ( 2 8 ) 当训练数据集d 某些记录中某些变量具体属性值缺失时，情况就完全不同了。在 这种情况下，似然函数，也就是m d l 打分函数无法分解，必须执行推理过程等方案进 行计算。而且因为此，随之带来了对网络结构g 的任一点局部改动都会影响到网络其 它相关部分评分的问题。与此同时，像网络结构已知和数据不完备情况下一样，也得 为学习过程中得出的候选网络结构寻找最佳参数。这就要用到e m 或最大梯度算法 等算法。 2 2目前主要算法概述 关于数据缺失情况下学习贝叶斯网的问题，国内外学者进行了研究并提出了诸 多算法。 6 数据缺失下学习贝叶斯网的研究第二章数据缺失下学习贝叶斯网概述 1 9 9 5 年，c h i b 等人借鉴参数学习的蒙特卡烙算法【1 2 】提出了一种可用于不完备数 据集网络结构边缘似然性计算的蒙特卡烙方法【1 8 】。该方法利用贝叶斯公式 p ( d i 驴掣群 ( 2 9 ) 公式2 9 右端分子的先验概率项p ( l b ) 可以直接估计和似然性项p ( d o b ，b ) 可 以通过贝叶斯推理计算，而分母的后验概率项p ( o b i d ，b ) 贝f j 可以用g s 策略估计。蒙 特卡烙方法非常准确，但是计算量大。当面对大规模的训练数据集时，计算所需时间 会成幂指数增长。 为了能处理大规模数据集，1 9 9 6 年g e i g e r 等对高斯近似中的问题进行了一系列研 究【1 9 】。在假定似然函数p ( o b i d ，b ) 拥有唯一m a p 值台等条件下时，高斯近似中的积 分2 0 , - i 采用拉普拉斯方法，称为拉普拉斯近似( 百为m l 值，p 为m a p 值) 。 l a p l a c e ( b i d ) = l o g ( p ( d i o b ，b ) ) + l o g ( p ( o b b ) ) + 若l o g2 7 r 一言1 0 9i a i ( 2 1 0 ) 公式2 1 0 中的p ( d f o b ，b ) 可以用贝叶斯推理计算，a 为赫斯行列式，d 为网络参 数总数。1 9 8 8 年k a s s 等已证明在某些条件下 2 l 】 il o gp ( d l b ) 一l a p l a c e ( b i d ) i o ( 1 n )( 2 1 1 ) 尽管拉普拉斯近似方法在一定程度上比蒙特卡烙方法来得有效，但需要计算计 算量庞大的赫斯行列式值f a l 。 早在1 9 7 8 年，s c h w a r z 就提出了一种非常有效但准确性稍差的近似方法一一贝 叶斯信息标准( b i c ) f 2 2 。它只保留了拉普拉斯近似式中随数据集规模n 增长的因 式。当取向与无穷时，赫斯行列式值l a l 趋于定值，以及m a p 值p 趋于m l 值扫。由 此，可以得到b i c 打分如公式2 1 2 b i c ( b d ) = l o g ( p ( d i o b ，b ) ) 一昙1 0 9 ( 2 1 2 ) 并且很容易得到公式2 1 3 il o gp ( d b ) 一b i c ( b d ) i 0 ( 1 )( 2 1 3 ) b i c 近似具有以下优点： 不依赖于先验概率，因此可以不估计先验概率分布，直接近似计算； 近似计算式相当简练 7 第二章数据缺失下学习贝叶斯网概述 数据缺失下学习贝叶斯网的研究 b c 近似恰巧等价于m d l 标准 1 9 9 6 年，c h i c k e r i n g 和h e c k e r m a n 等人通过实验并且比较了蒙特卡烙方法说明 了拉普拉斯近似类似方法和b i c 近似类似方法的有效性和准确性【2 3 】。总结他们的 实验可以得出如下几点结论。 当用于模型平均时拉普拉斯近似类似方法和b i c 近似类似方法没有一种近似 算法是准确的； 除了b i c 和m d l ，其余所有近似算法用于模型选择都是准确的； 除了b i c 和m d l ，其余所有近似算法很依赖于模型参数的先验概率； 计算m l 的否值时，b i c 和m d l 更准确。 c h i c k e r i n g 和h e c k e r m a n 等人指出上述等结论只对于用于聚类的根结点时隐藏 变量的朴素贝叶斯网络结构有效。 1 9 9 7 年f i r e d m a n 和s i n g h 几乎同时提出了著名的s e m 算法f 5 ，1 0 】。该算法借鉴 参数学习的e m 算法【1 4 】，粗略地说，是将不完备数据下学习贝叶斯网络问题转化为 较容易解决的完备数据集下的学习贝叶斯网络问题，在e m 补全数据集中内部搜索 最佳的贝叶斯网络结构。算法执行过程中始终有一个候选的网络结构，在每次循环 中，通过计算评价网络结构的期望统计因子，以试图发现某种评分标准下更好的网络 结构。s e m 算法对于解决不完备数据集下学习贝叶斯网问题具有里程碑的意义。 1 9 9 8 年，f i r e d m a n 提出了使用精确贝叶斯打分的b a y e s i a n - s e m 算法f 2 4 】。它也 是把不完备数据集转化为完备数据集，在参照当前最佳网络和不完备数据集下得到 统计因子基础上寻找贝叶斯打分最高的网络结构。但与s e m 算法不同的是，该算法 的搜索空间是网络结构，不再是网络结构和参数空间的乘积。 s e m 算法，虽然在一定程度上解决了问题，但该算法效率低，而且易于陷入局部 最优结构。2 0 0 4 年王双成等人提出了一种新的解决数据缺失时学习贝叶斯网络方案_ b n g s 算法 1 3 】。该方法反复使用g s 数据补全策略，参照当前网络，修复缺失数据， 用基于依赖分析方法进行学习和调整贝叶斯网，反复迭代之后使学习到的贝叶斯网最 终趋于稳定。b n g s 算法成功之处除了算法效率有很大改进之外，还在于解决了标 准g s 指数复杂性问题 1 2 】。2 0 0 5 年r i g g e l s e n 和f e e l d e r s 提出- j e m c 4 算法2 5 ，2 6 1 。 它根据数据集d 和当前最归咎网络利用重要性抽样估计后验分布p ( b i d ) 。 此外，1 9 9 6 年的p e d r o 和b i n d e r 还分别用遗传算法2 7 】和神经网络f 2 8 1 对不完 数据集下学习贝叶斯网问题进行了研究【2 9 ，3 0 】o 他们为这个领域的研究拓宽了思路， 补充了新的解决方案。 8 数据缺失下学习贝叶斯网的研究 第二章 数据缺失下学习贝叶斯网概述 鉴于本文需要，下面我们详细介绍具有代表性的基于打分一搜索机制的s e m 算 法和基于依赖分析的b n g s 算法。 2 2 1s e m 算法 2 2 1 1s e m 算法基本思想 s e m 算法是参数e m 算法的一个自然推广【1 0 】，其基本思想是：从某初始贝叶 斯网b 1 = ( g 1 ，0 x ) 出发开始迭代，在进行了t 次迭代之后得到当前最佳网络= ( g 。，) 后，第t + 1 次迭代由以下两步骤组成： 1 基于当前最佳网络b 。= ( ，伊) 对数据集d 利用e m 算法进行补全，使之完整并 得到完整数据集d 。； 2 基于数据集d 。对模型及参数进一步优化，得到b 件1 = ( 伊+ 1 ，0 。+ 1 ) 这里有两点需引起注意： 在参数e m 中基于补全后完整数据集d 。对参数进行一步优化得到的是基于d 的 最优参数，即最大似然概率。但是，对于s e m 算法基于d t 进行一步优化未必得 到基于的最优网络结构，因为在完备数据集下网络结构优化不是一步就能完 成的。 固定网络结构进行一步参数优化比进行一步网络结构优化要容易得多。 在s e m 算法中不是每次迭代都同时优化网络结构和参数。 2 2 1 2s e m 算法描述 设b = ( g ，p ) 是一贝叶斯网。这基于m d l 打分函数为： ，m d l ( b i d ) = l o gp ( d l b ) 一p e n ( b ，d )( 2 1 4 ) 其中l o g p ( d i b ) 为给定贝叶斯网时数据集的似然估计，p e n ( b ，d ) 为罚项值，取 决于数据集中结点变量的属性取值。 假设数据集d 有数据缺失，我们所关心的问题是在数据缺失情况下如何寻找 m d l 打分最高的贝叶斯网络b 7 = ( g ，p ，) i m l ( b 7 i d ) m d t ( b i d ) ，v b ( 2 1 5 ) 设从某一初始网络出发，通过一系列优化步骤之后，s e m 算法得到了当前最佳 网络贝叶斯网b + = ( g 。，日木) 。设d + 是基于当前最佳网络b + = ( g + ，p + ) 对数据集d 进 9 第二章数据缺失下学习贝叶斯网概述数据缺失下学习贝叶斯网的研究 行补全而得到的完备数据。与参数e m 的情况一样，一个贝叶斯n b = ( g ，p ) 基于数 据集d + 的m d l 评分为： f m d l ( b i d ) = l o gp ( d + i b ) - - p e n ( b ，d + ) 知m ( b l d 。) 也称为基于d 的期望m d l 打分，可以记为q ( b i 矽) ，即： q ( b b + ) = e 1 0 9p ( d + i b ) 一p e n ( b ，d ) 】 ( 2 1 6 ) ( 2 1 7 ) s e m 算法详细伪代码可见算法1 。该算法时间复杂度主要体现在e m 数据补全 策略上。e m 数据补全策略最好情况下参与估计结点变量可为0 个，在最坏情况，尤 其是高缺失率时参与估计结点变量极有可能涉及到绝大部分结点变量。也就是说，该 补全策略下参与估计的结点变量数非常不均衡，大大地降低了s e m 算法本身的效 率。 算法1s e m 算法 1 ：i n p u t ：有个实例的数据集d 及相关参数 2 ：o u t p u t ：贝叶斯网b 件1 3 ：c h o o s eb 1 = g 1 ，8 1 , 1 r a n d o m l y 4 ：f o rt = 1t ot m d o 5 ：f o r2 = 1t of 撇d o 6 ：8 t j + 1 = a r g m a x aq ( g 。， l a 。，) 7 ：e n df o r 8 ：f i n dan e t w o r ks t r u c t u r eg t + 1t h a tm a x m i z eq ( | g t ，8 t j + 1 ) 9 ：0 t + l a = a r gm a x 8q ( g 件1 ，日i g t ，o t j + 1 ) 1 0 ：e n df o r s e m 算法进行每一步优化时都选择当前最高期望打分的贝叶斯网，直至目标函 数f m d l ( b 。+ 1 ) = i m d l ( b 。) 无法改进为止。 定理1 i fq ( n s + ) q ( b + l b ) ，t h e n 知d 工( b ) f m d l ( b + ) 因此，若每一次优化都能找到比当前网络期望打分值高的网络b t + 1 ，目标函数就 向前推进。该定理的证明可见文献f 3 1 1 。 总之，s e m 算法参照当前最佳网络，利用e m 算法补全策略补全数据集，得到 统计所需要的期望统计因子，在一些假设下，可使打分函数具有可分解的的形式，把 1 0 数据缺失下学习贝叶斯网的研究 第二章数据缺失下学习贝叶斯网概述 数据缺失的学习问题转化为完备数据集学习贝叶斯网的问题。该算法力求在网络结 构和参数上经逐次迭代后趋于收敛，一定程度上提出了解决问题思路，但是却高概率 得收敛到局部最优。 ，2 2 2b n g s 算法 鉴于s e m 算法大多数情景下收敛于不可预知的局部最优的情况，王双成等人提 出了b n g s 算法【1 3 】。该算法的基本思想仍然是把数据缺失下学习贝叶斯网问题转 化成完备数据下的学习问题。首先随机初始化缺失训练数据，得到完整的数据集，并 利用该完整数据集建立最大似然树作为初始贝叶斯网络，然后进行迭代学习。在每一 次迭代中，参照当前最优贝叶斯网，结合g s 策略修正缺失数据集，在新得到的完整 数据集的基础上基于变量之间的基本依赖关系和依赖分析思想调整贝叶斯网，直到 贝叶斯网最终趋于稳定。 2 2 2 1 数据集及其初始网络的初始化 b n g s 算法首先随机初始化缺失的数据，把得到的数据集作为初始数据集d 1 ； 然后按某一顺序依次计算两个变量之间的互信息，并由大到小排序，依据不产生环路 的原则按顺序依次添加边，直到添加礼一1 条边为止。选择一个结点作为根结点，由根 结点向外的方向为边定向，并计算最大似然树参数，把最大似然树作为初始贝叶斯 网b 1 = ( g 1 ，p 1 ) 。作者认为该最大似然树和贝叶斯网拟合得很好，而且结构简单且稳 定，能够促使整体算法稳步收敛。 2 2 2 2 数据集修正与网络调整 第t 次迭代包括两步，算法直至网络趋于稳定或迭代时间片到。 1 利用当前贝叶斯网络进行抽样，修正待修正的数据与参数 按照b 所决定的联合分布公式2 1 、g t 所决定的变量顺序以及训练数据集d 。中 记录的顺序依次对具有缺失数据的结点变量进行抽样，并用抽样值修改该记录 中待估结点的具体属性值。文中指出每一次迭代修正数据集的次数不宜过多， 过多的修正次数会使数据集和贝叶斯网过度拟合，导致收敛到局部最优结构。 合理迭代次数后的数据集记为d 蚪1 ，并同时修改臼2 ，得到日件1 。 2 使用修正后的数据集调整贝叶斯网络，并相应修改参数 该算法利用贝叶斯网络的信息管道模型 3 2 1 描述结点变量之间存在的3 种 基本依赖关系( 边) 3 3 】： 第二章数据缺失下学习贝叶斯网概述数据缺失下学习贝叶斯网的研究 及物依赖( t r a n s i t i v ed e p e n d e n c i e s ) 表示变量的结点变量之间存在直接的 信息流动，而且信息流不能被其它结点所阻塞，即结点所表示的变量之间 条件不独立。这种边依赖关系也有效地得到保留。 非及物依赖( n o n t r a n s i t i v ed e p e n d e n c i e s ) 表示结点之间不存在直接的信 息流动，而是由连接两结点之间的开路产生的信息流，能被切割集中的结点 所阻塞，即以切割集中结点表示的变量为条件时，两个结点所表示的变量 之间条件独立。这种边应该去除。 诱发依赖( i n d u c e dd e p e n d e n c i e s ) ，这种依赖是由v 结构 3 4 】所导致的，结 点之间不存在直接的信息流动，是v 结构中的碰撞结点诱发的信息流，结 点所表示的变量之间无条件独立，以切割集( 不包括诱发结点) 中结点表示 的变量为条件时，两个结点所表示的变量之间也条件独立。这种边应该去 除。 用修正后的数据集重新计算父亲结点变量集合发生变化的参数即可。 2 3现有算法总结及存在问题 从上节不难看出，不管基于打分一搜索的s e m 算法，还是基于依赖分析的 b n g s 算法，以及其它类似算法都