caa a22 4500 445871482 CHVBK 20180317145513.0 cr unu---uuuuu 170323e20110101xx s 000 0 eng 10.1007/s10618-010-0178-6 doi (NATIONALLICENCE)springer-10.1007/s10618-010-0178-6 Learning Bayesian networks by hill climbing: efficient methods based on progressive restriction of the neighborhood [Elektronische Daten] [José Gámez, Juan Mateo, José Puerta] Learning Bayesian networks is known to be an NP-hard problem and that is the reason why the application of a heuristic search has proven advantageous in many domains. This learning approach is computationally efficient and, even though it does not guarantee an optimal result, many previous studies have shown that it obtains very good solutions. Hill climbing algorithms are particularly popular because of their good trade-off between computational demands and the quality of the models learned. In spite of this efficiency, when it comes to dealing with high-dimensional datasets, these algorithms can be improved upon, and this is the goal of this paper. Thus, we present an approach to improve hill climbing algorithms based on dynamically restricting the candidate solutions to be evaluated during the search process. This proposal, dynamic restriction, is new because other studies available in the literature about restricted search in the literature are based on two stages rather than only one as it is presented here. In addition to the aforementioned advantages of hill climbing algorithms, we show that under certain conditions the model they return is a minimal I-map of the joint probability distribution underlying the training data, which is a nice theoretical property with practical implications. In this paper we provided theoretical results that guarantee that, under these same conditions, the proposed algorithms also output a minimal I-map. Furthermore, we experimentally test the proposed algorithms over a set of different domains, some of them quite large (up to 800 variables), in order to study their behavior in practice. The Author(s), 2010 Gámez José Department of Computing Systems, Intelligent Systems and Data Mining Group-i3A, University of Castilla-La Mancha, 02071, Albacete, Spain aut Mateo Juan Department of Computing Systems, Intelligent Systems and Data Mining Group-i3A, University of Castilla-La Mancha, 02071, Albacete, Spain aut Puerta José Department of Computing Systems, Intelligent Systems and Data Mining Group-i3A, University of Castilla-La Mancha, 02071, Albacete, Spain aut Data Mining and Knowledge Discovery Springer US; http://www.springer-ny.com 22/1-2(2011-01-01), 106-148 1384-5810 22:1-2<106 2011 22 10618 https://doi.org/10.1007/s10618-010-0178-6 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10618-010-0178-6 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Gámez José Department of Computing Systems, Intelligent Systems and Data Mining Group-i3A, University of Castilla-La Mancha, 02071, Albacete, Spain aut NATIONALLICENCE 700 1- Mateo Juan Department of Computing Systems, Intelligent Systems and Data Mining Group-i3A, University of Castilla-La Mancha, 02071, Albacete, Spain aut NATIONALLICENCE 700 1- Puerta José Department of Computing Systems, Intelligent Systems and Data Mining Group-i3A, University of Castilla-La Mancha, 02071, Albacete, Spain aut NATIONALLICENCE 773 0- Data Mining and Knowledge Discovery Springer US; http://www.springer-ny.com 22/1-2(2011-01-01), 106-148 1384-5810 22:1-2<106 2011 22 10618 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer