支持向量机原理

1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业第3章 支持向量机基础By Dean 支持向量机（Support Vector Machies）是由Vapnik等人于1995年提出来的。之后随着统计理论的发展，支持向量机也逐渐受到了各领域研究者的关注，在很短的时间就得到很广泛的应用。支持向量机是建立在统计学习理论的VC维理论和结构风险最小化原理基础上的，利用有限的样本所提供的信息对模型的复杂性和学习能力两者进行了寻求最佳的折衷，以获得最好的泛化能力。SVM的基本思想是把训练数据非线性的映射到一个更高维的特征空间（Hi

2、lbert空间）中，在这个高维的特征空间中寻找到一个超平面使得正例和反例两者间的隔离边缘被最大化。SVM的出现有效的解决了传统的神经网络结果选择问题、局部极小值、过拟合等问题。并且在小样本、非线性、数据高维等机器学习问题中表现出很多令人注目的性质，被广泛地应用在模式识别，数据挖掘等领域(张学工 2000；崔伟东2001)。支持向量机可以用于分类和回归问题，本章着重介绍分类相关的知识。3.1 SVM的基本思想3.1.1最优分类面SVM是由线性可分情况的最优分类面发展而来的，用于两类问题的分类。下面用一个二维两类问题来说明SVM基本思想(白鹏 等，2008)。图3.1 最优超平面示意图C1和C2代

3、表两类数据样本，各样本在二维中显示如图3.1， 图中的直线P0,P1就是分类函数。如果一个线性函数就完全可以把两类所有样本分开，那么就称这些数据是线性可分的；否则称非线性可分。假设两类线性可分的训练数据样本x1,y1,x2,y2,xN,yw*线性判别函数的值一般是连续的实数，而分类问题需要输出的是离散值。例如利用数值-1表示类别C1，而用数值+1表示类别C2.所有的样本都只能用数值-1和+1表示。这时我们可以通过设置一个阀值，通过判断判别函数的值是大于或者小于这个阀值来判断属于某一类。若我们取这个阀值为0，即当f(x)0时，判别样本为类别C1(即-1)；当f(x)0时，判别样本为类别C2(即+

4、1).现在将判别函数进行归一化，使两类所有样本都满足f(x)1，这时离分类面近的样本都有f(x)=1yiw*x+b-10, i=1,这时分类间隔为2w. 寻求最优的分类面即使得分类间隔最大化。可以发现间隔最大等价于1因此最优化分类面问题可以表示成如下的约束优化问题，如下：Min w约束条件为：yiw*x+b-10, i=1,定义如下Lagrange函数:Lw,b,式中，i0为Lagrange乘子。为了求得函数式(3-5)的最小值，我们对Lw由式(3-6)和(3-2)可将上述的最优化分类面的求解问题转化为一个凸二次规划寻优的对偶问题，如下：Max i=1N约束条件为：i这个二次函数寻优的问题存在

5、唯一解，若iw*其中i*不为0对应的即为支持向量(Support Vector). 并且最优分类面的权系数向量是支持向量的线性组合。分类阀值b*式中xr,xs分别是两类中任意支持向量，fx此时SVM最一般的表达式已经被求得。3.1.2广义的最优分类面但当有少数样本使得原来线性可分的问题变成不可分问题，从而影响了分类器的性能。有时这少数的样本也是噪声，或是奇异值点，是我们在人工对数据分类错分的，为了忽略这些点对分类器的影响，和在经验风险和泛化性能之间求得平衡，松弛因子被引入。它容许错分样本的存在，这时分类面满足：yi当0i1时，样本xi可以正确分类；当w,式中C是惩罚因子(一个正常数). 此时，

6、式目标函数凸二次规划寻优的对偶问题约束条件(3-8)可被变换为如为： 0i3.2核函数3.2.1核函数变换基本思想对于非线性分类问题，在原始空间中最优化分类面也许不能得到令人满意的分类结果。针对这种情况，一个解决的思想是把原始空间中的非线性样本数据投影到某个更高维的空间中，在高维的空间中寻找一个最优超平面能线性地将样本数据分开，但是这种变化可能非常复杂。支持向量机利用核函数巧妙地解决了这个问题。核函数变换的基本思想是将一个n维空间中矢量x映射到更高维的特征空间中去，然后在高维空间中进行线性地分类。核函数变换的基本原理示意图如图3.2所示。由（3-7）、（3-11）可看出，都只涉及训练样本之间的

