基于类间最大间隔多级决策树 报告人：霍建兵

报告内容 基于Large-margin多级决策树的主要思想 进一步的工作

问题的提出 决策树归纳学习以Quinlan1986年提出的ID3算法为代表，由于该方法简单、容易实现而且适用于规模较大的学习问题，现在已经成为归纳学习的一个重要分支。但ID3算法在处理多类问题时效果不太好，所以[1]提出了一种多级决策树的归纳算法思想，其思想是：每一步将多类问题转化成两类问题，分步处理。

多级决策树的主要思想 多级决策树的归纳过程: 首先把多类问题转化为正、反的两类问题，然后生成第一级的决策树； 根据上一步的转化，将数据集划分为正、反两个数据子集； 递归的处理两个子集； 多级决策树的生成过程是一个递归的过程，如果所有的子集都包含一个类别停止。

基于类间间隔的多级决策树 多级决策树归纳过程中，将多类问题转化为两类问题是其中的关键步骤。由于每一个类别都可以划分为正类或者负类，对于一个m类数据集，共有2m-1种划分的方法。并且每一种划分的归纳能力一般是不同的。 因为Margin越大，归纳能力越强[3]，所以我们将Large Margin理论应用到多级决策树中。在每一级遍历所有可能划分方法，选取Margin最大的作为该级决策树的划分方法。 通过Large Margin确定了一种划分，原来的数据集就转化成了一个两类的问题，针对这个两类问题，我们再用传统的决策树方法进行归纳学习，产生第一级决策树。然后递归的产生多级决策树。

进一步的工作 多级决策树的理论基础 和其它的一些算法进行对比研究

理论基础 对于遵守经验风险最小化（ERM）的学习算法，假设空间（用来搜索目标函数的函数空间）越大，越难搜索到目标函数12。从直观上感觉当事例集一定的情况下，类别越多，则假设空间越大，这种方法需要做进一步研究。 据VC维或者算法(Stability)的稳定性16来推导出算法的归纳能力，该方法较难。

和其它算法的对比研究 比较其它多类划分两类启发式算法的效果， 比如： 和其它多类分类器的比较: 1.熵的方法 2.相关性矩阵 Multi-classes classifiers base on SVM

1.熵的方法 遍历所有的划分方法，比较第一个候选属性的信息增益，选取增益最大的作为当前多类问题的确定的划分。 2.相关性矩阵 优缺点：其前两种算法思路简单，计算量小，但 缺点是单一属性决定了属性的划分，没有综合 考虑数据的特点。 3.Multi-classes classifier base on SVM 1-VS-N 1-VS-1 DAGs

谢谢大家！

参考文献 Hongwei Yang,etl. A Decision Tree based on Hierarchy decomposition Quinlan J R. Induction of decision tree, Machine Learning,1986, 1(1): 81-106 V. N. Vapnik, Statistical learning theory, New York, Wiley, 1998, ISBN: 0-471-03003-1 V. N. Vapnik, The Nature of Statistical Learning Theory, Springer-Verlag, New York, 2000, ISBN: 0-387-98780-0 Xizhao Wang, Qiang He, Degang Chen, Daniel Yeung, A genetic algorithm for solving the inverse problem of support vector machines, Science Direct, 2005, 68: 225-238 V. N. Vapnik, An Overview of Statistical Learning Theory, IEEE Transactions on Neural Networks, Vol. 10, No.5, Pages 88 - 999, 1999. Weida Zhou, Li Zhang, Licheng Jiao, Linear programming support vector machines, Pattern Recognition, 2002, 35: 2927-2936. Xizhao Wang, Qiang He, Enhancing Generalization Capability of SVM-Classifiers with Feature Weight Adjustment, Lecture Notes in Computer Science, vol. 3213, pp.1037-1043, 2004, September Tom M. Mitchell. Machine Learning, Beijing: China Machine Press,2003.3 Tomaso Poggio, General conditions for predictivity in learning theory, nature vol 428 419-422 2004.3

Chih-Wei Hsu, Chih-Jen Lin A Comparison of Methods for Multiclass Support Vector Machines, IEEE Transactions on Neural Network, VoL.13, No.2, March 2002, 415-425 J.C.Platt, N. Cristianini, and J.Shawe-Taylor, Large margin DAG’s for multiclass classification, in Advances in Neural Information Processing System. Cambridge, MA: MIT Press, 2000, vol. 12, pp.547-553 E. Mayoraz and E. Alpaydin, “Support vector machines for multi-class classification,” in IWANN, vol. 2, 1999, pp. 833–842. J. Weston and C. Watkins, “Multi-class support vector machines,” presented at the Proc. ESANN99, M. Verleysen, Ed., Brussels, Belgium, 1999. Bousquet, O. & Elisseeff, A. Stability and generalization. J Machine Learn. Res. 2, 499–526 (2001).

Appendix VC维被认为是数学和计算机科学中非常重要的定量化概念，它可用来刻画分类系统的性能.  VC维的直观定义是:对一个指示函数集，如果存在h个样本能够被函数集中的函数按所有可能的2h种形式分开，则称函数集能够把h个样本打散，函数集的VC维就是它能打散的最大样本数目h，若对任意数目的样本都有函数能将它们打散.则函数集的VC维是无穷大。VC维反映了函数集的学习能力，VC维越大则学习机器越复杂，所以VC维又是学习机器复杂程度的一种衡量。

Stability是用来表示某一种算法归纳能力的一系列标准，当算法符合某一种标准时它都有一个从经验风险（训练精度）计算归纳能力的公式 Hypothesis Stability Cross-validation leave-one out (CVloo) Stability CVEEEloo stability

决策森林是多个决策树分类器的融合器，其中的每个决策树分类器地位是平等的，对于每单个决策树，训练集的抽取一般采用bootstrap抽样，测试是采用Max win voting

Multi-classes classifier base on SVM 1-VS-N 1-VS-1 DAGs