Skip to main content

Advertisement

SpringerLink
Log in

An improved evolutionary approach-based hybrid algorithm for Bayesian network structure learning in dynamic constrained search space

  • Original Article
  • Published:
Neural Computing and Applications Aims and scope Submit manuscript

Abstract

Learning Bayesian network (BN) structures from data is a NP-hard problem due to the vastness of the solution space. To address this issue, hybrid approaches that integrate the constraint-based (CB) method and the score-and-search (SS) method have been developed in the literature, but when the constrained search space is fixed and inaccurate, it is very likely to lose the optimal solution, leading to low learning accuracy. Besides, due to the randomness and uncertainty of the search, it is difficult to preserve the superiority of the structures, resulting in low learning efficiency. Therefore, we propose a novel hybrid algorithm based on an improved evolutionary approach to explore BN structure with highest matching degree of data set in dynamic constrained search space. The proposed algorithm involves two phases, namely the CB phase and the SS phase. In the CB phase, the mutual information is utilized as the restriction to limit the search space, and a binding parameter is introduced to the novel encoding scheme so that the search space can be dynamically changed in the evolutionary process. In the SS phase, a new operator is developed to pass on the excellent genes from generation to generation, and an update principle for the binding parameter is exploited for the dynamic selection of the search space. We conduct the comparative experiments on the benchmark network data sets and provide performance and applicability analysis of our proposed method. The experimental results show that the new algorithm is effective in learning the BN structures.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

References

  1. Yue K, Wu H, Fu XD, Xu J, Yin ZD, Liu WY (2017) A data-intensive approach for discovering user similarities in social behavioral interactions based on the Bayesian network. Neurocomputing 219:364–375

    Article  Google Scholar 

  2. Ramírez-Noriega A, Juárez-Ramíez R, Martínez-Ramírez Y (2017) Evaluation module based on Bayesian networks to Intelligent Tutoring Systems. Int J Inf Manag 37(1):1488–1498

    Article  Google Scholar 

  3. Larrañaga P, Karshenas H, Bielza C, Santana R (2013) A review on evolutionary algorithms in Bayesian network learning and inference tasks. Inf Sci 233:109–125

    Article  MathSciNet  MATH  Google Scholar 

  4. Chickering DM, Heckerman D, Meek C (2004) Large-sample learning of Bayesian networks is NP-hard. J Mach Learn Res 5(10):1287–1330

    MathSciNet  MATH  Google Scholar 

  5. Kalisch M, Bühlmann P (2016) Estimating high-dimensional directed acyclic graphs with the PC-algorithm. J Mach Learn Res 8(3):613–636

    MATH  Google Scholar 

  6. Villanueva E, Maciel CD (2014) Efficient methods for learning Bayesian network super-structures. Neurocomputing 123:3–12

    Article  Google Scholar 

  7. Spirtes P, Glymour C (1991) An algorithm for fast recovery of sparse causal graphs. Soc Sci Comput Rev 9(1):62–72

    Article  Google Scholar 

  8. Yuan C, Malone B (2013) Learning optimal bayesian networks: a shortest path perspective. J Artif Intell Res 48(10):23–65

    Article  MathSciNet  MATH  Google Scholar 

  9. O’Gorman B, Babbush R, Perdomo-Ortiz A, Aspuru-Guzik A, Smelyanskiy V (2015) Bayesian network structure learning using quantum annealing. Eur Phys J Spec Top 224(1):163–188

    Article  Google Scholar 

  10. Gheisari S, Meybodi MR (2016) BNC-PSO: structure learning of Bayesian networks by particle swarm optimization. Inf Sci 348:272–289

    Article  MathSciNet  MATH  Google Scholar 

  11. Wong ML, Leung KS (2004) An efficient data mining method for learning Bayesian networks using an evolutionary algorithm-based hybrid approach. IEEE Trans Evol Comput 8(4):378–404

    Article  Google Scholar 

  12. Lee J, Chung W, Kim E (2008) Structure learning of Bayesian networks using dual genetic algorithm. IEICE Trans Inf Syst 91(1):32–43

    Article  Google Scholar 

  13. Lee J, Chung W, Kim E, Kim S (2010) A new genetic approach for structure learning of Bayesian networks: matrix genetic algorithm. Int J Control Autom Syst 8(2):398–407

    Article  Google Scholar 

  14. Li BH, Liu SY, Li ZG (2012) Improved algorithm based on mutual information for learning Bayesian network structures in the space of equivalence classes. Multimed Tools Appl 60(1):129–137

    Article  Google Scholar 

  15. Teyssier M, Koller D (2005) Ordering-based search: a simple and effective algorithm for learning Bayesian networks. In: Proceedings of 21st conference on uncertainty in artificial intelligence, pp 584–590

  16. dos Santos EB, Hruschka Jr ER, Ebecken NFF (2010) Evolutionary algorithm using random multi-point crossover operator for learning Bayesian network structures. In: Proceedings of 9th international conference on machine learning and applications, pp 430–435

  17. dos Santos EB, Hruschka Jr ER, Hruschka ER, Ebecken NFF (2010) A distance-based mutation operator for learning bayesian network structures using evolutionary algorithms. In: Proceedings of IEEE congress on evolutionary computation, pp 1–8

  18. Jiang J, Wang J, Yu H, Xu H (2013) Poison identification based on Bayesian network: a novel improvement on K2 algorithm via markov blanket. In: Proceedings of 4th international conference in swarm intelligence, pp 173–182

    Google Scholar 

  19. Chen XW, Anantha G, Lin X (2008) Improving Bayesian network structure learning with mutual information-based node ordering in the K2 algorithm. IEEE Trans Knowl Data Eng 20(5):628–640

    Article  Google Scholar 

  20. Ji JZ, Zhang HX, Hu RB, Liu CN (2009) A Bayesian network learning algorithm based on independence test and ant colony optimization. Acta Automatica Sinica 35(3):281–288

    MATH  Google Scholar 

  21. Masegosa AR, Moral S (2013) New skeleton-based approaches for Bayesian structure learning of Bayesian networks. Appl Soft Comput 13(2):1110–1120

    Article  Google Scholar 

  22. Tsamardinos I, Brown LE, Aliferis CF (2006) The max–min hill-climbing Bayesian network structure learning algorithm. Mach Learn 65(1):31–78

    Article  Google Scholar 

  23. Kojima K, Perrier E, Imoto S, Miyano S (2010) Optimal search on clustered structural constraint for learning Bayesian network structure. J Mach Learn Res 11(1):285–310

    MathSciNet  MATH  Google Scholar 

  24. Larrañaga P, Poza M, Yurramendi Y, Murge RH, Kuijpers CMH (1996) Structure learning of Bayesian networks by genetic algorithms: a performance analysis of control parameters. IEEE Trans Pattern Anal Mach Intell 18(9):912–926

    Article  Google Scholar 

  25. Faulkner E (2007) K2GA: heuristically guided evolution of Bayesian network structures from data. In: Proceedings of 1st IEEE symposium on computational intelligence and data mining, pp 18–25

  26. Liu K, Ng JKY, Lee VCS, Son SH, Stojmenovic I (2016) Cooperative data scheduling in hybrid vehicular ad hoc networks: VANET as a software defined network. IEEE/ACM Trans Netw 24(3):1759–1773

    Article  Google Scholar 

  27. Robinson RW (1977) Counting unlabeled acyclic digraphs. In: Little CHC (ed) Lecture notes in mathematics: combinatorial mathematics, vol V. Springer, Berlin, pp 28–43

    Google Scholar 

  28. de Campos LM, Castellano JG (2007) Bayesian network learning algorithms using structural restrictions. Int J Approx Reason 45(2):233–254

    Article  MathSciNet  MATH  Google Scholar 

  29. Cooper GF, Herskovits E (1992) A Bayesian method for the induction of probabilistic networks from data. Mach Learn 9(4):309–347

    MATH  Google Scholar 

  30. Friedman N, Koller D (2003) Being Bayesian about network structure. A Bayesian approach to structure discovery in Bayesian networks. Mach Learn 50(1):95–125

    Article  MATH  Google Scholar 

  31. Bac FQ, Perov VL (1993) New evolutionary genetic algorithms for NP-complete combinatorial optimization problems. Biol Cybern 69(3):229–234

    Article  MATH  Google Scholar 

  32. Zhang H, Cao X, Ho JKL, Chow TWS (2017) Object-level video advertising: an optimization framework. IEEE Trans Ind Inf 69(3):229–234

    Google Scholar 

  33. Chickering DM (1995) A transformational characterization of equivalent Bayesian network structures. In: Proceedings of 11th conference on uncertainty in artificial intelligence, pp 87–98

  34. Cheng J, Greiner R, Kelly J, Bell D, Liu W (2002) Learning Bayesian networks from data: an information-theory based approach. Artif Intell 137(1–2):43–90

    Article  MathSciNet  MATH  Google Scholar 

  35. Lauritzen SL, Spiegelhalter DJ (1988) Local computations with probabilities on graphical structures and their application to expert systems. J R Stat Soc Ser B (Methodol) 50(2):157–224

    MathSciNet  MATH  Google Scholar 

  36. Mann HB, Whitney DR (1947) On a test of whether one of two random variables is stochastically larger than the other. Ann Math Stat 18(1):50–60

    Article  MathSciNet  MATH  Google Scholar 

  37. Liu H, Zhou S, Lam W, Guan J (2017) A new hybrid method for learning bayesian networks: separation and reunion. Knowl Based Syst 121:185–197

    Article  Google Scholar 

