Open Access Open Access  Restricted Access Subscription Access

A Hybrid Optimization Algorithm for Bayesian Network Structure Learning Based on Database


Affiliations
1 Department of Computer Engineering, Dongguan Polytechnic, Dongguan, China
2 School of Computer Science and Technology, Guangdong University of Technology, Guangzhou, China
 

The process of learning Bayesian networks includes structure learning and parameters learning. During the process, learning the structure of Bayesian networks based on a large database is a NP hard problem. The paper presents a new hybrid algorithm by integrating the algorithms of MMPC (max-min parents and children), PSO (particle swarm optimization) and GA (genetic algorithm) effectively. In the new algorithm, the framework of the undirected network is firstly constructed by MMPC, and then PSO and GA are applied in score-search. With the strong global optimization of PSO and the favorable parallel computing capability of GA, the search space is repaired efficiently and the direction of edges in the network is determined. The proposed algorithm is compared with conventional PSO and GA algorithms. Experimental results show that the proposed algorithm is most effective in terms of convergence speed.

Keywords

Bayesian Network, Particle Swarm Optimization, Genetic Algorithm, Crossover, Mutation.
User
Notifications
Font Size

  • COOPER G, HERSKOVITSE. A Bayesian method for the induction of probabilistic networks from data [J]. machine learning, 1992,(9). p. 309-347.
  • Tsamardinos I, Brown L F, Aliferis C F. The max-min hill climbing Bayesian network structure learning algorithm [J]. Machine Learning, 2006, 65,(1). p. 31-78.
  • Gao Shang, Yang Jingyu. Swarm intelligence algorithms and applications [M]. Beijing: China Water Power Press, 2006. p. 6-10.
  • Liang Jun. Research on particle swarm optimization applied in optimization problems [J]. Master degree theses of Guangxi normal university, 2008.
  • Xu Lijia. Hybrid optimization for Bayesian network structure learning. Academic journal of Zhejiang university, 2009, (5).
  • Junying Meng, Jiaomin Liu, Juan Wang, Ming Han. Target Tracking Based on Optimized Particle Filter Algorithm[J]. Journal of Software. 2013, Vol 8, No 5.
  • Ming Li, Bo Pang, Yongfeng He, Fuzhong Nian. Particle Filter Improved by Genetic Algorithm and Particle Swarm Optimization Algorithm[J]. Journal of Software. 2012, Vol 7, No 6.
  • Zhao Xuewu. Bayesian Network structure learning based on topological order and quantum genetic algorithm [J]. Application of Computer. 2013, (6)
  • Tao Dong, Wenqian Shang, Haibin Zhu. An Improved Algorithm of Bayesian Text Categorization[J]. Journal of Software. 2011, Vol 6, No 9.

Abstract Views: 170

PDF Views: 58




  • A Hybrid Optimization Algorithm for Bayesian Network Structure Learning Based on Database

Abstract Views: 170  |  PDF Views: 58

Authors

Junyi Li
Department of Computer Engineering, Dongguan Polytechnic, Dongguan, China
Jingyu Chen
School of Computer Science and Technology, Guangdong University of Technology, Guangzhou, China

Abstract


The process of learning Bayesian networks includes structure learning and parameters learning. During the process, learning the structure of Bayesian networks based on a large database is a NP hard problem. The paper presents a new hybrid algorithm by integrating the algorithms of MMPC (max-min parents and children), PSO (particle swarm optimization) and GA (genetic algorithm) effectively. In the new algorithm, the framework of the undirected network is firstly constructed by MMPC, and then PSO and GA are applied in score-search. With the strong global optimization of PSO and the favorable parallel computing capability of GA, the search space is repaired efficiently and the direction of edges in the network is determined. The proposed algorithm is compared with conventional PSO and GA algorithms. Experimental results show that the proposed algorithm is most effective in terms of convergence speed.

Keywords


Bayesian Network, Particle Swarm Optimization, Genetic Algorithm, Crossover, Mutation.

References