SVM原理以及Tensorflow 实现SVM分类(附代码)

xiaoxiao2021-02-28  14

1.1. SVM介绍1.2. 工作原理 1.2.1. 几何间隔和函数间隔1.2.2. 最大化间隔 1.3. 软间隔1.4. SMO算法1.5. 核函数1.6. 实例

1.1. SVM介绍

SVM(Support Vector Machines)——支持向量机是在所有知名的数据挖掘算法中最健壮,最准确的方法之一,它属于二分类算法,可以支持线性和非线性的分类。发展到今天,SVM已经可以支持多分类了,但在这一章里,我们着重讲支持向量机在二分类问题中的工作原理。 假设在一个二维线性可分的数据集中,图一A所示,我们要找到一个超平面把两组数据分开,这时,我们认为线性回归的直线或逻辑回归的直线也能够做这个分类,这条直线可以是图一B中的直线,也可以是图一C中的直线,或者图一D中的直线,但哪条直线才最好呢,也就是说哪条直线能够达到最好的泛化能力呢?那就是一个能使两类之间的空间大小最大的一个超平面。 这个超平面在二维平面上看到的就是一条直线,在三维空间中就是一个平面...,因此,我们把这个划分数据的决策边界统称为超平面。离这个超平面最近的点就叫做支持向量,点到超平面的距离叫间隔。支持向量机就是要使超平面和支持向量之间的间隔尽可能的大,这样超平面才可以将两类样本准确的分开,而保证间隔尽可能的大就是保证我们的分类器误差尽可能的小,尽可能的健壮。 图一

1.2. 工作原理

1.2.1. 几何间隔和函数间隔

在最大化支持向量到超平面距离前,我们首先要定义我们的超平面 h(x) h(x)(称为超平面的判别函数,也称给定 w w b b的泛函间隔),其中 w w为权重向量, b b为偏移向量:

h(x)=wTx+b h(x)=wTx+b 样本 x x到最优超平面的 几何间隔为: r=h(x)||w||=wTx+b||w|| r=h(x)||w||=wTx+b||w|| ||w|| ||w||是向量 w w的内积,是个常数,即 ||w||=w02+w12+...+wn2 ||w||=w02+w12+...+wn2,而 h(x) h(x)就是下面要介绍的函数间隔。

函数间隔

rˆ=h(x) r^=h(x) 函数间隔 h(x) h(x)它是一个并不标准的间隔度量,是人为定义的,它不适合用来做最大化的间隔值,因为,一旦超平面固定以后,如果我们人为的放大或缩小 w w b b值,那这个超平面也会无限的放大或缩小,这将对分类造成严重影响。而几何间隔是函数间隔除以 ||w|| ||w||,当 w w的值无限放大或缩小时, ||w|| ||w||也会放大或缩小,而整个 r r保持不变,它只随着超平面的变动而变动,不受两个参数的影响。因而,我们用几何间隔来做最大化间隔度量。

1.2.2. 最大化间隔

在支持向量机中,我们把几何间隔 r r作为最大化间隔进行分析,并且采用-1和1作为类别标签,什么采用-1和+1,而不是0和1呢?这是由于-1和+1仅仅相差一个符号,方便数学上的处理。我们可以通过一个统一公式来表示间隔或者数据点到分隔超平面的距离,同时不必担心数据到底是属于-1还是+1类。 我们一步一步的进行分析,首先如下图,在这个 2 R2空间中,假设我们已经确定了一个超平面,这个超平面的函数关系式应该是 h(x)=wTx+b=0 h(x)=wTx+b=0,这个式子表示我们图中的那条虚线,很明显,这个式子意思是说点x在超平面上,但我们要想使所有的点都尽可能的远离这个超平面,我们只要保证离这个超平面最近的点远离这个超平面,也就是说这些叫支持向量的点 x x∗需要尽可能的远离它。

我们把其中一个支持向量 x x∗到最优超平面的距离定义为:

