Optimal BN Structure Learning Algorithm Based on Double Constraints

CHEN Yi-wei; DI Ruo-hai; WANG Peng; ZHANG Xin-lan; ZHANG Huan; XU Wen

doi:10.12263/DZXB.20230268

您当前的位置：

首页 >

文章列表页 >

Optimal BN Structure Learning Algorithm Based on Double Constraints

PAPERS | 更新时间：2025-12-24

- Optimal BN Structure Learning Algorithm Based on Double Constraints
- ACTA ELECTRONICA SINICA Vol. 52, Issue 7, Pages: 2477-2490(2024)
- 作者机构：
  
  1.西安工业大学电子信息工程学院，陕西西安 710021
  2.航天材料及工艺研究所，北京 100076
- 作者简介：
- 基金信息：
  
  Xi'an Science and Technology Plan Project(2023JH-QCYJQ-0086);Outstanding Youth Science Fund Project of Shaanxi Province(2024JC-JCQN-57);Engineering Research Center Project of Shaanxi Universities in 2023(202301);Electronic Equipment Intelligent Testing and Reliability Evaluation Engineering Technology Research Center Project of Shaanxi Province(2023-ZC-GCZX-0047);Youth Innovation Team of Shaanxi Universities in 2022(202201);“Scientist + Engineer” Team of Qinchuangyuan in Shaanxi Province(2023KXJ-026)
- DOI：10.12263/DZXB.20230268
  CLC： TP181;
- Received：23 March 2023，
  
  Revised：2023-08-06，
  
  Published：25 July 2024
- 稿件说明：
移动端阅览
陈艺薇, 邸若海, 王鹏, 等. 基于双重约束的最优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 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Bayesian Program Analysis

Local-Global LWF Chain Graph Structure Learning Algorithm Based on Constraints

Enhanced Artificial Bee Colony Algorithm to Solve Semiconductor Final Test Scheduling Problem

Related Author

WANG Guan-cheng

ZHANG Xin

WU Yi-qian

CHEN Yi-fan

LI Tian-chi

ZHANG Yi-fan

XIONG Ying-fei

Related Institution

School of Computer Science， Peking University

Key Laboratory of High Confidence Software Technologies （Peking University）， Ministry of Education

School of Computer Science， Peking University

School of Computer Science and Information Engineering， Hefei University of Technology

School of Computer and Information Technology， Shanxi University

⁰