基于信息流改进的贝叶斯网络结构学习算法

李 明, 张 韧, 洪 梅, 白成祖

(国防科技大学气象海洋学院, 江苏 南京 211101)

0 引 言

大数据环境下,分析和挖掘海量数据以获取科学评价和决策信息,需要有效的知识表达和分析推理,其中以不确定知识的表达推理最为重要,而贝叶斯网络是对不确定问题模拟和推理的有效工具。从数据样本集中构建贝叶斯网络,包括结构学习和参数学习,其中结构学习是基础和核心。结构学习是指利用训练数据集,尽可能结合先验知识,构建与客观数据最吻合的有向网络拓扑结构,目前贝叶斯网络的研究热点之一就是如何从客观数据中自动学习和优化网络的拓扑结构。

贝叶斯网络结构学习的关键在于如何确定网络节点间的弧和弧方向,常用的结构学习算法可以分为基于统计检测方法和基于搜索评分方法两类。基于统计检测方法关键是选取合适的测度函数进行节点间的依赖程度测试,尤其是条件独立性测试,完成网络结构学习。基于搜索评分方法通常作为最优化问题来处理,即在一个网络结构空间中由评分函数引导搜索最优网络结构。由于从大规模数据库中进行结构学习是一个非确定性多项式(non-deterministic polynomial,NP)难题,所以对于节点较多情况时大都采用搜索评分方法:文献[1]提出基于K2评分的爬山算法;文献[2]提出基于最小描述长度(minimum description length,MDL)评分函数的K3算法;文献[3-4]先后将模拟退火算法和贪婪搜索算法用于网络结构的搜索学习;近些年,文献[5-7]将遗传算法、蚁群优化算法和粒子群算法用于结构学习。……