SVM算法原理及其Matlab应用

1、SVM 算法及其 Matlab 应用、SVM 算法 2.1.1、线性分类器及其求解 2.1.2、核函数 7.1.3、松弛变量 8.、 SVM 在多类分类中的应用 1.32.1、一对其余法 1.3.2.2、一对一 1.4.2.3、DAG 方法（有向无环图） 1.42.4、决策树方法 1.5.2.5、纠错输出编码法（ ECOC） 1.5、SVM 在 Matlab 中的应用 1.63.1、libsvm 工具箱和 Matlab 自带 svm 算法差异 1. 63.2、libsvm 训练函数及结果参数说明 1.63.3、libsvm 使用技巧 1.8一、SVM算法SVM(Support Vector M

2、achine,支持向量机)是一种有监督的机器学习方法， 可以学习不同类别的已知样本的特点， 进而对未知的样本进行预测。支持向量机 的目标就是要根据结构风险最小化原理，构造一个目标函数将 两类模式尽可能地 区分开。1.1、线性分类器及其求解下面以线性分类器为例，来引入 SVM算法的一些概念和处理流程。如图 1 所示，C1和C2是要区分的两个类别，在二维平面中它们的样本如图。 中间的直 线就是一个线性分类函数，它可以将两类样本完全分开，就称这些数据是线性可 分的，否则称为非线性可分的。设图中线性函数为g(x)=wx+b (x是样本的向量表示)，那么当有一个样本xi需要判别的时候，就可以看g(xi)

3、的值，若g(xi)0，就判别为类别C1,若g(xi)0，而yi也大于0; 若不属于该类别的话，那么 wxi+bvO，而yi也小于0，这意味着yi(wxi+b)总是 大于0的，而且它的值就等于|wxi+b| (也就是|g(xi)|)现在把w和b进行一下归一化，即用w/|w|和b/|w|分别代替原来的w和b， 那么间隔就可以写成这就是解析几何中点xi到直线g(x)=O的距离公式，当用归一化的 w和b代 替原值之后的间隔有一个专门的名称，叫做几何间隔，几何间隔所表示的正是点 到超平面的欧氏距离，我们下面就简称几何间隔为 距离”以上是单个点到某个 超平面的距离(就是间隔，后面不再区别这两个词)定义，同

4、样可以定义一个点 的集合(就是一组样本)到某个超平面的距离为此集合中离超平面最近的点的距 离。下面这张图更加直观的展示出了几何间隔的现实含义：H是分类面，而H1和H2是平行于H，且过离H最近的两类样本的直线,H1与H , H2与H之间的距离就是几何间隔。几何间隔与样本的误分次数间存在关系：其中的S是样本集合到分类面的间隔，R=max |xi| i=1,.,n ,即R是所有样 本中(xi是以向量表示的第i个样本)向量长度最长的值。误分次数一定程度上 代表分类器的误差。而从上式可以看出，误分次数的上界由几何间隔决定，而几何间隔越大的解，它的误差上界越小。因此最大化几何间隔成了我们训练阶段的 目标。

5、根据以上分析知，间隔：S =y(wx+b)=|g(x)|，几何间隔：可以看出S =|w|几何。注意到几何间隔与|w|是成反比的，因此最大化几何间 隔与最小化|w|在 S固定时完全是一回事。而我们常用的方法也是固定间隔(例 如固定为1)，寻找最小的这是一个寻优问题(也叫作一个规划问题)，而一个寻优问题最重要的部分-(I .Imin -| W|P是目标函数，我们的目标即找到inRllfT II 11也可以用来代替。接下来回想一下，我们的问题是有一堆点，可以被分成两类，我们要找出最 好的分类面，且|w|冃)因此需要有约束条件，我们前文提到过把间隔固定为1,这是指把所有样本 点中间隔最小的那一点的间隔

