基于蚁群优化的贝叶斯网结构学习算法

摘要

贝叶斯网是表示随机变量间依赖和独立关系的网络模型,由于具有结构清晰、语义明确等特点,故成为处理不确定性知识表示和推理的一种重要理论模型.贝叶斯网在机器学习、设备故障诊断、故障预测等领域有着广泛的应用,并已经取得了较大的成功.但仅由专家知识构建贝叶斯网通常十分困难,有时甚至是不可能的.因此,从数据中快速、准确地学习贝叶斯网结构具有重要的理论意义和应用价值.
　　 本文在研究蚁群优化和现有结构学习算法的基础上,提出了两种构造贝叶斯网结构的改进算法,主要工作包括三个部分:
　　 首先,针对求解贝叶斯网结构本质图存在的繁琐问题,提出了一种构建贝叶斯网本质图的组合算法.该算法由初始非循环有向图开始,首先对所有有向边进行排序,其次保持V-结构中的边不变,将不参与V-结构的有向边转化为无向边,最后依次根据三条规则判定各条无向边在本质图中的方向.给出了算法的理论证明,通过具体案例分析验证了算法的有效性,从而对在等价类空间上构造贝叶斯网结构具有重要意义.
　　 其次,基于互信息和贪婪搜索,提出了改进的贪婪搜索算法I-GREEDY-E.该算法根据互信息构造初始框架,其次利用最大支撑树算法精简初始框架,并通过条件独立性测试添加方向,最后利用贪婪算法得到最优网络结构.数值实验表明,与原始贪婪算法相比,无论是BIC评分值还是结构误差,I-GREEDY-E算法均有明显改善.
　　 最后,将互信息理论和蚁群优化结合起来,提出了基于互信息的蚁群算法I-ACO-E.该算法基于互信息知识构造初始无向图,其次通过条件独立性测试对无向边添加方向,最后利用蚁群搜索算法得到最优网络结构.实验结果表明,改进算法具有较强的学习能力,能更有效地处理大规模数据,且与新近的一些方法相比,具有更高的求解质量.

目录

文摘

英文文摘

第一章 绪论

1.1 贝叶斯网的研究背景和研究意义

1.2 国内外研究现状

1.3 本文主要研究内容及安排

第二章 贝叶斯网概述

2.1 贝叶斯网络

2.2 条件独立性和互信息理论

2.3 结构学习

2.3.1 基于评分搜索的方法

2.3.2 基于独立性测试的方法

第三章 构建贝叶斯网本质图的组合算法

3.1 算法思想

3.2 算法描述

3.3 算法理论分析

3.4 复杂度分析

3.5 数值实验

3.6 本章小结

第四章 基于互信息的结构学习算法

4.1 I-GREEDY-E算法

4.2 复杂度分析

4.3 数值实验

4.4 本章小结

第五章 基于蚁群优化的结构学习算法

5.1 蚁群优化

5.2 构建贝叶斯网结构的常用ACO算法

5.2.1 ACO-K2SN

5.2.2 ACO-B

5.2.3 ACO-E

5.3 I-ACO-E算法

5.3.1 算法起源

5.3.2 基于互信息压缩搜索空间

5.3.3 I-ACO-E算法描述

5.4 复杂度分析

5.5 数值实验

5.5.1 两种算法总体结果的比较

5.5.2 两种算法的收敛和时间性能比较

5.6 本章小结

结束语

致谢

参考文献

攻读硕士期间的主要研究成果