Computer Science

Computer Science ›› 2022, Vol. 49 ›› Issue (11A): 210800172-7.doi: 10.11896/jsjkx.210800172

• Artificial Intelligence • Previous Articles     Next Articles

Sub-BN-Merge Based Bayesian Network Structure Learning Algorithm

ZHONG Kun-hua1,2,3, CHEN Yu-wen1,2,3, QIN Xiao-lin1,3   

  1. 1 Chengdu Institute of Computer Applications,Chinese Academy of Sciences,Chengdu 610041,China
    2 Chongqing Institute of Green and Intelligent Technology,Chinese Academy of Sciences,Chongqing 400714,China
    3 University of Chinese Academy of Sciences,Beijing 100049,China
  • Online:2022-11-10 Published:2022-11-21
  • About author:ZHONG Kun-hua,born in 1984,doctoralstudent.His main research interests include machine learning,big data intelligent analysis and medical application of AI.
    QIN Xiao-lin,born in 1980,Ph.D,professor,Ph.D supervisor.His main research interests include automated reasoning,swarm intelligence and big data intelligent analysis.
  • Supported by:
    National Key Research & Development program of China(2018YFC0116704),Sichuan Science and Technology Program(2019ZDZX0006,2020YFG0010,2020YFQ0056),Science and Technology Service Network Initiative(KFJ-STS-QYZD-2021-21-001) and National Academy of Science Alliance Collaborative Program(Chengdu Branch of Chinese Academy of Sciences-Chongqing Academy of Science and Technology).

PDF (PC)

471

Abstract: Aiming at the problem that Bayesian network structure learning method K2 requires to provide accurate prior node order information which is difficult to obtain in practice,and hill-climb algorithm is highly dependent on initial network structure and easy to fall into local optimal,.a sub-BN merge based Bayesian network structure learning algorithm,(Sub-BN-Merge) is proposed in this paper.Firstly,for each node,the Sub-BN-Merge algorithm constructs a sub-net and merges them via voting to get a candidate parent set.Next,based on a scoring criterion,the algorithm searches the temporary optimal parent set of every nodes.Then,we breaks the cycle in the directed graph of the search result to get an directed acyclic graph.At last,further optimization is executed via a heuristic search method with directed acyclic graph as the initial value to get the final Bayesian network structure.Experiment is carried out on small network Asia,medium network Alarm and large network Win95pts.we also analyze the algorithm performance for the missing value situation.Experimental results show the effectiveness of the proposed algorithm.Our Sub-BN-Merge algorithm outperforms the comparison algorithms in term of structural Hamming distance and algorithm correct rate.

Key words: Bayesian network, Structure learning, Sub-net merge, K2 algorithm, Hill climb algorithm

CLC Number: 

  • TP181