6、定为1，即yi(w xi)+b 1 (i=1,2,(1是总的样本数)，也可以写成：yi(w xi)+b- 1 0 (i=1,2,1) l 是总的样本数)因此我们的两类分类问题也被我们转化成了它的数学形式，一个带约束的最小值的问题：atfbjcdfcoi0一一一QQ星胖本数在这个问题中，自变量就是 w，而目标函数是w的二次函数，所有的约束条件都是w的线性函数(哎，千万不要把 xi当成变量，它代表样本，是已知的)，这种规划问题有个很有名气的称呼二次规划(Quadratic Programmi ng QP)，而且可以更进一步的说，由于它的可行域是一个凸集，因此它是一个凸二次规划 而且对SVM来说，可

7、行域边界上的点有其特殊意义，实际上是它们唯一的决定了分类超平面，这些点（想象他们就是以前的图中恰好落在H1和H2上的点）就被称为支持向量。根据以上分析知，样本确定了 w，即w可以表示为样本的某种组合：W=aixi+ 0（2X2 + aXn式子中的a是数（又称拉格朗日乘子），而 xi是样本点，n是总样本点的个数。 因此g（x）的表达式严格的形式应该是：g（x）=+b但是上面的式子还不够好，想像一下图中正样本和负样本的位置， 若不动所 有点的位置，而只是把其中一个正样本点定为负样本点，三条直线都必须移动。 这说明w不仅跟样本点的位置有关，还跟样本的类别有关（也就是和样本的标 签”有关）。因此用下面

8、这个式子表示才算完整：w=aiyixi+ay2X2+ + aynXn （式 1）其中的yi就是第i个样本的标签，它等于i或者-i。其实以上式子的那一堆 拉格朗日乘子中，只有很少的一部分不等于 0 （不等于0才对w起决定作用）， 这部分不等于0的拉格朗日乘子后面所乘的样本点，其实都落在 Hi和H2 上, 也正是这部分样本（而不需要全部样本）唯一的确定了分类函数，当然，更严格 的说，这些样本的一部分就可以确定，因为例如确定一条直线，只需要两个点就 可以，即便有三五个都落在上面，我们也不是全都需要。这部分我们真正需要的 样本点，就叫做 支持向量！式i也可以用求和符号简写一下：W二丫匕輕）i=i因此原

9、来的g（x）表达式可以写为：ITJHI注意式子中x才是变量，即需要测试的样本x，而所有的Xi统统都是已知的 样本。还注意到式子中只有Xi和X是向量，因此一部分可以从内积符号中拿出来， 得到g（x）的式子为： +A （式2）11因此寻优问题从求W变成了求a这使优化问题少了很大一部分不等式约束。 接下来先跳过线性分类器求解的部分，来看看SVM在线性分类器上所做的 重大改进核函数。之前一直在讨论的线性分类器，只能对线性可分的样本做处理。如果提供的 样本线性不可分，那线性分类器将失效，是否有某种方法，让线性不可分的数据 变得线性可分呢？有！下面用一个二维平面中的分类问题作例子。如下图：横轴上端点a和b

10、之间红色部分里的所有点为正类，两边的黑色部分里的点 为负类。显然找不到符合条件的直线将两类点分开，但可以找到一条曲线，例如 下图中这条来判断点的所属类别，它的函数表达式可以写为：但它不是一个线性函数，不过，若新建一个向量y和a：这样 g(x)就可以转化为 f(y)=，即：g(x)=f(y)=ay在任意维度的空间中，这种形式的函数都是一个线性函数，因为自变量y的次数不大于1。这样，原来在二维空间中一个线性不可分的问题， 映射到四维 空间后？，变成了线性可分的！因此这也形成了我们最初想 解决线性不可分问题 的基本思路一一向高维空间转化，使其变得线性可分。而转化最关键的部分就在于找到 x到y的映射方

