第5章支持向量机

引言

分类作为数据挖掘领域中一项非常重要的任务,其目的是学会一个分类函数或分类模
型(或分类器), 而支持向量机本身就是一种监督式学习的方法,它广泛应用于统计分类及回
归分析中。支持向量机(supportvectormachine,SVM)是Vapnik等于1995 年首先提出的, 
它在解决小样本、非线性及高维模式识别中表现出许多特有的优势,并推广到人脸识别、行
人检测、文本自动分类等其他机器学习问题中。支持向量机方法是建立在统计学习理论的
VC 维理论和结构风险最小原理基础上的,根据有限的样本信息在模型的复杂性和学习能力
之间寻求最佳折中,以求获得最好的推广能力。

5.支持向量机概述
1 

支持向量机是20 世纪90 年代中期发展起来的基于统计学习理论的一种机器学习方
法,通过寻求结构化风险最小化提高学习机泛化能力,实现经验风险和置信范围的最小化, 
从而达到在统计样本量较少的情况下也能获得良好统计规律的目的。其基本模型定义为特
征空间上的间隔最大的线性分类器,即支持向量机的学习策略便是间隔最大化,最终可转化
为一个凸二次规划问题的求解。

5.1 
rin最大化
1.mag

首先考虑两类线性可分的情况,如图5-1所示。两类训练样本分别为实心点与空心点, 
SVM 的最优分类面要求分类线不但能将两类正确分开,即训练错误率为0,且使得分类间隔
(margin)最大。在图5-1(a)中,
H 
为把两类训练样本正确分开的分类线,H1、H2 为这两类
训练样本中距离
H 
最近,且平行于
H 
的直线,则margin即为H1、H2 之间的垂直距离。

xyx=(x)∈R

设训练数据集为(y1),(y2),…,(,),x2,…,
n 
,1}。

x1,x2,nn 
x1,ny∈{+1,

线性判别函数设为

g(x)=(wTx)+
b 
(5-1) 
其中,wTx 
为
w 
与
x 
的内积。分类面方程为(wTx)+b=0。将判别函数进行归一化,使两类
所有的样本都满足

x)≥1,使y=-1时,g(y=1时,x)≥1 。其中,离分类