7、点积运算xi,xj。假设存在一个非线性映射将在特征空间H中构造最优分类面时，计算的过程中仅使用了空间中的点积xi,xj，而没有用到单独的xi。如果存在一个“核函数”K，且Kxi,图3.2 核函数变换示意图3.2常见核函数核函数作为支持向量机理论的重要的组成部分引起了很多研究者的兴趣。常用的满足Mercer条件的核函数有线性函数，多项式函数，径向基函数，Sigmoid函数等，选择不同的核函数可以构造不同的支持向量机(张浩然 2002)。下面对这四种常见的核函数进行简单地介绍.线性函数K多项式函数K径向基函数KSigmoid函数K由这四种核函数可以构造出线性SVM、多项式SVM、RBF SVM和感

8、知SVM。满足Mercer条件核函数很多，这样又带来另外一个问题，即SVM的核函数如何选择。目前没有明确的标准来指导核函数的选择。在模型不确定的情况下，RBF核函数是一个不错的选择。3.3 SVM参数优化问题在实际应用的过程中，选择合适的支持向量机的参数是一项艰巨而又重要的一步，它会影响分类器的泛化能力和分类性能。参数选择实际上是一个优化搜索的过程，搜索空间中的每一个点都有可能是最佳模型的潜在解，并可由推广能力估计值做出相应的评估。所以，参数优化求解的过程在本质上是泛化误差最小化的求解问题。3.3.1常见SVM的寻优方法一般情况下，人们会使用简单并且直观的方法（如网格划分），通过大量的实验比较

9、获得较优的参数。这种方法可以找到在交叉验证意义下的最高的分类准确率，但是当想在更大的范围内寻找最佳的参数和时，这会有很大的计算量。Chapelle 等人采用了一种梯度下降(gradient descend, GD)的方法（Chapelle 2002）来对参数进行选择，这种方法虽然在计算时间上获得有效改善。但是梯度下降方法是一种线性的搜索方法，并且对初始点要求比较高，所有在寻优的过程中容易陷入局部最优。遗传算法(GA, Genetic Algorithm)是Michigan大学的Holland教授及其学生受生物模拟技术启发，提出的一种基于生物遗传和进化机制的自适应概率优化的技术。作为一种实用、高

10、效、鲁棒性强的优化方法，遗传算法很快收到国内外学者的高度重视并迅速发展。Chen (2004)和Zheng (2004)用不同的推广能力估计作为遗传算法的适应度函数对SVM的参数进行优化。结果表明：基于GA对SVM参数进行优化的方法大大的缩小了计算的时间，并且减小了对初始值的依赖度。但是遗传算法的操作往往比较复杂，对不同的优化问题需要设计不同的交叉或变异方式。粒子群算法(particle swarm optimization,PSO)是计算智能领域的一种群体智能优化算法，该算法最早是由Kenedy和Eberhat在对鸟类捕食行为研究时所提出的。PSO算法是从这种生物种群行为特征中得到启发，并应

11、用于优化问题的求解。与遗传算法不同，PSO是通过个体间的协作来寻找最优解, 这使得粒子群算法更加简单, 效率更高, 更容易实现, 因为它的显著的优点已被广泛应用于函数优化、模式分类等领域。杨慧中等人(2006)将粒子群算法应用于对SVM参数的优化，仿真结果表明PSO算法强劲的全局搜索能力大大提高了模型的准确率。3.3.2 PSO寻优算法PSO算法首先在搜索空间中初始化一群粒子，每一个粒子都有可能是极值优化问题的潜在最优解。我们可以用位置，速度和适应度值来三项指标来表示粒子的特征，并通过适应度值可以用来衡量粒子的好坏。其中，适应度值是通过适应度函数来计算得到的。假设在d维的搜索空间中，由n个粒子

12、组成的种群X=X1,X2,Xn,其中第i个粒子表示一个d维向量XiVijXij这里w为惯性权重,j=1,2,d,i=1,2,n;k是当前迭代的次数。Vij是粒子速度，加速度因子c3.3.2 基于PSO算法的SVM参数优化推广能力估计是参数选择的基础，通常的方法包括：留一法(leave-one-out), k-fold交叉验证法，支持向量率法等。由于k-fold交叉验证法的估计是无偏的，通常选用k-fold交叉验证支持向量机参数选择的目标值。由于本文中选择径向基核函数，所以PSO需优化的参数有惩罚系数C和核参数，具体的步骤如下(邵信光 等,2006)：读取训练样本，然后随机产生一组C,作为粒子的

