31第三十一章支持向量机

第三十一章支持向量机支持向量机是数据挖掘中的一项新技术，是借助于最优化方法来解决机器学习问题的新工具，最初由V.Vapnik等人提出，近几年来在其理论研究和算法实现等方面都取得了很大的进展，开始成为克服“维数灾难”和过学习等困难的强有力的手段，它的理论基础和实现途径的基本框架都已形成。§1支持向量分类机的基本原理根据给定的训练集T{(x1,y1),(x2,y2),L,(xl,yl)}∈(XY)l，其中xi∈XRn，X称为输入空间，输入空间中的每一个点xi由n个属性特征组成，yi∈Y{−1,1},i1,L,l。寻找Rn上的一个实值函数g(x)，以便用分类函数f(x)sgn(g(x)),推断任意一个模式x相对应的y值的问题为分类问题。1.1线性可分支持向量分类机考虑训练集T，若∃ω∈Rn，b∈R和正数ε，使得对所有使yi1的下标i有(ω⋅xi)b≥ε（这里(ω⋅xi)表示向量ω和xi的内积），而对所有使yi−1的下标i有(ω⋅xi)b≤−ε，则称训练集T线性可分，称相应的分类问题是线性可分的。记两类样本集分别为M{xi|yi1,xi∈T}，M−{xi|yi−1,xi∈T}。定义M的凸包conv(M)为NNconv(M)x∑λjxj|∑λj1,j1j1M−的凸包conv(M−)为N−N−conv(M−)x∑λjxj|∑λj1,j1j1λj≥0,j1,L,N;xj∈M,λj≥0,j1,L,N−;xj∈M−.其中N表示1类样本集中样本点的个数，N−表示−1类样本集中样本点的个数，定理1给出了训练集T线性可分与两类样本集凸包之间的关系。定理1训练集T线性可分的充要条件是，T的两类样本集M和M−的凸包相离。如下图所示图1训练集T线性可分时两类样本点集的凸包证明：①必要性-762-若T是线性可分的，M{xi|yi1,xi∈T}，M−{xi|yi−1,xi∈T}，由线性可分的定义可知，存在超平面H{x∈Rn:(ω⋅x)b0}(ω⋅xi)b≥ε，∀xi∈M且(ω⋅xi)b≤−ε，∀xi∈M−.而正类点集的凸包中的任意一点x和负类点集的凸包中的任意一点x'可分别表示为NN−x∑αixi和x'∑βjx'ji1j1NN−其中αi≥0,βj≥0且∑αi1，∑βj1。i1j1于是可以得到(ω⋅(ω⋅NNb∑αi((ω⋅xix)bω⋅∑αixii1i1N−N−b∑βj((ω⋅x')bω⋅∑βjx'jj1j1)x'jNb)≥ε∑αiε0i1N−)b)≤−ε∑βj−ε0j1由此可见，正负两类点集的凸包位于超平面(ω⋅x)b0的两侧，故两个凸包相离。②充分性设两类点集M，M−的凸包相离。因为两个凸包都是闭凸集，且有界，根据凸集强分离定理，可知存在一个超平面H{x∈Rn:(ω⋅x)b0}强分离这两个凸包，即存在正数ε0，使得对M，M−的凸包中的任意点x和x'分别有(ω⋅x)b≥ε(ω⋅x')b≤−ε显然特别的，对于任意的xi∈M，有(ω⋅xi)b≥ε，对于任意的xi∈M−，有(ω⋅xi)b≤−ε，由训练集线性可分的定义可知T是线性可分的。由于空间Rn中超平面都可以写为(ω⋅x)b0的形式，参数(ω,b)乘以任意一个非零常数后得到的是同一个超平面，定义满足条件y((ω⋅x)b)iimin(ω⋅x)ii1,L,l≥0,i1,L,lb1的超平面为规范超平面。定理2当训练集样本为线性可分时，存在唯一的规范超平面(ω⋅x)b0，使得(ω⋅xi)b≥1yi1;（1）yi−1.(ω⋅xi)b≤−1证明：规范超平面的存在性是显然的，下证其唯一性。假设其规范超平面有两个：(ω'⋅x)b′0和(ω⋅x)b′′0。由于规范超平面满足条件-763-和ε0，使得y((ω⋅x)b)iimin(ω⋅x)ii1,L,l≥0,i1,L,l,b1.由第二个条件可知ω'ω，b′b′′，或者ω'−ω，b′−b′′.第一个条件说明ω'−ω，b′−b′′不可能成立，故唯一性得证。式（1）中满足(ω⋅xi)b1成立的xi称为普通支持向量，对于线性可分的情况来说，只有它们在建立分类超平面的时候起到了作用，普通支持向量通常只占样本集很小的一部分，故而也说明SVM具有稀疏性。对于yi1类的样本点，其与规范超平面的间隔为min(ω⋅xi)b1，ωωyi1对于yi−1类的样本点，其与规范超平面的间隔为min(ω⋅xi)b1，ωωyi1则普通支持向量间的间隔为2。最优超平面即意味着最大化2。如图2所示ωω图2线性可分支持向量分类机(ω⋅x)b1称为分类边界，于是寻找最优超平面的问题可以转化为如下的二次规划问题min1ω22（2）s.t.yi((ω⋅xi)b)≥1i1,L,l该问题的特点是目标函数12ω2是ω的凸函数，并且约束条件都是线性的。引入Lagrange函数-764-1lL(ω,b,α)ω2∑αi(1−yi((ω⋅xi)b))2i1其中α(α1L,αl)T∈Rl为Lagrange乘子。根据wolfe对偶的定义，通过对原问题中各变量的偏导置零可得∂L0⇒ω∑αiyixil∂ωi1∂Ll0⇒∑αiyi0∂bi1带入Lagrange函数化为原问题的Lagrange对偶问题α1llijijijli−∑∑)∑max2i1j1yyαα(x⋅xαi1ls.t.∑yiαi0（3）i1αi≥0,i1,L,l求解上述最优化问题，得到最优解α*(α1*,Lαl*)T，计算ω*∑αi*yixii1l由KKT互补条件知αi*(1−yi((ω*⋅xi)b*))0可得，只有当xi为支持向量的时候，对应的αi*才为正，否则皆为零。选择α*的一个正分量α*j，并以此计算lb*yj−∑yiαi*(xi⋅xj),i1于是构造分类超平面(ω*⋅x)b*0，并由此求得决策函数lg(x)∑αi*yi(xi⋅x)b*,i1得到分类函数lf(x)sgn(∑αi*yi(xi⋅x)b*)（4）i1从而对未知样本进行分类。1.2线性支持向量分类机当训练集T的两类样本线性可分时，除了普通支持向量分布在两个分类边界(ω⋅xi)b1上外，其余的所有样本点都分布在分类边界以外。此时构造的超平面是硬间隔超平面。当训练集T的两类样本近似线性可分时，即允许存在不满足约束条件yi((ω⋅xi)b)≥1-765-的样本点后，仍然能继续使用超平面进行划分。只是这时要对间隔进行“软化”，构造软间隔超平面。简言之就是在两个分类边界(ω⋅xi)b1之间允许出现样本点，这类样本点被称为边界支持向量。显然两类样本点集的凸包是相交的，只是相交的部分较小。线性支持向量分类机如图3所示。图3线性支持向量分类机软化的方法是通过引入松弛变量ξi≥0,i1,L,l来得到“软化”的约束条件yi((ω⋅xi)b)≥1−ξii1,L,l,当ξi充分大时，样本点总是满足上述的约束条件，但是也要设法避免ξi取太大的值，为此要在目标函数中对它进行惩罚，得到如下的二次规划问题1lminω2C∑ξi,2i1s.t.yi((ω⋅xi)b)≥1−ξi,（5）ξi≥0,i1,L,l.其中C0是一个惩罚参数。其Lagrange函数如下1lllL(ω,b,ξ,α,γ)ω2C∑ξi−∑αi(yi((ω⋅xi)b)−1ξi)−∑γiξi,2i1i1i1其中γi≥0，ξi0。原问题的对偶问题如下α1llijijijli∑∑)∑αmax−2i1j1yyαα(x⋅xi1ls.t.∑yiαi0（6）i10≤αi≤C,i1,L,l求解上述最优化问题，得到最优解α*(α1*,Lαl*)T，计算ω*∑αi*yixi,i1l选择α*的一个正分量0α*jC，并以此计算-766-