The Learning and Optimizing of Markov Network Classifiers Based on Dependency Analysis
WANG ShuangCheng1,2, LIU XiHua3, TANG HaiYan1,2
1.Department of Information Science, Shanghai Lixin University of Commerce, Shanghai 201620 2.Risk Management Research Institute, Shanghai Lixin University of Commerce, Shanghai 201620 3.Economic Institute, Qingdao University, Qingdao 266071
Abstract：To decomposable probability model, it is proved that the Markov network classifier is optimal under zeroone loss. At present, the algorithms of learning the structure of Markov network classifier are inefficient and unreliable. In this paper, a new method of learning the structure of Markov network classifier is presented. The classifier structure is built by combining basic dependency relationship between variables, basic structure between nodes and the idea of dependency analysis. And Markov network classifier is optimized by removing unrelated and redundancy attribute variables to improve the ability of withstanding noise and predicting. A contrast experiment about the accuracy of classifiers is done by using artificial and real data. Experimental results show high classing accuracy of optimized Markov network classifier.
王双成，刘喜华，唐海燕. 基于依赖分析的马尔科夫网络分类器学习与优化*[J]. 模式识别与人工智能, 2006, 19(4): 485-490.
WANG ShuangCheng, LIU XiHua, TANG HaiYan. The Learning and Optimizing of Markov Network Classifiers Based on Dependency Analysis. , 2006, 19(4): 485-490.
[1] Ramoni M, Sebastiami P. Robust Bayes Classifiers. Artificial Intelligence, 2001, 125(1-2): 209-226 [2] Friedman N, Geiger D, Goldszmidt M. Bayesian Network Classifiers. Machine Learning, 1997, 29(2-3): 131-163 [3] Pearl J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. San Mateo, USA: Morgan Kaufmann, 1988, 117-133 [4] Wong M L, Lam W, Leung K S. Using Evolutionary Programming and Minimum Description Length Principle for Data Mining of Bayesian Networks. IEEE Trans on Pattern Analysis and Machine Intelligence, 1999, 21(2): 174-178 [5] Xiang Y, Wong S K M, Cercone N. A Microscopic Study of Minimum Entropy Search in Learning Decomposable Markov Networks. Machine Learning, 1997, 26(1): 65-92 [6] Karger D, Srebro N. Learning Markov Networks: Maximum Bounded Tree-Width Graphs. In: Proc of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. Washington, USA, 2001, 392-401 [7] Zhang Z, Yeung R W. A Non-Shannon-Type Conditional Inequality of Information Quantities. IEEE Trans on Information Theory, 1997, 43(6): 1982-1986 [8] Yeung R W, Zhang Z. On Characterization of Entropy Function via Information Inequalities. IEEE Trans on Information Theory, 1998, 44(4): 1440-1452 [9] Wang S C, Yuan S M, Wang H. Learning Markov Blanket Prediction Based on Bayesian Network. Pattern Recognition and Artificial Intelligence, 2004, 17(1): 17-21 (in Chinese) (王双成, 苑森淼, 王 辉. 基于贝叶斯网络的马尔科夫毯预测学习. 模式识别与人工智能, 2004, 17(1): 17-21) [10] Wang S C, Yuan S M. Research on Learning Bayesian Networks Structure with Missing Data. Journal of Software, 2004, 15(7): 1042-1048 (in Chinese) (王双成, 苑森淼. 具有丢失数据的贝叶斯网络结构学习研究. 软件学报, 2004, 15(7): 1042-1048) [11] Wang S C, Yuan S M. Learning Decomposable Markov Network Structure with Missing Data. Chinese Journal of Computers, 2004, 27(9): 1221-1228 (in Chinese) (王双成, 苑森淼. 具有丢失数据的可分解马尔科夫网络结构学习. 计算机学报, 2004, 27(9), 1221-1228) [12] Cheng J, Greiner R, Kelly J, et al. Learning Bayesian Networks from Data: An Information-Theory Based Approach. Artificial Intelligence, 2002, 137 (1-2): 43-90 [13] Chickering D M. Learning Equivalence Classes of Bayesian Network Structures. Machine Learning, 2002, 2(3): 445-498 [14] Tarjan R E, Yannakakis M. Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs. SIAM Journal on Computing, 1984, 13(3): 566-579 [15] Gamberger D, Lavrac N. Conditions for Occam’s Razor Applicability and Noise Elimination. In: Proc of the 9th European Conference on Machine Learning. Prague, Czech Republic, 1997, 108-123 [16] Murphy P M, Aha D W. UCI Repository of Machine Learning Databases. 1994. http: //www. ics. uci. edu/~mlearn/ MLRepository. html [17] Kohavi R. A Study of Cross-Validation and Bootstrap for Accuracy Estimation and Model Selection. In: Proc of the 14th International Joint Conference on Artificial Intelligence. San Mateo, USA: Morgan Kaufmann, 1995, 1137-1143
2006, Vol. 19 
