支持向量机方法课件

知识管理与数据分析实验室数据挖掘技术专题支持向量机12023/10/8知识管理与数据分析实验室肖莹支持向量机22023/10/8知识管理与数据分析实验室支持向量机(Support

Vector

Machine,简称SVM)是在统计学习理论基础上提出一种新型通用的机器学习方法。它建立在结构风险最小化原则基础之上，具有很强的学习能力。支持向量机32023/10/8知识管理与数据分析实验室其主要借助于最优化方法解决数据挖掘中的分类问题，是数据挖掘技术中一个新的研究热点。它是统计学习理论中最年轻也最实用的部分，在很多领域得到了成功应用，如人脸检测、手写数字识别、文本分类、生物信息学等。支持向量机的提出42023/11/27知识管理与数据分析实验室SVM理论源于Vapinik在1963年提出的用于解决模式识别问题的支持向量方法。这种方法从训练集中选择一组特征子集,使得对特征子集的线性划分等价于对整个数据集的分割。这组特征子集称为支持向量SV。在此后近30年中,对SV的研究主要集中在对分类函数的改进和函数预测上。支持向量机的提出52023/11/27知识管理与数据分析实验室在1971年,Kimel-dorf提出使用线性不等约束重新构造SV的核空间,解决了一部分线性不可分的问题,为以后SVM的研究开辟了道路。

1990年,Grace,Boster和Vapnik等人开始对

SVM技术进行研究,并取得突破性进展。

1995年,Vapnik提出了统计学习理论,较好地解决了线性不可分的问题,正式奠定了SVM的理论基础。支持向量机理论62023/11/27知识管理与数据分析实验室支持向量机的理论最初来自对数据分类问题的处理。对于数据分类问题,如果采用通用的神经网络方法来实现,其机理可以简单地描述为：系统随机产生一个超平面并移动它,直到训练集中属于不同分类的点正好位于平面的不同侧面。这种处理机制决定了：用神经网络方法进行数据分类最终获得的分割平面将相当靠近训练集中的点,而在绝大多数情况下,并不是一个最优解。支持向量机理论为此SVM考虑寻找一个满足分类要求的分割平面,并使训练集中的点距离该分割平面尽可能地远,即寻找一个分割平面,使其两侧的空白区域(margin)最大。72023/11/27知识管理与数据分析实验室支持向量机理论在很多情况下,训练数据集中的数据是线性不可分的,这使得SV的应用受到了很大的限制。为了解决这个问题,Vapnik等人提出使用SVM作为超平面分割方法的扩展。使用

SVM进行数据集分类工作的典型流程如图2所示。82023/11/27知识管理与数据分析实验室支持向量机理论92023/11/27知识管理与数据分析实验室首先,通过预先选定的一些非线性映射将输入空间映射到高维属性空间,使得在高维属性空间中有可能对训练数据实现超平面的分割,避免了在原输入空间中进行非线性曲面分割计算。SVM数据集形成的分类函数具有这样的性质:它是一组以SV为参数的非线性函数的线性组合,因此分类函数的表达式仅和SV的数量相关,而独立于空间的维度。在处理高维输入空间的分类时,这种方式尤其有效。支持向量机算法的发展102023/11/27知识管理与数据分析实验室模糊支持向量机最小二乘支持向量机加权支持向量机(有偏样本的加权,有偏风险加权)主动学习的支持向量机粗糙集与支持向量机的结合基于决策树的支持向量机分级聚类的支持向量机支持向量机算法的发展112023/11/27知识管理与数据分析实验室算法上的提高---Vapnik

在1995

年提出了“chunking” 算法，

Osuna

提出了一种分解算法，

Platt

