Research On Bayesian Networks Structure Learning Algorithm

Bayesian networks(BNs)is theoretical models,which are regarded as one of the most effective theoretical models in the field of representing and reasoning under uncertainty.BNs are applied more frequently recent years in various research areas such as image processing,disease prediction,etc.Learning BNs structure quickly and accurately is important for the BNs structure has a high correlation with the prediction result and learning BNs structure had been proved to be an NP-hard problem.Heuristic search algorithms are widely used in BNs structure learning problems.The main problem of the BNs structure learning algorithm based on Genetic algorithm(GA)is that the executing time is too long,and may easily trap into local optima.When the sample size of data becomes large,stand-alone algorithms cannot get the BNs structure in limited time,and executing each calculation process independently which makes a great number of unnecessary calculations.In this paper,the GA-based BNs structure learning algorithm is studied to solve above problems.Firstly,an efficient knowledge-driven Genetic algorithm(EKGA-BN)is proposed for solving the problems that the convergence speed is slow and the algorithm may easily trap into local optimal under small data volume.Combining with Spark platform,an all-phase GA-based distributed BNs structure learning algorithm is proposed for massive data situation.(1)In order to solve the problems of time-consuming caused by large search space,slow convergence rate and easily trap into local optimal for the existing GA-based learning algorithm,the efficient knowledge-driven GA is proposed.A novel selection operator is used in the proposed EKGA-BN,to keep population diversity in order to learn a BNs structure with higher accuracy.The idea of Hill climbing algorithm(HC)is combined in the selection operator so as to accelerate the convergence rate.In order to enhance the local search ability of EKGA-BN,a novel knowledge-driven mutation procedure is proposed.The correct BN structure information contained by the individuals in the elite set is analyzed so as to guide the local search process.Experiments are carried out for various kinds of small,medium,large,and extreme large models with small data size.The experimental results show the effectiveness of each proposed operator and the superior performance in accuracy,convergence rate and the searching results.(2)In order to solve the problems that long executing time and redundant computations of GA-based BNs structure learning algorithm in massive data situation,and the BN structure low accuracy of existing distributed BN structure learning algorithm.We combine hybrid BNs structure learning algorithm with Spark platform,and propose an all phase distributed GA-based hybrid algorithm(DGA-BN).The all-phase parallelization algorithm includes super structure construction parallelization,score calculation parallelization,and paralleization of GA operators.And Redis is also introduced to store the intermediate data so as to reuse the data efficiently in the process of score calculation,which reduce the redundant calculation time and accelerate the efficiency.Experiments are carried out in the case of massive data with different models.The experimental results show that each proposed operator in DGA-BN is effective,and has superior performance in accuracy and executing time comparing to the traditional algorithm and other new distributed hybrid algorithms.Therefore the proposed DGA-BN provides a new idea for BNs structure learning methods in massive data situation.