贝叶斯网络结构学习的最大最小爬山算法研究

摘要

贝叶斯网络是人工智能领域研究不确定环境下知识表示和因果推理的有效工具之一，如何从数据中自动构建贝叶斯网络结构是目前贝叶斯网络学习研究的热点。最大最小爬山(Max-Min Hill-Climbing, MMHC)算法是Tsamardinos等研究者于2006年提出的一种经典的混合结构学习算法，该算法分为两个阶段，本文主要针对MMHC算法第二阶段中爬山搜索算法易于陷入局部最优的问题，结合近年来新型的启发式搜索算法，提出了相应的改进措施。论文主要工作如下：　　第一，提出了一种基于粒子群搜索策略的MMHC算法。粒子群算法最初用于解决连续优化问题，而MMHC算法第二阶段的寻优是一个离散化问题，从而研究离散二进制粒子群算法。本文针对贝叶斯网络结构学习这一特定问题，分析了离散二进制粒子群算法的可行性，并使其适用于贝叶斯网络结构学习的寻优过程，将其作为MMHC算法第二阶段的搜索策略，提出基于粒子群搜索策略的MMHC算法，并通过数值实验与MMHC算法作比较，验证了改进算法的有效性。　　第二，提出了一种基于布谷鸟搜索策略的MMHC算法。本文在原有二进制布谷鸟算法的基础上，将当前最优解信息引入步长控制量α中，从而得到改进的Lévy飞行的位置更新的跳跃路径：Steptid=α0(Xbesttd-Xtid)(+)Levy，并通过进一步分析Steptid与Levy(λ)的正负取值情况，得到新的位置更新公式，提出一种改进的二进制布谷鸟算法。然后，将改进的二进制布谷鸟算法作为MMHC算法第二阶段的搜索策略，提出基于布谷鸟搜索策略的MMHC算法，并通过数值实验与MMHC算法作比较，验证了本文提出算法的有效性。　　第三，将算法应用于环境空气质量评价中，选取青岛市近三年的日均空气质量数据，在训练集上分别利用两个改进算法以及MMHC算法构建环境空气质量模型，并在测试集上进行分类实验，比较了改进算法与MMHC算法所构建的模型对空气质量指数的评价性能，进一步验证了改进算法的有效性。　　最后，总结了本文的主要研究内容，并提出下一步的研究方向。

目录

声明

变量注释表

1 绪 论

1.1 引 言

1.2 国内外研究现状综述

1.3 问题的提出及研究意义

1.4 主 要 研 究 内 容 及 安 排

2 贝叶斯网络的相关知识

2.1 贝叶斯网络基础知识

2.2 贝叶斯网络结构学习

2.2.1 基于评分搜索的方法

2.2.2 基于依赖分析的方法

2.2.3 混合学习的方法

2.3 MMHC算法

2.3.1 MMPC算法

2.3.2 MMHC算法

2.4 本章小结

3 基于粒子群搜索策略的MMHC算法

3.1.1算法的思想及数学模型

3.1.2 算法步骤

3.2 离散二进制粒子群算法

3.3 改进的MMHC算法

3.3.1 问题描述

3.3.2 算法描述

3.4 实验与分析

3.5 本章小结

4 基于布谷鸟搜索策略的MMHC算法

4.1.1 算法思想

4.1.2 算法步骤

4.2 改进的二进制布谷鸟算法

4.2.1 二进制布谷鸟算法

4.2.2 改进的二进制布谷鸟算法

4.3 改进的MMHC算法

4.4 实验与分析

4.5 本章小结

5 改进算法在环境空气质量评价中的应用

5.1 变量选择与离散化

5.2 模型求解与结果分析

5.3 本章小结

6 总结与展望

6.1 本文的主要工作

6.2 工作展望

参考文献

作者简历

致谢

学位论文数据集