Research On Bayesian Network With Tree Structure Based On Directed Graph

In the domain of Data Mining, classification is a very important technology. Restricted Bayesian classifiers increase corresponding restricted conditions for normal Bayesian classifiers to solve the problem that learning an optimal Bayesian network is NP-hard. Tree augmented naive Bayes classifier is a typical learning method, and has good classification performation even though its learning structure is simple. Restricted Bayesian classifiers have been one of the most hotspots in classification technology research area.This paper first introduces the concept of classification and relevant technologies, then describes some algorithms of restricted Bayesian classifiers, especially analyses the theoretical basis and classifier's structure of Naive Bayes, TAN, HCS and SP. On the other hand, in the course of building the TAN classifier, the problem about optimal spanning trees has been involved. So we expound the algorithms for optimal spanning trees of a graph and their possible applications in Bayesian classifier. Based on the works above, we propose a new method to build TAN classifier. Firstly, according to the information theory, we analyse the means to reflect the dependence relation between attributes, introduce the production of mutual information and proposed a new unsymmetrical function to reflect the dependence relation. Secondly, a directed graph is built according to this function between attributes. We utilize Edmonds algorithm to get an optimal spanning tree of the graph, which is used as an initialized structure for the new classifier. In the end, a heuristic searching methods which is called IP is proposed to modify the structure. We introduce the new algorithm in detail and compute it's time complexity. In the course of experiments, we build two new classifiers: MTAN and DTAN. MTAN is gained by applying the new function to reflect the influence attributes. DTAN is attained by applying IP algorithm on MTAN. The comparison of TAN and MTAN test the new function, and the comparison of SP and DTAN is used to test the new heuristic searching methods IP.