g(

x)≤-1;g(


第5 章 支持向量机
图5-1 最优分类面示意图
面最近的样本的g(x) =1。通常,还可以定义g(x)>0时,x 被分为ω1 类;g(x)<0时,x 
被分为ω2 类;g(x)=0时为决策面。设x1,x2 是决策面上的两点,于是就有
wTx1 +b=wTx2 +b, 即wT(x1 -x2)=0 (5-2) 
可以看出,w 与x1-x2 正交,x1-x2 即决策面的方向,所以w 就是决策面的法向量。
我们的目标是求分类间隔最大的决策面,首先表示出分类间隔margin。空间任意x(见
图5-1)可表示为
x =xp +r w
w (5-3) 
在式(5-3)中,xp 是x 在H 上的投影向量(见图5-1(b)),r 是x 到H 的垂直距离。
ww
表示w 方向上的单位向量,将式(5-3)代入式(5-1)中,可得
g(x)=wT xp +r w
w 
.
è .
.
. ÷ 
+b0 =wTxp +b0 +rwTw 
w =r w (5-4) 
wTxp +b=0,则r 表示为
r= g(x) w (5-5) 
由以上分析可知,距离分类面最近的样本满足|g(x)|=1,这样分类间隔就为
margin=2r= 2w
(5-6) 
因此,若要求margin的值最大,即求w 或w 2 的最小值。
5.1.2 支持向量机优化
因为要求所有训练样本正确分类,即需要满足如下的条件: 
yi[(wTx)+b]-1≥0, i=1,2,…,n (5-7) 
在以上条件下,求使w 2 最小的分类面。而H1、H2 上的训练样本就是式(5-7)中等
号成立的那些样本,叫作支持向量(supportvector),在图5-1(a)中用圆圈标记。所以,最优
分类面问题可以表示为如下的约束优化问题: 
MinΦ(w)=12
w 2 =12
(wTw) (5-8) 
51

约束条件为
yi[(wTx)+b]-1≥0, i=1,2,…,n 
构造Lagrange函数,即
L(w,b,a)=MinMax w a 12
w 2 - Σn 
i=1
ai(yi((xi,w)+b)-1) (5-9) 
其中,ai 为Lagrange系数,这里就对w 和b 求Lagrange函数的极小值。将L 对w 求偏导
数,并令其等于0,可得
.wL(w,b,a)=w - Σaiyixi =0 
得出
w* =Σaiyixi (5-10) 
将式(5-10)代入L 的方程,就得到了L 关于w 的最优解,即
L(w* ,b,a)=-12
Σi Σj 
aiajyiyj(xiTxj)- Σi 
aiyib+ Σi 
ai (5-11) 
再对b 求偏导,即
.bL(w,b,a)=Σiaiyi =0 (5-12) 
将式(5-12)代入L 关于w 的最优解,就可以得到L 关于w 和b 的最优解,即
L(w* ,b* ,a)=-12
Σi Σj 
aiajyiyj(xiTxj)+ Σi 
ai (5-13) 
下面寻找原始问题的对偶问题并求解,原始问题的对偶问题为
MaxQ(a)=-12
Σi Σj 
aiajyiyj(xiTxj)+ Σi 
ai 
s.t.Σn 
i=1
aiyi =0, ai ≥0,i=1,2,…,n 
(5-14) 
若ai* 为最优解,则可求得
w* =Σn 
i=1
ai*yixi (5-15) 
可以看出,这是不等式约束的二次函数极值问题,满足KKT (karush-kuhn-tucker)条
件。这样,使得式(5-15)最大化的w* 和b* 需要满足
Σn 
i=1
ai(yi [(wTx)+b] -1)=0 (5-16) 
而对于多数样本,它们不在离分类面最近的直线上,即yi[(wTxi)+b]-1>0,从而一
定有对应的ai=0,也就是说,只有在边界上的数据点(支持向量)才满足
yi[(wTx)+b]-1=0 
ai ≠0,i=1,2,…,n (5-17) 
它们只是全体样本中很少的一部分,相对于原始问题大幅减少了计算的复杂度。最终
求得上述问题的最优分类函数,即
f(x)=sgn{(w*Tx)+b* } =sgn{Σai *yi(xiTx)+b* } (5-18) 
52

第5 章 支持向量机
其中,sgn()为符号函数。由于非支持向量对应的ai 都为0,因此式(5-18)中的求和实际上
只对支持向量进行。b* 是分类的阈值,可以由任意一个支持向量用式(5-16)求得。这样就
求得了在两类线性可分情况下的SVM 分类器。然而,并不是所有的两类分类问题都是线性
可分的。对于非线性问题,SVM 设法将它通过非线性变换转化为另一空间中的线性问题, 
在这个变换空间求解最优的线性分类面。而这种非线性变换可以通过定义适当的内积函
数,即核函数实现。目前得到的常用核函数主要有多项式核、径向基核以及Sigmoid核,其
参数的选择对最终的分类效果也有较大影响。也就是说,以前新来的要分类的样本首先根
据w 和b 做一次线性运算,然后看求的结果是大于0还是小于0,由此判断是正例还是负例。
现在有了ai,不需要求出w,只将新来的样本和训练数据中的所有样本做内积和即可。从
KKT条件中得到,只有支持向量的ai >0,其他情况ai =0。因此,只求新来的样本和支持
向量的内积,然后运算即可。
核函数概念的提出使SVM 完成了向非线性分类的转变。观察图5-2,把横轴上端点a 
和b之间红色部分里的所有点定为正类,两边的黑色部分里的点定为负类。试问,能找到一
个线性函数用来把两类正确分开么? 答案是不能,因为二维空间里的线性函数就是直线,显
然找不到符合条件的直线。但可以找到一条曲线,如图5-3中的这条曲线。
图5-2 二维空间线性不可分的例子(见彩图) 图5-3 二维空间核函数举例
显然,通过点在这条曲线的上方还是下方就可以判断点所属的类别。这条曲线就是大
家熟知的二次曲线,它的函数表达式可以写为
g(x)=c0 +c1x +c2x2 
那么,首先需要将特征x 扩展到三维(1,x,x2),然后寻找特征和结果之间的模型。通
常将这种特征变换称作特征映射(featuremapping)。映射函数称作Φ (),在这个例子中, 
Φ(x)= 
1x 
x2 
é
.
êêêê 
ù
.
úúúú
,我们希望将得到的特征映射后的特征应用于SVM 分类,而不是最初的特征。
这样,需要将前面wTx+b 公式中的内积从<x(i),x>映射到<Φ(x(i)),Φ(x)>。由式(5-15) 
可知,线性分类用的是原始特征的内积<x(i),x>,在非线性分类时只选用映射后的内积即
可,至于选择何种映射,需要根据样本特点和分类效果选择。
然而,为了进行非线性分类,特征映射后会使维度大幅增加,对运算速度是一个极大的
53

挑战,而核函数很好地解决了这个问题。将核函数形式化定义,如果原始特征内积是<x,z>, 
映射后为<Φ(x),Φ(z)>,那么定义核函数(kernel)为k(x,z)=Φ (x)TΦ(z)。下面举例说
明这个定义的意义。令K (x,z)=(xTz)2,展开后得到
K (x,z)=(xTz)2 = Σm 
i=1
xiz( i ) Σm 
j=1
( xjzj ) =Σm 
i=1Σm 
j=1
xiyjzizj 
=Σm 
i=1Σm 
j=1(xixj)(zizj)=Φ(x)TΦ(z) (5-19) 
这里的Φ()指的是如下的映射(维数n=3时): 
Φ(x)= 
x1x1 
x1x2 
x1x3 
x2x1 
x2x2 
x2x3 
x3x1 
x3x2 
x3x3 
é
.
êêêêêêêêêêêêêêê 
ù
.
úúúúúúúúúúúúúúú 
也就是说,核函数K (x,z)=(xTz)2 只能在选择类似这样的Φ()作为映射才等价于映
射后特征的内积。此处用三维向量的核函数代表了九维向量的内积,大幅减小了运算量。
核函数的形式有很多,判断核函数有效性的是Mercer定理,常用的核函数有以下几种。
多项式核函数:K (x,z)= [xTz+1]q, 
径向基函数:K (x,z)=exp - x-z 2 
σ2 
.
è .
.
. ÷ 
, 
S 形函数:K (x,z)=tanh(v(xTz)+c)。
对核函数进行概括,即不同的核函数用原始特征不同的非线性组合拟合分类曲面。
SVM 还有一个问题,回到线性分类器,在训练线性最小间隔分类器时,如果样本线性可分, 
则可以得到正确的训练结果;但如果样本线性不可分,那么目标函数无解,会出现训练失败。
而在实际应用中,这种现象是很常见的,所以SVM 引入了松弛变量,即
Φ(w,ξ)=12
w 2 +cΣl 
i=1
ξ 
wTxi +b ≥+1-ξi yi =+1 
wTxi +b ≤-1+ξi yi =-1 
ξi ≥0 .i 
c 值有明确的含义:选取大的c 值,意味着更强调最小化训练错误。非线性分类有相同
的做法,这里不再赘述。
54

第 
5 
章支持向量机


5.支持向量机的实例
2 

目前,关于支持向量机的研究,除理论研究外,主要集中在对它和一些已有方法进行实
验对比研究。比如,贝尔实验室利用美国邮政标准手写数字库进行的对比实验,每个样本数
字都是16×16 的点阵(即256 维), 训练集共有7300 个样本,测试集有2000 个样本。表5-1 
是用人工和几种传统方法得到的分类器的测试结果,其中两层神经网络的结果是取多个两
层神经网络中的较好者,而LeNet1 是一个专门针对这个手写数字识别问题设计的五层神
经网络。

表5-
1 
传统方法对美国邮政手写数字库的识别结果

分类器测试错误率/
% 
分类器测试错误率/
% 
人工分类2.5 两层神经网络5.9 
决策树方法16.2 LeNet1 5.1 

3种支持向量机的实验结果见表5-2。

表5-
2 3 
种支持向量机的实验结果

支持向量机类型内积函数中的参数支持向量个数测试错误率/
% 
多项式内积q=3 274 4.0 
径向基函数内积σ2=0.3 291 4.1 
Sigmoid内积b=2,c=1 254 4.2 

这个实验一方面初步说明了SVM 方法较传统方法有明显的优势,也说明了不同的
SVM 方法可以得到性能相近的结果(不像神经网络那样十分依赖对模型的选择)。另外,实
验中还得到3种不同的支持向量机,最终得出的支持向量只是总训练样本中很少的一部分, 
而且3组支持向量中有80% 以上是重合的,也说明支持向量本身对不同的方法具有一定的
不敏感性。遗憾的是,这些结论目前都仅仅是有限实验中观察到的现象,如果能够证明它们
确实是正确的,将会使支持向量机的理论和应用有巨大的突破。此外,支持向量机有一些免
费软件,如LibSVM 、SVMlight、bSVM 、mySVM 、MATLABSVMtoolbox等。其中,LibSVM 
是台湾大学林智仁(LinChih-Jen)教授等开发设计的一个简单、易于使用和快速有效的
SVM 模式识别与回归的软件包,它不仅提供了编译好的可在Windows系统上执行的文件, 
还提供了源代码。

5.支持向量机的实现算法
3 

下面用台湾大学林智仁教授所做的SVM 工具箱做一个简单的分类,这个工具箱能够给
出分类的精度和每类的支持向量,但是用MATLAB 工具箱不能画出分类面,用训练样本点

55


作为输入来测试模型的性能试验程序和结果,如图5-4所示。
图5-4 训练样本
测试样本如图5-5所示。
图5-5 测试样本
分类器分类代码如下。 
N=50; 
n=2*N; 
x1=randn(2,N); 
y1=ones(1,N); 
x2=2+randn(2,N); 
y2=-ones(1,N); 
figure; 
plot(x1(1,:),x1(2,:),'o',x2(1,:),x2(2,:),'k.'); 
56

第5 章 支持向量机
axis([-3 8 -3 8]); 
title('C-SVC') 
hold on; 
X1=[x1,x2]; 
Y1=[y1,y2]; 
X=X1'; 
Y=Y1'; 
model=svmtrain(Y,X) 
Y_later=svmpredict(Y,X,model); 
%Clnum=sum(Y_later>0); 
%C2num=2*N-C1num; 
% %x3=zeros(2,C1num) 
%x4=zeros(2,C2num) 
figure; 
for i=1:2*N 
if Y_later(i) > 0 
plot(X1(1,i),X1(2,i),'o'); 
axis([-3 8 -3 8]); 
hold on 
else 
plot(X1(1,i),x1(2,i),'k.'); 
hold on 
end 
end 
进一步,关于最优和广义最优分类面的推广能力,有下面的结论。如果一组训练样本能
够被一个最优分类面或广义最优分类面分开,则对于测试样本,分类错误率的期望的上界是
训练样本中平均的支持向量占总训练样本数的比例,即
E(P(error))≤ E[支持向量机] 
训练样本总数-1 (5-20) 
因此,支持向量机的推广性与变换空间的维数也是无关的。只要能够适当地选择一种
内积定义,构造一个支持向量数相对较少的最优或广义最优分类面,就可以得到较好的推广
性。在这里,统计学习理论使用了与传统方法完全不同的思路,即不像传统方法那样首先试
图将原输入空间降维(即特征选择和特征变换),而是设法将输入空间升维,以求在高维空间
中问题变得线性可分(或接近线性可分);因为升维后只是改变了内积运算,并没有使算法复
杂性随着维数的增加而增加,而且在高维空间中的推广能力并不受维数影响,因此这种方法
才是可行的。
5.4 多类支持向量机
SVM 最初是为两类问题设计的,当处理多类问题时,就需要构造合适的多类分类器。
目前,构造SVM 多类分类器的方法主要有两种:一种是直接法,通过对原始最优化问题进
57

行适当改变,从而同时计算出所有分类决策函数,这种方法看似简单,但其计算复杂度比较

高,实现起来比较困难,只适用于小型问题;另一类是间接法,主要通过组合多个二分类器实

现多分类器的构造,常见的方法有一对多法和一对一法两种。

(1)一对多法(one-versus-rest,OVR)SVM 。每次训练时,把指定类别的样本归为一
类,其他剩余的样本归为另一类,这样
N 
个类别的样本就构造出
N 
个SVM分类器。对未
知样本进行分类时,具有最大分类函数值的那一类作为其归属类别。
(2)一对一法(one-versus-one,OVO)SVM 。这种方法是在任意两类样本之间设计一个
SVM分类器,因此
N 
个类别的样本就需要设计
N 
(
N 
-1)/2个SVM分类器。当对未知样
本进行分类时,使用“投票法”,最后得票最多的类别即该未知样本的类别。
5.5 
总结
SVM以统计学习理论作为坚实的理论依据,它有很多优点:基于结构风险最小化,克
服了传统方法的过学习(overfiting)和陷入局部最小的问题,具有很强的泛化能力;采用核
函数方法,向高维空间映射时并不增加计算的复杂性,又有效地克服了维数灾难(curseof 
dimensionality)问题。同时,目前的SVM研究也有下面的局限性。

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

(2)训练测试SVM的速度和规模是另一个问题,尤其是对实时控制问题,速度是一个
对SVM应用限制很大的因素;针对这个问题,Plat 
和Kerthi等分别提出SMO(Sequential 
MinimalOptimization)和改进的SMO方法,但还值得进一步研究。
(3)现有SVM理论仅讨论具有固定惩罚系数
c 
的情况,而实际上正、负样本的两种误
判造成的损失往往是不同的。
课后习题

1.支持向量机的基本思想和原理分别是什么? 为什么要引入核函数? 
2.试分析支持向量机对缺失数据和噪声敏感的原因。
3.比较感知机的对偶形式与线性可分支持向量机的对偶形式。
T,T,T, T,T,
4.已知正例点x1=(1,2)x2=(2,3)x3=(3,3)负例点x4=(2,1)x5=(3,2)
试求最大间隔分离超平面和分类决策函数,并在图上画出分离超平面、间隔边界及支持
向量。
58