13、初始位置;把所以训练样本均匀地分割成k个互不包含的子集S1根据当前C,训练SVM，并计算出k次识别率的平均值得到k-fold交叉验证识别率；将k-fold交叉验证识别率作为适应度，并记忆个体与群体所对应的最佳适应度位置，然后更新位置和速度搜索更好的C,；重复步骤2)直到满足最大迭代次数；优化结束，输出结果。3.4 SVM多类分类问题 支持向量机是一种二类问题分类器，它只能回答属于正类还是负类的问题，但在实际的应用过程还会遇到多类问题。下面我们介绍详细介绍下多类分类问题的基本原理。由SVM推到多类SVM目前主要有两种方法：(1)在一个优化公式中对所有的数据同时进行全局优化 (2) 将多类问题分解

14、成多个二值分类问题。在数据相同的情况下，前者的计算比后者复杂的多。所以在实际使用过程中，多类SVM问题被分解成多了二值分类问题(Rocha and Goldenstein 2009)。多类分类器常用的二值分类器组合有一对多(one against all), 一对一(one against one),DAGSSVM(Directed Acyclic Graph SVM)三种。在文献（Hsu and Lin 2002）中，作者通过实验证明了在实际的应用的过程中，“一对一”和DAG方法更适合被应用于复杂问题的识别分类。本文中采用的是“一对一”结构。3.4.1 基于二值分类的SVM多类分类原理已知n

15、类数据样本训练集：x上标代表类别数， ti代表第i类训练样本数, 训练集样本总数为 t1+t2+.+tn，其中xiRd, 首先构造n个二值分类器，fkx, k=1,n将第k类的训练样本和其他训练样本集分开。如果样本xi属于第k类，则有然后，寻找函数fkxi，k=1,nyi3.4.2 多类二值分类器组合一对多组合(one-against-rest)这种方法由n个SVM分类器组成，第i层SVM的训练样本是由正样本(第i类的数据样本)和负样本(其余所有类样本)组成。以4类样本为例，首先把样本类1作为正样本，把类2、3、4作为负样本，训练得到SVM1；再将样本类2作为正样本，把类1、3、4作为负样本，

16、训练得到SVM2；按照这个方法训练得到4个二类分类器SVM。所得到SVM数目和样本的类别数一致。这种方法的有点是每个优化问题的规模比较小，分类速度比较快。但是有时会出现这种尴尬的问题，对于一个待分类的样本，所有的类别都说不是自己的，或者所有的类别都说是自己的，这就会出现不可分类现象和重叠分类现象。其分类原理结构图可表示如下图3.3。图3.3 一对多组合一对一组合(one-against-one)“一对一”方法的分类思想是每次从样本数据的n类别中挑出两个不同类别，对这两类用二值分类器SVM分类，这样可以构建出nn-12个分类器。第一个SVM分类器只告诉你别类是“1或是2”，第二个SVM只告诉你别

17、类是“1或者3”，最后一个待识别的别类由这nn-12个图3.4 一对一组合 DAG DAG多类结构实际上就是将支持向量机将决策树相结合而形成的。这种方法的训练的过程和“一对一”方法也是通过构造 nn-12个SVM分类器（王建芬 2001）。对n类样本分类问题构造DAG(二叉决策树)结构的多类分类结构，树的每一个叶节点代表一类，度为2的非叶节点即为一个子SVM分类器。因此，对于有2n-1结点的决策树，则有叶节点个数为n(即为n类),子SVM分类器个数为n-1。DAG的特点是具有层次结构，测试速度快，没有理论指导，需要一定的先验知识。 对于一个有k个叶节点的图3.5 多类分类问题的二叉决策树结构3.5 本章小结支持向量机是一种基于结构风险最小化原则提出的二值分类器方法，其作为统计学习理论的实践方法受到了广大研究者的兴趣。本章节主要介绍了支持向量机的基本思想、核函数、参数的选择和多类分类问题。SVM的基本思想是构造一个超平面作为分类判别平面，使得两类样本之间的间隔最大。对于比较复杂的非线性问题，如果在原始空间中不能够寻找到令人满意的分类效果的最优超平面，则通过非线性变换转化为某个更高维空间中的线性问题。这里引入核函数的概念，使得实现某一个非线性变换后的线性分类而没有增加计算的复杂度。SVM是针对二类问题设计的分类器，当用其来解决多类问题时，我