《数据挖掘基础及其应用》课件第5章

第5章分类Ⅱ:支持向量机5.1引言5.2数学模型5.3优化理论5.4SVM优化5.5非线性SVM5.6SVM的应用本章小结

5.1引言

SVM是一种二分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器。SVM还可以引入核技巧,这使它成为实质上的非线性分类器。SVM的学习策略就是最大化间隔,可形式化为一个求解凸二次规划的问题,并在求解系统中加入了正则化项优化结构风险(StructuralRisk),它是一个具有稀疏性和鲁棒性的分类器。

SVM的发展史分为三个阶段:出现阶段、拓展阶段和大规模应用阶段。

(1)出现阶段。

(2)拓展阶段。

(3)大规模应用阶段。

SVM备受关注,其主要原因包括:

(1)SVM是一种有坚实理论基础的学习方法。它基本上不涉及概率测度及大数定律等,因此不同于现有的统计方法。

(2)对特征空间划分的最优超平面是SVM的目标,最大化分类边际的思想是SVM方法的核心。

(3)支持向量是SVM的训练结果,在SVM分类决策中起决定作用的是支持向量。

(4)SVM的最终决策函数只由少数的支持向量确定,计算的复杂性取决于支持向量的数目,而不是样本空间的维数,这在某种意义上避免了“维数灾难”,可解决高维问题。

(5)非线性映射是SVM方法的理论基础,SVM利用内积核函数代替向高维空间的非线性映射。

(6)SVM的学习算法是求解凸二次规划的最优化算法,可以避免神经网络结构选择和局部极小的问题。

5.2数学模型

5.2.1算法动机问题1:线性可分空间中有多种分类器,如何选择最优的分类器(分界线)?例如,给定数据如图5-1所示,其中点的形状区分数据对象的类别。在数据线性可分的情况下,分类边界B1和B2哪条更好呢?图5-1点代表数据对象,同一形状点隶属于同一类别

SVM的基本思想:

(1)在线性可分的情况下,在原空间寻找两类样本的最优分类超平面。

(2)通过使用结构风险最小化原理在属性空间构建最优分类超平面,使得分类器达到全局最优,并使整个样本空间的期望风险以某个概率满足一定上界。

SVM的原理图如图5-2所示。其中,虚线是边界。边界太窄,则容错性低,结构风险高;边界太宽,则容错性高,结构风险低。所以,边界的选择至关重要。图5-2SVM原理示意图:最大边界边缘

SVM突出的优点表现为以下几方面:

(1)基于统计学习理论中结构风险最小化原则。

(2)SVM的求解问题对应的是一个凸优化问题,因此得到的局部最优解一定是全局最优解。

(3)核函数的成功应用,将非线性问题转化为线性问题求解。

(4)分类间隔的最大化,使得SVM算法具有较好的鲁棒性。

5.2.2数学模型

给定训练样本集D={(x1,y1),(x2,y2),…,(xm

,ym)},yi∈{+1,-1},线性分类器基于训练样本D在二维空间中找到一个超平面来分开两类样本。当然,这样的超平面有很多,如图5-1所示。

假设:图5-3点到超平面的距离

因为yi∈{+1,-1},如图5-4所示,则两个异类支持向量到超平面的距离之和(也称为“间隔”)可表示为很显然,我们要找到符合这样一个条件的超平面来分开两类数据:这个超平面离两类样本都足够远,也就是使得“间隔”最大,即最终确定的参数w和b,使得r最大。即图5-4支持向量与间隔

5.3优化理论

5.3.1凸优化定义5.1(凸函数)X∈Rn为一凸集,f:X→R为一凸函数,凸优化就是要找出一点x*∈X,使得任意x∈X,都满足f(x*)≤f(x)。目标函数和约束条件都为变量的线性函数,称作线性规划问题。目标函数为变量的二次函数和约束条件为变量的线性函数,称作二次规划问题。目标函数和约束条件都为非线性函数,称作非线性规划问题。

5.3.2对偶理论

在线性规划早期发展中最重要的发现是对偶问题,即每一个线性规划问题(称为原始问题)有一个与它对应的对偶线性规划问题(称为对偶问题)。

对偶理论是研究线性规划中原始问题与对偶问题之间关系的理论。对偶理论属自动控制与系统工程范畴,主要研究经济学中的相互确定关系,涉及经济学的诸多方面。产出与成本的对偶、效用与支出的对偶,是经济学中典型的对偶关系。经济系统中还有许多其他这样的对偶关系。利用对偶性来进行经济分析的方法,称为对偶方法。