11、法。遗憾的是，假设x是由 x变换得到的高维变量，在此维度下，问题先行可分，那么只需计算 f(x=+b的值来进行分类，即只关心高维空间里内积 的值。而从理 论上说，x是经由x变换来的，因此广义上可以把它叫做x的函数，而w是常量，它是一个低维空间里的常量 w经过x与x之间相同的变换得到的，所以给 了一个w和x的值，就有一个确定的f(x 值与其对应。那么是否能有这样一种 函数K(w,x),它接受低维空间的输入值，却能算出高维空间的内积值Vwx ?如果有这样的函数，那么当给了一个低维空间的输入x以后，使g(x)=K(w,x)+b和f(x =+b这两个函数的计算结果就完全一样，也就不用费力找映射关系了。

12、1.2、核函数上述的K(w,x)确实存在，它被称作 核函数(核，kernel)，而且只要是满足 了 Mercer条件的函数，都可以作为核函数。核函数的基本作用就是接受两个低 维空间里的向量，能够计算出经过某个变换后在高维空间里的向量内积值。回想我们上节说的求一个线性分类器，它的形式应该是：H1=1现在这个就是高维空间里的线性函数，就可以用以下低维空间里的函数来代 替。由以上分析又引出两个问题：1. 既然有很多的核函数，针对具体问题该怎么选择？2. 如果使用核函数向高维空间映射后，问题仍然是线性不可分的，那怎么 办？对第一个问题，即核函数的选择，现在还缺乏指导原则！通常而言，径向基核函数(RBF

13、)核是合理的首选。这个核函数将样本非线 性地映射到一个更高维的空间，与线性核不同，它能够处理分类标注和属性的非 线性关系。并且，线性核是RBF的一个特例(Keerthi and Lin 2003)。同时，Sigmoid 核的表现很像一定参数的 RBF核(Lin and Link 2003)。第二个原因，超参数的 数量会影响到模型选择的复杂度，而多项式核比RBF核有更多的超参数。最后， RBF核有更少的数值复杂度。当然，也存在一些情形RBF核是不适用的。特别地，当特征维数非常大的时候，很可能只能适用线性核。1.3、松弛变量对上述第二个问题，可以用松弛变量来解决，下面对松弛变量进行详细描述。现在我

14、们已经把一个本来线性不可分的文本分类问题，通过映射到高维空间 而变成了线性可分的。就像下图这样：圆形和方形的点各有成千上万个，现在想象我们有另一个训练集，只比原先 这个训练集多了一个样本，映射到高维空间以后，也就多了一个样本点，但是这 个样本的位置如下图，就是图中黄色那个点，它是方形的，因而它是负类的一个 样本，这单独的一个样本，使得原本线性可分的问题变成了线性不可分的。 这样 类似的问题(仅有少数点线性不可分)叫做 近似线性可分”的问题。以我们人类的常识来判断，这个样本点很可能是噪声，我们会简单的忽略这 个样本点，仍然使用原来的分类器，其效果丝毫不受影响。但这种对噪声的容错性是人的思维带来的

15、， 我们的程序可没有。由于我们原 本的优化问题的表达式中，确实要考虑所有的样本点，在此基础上寻找正负类之 间的最大几何间隔，而几何间隔本身代表的是距离，是非负的，像上面这种有噪 声的情况会使得整个问题无解。这种解法其实也叫做 硬间隔”分类法，因为他硬 性的要求所有样本点都满足和分类平面间的距离必须大于某个值。因此由上面的例子中也可以看出， 硬间隔的分类法其结果容易受少数点的控制。 但解决方法也很明显，就是允许一些点到分类平面的距离不满足原先的要求。由于不同的训练集各点的间距尺度不太一样， 因此用间隔（而不是几何间隔）来衡 量有利于我们表达形式的简洁。我们原先对样本点的要求是：（）+*1 （i=

16、12 是样本数）意思是说离分类面最近的样本点函数间隔也要比 1大。如果要引入容错性， 就给1这个硬性的阈值加一个松弛变量，即允许对“i-. -1 w |7jJO叫）+血1一壬 0 12*. J）馄样本BQ|w就是我们的目标函数（当然系数可有可无），希望它越小越好，因而损失就 必然是一个能使之变大的量（能使它变小就不叫损失了，我们本来就希望目标函 数值越小越好）。那如何来衡量损失，有两种常用的方式，有人喜欢用J-1而有人喜欢用J-1其中I都是样本的数目。两种方法没有大的区别。如果选择了第一种，得到 的方法的就叫做二阶软间隔分类器，第二种就叫做一阶软间隔分类器。把损失加 入到目标函数里的时候，就需

17、要一个惩罚因子（cost，也就是libSVM的诸多参 数中的C）,原来的优化问题就变成了下面这样：min 和伙+4subject to 北讥R 3样本0 （Si）这个式子有这么几点要注意：（1） 并非所有的样本点都有一个松弛变量与其对应。实际上只有 离群点” 才有，或者也可以这么看，所有没离群的点松弛变量都等于 0 （对负类来说，离 群点就是在前面图中，跑到 H2右侧的那些负样本点，对正类来说，就是跑到H1左侧的那些正样本点）。（2）松弛变量的值实际上标示出了对应的点到底离群有多远，值越大，点 就越远。（3）惩罚因子C决定了你有多重视离群点带来的损失，显然当所有离群点 的松弛变量的和一定时，你

18、定的 C越大，对目标函数的损失也越大，此时就暗示着你非常不愿意放弃这些离群点，最极端的情况是你把C定为无限大，这样只要稍有一个点离群，目标函数的值马上变成无限大，马上让问题变成无解，这 就退化成了硬间隔问题。（4）惩罚因子C不是一个变量，整个优化问题在解的时候，C是一个你必须事先指定的值，指定这个值以后，解一下，得到一个分类器。（5）尽管加了松弛变量这么一说，但这个优化问题仍然是一个优化问题（汗， 这不废话么），解它的过程比起原始的硬间隔问题来说， 没有任何更加特殊的地 方。从大的方面说优化问题解的过程，就是先试着确定一下w，也就是确定了前 面图中的三条直线，这时看看间隔有多大，又有多少点离群

19、，把目标函数的值算 一算，再换一组三条直线（你可以看到，分类的直线位置如果移动了，有些原来 离群的点会变得不再离群，而有的本来不离群的点会变成离群点），再把目标函 数的值算一算，如此往复（迭代），直到最终找到目标函数最小时的w。至此一个比较完整的支持向量机框架就有了，简单说来，支持向量机就是使用了核函数的软间隔线性分类法。接下来讨论一下惩罚因子C。回头看一眼引入了松弛变量以后的优化问题：msnbjectto为0叫）彳可王&口 J馄檢忖R）（式1）注意其中C表征了你有多么重视离群点，C越大越重视，越不想丢掉它们。 这个式子是以前做SVM的人写的，但没有任何规定说必须对所有的松弛变量都 使用同一个

20、惩罚因子，我们完全可以给每一个离群点都使用不同的 C，这时就意 味着你对每个样本的重视程度都不一样。当然实际使用的时候并没有这么极端， 但一种很常用的变形可以用来解决分类问题中样本的偏斜”问题。样本的偏斜问题，也叫数据集偏斜（unbalaneed，它指的是参与分类的两 个类别（也可以指多个类别）样本数量差异很大。比如说正类有 10000个样本, 而负类只给了 100个，这会引起的问题显而易见，可以看看下面的图：o方形的点是负类。H , Hi, H2是根据给的样本算出来的分类面，由于负类的 样本很少很少，所以有一些本来是负类的样本点没有提供， 比如图中两个灰色的 方形点，如果这两个点有提供的话，

21、那算出来的分类面应该是 H, H2,和Hi,他 们显然和之前的结果有出入，实际上负类给的样本点越多，就越容易出现在灰色 点附近的点，我们算出的结果也就越接近于真实的分类面。 但现在由于偏斜的现 象存在，使得数量多的正类可以把分类面向负类的方向 推”因而影响了结果的 准确性。对付数据集偏斜问题的方法之一就是在惩罚因子上作文章，想必大家也猜到了, 那就是给样本数量少的负类更大的惩罚因子， 表示我们重视这部分样本（本来数 量就少，再抛弃一些，那人家负类还活不活了），因此我们的目标函数中因松弛 变量而损失的部分就变成了：G刀 2一刀J4=1其中i=1p都是正样本，j=p+1p+q都是负样本。libSV

22、M这个算法包在解 决偏斜问题的时候用的就是这种方法。二、SVM在多类分类中的应用从SVM的那几张图可以看出来，SVM是一种典型的两类分类器，即它只 回答属于正类还是负类的问题。而现实中要解决的问题，往往是多类的问题。如 何由两类分类器得到多类分类器，就是一个值得研究的问题。SVM多类分类方法的实现根据其指导思想大致有两种：(1) 通过对前面所述支持向量分类机中的原始最优化问题的适当改变，使得它 能同时计算出所有多类分类决策函数，从而一次性”地实现多类分类。原 始问题可以改写为：mintl/2S I 1叫1 F +匚左工歆S* T* (Wf x,) + E 步* 出)+ 虬 + 2 *er式中：

23、Z = 1为样本数址=1,2严MM为类别数量出这样就可得到决策函数；Ax)-maxL( -i小十阴.判别结果为笫扌类。(2) 将多类问题分解为一系列SVM可直接求解的两类问题，基于这一系列SVM求解结果得出最终判别结果。虽然第(1)种指导思想看起来简单，但由于它的最优化问题求解过程太复杂， 计算量太大，实现起来比较困难，因此未被广泛应用。而基于第(2)种指导思想的SVM多类分类方法主要有5种。2.1、一对其余法一对余类法(One versus rest OVR)是最早出现也是目前应用最为广泛的方法 之一，其步骤是构造k个两类分类机(设共有k个类别)，其中第i个分类机把第 i类同余下的各类划分开

24、，训练时第i个分类机取训练集中第i类为正类，其余类 别点为负类进行训练。判别时，输入信号分别经过k个分类机共得到k个输出值 fi(x)=sgn(gi(x)，若只有一个+1出现，则其对应类别为输入信号类别；实际情况 下构造的决策函数总是有误差的，若输出不只一个+1,或者没有一个输出为+1, 则比较g(x)输出值，最大者对应类别为输入的类别。这种方法的优点是，对k类问题，只需要训练k个两类分类支持向量机，故 其所得到的分类函数的个数较少，其分类速度相对较快，但容易出现样本偏斜问 题。2.2、一对一该方法在每两类间训练一个分类器，因此对于一个k类问题，将有k(k-1)/2个分类函数。当对一个未知样本

25、进行分类时，每个分类器都对其类别进行判断.并 为相应的类别投上一票”最后得票最多的类别即作为该未知样本的类别。决策 阶段采用投票法，可能存在多个类的票数相同的情况，从而使未知样本同时属于 多个类别，影响分类精度。2.3、DAG方法(有向无环图)DAG-SvMS是由Platt提出的决策导向的循环图DAG导出的，是针对 一对一 SvMS存在误分，拒分现象提出的。这种方法的训练过程类似于一对一”方法，k类别问题需要求解k(k-1)/2个支持向量机分类器，这些分类器构成一个有向 无环图。该有向无环图中含有 k(k-1)/2个内部节点和k个叶结点，每个节点对 应一个二类分类器。图2四类何 DAGSVM结

26、构图DAG-SVMS简单易行，只需要使用k-1个决策函数即可得出结果，较 一对 一方法提高了测试速度，而且不存在误分、拒分区域；另外，由于其特殊的结 构，故有一定的容错性，分类精度较一般的二叉树方法高。然而，由于存在自上 而下的误差积累”现象是层次结构固有弊端，故 DAG-SVMS也逃脱不掉。即如 果在某个结点上发生了分类错误，则会把分类错误延续到该结点的后续结点上.2.4、决策树方法决策树的基本思想是从根节点开始，采用某种方法将该节点所包含的类别划 分为两个子类，然后再对两个子类进一步划分，如此循环，直到子类中只包含一 个类别为止，这样，就得到了一个倒立的二叉树。最后，在二叉树各决策节点训

27、练支持向量机分类器，实现对识别样本的分类。决策树支持向量机多分类方法有 很多种，不同方法的主要区别在于设计树结构的方法不同。SV1IJ（b怡二观冊缺二观完全二叉树结构分类时使用的平均分类器数目为Iog2k，偏二叉树使用的平均分类器数为（k+1）/2-1 /k，具有其他层次结构的二叉树使用的分类器平均值介 于二者之间。完全二叉树分类时所需要的分类器数目最少，因此具有较少支持向量的完全二叉树的分类器速度也是较快的。2.5、纠错输出编码法（ECOC）对于K类分类问题，可以根据不同方法构造一系列的两类分类问题，对于每个两类分类问题可以建立一决策函数。共得到L个决策函数，如果这些决策函数完全正确，K类中

28、的每一类都对应一个元素为-1或+1的长度为L的数列， 按照K类中的第一类、第二类，第K类的顺序，把这些数列排列起来，便 可得到一个K行L列的编码矩阵，若要判断一个测试输入点的归属，首先用所 得到的L个决策函数，得到一个元素为-I或I的长度为L的数列，然后将此数列 与先前得到矩阵比较，相应于矩阵中有一行且仅有一行向与此数列相同，这个行 数就是输入点的归属类；若矩阵中没有一行与该数列相同，可以通过计算汉明距 离找出最近的一行，改行对应的类别即为该点的类别。三、 SVM 在 Matlab 中的应用Matlab有自带的支持向量机算法，但存在一定的局限性，因此安装了台湾大 学林智仁(Lin Chih-J

29、en教授等开发的SVM模式识别与回归的软件包libsvm。3.1、l i bsvm 工具箱和 Matlab 自带 svm 算法差异下面先对比一下 libsvm 工具箱和 Matlab 自带的 svm 算法的差异：(1) MATLAB 自带的 svm 实现函数仅有的模型是 C-SVC(C-support vector classification)；而libsvm工具箱有 C-SVC (正负样本采用不同的代价权值) ， nu-SVC(nu-support vector classification), one-class SVM(distribution estimation), epsilon

30、-SVR(epsilon-support vector regression), nu-SVR(nu-support vector regressio n等多种模型可供使用。(2) MATLAB 自带的 svm 实现函数仅支持分类问题，不支持回归问题；而 libsvm 不仅支持分类问题，亦支持回归问题。(3) MATLAB自带的svm实现函数仅支持二分类问题，多分类问题需按照多 分类的相应算法编程实现；而 libsvm 采用 1v1 算法支持多分类 。(4) MATLAB自带的svm实现函数采用RBF核函数时无法调节核函数的参 数gamma,貌似仅能用默认的；而libsvm可以进行该参数的调节

31、。(5) libsvm中的二次规划问题的解决算法是 SMO;而MATLAB自带的svm实现函数中二次规划问题的解法有三种可以选择：经典二次方法；SMO;最小二乘。3.2、libsvm 训练函数及结果参数说明libsvm在训练model的时候，需要用到svmtrain函数，调用方法如下：m = svmtrain(y, x, -s 0 -t 2 -c 1 -g 1)；其中 Y 为训练样本的类别， X 为对应的训练样 本， -s 0 -t 2 -c 1 -g 1 是对参数的设置，下面进行详细说明：( 1) -s svm 类型： SVM 设置类型 (默认 0)0 - C-SVC1 -v-SVC2 -

32、一类 SVM3 - e -SVR4 - v-SVR（2）-t 核函数类型：核函数设置类型 （默认 2）0 -线性：uv1 -多项式：（r*uv + coefOdegree2 -RBF 函数：exp（-gamma|u-v$2）3 -sigmoid: tanh（r*uv + coefO）（3）-d degree核函数中的degree设置（针对多项式核函数）（默认3）-g r（gama）:核函数中的gamma函数设置（针对多项式/rbf/sigmoid核函 数）（默认 1/ k）-r coef0:核函数中的coef0设置（针对多项式/sigmoid核函数）（默认0） -c cost:设置C-SVC,

33、 e -SVR和v-SVR的参数（损失函数）（默认1）-n nu:设置v-SVC , 类SVM和v- SVR的参数（默认0.5）-p p：设置e -SVR中损失函数p的值（默认0.1）-m cachesize设置cache内存大小，以 MB为单位（默认40）-e eps设置允许的终止判据（默认0.001）-h shrinking :是否使用启发式，0或1（默认1）-wi weight :设置第几类的参数 C为weight*C（C-SVC中的C）（默认1）-v n: n-fold 交互检验模式， n 为 fold 的个数，必须大于等于 2 其中 -g 选项中的 k 是指输入数据中的属性数。 option -v 随机地将数据剖分 为 n 部。通过训练得到的模型 m 中包含参数的意义如下：struct svm_modelstruct svm_parameter param;/* parameter */int nr_class; /* number of classes, = 2 in regression/one class svm */int l;