31、支持向量机(数学建模).pdf

-761-第三十一章 支持向量机 支持向量机是数据挖掘中的一项新技术，是借助于最优化方法来解决机器学习问题的新工具，最初由 V.Vapnik 等人提出，近几年来在其理论研究和算法实现等方面都取得了很大的进展，开始成为克服“维数灾难”和过学习等困难的强有力的手段，它的理论基础和实现途径的基本框架都已形成 § 1 支持向量分类机的基本原理 根据给定的训练集 lllYX,yx,yx,yxT )()}(,),(),{(2211×∈= L ， 其中niRXx =∈ ， X 称为输入空间，输入空间中的每一个点ix 由 n 个属性特征组成， liYyi,,1},1,1{ L=−=∈ 寻找nR 上的一个实值函数 )(xg ，以便用分类函数 )),(sgn()( xgxf = 推断任意一个模式 x 相对应的 y 值的问题为分类问题 1.1 线性可分支持向量分类机 考虑训练集 T ，若nR∈∃ω ， Rb∈ 和正数 ε ，使得对所有使 1=iy 的下标 i 有εω ≥+⋅ bxi)( （这里 )(ix⋅ω 表示向量 ω 和ix 的内积） ， 而对所有使 1−=iy 的下标 i有εω −≤+⋅ bxi)( ，则称训练集 T 线性可分，称相应的分类问题是线性可分的。

记两类样本集分别为 },1|{ TxyxMiii∈==+， },1|{ TxyxMiii∈−==−定义+M 的凸包 )(conv+M 为 ,;,,1,0,1|)(conv11⎭⎬⎫⎩⎨⎧∈=≥===∑∑++==+++NjNjjjjjjMxNjxxM Lλλλ −M 的凸包 )(conv−M 为 .;,,1,0,1|)(conv11⎭⎬⎫⎩⎨⎧∈=≥===∑∑−−==−−−NjNjjjjjjMxNjxxM Lλλλ 其中+N 表示 1+ 类样本集中样本点的个数，−N 表示 1− 类样本集中样本点的个数，定理 1 给出了训练集 T 线性可分与两类样本集凸包之间的关系 定理 1 训练集 T 线性可分的充要条件是， T 的两类样本集+M 和−M 的凸包相离如下图所示 图 1 训练集 T 线性可分时两类样本点集的凸包 证明：①必要性 -762- 若 T 是线性可分的， },1|{ TxyxMiii∈==+， },1|{ TxyxMiii∈−==−，由线性可分的定义可知，存在超平面 }0)(:{ =+⋅∈= bxRxHnω 和 0>ε ，使得 εω ≥+⋅ bxi)( ，+∈∀ Mxi且 εω −≤+⋅ bxi)( ， .−∈∀ Mxi而正类点集的凸包中的任意一点 x 和负类点集的凸包中的任意一点 'x 可分别表示为 ∑+==Niiixx1α 和∑−==Njjjxx1'' β 其中 0,0 ≥≥jiβα 且∑+==Nii11α ，∑−==Njj11β 。

于是可以得到 0))(()(111>=≥+⋅=+⎟⎟⎠⎞⎜⎜⎝⎛⋅=+⋅∑∑∑+++===εαεωααωωNiiNiiiNiiibxbxbx 0))'((')'(111ε ，使得对+M ，−M 的凸包中的任意点 x 和 'x 分别有 εω ≥+⋅ bx)( εω −≤+⋅ bx )'( 显然特别的，对于任意的+∈Mxi，有 εω ≥+⋅ bxi)( ，对于任意的−∈Mxi，有εω −≤+⋅ bxi)( ，由训练集线性可分的定义可知 T 是线性可分的 由于空间nR 中超平面都可以写为 0)( =+⋅ bxω 的形式， 参数 ),( bω 乘以任意一个非零常数后得到的是同一个超平面，定义满足条件 ⎪⎩⎪⎨⎧=+⋅=≥+⋅=1)(min,,1,0))((,,1bxlibxyiliiiωωLL的超平面为规范超平面 定理 2 当训练集样本为线性可分时，存在唯一的规范超平面 0)( =+⋅ bxω ，使得 ⎩⎨⎧−=−≤+⋅=≥+⋅1.1)(1;1)(iiiiybxybxωω（ 1） 证明：规范超平面的存在性是显然的，下证其唯一性 假设其规范超平面有两个： 0)'( =′+⋅ bxω 和 0)"( =′′+⋅ bxω 。

