支持向量机可编辑.docxVIP

实用文档

支持向量机

支持向量机，英文名为supportvectormachine，一般简称SVM，通俗来讲，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略便是间隔最大化，最终可转化为一个凸二次规划（convexquadraticprogramming）问题的求解,支持向量机的学习算法是求解凸二次规划的最优化算法。其方法包含构建由简到繁的模型：线性可分支持向量机、线性支持向量机和非线性支持向量机。

线性可分支持向量机

假定一特征空间上的训练数据集T=x1,y1,x2,y2,?,xN,yN，其中xi∈χ=Rn,

一般地，当训练数据集线性可分时，存在无穷多个分离超平面可将两类数据正确分开，线性可分支持向量机利用间隔最大化求最优分离超平面，这是解是唯一的。若最优分离超平面为w??x+b?

在上图中，有A、B、C三个点，表示三个实例，设“。”表示正类，“×”表示负类，则这三个点全在正类。A距分类超平面较远，若预测该点为正类就比较确信预测是正确的；C距分类超平面较近，若预测该点为负类就不那么确信；B介于AC两者之间，预测为正类的确信度也在A与C之间。故一般来说，点距离分离超平面的远近可以表示分类预测的确信程度。在超平面w?x+b=0确定的情况下，w?x+b能够相对地表示点x到超平面的远近，而w?x+b的符号与类标记y的符号是否一致可表示分类是否正确，所以yw?x+b可以来表示分类的真确性及确信度，我们称之为函数间隔。也就是，样本点xi,yi的函数间隔为γi=yiw?xi+b，训练样本集T的函数间隔为超平面w,b关于T中所有样本点

支持向量机学习的基本思想是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对线性可分的训练数据集而言，线性可分的超平面有无穷多，但是几何间隔最大的只有一个。几何间隔最大意味着以充分大的的确信度对训练数据集进行分类，也就是说，不仅将正负实例分开，而且对最难分的实例点（离超平面最近的点）也有足够大的确信度把它们分开，这样的超平面应该对未知的新实例有很好的分类预测能力。

最大间隔分类超平面

这个问题可以表示为下面的的约束最优化问题：

maxw,b

s.tyiww

即我们希望最大化超平面w,b关于训练数据集的几何间隔γ，约束条件表示超平面每个训练样本点的几何间隔至少是γ，考虑几何间隔和函数间隔的关系，可将这个问题改写为

s.t

函数间隔的取值并不影响最优化问题的解，事实上，假设将w和b按比例改变，函数间隔也改变同样的倍数，这一改变对这最优化问题的不等式约束没有影响，对目标函数的优化也没有影响，也就是说，它产生的是一组等价问题，为此我们可以取，将其代入，且注意到最大化1w和最小化12w

这是个凸二次规划问题。

在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量。支持向量就是使下列约束条件等号成立的点，即

yi

对yi=+1

H1

上，对yi=?1

H2

上，下图在H1和H2

由图可知，再决定分离超平面时只有支持向量起作用，而其他实例点并不起作用，如果移动支持向量将改变所求的解；但是如果在间隔边界以外移动其他的点，甚至去掉这下点，则解是不变的，由于支持向量在确定分离超平面中起决定作用，所以这种分类模型取名为支持向量机。支持向量的个数一般很少，所以支持向量机由很少的“重要的”训练样本确定。

学习的对偶算法

首先构建拉格朗日函数，为此，引进拉格朗日乘子（Lagrangemultiplier）αi≥0,

Lw,b,α

根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：

所以，为了得到对偶问题的解，需要先求Lw,b,α对w、b的极小，再求对α的极大。

求

将拉格朗日函数Lw,b,α分别对w、b求偏导并令其为零，可得

w=i=1

i=1N

将其结果代入拉格朗日函数，化简可得

Lw,b,α

即=?12

求对α的极大，即是对偶问题

?12

s.t.i=1

αi

根据KKT条件可得，设α?=α1,?

w?

b?

分类决策函数可以写成

fx

这就是说，分类决策函数只依赖于输入x和训练样本输入的内积。此外，w?和b?只依赖于训练数据中对应于αi?0的样本xi,yi，而其他的样本点对

线性支持向量机

线性可分支持向量机对线性不可分训练数据是不适用的，因为此时不等式约束并不成立，为了解决此问题，线性支持向量机产生了。

线性不可分数据集中，通常情况下是训练数据中有一些奇异点，若将这些奇异点取出，剩下大部分样本点组成的集合石线性可分的。线性不可分意味着某些样本点xi,yi不满足间隔大于等于1的约束条件，为了解决此问题，可以对每个样本点x

yi

目标函数变为

12

C为惩罚参数，一般由问题决定，是调和二者的系数。

线性不可分的学习支持向量机的学