线性可分的问题的分析介绍

支持向量机是从两类线性可分情形下的最优分类超平面(Optimal Hyperplane)提出来的。给定一个包含两类样本的训练集,若训练集中所有样本点均可被某超平面正确划分,且距离超平面最近的两类样本点之间距离最大,则称该超平面为最优超平面[98]。

设训练样本集为:

其中x i∈X⊂R n为n维空间中的样本点,y i∈Y＝{1,－1}为所属类别,若y i＝1,i＝1,…,l,则称其对应样本点x i属于正类,否则y i＝1时x i属于负类。

若此问题为线性可分,则存在超平面:

使得训练样本集中的正类样本点分别位于超平面的两侧,并且训练样本集对于线性函数y＝(ω·x)＋b的几何间隔最大,由此构造分类决策函数:

支持向量机处理此类线性可分问题思路如图4.1(a)所示。图中矩点代表正类样本点,圆点代表负类样本点,H为分类线,H 1,H 2分别离分类线最近的正负类样本点所构成的平行于分类线的直线。设H对应的方程为(ω·x)＋b＝0,则H 1,H 2对应的方程则是(ω·x)＋b＝1,(ω·x)＋b＝－1,H 1与H 2之间的距离d即为分类间隔:

要求超平面对所有样本正确分类,等价于求解如下最优问题:

使上式最小化条件成立的样本点被称为支持向量(Support Vector,SV),它们通常只是全体样本中的很少一部分。引入拉格朗日函数对上述问题求解,可以将原分类问题转换为简单的对偶问题:

其中α＝(α1,…,αl)是拉格朗日乘子,I＝{1,…,l}。根据Kuhn-Tucker条件,这个优化问题的解必须满足:(www.xing528.com)

求解上述问题后得到的最优分类函数是

由于非支持向量对于αi均为零,因此式中的求和实际只对支持向量进行,对支持向量的分类等价于对所有训练样本的分类。可以说,支持向量包含了分类的重要信息,这也是支持向量机解决小样本问题的核心思想。

在实际应用中,由于存在离群值或测量误差,无法找到能把两类训练样本完全分离的最优超平面。如图4.1(b)所示,存在少量样本被错分,但可以找到大致将两类训练样本分离的超平面,这类问题被称为近似线性可分情形,通过引入松弛变量将其视作线性分类问题。其思路是对第i个训练点(x i,y i)加入松弛变量ξi≥0,将公式(4.7)中的约束放宽为:

图4.1　线性可分情形下的两分类问题

在近似线性可分情形下,为了保证最大分类间隔的同时减少错分率,需要在目标函数中加入对错分训练样本的惩罚项,以及惩罚参数C,此时,最优分类超平面问题等价于如下凸二次规划问题:

其中C为可调参数,表示对错分类的惩罚程度,C值越大则惩罚力度越大。和线性可分情况类似,引入拉格朗日函数将此类近似线性可分问题转换为简单的对偶问题:

若α∗为问题的一个解,可推知。选择α∗的分量,满足,据此计算出,这时可以构造分类超平面(ω·x)＋b∗＝0,并由此得到分类决策函数:

对于给定未知类别样本点x i,若f(x i)＞0,则x i属于正类;若f(x i)＜0,则x i属于负类。在近似可分情形下,若αi＝0,仍然称其对应的样本点x i为非支持向量;若αi＞0,则称其对应的样本点x i为支持向量。进一步细分,若αi＝C,这时有ξI＞0,对应的样本x i称为界上支持向量;若0＜αi＜C,这时有ξi＝0,对应的样本x i称为界内支持向量。