论文部分内容阅读
摘要：支持向量机（Support Vector Machine， SVM）是一种基于统计学习理论的机器学习方法，由于其出色的学习性能，早已成为当前机器学习界的研究热点；而决策树是一种功能强大且相当受欢迎的分类和预测工具。本文重点介绍支持向量机与决策树结合解决多分类问题的算法，并对其进行评析和总结。
关键词：支持向量机；决策树；多分类；SVMDT
中图法分类号：TP39文献标识码：A 文章编号：1009-3044(2008)08-10ppp-0c
1 引言
基于数据的机器学习是现代智能技术中的重要方面。通过对已知事实的分析总结出规律，预测不能直接观测的事实，即利用学习得到的规律，不但可以较好地解释已知的实例，而且能够对未来现象或无法观测的现象做出正确的预测和判断，我们把这种能力叫做推广能力。在人们对机器智能的研究中，一直希望能够用机器（计算机）来模拟这种学习能力，就是我们所说的基于数据的机器学习，或简单的称为机器学习问题 。机器学习这门学科所关注的问题是：计算机程序如何随着经验积累自动提高性能 。统计学在解决机器学习问题中起着基础性的作用。传统统计学研究的是样本数目趋于无穷大时的渐近理论 ，现有的学习方法也多是基于此假设。但在实际问题中，样本数往往是有限的，因此一些理论上很优秀的学习方法实际中表现却可能不尽人意。与传统统计学相比，统计学习理论(Statistical Learning Theory，SLT)是一种专门研究小样本情况下机器学习规律的理论 。Ｖ.Vapnik 等人从六、七十年代开始致力于此方面研究，为解决有限样本学习问题提供了一个统一的框架；同时，在统计学习理论基础上发展了一种新的通用学习方法——支持向量机(Support Vector Machine，SVM)3，它已初步表现出很多优于已有方法的性能。曾有学者认为，SLT和SVM 正成为继神经网络研究之后新的研究热点，并将有力地推动机器学习理论和技术的发展。
决策树通过把样本从根结点排列到某个叶子结点来分类，叶子结点即为样本所属的分类类别。其思路是找出最有分辨力的属性，把样本集划分为许多子集（对应树的一个分枝），构成一个分枝过程，然后对每一个子集递归调用分枝过程，直到所有子集包含同一类型的样本。最后得到的决策树能对新的样本进行分类。
本文通过对支持向量机在多分类方面的推广，引入决策树的研究，阐述SVM与决策树相结合解决多分类问题的方法。本文内容安排如下：第二节支持向量机，概述支持向量机，探讨SVM在多分类方面的推广，分析现有算法；第三节决策树的研究，介绍决策树的历史与发展；第五节支持向量机决策树，重点讨论将SVM与决策树结合的算法；最后总结。
2 支持向量机相关介绍
2.1 支持向量机（Support Vector Machine，SVM）
V. Vapnik提出的支持向量机理论因其坚实的理论基础和诸多良好特性在近年获得了广泛的关注。已经有许多事实证明，作为支持向量机最基本思想之一的结构化风险最小化原则（Structural Risk Minimization, SRM ）要优于传统的经验风险最小化原则（Empirical Risk Minimization, ERM）。不同于ERM试图最小化训练集上误差的做法，SRM试图最小化VC维的上界，从而使其学习机获得了更好的推广性能，这恰恰是统计学习理论最重要的目标之一。
SVM的优势在于其方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性(即对特定训练样本的学习精度，Accuracy)和学习能力(即无错误地识别任意样本的能力)之间寻求最佳折衷，以期获得最好的推广能力(Generalizatin Ability) 2。支持向量机方法的几个主要优点是：可以解决小样本情况下的机器学习问题；可以提高泛化性能；可以解决高维问题；可以解决非线性问题；可以避免神经网络结构选择和局部极小点问题 。
2.2 多类支持向量机
然而，最初研究的SVM是用来解决二分类问题，并不能直接运用在多分类方面，如何有效地将其推广到多类分类问题还是一个正在研究的问题。当前已经有算法将SVM推广到多类分类问题，这些算法统称为“多类支持向量机”(Multi-Category Support Vector Machines，M-SVMs) 。它们可以大致分为两大类：其一，是Weston 在1998年提出的基于改进目标函数的多类分类算法，即将多个分类面的参数求解合并到一个最优化问题中，通过求解该最优化问题“一次性”地实现多类分类；其二，通过某种方式构造一系列的两类分类器并将它们组合在一起来实现多类分类。第一类方法尽管看起来简洁，但是在最优化问题求解过程中的变量远远多于第二类方法，训练速度不及第二类方法，而且在分类精度上也不占优势。当训练样本数非常大时，这一问题更加突出。正因如此，第二类方法更为常用。这类方法目前主要有四种分支算法：1对多算法、1对1算法、DAGSVM有向无环图以及ECOC纠错码。
这些方法虽然具有理论依据，但存在一个最优化问题，导致在训练过程中会耗费大量的时间，所以并没有得到很好的应用，只有1对1算法和DAGSVM有向无环图在实际中应用较多。由于1对多SVMs和1对1 SVMs对未知样本分类时需要使用所有的分类器，且分类结果与分类器使用顺序无关，因此它们的组合方式是唯一的。DAGSVM中的有向无环图的组合方式有很多种，但实验证明组合变化对分类结果影响不大。并且DAGSVM和ECOC的测试次数至少是N次，所以当类别很多时将不能很好的应用。
同时，在将多类问题转化为两类问题求解时，往往会出现无法分类区(未知区或重叠区)，可以用一个简单的三类例子来说明，如图1所示。图1(a)中使用1对多算法分类，每次判定全部样本集中的模式属于或不属于某一类；图1(b)中采用1对1算法分类，每次只取样本集中两类模式样本进行分类。这两种方法都会产生图1(a)、 图1(b)所示的阴影区，在这个区域中的模式样本，要么无法确定它们的类别，要么属于多个类别，总之，无法将其唯一判至某类，从而出现拒识。
图1 无法分类区域示意图
3 决策树简介
决策树起源于概念学习系统（Concept Learning System，CLS）的研究 ，但CLS的不足是它处理的学习问题不能太大。为此，20世纪70年年代末期Quinlan 提出了著名的ID3学习算法，它采用信息增益作为启发策略，通过选择窗口来形成决策树 。ID3算法的核心是：在决策树各级结点上选择属性时，用信息增益（information gain）作为属性的选择标准，以使得在每一个非叶结点进行测试时，能获得关于被测试记录最大的类别信息。其具体方法是：检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类，如图2所示。ID3算法的优点是：算法的理论清晰，方法简单，学习能力较强。其缺点是：只对比较小的数据集有效，且对噪声比较敏感，当训练数据集加大时，决策树可能会随之改变。
图3 类距离法示意图
5 总结
目前支持向量机已经得到普遍的认识和广泛的应用，而决策树算法也已经有了广泛的应用， 并且有了许多成熟的系统， 这些系统广泛应用于各个领域， 如语音识别， 模式识别， 专家系统等。但是， 解决一个复杂的数据挖掘问题的任何算法都要面临以下问题： 从错误的数据中学习、从分布的数据中学习、从有偏的数据中学习、学习有弹性的概念、学习那些抽象程度不同的概念、整合定性与定量的发现等， 归纳学习当中还有很多未开发的课题等待我们去研究。
并且我们始终要牢记一点，没有一个分类方法在对所有数据集上进行分类学习均是最优的，所以怎样使得算法尽可能的提高训练速度，减少分类错误，增加泛化性能是我们下一步的工作。
参考文献：
[1]V.Vapnik,著.张学工,译.统计学习理论的本质[M].北京:清华大学出版社,2000.
[2]Tom M.Mitchell,著.曾花军,张银奎,等.译.机器学习[M].北京:机械工业出版社,2003.
[3]V.Vapnik,著.许建华,张学工,译.统计学习理论[M].北京:电子工业出版社,2004.
[4]张学工.关于统计学习理论与支持向量机[J].自动化学报,2000,26(1):32-42．
[5]张浩然,汪晓东.支持向量机的学习方法综述[J].浙江师范大学学报（自然科学版）,2005,28(3):283-287.
[6]刘志刚,李德仁,秦前清,等.支持向量机在多类分类问题中的推广[J].计算机工程与应用,2004,40(7):10-13.
[7]Weston J,Watkins C.Multi-class support vector machines. Royal Holloway College, Tech Rep: SCD-TR-98-04,1998.
[8]Earl B．Hunt, Janet Marin, Philip J．Stone. Experiments in Induction[M].Academic Press,New York,1966.
[9]J.Ross Quinlan.Induction of decision trees[J].Machine Learning,1986,(1):81-106.
[10]Paul E,Utgoff.Incremental induction of decision trees[J]Machine Learning,1989,4(2):161-186.
[11]J.Ross Quinlan. C4.5: Programs for Machine Learning[M].Academic Press,New York,1993.
[12]Fumitake Takahashi,Shigeo Abe. Decision-Tree-Based Multi-class Support Vector Machines [A].Proceeding of ICONIP’02[C], Singapore:IEEE Press,2002.1419-1422.
[13]Scott Selikoff,The SVM-Tree Algorithm: A New Method for Handling Multi-Class SVMs. Cornell University,2003.
[14]Jin-Seon Lee, II-Seok Oh. Binary classification trees for multi-class classification prooblems[M].IEEE, 2003: 770-774.
[15]唐发明,王仲东,陈绵云.一种新的二叉树多类支持向量机算法[J].计算机工程与应用,2005,41(7):24-26.
关键词：支持向量机；决策树；多分类；SVMDT
中图法分类号：TP39文献标识码：A 文章编号：1009-3044(2008)08-10ppp-0c
1 引言
基于数据的机器学习是现代智能技术中的重要方面。通过对已知事实的分析总结出规律，预测不能直接观测的事实，即利用学习得到的规律，不但可以较好地解释已知的实例，而且能够对未来现象或无法观测的现象做出正确的预测和判断，我们把这种能力叫做推广能力。在人们对机器智能的研究中，一直希望能够用机器（计算机）来模拟这种学习能力，就是我们所说的基于数据的机器学习，或简单的称为机器学习问题 。机器学习这门学科所关注的问题是：计算机程序如何随着经验积累自动提高性能 。统计学在解决机器学习问题中起着基础性的作用。传统统计学研究的是样本数目趋于无穷大时的渐近理论 ，现有的学习方法也多是基于此假设。但在实际问题中，样本数往往是有限的，因此一些理论上很优秀的学习方法实际中表现却可能不尽人意。与传统统计学相比，统计学习理论(Statistical Learning Theory，SLT)是一种专门研究小样本情况下机器学习规律的理论 。Ｖ.Vapnik 等人从六、七十年代开始致力于此方面研究，为解决有限样本学习问题提供了一个统一的框架；同时，在统计学习理论基础上发展了一种新的通用学习方法——支持向量机(Support Vector Machine，SVM)3，它已初步表现出很多优于已有方法的性能。曾有学者认为，SLT和SVM 正成为继神经网络研究之后新的研究热点，并将有力地推动机器学习理论和技术的发展。
决策树通过把样本从根结点排列到某个叶子结点来分类，叶子结点即为样本所属的分类类别。其思路是找出最有分辨力的属性，把样本集划分为许多子集（对应树的一个分枝），构成一个分枝过程，然后对每一个子集递归调用分枝过程，直到所有子集包含同一类型的样本。最后得到的决策树能对新的样本进行分类。
本文通过对支持向量机在多分类方面的推广，引入决策树的研究，阐述SVM与决策树相结合解决多分类问题的方法。本文内容安排如下：第二节支持向量机，概述支持向量机，探讨SVM在多分类方面的推广，分析现有算法；第三节决策树的研究，介绍决策树的历史与发展；第五节支持向量机决策树，重点讨论将SVM与决策树结合的算法；最后总结。
2 支持向量机相关介绍
2.1 支持向量机（Support Vector Machine，SVM）
V. Vapnik提出的支持向量机理论因其坚实的理论基础和诸多良好特性在近年获得了广泛的关注。已经有许多事实证明，作为支持向量机最基本思想之一的结构化风险最小化原则（Structural Risk Minimization, SRM ）要优于传统的经验风险最小化原则（Empirical Risk Minimization, ERM）。不同于ERM试图最小化训练集上误差的做法，SRM试图最小化VC维的上界，从而使其学习机获得了更好的推广性能，这恰恰是统计学习理论最重要的目标之一。
SVM的优势在于其方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性(即对特定训练样本的学习精度，Accuracy)和学习能力(即无错误地识别任意样本的能力)之间寻求最佳折衷，以期获得最好的推广能力(Generalizatin Ability) 2。支持向量机方法的几个主要优点是：可以解决小样本情况下的机器学习问题；可以提高泛化性能；可以解决高维问题；可以解决非线性问题；可以避免神经网络结构选择和局部极小点问题 。
2.2 多类支持向量机
然而，最初研究的SVM是用来解决二分类问题，并不能直接运用在多分类方面，如何有效地将其推广到多类分类问题还是一个正在研究的问题。当前已经有算法将SVM推广到多类分类问题，这些算法统称为“多类支持向量机”(Multi-Category Support Vector Machines，M-SVMs) 。它们可以大致分为两大类：其一，是Weston 在1998年提出的基于改进目标函数的多类分类算法，即将多个分类面的参数求解合并到一个最优化问题中，通过求解该最优化问题“一次性”地实现多类分类；其二，通过某种方式构造一系列的两类分类器并将它们组合在一起来实现多类分类。第一类方法尽管看起来简洁，但是在最优化问题求解过程中的变量远远多于第二类方法，训练速度不及第二类方法，而且在分类精度上也不占优势。当训练样本数非常大时，这一问题更加突出。正因如此，第二类方法更为常用。这类方法目前主要有四种分支算法：1对多算法、1对1算法、DAGSVM有向无环图以及ECOC纠错码。
这些方法虽然具有理论依据，但存在一个最优化问题，导致在训练过程中会耗费大量的时间，所以并没有得到很好的应用，只有1对1算法和DAGSVM有向无环图在实际中应用较多。由于1对多SVMs和1对1 SVMs对未知样本分类时需要使用所有的分类器，且分类结果与分类器使用顺序无关，因此它们的组合方式是唯一的。DAGSVM中的有向无环图的组合方式有很多种，但实验证明组合变化对分类结果影响不大。并且DAGSVM和ECOC的测试次数至少是N次，所以当类别很多时将不能很好的应用。
同时，在将多类问题转化为两类问题求解时，往往会出现无法分类区(未知区或重叠区)，可以用一个简单的三类例子来说明，如图1所示。图1(a)中使用1对多算法分类，每次判定全部样本集中的模式属于或不属于某一类；图1(b)中采用1对1算法分类，每次只取样本集中两类模式样本进行分类。这两种方法都会产生图1(a)、 图1(b)所示的阴影区，在这个区域中的模式样本，要么无法确定它们的类别，要么属于多个类别，总之，无法将其唯一判至某类，从而出现拒识。
图1 无法分类区域示意图
3 决策树简介
决策树起源于概念学习系统（Concept Learning System，CLS）的研究 ，但CLS的不足是它处理的学习问题不能太大。为此，20世纪70年年代末期Quinlan 提出了著名的ID3学习算法，它采用信息增益作为启发策略，通过选择窗口来形成决策树 。ID3算法的核心是：在决策树各级结点上选择属性时，用信息增益（information gain）作为属性的选择标准，以使得在每一个非叶结点进行测试时，能获得关于被测试记录最大的类别信息。其具体方法是：检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类，如图2所示。ID3算法的优点是：算法的理论清晰，方法简单，学习能力较强。其缺点是：只对比较小的数据集有效，且对噪声比较敏感，当训练数据集加大时，决策树可能会随之改变。
图3 类距离法示意图
5 总结
目前支持向量机已经得到普遍的认识和广泛的应用，而决策树算法也已经有了广泛的应用， 并且有了许多成熟的系统， 这些系统广泛应用于各个领域， 如语音识别， 模式识别， 专家系统等。但是， 解决一个复杂的数据挖掘问题的任何算法都要面临以下问题： 从错误的数据中学习、从分布的数据中学习、从有偏的数据中学习、学习有弹性的概念、学习那些抽象程度不同的概念、整合定性与定量的发现等， 归纳学习当中还有很多未开发的课题等待我们去研究。
并且我们始终要牢记一点，没有一个分类方法在对所有数据集上进行分类学习均是最优的，所以怎样使得算法尽可能的提高训练速度，减少分类错误，增加泛化性能是我们下一步的工作。
参考文献：
[1]V.Vapnik,著.张学工,译.统计学习理论的本质[M].北京:清华大学出版社,2000.
[2]Tom M.Mitchell,著.曾花军,张银奎,等.译.机器学习[M].北京:机械工业出版社,2003.
[3]V.Vapnik,著.许建华,张学工,译.统计学习理论[M].北京:电子工业出版社,2004.
[4]张学工.关于统计学习理论与支持向量机[J].自动化学报,2000,26(1):32-42．
[5]张浩然,汪晓东.支持向量机的学习方法综述[J].浙江师范大学学报（自然科学版）,2005,28(3):283-287.
[6]刘志刚,李德仁,秦前清,等.支持向量机在多类分类问题中的推广[J].计算机工程与应用,2004,40(7):10-13.
[7]Weston J,Watkins C.Multi-class support vector machines. Royal Holloway College, Tech Rep: SCD-TR-98-04,1998.
[8]Earl B．Hunt, Janet Marin, Philip J．Stone. Experiments in Induction[M].Academic Press,New York,1966.
[9]J.Ross Quinlan.Induction of decision trees[J].Machine Learning,1986,(1):81-106.
[10]Paul E,Utgoff.Incremental induction of decision trees[J]Machine Learning,1989,4(2):161-186.
[11]J.Ross Quinlan. C4.5: Programs for Machine Learning[M].Academic Press,New York,1993.
[12]Fumitake Takahashi,Shigeo Abe. Decision-Tree-Based Multi-class Support Vector Machines [A].Proceeding of ICONIP’02[C], Singapore:IEEE Press,2002.1419-1422.
[13]Scott Selikoff,The SVM-Tree Algorithm: A New Method for Handling Multi-Class SVMs. Cornell University,2003.
[14]Jin-Seon Lee, II-Seok Oh. Binary classification trees for multi-class classification prooblems[M].IEEE, 2003: 770-774.
[15]唐发明,王仲东,陈绵云.一种新的二叉树多类支持向量机算法[J].计算机工程与应用,2005,41(7):24-26.