（计算机科学与技术专业论文）贝叶斯网络结构学习算法研究.pdf

摘要 贝叶斯网络提供了一种表示因果关系的方法。它结合图模型理论和 统计学来表达随机变量之间的不确定性知识，并高效地执行推理任务。 最近2 0 多年来，贝叶斯网络学习一直是人工智能和机器学习领域中一个 非常活跃的研究课题，并且提出了许多经典高效的算法。尽管这些方法 都获得了很好的性能，但是当面对有限数据集或高维数据集时，这两类 方法在学习的准确性和效率上都存在缺限。本文的主要贡献如下： 1 ) 最大相关一最小冗余贪婪贝叶斯网络学习算法 结点有序情况下，改进了k 2 算法，使它适用于高维小采样数据集。 引入最大相关一最小冗余特征选择技术，提出局部贝叶斯增量函数以控制 所学贝叶斯网络结构的复杂度。实验结果表明，在小采样数据集上，该 方法在准确性上优于k 2 算法。 未知结点次序情况下，引入了基于结点次序的启发式搜索，提出一 个新颖的候选父结点集合产生方法。同时，我们也引入了最大相关一最小 冗余特征选择技术和局部贝叶斯增量函数，使之适用于小采样数据集。 实验结果表明，在小采样数据集上，该方法在准确性上优于现有算法。 2 ) 基于集成方法的贝叶斯网络学习算法 提出一类学习贝叶斯网络的高效算法。该方法把集成学习应用到贝 叶斯网络学习算法中，学习到一个更加准确的贝叶斯网络。 提出基于增量采样的贝叶斯网络集成学习算法。基于贝叶斯网络学 习的因果马尔科夫属性，提出基于根结点的增量采样技术和相应的组件 集成技术。 提出基于采样分解的贝叶斯网络集成学习算法。基于贝叶斯网络学 习的因果马尔科夫属性，提出基于根结点的采样分解技术和相应的组件 集成技术。 实验结果表明，在有限数据集上，这两类集成贝叶斯网络结构学习 方法在准确性上优于现有算法。 3 ) 关联规贝, l j - 贝叶斯网络集成学习算法 提出基于启发式2 层计数的频繁项集挖掘算法。提出一个新颖的2 层频繁项集生成方法，大大减少了数据集的遍历次数。在每次数据集遍 历过程中，提出启发式遍历技术，减少了数据集遍历时间。实验结果表 贝叶斯网络结构学习算法研究 明，在高维松散大数据集上，效率上优于a p f i o f i 算法。 提出基于启发式2 层计数的频繁项集一贝叶斯网络集成学习算法。 该算法把频繁项集挖掘算法应用到贝叶斯网络学习的得分& 搜索方法中， 利用频繁项集限制贝叶斯网络结构搜索空间，提高了网络结构空间的搜 索效率。实验结果表明，在高维松散大数据集上，本集成算法在效率和 准确性上优于传统的贝叶斯网络学习方法。 4 ) 贝叶斯网络在通信领域的应用初探 对客户流失预测分析问题进行了初步探索，初步提出一个基于贝叶 斯网络的主动流失客户预测分析模型。 关键词贝叶斯网络特征选择集成学习关联规则最大相关一 最小冗余采样技术 a b s t r a c t b a y e s i a nn e t w o r k ( b n ) i sa ni m p o r t a n tm e t h o df o rp r e s e n t i n gc a u s a l i t y a n du n c e r t a i n t ya m o n gr a n d o mv a r i a b l e sb a s e do ng r a p h i c a lm o d e lt h e o r ya n d s t a t i s t i c s i tc a ne f f e c t i v e l yr e a s o nu n d e ru n c e r t a i n t ya n dt a k ed e c i s i o n s d u r i n gt h el a s tt w od e c a d e s ，m a n yb nl e a r n i n ga l g o r i t h m s h a v eb e e n p r o p o s e d a l t h o u g he n c o u r a g i n g r e s u l t sh a v eb e e n r e p o r t e d ，t h et w o a p p r o a c h e sb o t hs u f f e rs o m ed i f f i c u l t i e si na c c u r a c ya n de f f i c i e n c yo nl i m i t e d d a t a s e t so rh i g hd i m e n s i o n a ld a t a s e t s t of u r t h e re n h a n c el e a r n i n ga c c u r a c yo r e 衔c i e n c y , t h i sd i s s e r tp r e s e n t st h ef o l l o w i n gc o n t r i b u t i o n s ： 1 ) m a x r e l e v a n c ea n dm i n - r e d u n d a n c yg r e e d y ( m r m r g ) b nl e a r n i n g a l g o r i t h m s g i v e na l lo r d e r i n ga m o n gn o d e s ，m r m r ga l g o r i t h mi sa nv a r i a n to fk 2 a l g o r i t h mf o rl e a r n i n gb no nh i g hd i m e n s i o n a la n ds m a l ld a t a s e t s m r m r g a l g o r i t h ma p p l i e sm a x r e l e v a n c ea n dm i n - r e d u n d a n c y ( m i 湖r ) f e a t u r e s e l e c t i o nt e c h n o l o g ya n dp r o p o s e sl o c a lb a y e s i a ni n c r e m e n t ( l b i ) f u n c t i o n e x p e r i m e n t a lr e s u l t ss h o wt h a tm r m rga l g o r i t h mh a sm u c hb e r e ra c c u r a c y t h a nk 2a l g o r i t h mo nh i g hd i m e n s i o n a la n ds m a l ld a t a s e t s 、i t hn oo r d e r i n gc o n s t r a i n t ，a no r d e r i n gb a s e dh e u r i s t i cs e a r c ha p p r o a c h i sa p p l i e d ，an o v e lm e t h o dg e n e r a t i n gc a n d i d a t ep a r e n t ss e ti sp r o p o s e da n da n e wm r m r ga l g o r i t h mi sp r e s e n t e d ，c a l l e do r d e r i n g - b a s e dm a x - r e l e v a n c e a n dm i n - r e d u n d a n c yg r e e d y ( o m r m r g ) a tt h es a m et i m e ，o m r m r g a l g o r i t h ma l s ou s e sm r m rt e c h n o l o g ya n dl b if u n c t i o n e x p e r i m e n t a l r e s u l t ss h o wt h a to m i u 订r ga l g o r i t h mh a sm u c hb e a e ra c c u r a c yt h a n t r a d i t i o n a la l g o r i t h m so nh i g hd i m e n s i o n a la n ds m a l ld a t a s e t s 2 、) e n s e m b l eb a s e db a y e s i a nn e t w o r k1 e a r n i n ga l g o r i t h m s e n s e m b l el e a r n i n ga p p r o a c hi si n c o r p o r a t e di n t ob nl e a r n i n ga l g o r i t h m s t w on o v e le n s e m b l eb a s e db nl e a r n i n ga l g o r i t h m sa r ep r o p o s e d m o r e a c c u r a t eb a y e s i a nn e t w o r k sa r ea c q u i r e db yb o t ho ft h ea l g o r i t h m s o n ea l g o r i t h mi sc a l l e da d d i t i v es a m p l i n gb a s e db ne n s e m b l el e a r n i n g b a s e do nt h em a r k o vc o n d i t i o no fb nl e a r n i n g r o o tn o d e sb a s e da d d i t i v e s a m p l i n gm e t h o da n dr e l a t i v ec o m p o n e n t si n t e g r a t i o nm e t h o da r ep r o p o s e d t h eo t h e r a l g o r i t h m i sc a l l e d s a m p l ed e c o m p o s i t i o nb a s e db n e n s e m b l el e a r n i n g b a s e do nt h em a r k o vc o n d i t i o n ，r o o tn o d e sb a s e ds a m p l e d e c o m p o s i t i o nm e t h o da n dr e l a t i v ec o m p o n e n t si n t e g r a t i o nt e c h n o l o g ya r e p r o p o s e d t h ee x p e r i m e n t a lr e s u l t sr e v e a lt h a te n s e m b l eb a s e db nl e a r n i n g m e t h o d sc a na c h i e v ei m p r o v e dr e s u l t sc o m p a r e dw i t hi n d i v i d u a lb n l e a r n i n g a l g o r i t h m si nt e r m so fa c c u r a c yo nl i m i t e dd a t a s e t s 3 ) f r e q u e n ti t e m s e t sb a s e db nl e a r n i n ga l g o r i t h m an e wf r e q u e n ti t e m s e t sm i n i n ga l g o r i t h mi sp r o p o s e d ，c a l l e dh e u r i s t i c t w ol e v e l c o u n t i n gb a s e df r e q u e n t i t e m s e t s m i n i n g ( f i m h t l c ) f i m - h t l ca l g o r i t h mi n t r o d u c e san o v e ls u p p o r tc o u n t i n gm e t h o d ，h e u r i s t i c t w ol e v e lc o u n t i n g ( h t l c ) ，w h i c hr e d u c e st h en u m b e ro fp a s s e so v e r d a t a s e t st oah a l f f i m - h t l ca l g o r i t h ma l s oa p p l i e sa l lh e u r i s t i ct r a v e r s a l t e c h n o l o g yw h i c hs p e e d su po n ep a s so v e rd a t a s e t s t h ee x p e r i m e n t a lr e s u l t s c o n f i r mt h a tf i m - h t l ca l g o r i t h mi sm u c hf a s t e rt h a na p r i o r ia l g o r i t h mo n s p a r s ea n dl a r g ed a t a s e t s af r e q u e n ti t e m s e t sb a s e db nl e a r n i n ga l g o r i t h mi s p r o p o s e d t h i s a l g o r i t h me x p l o i t sf r e q u e n ti t e m s e t st ol i m i tt h es e a r c h i n gs p a c eo fp o s s i b l e b a y e s i a nn e t w o r k sa n de n h a n t et h ee f f i c i e n c yo fs e a r c h i n g t h i sa l g o r i t h mi s o f t e nu s e dt ol e a mb n so nh i g hd i m e n s i o n a l ，s p a r s ea n dl a r g ed a t a s e t s t h e e x p e r i m e n t a lr e s u l t ss h o wt h a tt h i sa l g o r i t h mi sm o r ee f f i c i e n tt h a nt r a d i t i o n a l b nl e a r n i n ga l g o r i t h m so nh i g hd i m e n s i o n a l ，s p a r s ea n d l a r g ed a t a s e t s 4 ) p r e l i m i n a r yr e s e a r c ho nt h ea p p l i c a t i o no fb ni nc o m m u n i c a t i o nf i e l d ar e s e a r c ho nc u s t o m e rc h u r n i n gp r o b l e mw a sp e r f o r m e d a p r e l i m i n a r y b n p r e d i c t i o nm o d e lf o ra c t i v e l yc h u m i n gc u s t o m e ri sp r o p o s e d k e yw o r d s b a y e s i a nn e t w o r km a x - r e l e v a n c ea n dm i n r e d u n d a n c y e n s e m b l ea s s o c i a t i o nr u l e s a m p l i n gt e c h n i q u ec u s t o m e rc h u r n 缩略语 b n ：b a y e s i a nn e t w o r k m r m r ：m a x r e l e v a n c ea n dm i n r e d u n d a n c y m r m r g ：m a x - r e l e v a n c ea n dm i n r e d u n d a n c yg r e e d y l b i ：l o c a lb a y e s i a ni n c r e m e n t o m r m r g ：o r d e r i n g - b a s e dm a x - r e l e v a n c ea n dm i n - - r e d u n d a n c yg r e e d y h t l c ：h e u r i s t i ct w ol e v e lc o u n t i n g f i m h t l c ：h e u r i s t i ct w ol e v e lc o u n t i n gb a s e df r e q u e n ti t e m s e tm i n i n g m d l ：m i n i m u md e s c r i p t i o nl e n g t h m c m c ：m o n t ec a r l om a r k o vc h a i n b i c ：b a y e s i a ni n f o r m a t i o nc r i t e r i o n r n s d ：r o o tn o d e sb a s e ds a m p l ed e c o m p o s i t i o n r n s ：r o o tn o d e sb a s e ds a m p l i n g b s s ：b u s i n e s ss u p p o r ts y s t e m o s s ：o p e r a t i o ns u p p o r ts y s t e m c r m ：c u s t o m e rr e l a t i o n s h i pm a n a g e m e n t 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 趔终 日期： 呈! 里：丛2f l 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学校可以 公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇 编学位论文。( 保密的学位论文在解密后遵守此规定) 本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： 日期：呈空z ! 厶至z 日期： 塑竺乏：! ! ：竺】 第一章绪论 1 1 研究背景和意义 随着计算机技术和网络技术的迅猛发展，使得人们利用信息技术收集数据的能力 大幅度提高。人们深刻地认识到，存储在计算机系统中的各种各样的数据都是宝贵的 信息资源，其中有可能蕴藏着许多有用的知识，这些信息或知识，将可能提供或预示 无限的商机、关键性的技术改进、乃至重要的科学发现，从而产生显著的经济、社会 效益。但是，由于人们目前所用工具的局限性而无法将其挖掘出来。因此，如何从各 种类型的数据中获得实际领域中可利用的、有价值的信息和知识，提高商务管理、生 产控制、市场分析和科学研究等方面的效率，成为计算机研究人员面临的具有挑战性 的任务。例如，九十年代以来，中国通信运营企业的信息化得到了巨大的发展和广泛 的应用，电信业务运营支撑管理系统( o s s m s s ) 和企业资源规划系统( e i 冲) 都已经得到 了不同程度的应用，并取得了巨大的成就。但是在很多情况下这些系统产生的有用数 据无法提炼为有价值的知识，不能及时提供给管理决策者，也就不可能真正转换为强 大的生产力。当前，随着电信领域体制改革的深化，通信运营企业间的竞争也日趋激 烈。谁能正确地分析这些数据，得到有用的知识，谁就能向用户提供更好的服务，发 现更多的商机，在竞争中获胜。 知识发现和数据挖掘1 1 - 4 正是适应这些需求而提出来的，是当前数据库与人工智 能领域研究的热点课题，其目标是在现实世界中，针对具有量的、质的、复杂形态的 各种信息源，挖掘先前未知的、具有潜在应用价值的、最终可被用户所理解的模式【5 6 】。 近年来，人们研究出多种用于知识发现和数据挖掘的方法和技术。主要分为基于 统计的方法【7 1 0 1 、基于机器学习的方法【1 1 , 1 2 1 、基于数学的方法【1 3 , 1 4 】。其中，基于统计 的方法包括回归分析、判别分析、关联分析、贝叶斯网络方法、时间序列分析等；基 于机器学习的方法可分为决策树方法、规则归纳方法、基于实例的方法、神经网络方 法、演化算法等；基于数学的方法有粗糙集方法、模糊逻辑方法等。 在众多的知识发现和数据挖掘方法中，贝叶斯网络结合图论和统计学方面的知 识，提供了一种表示变量之间因果关系的方法。贝叶斯网络以概率论和图论为基础， 结点表示了随机变量，结点间的有向边表示了变量之间的因果关系，变量间影响的程 度由网络中依附在父、子结点对上的条件概率来表示；它是表示和处理不确定知识的 理想模型【1 5 1 引。 贝叶斯网络作为不确定性知识表示的理想模型，具有以下特点【1 5 j 8 】： 贝叶新l 旬络结构学习算法研究 1 ) 具有孥实的数学基础 贝叶斯理论是贝叶斯概率和经典的统计学理论相结合的结果，它给出了信任函数 在数学上的计算方法，刻画了信任度与样本数据的一致性以及信任度随数据而变化的 增量学习特性，长期的理论研究和实践应用，证明了其有效性和正确性。 2 ) 贝叶斯网络是有向无循环图，能够清晰和直观地显示变量之间的因果关系。 3 ) 贝叶斯网络可以图形化表示随机变量间的联合概率，利用概率理论能够处理 各种不确定性信息。 4 ) 贝叶斯网络可以处理不完整和带噪音的数据集。 总之，贝叶斯网络的最大特点是用概率表示所有形式的不确定性。由于上述特点， 贝叶斯网络很快就成为知识发现和数据挖掘领域进行不确定性推理和建模的一个有 效工具。 1 2 贝叶斯网络的产生、发展及研究现状 贝叶斯方法起源于英国学者t h o m a sb a y e s 的论文【1 w “a ne s s a yt o w a r ds o l v i n ga p r o b l e mi nt h ed o c t r i n eo f c h a n c e s 。f i s h e r 的似然推理促进了贝叶斯学派的发展，使 贝叶斯估计、推断及理论系统化。j e f f e r y 对无信息先验分布的重要突破形成了j e f f e r y 准则【2 0 1 ，j e f f e r y 的著作概率论标志着贝叶斯学派的形成。2 0 世纪5 0 年代，以 r o b b i n s 为代表提出经验贝叶斯方法和经典方法相结合【z 1 1 ，引起统计界的广泛重视。 1 9 5 8 年英国历史最悠久的统计杂志b i o m e t r i k a 重新全文刊登了b a y e s 的论文。2 0 世 纪8 0 年代，随着人工智能的发展，p e a r l 等提出贝叶斯网络，并将贝叶斯网络成功地 应用于专家系统，成为不确定专家知识和推理的流行方法【2 2 1 。9 0 年代以后，随着机 器学习、数据挖掘技术的兴起，以及贝叶斯方法的不确定性知识表示能力、综合先验 知识的能力、抗噪音能力等特性，使得贝叶斯方法成为数据挖掘和机器学习中一个重 要研究方向1 2 3 2 4 | 。 2 0 世纪9 0 年代以来，研究主要集中在如何从数据和专家知识中获得贝叶斯网络。 目前主要存在两类贝叶斯网络学习方法：基于搜索和评分的方法( s e a r c ha n ds c o r e b a s e dm e t h o d ) 和基于独立性测试的方法( c o n d i t i o n a li n d e p e n d e n c et e s t i n gb a s e d m e t h o d ) 。 基于搜索和评分的方法主要由两部分组成：评分函数和搜索算法。 常用的评分函数有贝叶斯评分函数和基于信息论的评分函数等。2 0 世纪9 0 年代 初，c o o p e r 和h e r s k o v i t s 建立了著名的基于爬山搜索算法和贝叶斯评分函数的k 2 算法 2 5 , 2 6 1 ，l q 算法是结合先验信息进行贝叶斯网络结构学习的一个有实际意义的重 要算法，在整个贝叶斯网络学习的研究发展过程中占有重要地位。h e c k e r m a n 等扩展 2 第一章绪论 了贝叶斯评分函数的思想，为了避免对训练数据的过度拟合，通过先验知识实现对网 络结构复杂度的一种约束【2 7 。2 9 】。b o u c k a e r t 和s u z u k i 等使用基于信息论中的最小描述 长度原理( m i n i m u md e s c r i p t i o nl e n g t h - m d l ) 的评分函数代替k 2 算法中贝叶斯评分 函数，提出l o 算法【3 0 , 3 1 】。l a m 提出的算法使用m d l 评分函数，通过启发式搜索方 法找出近似最佳的贝叶斯网络，不需要知道结点顺序等先验信息【3 2 习j 。 贝叶斯网络学习是一个n p h a r d 问题【3 4 , 3 5 】。因此，在基于评分和搜索的贝叶斯网 络学习方法中，采用了启发式搜索算法( 例如：随机局部搜索算法、遗传算法、演化 算法等) ，找到的是近似最优的贝叶斯网络。l q 算法【2 5 2 6 1 使用贪婪搜索算法查找次优 贝叶斯网络。s u z u k i 应用分支界限算法和m d l 评分函数学习最优的贝叶斯网络p 。 c a m p o s 等应用随机局部搜索算法学习贝叶斯网络【3 “1 1 。w o n g ( 4 2 4 引，c a m p o s 4 9 1 ， l a r r a n a g a 5 0 - 矧等应用遗传算法或演化算法学习贝叶斯网络。f r i e d m a n ，r i g g e l s e n 等应 用m c m c ( m o n t ec a r l om a r k o vc h a i n ) 模型查找过程学习贝叶斯网络【5 孓捌。同时， l a n - a n a g a , c a m p o s 等提出基于结点次序的搜索空间，并应用遗传算法或演化算法查找 具有最大评分值的结点次序唧躬】。k o c k a , s t u d e n y , c a s t e l o 等提出一个新的结构查找空 间，称作等价类模型空间，并且基于该空间提出了新的查找算子，取得了更好的结果 6 4 - 6 8 o 基于独立性测试的方法把贝叶斯网络被看作是编码了变量间独立性关系的有向 无循环图结构，因此学习网络结构的目的是找到具有独立性关系的变量组，常用的测 试独立性关系的技术是卡方检验和条件互信息。 s p i r t e s 等提出的s g s 算法眇】在不给定结点顺序的情况下，利用条件独立性测试 确定边的存在性和方向，但需要指数数量的条件独立性检验。不久，s p i r t e s 对s g s 算法的搜索策略进行改进，提出了p c 算法【6 9 ，7 0 】，该算法对于稀疏网络的结构学习表 现出较小的计算量。c h e n g 在1 9 9 7 年基于信息通道概念，提出了基于独立性测试的 贝叶斯网络学习算法。该算法在大多数测试数据集上都体现了很好的性能 7 1 - 7 3 j 。 m a r g a r i t i s 提出g s 算法【7 4 1 ，该算法首先通过条件独立性测试识别结点的马尔可夫边 界，然后以一个最大一致性方式连接所有结点，从而学习到一个贝叶斯网络。作者同 时证明了该算法的正确性。 在不完全数据集上学习贝叶斯网络，f r i e d m a n 提出了s t r u c t u r a le m 算法 7 5 , 7 6 ， 该算法结合了e m 算法和结构搜索的方法，e m 算法用于优化网络参数，结构搜索用 于模型选择。f r i e d m a n 证明s e m 可以在算法的每个循环内查找较好的得分网络。 m y e r s ，田凤占等把启发式搜索算法引入不完全数据下贝叶斯网络学习算法，进一步 改进了不完全数据集下的贝叶斯网络学习精度【7 7 。引。 3 贝叶斯网络结构学习算法研究 贝叶斯网络和贝叶斯技术以其坚实的概率论基础得到了广泛的应用。在商业应用 领域，微软公司将贝叶斯网络应用到自己的办公自动化系列产品( o f f i c e9 7 、o f f i c e 2 0 0 0 ) 中。微软还推出了第一个基于贝叶斯网络的专家系统，一个用于幼儿保健的网 站，使父母们可以自行诊断幼儿的疾病。还有许多医疗诊断分析软件也是以贝叶斯网 络为理论基础开发的，例如，p a t h f i n d e r 系统【s 、c p c s b n 远程医疗系统【s l 】等。 n e i l 等将贝叶斯网络用于模拟军事对抗和预测【8 2 1 ；a l b e r o l a 等把贝叶斯网络用于人类 学习中的问题解决【8 3 】：r o d r i g u e s 等把贝叶斯网络用于制造控制系统【8 4 】；贝叶斯网络 同时在d n a 分析【8 5 1 、病理分析【8 6 】、信号检测【8 7 】、系统可靠性分析8 8 】、金融风险分析 8 9 , 9 0 】、图像分析和语音识；) j 1 9 1 , 9 2 】、软件测试【9 3 1 、无线传感器网纠9 4 】等方面均得到了成 功的应用。 国内近十多年出现了许多关于使用贝叶斯网络解决实际问题的研究。宫秀军、史 忠植研究了基于b a y e s 潜在语义模型的半监督w e b 挖掘问题p 5 j ；林士敏、田风占等 把动态贝叶斯网络应用于宏观经济决策和宏观经济建模与仿真研刭9 6 踟】；邓勇将贝叶 斯网络用于模型诊断【恻：曹冬明等使用贝叶斯网络进行故障定位【1 0 0 】；李伟生等对基 于贝叶斯网络的规划识别进行了研刭1 0 l j 等等。 目前，贝叶斯网络的研究主要集中在以下几个方向。一个研究方向是基于不完整 数据集构造贝叶斯网络，以充分利用不完整数据样本中所包含的信息；另一个研究方 向是降低贝叶斯网络学习算法的时间和空间复杂度，提高贝叶斯网络学习的健壮性， 提高所学贝叶斯网络的精确性，特别是在小采样数据集下。最近的研究开始减弱甚至 放弃某些假设，从更一般意义下研究网络结构的学习。此外，现在贝叶斯方法和技术 的应用领域不断地扩展，如基于分布的搜索算法【1 0 2 , 1 0 3 】、信息智能检索【1 0 4 1 删等。 1 3 本文的研究内容 本文的研究主要涉及，在有限数据集合或高维松散数据集合下，提高贝叶斯网络 学习的精度，提高贝叶斯网络学习效率，以及探索贝叶斯网络在通信领域中的应用。 主要进行了以下几个方面的工作： 1 基于最大相关最小冗余特征选择技术的贝叶斯网络贪婪学习算法研究 在当前的贝叶斯网络学习方法中，评分函数和条件独立性测度都是高维算子。在 高维小采样数据集下，随着父集合和条件集合中结点数目的增多，评分函数和条件独 立性测度的计算结果极有可能是不可靠的，从而影响到所学的贝叶斯网络的准确性。 为此，本人把最大相关一最小冗余特征选择技术引入到高维小采样数据集下的贝叶斯 网络学习中。该方法主要分为两种情况：1 ) 已知结点次序；2 ) 未知结点次序。 1 ) 已知结点次序 4 第一章绪论 已知结点次序情况下，最大相关最小冗余贪婪贝叶斯网络结构学习( m r m r g ) 算法改进了k 2 算法，使它适用于高维小采样数据集。m r m r g 算法利用最大相关一 最小冗余特征选择技术和局部贝叶斯增量函数确立评价准则，并通过局部贝叶斯增量 函数控制所学贝叶斯网络结构的复杂度，从而改进所学贝叶斯网络的精度。实验结果 表明，在小采样数据集上，该方法在准确性上优于k 2 算法。 2 ) 未知结点次序 未知结点次序情况下，基于结点次序的最大相关一最小冗余贪婪贝叶斯网络结构 学习算法( o m r m r g ) 己j i 入了基于结点次序的贪婪启发式搜索，提出一个新的候选父 结点集合生成方法提高了学习精度。我们也引入了最大相关一最小冗余特征选择技术 和局部贝叶斯增量函数，使该算法适用于高维小采样数据集。实验结果表明，在高维 小采样数据集上，该方法在准确性优于现有算法。 2 基于集成方法的贝叶斯网络学习算法研究 集成方法是一些学习算法，对于同一任务，组件学习器被训练多次，并且这些训 练结果( 组件) 被集成用于处理新的实例【7 1 。由于集成学习器比它的组件学习器更 加准确，因此集成学习已经成为监督学习的一个热门课题，并且被成功地应用于脸识 别【1 0 8 , 1 0 9 】、医疗诊吲1 1 0 , 1 1 1 1 以及地震信号分类【1 1 2 1 等等。 近些年，贝叶斯网络已经成为成功地分析现实世界因果结构的主要工具。我们提 出一类学习贝叶斯网络的有效算法。该方法把集成学习应用到贝叶斯网络学习算法 中，学习到一个更加准确的贝叶斯网络。 1 ) 基于增量采样的贝叶斯网络集成学习算法 基于贝叶斯网络学习的因果马尔科夫属性，该集成方法提出了基于根结点的增量 采样技术和相应的组件集成技术。实验结果表明，在有限数据集上，该集成贝叶斯网 络结构学习方法在准确性上优于现有算法。 2 ) 基于采样分解的贝叶斯网络集成学习算法 基于贝叶斯网络学习的因果马尔科夫属性和忠实性属性，该集成方法提出了基于 根结点的采样分解技术和相应的组件集成技术。实验结果表明，在有限数据集上，该 集成贝叶斯网络结构学习方法在准确性上优于现有算法。 3 关联规则一贝叶斯网络集成学习算法研究 决策树、神经网络和贝叶斯网络的集成【1 1 3 , 1 1 4 】已经受到许多研究人员的重视，但 是，关联规则与贝叶斯网络集成的研究还比较少；我们提出把频繁项集挖掘算法与贝 叶斯网络学习算法集成以提高贝叶斯网络结构空间查找的速度。 1 ) 基于启发式2 层计数的频繁项集挖掘算法 5 贝叶斯网络结构学习算法研究 a p r i o r i 频繁项集挖掘算法存在着耗时或占用内存空间大的缺点。为了进一步解 决这个问题，提出启发式二层计数频繁项集挖掘算法( f i m h t l c ) 。f i m h t l c 算法 使用了一个新颖的项集生成方法，该方法大大减少了数据集的遍历次数。在每次数据 集遍历过程中，f i m h t l c 算法还采用了启发式技术和划分技术，减少了数据集遍历 时间。实验结果表明，在高维松散大数据集上，f i m h t l c 算法在效率上优于a p r i o r i 算法。 2 ) 基于频繁项集的贝叶斯网络学习算法 提出基于频繁项集的贝叶斯网络学习算法，用于处理高维松散数据集合。该算法 把频繁项集应用到基于贝叶斯网络学习的得分& 搜索方法中，提高了网络结构空间搜 索效率。实验结果表明，在高维松散大数据集上，本算法在效率和准确性上都优于传 统学习方法。 4 贝叶斯网络在通信领域的应用初探 提出一个基于贝叶斯网络的主动离网客户预测分析初级模型。 1 4 论文组织 本文后面的章节组织如下： 第二章贝叶斯网络概述本章包括贝叶斯网络相关概念以及d 一分隔介绍，贝叶 斯网络学习前提假设的介绍，贝叶斯网络参数学习和贝叶斯网络结构学习介绍。 第三章基于最大相关最小冗余贝叶斯网络贪婪学习算法研究本章介绍了熵、 相对熵和互信息的概念和最大相关最小冗余特征选择技术，研究了k 2 算法特点；提 出了局部贝叶斯增量函数，把最大相关最小冗余特征选择技术和局部贝叶斯增量函 数用于k 2 算法，提出最大相关最小冗余贪婪贝叶斯网络学习算法( m r m r g ) ；介绍 了基于结点次序的贪婪搜索算法，提出基于结点次序的最大相关最小冗余贪婪贝叶 斯网络学习算法( o m r m r g ) ，提出一个新颖的候选父结点集合生成方法；最后，给 出m r m r g 和o m r m r g 的实验分析结果。 第四章基于集成的贝叶斯网络学习算法研究本章介绍了图模型的基本概念，介 绍了集成学习中的b a g g i n g 方法和常用的组件集成技术；提出基于集成的贝叶斯网络 学习框架，提出根结点搜索方法；提出基于根结点采样分解技术的贝叶斯网络学习算 法，其中，包括基于根结点的采样分解方法和相应的集成方法，同时，给出正确性证 明；提出基于根结点的采样增量方法和相应的集成方法，同时，给出正确性证明；最 后，给出这两类贝叶斯网络集成学习方法的实验分析结果。 第五章关联规则贝叶斯网络集成学习算法研究本章介绍了关联规则的相关概 念，对a p d o f f 算法进行了研究，提出基于启发式2 层计数的频繁项集挖掘算法；然 6 第一章绪论 后，提出基于频繁项集的贝叶斯网络学习算法；最后，给出基于启发式2 层计数的频 繁项集挖掘算法和基于频繁项集的贝叶斯网络学习算法的实验分析结果。 第六章贝叶斯网络在通信领域的应用初探本章初步探索了客户流失预测分析 问题，提出基于贝叶斯网络的主动流失客户预测分析模型。 7 第二章贝叶斯网络概述 2 1 贝叶斯网络相关概念 在概率理论中，联合概率分布为所有随机变量的每个可能的组合值指定了一个概 率值。给定联合概率分布，人们可以计算任何先验下的后验概率。但是，清晰地描述 一个联合分布需要随机变量个数的指数数量级个参数。贝叶斯网络利用因果效应的局 部性，解决了联合分布的表示问题，并且能够表示变量之间的条件独立性。 关于一组变量v = 五，五，以 的贝叶斯网络【5 1 由以下两个部分组成： 1 ) 一个表示变量集合y 中变量的条件独立性关系的网络结构& 2 ) 与每一个变量相联系的条件概率表p 。 网络结构s 是一个有向无环图，s 中的结点一一对应于v 中的变量，结点之间没 有弧线连接表示结点之间是条件独立的，s 和p 定义v 的联合概率分布【5 1 。根据条 件独立性的性质，联合概率分布为： j i p ( 五，五，以i 孝) = i jp ( 置lp a ( x i ) ，善) i = 1 对于每个变量，忍陇) 是石的父集合。 贝叶斯网络的一个简单的例子见图2 1 。假设所有变量都是离散变量。这个例子 描述了在大学校园的一个虚构的情景。整个情景抽象为5 个变量，所有变量都是布尔 变量：a ( a = t r u e 表示夏天) ，烈庐t r u e 表示白天) ，c ( c = t r u e 表示天气晴朗) ， d 呵r u e 表示人们坐在户外的草坪上) 以及戤互主i t r u e 表示计算机实验室没有人) 。 在图2 1 中，每个变量的条件概率表中的每一行都记录了给定该变量的父集合的某个 实例后，该变量为“t r u e ”或“f a l s e ”的概率值。例如，如果是夏天并且是白天， 那么天气晴朗的概率为0 9 。 从图2 1 中的贝叶斯网络，直观上可知，c 依赖于爿和曰；彳和b 相互独立；指 定c 的值后，彳和d 相互独立。通常，贝叶斯网络可以表示一组条件独立性语句。 在一定的假设下，贝叶斯网络也可以表示变量之间的依赖关系。根据p e a r l 描述的一 组公理1 1 1 6 1 ，可以推出某个贝叶斯网络能够表示的所有独立性关系。然而，根据p e a r l 公理确定贝叶斯网络能够表示的独立性关系非常麻烦，因为这些公理需要重复地使 用，直到这个独立性关系被证明是成立的或者是不成立的。一个等价的方法就是使用 d 分隔( d s e p a r a t i o n ) 从贝叶斯网络结构中“读取”独立性关系。因为应用d 分隔比应 用p e 砌公理要便捷很多，所以，实际中经常使用d 分隔。 第二章贝叶斯网络概述 0 7 5o 2 5 - 彳、)i 曰、) 0 5o 5 二矿， u 4 = “y e s ”b = “y e s ” 0 90 i 4 = “y e s ” b = “1 1 0 ”o o1 0 4 = “i i o ” 上净“y e s ” 0 40 6 4 = n o ”上 = “n o ” 0 01 o p e o p l eo nl a w n ”夕 ( “y e s ” 0 80 2( d ) ( - “n o ”0 1o 9 ， 厂、“c o m p u t e rl a be m p t y u 陟y e s ” 0 70