基于依赖分析的贝叶斯网络结构学习算法研究

摘要

贝叶斯网络是非常重要的一类概率图模型，它用直观的图结构描述随机变量之间的条件独立关系，在不确定性知识的表达和推理方面具有独特的优势，如今已经成功地应用于机器学习、医疗诊断、经济预测、人工智能、数据挖掘、统计推理等多个领域．然而，随着网络规模的不断扩大，仅仅依赖专家领域知识构建贝叶斯网络是相当的困难，甚至是不可行的．基于此，从数据中学习贝叶斯网络结构并进行推理计算已经成为该研究领域的重点和难点问题.
　　在基于独立性测试的方法中，贝叶斯网络被看作是表示变量之间独立关系的网络模型，该类方法从无向完全图出发，利用给定的数据集 D，通过计算任意两个变量之间的卡方统计量或者条件互信息定量描述变量之间的条件独立关系，以此确定相邻节点之间的边是否存在，从而得到与这些条件独立性关系匹配一致的网络模型．该类方法从原理上更接近于贝叶斯网的语义特性，在实际应用中取得较好的效果，而计算节点之间的互信息和高阶条件独立性测试是这类算法复杂度的主要体现，随着节点数目的逐渐增加，独立性测试的次数也会逐渐增加，因此，对复杂数据模式降维，设计出计算效率高的算法就显得十分有必要．
　　本文对贝叶斯网络结构学习进行了比较全面的描述，对贝叶斯网络结构学习的研究现状做了总结，用算法实例对各类算法所存在的不足进行说明，并且指出了各类算法的优缺点．由于从数据中构建贝叶斯网络结构是一个NP-难问题，在本文中，我们提出了基于互信息和PC算法相结合的算法，该算法的思想是从空图开始用互信息得到一个初始无向图，第二个阶段是用PC算法得到部分有向无环图．
　　实验结果显示，我们的算法在相同的条件下优于PC算法，改进的算法降低了条件独立检验的次数，减少了独立检验测试的时间，从而有更明显的优势．

目录

封面

声明

中文摘要

英文摘要

插图索引

表格索引

符号对照表

缩略语对照表

目录

第一章 绪论

1.1 研究背景及意义

1.2 贝叶斯网络的研究现状

1.3 本文的研究内容和结构安排

第二章 贝叶斯网络的相关知识

2.1 贝叶斯网络基本模型

2.2 贝叶斯网络结构学习

2.3 本章小结

第三章 贝叶斯网络结构学习的改进算法

3.1 贝叶斯网络结构学习的前提假设

3.2 PC算法相关知识简介

3.3 边的定向规则

3.4 构造初始无向图

3.5 MUPC算法

3.6 数值实验

3.7 本章小结

第四章 总结与展望

4.1 工作和成果总结

4.2 展望

结束语

致谢

参考文献

攻读硕士学位期间的研究成果