原始问题和对偶问题的标准形式如下。设原始问题为

则对偶问题为

定理5.1(弱对偶定理)若上述原始问题和对偶问题分别有可行解x0和y0,则cx0≤y0b。这个定理表明极大化问题任一可行解的目标函数值总是不大于它的对偶问题的任一可行解的目标函数值。

定理5.2(强对偶定理)若上述原始问题和对偶问题都可行,则它们分别有最优解x*和y*,且cx*=y*b。

定理5.3(最优准则定理)若上述原始问题和对偶问题分别有可行解x0

和y0,且两者的目标函数值相等,即cx0≤y0b,则两个可行解分别为对应线性规划的最优解。

定理5.4(松弛定理)若上述原始问题和对偶问题分别有可行解x0

和y0,且u0和v0分别为它们的松弛变量,则当且仅当x0

v0=0和y0u0=0时,x0

和y0分别为它们的最优解。x0

v0=0和y0u0=0这两个等式称为互补松弛条件。

定理5.5(互补松弛定理)若上述原始问题和对偶问题分别有可行解x0

和y0,且u0和v0分别为它们的松弛变量,则当且仅当x0

v0+y0u0=0时,x0

和y0为它们的最优解。

1.对称对偶线性规划

具有对称形式的线性规划的特点是:

(1)全部约束条件均为不等式,对极大化问题为“≤”,对极小化问题为“≥”。

(2)全部变量均为非负。

其算法流程如算法5.1所示。

2.非对称对偶线性规划

(1)有时线性规划并不以对称方式出现,如约束条件并不都是同向不等式;

(2)变量可以是非正的或没有符号约束。

非对称对偶线性规划可参照原始对偶表按下列步骤进行,其算法流程如算法5.2所示。

5.3.3拉格朗日方法和KKT条件

定义5.2(拉格朗日乘子法)对于等式约束,我们可以通过一个拉格朗日系数a把等式约束和目标函数组合成为一个式子L(a,x)=f(x)+ah(x),这里把a和h(x)视为向量形式,a是行向量,h(x)为列向量,然后求取最优值。可以通过对L(a,x)对各个参数求导取零,联立等式进行求取。

定义5.3(KKT条件)对于含有不等式约束的优化问题,如何求取最优值呢?常用的方法是KKT条件。同样的,把所有的不等式约束、等式约束和目标函数全部写为一个式子L(a,b,x)=f(x)+ag(x)+bh(x),KKT条件则是要求最优值必须满足以下条件:

(1)L(a,b,x)对x求导为零;

(2)h(x)=0;

(3)ag(x)=0。

问题2:为什么拉格朗日乘子法和KKT条件能够得到最优值?

先说拉格朗日乘子法。设优化目标函数z=f(x),x是向,z取不同的值,相当于可以投影在x构成的平面(曲面)上,即称为等高线。如图5-5所示,目标函数是f(x,y),这里x是向量,虚线是等高线。图5-5-等高线与目标函数的曲线相切

而之前说明过,ag(x)=0,这是KKT条件的第3个条件,当然已知的条件h(x)=0必须被满足。因此,满足强对偶条件优化问题的最优值都必须满足KKT条件,即上述说明的三个条件。可以把KKT条件视为拉格朗日乘子法的泛化。

5.4SVM优化

5.4.1硬间隔SVM利用拉格朗日优化方法可以把上述最优分类面问题转化为如下较简单的对偶问题,即约束条件为

5.4.2软间隔SVM

解决该问题的一个办法是允许SVM在一些样本上出错。为此,引入“软间隔”(SoftMargin)的概念,如图5-6所示。图5-6软间隔示意图(灰色圆圈圈出了一些不满足约束的样本)图5-7三种常见的替代损失函数

对软间隔SVM,KKT条件要求:

5.5

非线性SVM

5.4节介绍了在数据为线性可分的情况下,如何用SVM对数据集进行训练,从而得到一个线性分类器。实际上,线性不可分简单来说就是一个数据集不可以通过一个线性分类器(直线、平面)来实现分类。这样的数据集在实际应用中是很常见的,例如人脸图像、文本文档等。如图5-8所示的数据都是线性不可分的,即无法用直线将两类样本完全分开。图5-8线性不可分

问题3:前面所处理的都是线性分界线,如何处理非线性问题?

