MPD-PSO：一种新的基于混合方式的贝叶斯网络结构学习算法

摘要

贝叶斯网络目前在数据挖掘、模式识别和智能决策等人工智能领域得到了广泛的应用。作为一个重要的推理工具，如何有效地学习贝叶斯网络是解决实际问题首要工作。贝叶斯网络的学习问题可以分成两个部分:网络结构学习和网络参数学习（条件概括表学习）。而要准确的学习整个网络，结构学习是最先解决的问题，决定着贝叶斯网络的应用价值。目前贝叶斯网络结构学习所采用的方法包括三种:(1)基于依赖分析的结构学习方法，该方法对于网络结构比较稀疏的结构学习有很好的学习效果，但对于规模较大的问题很难取得满意的时间复杂度，并且在变量规模较大的情况下，条件独立性测试的结果也将变得不可靠;(2)基于评分搜索的学习方法，该方法在整个网络空间中，通过对网络结构评分的优劣来搜索最优的结构，这种方法在计算复杂度上要好于第一种方法，但得到的网络结构准确度不够高;(3)基于混合方式的结构学习方法，混合方式可以结合上述两种方法的优点，并克服其不足之处，因此成为结构学习中比较常用的方法，并得到了比较广泛的应用。
　　本文引入了一种将最大主子图分解技术和粒子群算法相结合的结构学习方法MPD-PSO(Maximal Prime Decomposition-Particle Swarm Optimization)。该方法首先利用MBDA算法获得目标变量的Markov边界，并以此构建无向独立图，再利用最大主子图分解技术(MPD)将大的无向图分解为多个主子图，以此来降低搜索空间的大小，最后利用粒子群算法(PSO)分别对每个子图进行学习，再将学习后的子网络结构通过合并及边的调整，最终获得完整的最优网络结构。本文以ALARM网为实验数据集，对MPD-PSO算法与粒子群算法在不同大小样本集下的学习效果进行了充分的对比，证明MPD-PSO算法在学习效果、运行时间上均优于所比较的粒子群算法。

目录

声明

摘要

第一章 绪论

1．1 研究背景与意义

1．2 国内外研究现状

1．3 本文研究内容

1．4 本文结构

第二章 贝叶斯网络结构学习

2．1 贝叶斯网络的提出

2．2 贝叶斯网络相关定义

2．3 贝叶斯网络结构学习原理

2．4 本章小结

第三章 粒子群算法和图分解方式下的贝叶斯网络结构学习

3．1 传统的结构学习方法

3．1．1 基于依赖的结构学习方法

3．1．2 基于评分搜索的结构学习方法

3．2 混合方式下的结构学习方法

3．3 图分解方法

3．3．1 图分解原理

3．3．2 最大主子图分解技术

3．4 MPD-PSO算法

3．5 本章小结

第四章 实验设计与结果

4．1 实验设计

4．1．1 实验环境

4．1．2 实验数据

4．2 实验结果分析

4．3 本章小结

第五章 结论

5．1 总结

5．2 后续工作

参考文献

致谢