Research On Bayesian Network Structure Learning Based On K2 Algorithm

Bayesian network is a graph model that combines probability theory with graph theory,which significantly reduces the difficulty of uncertainty knowledge expression and reasoning.It is currently widely used in image processing,industrial fault diagnosis,medical diagnosis and information retrieval,etc.Domain is one of the powerful tools for dealing with uncertain information.Bayesian network learning is divided into parameter learning and structural learning.Among them,the structural learning part is the focus of more research by researchers.The method of manually constructing the network structure by experts relying on domain knowledge becomes infeasible as the number of nodes increases and the network becomes more complex.Therefore,how to automatically learn the Bayesian network structure from the known data in a reasonable time is a difficult problem in current research,and it is also a NP-hard problem.K2 algorithm is a classic Bayesian network structure learning algorithm,which can effectively reduce the search space,reduce the time complexity of calculation,and can learn a more accurate Bayesian network structure,but the algorithm strongly depends on the priori The quality of the node sequence,inaccurate prior sequences will lead to the learning of the wrong Bayesian network structure,which directly affects the learning performance.Therefore,in order to improve the accuracy and stability of the K2 algorithm,two improved heuristic Bayesian network learning algorithms based on the K2 algorithm are proposed,which can automatically learn a relatively accurate node sequence within a reasonable time to obtain a high-quality structural model.The main work of this paper is as follows:(1)Aiming at the order dependence problem of K2 algorithm,a heuristic Bayesian network structure learning method H-vn K2 based on v-structure and neighbor set is proposed,which can effectively learn variable order from a given dataset.Specifically,first use the improved version of causal effect to obtain the node priority sequence,and use it as the initial sequence;based on the v-structure knowledge learned by the PC algorithm,quickly and accurately correct the order of some parent and child nodes,and obtain the optimal order of some nodes;Based on the neighbor set knowledge learned by the PC algorithm,the order of the parent and child nodes is further modified from the global optimal angle with the distance threshold heuristic strategy,and the optimal order of all nodes is obtained;Finally,take the optimal node sequence as the prior node sequence,and use the K2 algorithm to obtain the Bayesian network structure.Experiments show that the proposed algorithm significantly outperforms the comparison algorithms on standard dataset networks.(2)Since the distance threshold adjustment strategy of the H-vn K2 algorithm adopts a fixed value,there are some cases where the error node sequence does not reach the threshold and is not detected.In order to further improve the accuracy,a more accurate Bayesian network structure is obtained.Based on the H-vn K2 algorithm,this paper proposes an improved K2 learning method TSK2 that combines variable neighbor sets and v-structure information.Specifically,inspired by the orientation rules of the constraint algorithm,the method reliably adjusts the in-order position of the neighbors of the sink with the help of the identified vstructure and neighbor set information;Secondly,inspired by the basic structure of the shell net,with the help of the variable neighbor set information,the optimal sequence is obtained by performing the search of the three basic structures of shun-connection,sub-connection,and confluence-connection to accurately correct the order positions of parent nodes and child nodes.The experimental results show that compared with the H-vn K2 algorithm,the proposed new algorithm has better learning performance and can learn the Bayesian network structure more accurately.