基于双重约束的最优BN结构学习算法

陈艺薇; 邸若海; 王鹏; 张新兰; 张欢; 许文

doi:10.12263/DZXB.20230268

您当前的位置：

首页 >

文章列表页 >

基于双重约束的最优BN结构学习算法

学术论文 | 更新时间：2025-12-24

- 基于双重约束的最优BN结构学习算法
- Optimal BN Structure Learning Algorithm Based on Double Constraints
- 电子学报 2024年52卷第7期页码：2477-2490
- 作者机构：
  
  1.西安工业大学电子信息工程学院，陕西西安 710021
  2.航天材料及工艺研究所，北京 100076
- 作者简介：
  
  [ "陈艺薇女，1999年2月出生，陕西宝鸡人.西安工业大学电子信息工程学院研究生.主要研究方向为复杂系统建模与评估.E-mail: 1793692717@qq.com" ]
  [ "邸若海男，1986年9月出生，陕西西安人.西安工业大学电子信息工程学院副教授.主要研究方向为复杂系统建模、机器学习理论方法、作战系统仿真.E-mail: xfwtdrh@163.com" ]
  [ "王鹏男，1978年10月出生，山东泰安人.西安工业大学电子信息工程学院教授.主要研究方向为复杂系统建模、图像处理研究.E-mail: wp-xatu@163.com" ]
  [ "张新兰女，1986年9月出生，江西南康人.航天材料及工艺研究所高级工程师.主要研究方向为非金属材料与环境适应性.E-mail: xinlan70@sohu.com" ]
  [ "张欢女，1988年7月出生，陕西宝鸡人.航天材料及工艺研究所高级工程师.主要研究方向为材料贮存与环境适应性.E-mail: zhanghuan701@163.com" ]
- 基金信息：
  
  西安市科技计划项目(2023JH-QCYJQ-0086);陕西省杰出青年科学基金(2024JC-JCQN-57);2023陕西省高校工程研究中心项目(202301);陕西省电子设备智能测试与可靠性评估工程技术研究中心项目(2023-ZC-GCZX-0047);2022陕西省高校青年创新团队(202201);陕西省秦创原“科学家+工程师”队伍建设项目(2023KXJ-026)
- DOI：10.12263/DZXB.20230268
  中图分类号： TP181;
- 收稿：2023-03-23，
  
  修回：2023-08-06，
  
  纸质出版：2024-07-25
- 稿件说明：
移动端阅览
陈艺薇, 邸若海, 王鹏, 等. 基于双重约束的最优BN结构学习算法[J]. 电子学报, 2024, 52(07): 2477-2490.

CHEN Yi-wei, DI Ruo-hai, WANG Peng, et al. Optimal BN Structure Learning Algorithm Based on Double Constraints[J]. Acta Electronica Sinica, 2024, 52(07): 2477-2490.
陈艺薇, 邸若海, 王鹏, 等. 基于双重约束的最优BN结构学习算法[J]. 电子学报, 2024, 52(07): 2477-2490. DOI：10.12263/DZXB.20230268

CHEN Yi-wei, DI Ruo-hai, WANG Peng, et al. Optimal BN Structure Learning Algorithm Based on Double Constraints[J]. Acta Electronica Sinica, 2024, 52(07): 2477-2490. DOI：10.12263/DZXB.20230268

摘要

针对现有基于动态规划的贝叶斯网络结构学习算法复杂度高、无法在合理时间内学习大规模网络的问题，提出基于双重约束的最优贝叶斯网络（Bayesian Network，BN）结构学习算法.首先，利用最大信息系数和马尔科夫毯限制条件独立性（Conditional Independence，CI）测试的候选节点集合和约束集，得到邻居节点集合；其次，利用邻居节点集合约束父节点图的搜索过程，得到候选父节点集合，从候选父节点集合中取出每个节点的最优父集构造初始有向图；再次，利用Tarjan算法计算初始有向图中的强连通分量，得到节点块序；最后，利用节点块序约束节点序图的搜索过程，获得最优的BN结构.实验表明，相比于现有的5种基于动态规划的结构学习算法，本文提出的算法在精度稍微降低的前提下，极大幅度提高了算法的学习效率，如Sachs网络，本文提出的算法相对DPCMB（Dynamic Programming Constrained with Markov Blanket）算法降低了40.3%的时耗，算法精度下降了12.1%.

