Research On Bayesian Network Structure Learning Algorithms

Bayesian network (BN) is an important method for presenting causality and uncertainty among random variables based on graphical model theory and statistics. It can effectively reason under uncertainty and take decisions. During the last two decades, many BN learning algorithms have been proposed. Although encouraging results have been reported, the two approaches both suffer some difficulties in accuracy and efficiency on limited datasets or high dimensional datasets. To further enhance learning accuracy or efficiency, this dissert presents the following contributions:1) Max-Relevance and Min-Redundancy greedy (MRMRG) BN learning algorithmsGiven an ordering among nodes, MRMRG algorithm is an variant of K2 algorithm for learning BN on high dimensional and small datasets. MRMRG algorithm applies Max-Relevance and Min-Redundancy (MRMR) feature selection technology and proposes Local Bayesian Increment (LBI) function. Experimental results show that MRMRG algorithm has much better accuracy than K2 algorithm on high dimensional and small datasets.With no ordering constraint, an ordering based heuristic search approach is applied, a novel method generating candidate parents set is proposed and a new MRMRG algorithm is presented, called Ordering-based Max-Relevance and Min-Redundancy Greedy (OMRMRG). At the same time, OMRMRG algorithm also uses MRMR technology and LBI function. Experimental results show that OMRMRG algorithm has much better accuracy than traditional algorithms on high dimensional and small datasets.2) Ensemble based Bayesian network learning algorithmsEnsemble learning approach is incorporated into BN learning algorithms. Two novel ensemble based BN learning algorithms are proposed. More accurate Bayesian networks are acquired by both of the algorithms.One algorithm is called Additive Sampling based BN Ensemble Learning. Based on the Markov condition of BN learning, root nodes based additive sampling method and relative components integration method are proposed.The other algorithm is called Sample Decomposition based BN Ensemble learning. Based on the Markov condition, root nodes based sample decomposition method and relative components integration technology are proposed.The experimental results reveal that ensemble based BN learning methods can achieve improved results compared with individual BN learning algorithms in terms of accuracy on limited datasets.3) Frequent Itemsets based BN learning algorithmA new frequent itemsets mining algorithm is proposed, called Heuristic Two Level Counting based Frequent Itemsets Mining (FIM-HTLC). FIM-HTLC algorithm introduces a novel support counting method, Heuristic Two Level Counting (HTLC), which reduces the number of passes over datasets to a half. FIM-HTLC algorithm also applies an heuristic traversal technology which speeds up one pass over datasets. The experimental results confirm that FIM-HTLC algorithm is much faster than Apriori algorithm on sparse and large datasets.A frequent itemsets based BN learning algorithm is proposed. This algorithm exploits frequent itemsets to limit the searching space of possible Bayesian networks and enhance the efficiency of searching. This algorithm is often used to learn BNs on high dimensional, sparse and large datasets. The experimental results show that this algorithm is more efficient than traditional BN learning algorithms on high dimensional, sparse and large datasets.4) Preliminary research on the application of BN in communication field A research on customer churning problem was performed. A preliminaryBN prediction model for actively churning customer is proposed.