于1998年提出了序贯最小优化核函数的构造和参数的选择理论研究支持向量机从两类问题向多类问题的推广支持向量机的特点122023/11/27知识管理与数据分析实验室（1） 非线性映射是SVM方法的理论基础,SVM利用内积核函数代替向高维空间的非线性映射；（2）对特征空间划分的最优超平面是SVM的目标,最大化分类边际的思想是SVM方法的核心；（3）支持向量是SVM的训练结果,在SVM分类决策中起决定作用的是支持向量。支持向量机的特点132023/11/27知识管理与数据分析实验室（4）SVM是一种有坚实理论基础的新颖的小样本学习方法。它基本上不涉及概率测度及大数定律等,因此不同于现有的统计方法。从本质上看,它避开了从归纳到演绎的传统过程,实现了高效的从训练样本到预报样本的“转导推理”,大大简化了分类和回归等问题。支持向量机的特点142023/11/27知识管理与数据分析实验室（5）SVM的最终决策函数只由少数的支持向量所确定,计算的复杂性取决于支持向量的数目,而不是样本空间的维数,这在某种意义上避免了“维数灾难”。支持向量机的应用举例152023/11/27知识管理与数据分析实验室以在手写数字识别和文本分类中的应用为例说明。这个问题通常用来做分类器的测试平台，最初是美国邮政服务部门使用手写邮政编码自动分类邮件的需要提出的。支持向量机的应用举例162023/11/27知识管理与数据分析实验室这是一个可识别性较差的数据库，人工识别平均错误率是2.5%，用决策树方法识别错误率是16.2%，两层神经网络中错误率最小的是5.9%，专门针对该问题设计的五层神经网络错误率为5.1%(其中利用了大量先验知识)，而用SVM方法得到的错误率仅为

4.0%，且其中直接采用了16X16的字符点阵作为svm的输入，并没有进行专门的特征提取。支持向量机的应用举例172023/11/27知识管理与数据分析实验室文本分类的任务是将文本文件根据内容分

为预先定义的几个类别。很多领域都有这

种问题，包括邮件过滤、网页搜索、办公

自动化、主题索引和新闻故事的分类。因

为一个文件可以分给不止一个类别，所以

这不是一个多分类问题，而是两分类问题，即是或不是属于某类。支持向量机的应用举例182023/11/27知识管理与数据分析实验室Joachims等人用传统的向量空间模型作为输入训练支持向量机，表现出比传统方法如简单贝叶斯、Rocchio、决策树的C4.5算法和K近邻等更好的性能，这是因为传统方法在文本的高维向量空间中的推广性能差，而支持向量机得到的最大间隔分类器克服了高维空间中的维数困难。支持向量机的不足192023/11/27知识管理与数据分析实验室（1）SVM算法对大规模训练样本难以实施。由于SVM是借助二次规划来求解支持向量，而求解二次规划将涉及m

阶矩阵的计算（m为样本的个数），当m数目很大时该矩阵

的存储和计算将耗费大量的机器内存和运

算时间。支持向量机的不足202023/11/27知识管理与数据分析实验室（2）用SVM解决多分类问题存在困难经典的支持向量机算法只给出了二类分类的算法，而在数据挖掘的实际应用中，一般要解决多类的分类问题。可以通过多个二类支持向量机的组合来解决。支持向量机的研究难点212023/11/27知识管理与数据分析实验室（1）核函数和参数的构造和选择缺乏理论指导。核函数的选择影响着分类器的性能，如何根据待解决问题的先验知识和实际样

本数据，选择和构造合适的核函数、确定

核函数的参数等问题，都缺乏相应的理论

指导。支持向量机的研究难点222023/11/27知识管理与数据分析实验室（2）训练大规模数据集的问题。如何解决训练速度与训练样本规模间的矛盾，测试速度与支持向量数目间的矛盾，找到对大规模样本集有效的训练算法和分类实现算法，仍是未很好解决的问题。支持向量机的研究难点232023/11/27知识管理与数据分析实验室（3）多类分类问题的有效算法与SVM

优化设计问题。尽管训练多类SVM

问题的算法已被提出，但用于多类分类问题时的有效算法、多类SVM

的优化设计仍是一个需要进一步研究的问题。