由于规范超平面满足条件 -763-⎪⎩⎪⎨⎧=+⋅=≥+⋅=.1)(min,,,1,0))((,,1bxlibxyiliiiωωLL由第二个条件可知 "' ωω = ， bb ′′=′ ， 或者 "' ωω −= ， bb ′′−=′ . 第一个条件说明 "' ωω −= ， bb ′′−=′ 不可能成立，故唯一性得证 式（ 1）中满足 1)( ±=+⋅ bxiω 成立的ix 称为普通支持向量，对于线性可分的情况来说，只有它们在建立分类超平面的时候起到了作用，普通支持向量通常只占样本集很小的一部分，故而也说明 SVM 具有稀疏性对于 1=iy 类的样本点，其与规范超平面的间隔为 ωωω1)(min1=+⋅=bxiyi， 对于 1−=iy 类的样本点，其与规范超平面的间隔为 ωωω1)(min1=+⋅−=bxiyi， 则普通支持向量间的间隔为ω2最优超平面即意味着最大化ω2如图 2 所示 图 2 线性可分支持向量分类机 1)( ±=+⋅ bxω 称为分类边界，于是寻找最优超平面的问题可以转化为如下的二次规划问题 libxyii,,11))((.t.s21min2L=≥+⋅ωω（ 2） 该问题的特点是目标函数221ω 是 ω 的凸函数，并且约束条件都是线性的。

引入 Lagrange 函数 -764- ∑=+⋅−+=liiiibxybL12)))((1(21),,( ωαωαω 其中+∈=llRT1),( ααα L 为 Lagrange 乘子根据 wolfe 对偶的定义，通过对原问题中各变量的偏导置零可得 ∑==⇒=∂∂liiiixyL10 αωω001=⇒=∂∂∑=iliiybLα 带入 Lagrange 函数化为原问题的 Lagrange 对偶问题 ,l,iαyαxxααyyiliiiliililjjijijiL1,00.t.s)(21max1111=≥=+⋅−∑∑∑∑====αα（ 3） 求解上述最优化问题，得到最优解T**1*),(lααα L= ，计算 ∑==liii*ixy1*αω 由 KKT 互补条件知 0)))((1(***=+⋅− bxyiiiωα 可得，只有当ix 为支持向量的时候，对应的*iα 才为正，否则皆为零选择*α 的一个正分量*jα ，并以此计算 ,)(1∑=⋅−=liji*iij*xxαyyb 于是构造分类超平面 0)(**=+⋅ bxω ，并由此求得决策函数 ,)()(*1bxxyxgliii*i+⋅=∑=α 得到分类函数 ))((sgn)(*1bxxyxfliii*i+⋅=∑=α （ 4） 从而对未知样本进行分类。

1.2 线性支持向量分类机 当训练集 T 的两类样本线性可分时，除了普通支持向量分布在两个分类边界1)( ±=+⋅ bxiω 上外，其余的所有样本点都分布在分类边界以外此时构造的超平面是硬间隔超平面当训练集 T 的两类样本近似线性可分时，即允许存在不满足约束条件 1))(( ≥+⋅ bxyiiω -765-的样本点后，仍然能继续使用超平面进行划分只是这时要对间隔进行“软化” ，构造软间隔超平面简言之就是在两个分类边界 1)( ±=+⋅ bxiω 之间允许出现样本点，这类样本点被称为边界支持向量显然两类样本点集的凸包是相交的，只是相交的部分较小线性支持向量分类机如图 3 所示 图 3 线性支持向量分类机 软化的方法是通过引入松弛变量 lii,,1,0 L=≥ξ 来得到“软化”的约束条件 ,,,11))(( libxyiiiL=−≥+⋅ ξω 当iξ 充分大时，样本点总是满足上述的约束条件，但是也要设法避免iξ 取太大的值，为此要在目标函数中对它进行惩罚，得到如下的二次规划问题 .,,1,0,1))((s.t.,21min12libxyCiiiiliiL=≥−≥+⋅+∑=ξξωξω（ 5） 其中 0>C 是一个惩罚参数。

其 Lagrange 函数如下 ,)1))(((21),,(1112∑∑∑===−+−+⋅−+=liiiliiiiiliibxyCbL ξγξωαξωγαω ,ξ, 其中 0≥iγ ， 0>iξ 原问题的对偶问题如下 ,l,iCyxxααyyiliiiliililjjijijiL1,00.t.s)(21max1111=≤≤=+⋅−∑∑∑∑====αααα（ 6） 求解上述最优化问题，得到最优解T**1*),(lααα L= ，计算 ,1*∑==liii*ixyαω 选择*α 的一个正分量 C*j⇒=iiixgyα 1)(0*=⇒ε ，线性超平面 bxxfy +⋅== )()( ω 沿 y 方向依次上下平移 ε 所扫过的区域构成硬 −ε 带超平面，并且超平面满足 liybxii,,1,)( L=≤−+⋅≤− εωε 当 ε 足够大时，硬 −ε 带超平面总是存在的，而最小能使硬 −ε 带超平面存在的 ε 为minε ，是下列优化问题的最优值 liybxiib,,1,)(s.t.min,L=≤−+⋅≤− εωεεω（ 8） 可见，只要选定的minεε > ，硬 −ε 带超平面就有无限多个，从给定的训练集 T 出发，可以构造正负两类点， },,1,),{(},,1,),{(liyxDliyxDiiiiLL=−==+=ΤΤ−ΤΤ+εε（ 9） 则回归问题转化为线性二分类问题。

由定理 4 可知硬 −ε 带超平面与线性划分之间的关系 -769-图 4 三种情况下+D 和−D 的凸包分布 定理 4 设上述给定的训练集 T 和 0>ε ，考虑由（ 9）定义的集合+D 和−D 则一个超平面 bxxfy +⋅== )()( ω 是硬 −ε 带超平面的充要条件是+D 和−D 的凸包分别位于该超平面的两侧 证明：①必要性 对给定的 0>ε ，若 bxxfy +⋅== )()( ω 是硬 −ε 带超平面，据其定义可知 liybxii,,1,)( L=≤−+⋅≤− εωε 上式可以简单表示为 0)~(0)~(≤−−−≥−−+beAeybeAeyωεωε（ 10） 其中Τ= ),,(~1 lyyy L ，Τ= )1,,1( Le ，Τ= ),,(1 lxxA L ，+D 的凸包中的任意一点都可以表示为 ∑=ΤΤΤΤ+==liiiiyxyxuttt1),(),( ε 其中Τ= ),,(1 luuu L ，且满足∑==liiu11， 0≥iu ， li ,,1L= ，由（ 10）的第一式可知 .0)()ˆ()( ≥−⋅−+=−⋅−ΤΤΤbuAueybttxyωεω （ 11） 类似的，−D 的凸包的任意一点都可以表示为 ∑=ΤΤΤΤ−==liiiiyxyxvsss1),(),( ε 其中Τ= ),,(1 lvvv L ，且满足∑==liiv11， 0≥iv ， li ,,1L= ，由（ 10）的第二式可知 0)()ˆ()( ≥−⋅−−=−⋅−ΤΤΤbuAueybssxyωεω （ 12） 由（ 11）和（ 12）可知+D 和−D 的凸包分别位于该超平面的两侧。

②充分性： 任取满足 1=Τue ， 0≥u 的凸组合系数向量 u ，则可以得到+D 中的一点ΤΤΤΤ+ ))~(,)(( ueyuA ε ，与此对应，选择满足 1=Τve ， vAuAΤΤ= -770- 的凸组合系数向量 v，则可以得到−D 中的一点 ΤΤΤΤΤΤΤΤ−=− ))~(,)(())~(,)(( veyuAveyvA εε 将该点与上述+D 中的点比较，他们的前 n个分量相同，同时超平面 bxxfy +⋅== )()( ω 分离两个集合+。