r=h(x)||w||=1||w||1||w||if:y=h(x)=+1if:y=h(x)=1 r∗=h(x∗)||w||={1||w||if:y∗=h(x∗)=+1−1||w||if:y∗=h(x∗)=−1

这是我们通过把函数间隔 h(x) h(x)固定为1而得来的。我们可以把这个式子想象成还存在两个平面,这两个平面分别是 wTxs+b=1 wTxs+b=1 wTxs+b=1 wTxs+b=−1,对应上图中的两根实线。这些支持向量 xs xs就在这两个平面上,这两个平面离最优超平面的距离越大,我们的间隔也就越大。对于其他的点 xi xi如果满足 wTxi+b>1 wTxi+b>1,则被分为1类,如果满足满足 wTxi+b<1 wTxi+b<−1,则被分为-1类。即有约束条件:

wTxi+b1wTxi+b1yi=+1yi=1 {wTxi+b⩾1yi=+1wTxi+b⩽−1yi=−1

支持向量到超平面的距离知道后,那么分离的间隔 ρ ρ很明显就为:

ρ=2r=2||w|| ρ=2r∗=2||w|| 这下我们就要通过找到最优的 w w b b来最大化 ρ ρ了,感觉又像回到了逻辑回归或线性回归的例子。但是这里,我们最大化 ρ ρ值需要有条件限制,即: maxw,b2||w||yi(wTxi+b)1, (i=1,..,n) {maxw,b2||w||yi(wTxi+b)⩾1, (i=1,..,n) yi(wTxi+b) yi(wTxi+b)的意思是通过判断 yi yi wTxi+b wTxi+b是否同号来确定分类结果。 接着,为了计算方便,我们把上式最大化 ρ ρ换成: minw,b12||w||2yi(wTxi+b)1, (i=1,..,n) {minw,b12||w||2yi(wTxi+b)⩾1, (i=1,..,n)

这种式子通常我们用拉格朗日乘数法来求解,即:

L(x)=f(x)+αg(x) L(x)=f(x)+∑αg(x) f(x) f(x)是我们需要最小化的目标函数, g(x) g(x)是不等式约束条件,即前面的 yi(wTxi+b)1 yi(wTxi+b)⩾1 α α是对应的约束系数,也叫拉格朗日乘子。为了使得拉格朗日函数得到最优化解,我们需要加入能使该函数有最优化解法的KKT条件,或者叫最优化条件、充要条件。即假设存在一点 x x∗

1.2.2.0.0.1.  L(x) L(x∗) x x∗求导为0

1.2.2.0.0.2.  αigi(x)=0 αigi(x∗)=0,对于所有的 i=1,.....,n i=1,.....,n

这样构建我们的拉格朗日函数为:

L(w,b,α)=12wTwi=1nαi[yi(wTxi+b)1] L(w,b,α)=12wTw−∑i=1nαi[yi(wTxi+b)−1] 以上的KKT条件 αi[yi(wTxi+b)1]=0 αi[yi(wTxi+b)−1]=0表示,只有距离最优超平面的支持向量 (xi,yi) (xi,yi)对应的 α α非零,其他所有点集的 α α等于零。综上所述,引入拉格朗日乘子以后,我们的目标变为: minw,bmaxα0L(w,b,α) minw,bmaxα⩾0L(w,b,α) 即先求得 α α的极大值,再求 w w b b的极小值。可以把该问题转为为等价的凸优化和对偶问题来求解,对于凸优化和对偶问题可以参考《凸优化》这本书,因为该理论可以整整用一本书来介绍了,笔者在这里也只能点到为止了。通过对偶,我们的目标可以又变成: maxα0minw,bL(w,b,α) maxα⩾0minw,bL(w,b,α) 即先求得 w w b b的极小值,在求 α α的极大值。用 L(w,b,α) L(w,b,α) w w b b分别求偏导,并令其等于0: L(w,b,α)w=0 L(w,b,α)b=0 {∂L(w,b,α)∂w=0 ∂L(w,b,α)∂b=0 得: w=ni=1αiyixi ni=1αiyi=0 {w=∑i=1nαiyixi ∑i=1nαiyi=0 把该式代入原来的的拉格朗日式子可得(推导过程省略): W(α)=i=1nαi12i=1nj=1nαiαjyiyjxiTxj W(α)=∑i=1nαi−12∑i=1n∑j=1nαiαjyiyjxiTxj i=1nαiyi=0 ,αi0(i=1,...,n) ∑i=1nαiyi=0 ,αi⩾0(i=1,...,n) W(α) W(α)函数消去了向量 w w和向量 b b,仅剩 α α这个未知参数,只要我们能够最大化 W(α) W(α),就能求出对应的 α α,进而求得 w w b b。对于如何求解 α α,SMO算法给出了完美的解决方案,下一节我们详细讲述。这里我们假设通过SMO算法确定了最优 α α∗,则 w=i=1nαiyixi w∗=∑i=1nαi∗yixi 最后使用一个正的支持向量 xs xs,就可以计算出 b b b=1wTxs b∗=1−w∗Txs

1.3. 软间隔

在4.2节中我们推导了如何计算 w w b b α α,但别忘了以上所有的推导都是在线性可分的条件下进行的,但是现实世界的许多问题并不都是线性可分的,尤其存在许多复杂的非线性可分的情形。如果样本不能被完全线性分开,那么情况就是:间隔为负,原问题的可行域为空,对偶问题的目标函数无限,这讲导致相应的最优化问题不可解。 要解决这些不可分问题,一般有两种方法。第一种是放宽过于严格的间隔,构造软间隔。另一种是运用核函数把这些数据映射到另一个维度空间去解决非线性问题。在本节中,我们首先介绍软间隔优化。 假设两个类有几个数据点混在一起,这些点对最优超平面形成了噪声干扰,软间隔就是要扩展一下我们的目标函数和KKT条件,允许少量这样的噪声存在。具体地说,就要引入松驰变量 ξi ξi来量化分类器的违规行为:

minw,b12||w||2+Cni=1ξiyi(wTxi+b)1ξi,ξi0,(i=1,..,n) {minw,b12||w||2+C∑i=1nξiyi(wTxi+b)⩾1−ξi,ξi⩾0,(i=1,..,n) 参数C用来平衡机器的复杂度和不可分数据点的数量,它可被视为一个由用户依据经验或分析选定的“正则化”参数。松驰变量 ξi ξi的一个直接的几何解释是一个错分实例到超平面的距离,这个距离度量的是错分实例相对于理想的可分模式的偏差程度。对上式的化解,可得: W(α)=i=1nαi12i=1nj=1nαiαjyiyjxiTxj W(α)=∑i=1nαi−12∑i=1n∑j=1nαiαjyiyjxiTxj

i=1nαiyi=0,0αiC(i=1,...,n) ∑i=1nαiyi=0,0⩽αi⩽C(i=1,...,n) 可以看到,松驰变量 ξi ξi没有出现在 W(α) W(α)中,线性可分与不可分的差异体现在约束 αi0 αi⩾0被替换成了约束 0αiC 0⩽αi⩽C。但是,这两种情况下求解 w w b b是非常相似的,对于支持向量的定义也都是一致的。 在不可分情况下,对应的KKT条件为: αi[yi(wTxi+b)1+ξi]=0,(i=1,...,n) αi[yi(wTxi+b)−1+ξi]=0,(i=1,...,n)

1.4. SMO算法

1996年, John Platt发布了一个称为SMO的强大算法,用于训练SVM。 SMO表示序列最小优化(Sequential Minimal Optimization)。 Platt的SMO算法是将大优化问题分解为多个小优化问题来求解,这些小优化问题往往很容易求解,并且对它们进行顺序求解的结果与将它们作为整体来求解的结果是完全一致的。 SMO算法的目标是求出一系列 α α,一旦求出了这些 α α,就很容易计算出权重向量 w w b b,并得到分隔超平面。 SMO算法的工作原理是:每次循环中选择两个 α α进行优化处理。一旦找到一对合适的 α α,那么就增大其中一个同时减小另一个。这里所谓的“合适”就是指两个 α α必须要符合一定的条件,条件之一就是这两个 α α必须要在间隔边界之外,而其第二个条件则是这两个 α α还没有进行过区间化处理或者不在边界上。 对SMO具体的分析如下,在4.3节中我们已经得出了

W(α)=i=1nαi12i=1nj=1nαiαjyiyjxiTxj W(α)=∑i=1nαi−12∑i=1n∑j=1nαiαjyiyjxiTxj

i=1nαiyi=0,0αiC(i=1,...,n) ∑i=1nαiyi=0,0⩽αi⩽C(i=1,...,n)

其中 (xi,yi) (xi,yi)已知,C可以预先设定,也是已知数,现在就是要最大化 W(α) W(α),求得参数 α=[α1,α2,...,αn] α=[α1,α2,...,αn]。SMO算法是一次选择两个 α α进行优化,那我们就选择 α1 α1 α2 α2,然后把其他参数 [α3,α4,...,αn] [α3,α4,...,αn]固定,这样 α1 α1 α2 α2表示为下面的式子,其中 ζ ζ是实数值:

α1y1+α2y2=i=3nαiyi=ζ α1y1+α2y2=−∑i=3nαiyi=ζ 然后用 α2 α2来表示 α1 α1 α1=(ζα2y2)y1 α1=(ζ−α2y2)y1 把上式带入 W(α) W(α)中: W(α)=W(α1,α2,...,αn)=W((ζα2y2)y1,α2,...,αn) W(α)=W(α1,α2,...,αn)=W((ζ−α2y2)y1,α2,...,αn) 省略一系列化解过程后,最后会化解成我们熟悉的一元二次方程,a,b,c均是实数值: W(α2)=a