An improved evolutionary approach-based hybrid algorithm for Bayesian network structure learning in dynamic constrained
- PDF / 3,473,782 Bytes
- 22 Pages / 595.276 x 790.866 pts Page_size
- 54 Downloads / 214 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL ARTICLE
An improved evolutionary approach-based hybrid algorithm for Bayesian network structure learning in dynamic constrained search space Jingguo Dai1 • Jia Ren1,2
•
Wencai Du1,3 • Vladimir Shikhin4 • Jixin Ma5
Received: 19 August 2017 / Accepted: 24 July 2018 Ó The Natural Computing Applications Forum 2018
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. Keywords Bayesian networks Structure learning Mutual information Genetic algorithm
1 Introduction
& Jia Ren [email protected] Jingguo Dai [email protected] 1
College of Information Science and Technology, Hainan University, Room 216, No. 58, Renmin Avenue, Haikou 570228, Hainan Province, China
2
State Key Laboratory of Marine Resource Utilization in the South China Sea, Hainan University, Haikou, China
3
Faculty of International Tourism and Management, City University of Macau, Taipa, China
4
Moscow Power Engineering Institute, Moscow, Russia
5
Department of Computing and Information Systems, University of Greenwich, London, UK
A Bayesian network (BN) is a probabilistic graphical model that depicts the uncertain relationships among random variables in the domain. This model is composed of two elements: a directed acyclic graph (DAG) and conditional probability tables (CPTs). The structure of a BN is defined as a DAG, where each node represents a variable and directed edges denote the conditional dependence relationships among nodes. And a CPT quantifies the degree of dependence
Data Loading...
