Hybrid Parrallel Bayesian Network Structure Learning from Massive Data Using MapReduce

Bayesian Network (BN) is the popular and important data-mining model for representing uncertain knowledge. Much work has been done on migrating the BN structure learning algorithms, such as constraint-based (CB) and score-and-search-based (SSB) ones, to the MapReduce framework. But this approach is not suitable for hybrid algorithms, which have to conduct the Map and Reduce operation for all the data to get the scores, but not just the scores of the data in the pruned structures as in the traditional centralized version of hybrid algithm. This means the most time-comsuming part of the algorithm, the Map operations, will be run twice, once in CB and once in SSB. So in the MapReduce framework, when facing massive data, the simple migration of the traditional hybrid algorithm is almost equivalent to executing the CB and SSB sequentially, with little advantage. In this paper, we introduce a distributed hybrid BN structure learning algorithm. By using constraints and search methods that require the same data basis, the algorithm only needs to conduct the Map operation only once, in the CB stage, to prepare the data for the calculation of constraints and scores. Then it reuses intermediate results of constraints calculation in the SSB stage without Mapping the whole data again, thus greatly simplified the computing work. Experiment results show that the efficiency of the algorithm is more than doubled compared to the SSB, and the accuracy is improved by about 36% compared to the CB.