[1]KYRIMI E,MOSSADEGN S,TAI N,et al.An incremental explanation of inference in Bayesian networks for increasing model trustworthiness and supporting clinical decision making [J].Artificial Intelligence In Medicine,2020,103.
[2]ADABOR E S,ACQUAAH-MENSAH G K.Restricted-dere-stricted dynamic Bayesian Network inference of transcriptional regulatory relationships among genes in cancer [J].Computational Biology and Chemistry,2019,79:155-164.
[3]CHATRABGOUN O,HOSSEINIAN-FAR A.Approximatingnon-Gaussian Bayesian networks using minimum information vine model with applications in financial modelling [J].Journal of Computational Science,2018,24:266-276.
[4]ADEDIPE T,SHAFIEE M.Bayesian Network Modelling forthe Wind Energy Industry:An Overview [J].Reliability Engineering and System Safety,2020,202.
[5]COOPER G F,HERSKOVITS E.A Bayesian Method for the Induction of Probabilistic Networks from Data [J].Machine Learning,1992,9(4):309-347.
[6]SCUTARI M,GRAAFLAND C E.Who learns better Bayesian network structures:Accuracy and speed of structure learning algorithms [J].International Journal of Approximate Reasoning,2019,115:235-253.
[7]SPIRTER P,GLYMOUR C.Causation,Prediction,and Search(2nd edition)[M].The MIT Press,2000.
[8]CHICKERING D M,HECKERMAN D.Large-Sample Learning of Bayesian Networks is NP-Hard [J].Journal of Machine Learning Research,2004,5:1287-1330.
[9]TABAR V R,ESKANDARI F.Finding a set of candidate parents using dependency criterion for the K2 algorithm [J].Pattern Recognition Letters,2018,111:23-29.
[10]BEHJATI S,BEIGY H.Improved K2 algorithm for Bayesiannetwork structure learning [J].Engineering Applications of Artificial Intelligence,2020,91.
[11]YAN ZHI,ZHANG P.Research on Bayesian Network Structure Learning Algorithm Based on Jaya [J].Computer Engineering and Applications,2019,55(19):173-177,184.
[12]LIU H R,ZHANG L Y.Bayesian Network Structure Learning Based on Improved Whale Optimization Strategy [J].Journal of Electronics & Information Technology,2019,41(6):1434-1441.
[13]LIU B,FAN R X.Bayesian network structure learning algo-rithm based on hybrid binarysalp swarm-differential evolution algorithm [J].Journal on Communications,2019,40(7):151-161.
[14]LI J W,LI G N.Application of CS-PSO algorithm in Bayesian Network structure learning [J].Journal of Measurement Science and Instrumentation,2020,11(1):94-102.
[15]CHICKERING D M.Optimal Structure Identification WithGreedy Search [J].Journal of Machine Learning Research,2002,3:507-552.
[16]ALONSO-BARBA J I,OSSA L D L.Scaling up the GreedyEquivalence Search algorithm by constraining the search space of equivalence classes [J].International Journal of Approximate Reasoning,2013,54:429-451.
[17]ALONSO J I,OSSA L D L.On the use of local search heuristics to improve GES-based Bayesiannetwork learning [J].Applied Soft Computing,2018,64:366-376.
[18]FRIEDMAN N,KOLLER D.A Bayesian Approach to Structure Discovery in Bayesian Networks [J].Machine Learning,2003,50:95-125.
[19]LIU B,WANG H Y.Learning Bayesian Network Structure from Node Ordering Searching Optimal [J].Journal of Electronics & Information Technology,2018,40(5):1234-1241.
[20]MARCO S.bnlearn-an R package for Bayesian network learning and inference [EB/OL].[2017-09-06].http://www.bnlearn.com/bnrepository,2013.
[21]TEYSSIER M,KOLLER D.Ordering-Based Search:A Simpleand Effective Algorithm for Learning Bayesian Networks[J].arXiv:1207.1429.
[1] LI Jia-rui, LING Xiao-bo, LI Chen-xi, LI Zi-mu, YANG Jia-hai, ZHANG Lei, WU Cheng-nan. Dynamic Network Security Analysis Based on Bayesian Attack Graphs [J]. Computer Science, 2022, 49(3): 62-69.
[2] LI Chao, QIN Biao. Efficient Computation of Intervention in Causal Bayesian Networks [J]. Computer Science, 2022, 49(1): 279-284.
[3] LI Chao, QIN Biao. Efficient Computation of MPE in Causal Bayesian Networks [J]. Computer Science, 2021, 48(4): 14-19.
[4] XU Yuan-yin,CHAI Yu-mei,WANG Li-ming,LIU Zhen. Emotional Sentence Classification Method Based on OCC Model and Bayesian Network [J]. Computer Science, 2020, 47(3): 222-230.
[5] ZHANG Cheng-wei, LUO Feng-e, DAI Yi. Prediction Method of Flight Delay in Designated Flight Plan Based on Data Mining [J]. Computer Science, 2020, 47(11A): 464-470.
[6] LIN Lang, ZHANG Zi-li. Bayesian Structure Learning Based on Physarum Polycephalum [J]. Computer Science, 2019, 46(9): 206-210.
[7] CHAI Hui-min, FANG Min, LV Shao-nan. Local Path Planning of Mobile Robot Based on Situation Assessment Technology [J]. Computer Science, 2019, 46(4): 210-215.
[8] LIU Hui-qing, GUO Yan-bu, LI Hong-ling, LI Wei-hua. Short Text Feature Extension Method Based on Bayesian Networks [J]. Computer Science, 2019, 46(11A): 66-71.
[9] XING Zhi-wei, ZHU Hui, LI Biao, LUO Qian. Dynamic Estimation of Flight Departure Time Based on Bayesian Network [J]. Computer Science, 2019, 46(10): 329-335.
[10] ZHANG Zhi-dong, WANG Zhi-hai, LIU Hai-yang and SUN Yan-ge. Ensemble Multi-label Classification Algorithm Based on Tree-Bayesian Network [J]. Computer Science, 2018, 45(3): 189-195.
[11] XU Jian-rui, LI Zhan-wu and XU An. KDE-CGA Algorithm of Structure Learning for Small Sample Data Bayesian Network [J]. Computer Science, 2017, 44(Z11): 437-441.
[12] CAO Ru-sheng, NI Shi-hong and ZHANG Peng. Bayesian Networks Structure Learning Algorithm Based on Cloud Genetic Annealing [J]. Computer Science, 2017, 44(9): 239-242.
[13] LIU Dong-rui, LIU Dong-sheng, ZHANG Li-ping, HOU Min and WANG Chun-hui. Prediction of Code Clone Quality Based on Bayesian Network [J]. Computer Science, 2017, 44(4): 165-168.
[14] FU Yong-ping and QIU Yu-hui. Method of Personalized Collaboration Filter Recommendation Based on Bayesian Network [J]. Computer Science, 2016, 43(9): 266-268.
[15] CAO Ru-sheng, NI Shi-hong, ZHANG Peng and XI Xian-yang. EM Parameter Learning Algorithm of Bayesian Network Based on Cloud Model [J]. Computer Science, 2016, 43(8): 194-198.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.