近似图引导的演化贝叶斯网络结构学习算法  

Approximate Graph Guided Evolutionary Bayesian Network Structure Learning Algorithm

作　　者：曾奕博 钱鸿 李丙栋 窦亮[1,2] 周爱民[1,2] ZENG Yibo;QIAN Hong;LI Bingdong;DOU Liang;ZHOU Aimin(Shanghai Institute of AI for Education,East China Normal University,Shanghai 200062,China;School of Computer Science and Technology,East China Normal University,Shanghai 200062,China)

机构地区：[1]华东师范大学上海智能教育研究院,上海200062 [2]华东师范大学计算机科学与技术学院,上海200062

出　　处：《小型微型计算机系统》2024年第1期52-61,共10页Journal of Chinese Computer Systems

基　　金：国家自然科学基金委青年科学基金项目(61907015,62106076)资助;上海市科学技术委员会上海市科技创新行动计划项目(19511120601)资助;上海市2020年度“科技创新行动计划”高新技术领域项目(20511102502)资助;上海市教育委员会与上海市教育发展基金会“晨光计划”项目(21CGA32)资助.

摘　　要：贝叶斯网络结构学习是贝叶斯网络推理及应用的基础.搜索高质量的节点序是贝叶斯网络结构学习的一类重要方法.针对在节点序空间中,搜索高质量节点序存在的难以高效、准确评估解的问题,本文提出了一种近似图引导的演化贝叶斯网络结构学习算法.首先,该算法利用互信息构建无向近似图;其次,该算法通过结合节点序和无向近似图构造有向图结构,将其贝叶斯信息准则评分作为节点序的适应度来高效评估节点序,并在演化优化的框架下,使用提出的基于Kendall Tau Distance的交叉算子和基于逆度的变异算子搜索最优节点序;最后,将搜索到的最优节点序输入K2算法得到其对应的贝叶斯网络结构.在4种不同规模网络上的实验结果表明,该算法在收敛时间和准确度之间取得了较好的平衡,其评分相较于对比算法中的次优解分别提升了10.91%、12.28%、53.96%、10.87%.Bayesian network structure learning is the foundation of Bayesian network inference and applications.Furthermore,searching for high-quality orderings is an important part for Bayesian network structure learning.To deal with the problem that it is hard to evaluate solutions efficiently and correctly while searching high-quality orderings in ordering space,a novel approximate graph guided evolutionary Bayesian network structure learning algorithm(AGEA)is proposed.Firstly,mutual information is treated as priori information to construct the undirected approximate graph includes all nodes.Then,the directed approximate graph is made up of ordering and undirected approximate graph.And the fitness of the ordering is the Bayesian information criterion score of its corresponding directed approximate graph.Moreover,the optimal ordering is searched by proposed crossover operator based on Kendall tau distance and mutate operator based on inverse degree in the framework of evolutionary optimization.Last,the searched optimal ordering is utilized by K2 algorithm to construct the Bayesian network structure.Experiment results on 4 different scales of Bayesian networks demonstrate that the proposed AGEA has achieved a better balance between convergence time and accuracy.And the F1 scores of AGEA have improved separately 10.91%,12.28%,53.96%,10.87%compared to the suboptimal solutions.

关 键 词：贝叶斯网络 结构学习 演化算法 近似图 互信息 K2算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]