Abstract

Aiming at the problem that existing Bayesian network (BN) structure learning algorithms based on Dynamic programming are too complex to learn large-scale networks within a reasonable time

a Bayesian network structure learning algorithm based on double constraints is proposed. Firstly

the set of neighbor nodes is obtained by using the set of candidate nodes and constraint set for conditional independence (CI) tests based on the maximum information coefficient and Markov blanket. Secondly

the neighbor node set is used to constrain the search process of the parent node graph

so as to obtain the candidate parent node set. On this basis

the optimal parent set of each node is extracted from the candidate parent node set to construct the initial directed graph. Thirdly

the strongly connected components of the initial digraph are calculated using the Tarjan algorithm to get the node block order. Finally

the optimal BN structure is obtained by using node block order to constrain the search process of node order graph. Experiments show that

compared with the existing five structural learning algorithms based on dynamic programming

the algorithm proposed in this paper greatly improves the learning efficiency of the algorithm under the premise of slightly reduced accuracy. For Sachs network

the proposed algorithm reduces the time consumption by 40.3% and the accuracy by 12.1% compared with DPCMB (Dynamic Programming Constrained with Markov Blanket) algorithm.

关键词

Keywords

references

MIGLIORINI F , MAFFULLI N , COLAROSSI G , et al . Effect of drugs on bone mineral density in postmenopausal osteoporosis: A Bayesian network meta-analysis [J ] . Journal of Orthopaedic Surgery and Research , 2021 , 16 ( 1 ): 533 .

LI Y Q , MAVADATI S M , MAHOOR M H , et al . Measuring the intensity of spontaneous facial action units with dynamic Bayesian network [J ] . Pattern Recognition , 2015 , 48 ( 11 ): 3417 - 3427 .

HE J , YU X C , YU L J , et al . Facial emotion and action unit recognition based on Bayesian network [C ] // 2019 8th International Conference on Computing and Pattern Recognition . New York : ACM , 2019 : 363 - 368 .

KOC L , CARSWELL A . Application of an AODE based classifier to detect DOS attacks [J ] . International Journal of Computer Science and Network Security , 2015 , 15 ( 2 ): 24 .

SUN X Y , DAI J , LIU P , et al . Using Bayesian networks for probabilistic identification of zero-day attack paths [J ] . IEEE Transactions on Information Forensics and Security , 2018 , 13 ( 10 ): 2506 - 2521 .

DON M G , KHAN F . Dynamic process fault detection and diagnosis based on a combined approach of hidden Markov and Bayesian network model [J ] . Chemical Engineering Science , 2019 , 201 : 82 - 96 .

AMIN M T , KHAN F , AHMED S , et al . A data-driven Bayesian network learning method for process fault diagnosis [J ] . Process Safety and Environmental Protection , 2021 , 150 : 110 - 122 .

CHEN C , ZHANG L , TIONG R . A novel learning cloud Bayesian network for risk measurement [J ] . Applied Soft Computing , 2020 , 87 : 105947 .

BOUDALI H , DUGAN J B . A continuous-time Bayesian network reliability modeling and analysis framework [J ] . IEEE Transactions on Reliability , 2006 , 55 ( 1 ): 86 - 97 .

ZHOU Q J , WONG Y D , LOH H S , et al . A fuzzy and Bayesian network CREAM model for human reliability analysis—The case of tanker shipping [J ] . Safety Science , 2018 , 105 : 149 - 157 .

LI M , WANG H T , WANG D M , et al . Risk assessment of gas explosion in coal mines based on fuzzy AHP and Bayesian network [J ] . Process Safety and Environmental Protection , 2020 , 135 : 207 - 218 .

CHICKERING D M , HECKERMAN D , MEEK C . Large-sample learning of Bayesian networks is NP-hard [J ] . Journal of Machine Learning Research , 2004 , 5 : 1287 - 1330 .

