现代机器学习 课件 第6章 支持向量机

第6章支持向量机6.1支持向量机简介6.2线性支持向量机6.3非线性支持向量机6.4支持向量机的应用本章小结

6.1支持向量机简介

支持向量机是一种二分类模型,其基本模型是定义在特征空间上使得特征间隔最大的线性分类器,以间隔最大为目标使其有别于感知机。在面对非线性分类问题时,支持向量机可以使用核函数的技巧,对非线性特征进行分类。支持向量机的学习目标是使得特征间隔最大化,其数学形式为一个求解凸二次规划最优解的问题,即支持向量机的学习过程是求解凸二次规划的最优解的过程。

支持向量机的学习过程是一个构造由简至繁构造模型的过程,包含线性可分支持向量机、线性支持向量机和非线性支持向量机。简单模型是复杂模型在特殊情况下的一种模式,

也是分析复杂模型的基础。在训练数据线性可分的情况下,通过使硬间隔最大化为目标训练,可以得到一个线性分类器,即线性可分支持向量机,也称为硬间隔支持向量机;在训练数据近似线性可分的情况下,通过使软间隔最大化为目标训练,得到的也是一个线性分类器,即线性支持向量机,也称为软间隔支持向量机;在训练数据线性不可分的情况下,通过将核函数方法和软间隔最大化并用,可以学习出非线性支持向量机。

当输入数据空间为欧式空间或者离散集合,特征空间为希尔伯特空间时,核函数表示将输入数据从输入空间映射到特征空间后得到的特征向量之间的内积,通过引入核函数的

方法,可以使得支持向量机能够处理非线性分类问题,等价于隐式的在高维特征空间中学习线性支持向量机。核函数方法是比支持向量机更为一般的机器学习方法。

6.2线性支持向量机

给定训练样本集:其中,xi为第i个特征向量,yi表示xi的类别,(xi,yi)称为样本点。

图6.1所示的二维特征空间中的分类问题,训练数据集线性可分,此时可以将两种数据正确分类的直线有无数条,而线性支持向量机对应的直线为使得两类数据正确划分且间隔最大的直线。图6.1多种分类超平面的分类结果

6.2.1函数间隔与几何间隔

一般情况下,一个点距离超平面的远近程度可以代表分类预测的确信度,在超平面w·x+b=0已经确定的情况下,w·x+b能够相对地表示点x距离超平面的远近程度,而根据w·x+b和其对应的类别标记y是否一致,可以判断分类结果是否正确,所以,y(w·x+b)可以用来表示分类的正确与否,以及其确信度,这就是函数间隔的概念。

对于给定的训练数据集T和超平面(w,b),定义超平面关于样本点(xi,yi)的函数间隔为

对于整个训练数据集,超平面(w,b)关于整个训练数据集T的函数间隔由超平面(w,b)关于T中所有样本函数间隔的最小值表示:

对于给定的训练数据集T和超平面(w,b),定义超平面关于样本点(xi,yi)的几何间隔为．

对于整个训练数据集,超平面(w,b)关于整个训练数据集T的几何间隔由超平面(w,b)关于T中所有样本几何间隔的最小值表示:

超平面(w,b)关于样本点(xi,yi)的几何间隔一般是带符号的距离,当样本点正确分类时,其就表示样本点到超平面的距离。

从上述分析可知,函数间隔和几何间隔有如下关系:

6.2.2线性可分问题

几何间隔最大的分离超平面可以由下式表示:

上式可解释为,在超平面(w,b)关于训练数据集中的所有样本的点的几何间隔至少是γ的约束条件下,希望能够使得超平面(w,b)关于训练数据集的几何间隔γ能够取得最大值。

由几何间隔和函数间隔之间的关系可知,上述问题可以转化为

综上所述,可得线性可分支持向量机的学习算法为最大间隔算法,算法如下:

在线性可分的情况下,训练数据集的样本中与分离超平面距离最近的样本点被称为支持向量。支持向量是使得约束条件取等号时的特征点,即

对于正例样本点:

对于负例样本点:

从图6.2可以看到,在求解最优化问题时,间隔只依赖于支持向量到分离超平面的距离。所以,在确定分离超平面时只有支持向量起作用,样本集中的其他样本点并不起作用。移动支持向量会使得所求解得到的分离超平面改变,而移动

其他的样本点并不会对最终解造成影响。所以,支持向量机其实是由较少有代表性的训练样本决定的。图6.2支持向量和几何间隔

6.2.3对偶问题

6.3非线性支持向量机

线性分类支持向量机是一种解决线性分类问题时非常有效的方法,但是在面对非线性分类问题时,就需要使用非线性支持向量机。非线性分类问题是指无法用直线(线性模型)将正负实例区分开的问题,如图6.3所示。图6.3线性不可分样本

对于这样的问题,可以将样本从原始空间映射到一个更高维的特征空间,使得样本在高维特征空间中线性可分,并且能在高维空间中找到合适的分离超平面。如图6.4所示,如

果原始空间是有限维的,其特征数也是有限的,则一定存在一个更高维的特征空间使得样本可以在此高维空间中线性可分。图6.4高维空间线性可分

6.3.1核方法

令φ(x)表示将x映射后的特征向量,则在特征空间中的分类决策函数可用下式表示:

与之对应的所需求解的最优化问题也会转换为下式:

那么,其对偶问题可以表示为

定义函数K(xi,xj)满足下式:

此时对偶问题的目标函数可以写成:

在进行空间映射时,特征空间一般是更高维的空间,可以看到,在给定核函数K(xi,xj)的情况下,映射函数和对应的特征空间并不是唯一的。

6.3.2常用核函数

另外,还可以通过多个核函数的组合形成新的核函数:

6.3.3非线性支持向量分类

通过使用核函数的方法,可以对非线性问题进行分类。将线性支持向量机扩展到非线性支持向量机,只需要将对偶形势中的内积替换成相应的核函数即可。对于非线性分类数

据集,通过引入核函数,使得几何间隔最大,可以学习到如下的分类决策函数:

非线性支持向量机学习算法如下:

6.4支持向量机的应用在鸢尾花数据集中,每行数据共有五列,其中前四列为特征,最后一列为类别。数据集中的四个特征分别代表萼片的长度和宽度,滑板的长度和宽度;类别总共有三种。首先读取数据集,并从数据集中提取数据特征,将类别标签转换为数字形式。然后,将读取到的数据集随机划分为训练样本和测试样本,将已经准备好的数据送入SVM模型中训练。这里的SVM模型直接使用Scikit-Learn库中的SVM模型,注意需要提前导入Scikit-Learn库。最后,计算分类准确率,验证最终的分类结果。实验结果表明,SVM模型已经可以很好地对鸢尾花数据集进行分类,且过拟合现象很微弱。

本章小结

支持向量机是一种经典的二分类模型,其基本模型是定义在特征