SVM算法原理及其Matlab应用

SVM算法及其Matlab应用一、SVM算法..............................................................................................................21.1、线性分类器及其求解...................................................................................21.2、核函数...........................................................................................................71.3、松弛变量.......................................................................................................8二、SVM在多类分类中的应用................................................................................132.1、一对其余法.................................................................................................132.2、一对一.........................................................................................................142.3、DAG方法（有向无环图）.......................................................................142.4、决策树方法.................................................................................................152.5、纠错输出编码法（ECOC）......................................................................15三、SVM在Matlab中的应用...................................................................................163.1、libsvm工具箱和Matlab自带svm算法差异...........................................163.2、libsvm训练函数及结果参数说明.............................................................163.3、libsvm使用技巧.........................................................................................18一、SVM算法SVM(SupportVectorMachine，支持向量机）是一种有监督的机器学习方法，可以学习不同类别的已知样本的特点，进而对未知的样本进行预测。支持向量机的目标就是要根据结构风险最小化原理,构造一个目标函数将两类模式尽可能地区分开。1.1、线性分类器及其求解下面以线性分类器为例，来引入SVM算法的一些概念和处理流程。如图1所示，C1和C2是要区分的两个类别，在二维平面中它们的样本如图。中间的直线就是一个线性分类函数，它可以将两类样本完全分开，就称这些数据是线性可分的，否则称为非线性可分的。设图中线性函数为g(x)=wx+b（x是样本的向量表示），那么当有一个样本xi需要判别的时候，就可以看g(xi)的值，若g(xi)0，就判别为类别C1，若g(xi)0，则判别为类别C2（等于的时候就拒绝判断）。此时也等价于给函数g(x)附加一个符号函数sgn()，即f(x)=sgn[g(x)]是我们真正的判别函数。中间那条直线的表达式是g(x)=0，即wx+b=0，我们也把这个函数叫做分类面。从图可知，中间那条分界线并不是唯一的，把它稍微旋转一下，只要不把两类数据分错，仍然可以达到上面说的效果，稍微平移一下，也可以。那么哪一个函数更好呢？显然必须要先找一个指标来量化“好”的程度，通常使用的都是叫做“分类间隔”的指标。设每一个样本由一个向量（样本特征所组成的向量）和一个标记（标示出这个样本属于哪个类别）组成。如下：Di=(xi,yi)，xi是特征向量（维数很高），yi是分类标记。在二元的线性分类中，这个表示分类的标记只有两个值，1和-1（用来表示属于还是不属于这个类）。有了这种表示法，我们就可以定义一个样本点到某个超平面的间隔：δi=yi(wxi+b)首先注意到如果某个样本属于该类别的话，那么wxi+b0，而yi也大于0；若不属于该类别的话，那么wxi+b0，而yi也小于0，这意味着yi(wxi+b)总是大于0的，而且它的值就等于|wxi+b|（也就是|g(xi)|）现在把w和b进行一下归一化，即用w/||w||和b/||w||分别代替原来的w和b，那么间隔就可以写成这就是解析几何中点xi到直线g(x)=0的距离公式，当用归一化的w和b代替原值之后的间隔有一个专门的名称，叫做几何间隔，几何间隔所表示的正是点到超平面的欧氏距离，我们下面就简称几何间隔为“距离”。以上是单个点到某个超平面的距离（就是间隔，后面不再区别这两个词）定义，同样可以定义一个点的集合（就是一组样本）到某个超平面的距离为此集合中离超平面最近的点的距离。下面这张图更加直观的展示出了几何间隔的现实含义：H是分类面，而H1和H2是平行于H，且过离H最近的两类样本的直线，H1与H，H2与H之间的距离就是几何间隔。几何间隔与样本的误分次数间存在关系：其中的δ是样本集合到分类面的间隔，R=max||xi||i=1,...,n，即R是所有样本中（xi是以向量表示的第i个样本）向量长度最长的值。误分次数一定程度上代表分类器的误差。而从上式可以看出，误分次数的上界由几何间隔决定，而几何间隔越大的解，它的误差上界越小。因此最大化几何间隔成了我们训练阶段的目标。根据以上分析知，间隔：δ=y(wx+b)=|g(x)|，几何间隔：可以看出δ=||w||δ几何。注意到几何间隔与||w||是成反比的，因此最大化几何间隔与最小化||w||在δ固定时完全是一回事。而我们常用的方法也是固定间隔（例如固定为1），寻找最小的||w||。这是一个寻优问题（也叫作一个规划问题），而一个寻优问题最重要的部分是目标函数，我们的目标即找到也可以用来代替。接下来回想一下，我们的问题是有一堆点，可以被分成两类，我们要找出最好的分类面，且||w||0因此需要有约束条件，我们前文提到过把间隔固定为1，这是指把所有样本点中间隔最小的那一点的间隔定为1，即yi[(w·xi)+b]≥1(i=1,2,…,l)（l是总的样本数），也可以写成：yi[(w·xi)+b]-1≥0(i=1,2,…,l)（l是总的样本数）因此我们的两类分类问题也被我们转化成了它的数学形式，一个带约束的最小值的问题：在这个问题中，自变量就是w，而目标函数是w的二次函数，所有的约束条件都是w的线性函数（哎，千万不要把xi当成变量，它代表样本，是已知的），这种规划问题有个很有名气的称呼——二次规划（QuadraticProgramming，QP），而且可以更进一步的说，由于它的可行域是一个凸集，因此它是一个凸二次规划。而且对SVM来说，可行域边界上的点有其特殊意义，实际上是它们唯一的决定了分类超平面，这些点（想象他们就是以前的图中恰好落在H1和H2上的点）就被称为支持向量。根据以上分析知，样本确定了w，即w可以表示为样本的某种组合：w=α1x1+α2x2+…+αnxn式子中的αi是数（又称拉格朗日乘子），而xi是样本点，n是总样本点的个数。因此g(x)的表达式严格的形式应该是：g(x)=w,x+b但是上面的式子还不够好，想像一下图中正样本和负样本的位置，若不动所有点的位置，而只是把其中一个正样本点定为负样本点，三条直线都必须移动。这说明w不仅跟样本点的位置有关，还跟样本的类别有关（也就是和样本的“标签”有关）。因此用下面这个式子表示才算完整：w=α1y1x1+α2y2x2+…+αnynxn（式1）其中的yi就是第i个样本的标签，它等于1或者-1。其实以上式子的那一堆拉格朗日乘子中，只有很少的一部分不等于0（不等于0才对w起决定作用），这部分不等于0的拉格朗日乘子后面所乘的样本点，其实都落在H1和H2上，也正是这部分样本（而不需要全部样本）唯一的确定了分类函数，当然，更严格的说，这些样本的一部分就可以确定，因为例如确定一条直线，只需要两个点就可以，即便有三五个都落在上面，我们也不是全都需要。这部分我们真正需要的样本点，就叫做支持向量！式1也可以用求和符号简写一下：因此原来的g(x)表达式可以写为：注意式子中x才是变量，即需要测试的样本x，而所有的xi统统都是已知的样本。还注意到式子中只有xi和x是向量，因此一部分可以从内积符号中拿出来，得到g(x)的式子为：因此寻优问题从求w变成了求α。这使优化问题少了很大一部分不等式约束。接下来先跳过线性分类器求解的部分，来看看SVM在线性分类器上所做的重大改进——核函数。之前一直在讨论的线性分类器,只能对线性可分的样本做处理。如果提供的样本线性不可分，那线性分类器将失效，是否有某种方法，让线性不可分的数据变得线性可分呢？有！下面用一个二维平面中的分类问题作例子。如下图：横轴上端点a和b之间红色部分里的所有点为正类，两边的黑色部分里的点为负类。显然找不到符合条件的直线将两类点分开，但可以找到一条曲线，例如下图中这条来判断点的所属类别，它的函数表达式可以写为：但它不是一个线性函数，不过，若新建一个向量y和a：这样g(x)就可以转化为f(y)=a,y，即：g(x)=f(y)=ay在任意维度的空间中，这种形式的函数都是一个线性函数，因为自变量y的次数不大于1。这样，原来在二维空间中一个线性不可分的问题，映射到四维空间后？，变成了线性可分的！因此这也形成了我们最初想解决线性不可分问题的基本思路——向高维空间转化，使其变得线性可分。而转化最关键的部分就在于找到x到y的映射方法。遗憾的是，假设x’是由x变换得到的高维变量，在此维度下，问题先行可分，那么只需计算f(x’)=w’,x’+b的值来进行分类，即只关心高维空间里内积w’,x’的值。而从理论上说，x’是经由x变换来的，因此广义上可以把它叫做x的函数，而w’是常量，它是一个低维空间里的常量w经过x与x’之间相同的变换得到的，所以给了一个w和x的值，就有一个确定的f(x’)值与其对应。那么是否能有这样一种函数K(w,x),它接受低维空间的输入值，却能算出高维空间的内积值w’,x’？如果有这样的函数，那么当给了一个低维空间的输入x以后，使g(x)=K(w,x)+b和f(x’)=w’,x’+b这两个函数的计算结果就完全一样，也就不用费力找映射关系了。1.2、核函数上述的K(w,x)确实存在，它被称作核函数（核，kernel），而且只要是满足了Mercer条件的函数，都可以作为核函数。核函数的基本作用就是接受两个低维空间里的向量，能够计算出经过某个变换后在高维空间里的向量内积值。回想我们上节说的求一个线性分类器，它的形式应该是：现在这个就是高维空间里的线性函数，就可以用以下低维空间里的函数来代替。由以上分析又引出两个问题：1．既然有很多的核函数，