SVM算法原理及其Matlab应用..docx

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(Support Vector Machine，支持向量机）是一种有监督的机器学习方法，可以学习不同类别的已知样本的特点，进而对未知的样本进行预测。支持向量机的目标就是要根据结构风险最小化原理,构造一个目标函数将两类模式尽可能地区分开。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是总的样本数）　　因此我们的两类分类问题也被我们转化成了它的数学形式，一个带约束的最小值的问题：在这个