基于类间最大间隔理论的多级决策树归纳算法
|
摘要
决策树归纳算法出于其实现简单,归纳能力强而逐渐成为了最常用的机器学习算法之一。但当要处理的问题类别个数增多时,传统的决策树算法由于产生的单一决策树过于复杂,而出现概括能力降低,预测精度下降的问题。针对该问题,本文提出了一种基于类间最大间隔理论的多级决策树归纳算法,多级决策树的主要思想是首先把多类别问题转化成正反两类问题来产生第一级的决策树,然后把正子类再细分为正、反两类来产生第二级的决策树,同理把第一级的反子类也细分为正、反两类来产生第三级的决策树,在第二级的得到的正反两类重复上面的工作,直到把所有类别都分开。本文将最大间隔理论引入到了多级决策树归纳中,以期在每一级划分正反子类时能得到较优的划分。
本文在阐述算法思想和步骤的基础上,通过与传统的决策树算法进行实验对比,得到了如下结论：多级决策树算法能够得到条数较少、概括性更强的规则,从而能够有效提高训练和测试精度。因此,该算法在多类别的分类问题及相关应用领域中具有明显的优势和潜力。
Decision Tree (DT) algorithm has already been one of the most import Machine Learning algorithms because of its simple accomplishment and high generalization ability. However, when DT deals with Multi-classes problems, it will have several problems, such as low generalization ability and testing precision, because the tree generated by DT is so complexity. To cope with this problem, this paper presents a Multi-Stage algorithm based on Large-Margin theory (LMDT). The main idea of LMDT is that firstly the MDT algorithm converts the multi-class problem into two-class problem by large margin learning of SVM hyper-planes, and then for each two-class problem, it uses traditional DT algorithm to generate a decision tree which splits a dataset into two subsets for the further induction. In this paper, we introduce the Large Margin Theory into the induction of Multi-Stage to get splits with good generality in each stage.
In this paper, we first introduce the main idea and detail of the LMDT algorithm, and then with the experimental comparison, we draw the conclusion that LMDT is superior to other algorithm and has good performance, because it not only can get rules with high generalization ability but also has high training and testing precision rate.
本文在阐述算法思想和步骤的基础上,通过与传统的决策树算法进行实验对比,得到了如下结论：多级决策树算法能够得到条数较少、概括性更强的规则,从而能够有效提高训练和测试精度。因此,该算法在多类别的分类问题及相关应用领域中具有明显的优势和潜力。
Decision Tree (DT) algorithm has already been one of the most import Machine Learning algorithms because of its simple accomplishment and high generalization ability. However, when DT deals with Multi-classes problems, it will have several problems, such as low generalization ability and testing precision, because the tree generated by DT is so complexity. To cope with this problem, this paper presents a Multi-Stage algorithm based on Large-Margin theory (LMDT). The main idea of LMDT is that firstly the MDT algorithm converts the multi-class problem into two-class problem by large margin learning of SVM hyper-planes, and then for each two-class problem, it uses traditional DT algorithm to generate a decision tree which splits a dataset into two subsets for the further induction. In this paper, we introduce the Large Margin Theory into the induction of Multi-Stage to get splits with good generality in each stage.
In this paper, we first introduce the main idea and detail of the LMDT algorithm, and then with the experimental comparison, we draw the conclusion that LMDT is superior to other algorithm and has good performance, because it not only can get rules with high generalization ability but also has high training and testing precision rate.
引文
[1]Tom M.Mitchell著.曾华军,张银奎译.机器学习.北京.机械工业出版社.2003.
[2]董彦军.模糊决策树剪枝研究：[工学硕士学位论文].河北大学.2006.
[3]J.R. Quinlan,Induction of decision tree. Machine Leaning,1986,1(1).81-106.
[4]杨宏伟.赵明华,孙娟,王熙照.基于层次分解的决策树.计算机工程与应用.2003,23(3).108-110.
[5]V. N. Vapnik. Statistical learning theory. New York. Springer-Verlag.1998.
[6]V. N. Vapnik. The Nature of Statistical Learning Theory. New York. Springer-Verlag.2000.
[7]Xizhao Wang, Qiang He, Degang Chen, Daniel Yeung. A genetic algorithm for solving the inverse problem of support vector machines. Neuro Computing.2005,68.225-238.
[8](英)克里斯特安尼(Cristianini, N.)等著.李国止,王猛,曾华君等译.支持向量机导论.北京.电子工业出版社.2003.
[9]黄琼英.支持向量机多类分类算法以及应用：[工学硕士学位论文].河北工业大学.2005.
[10]邢红杰 多级支持向量机：[工学硕士学位论文].河北大学,2003.6：20-23.
[11]E. Mayoraz, E. Alpaydin. Support vector machines for multi-class classification. Proceeding of 1WANN,1999,2.833-842.
[12]J. C. Platt. N. Cristianini, J. Shawe-Taylor. Large margin DAG's for multiclass classification. Advances in Neural Information Processing Systems. MIT Press. Cambridge, MA:2000,12:547-553.
[13]Robert Tibshirani, Trevor Hastie. Margin Trees for High-dimensional Classification. Journal of Machine Learning Research.2007,8:637-652.
[14]J. Weston,C. Watkins. Multi-class support vector machines. Proceeding of ESANN99. M. Verleysen. Ed., Brussels, Belgium,1999.
[15]V. N. Vapnik. An Overview of Statistical Learning Theory. IEEE Transactions on Neural Networks, 1999.10(5):88-99.
[16]Hsu Chih-Wei, Lin Chih-Jen. A comparison of methods for multi-class support vector machines. IEEE Transactions on Neural Networks.2002,13(2):415-425.
[17]Jianbing Huo.Xizhao Wang. Mingzhu Lu. Induction of Multi-Stage Decision Trees. Proceedings of the International Conference on System, Man and Cybernetics.2006:835-839.
[18]Jianbing Huo, Hao chen, Mingzhu Lu, Xizhao Wang, Comprehensive Fault Diagnosis Of Power Transformer Based On Multi-Stage Decision Tree, Proceedings of the Fifth International Conference on Machine Learning and Cybernetics. Dalian.2006.
[19]Kristin P. Bennett. Nello Cristianini, John Shawe-Taylor, Donghui Wu. Enlarging the Margins in Perceptron Decision Trees. Machine Learning.2000,41:295-313.
[20]Quinlan. R.. C4.5:Programs for Machine Learning.1993. Morgan Kaufmann, San Mateo.
[21]Shigeo Abe,Takuya Inoue. Fuzzy Support Vector Machines for Multiclass Problems. Proceeding of ESANN'2002. Bruges,Belgium.2002,24(26):113-118.
[22]Yuan.Y, Shaw,M.J. Induction of Fuzzy Decision Trees. Fuzzy Sets and Systems.1995,69:125-139
[23]E. J. Bredensteiner and K. P. Bennett. Multicategory classification by support vector machines. Comput. Optimiz. Applicat..1999:53-79.
[24]E. Mayoraz and E. Alpaydin. Support vector machines for multi-class classification. Proceeding in IWANN.1999,2:833-842.
[25]宋辛科.基于支持矢量机和决策树的多值分类器.计算机工程.2005,31(14)：171-175
[26]路斌,杨建武,陈晓鸥.一种基于SVM的多层分类策略.计算机工程.2005.1,(31)：73-76
[27]刘志刚,李德仁,秦前清,史文中.支持向量机在多类分类问题中的推广.计算机工程与应用.2004,7：10-13.
[28]Hyafil, L. Rivest, R.L. Constructing Optimal Binary Decision Trees. In NP-Complete Information Processing Letters.1976. Vol.5(1):15-17.
[29]Merz, C., Murphy, P. UCI Repository of Machine Learning Databases.1996. Available Online from Ftp://Ftp.Ics.Uci.Edu/Pub/Machine-Learning-Database.
[30]D. Michie, D. J. Spiegelhalter, C. C. Taylor. Machine Learning, Neural and Statistical Classification. 1994. Available online from ftp.ncc.up.pt/pub/statlog/.
[31]E. Osuna, R. Freund, F. Girosi. "Training support vector machines:An application to face detection," in Proc. CVPR'97.1997.
[2]董彦军.模糊决策树剪枝研究：[工学硕士学位论文].河北大学.2006.
[3]J.R. Quinlan,Induction of decision tree. Machine Leaning,1986,1(1).81-106.
[4]杨宏伟.赵明华,孙娟,王熙照.基于层次分解的决策树.计算机工程与应用.2003,23(3).108-110.
[5]V. N. Vapnik. Statistical learning theory. New York. Springer-Verlag.1998.
[6]V. N. Vapnik. The Nature of Statistical Learning Theory. New York. Springer-Verlag.2000.
[7]Xizhao Wang, Qiang He, Degang Chen, Daniel Yeung. A genetic algorithm for solving the inverse problem of support vector machines. Neuro Computing.2005,68.225-238.
[8](英)克里斯特安尼(Cristianini, N.)等著.李国止,王猛,曾华君等译.支持向量机导论.北京.电子工业出版社.2003.
[9]黄琼英.支持向量机多类分类算法以及应用：[工学硕士学位论文].河北工业大学.2005.
[10]邢红杰 多级支持向量机：[工学硕士学位论文].河北大学,2003.6：20-23.
[11]E. Mayoraz, E. Alpaydin. Support vector machines for multi-class classification. Proceeding of 1WANN,1999,2.833-842.
[12]J. C. Platt. N. Cristianini, J. Shawe-Taylor. Large margin DAG's for multiclass classification. Advances in Neural Information Processing Systems. MIT Press. Cambridge, MA:2000,12:547-553.
[13]Robert Tibshirani, Trevor Hastie. Margin Trees for High-dimensional Classification. Journal of Machine Learning Research.2007,8:637-652.
[14]J. Weston,C. Watkins. Multi-class support vector machines. Proceeding of ESANN99. M. Verleysen. Ed., Brussels, Belgium,1999.
[15]V. N. Vapnik. An Overview of Statistical Learning Theory. IEEE Transactions on Neural Networks, 1999.10(5):88-99.
[16]Hsu Chih-Wei, Lin Chih-Jen. A comparison of methods for multi-class support vector machines. IEEE Transactions on Neural Networks.2002,13(2):415-425.
[17]Jianbing Huo.Xizhao Wang. Mingzhu Lu. Induction of Multi-Stage Decision Trees. Proceedings of the International Conference on System, Man and Cybernetics.2006:835-839.
[18]Jianbing Huo, Hao chen, Mingzhu Lu, Xizhao Wang, Comprehensive Fault Diagnosis Of Power Transformer Based On Multi-Stage Decision Tree, Proceedings of the Fifth International Conference on Machine Learning and Cybernetics. Dalian.2006.
[19]Kristin P. Bennett. Nello Cristianini, John Shawe-Taylor, Donghui Wu. Enlarging the Margins in Perceptron Decision Trees. Machine Learning.2000,41:295-313.
[20]Quinlan. R.. C4.5:Programs for Machine Learning.1993. Morgan Kaufmann, San Mateo.
[21]Shigeo Abe,Takuya Inoue. Fuzzy Support Vector Machines for Multiclass Problems. Proceeding of ESANN'2002. Bruges,Belgium.2002,24(26):113-118.
[22]Yuan.Y, Shaw,M.J. Induction of Fuzzy Decision Trees. Fuzzy Sets and Systems.1995,69:125-139
[23]E. J. Bredensteiner and K. P. Bennett. Multicategory classification by support vector machines. Comput. Optimiz. Applicat..1999:53-79.
[24]E. Mayoraz and E. Alpaydin. Support vector machines for multi-class classification. Proceeding in IWANN.1999,2:833-842.
[25]宋辛科.基于支持矢量机和决策树的多值分类器.计算机工程.2005,31(14)：171-175
[26]路斌,杨建武,陈晓鸥.一种基于SVM的多层分类策略.计算机工程.2005.1,(31)：73-76
[27]刘志刚,李德仁,秦前清,史文中.支持向量机在多类分类问题中的推广.计算机工程与应用.2004,7：10-13.
[28]Hyafil, L. Rivest, R.L. Constructing Optimal Binary Decision Trees. In NP-Complete Information Processing Letters.1976. Vol.5(1):15-17.
[29]Merz, C., Murphy, P. UCI Repository of Machine Learning Databases.1996. Available Online from Ftp://Ftp.Ics.Uci.Edu/Pub/Machine-Learning-Database.
[30]D. Michie, D. J. Spiegelhalter, C. C. Taylor. Machine Learning, Neural and Statistical Classification. 1994. Available online from ftp.ncc.up.pt/pub/statlog/.
[31]E. Osuna, R. Freund, F. Girosi. "Training support vector machines:An application to face detection," in Proc. CVPR'97.1997.