欢迎来到天天文库
浏览记录
ID:45033370
大小:383.50 KB
页数:15页
时间:2019-11-08
《支持向量机(SVM)算法推导及其分类地算法实现》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、实用文档支持向量机算法推导及其分类的算法实现摘要:本文从线性分类问题开始逐步的叙述支持向量机思想的形成,并提供相应的推导过程。简述核函数的概念,以及kernel在SVM算法中的核心地位。介绍松弛变量引入的SVM算法原因,提出软间隔线性分类法。概括SVM分别在一对一和一对多分类问题中应用。基于SVM在一对多问题中的不足,提出SVM的改进版本DAGSVM。Abstract:Thisarticlebeginswithalinearclassificationproblem,GraduallydiscussformationofSVM,andtheirderivation.Descr
2、iptiontheconceptofkernelfunction,andthecorepositioninSVMalgorithm.Describesthereasonsfortheintroductionofslackvariables,andproposesoft-marginlinearclassification.SummarytheapplicationofSVMinone-to-oneandone-to-manylinearclassification.BasedonSVMshortageinone-to-manyproblems,animprovedversio
3、nwhichcalledDAGSVMwasputforward.关键字:SVM、线性分类、核函数、松弛变量、DAGSVM1.SVM的简介支持向量机(SupportVectorMachine)是Cortes和Vapnik于1995年首先提出的,它在解决小样本、非线性及高维模式识别中表现出许多特有的优势,并能够推广应用到函数拟合等其他机器学习问题中。支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的,根据有限的样本信息在模型的复杂性(即对特定训练样本的学习精度,Accuracy)和学习能力(即无错误地识别任意样本的能力)之间寻求最佳折衷,以期获得最好的推广能
4、力。对于SVM的基本特点,小样本,并不是样本的绝对数量少,而是与问题的复杂度比起来,SVM算法要求的样本数是相对比较少的。非线性,是指SVM擅长处理样本数据线性不可分的情况,主要通过松弛变量和核函数实现,是SVM的精髓。高维模式识别是指样本维数很高,通过SVM建立的分类器却很简洁,只包含落在边界上的支持向量。实用文档2.线性分类器及其求解线性分类器,是最简单也很有效的分类器形式。在一个线性分类器中,可以看到SVM形成的思路,并接触很多SVM的核心概念。用一个二维空间里仅有两类样本的分类问题来举例。如图1所示图1两类样本分类C1和C2是要区分的两个类别,在二维平面中它们的样本如
5、图1所示。中间的直线就是一个分类函数,它可以将两类样本完全分开。一般的,如果一个线性函数能够将样本完全正确的分开,就称这些数据是线性可分的,否则称为非线性可分的。很容易看出来,图1中间那条分界线并不是唯一的,旋转一下,只要不把两类数据分错,仍然可以达到分类的效果,稍微平移一下,也可以。对同一个问题存在多个分类函数的时候,哪一个函数更好呢?必须要先找一个指标来量化“好”的程度,通常使用分类间隔来衡量。设平面中的直线方程为:(1)设是一个有某一对象抽取出的n维向量,为分类标记,则可以定义点到某一超平面的间隔:(2)用和替代(2)式中的w和b得:(3)实用文档将(3)式得到的间隔称
6、为几何间隔,几何间隔所表示的正是点到超平面的欧氏距离,以上是单个点到某个超平面的距离定义,同样可以定义一个点的集合(就是一组样本)到某个超平面的距离为此集合中离超平面最近的点的距离。图2更加直观的展示出了几何间隔的含义。图2分割超平面图2中,H是分类面,H1和H2是平行于H,且过离H最近的两类样本的直线,H1与H,H2与H之间的距离就是几何间隔。几何间隔与样本的误分次数间存在关系:其中的δ是样本集合到分类面的间隔,,即R是所有样本中向量长度最长的值。从上式可以看出,误分次数的上界由几何间隔决定。因此选择几何间隔来作为评价一个解优劣的指标,几何间隔越大的解,它的误差上界越小。因
7、此最大化几何间隔成了我们训练阶段的目标。从(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、w
30、
31、=0的时候就得到了目标函数的最小值。反映在图2中,就是与两条直线间的
此文档下载收益归作者所有