Bayesian Network Structure Learning Algorithm Based On Ant Colony Optimization

Bayesian networks are network models for representing the dependent and independent relationships among random variables. Because of their clear structure and well-defined semantics, they become important theoretical models for solving uncertainty knowledge representation and inference. Bayesian networks have been applied in the fields such as machine learning, equipment fault diagnosis, failure prediction, and have achieved a great success. But it is usually difficult to construct a Bayesian network by only using expert knowledge, and sometimes it is even impossible. Therefore it is of great theoretical significance and application value to quickly and accurately learn Bayesian network structures from data.Two improved algorithms are proposed in this paper based on the study of ant colony optimization and the current structure learning algorithms, and the main results consist of the following three parts:Firstly, it is trivial to find the essential graph of a Bayesian network structure, and a combined algorithm is presented for constructing the essential graph of a Bayesian network. The algorithm starts from the initial directed acyclic graph, firstly sorts all the directed edges, then keeps the edges participating in V-structures unchanged and transforms others into undirected edges, and finally determines the orientation of all undirected edges in the essential graph with respect to the three rules successively. The correctness of the method is proven and the validity of the algorithm is analyzed in the case at last, which is of great significance for constructing Bayesian network structures in the space of equivalence classes.Secondly, an improved greedy search algorithm I-GREEDY-E is proposed based on mutual information and greedy search. This algorithm builds the initial skeleton using mutual information, then refines the initial skeleton by employing the maximum spanning tree algorithm, and orients edges according to conditional independence tests. Finally the optimal network structure could be obtained using greedy search. Numerical experiments show that, I-GREEDY-E algorithm has some improvements both in BIC score and structure error compared with GREEDY-E algorithm.Finally, an ant colony algorithm I-ACO-E is depicted based on mutual information by combining mutual information theory and ant colony optimization. This algorithm constructs the initial undirected graph using mutual information, then orients undirected edges based on conditional independence tests, and finally ant colony search algorithm is performed to explore the optimal structure. The results of testing show that the improved algorithm has strong ability to solve large scale networks efficiently, and it also has a better solution quality compared with recent methods.