Computer Science ›› 2015, Vol. 42 ›› Issue (3): 214-217.doi: 10.11896/j.issn.1002-137X.2015.03.044

Previous Articles     Next Articles

Bayesian Network Structure Learning Algorithm Based on Conditional Mutual Information and Probabilistic Jumping Mechanism

WEI Zhong-qiang, XU Hong-zhe, LI Wen and GUI Xiao-lin   

  • Online:2018-11-14 Published:2018-11-14

Abstract: Precise construction of Bayesian network classifier is an NP-hard problem.K2 algorithm can reduce search space effectively and 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,K2 algorithm uses a greedy search strategy and is easy to fall into local optimization solutions.This paper presented a new Bayesian network structure learning algorithm based on conditional mutual information and probabilistic jumping mechanism.Firstly,conditional mutual information is used to determine the initial node ordering as input of K2 algorithm.Then probabilistic jumping mechanism is introduced into K2 algorithm to improve the search process and the ability of global optimization,and learn more reasonable network structure.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.

Key words: Bayesian network classifier,Structure learning,Conditional mutual information,Probabilistic jumping,K2 algorithm

[1] Pearl J.Fusion,Propagation,and Structuring in Belief Networks[J].Artificial Intelligence,1986,29:241-288
[2] 黄建明.贝叶斯网络在学生成绩预测中的应用[J].计算机科学,2012,9(11A):280-282
[3] 李亚飞,吕强,苏伟峰,等.一种小规模数据集下的贝叶斯网络学习方法及其应用[J].计算机科学,2011,8(7):181-184
[4] Wong M L,Leung K S.An efficient data mining method forlearning Bayesian networks using an evolutionary algorithm based hybrid approach[J].IEEE Transactions on Evolutionary Computation,2004,8(4):378-404
[5] Chen X W.Improving Bayesian Network structure learning with mutual information-based node ordering in the K2 algorithm[J].IEEE Transactions on Knowledge and Data Engineering,2008,20(1):1-13
[6] 冀俊忠,张鸿勋,胡仁兵,等.基于独立性测试和蚁群优化的贝叶斯网结构学习算法[J].自动化学报,2009,35(3):281-288
[7] Darwiche A.A differential approach to inference in Bayesiannetworks[J].Journal of ACM,2003,0(3):280-305
[8] Lerner B,Malka R.Investigation of the K2 algorithm in learning Bayesian network classifiers[J].Applied Artificial Intelligence,2011,25(1):74-96
[9] Cooper G F,Herskovits E.A Bayesian method for the induction of probabilistic networks from data[J].Machine Learning,1992,9(4):309-347
[10] Chen X W,Anantha G,Lin X.Improving Bayesian networkstructure learning with mutual information-based node ordering in the K2 algorithm[J].IEEE Transactions on Knowledge and Data Engineering,2008,20(5):628-640
[11] Zhang Y,Zhang W,Xie Y.Improved heuristic equivalent search algorithm based on Maximal Information Coefficient for Baye-sian Network Structure Learning[J].Neurocomputing,2013,117(2):186-195
[12] Chickering D M.Optimal structure identification with greedysearch[J].The Journal of Machine Learning Researeh,2002,3 :507-554
[13] Fleuret F.Fast binary feature selection with conditional mutual information[J].The Journal of Machine Learning Research,2004,5:1531-1555
[14] Al-Rifaie M M,Blackwell T.Bare bones particle swarms with jumps[M].Swarm Intelligence.Springer Berlin Heidelberg,2012:49-60
[15] Jiang J,Wang J,Yu H,et al.Poison Identification Based onBayesian Network:A Novel Improvement on K2 Algorithm via Markov Blanket[M].Advances in Swarm Intelligence.Springer Berlin Heidelberg,2013:173-182
[16] Lauritzen S L,Spiegelhalter D J.Local computations with probabilities on graphical structures and their application to expert systems[J].Journal of the Royal Statistical Society,Series B (Methodological),1988,50(2):157-224
[17] Beinlich I A,Suermondt H J,Chavez R M,et al.The ALARM monitoring system[C]∥A case study with two probabilistic inference techniques for belief networks.Springer Berlin Heidelberg,1989:247-256

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!