Research On Improvement Of Byesian Networks Structure Learning Algorithm

Bayesian network is an important knowledge representation and reasoning tool under uncertain conditions. Currently that learning a Bayesian network from data is an important problem has become a hotspot. Tsamardinos presented a new algorithm for Bayesian network structure learning, called Max-Min Hill-Climbing (MMHC). It outperforms on average and in terms of various metrics several prototypical and state-of-the-art algorithms. However, there are some problems with MMHC algorithm.On the basis of the research and analysis of the problems of MMHC algorithm, this dissertation presents improved algorithms to solve problems found in MMHC algorithm. The details are given as follows.1. This dissertation analyses the problems of BDeu scoring, apply and evaluate several widely used scoring metrics of Bayesian network such as MIT, K2, BDeu and MDL to MMHC algorithm. Detailed results of a complete experiment show that the K2 scoring in this algorithm is the best, generally better than BDeu scoring. MMHC algorithm uses K2 scoring to improve the performance of algorithm effectively. 2. MMHC algorithm uses a greedy search, but it is easy to get into the local optimum. In order to overcome this shortcoming, an improved algorithm was proposed. The algorithm applied Simulated Annealing, Random Repeated Hill-Climbing Search, and Tabu Search instead of Greedy search to improve efficiency. Detailed results of a complete experiment show that these three search algorithm is generally superior to greed search, Simulated Annealing is the best.3. Such a procedure might fail to find a high-scoring network: a misguided choice of candidate parents and children in the first phase of MMHC algorithm can lead to a low scoring network in the second phase. In order to overcome this shortcoming, an improved algorithm was proposed. Experimental results show that this improvement to improve performance of algorithm effectively.