Abstract
In this paper, a novel method for structure learning of a Bayesian network (BN) is developed. A new genetic approach called the matrix genetic algorithm (MGA) is proposed. In this method, an individual structure is represented as a matrix chromosome and each matrix chromosome is encoded as concatenation of upper and lower triangular parts. The two triangular parts denote the connection in the BN structure. Further, new genetic operators are developed to implement the MGA. The genetic operators are closed in the set of the directed acyclic graph (DAG). Finally, the proposed scheme is applied to real world and benchmark applications, and its effectiveness is demonstrated through computer simulation.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
F. V. Jensen, “Introduction to Bayesian networks,” Technical Report IR 93-2003, Dept. of Mathematics and Computer Science, Univ. of Aalborg, Denmark, 1993.
M. L. Wong and K. S. Leung, “An efficient data mining method for learning Bayesian networks using an evolutionary algorithm-based hybrid approach,” IEEE Trans. on Evolutionary Computation, vol. 8, pp. 378–404, Aug. 2004.
H. Wang, D. Dash, and M. J. Druzdzel, “A method for evaluating elicitation schemes for probabilistic models,” IEEE Trans. on Systems, Man, and Cybernetics, Part B, vol. 32, no. 1, pp. 38–43, Feb. 2002.
S. Acid, L. M. De Campos, A. Gonzalez, R. Molina, and N. Perez de la Blanca, “Learning with CASTLE,” Symbolic and Quantitative Approaches to Uncertainty, R. Kruse and P. Siegel, eds., Lecture Notes in Computer Science 548. Springer-Verlag, 1991.
D. M. Chickering, D. Geiger, and D. Heckerman, “Learning Bayesian networks: search methods and experimental results,” Proc. Fifth Int’l Workshop Artificial Intelligence and Statistics, pp. 112–128, 1995.
G. M. Provan and M. Singh, “Learning Bayesian networks using feature selection,” Preliminary Papers Fifth Int’l Workshop Artificial Intelligence and Statistics, pp. 450–456, 1995.
P. Larrañaga, M. Poza, Y. Yurramendi, R. Murga, and C. Kuijpers, “Structure learning of Bayesian network by genetic algorithms: a performance analysis of control parameters,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 18, no. 9, pp. 912–926, Sept. 1996.
R. Garza-Domínguez, M. Martínez-Morales, N. Cruz-Ramírez, J. L. Jiménez-Andrade, and A. G. Hernández, “A method based on genetic algorithms and fuzzy logic to induce Bayesian networks,” Proc. Fifth Mexican International Conference in Computer Science, Colima, Mexico, pp. 176–180, 2004.
L. M. d. Campos, J. A. Gámez, and S. Moral, “Partial abductive inference in Bayesian belief networks — an evolutionary computation approach by using problem-specific genetic operators,” IEEE Trans. on Evolutionary Computation, vol. 6, pp. 105–131, April 2002.
J. Lee, W. Chung, and E. Kim, “Structure learning of Bayesian networks using dual genetic algorithm,” IEICE Trans. on Information and Systems, vol. E91-D, no. 1, pp. 32–43, 2008.
G. F. Cooper and E. A. Herskovits, “A bayesian method for the induction of probabilistic networks from data,” Machine Learning, vol. 9, no. 4, pp. 309–347, 1992.
X. Li, X. He, and S. Yuan, “Learning Bayesian networks structures from incomplete data based on extending evolutionary programming,” Proc. Int’l Conf. Machine Learning and Cybernetics, vol. 4, pp. 2039–2043, Aug. 2005.
S. Shetty and M. Song, “Structure learning of Bayesian networks using a semantic genetic algorithm-based approach,” Proc. Int’l Conf. Information Technology: Research and Education, pp. 454–458, 2005.
W. Chung, Context Aware Application for Smart Home Based on Bayesian Network, Master thesis, Yonsei University, 2006.
F. V. Jensen, Bayesian Networks and Decision Graphs, Springer, 2001.
S. Z. Zhang, Z. N. Zhang, N. H. Yang, J. Y. Zhang, and X. K. Wang, “An improved EM algorithm for Bayesian networks parameter learning,” Machine Learning and Cybernetics, vol. 3, pp. 1503–1508, Aug. 2004.
Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, Springer, 1999.
P. Larrañaga, C. Kuijpers, and R. Murga, “Learning Bayesian network structures by searching for the best ordering with genetic algorithms,” IEEE Trans. on Systems, Man, and Cybernetics, Part A, vol. 26, pp. 487–493, 1996.
P. Korpipää, M. Koskinen, J. Peltola, S. Mäkelä, and T. Seppänen, “Bayesian approach to sensorbased context awareness,” Personal and Ubiquitous Computing, vol. 7, no. 2, pp. 113–124, 2003.
I. A. Beinlinch, H. J. Suermondt, R. M. Chavez, and G. F. Cooper, “The ALARM monitoring system: a case study with two probabilistic inference techniques for belief networks,” Proc. Second European Conf. Artificial Intelligence in Medicine, pp. 247–256, 1989.
K. B. Hwang and B. T. Zhang, “Bayesian model averaging of Bayesian network classifiers over multiple node-orders application to sparse datasets,” IEEE Trans. on Systems, Man, and Cybernetics, Part B, vol. 35, no. 6, pp. 1302–1310, Dec. 2005.
Author information
Authors and Affiliations
Corresponding author
Additional information
Recommended by Editorial Board member Sungshin Kim under the direction of Editor Young-Hoon Joo. This work was supported by the Ministry of Commerce, Industry and Energy of Korea (HISP). E. Kim appreciates the financial support from LG Yonam Foundation during his sabbatical year at the University of California, Berkeley.
Jaehun Lee received his B.S. and M.S. degrees in Electrical and Electronic Engineering from Yonsei University, Seoul, Korea, in 2005 and 2007, respectively. He is currently a Ph.D. candidate of the School of Electrical and Electronic Engineering at Yonsei University. His current research interests include computational intelligence, localization and tracking in wireless sensor network.
Wooyong Chung received his B.S. and M.S. degrees in Electrical and Electronic Engineering from Yonsei University, Seoul, Korea, in 2004 and 2006, respectively. He is currently a Ph.D. candidate of the School of Electrical and Electronic Engineering at Yonsei University. His current research interests include fuzzy control and evolutionary algorithm.
Euntai Kim received his B.S. (with top honors), M.S., and Ph.D. degrees in Electronic Engineering from Yonsei University, Seoul, Korea, in 1992, 1994, and 1999, respectively. From 1999 to 2002, he was a full-time lecturer with the Department of Control and Instrumentation Engineering at Hankyong National University, Gyeonggi-do, Korea. Since 2002, he has been with the School of Electrical and Electronic Engineering at Yonsei University, where he is currently an Associate Professor. He was a Visiting Scholar with the University of Alberta, Edmonton, Canada, and the Berkeley Initiative in Soft Computing (BISC), UC Berkeley, USA, in 2003 and 2008, respectively. His current research interests include computational intelligence and machine learning and their application to intelligent service robots, unmanned vehicles, home networks, biometrics, and evolvable hardware.
Soohan Kim received his B.S. degrees in Material Science from Chonnam National University, Gwangju, Korea, in 1990. He is currently a Senior Manager and Project Leader of the Internet Infra Technical Planning Team at Samsung Electronics Co. in Korea HQ. He joined Samsung in 1993 and was the first Software Development manager. His current research interests include Contents Sharing with 3 Screens, Multi-Media Platforms, localization and tracking in home network.
Rights and permissions
About this article
Cite this article
Lee, J., Chung, W., Kim, E. et al. A new genetic approach for structure learning of Bayesian networks: Matrix genetic algorithm. Int. J. Control Autom. Syst. 8, 398–407 (2010). https://doi.org/10.1007/s12555-010-0227-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12555-010-0227-3