文档介绍：北京工业大学
硕士学位论文
基于K2评分的贝叶斯网结构学习算法的研究
姓名:张鸿勋
申请学位级别:硕士
专业:计算机软件与理论
指导教师:冀俊忠
20090401
摘要珺是联合概率分布的一种图形化表示,由于具有结构清晰,语义明确等特点,因此成为处理不确定性知识表示和推理的一种重要理论模型。贝叶斯网在机器学习、医疗诊断、金融分析等领域有着广泛的应用,并已经取得了较大的成功。但仅由专家构建贝叶斯网通常十分困难,有时甚至是不可能的。因此,从数据中快速、准确地学习贝叶斯网络结构具有重要的理论意义和应用价值。本文在研究国内外现有算法的基础上,针对其中的一些贝叶斯网结构学习算法的不足,以网络结构评分为测度,提出了几种改进方法。主要工作包括三首先,针对目前学习算法参数较多,结构复杂的不足,将禁忌搜索τ玫奖匆端雇峁寡暗敝校岢隽艘恢只诮伤阉鞯谋匆端雇构学习算法。新算法首先利用加边、减边、逆向边三个算子产生当前解的邻域,然后将禁忌表和蔑视准则结合使用来引导和限制搜索过程,两步骤迭代进行,最后达到全局最优解或近似最优解。与其他算法相比,新算法结构简单、参数少,易于实现和应用,同时求解质量也有一定的提高。其次,针对蚁群优化学习贝叶斯网结构算法瓸的不足,提出了基于独立性测试和蚁群优化的结构学习的改进算法狟。新算法首先利用锥懒性测试来限制侯选结构的搜索空间,避免了蚁群的一些不必要的搜索,然后融合解的全局评分增益和节点间局部的互信息,给出了启发能力更强的启发函数来引导随机搜索,实验结果表明,新算法能更有效地处理大规模数据,且大幅度提升了学习速度。插入对数据进行完备化,在完备数据下,利用改进的蚁群优化过程使结构不断进化,直到获得全局最优的解。实验结果表明,新方法能够有效地从不完备数据中学习贝叶斯网结构,且与新近的一些方法相比,具有更高的学习精度。关键词贝叶斯网;结构学习;蚁群算法;禁忌搜索:缺失数据贝叶斯网个部分:最后,针对数据不完备情况下贝叶斯网算法学习精度不高的问题,—J紫人婊跏蓟垂鄄斓降氖据,得到完整的数据集,并利用蚁群算法学习得到初始网络结构:然后进行迭代学习,在每次迭代中根据当前最好的贝叶斯网结构,利用估计和随机的采样
—狟瓼,—琲,籅,,,—瑆——,瓹,瓸琭甎。琹:‘瑂瓵瓵瑃琒,
..瑂,,,,...
签名:拯趱塑导师签名:鲎鳖显:日期:逸醯签名:蜀缒三垒塑日期:趁芝缝‘髅旦独创性声明关于论文使用授权的说明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得北京工业大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。本人完全了解北京工业大学有关保留、使用学位论文的规定,即:学校有权保留送交论文的复印件,允许论文被查阅和借阅:学校可以公布论文的全部或部分内容,可以采用影印、缩印或其他复制手段保存论文。C艿穆畚脑诮饷芎笥ψ袷卮斯娑
。贝叶斯网具有理论基础坚实,结构直观,语义清晰等特点,因此成为处理不确定性知识的主流模型,已经成功的应用到医疗诊断、金融分析、自动目标识别、军事等很多领域。贝叶斯网的构造方法有两种,一种是通过咨询专家进行手工构造,一种是利用计算机从数据集中学习。前者一般不采用,因为当数据量较大时,仅仅依赖于专家知识构造网络是费时费力,甚至是不可能的R虼斯谕獾难д咧饕P巳集中在如何从数据中学习贝叶斯网,从而使其成为当今的一个热门研究领域。从数据中学习贝叶斯网的结构,可以概括为:找出与给定的数据集相对应的后验概率最大的网络模型【;谕瓯甘莸慕峁寡胺椒ㄏ喽员冉铣墒欤中主要分为基于约束满足的方法和基于评分搜索的方法。然而,现实世界中的数据并不都是完备的,因为某些变量的值不可观测或者观测代价较大,所以导致数据集通常包含缺失值。另外,贝叶斯网的优势之一就是可以进行缺失数据下的推理,然而与此同时要求其训练数据集必须是完备的就难以让人信服。因此对不完备数据下贝叶斯网结构学习的研究更具有实际意义。综上,全面深入的研究贝叶斯网络结构学习问题,无论在理论上还是在现实生活的应用中都有着重要的意义和价值。内外的学者对其进行了积极的探索,并取得了一定的成果,其中数据完备时的算法相对比较成熟。从实现的机理上,这些算法可概括为两种基本方法:谠际愕姆椒