Download references

Acknowledgements

This study was funded by the National Natural Science Foundation of China (61562018), the International S&T Cooperation Projects of China (2015DFR10510), the Natural Science Foundation of Hainan Province, China (20166209) and the Research Projects of Hainan Institutes of Higher Education, China (HNKY2014-04).

Author information

Authors and Affiliations

  1. College of Information Science and Technology, Hainan University, Room 216, No. 58, Renmin Avenue, Haikou, 570228, Hainan Province, China

    Jingguo Dai, Jia Ren & Wencai Du

  2. State Key Laboratory of Marine Resource Utilization in the South China Sea, Hainan University, Haikou, China

    Jia Ren

  3. Faculty of International Tourism and Management, City University of Macau, Taipa, China

    Wencai Du

  4. Moscow Power Engineering Institute, Moscow, Russia

    Vladimir Shikhin

  5. Department of Computing and Information Systems, University of Greenwich, London, UK

    Jixin Ma

Authors
  1. Jingguo Dai
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jia Ren
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Wencai Du
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Vladimir Shikhin
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Jixin Ma
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jia Ren.

Ethics declarations

Conflict of interest

The authors declare that we have no conflict of interest.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Dai, J., Ren, J., Du, W. et al. An improved evolutionary approach-based hybrid algorithm for Bayesian network structure learning in dynamic constrained search space. Neural Comput & Applic 32, 1413–1434 (2020). https://doi.org/10.1007/s00521-018-3650-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00521-018-3650-7

Keywords

Search

Navigation