线性可分的情况有相当的局限性,所以SVM的终极目标还是要解决数据线性不可分的问题。解决这种线性不可分问题的基本思路有两种:

•加入松弛变量和惩罚因子,找到相对“最优”超平面,这里的“最优”可以理解为尽可能地将数据正确分类;

•使用核函数,将低维的数据映射到更高维的空间,使得在高维空间中的数据是线性可分的,则在高维空间使用线性分类模型即可,如图5-9所示。图5-9核函数将线性不可分数据映射到高维空间

对于非线性问题,可以通过非线性交换转化为某个高维空间中的线性问题,在变换空间求最优分类超平面。这种变换可能比较复杂,因此这种思路在一般情况下不易实现。但

是我们可以看到,在上节的对偶问题中,不论是寻优目标函数还是分类函数,都只涉及训练样本之间的内积运算(x·xi)。设非线性映射Φ:Rd→H将输入空间的样本映射到高维(可能是无穷维)的特征空间H中,当在特征空间H中构造最优超平面时,训练算法仅使用空间中的点积,即φ(xi)·φ(xj),而没有单独的φ(xi)出现。因此,如果能够找到一个函数K,使得

那么在高维空间实际上只需进行内积运算,而这种内积运算是可以用原空间中的函数实现的。根据泛函的有关理论,只要一种核函数K(xi·xj)满足Mercer条件,它就对应某一变

换空间中的内积。因此,在最优超平面中采用适当的内积函数K(xi·xj)就可以实现某一非线性变换后的线性分类,而计算复杂度却没有增加。此时,目标函数式(5-13)变为

而相应的分类函数也变为

概括地说,SVM就是通过某种事先选择的非线性映射,将输入向量映射到一个高维特征空间,在这个特征空间中构造最优分类超平面。在形式上,SVM分类函数类似于一个神经网络,输出是中间节点的线性组合,每个中间节点对应于一个支持向量,如图5-10所示。图5-10核SVM示意图

目前研究最多的核函数主要有三类:

(1)多项式核函数:

式中:q是多项式的阶次。通过该式可得到q阶多项式分类器。

(2)径向基核函数(RBF):

(3)S形核函数:

这时的SVM算法中包含了一个隐层的多层感知器网络,网络的权值、隐层节点数都是由算法自动确定的,而不像传统的感知器网络那样由人凭借经验确定。此外,该算法不存在困扰神经网络的局部极小点的问题。

以统计学习理论作为坚实的理论依据,SVM有很多优点,如基于结构风险最小化,克服了传统方法的过学习(Overfitting)和陷入局部最小的问题,具有很强的泛化能力;采用核函数方法,向高维空间映射时并不增加计算的复杂性,又有效地克服了维数灾难(CurseofDimensionality)问题。

但同时也要看到目前SVM研究的一些局限性:

(1)SVM的性能很大程度上依赖于核函数的选择,但没有很好的方法指导针对具体问题的核函数选择。

(2)训练测试SVM的速度和规模是另一个问题,尤其是实时控制问题。速度是一个对SVM应用有很大限制的因素。针对这个问题,Platt和Keerthi等分别提出了SMO

(SequentialMinimizationOptimization)和改进的SMO方法,但还需要进一步研究。

现有的SVM理论仅讨论具有固定惩罚系数C的情况,而实际上正负样本的两种误判造成的损失往往是不同的。

5.6SVM的应用

5.6.1人脸识别Osuna最早将SVM应用于人脸识别,并取得了较好的效果。其方法是训练非线性SVM分类器,以完成人脸与非人脸的分类。由于SVM的训练需要大量的存储空间,并且非线性SVM分类器需要较多的支持向量,所以速度很慢。为此,马勇等提出了一种层次型结构的SVM分类器,它由一个线性SVM组合和一个非线性SVM组成。

人脸检测研究中更复杂的情况是姿态的变化。叶航军等提出了利用SVM进行人脸姿态的判定,他将人脸姿态划分成6个类别,从一个多姿态人脸库中手工标定训练样本集和测试样本集,训练基于SVM的姿态分类器,可以将分类错误率降低到1.67%,这明显优于在传统方法中效果最好的人工神经元网络方法。

5.6.2语音识别

声纹识别属于连续输入信号的分类问题。SVM是一个很好的分类器,但不适合处理连续输入样本。为此,忻栋等引入隐式马尔可夫模型(HiddenMarkovModel,HMM),建立了SVM和HMM的混合模型。HMM适合处理连续信号,而SVM适合处理分类问题;HMM的结果反映了同类样