Abstract
The precise construction of Bayesian network classifier from database is an NP-hard problem and still one of the most exciting challenges. K2 algorithm can reduce search space effectively, improve learning efficiency, but it requires the initial node ordering as input, which is very limited by the absence of the priori information. On the other hand, search process of K2 algorithm uses a greedy search strategy and solutions are easy to fall into local optimization. In this paper, we present an improved Bayesian network structure learning with node ordering via K2 algorithm. This algorithm generates an effective node ordering as input based on conditional mutual information. The K2 algorithm is also improved combining with Simulated Annealing algorithm in order to avoid falling into the local optimization. Experimental results over two benchmark networks Asia and Alarm show that this new improved algorithm has higher classification accuracy and better degree of data matching.
This research is supported by the central university basic scientific research business (XKJC2014008).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Pearl, J.: Fusion, Propagation, and Structuring in Belief Networks. Artificial Intelligence 29, 241–288 (1986)
Wong, M.L., Leung, K.S.: An Efficient Data Mining Method for Learning Bayesian Networks using an evolutionary algorithm based hybrid approach. IEEE Transactions on Evolutionary Computation 8(4), 378–404 (2004)
Chen, X.W., Anantha, G., Lin, X.: Improving Bayesian Network Structure Learning With Mutual information-based node ordering in the K2 algorithm. IEEE Transactions on Knowledge and Data Engineering 20(1), 1–13 (2008)
Darwiche, A.: A Differential Approach to Inference in Bayesian Networks. arXiv preprint arXiv:1301.3847 (2013)
Lerner, B., Malka, R.: Investigation of the K2 Algorithm in Learning Bayesian Network classifiers. Applied Artificial Intelligence 25(1), 74–96 (2011)
Cooper, G., Herskovits, F.E.: A Bayesian Method for The Induction of Probabilistic networks from data. Machine Learning 9(4), 309–347 (1992)
Lam, W., Bacchus, F.: Learning Bayesian Belief Networks: all Approach Based on the MDL Principle. Computational Intelligence 10(4), 269–293 (1994)
De Campos, L.M., Juan, M.F., José, A.G., et al.: Ant Colony Optimization for Learning Bayesian networks. Computational Intelligence 10, 269–293 (1994)
Chickering, D.M.: Optimal structure identification with Greedy Search. The Journal of Machine Learning Researeh 3, 507–554 (2002)
Chickering, D., Geiger, D., Heckerman, D.: Learning Bayesian Networks: Search methods and experimental results. In: Proceedings of Fifth Conference on Artificial Intelligence and Statistics, pp. 112–128 (1995)
Aarts, E., Korst, J., Michiels, W.: Simulated annealing. Search methodologies, pp. 187–210. Springer, US (2005)
Steck, H.: Learning the Bayesian Network Structure: Dirichlet prior Versus Data. arXiv preprint arXiv:1206.3287 (2012)
Rissanen, J.: Minimum description length principle. Encyclopedia of Machine Learning, pp. 666–668. Springer, US (2010)
Lam, W., Bacchus, F.: Using Causal Information And Local Measures to Learn Bayesian networks. In: Proceedings of the Ninth International Conference on Uncertainty in Artificial Intelligence, pp. 243–250. Morgan Kaufmann Publishers Inc. (1993)
Yun, Z., Keong, K.: Improved MDL Score for Learning of Bayesian Networks. In: Proceedings of the International Conference on Artificial Intelligence in Science and Technology, AISAT, pp. 98–103 (2004)
Jiang, J., Wang, J., Yu, H., Xu, H.: Poison Identification Based on Bayesian Network: A Novel Improvement on K2 Algorithm via Markov Blanket. In: Tan, Y., Shi, Y., Mo, H. (eds.) ICSI 2013, Part II. LNCS, vol. 7929, pp. 173–182. Springer, Heidelberg (2013)
Lauritzen, S.L., Spiegelhalter, D.J.: Local Computations with Probabilities on Graphical structures and their application to expert systems. Journal of the Royal Statistical Society, Series B (Methodological), 157–224 (1988)
Beinlich, I.A., Suermondt, H.J., Chavez, R.M., Cooper, G.F.: The ALARM monitoring system: A Case Study with Two Probabilistic Inference Techniques for Belief Networks, pp. 247–256. Springer, Heidelberg (1989)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Wei, Z., Xu, H., Li, W., Gui, X., Wu, X. (2014). Improved Bayesian Network Structure Learning with Node Ordering via K2 Algorithm. In: Huang, DS., Jo, KH., Wang, L. (eds) Intelligent Computing Methodologies. ICIC 2014. Lecture Notes in Computer Science(), vol 8589. Springer, Cham. https://doi.org/10.1007/978-3-319-09339-0_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-09339-0_5
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-09338-3
Online ISBN: 978-3-319-09339-0
eBook Packages: Computer ScienceComputer Science (R0)