支持向量机(SVM)算法推导及其分类的算法实现

《支持向量机(SVM)算法推导及其分类的算法实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、支持向量机算法推导及其分类的算法实现摘要：本文从线性分类问题开始逐步的叙述支持向量机思想的形成，并提供相应的推导过程。简述核函数的概念，以及kernel在SVM算法中的核心地位。介绍松弛变量引入的SVM算法原因，提出软间隔线性分类法。概括SVM分别在一对一和一对多分类问题中应用。基于SVM在一对多问题中的不足，提出SVM的改进版本DAGSVM。Abstract：Thisarticlebeginswithalinearclassificationproblem,GraduallydiscussformationofSVM,andtheird

2、erivation.Descriptiontheconceptofkernelfunction,andthecorepositioninSVMalgorithm.Describesthereasonsfortheintroductionofslackvariables,andproposesoft-marginlinearclassification.SummarytheapplicationofSVMinone-to-oneandone-to-manylinearclassification.BasedonSVMshortageinon

3、e-to-manyproblems,animprovedversionwhichcalledDAGSVMwasputforward.关键字：SVM、线性分类、核函数、松弛变量、DAGSVM1.SVM的简介支持向量机(SupportVectorMachine)是Cortes和Vapnik于1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学

4、习精度，Accuracy）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力。对于SVM的基本特点，小样本，并不是样本的绝对数量少，而是与问题的复杂度比起来，SVM算法要求的样本数是相对比较少的。非线性，是指SVM擅长处理样本数据线性不可分的情况，主要通过松弛变量和核函数实现，是SVM的精髓。高维模式识别是指样本维数很高，通过SVM建立的分类器却很简洁，只包含落在边界上的支持向量。2.线性分类器及其求解线性分类器，是最简单也很有效的分类器形式。在一个线性分类器中，可以看到SVM形成的思路,并接触很多SVM的

5、核心概念。用一个二维空间里仅有两类样本的分类问题来举例。如图1所示图1两类样本分类C1和C2是要区分的两个类别，在二维平面中它们的样本如图1所示。中间的直线就是一个分类函数，它可以将两类样本完全分开。一般的，如果一个线性函数能够将样本完全正确的分开，就称这些数据是线性可分的，否则称为非线性可分的。很容易看出来，图1中间那条分界线并不是唯一的，旋转一下，只要不把两类数据分错，仍然可以达到分类的效果，稍微平移一下，也可以。对同一个问题存在多个分类函数的时候，哪一个函数更好呢？必须要先找一个指标来量化“好”的程度，通常使用分类间隔来衡量。设平面

6、中的直线方程为：（1）设是一个有某一对象抽取出的n维向量，为分类标记，则可以定义点到某一超平面的间隔：（2）用和替代（2）式中的w和b得：（3）将（3）式得到的间隔称为几何间隔，几何间隔所表示的正是点到超平面的欧氏距离，以上是单个点到某个超平面的距离定义，同样可以定义一个点的集合（就是一组样本）到某个超平面的距离为此集合中离超平面最近的点的距离。图2更加直观的展示出了几何间隔的含义。图2分割超平面图2中，H是分类面，H1和H2是平行于H，且过离H最近的两类样本的直线，H1与H，H2与H之间的距离就是几何间隔。几何间隔与样本的误分次数间存在

7、关系：其中的δ是样本集合到分类面的间隔，，即R是所有样本中向量长度最长的值。从上式可以看出，误分次数的上界由几何间隔决定。因此选择几何间隔来作为评价一个解优劣的指标，几何间隔越大的解，它的误差上界越小。因此最大化几何间隔成了我们训练阶段的目标。从（3）式可知，几何间隔与

8、

9、w

10、

11、是成反比的，因此最大化几何间隔与最小化

12、

13、w

14、

15、等价。通常不是固定

16、

17、w

18、

19、的大小而寻求最大几何间隔，而是固定间隔（例如固定为1），寻找最小的

20、

21、w

22、

23、。　　此时变成一个最优化问题，若想寻找一个小

24、

25、w

26、

27、，就可以用下面的式子表示：　　但实际上对于这个目标，常常使

28、用另一个完全等价的目标函数来代替，如下：如果直接来解这个求最小值问题，很容易看出当

29、

30、w

31、

32、=0的时候就得到了目标函数的最小值。反映在图2中，就是与两条直线间的距离无限大，这个时候，所有的样本