Improved K2 algorithm for Bayesian network structure learning

被引:49
作者
Behjati, Shahab [1 ]
Beigy, Hamid [2 ]
机构
[1] Inst Res Fundamental Sci IPM, Sch Comp Sci, Tehran, Iran
[2] Sharif Univ Technol, Dept Comp Engn, Tehran, Iran
关键词
Bayesian network; Structure learning; Score-based algorithms; Constraint-based algorithm; COMPUTATIONAL INTELLIGENCE; SEARCH ALGORITHM; SPACE; TESTS;
D O I
10.1016/j.engappai.2020.103617
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
In this paper, we study the problem of learning the structure of Bayesian networks from data, which takes a dataset and outputs a directed acyclic graph. This problem is known to be NP-hard. Almost most of the existing algorithms for structure learning can be classified into three categories: constraint-based, score-based, and hybrid methods. The K2 algorithm, as a score-based algorithm, takes a random order of variables as input and its efficiency is strongly dependent on this ordering. Incorrect order of variables can lead to learning an incorrect structure. Therefore, the main challenge of this algorithm is strongly dependency of output quality on the initial order of variables. The main contribution of this paper is to derive a significant order of variables from the given dataset. Also, one of the significant challenges of structure learning is to find a practical structure learning approach to learn an optimal structure from complex and high-dimensional datasets in a reasonable time. We propose a new fast and straightforward algorithm for addressing this problem in a reasonable time. The proposed algorithm is based on an ordering by extracting strongly connected components of the graph built from data. We reduce the super-exponential search space of structures to the smaller space of nodes ordering. We evaluated the proposed algorithm using some standard benchmark datasets and compare the results with the results obtained from some state of the art algorithms. Finally, we show that the proposed algorithm is competitive with some algorithms for structure learning.
引用
收藏
页数:12
相关论文
共 75 条
[1]  
Akaike H., 1998, Selected Papers of Hirotugu Akaike, P199, DOI [10.1007/978-1-4612-1694-0_15, DOI 10.1007/978-1-4612-1694-015]
[2]   Scaling up the Greedy Equivalence Search algorithm by constraining the search space of equivalence classes [J].
Alonso-Barba, Juan I. ;
delaOssa, Luis ;
Gamez, Jose A. ;
Puerta, Jose M. .
INTERNATIONAL JOURNAL OF APPROXIMATE REASONING, 2013, 54 (04) :429-451
[3]   Structural learning of Bayesian networks using local algorithms based on the space of orderings [J].
Alonso-Barba, Juan I. ;
delaOssa, Luis ;
Puerta, Jose M. .
SOFT COMPUTING, 2011, 15 (10) :1881-1895
[4]  
[Anonymous], 2012, ARXIV12066875
[5]  
[Anonymous], 2011, Bayesian Statistics, DOI DOI 10.1093/ACPROF:OSO/9780199694587.003.0010
[6]  
[Anonymous], 2019, SUSTAINABILITY BASEL, DOI [DOI 10.3390/su11010189, DOI 10.3390/SU11010189]
[7]  
[Anonymous], 2020, Handbook of research on machine and deep learning applications for cybersecurity
[8]   Computational intelligence approach for modeling hydrogen production: a review [J].
Ardabili, Sina Faizollahzadeh ;
Najafi, Bahman ;
Shamshirband, Shahaboddin ;
Bidgoli, Behrouz Minaei ;
Deo, Ravinesh Chand ;
Chau, Kwok-wing .
ENGINEERING APPLICATIONS OF COMPUTATIONAL FLUID MECHANICS, 2018, 12 (01) :438-458
[9]  
Bartlett M., 2013, P C UNC ART INT, P182
[10]   Integer Linear Programming for the Bayesian network structure learning problem [J].
Bartlett, Mark ;
Cussens, James .
ARTIFICIAL INTELLIGENCE, 2017, 244 :258-271