【十大经典数据挖掘算法】SVM

SVM(Support Vector Machines)是分类算法中应用广泛、效果不错的一类。《统计学习方法》对SVM的数学原理做了详细推导与论述,本文仅做整理。由简至繁SVM可分类为三类:线性可分(linear SVM in linearly separable case)的线性SVM、线性不可分的线性SVM、非线性(nonlinear)SVM。

1. 线性可分

对于二类分类问题,训练集T={(x1,y1),(x2,y2),,(xN,yN)}T={(x1,y1),(x2,y2),⋯,(xN,yN)},其类别yi{0,1}yi∈{0,1},线性SVM通过学习得到分离超平面(hyperplane):

wx+b=0w⋅x+b=0

以及相应的分类决策函数:

f(x)=sign(wx+b)f(x)=sign(w⋅x+b)

有如下图所示的分离超平面,哪一个超平面的分类效果更好呢?
1483015537-8879-20161015215846703-1219368032

直观上,超平面B1B1的分类效果更好一些。将距离分离超平面最近的两个不同类别的样本点称为支持向量(support vector)的,构成了两条平行于分离超平面的长带,二者之间的距离称之为margin。显然,margin更大,则分类正确的确信度更高(与超平面的距离表示分类的确信度,距离越远则分类正确的确信度越高)。通过计算容易得到:

margin=2wmargin=2∥w∥

从上图中可观察到:margin以外的样本点对于确定分离超平面没有贡献,换句话说,SVM是有很重要的训练样本(支持向量)所确定的。至此,SVM分类问题可描述为在全部分类正确的情况下,最大化2w2∥w∥(等价于最小化12w212∥w∥2);线性分类的约束最优化问题:

minw,b12w2s.t.yi(wxi+b)10(1)(2)(1)minw,b12∥w∥2(2)s.t.yi(w⋅xi+b)−1≥0

对每一个不等式约束引进拉格朗日乘子(Lagrange multiplier)αi0,i=1,2,,Nαi≥0,i=1,2,⋯,N;构造拉格朗日函数(Lagrange function):

L(w,b,α)=12w2i=1Nαi[yi(wxi+b)1](3)(3)L(w,b,α)=12∥w∥2−∑i=1Nαi[yi(w⋅xi+b)−1]

根据拉格朗日对偶性,原始的约束最优化问题可等价于极大极小的对偶问题:

maxαminw,bL(w,b,α)maxαminw,bL(w,b,α)

L(w,b,α)L(w,b,α)w,bw,b求偏导并令其等于0,则

Lw=wi=1Nαiyixi=0w=i=1NαiyixiLb=i=1Nαiyi=0i=1Nαiyi=0∂L∂w=w−∑i=1Nαiyixi=0⇒w=∑i=1Nαiyixi∂L∂b=∑i=1Nαiyi=0⇒∑i=1Nαiyi=0

将上述式子代入拉格朗日函数(3)(3)中,对偶问题转为

maxα12i=1Nj=1Nαiαjyiyj(xixj)+i=1Nαimaxα−12∑i=1N∑j=1Nαiαjyiyj(xi⋅xj)+∑i=1Nαi

等价于最优化问题:

minαs.t.12i=1Nj=1Nαiαjyiyj(xixj)i=1Nαii=1Nαiyi=0αi0,i=1,2,,N(4)(5)(6)(4)minα12∑i=1N∑j=1Nαiαjyiyj(xi⋅xj)−∑i=1Nαi(5)s.t.∑i=1Nαiyi=0(6)αi≥0,i=1,2,⋯,N

线性可分是理想情形,大多数情况下,由于噪声或特异点等各种原因,训练样本是线性不可分的。因此,需要更一般化的学习算法。

2. 线性不可分

线性不可分意味着有样本点不满足约束条件(2)(2),为了解决这个问题,对每个样本引入一个松弛变量ξi0ξi≥0,这样约束条件变为:

yi(wxi+b)1ξiyi(w⋅xi+b)≥1−ξi

目标函数则变为

minw,b,ξ12w2+Ci=1Nξiminw,b,ξ12∥w∥2+C∑i=1Nξi

其中,CC为惩罚函数,目标函数有两层含义:

  • margin尽量大,
  • 误分类的样本点计量少

CC为调节二者的参数。通过构造拉格朗日函数并求解偏导(具体推导略去),可得到等价的对偶问题:

minα12i=1Nj=1Nαiαjyiyj(xixj)i=1Nαi(7)(7)minα12∑i=1N∑j=1Nαiαjyiyj(xi⋅xj)−∑i=1Nαi
s.t.i=1Nαiyi=00αiC,i=1,2,,N(8)(9)(8)s.t.∑i=1Nαiyi=0(9)0≤αi≤C,i=1,2,⋯,N

与上一节中线性可分的对偶问题相比,只是约束条件αiαi发生变化,问题求解思路与之类似。

3. 非线性

对于非线性问题,线性SVM不再适用了,需要非线性SVM来解决了。解决非线性分类问题的思路,通过空间变换ϕϕ(一般是低维空间映射到高维空间xϕ(x)x→ϕ(x))后实现线性可分,在下图所示的例子中,通过空间变换,将左图中的椭圆分离面变换成了右图中直线。

1483015537-6448-20161015215902843-1665550699

在SVM的等价对偶问题中的目标函数中有样本点的内积xixjxi⋅xj,在空间变换后则是ϕ(xi)ϕ(xj)ϕ(xi)⋅ϕ(xj),由于维数增加导致内积计算成本增加,这时核函数(kernel function)便派上用场了,将映射后的高维空间内积转换成低维空间的函数:

K(x,z)=ϕ(x)ϕ(z)K(x,z)=ϕ(x)⋅ϕ(z)

将其代入一般化的SVM学习算法的目标函数(7)(7)中,可得非线性SVM的最优化问题:

minαs.t.12i=1Nj=1NαiαjyiyjK(xi,xj)i=1Nαii=1Nαiyi=00αiC,i=1,2,,N(10)(11)(12)(10)minα12∑i=1N∑j=1NαiαjyiyjK(xi,xj)−∑i=1Nαi(11)s.t.∑i=1Nαiyi=0(12)0≤αi≤C,i=1,2,⋯,N

4. 参考资料

[1] 李航,《统计学习方法》.
[2] Pang-Ning Tan, Michael Steinbach, Vipin Kumar, Introduction to Data Mining.


如需转载,请注明作者及出处.
作者:Treant

内容多来自网络,如有侵权,请联系QQ:23683716,谢谢。:一起大数据 » 【十大经典数据挖掘算法】SVM

优秀人才不缺工作机会,只缺适合自己的好机会。但是他们往往没有精力从海量机会中找到最适合的那个。 100offer 会对平台上的人才和企业进行严格筛选,让「最好的人才」和「最好的公司」相遇。 注册 100offer,谈谈你对下一份工作的期待。一周内,收到 5-10 个满足你要求的好机会!
赞 (0)
分享到:更多 ()