Research On Structure Learning Of Bayesian Classifier Based On Genetic Algorithms

In the past twenty years, world economic make the rapid development of information technique and widely application of Internet , we have higher and higher capability to collect data, which make us to collect and deal more and more data. By the challenge of "rich data and poor information", Data Mining and Knowledge Discovery technology be emerged as the times require and vigorous developed to more and more powerful vitality. Classify is a very important task of Data Mining, its purpose is to find out classify function or classify model. At present classify measures are mainly some machine learning methods, Such as decision-tree method, role-induce method, neural network method, genetic algorithm, ant algorithms and so on. Among these classify methods, Bayesian Network, as an effect way for knowledge representation and probability reason model, is a powerful decision analysis tool dealing with graph of uncertain information. With firm theory foundation, natural knowledge denotation, flexible reasoning ability and convenient decision-making mechanism, it attach importance to more and more people. In recent years Data Mining based on BN has made good effects. It is a research hotspot. Bayesian method is developed as system express and settle statistics problem based on Bayesian theory. Bayesian Network used in classification is called Bayesian Classifier, which is a special form of Bayesian Network for that both variable-choosing and state number have been decided with attribute nodes given and class node unknown. Bayesian Classifier family has three common classifiers: NBC, TANC and BNC. The learning for Bayesian Classifier includes structure learning and parameter learning and inference class node of MAP. Complete Bayesian Networks learning is NP-hard. Many researchers learn Bayesian Networks using approximate methods. Duda put forwards NB structure; Friedman put forwards TAN structure; Keogh put forwards SP structure; Huajie Zhang put forwards SN structure; Cheng put forwards BAN and GBN structure; Shi Hong-bo optimizes TAN structure. They obtain good effects in Bayesian Classifier. How to learn excellent structure in short time is an important problem of relative researchs. Genetic algorithm is a self-organizing and adaptive artificial intelligence technique, it simulates natural evolutin process and mechanism to solve extremum problem. It comes from Darwinian's natural evolution theory and Mendelian's genetic theory with stable biology foundation. Genetic algorithm is a global search optimize algorithm, it can get the best global solution. Apply Genetic algorithm into structure learning of Bayesian networks is goal of this dissertation. The main works of this paper is as follows: ⑴Generalize and summarize main frame of Bayesian Networks. Discuss Bayesian Networks structure learning algorithm in brief. ⑵We download many kinds of Bayesian Networks software package(JavaBayes, Hugin, MSBNx, BayesBuilder, etc). Basing these BN software package, we use BNT(BN Toolkit) software package as prototype and On MBNC (Bayesian Networks Classifier using MATLAB) experimental platform which constructed by Cheng Ze-kai etc . We can pretreat data, test structure learning and parameter learning algorithm for Bayesian Classifier and realized Bayesian Classifier based on genetic algorithms, constructed algorithms module of MBNC. (3) In order to introduce Genetic algorithm into Bayesian networks structure learning, we've investigated Genetic Algorithms and programming Genetic Algorithms use MATLAB based on integer coding for solving traveling salesman problem;It is very important in theories and applications to design high quality genetic algorithms programs. The research on Genetic Algorithms is a hotspot in recent years. This paper investigates select operators, cross operators, mutation operators based on integer coding, and applies it for solving Traveling Salesman Problem. Make cross probability and mutation probability adaptive in programs write by MATLAB, Experimental result shows that this algorithm can get a better result. (4) Structure Learning of TANC Based on BIC and Genetic Algorithms。Tree Augmented Na?ve Bayesian Classifier (TANC) is a type of quite applied classifier, its performance is superior to Na?ve Bayesian Classifier. Existing TANC structure learning algorithms are based on relativity analysis using mutual information criterion or based on search & scoring using Bayesian information criterion. Using BIC as evaluate function, this paper introduces Genetic algorithm into TANC structure learning, and proposes a new TANC structure learning algorithm based on BIC and Genetic algorithm. Using classification accuracy to scale classification performance. Experiment results show that GA-TANC is accurate and effective. (5) Structure Learning of BNC Based on K2 and Genetic Algorithms。Structure Learning of Bayesian Networks Classification is a NP hard problem. K2 algorithm is an effective and high veracity method,but it requires giving the order of nodes first. In order to find out the best order of nodes, an algorithm is proposed based on K2 and Genetic algorithms. Integer coding is induced in structure learning of Bayesian networks classification,it provides guarantee of get the best order of nodes and convergence of Bayesian networks. Experimental result shows that this algorithm is better than using K2 algorithm only with random order of nodes,it is accurate and valid. (6) Structure Learning of BNC Based on BIC and Hybrid Genetic Algorithms。Structure Learning of Bayesian Networks Classification is a NP hard problem. Greed search algorithm is an effective and high veracity method, but it is easy to get into the local best . Standard genetic algorithm is a global search optimal algorithm, which simulates the proceeding of natural evolution and can get the global best. But its individual can't provides guarantee of get the local best. An algorithm is proposed to combine these two algorithms with BIC as evaluate function, which can get better effect. Experimental result shows that this algorithm is better than using GS algorithm only, it is accurate and effective.