（计算机应用技术专业论文）极大或极小数据集下贝叶斯网学习的研究.pdf

极大或极小数据集下贝叶斯网学习的研究 摘要 摘要 极大数据集是指数据量巨大，以致于计算机内存不能全部容纳的数据集；极小数 据集是指由于实验条件和实验代价等限制，导致获得的珍贵数据资源比较少的数据 集。本文对极大或极小数据集下的贝叶斯网络学习进行了研究，并提出了相关的解决 方案。 首先，提出了一种在数据缺失训练集下增量学习贝叶斯网络的有效的算法 i b n m ，该算法用结构化的e m 算法来补全数据集中缺失的数据，并且能在并行和启 发式搜索策略提供的较大的搜索空间里搜索，有效地避免了采用结构化e m 算法而 导致的局部极值，同时采用了对数据分批次学习的增量学习方法，解决了大规模数据 学习存在的内存空间不足的问题，并将i b n m 应用到网络流量预测中去。实验结果 表明i b n m 算法在数据缺失下贝叶斯网络的增量学习中确实能够学出相对精确的网 络模型，该算法也是对贝叶斯网络增量学习方面的一个必要的补充。 其次，建立了一种小规模数据集下学习贝叶斯网络的有效算法f c l b n 。f c l b n 利用b o o t s t r a p 方法在给定的小样本数据集上进行重抽样，然后用在抽样后数据集上 学到的贝叶斯网络来估计原数据集上的贝叶斯网络的高置信度的特征，并用这些特 征来指导在原数据集上的贝叶斯网络搜索。用标准的数据集验证了f c l b n 的有效 性，并将f c l b n 应用到了酵母菌细胞蛋白质分子定位预测问题中去。 最后，从极小数据集下的贝叶斯网络学习中受到启发，对大规模数据集下贝叶斯 网络的学习过程进行改进，提出了m m i b n 算法。相对于大规模数据集而言，每一批 次数据的学习实际上就是一个小规模数据集学习的问题，m m i b n 算法就是将特征 置信指导的方法融入到增量学习过程中去。实验验证了这一改进确实使得大规模数 据集下贝叶斯网络的学习结果更加精确。 关键词：贝叶斯网络；极大或极小数据集；增量学习；特征置信 作 者：李亚飞 指导教师：吕强 极大或极小数据集下贝叶斯网学习的研究 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 tt h es t u d yo nl e a r n i n gb a y e s i a nn e t w o r kf r o me x t r e m e l yl a r g eo r s m a l ld a t a s e t sa n di t sa p p l i c a t i o n e x t r e m e l yl a r g ed a t a s e t sr e f e rt ot h ed a t a s e t sw h i c hc a n t b el o a d e di n t om e m o r yi nw h o l e e x t r e m e l ys m a l ld a t a s e t sr e f e rt ot h o s ee x p e n s i v ee x p e r i - m e n t a ld a t a s e t sb e c a u s eo fv a r i o u sl i m i t a t i o n s f i r s t l y , a ne f f i c i e n ta p p r o a c hf o ri n c r e m e n t a ll 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 si b n - ma l g o r i t h mi sp r e s e n t e d t h ea l g o r i t h mu s e ss t r u c t u r a le ma l g o r i t h mt o c o m p l e m e n tt h em i s s i n gv a l u e si nt h ed a t a s e t s ，a n ds e a r c h e si nt h el a r g e rs p a c ep r o v i d e db y p a r a l l e lh e u r i s t i cs t r a t e g i e st oe s c a p et h el o c a lm i n i m ac a u s e db ye m i n c r e m e n t a ll e a r n i n g m e t h o di sa l s oa d o p t e di ni b n mt or e s o l v et h em e m o r ys p a c el i m i tc a u s e db yt h ee x t r e m e l y l a r g ed a t a s e t t h ee x p e r i m e n t ss h o wt h a ti b n ma l g o r i t h mc a nl e a r nc o m p a r a t i v e l ya c c u r a t en e t w o r kf r o mt h ee x t r e m e l yl a r g ed a t a s e t i b n - mi sa ni n t e r e s t i n gi m p r o v e m e n tf o r i n c r e m e n t a ll e a r n i n gb a y e s i a nn e t w o r k s e c o n d l y , a n e f f i c i e n ta l g o r i t h mf c l b nf o rl e a r n i n gb a y e s i a nn e t w o r kf r o me x t r e m e l y s m a l ld a t a s e t si sp r o p o s e d f c l b nu s e st h em e t h o do fb o o t s t r a pt or e s a m p l ef r o mt h e s m a l ld a t a s e l s ，a n de s t i m a t e st h eh i g hc o n f i d e n c ef e a t u r e so ft h es o u r c es m a l ld a t a s e t sf r o m t h eb a y e s i a nn e t w o r k sl e a r n e df r o mt h er e s a m p l i n gs m a l ld a m s e l s t h eh i g hc o n f i d e n c e f e a t u r e sa r et a k e nt og u i d et h es e a r c ho ft h eb e s tb a y e s i a nn e t w o r ko nt h es o u r c ed a t a s e t s a f t e rb e i n ge v a l u a t e do nt h es t a n d a r db e n c h m a r kd a t a s e t s ，f c l b ni sa p p l i e dt op r e d i c ty e a s t p r o t e i nl o c a l i z a t i o n t h er e s u l to ft h ee x p e r i m e n t si n d i c a t e st h a tt h ef c l b na l g o r i t h mc a n l e a r nr e l a t i v e l ya c c u r a t en e t w o r kf r o ms m a l ld a t a s e t s l a s t l y , i n s p i r e df r o mt h el e a r n i n gb a y e s i a nn e t w o r kf r o mt h es m a l ld a t a s e t s ，t h ea l g o - r i t h mm m l b ni sp r o p o s e dt oi m p r o v et h el e a r n i n gm e t h o do fl e a r n i n gb a y e s i a nn e t w o r k f r o me x t r e m e l yl a r g ed a t a s e t s i nf a c t ，e a c hb a t c hd a t al e a r n i n gp r o b l e mi sc o n v e r t e dt oa l e a r n i n gp r o b l e m f r o me x t r e m e l ys m a l ld a t a s e t s t h eg u a r d i n go ff e a t u r ec o n f i d e n c ei si n t r o d u c et ot h ei b n m t h er e s u l to ft h ee x p e r i m e n t si n d i c a t e st h a tt h ec o m b i n a t i o no fi b n m a n df c l b nc a nl e a r nb e t t e ra c c u r a t en e t w o r kf r o me x t r e m e l yl a r g ed a t a s e t s k e y w o r d s ：b a y e s i a nn e t w o r k ，e x t r e m e l yl a r g eo rs m a l ld a t a s e t s ，i n c r e m e n t a ll e a r n i n g ， f e a t u r ec o n f i d e n c e i i i w r i t t e nb y ：l iy a f e i a b s t r a c t极大或极小数据集下贝叶斯网学习的研究 s u p e r v i s e db y ：l i iq i a n g 极大或极小数据集下贝叶斯网学习的研究插图 插图 1 1 全文工作框架图 4 2 1n a i v eb a y e s 网络结构 8 2 2t a nb a y e s 网络结构9 3 1支持数据缺失的贝叶斯网络增量学习方法框架图1 9 3 2 i b n m 算法流程图 2 2 3 3 缺失数据1 0 和2 0 情况下两种方法的内存消耗 2 3 3 4 缺失数据1 0 和2 0 情况下两种方法与标准图l o g l o s s 的差 2 4 3 5 第一天日志学到的网络结构 2 8 3 6 第二天日志学到的网络结构2 8 3 7 第三天日志学到的网络结构 2 8 4 1 基于特征置信的贝叶斯网络学习方法框架图 2 9 4 2 ( a ) d a g 图( b ) d a g 图( c ) p d a g 图 3 0 4 3 f c l b n 算法流程图 3 2 5 1 增量学习内嵌置信指导的贝叶斯网络学习框架图 3 9 5 2m m i b n 算法流程图 4 0 5 3 m m i b n 和i b n m 算法的空间消耗比较 4 2 极大或极小数据集下贝叶斯网学习的研究表格 表格 2 1 b a y e s i a n 网络学习分类 7 3 1 i b n m 与i l p 算法网络流量预测正确率 2 7 4 1 不同置信度下边的估计情况 4 2 不同置信度下网络结构的估计情况 4 3 不同置信度下学出的网络的l o g l o s s 值 4 4 对f c l b n 、n a i v e 、t a n 、s v m 进行交叉验证的结果 4 5 对f c l b n 、n a i v e 、t a n 、s v m 进行分类预测的结果 5 1 m m i b n 与i b n m 算法学出的网络结构的比较 5 2 m m i b n 与i b n m 算法数据拟合程度比较 5 3 m m i b n 和i b n m 算法网络流量预测正确率比较 3 4 3 4 3 5 3 7 3 8 4 2 4 3 4 4 极大或极小数据集下贝叶斯网学习的研究 算法 1 2 3 4 5 6 算法 b o o t s t r a p 抽样扩展数据集算法 1 2 s e m 算法 1 5 p a c o b 算法 1 7 i b n m 算法 2 l f c l b n 算法 3 2 m m i b n 算法 4 1 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名日期： 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 x 研究生签名：么幺竺兰日期：型2 二生二丝 导师签名：勉日期：4 型 极大或极小数据集下贝叶斯网学习的研究 第一章引言 第一章引言 1 1 课题背景 由于贝叶斯网络的完美优越性，仅靠专家知识通过非常繁杂的途径构造出不准 确的贝叶斯网络已经满足不了现实的需要。因此如何从现实世界大量的数据集中学 习贝叶斯网络显得至关重要。现实世界大量容易获的的数据集以及先进计算机超强 的计算能力都为学习贝叶斯网络提供了有力的条件。 在经典的贝叶斯网络研究中，从数据集这个角度来说，分为正常的数据集和异常 的数据集两种，正常的数据集是指那些数据精确完整以及数据规模适合计算平台的 数据集；异常的数据集是指包含具有隐藏变量或数据缺失以及数据规模不适合计算 平台的数据集，其中数据规模不合理又包括极大数据集和极小数据集两种情况。具有 隐藏变量和数据缺失方面的贝叶斯网络学习，已经进行了较多的研究，但对数据规模 不合理这一方面的研究并不太多，然而这个问题在现实生活中是确实存在的，也很普 遍。比如网络日志挖掘和蛋白质结构预测定位等。由于网络日志数据记录量极大，使 得数据不能被全部读入内存，导致现有的经典的算法不能很好地发挥作用；在生物信 息学方面，由于实验难度极大，致使获得的珍贵实验数据量较少，同样地经典算法也 不能很好的对之进行学习。这种数据集规模庞大或者严重不足的情形就迫切需要对 现有的算法进行改进，以适应于这些特殊应用场景的需要。本文所指的极大规模数据 集是指数据规模超过百万条记录以上的数据集，极小规模数据集是指数据规模仅有 几百条记录的数据集。 1 2 课题内容 本文的研究内容主要从以下几个方面着手。 对于极大数据集下贝叶斯网络的研究主要包括以下几个方面： 1 由于数据量极大，导致数据不能全部读入内存，在这种情况下如何合理的保存 学过的数据信息。 2 由于经典的贝叶斯网络学习算法中的打分函数都是对固定的数据集进行打分 的，而极大数据集下贝叶斯网络的学习则是通过数据分批来学习，这样数据集 就是动态变化的。那么我们就需要改进原来的打分方案，使其适应于统计起点 不同的数据。 】 第一章 引言 极大或极小数据集下贝叶斯网学习的研究 3 利用合理的搜索算法，找出最优的网络模型。 4 改进后的算法在网络流量预测方面的应用。 对于极小数据集下贝叶斯网络的研究主要包括以下几个方面： 1 在现有的数据集数量一定情况下，采用合理的统计方法来处理数据集，弥补数 据量少导致的学出网络质量不精确的问题。 2 对用高置信特征直接估计原数据集上所蕴含的网络结构的学习流程进行了改 进，用高置信的特征来指导在原数据集上的贝叶斯网络搜索，使得能有更好的 学习结果。 3 利用合理的搜索算法，找出最优的网络模型。 4 改进后的算法在酵母菌细胞蛋白质分子预测定位方面的应用。 极大极小数据集下贝叶斯网络的学习，并不是相互独立的，那么如何很好的集合 这两种学习算法的优点，相互取长补短，这也是本课题研究的一个重要内容。 1 3 课题意义 贝叶斯网络的图论语言简单易懂，能够帮助人们理清问题的结构，同时又是严格 的数学语言，可以直接用计算机来处理，因此贝叶斯网络成为许多研究领域的常用工 具。例如在医疗诊断、工业应用、金融分析、计算机系统等方面都有成功的应用川。而 所有的这一切应用都必须建立在这样一个前提下：贝叶斯网络的结构和参数已经被 学习到和训练好。本文所要解决的就是在这些应用中经常遇到的极大极小数据集下 的贝叶斯网络学习问题。 对于极大规模数据集下的贝叶斯网络学习来说，由于数据数量比较多，一次不能 全部装入内存，致使经典算法不能很好来处理这些数据，因此我们只有对数据进行分 批次学习。但在数据分批次学习时，如何合理地保存学过的数据信息，是在大规模数 据集下贝叶斯网络所必须解决的问题。如在网络日志挖掘方面，据统计苏州大学网关 处一个小时的日志记录大概有7 0 多万条，一天的记录大概有1 0 0 0 多万条。在这种情况 下，相对于有限的内存存储空间来说，数据量是巨大的，计算机不能一次性处理这么 多数据，此时就有必要对极大数据集情况下的贝叶斯网络学习进行研究了。 对于极小规模数据集下贝叶斯网络的学习来说，由于获取数据样本的实验困难 比较大或者代价十分高，致使获得的珍贵数据资源比较少，那么数据量严重不足是我 们要面临的问题。比如在基因工程中，测一条基因链就要耗费几千万美元伫，但是我 2 极大或极小数据集下贝叶斯网学习的研究第一章引言 们得到的实验的数据依然很少，基因链中属性的个数有上千个，得到的数据记录条 数却只有几千条，很难覆盖所有属性取值的组合；k d dc u p 2 0 0 1 中凝血酶药物设计问 题p 1 ，所用到的化合物包含多达1 3 5 9 3 1 个二值属性，但实验要用到的描述属性之间关 系的记录却只有1 9 8 3 条。这种情况下，由于实验数据的严重不足，导致经典的贝叶斯 网络学习方法没有办法进行，所以也迫切需要对极小数据集下的贝叶斯网络学习进 行必要的研究。 1 4 本文的组织结构 本文的主要章节安排如下： 第一章主要介绍本文的研究背景、研究内容和研究意义。 第二章主要概述贝叶斯网络的一些基本概念，并对本文所使用的一些基本算法 进行了阐述，论述了国内外关于异常数据集下贝叶斯网络学习研究状况。 第三章主要描述了极大数据集下贝叶斯网络的相关研究，并通过对网络日志的 贝叶斯网络建模来预测网络流量。 第四章主要描述了极小数据集下贝叶斯网络的相关研究，同时选取了一个生物 信息学中的案例来对极小数据集下的贝叶斯网络的应用情况进行了实验。 第五章结合极大或极小数据集下贝叶斯网络学习的优缺点，将两种方法综合起 来，将极小数据集下的学习方法应用到极大规模数据集贝叶斯网络的学习过程中去， 改进了极大数据集下贝叶斯网络的学习流程，进一步提高了极大数据集下贝叶斯网 络学习的精度。 第六章主要是对本文工作的总结及其展望。 为了能够更好地对本文的结构有一个清晰认识，我们给出本文研究内容的框架 图，如图1 1 所示。图1 1 中，最上面的一部分是数据缺失下贝叶斯网络的相关工作， 中间的那一部分是极大数据集下贝叶斯网络学习的研究内容，最下面一部分是极小 数据集下贝叶斯网络学习的研究内容。 针对缺失数据下贝叶斯网络学习的研究。主要是采用e m 算法对缺失数据进行 补全，然后再调用完整数据集下学习贝叶斯网络较好的算法p a c o b 来进行网 络的学习。 针对极大数据集下的贝叶斯网络学习的研究。提出了一种i b n m 算法，用结构 化的e m 算法来补全数据集中缺失的数据，并且能在并行和启发式搜索策略提 供的较大的搜索空间里搜索，有效地避免了采用结构化e m 算法而导致的局部 3 第一章引言极大或极小数据集下贝叶斯网学习的研究 援 士 散 据 羹 图1 1 ：全文工作框架图 极值，同时采用了对数据分批次学习的增量学习方法，解决了大规模数据学习 存在的内存空间不足的问题，并将i b n m 应用于网络流量预测中。 针对极小数据集下贝叶斯网络学习的研究。提出了种小规模数据集下学习贝 叶斯网络的有效算法f c l b n 。f c l b n 利用b o o t s t r a p 方法在给定的小样本数据 集上进行重抽样，然后用在抽样后数据集上学到的贝叶斯网络来估计原数据集 上的贝叶斯网络的高置信度的特征，并用这些特征来指导在原数据集上的贝叶 斯网络搜索，本部分我们将f c l b n 应用到酵母菌细胞蛋白质分子定位应用中 去。 在极大数据集下贝叶斯网络的增量学习中，每一批次数据相对于整个数据集来 说也是一个极小数据集，鉴于f c l b n 在极小规模数据集上贝叶斯网络学习的 优势，将f c l b n 算法内嵌到i b n m 算法中去，提出了m m i b n 算法。m m i b n 算法通过提高每一批次数据学习的精度，来提高最终得到的网络模型的质量。 4 极大或极小数据集下贝叶斯网学习的研究 第二章 相关技术概述 第二章相关技术概述 不确定知识的推理是人工智能领域一个重要的研究课题，贝叶斯网络将先验知 识与样本信息相结合、依赖关系与概率表示相结合，是目前不确定知识和推理领域最 有效的理论模型之一。贝叶斯网络又称为信念网络，是一种对概率关系的有向图解描 述，适用于不确定性和概率性事物川。 贝叶斯统计和图论的发展为贝叶斯网络理论的引入提供了坚实的理论基础，而 人工智能、专家系统和机器学习在实践中的广泛应用，成为贝叶斯网络产生和发展的 催化剂。 贝叶斯网络建模主要是网络参数学习和网络结构学习。而贝叶斯网络推理实质 上是回答任何给定证据下的查询问题，包括因果推理、诊断推理以及支持推理等方 面。 2 1 贝叶斯网络模型的描述 贝叶斯网络( b n ) ，又称为信度网，由一个有向无环图( d i r e c t e d a c y l i c g r a p h ，d a g ) 和条件概率表( c o n d i t i o n a lp r o b a b i l i t yt a b l e ，c p t ) 组成州。 n 元随机变量x = x 1 ，x 2 ，l 的贝叶斯网络模型是一个二元组b = ( b s ，b p ) 。b s = ( x ，e ) 是一个有向无环图( d i r e c t e da c r y l i cg r a p h ，d a g ) ，其中x = x 。，恐，墨 为结点集，每个结点可以看成取离散或者连续值的变量( 本文只限定 其取离散值) ；e 是有向边的集合，每条边表示两结点间依赖关系，依赖程度有条件 概率参数决定。称b s 为b n 的网络结构。b p = 尸( x l 砜) ，x f x ) 贝叶斯网络模型的 一组条件概率分布的集合。在各结点取离散值的情况下，b p 为一组条件概率表的集 合。x f 是在b s 中x f 所有父结点的集合，表示结点蕾在其父结点某一取值组合状态 下的条件概率分布。这说明，在贝叶斯网络模型中，结点的取值依赖于其父结点的取 值状态。 这里，学习贝叶斯网络的问题描述为：给定一组实例构成的训练集合d - d l ，d 2 ，磊 ，找到一个与d 匹配最好的网络b 。这样，学习贝叶斯网络问题 转化为优化问题。这时类变量和属性变量不加区分。 实际处理这个问题的方法是在可能的网络构成的空间中进行启发式搜索。搜索 成功的关键是基于一个合理的评分函数，指导搜索各种网络结构，找到与训练数据匹 配程度最高的一个最优网络。 5 第二章 相关技术概述 极大或极小数据集下贝叶斯网学习的研究 常用的评分函数主要有两种：贝叶斯评分函数瞪1 和最小描述长度原理( m d l ：m i n i m a l d e s c r i p i t o nl e n g t h ) 评分函数1 6 1 。它们是渐进正确的，即随着样本数目的增加，得分最 高的网络将任意逼近样本的概率分布。 2 2 贝叶斯网络的构造方式 一般情况下贝叶斯网络有三种构造方式： 1 由领域专家确定贝叶斯网的变量( 有时也称为影响因子) 节点，然后通过专家的 知识来确定贝叶斯网络的结构，并指定它的分布参数。这种方式构造的贝叶斯 网完全在专家的指导下进行，由于人类获得知识的有限性，导致构建的网络与 实践中积累下的数据具有很大的偏差。 2 由领域专家确定贝叶斯网络的节点，通过大量的训练数据，来学习贝叶斯网的 结构和参数。这种方式完全是一种数据驱动的方法，具有很强的适应性，而且 随着人工智能、数据挖掘和机器学习的不断发展，使得这种方法成为可能。如 何从数据中学习贝叶斯网的结构和参数，已经成为贝叶斯网络研究的热点。 3 由领域专家确定贝叶斯网络的节点，通过专家的知识来指定网络的结构，而通 过机器学习的方法从数据中学习网络的参数。这种方式实际上是前两种方式的 折衷，当领域中变量之间的关系较明显的情况下，这种方法能大大提高学习的 效率。 可以看出，在由领域专家确定贝叶斯网络的节点后，构造贝叶斯网的主要任务就 是学习它的结构和参数。很显然，学习结构和参数不是完全独立的。一方面节点的条 件概率很大程度上依赖于网络的拓朴结构；另一方面，网络的拓朴结构直接由联合概 率分布的函数来决定。 根据构成贝叶斯网络的结点变量是离散的变量且取有限个值或是连续的变量或 是既有连续变量又有离散变量三种不同情况，贝叶斯网络的类型可以分为离散型、连 续型、混合型三种。近年来，关于贝叶斯网络的理论研究重点集中于贝叶斯网络的结 构学习和参数学习方面。结构学习是指对于每一特征节点找到除根节点之外的所有 父节点，参数学习是指在己知结构的基础上获得上述参数的估计。 2 3 贝叶斯网络的学习 学习贝叶斯网就是要找到按照某种测度最好地与给定实例数据集拟合网络结构。 一般而言，寻找一种网络包括寻找一种有向无环图结构b s 和获得与曰s 中每个结点 相关的条件概率表。因此学习贝叶斯网络问题可以分为以下两方面1 7 1 ： 6 极大或极小数据集下贝叶斯网学习的研究第二章相关技术概述 1 结构学习，主要是有向无环图拓扑结构的学习 2 参数学习，主要是网络中每个变量的局部条件概率分布的学习 贝叶斯网络的结构学习和参数学习显然不是完全独立的：一方面结点的条件概率很 大程度上依赖于网络的拓扑结构；另一方面，网络的拓扑结构直接由联合概率分布的 函数来决定。但一般情况下，我们还是把这两个方面分开来进行，因为带有太多连接 的复杂的网络结构所需观测的参数比较多，而为使获得这些参数达到某种信任程度 所需的数据量随着参数数量的增加而迅速增长，并且复杂的结构需要太大的存储空 间以及冗长繁琐的计算过程才能产生预测和解释。 因此，为使贝叶斯网络作为知识模型是可用的，在学习过程中致力于寻找一种最 简单的网络结构是非常必要的，这种简单的结构模型称之为稀疏网络，它含有最少可 能的参数及最少可能的依赖关系。 根据网络结构是否已知、数据集是否完整，可以把学习贝叶斯网络的方法分为四 类懈1 ，各种情形学习重点及方法如表2 1 所示。 表2 1 ：b a y e s i a n 网络学习分类 网络结构已知网络结构未知 数据完备概率参数学习，简单统计估计，m l e找最优网络结构：m d l ，b d e 等评价标 方法，b a y e s i a n 方法 准，启发式搜索，模拟退火搜索等算法 数据不完备找最优概率参数，e m 算法，基于梯度既要找最佳结构，又要找最优参数，有 方法，蒙特卡洛法，高斯算法等结构e m 算法，混合模型 本文研究的是在数据不完备、网络结构未知条件下的贝叶斯网络的学习方法，我 们也称这种学习为异常数据集下的贝叶斯网络学习。 2 4 贝叶斯网络分类器和s v m 分类器 贝叶斯网络的一个重要的用途是用于分类，本文将学习到的贝叶斯网络用于分 类应用，并与常见的s v m 分类器分类结果进行了比较，所以本小节我们对一些贝叶 斯网络分类器和s v m 分类器进行简单的介绍。 2 。4 1 朴素贝叶斯分类器 朴素贝叶斯模型( n a i v eb a y e sm o d e l ) ，又称朴素贝叶斯分类器( n a i v eb a y e s c l a s s i f i e r ) ，是一个包含一个根节点、多个叶节点的树状贝叶斯网，如图2 1 所示。其中 叶节点a 1 4 。是属性变量，描述待分类对象的属性，根节点c 是类别变量，描述对 7 第二章相关技术概述极大或极小数据集下贝叶斯网学习的研究 象的类别。用朴素贝叶斯模型进行分类就是给定一个数据点，即各属性变量的取值 a l = 口1 ，a 。- - a 。，计算后验分布p ( cj a l = a l ，a 。= a n ) ，然后选择概率最大的那个 c 值作为这个数据点所属的类别。在医疗诊断中，c 代表一系列疾病，a l - 4 。代表 这些疾病可能导致的症状，诊断就是根据症状来确定疾病。朴素贝叶斯模型包含了 c 图2 1 ：n a i v eb a y e s 网络结构 一个所谓的局部独立( 1 0 c a li n d e p e n d e n c e ) 假设，即给定类别变量c ，各属性变量a f 相互条件独立。这意味着，联合概率分布满足公式2 i 。 朴素贝叶斯模型最早由w a r n e r 等提出，用于先天性心脏病的诊断，其主要优点 是结构简单，计算复杂度低。尽管它采用的局部独立假设显然过于理想化，但实验数 据显示，其性能和其它常见的分类器不相上下。 n p ( c , a 1 ，a 2 ) = p ( c ) 几p ( a f i c ) ( 2 1 ) j = f 2 4 2t a n 分类器 朴素贝叶斯模型中的局部独立假设在实际中往往不成立。为使模型更加符合实 际，可以在其中的各叶子节点之间增加一些必要的边，以显示各变量属性之间的依赖 关系，如果规定属性变量之间成树状结构，那么模型就称为加树朴素贝叶斯模型，简 称t a n 模型。图2 2 给出了这样的一个例子，在t a n 模型中，联合概率分布为 占 p ( c ，a l a 2 ) = p ( c ) ilp ( a i i i a 。) ( 2 2 ) 注意这里的属性变量a ，的父节点巩i 不仅包括类别变量c ，也可能包括其它的属 性变量。相比之下，在朴素贝叶斯模型中a i 只包括c 。这说明，t a n 模型不再要求 局部独立假设成立。有研究表明，t a n 模型的分类效果往往比朴素贝叶斯要好。 8 极大或极小数据集下贝叶斯网学习的研究第二章相关技术概述 c a i 舢a z i 图2 2 ：t a nb a y e s 网络结构 t a n 的根结点与所有的子结点都有一张表，所以各个子结点不但存储与之关联 的另一个子结点的概率分布，还要存储针对于根结点的概率分布。因为t a n 的结构 要优于n a i v eb a y e s ，所以可以简单推断出t a n 能够拥有比n a i v eb a y e s 更好的效果， 而且在加入平滑处理后，t a n 在大多数实例中确实比n a i v eb a y e s 表现更好。 2 4 3s v m 分类器 s v m 的主要思想可以概括为两点： 1 它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映 射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分， 从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可 能； 2 它基于结构风险最小化理论之上在特征空间中建构最优分割超平面，使得学习 器得到全局最优化，并且在整个样本空间的期望风险以某个概率满足一定上晃。 支持向量机方法是建立在统计学习理论的v c 维理论和结构风险最小原理 基础上的，根据有限的样本信息在模型的复杂性( 即对特定训练样本的学习精 度，a c c u r a c y ) 和学习能力( 即无错误地识别任意样本的能力) 之间寻求最佳折衷，以 期获得最好的泛化能力( g e n e r a l i z a t i o na b i l i t y ) 1 9 1 1 1 0 1 。 s v m 方法有很坚实的理论基础，s v m 训练的本质是解决一个二次规划( q r , ) 问 题，得到的是全局最优解，这使它有着其他统计学习技术难以比拟的优越性。 s v m 分类器的文本分类效果很好，是最好的分类器之一。其缺点是核函数的选 择缺乏指导，难以针对具体问题选择最佳的核函数；另外s v m 训练速度极大地受到 9 第二章相关技术概述极大或极小数据集下贝叶斯网学习的研究 训练集规模的影响，计算开销比较大，针对s v m 的训练速度问题，研究者提出了很 多改进方法，包括c h u n k i n g 方法、o s u n a 算法、s m o 算法和交互s v m 等等嘲讲。 2 4 4 基于贝叶斯分类器的比较 文献【l1 1 9 通过实验对几种分类器精确度进行比较，由实验结果可以看出t a n 和c lm u l t i n e t s 都能达到较高的精确度，特别是当有足够多的实例能得到精确的条件 概率时，这两种模型的效果更好。所以从实验的结果来看这两种贝叶斯分类器可以与 机器学习中目前最好的分类器相媲美，是机器学习领域最有效的分类器之一。 2 5 异常数据集下的贝叶斯网络学习概述 极大数据集和极小数据集是异常数据集下贝叶斯网络学习的两种典型的情况， 而且极大数据集通常伴随有数据缺失的情况。本小节我们对极大极小数据集下贝叶 斯网络的研究现状进行相关的阐述。 2 5 1 极大数据集下贝叶斯网络的学习 对于极大数据集下的贝叶斯网络学习来说，一般的解决方案都是将极大规模的 数据集进行分批学习，常用的解决方案有两种：简单增量学习和最大后验概率增量学 习。 最早提出极大数据集下贝叶斯网络学习研究的是f r i e d m a n ，这一问题的提出为 贝叶斯网络的学习增添了新研究的内容。 f r i e d m a n 于1 9 9 7 年在文献【1 2 中提出了用增量学习来解决极大数据集下贝叶斯 网络学习问题。由于数据量过大，一次并不能全部读入内存，只有分批次来对之进行 增量学习，但是如果简单的将数据分割为几块，不对学过的信息进行较好的保存，结 果往往很难令人满意。文献【1 2 用记录数据频数的方式来代替保存数据集的方式，很 好的解决了对历史信息保存的问题。同时，经典的贝叶斯网络学习过程中都是针对固 定的数据集对不同的网络结构进行打分，然而在增量的学习的过程中，由于数据是分 批到来的，所以不能直接套用经典的网络结构打分方法。文献【1 2 中引入平均打分函 数来处理数据集动态变化的问题，取得了较好的结果。文献【1 2 的最主要贡献是为解 决大规模数据集下贝叶斯网络的学习提供了初步的解决方案。但其利用了搜索网络 结构策略比较简单的h c 算法，所以实验的效果并不好。同时对于大规模数据集下的 数据缺失问题也没有得到很好的解决。 文献【1 3 】于1 9 9 8 年提出了用s e m 策略来解决常规数据集中的数据缺失下的贝叶 斯网络学习问题，该算法实际上参数学习的e m 算法h 4 1 的一个变种，简单地说，是将 1 0 极大或极小数据集下贝叶斯网学习的研究 第二章相关技术概述 不完备数据下学习贝叶斯网络问题转化为较容易解决的完备数据集下的学习贝叶斯 网络问题，在e m 补全数据集中内部搜索最佳的贝叶斯网络结构。算法执行过程中始 终有一个候选的网络结构，在每次循环中，通过计算评价网络结构的期望统计因子， 以试图发现某种评分标准下更好的网络结构。s e m 算法对于解决不完备数据集下学 习贝叶斯网问题具有里程碑的意义。但它并没有把它应用到大规模数据的贝叶斯网 络学习过程中去。 文献【1 5 于2 0 0 5 年提出了一种包含隐藏变量的贝叶斯网络增量学习方法i l b n 。 该方法将遗传算法引入到了贝叶斯网络的增量学习过程中，用遗传算法进化贝叶斯 网络的结构，在一定程度上缓解了确定性搜索算法的局部极值问题。通过定义新变异 算子和扩展传统的交叉算子，i l b n 能够增量学习包含隐变量的贝叶斯网络结构。文 献【1 5 扩充了极大数据集下贝叶斯网络的学习，但是，同样也没有对于大规模数据集 下的数据缺失问题进行相关的研究。 文献【1 6 在2 0 0 6 年提出了将e m 算法引入面向大规模数据集的贝叶斯网络参数 学习中去，采用划分数据块的方法将大规模数据集划分为小的样本集来处理，虽然降 低了e m 算法的计算量，但是这种简单的分割数据集，破坏了数据的完整性，并没有 很好的积累学过数据的信息，以至于最后的学习结果并不理想。 2 5 2 极小数据集下贝叶斯网络的学习 e f r o n 等人于1 9 9 3 年在b o o t s t r a p 引论一书中提出了b o o t s t r a p 这一经典的解决小 样本数据集的方法。b o o t s t r a p 的提出为以后统计学中处理小样本数据集问题做出 了重要的贡献。本文我们对极小数据集的处理利用的也是b o o t s t r a p 这一经典的统计 学方法。 文献f 1 8 在1 9 9 9 年提出了小规模数据集下贝叶斯网络学习的解决方案，将 b o o t s t r a p 方法应用n d , 规模数据集的贝叶斯网络学习过程中去。 其中的b o o t s t r a p 抽样可以分为两种，分别是：有参b o o t s t r a p 和无参b o o t s t r a p 。 其中无参b o o t s t r a p 由以下步骤构成： 1 f o ri = 1 ，2 ，m ( a ) 从d 中随机有放回地抽出条记录，并用d f 来标记抽样得到的数据集 ( b ) 在d ，上应用贝叶斯网络学习程序推出一个网络结构岛= e ( d f ) 2 对于每一个感兴趣的特征进行如下定义： 玮= 去x i m lf ( g i ) 11 第二章相关技术概述极大或极小数据集下贝叶斯网学习的研究 有参b o o t s t r a p 与无参b o o t s t r a p 是一个基本上相似的过程，只不过无参b o o t s t r a p 是在 训练数据集上进行重抽样，而有参b o o t s t r a p 的重抽样则是在由现有的数据集上学习 出的一个网络结构b 上进行，具体步骤如下所示： 1 从数据集d 学习出一个贝叶斯网络b 2 f o ri = 1 ，2 ，m ( a ) 根据网络结构b ，生成条数据记录，标记为d f ( b ) 应用现有的学习程序从d f 中学习出网络结构& = g ( d f ) 3 对于每一个感兴趣的特征进行如下定义： p = 击譬1f ( g i ) 其r 辛f ( d ，) 表示我们感兴趣的网络结构特征，比如拓扑排序、结点邻域、边等；戚表示 相关置信特征的置信度。文献 1 8 】验证了无参b o o t s t r a p 要比有参b o o t s t r a p 得到的实 验效果更好一些。 但无论是有参还是无参的b o o t s t r a p 方法，文献 1 8 】的不足之处就是没有很好的 利用这些置信特征，直接通过置信特征来估计原有网络模型，以致于学到的网络结构 的准确率并不高。 文献 1 9 】利用b o o t s t r a p 来处理小样本数据集，通过算法1 对数据集进行扩充，以 此来弥补数据严重不足导致的学出网络精度不高的缺点。算法1 中假设原始数据集 算法1b o o t s t r a p 抽样扩展数据集算法 1 ：i n p u t ：大小为n 的原始数据集d ，方差阈值t 2 ：o u t p u