吕志刚 , 李叶 , 王洪喜 , 等 . 贝叶斯网络的结构学习综述‍ [J ] . 西安工业大学学报 , 2021 , 41 ( 1 ): 1 - 17 .

LVU Z G , LI Y , WANG H X , et al . Overview of Bayesian network structure learning [J ] . Journal of Xi'an Technological University , 2021 , 41 ( 1 ): 1 - 17 . (in Chinese)

朱明敏 , 刘三阳 , 杨有龙 . 基于混合方式的贝叶斯网络等价类学习算法 [J ] . 电子学报 , 2013 , 41 ( 1 ): 98 - 104 .

ZHU M M , LIU S Y , YANG Y L . Structural learning Bayesian network equivalence classes based on a hybrid method [J ] . Acta Electronica Sinica , 2013 , 41 ( 1 ): 98 - 104 . (in Chinese)

KOIVISTO M , SOOD K . Exact Bayesian structure discovery in Bayesian networks [J ] . Journal of Machine Learning Research , 2004 , 5 : 549 - 573 .

JAAKKOLA T , SONTAG D , GLOBERSON A , et al . Learning Bayesian network structure using LP relaxations [C ] // International Conference on Artificial Intelligence and Statistics . Brookline : Microtome Publishing , 2010 : 358 - 365 .

CAMPOS D P C , JI Q . Efficient structure learning of Bayesian networks using constraints [J ] . Journal of Machine Learning Research , 2011 , 12 : 663 - 689 .

叶思懋 . 融合先验的贝叶斯网络结构学习及其在智能决策中的应用 [D ] . 西安 : 西北工业大学 , 2018 .

YE S M . Learning Bayesian Network Structure Learning with Prior Fusion and its Application in Intelligent Decision-Making [D ] . Xi'an : Northwestern Polytechnical University , 2018 . (in Chinese)

谭翔元 , 高晓光 , 贺楚超 . 基于马尔科夫毯约束的最优贝叶斯网络结构学习算法 [J ] . 电子学报 , 2019 , 47 ( 9 ): 1898 - 1904 .

TAN X Y , GAO X G , HE C C . Learning optimal Bayesian network structure constrained with Markov blanket constraint [J ] . Acta Electronica Sinica , 2019 , 47 ( 9 ): 1898 - 1904 . (in Chinese)

YANG Y , GAO X G , GUO Z G . Finding optimal Bayesian networks by a layered learning method [J ] . Journal of Systems Engineering and Electronics , 2019 , 30 ( 5 ): 946 - 958 .

LI X , GAO X , WANG C . A novel BN learning algorithm based on block learning strategy [J ] . Sensors (Basel, Switzerland) , 2020 , 20 ( 21 ): E6357 .

张连文 , 郭海鹏 . 贝叶斯网引论 [M ] . 北京 : 科学出版社 , 2006 .

ZHANG L W , GUO H P . Introduction to Bayesian Networks [M ] . Beijing : Science Press , 2006 . (in Chinese)

MALONE B , YUAN C , HANSEN E A . Memory-efficient dynamic programming for learning optimal Bayesian networks [J ] . Proceedings of the AAAI Conference on Artificial Intelligence , 2011 , 25 ( 1 ): 1057 - 1062 .

RESHEF D N , RESHEF Y A , FINUCANE H K . Detecting novel associations in large data sets [J ] . Science , 2011 , 334 ( 6062 ): 1518 - 1524 .

ZHANG Y H , ZHANG W S , XIE Y . Improved heuristic equivalent search algorithm based on maximal information coefficient for Bayesian network structure learning [J ] . Neurocomputing , 2013 , 117 : 186 - 195 .

SHAO F B , LI K P , XU X M . Railway accidents analysis based on the improved algorithm of the maximal information coefficient [J ] . Intelligent Data Analysis , 2016 , 20 ( 3 ): 597 - 613 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

贝叶斯程序分析

基于约束的局部-全局LWF链图结构学习算法

增强人工蜂群算法求解半导体最终测试调度问题