支持向量机在分类中的应用

第10卷　第8期2005年8月

中国图象图形学报JournalofImageandGraphics

Vol.10,No.8

Aug.,2005

支持向量机在分类中的应用

陆　波　　尉询楷　　毕笃彦

(空军工程大学工程学院,西安　710038)

摘　要　通过引入结构风险最小化原则和最优分类面的概念,介绍了支持向量机及其用于非线性分类的基本原理和训练算法,并选用不同的核函数及参数对一组线性不可分的两类样本进行了划分识别,得到了较好的效果,并对结果进行了分析说明,展望了支持向量机的发展趋势。关键词　支持向量机　最优分类面　非线性分类　二次规划

中图法分类号:TP18　　文献标识码:A　　文章编号:100628961(2005)0821029207

ApplicationsofSupportVectorMachinesinClassification

LUBo,WEIXun2kai,BIDu2yan

(TheEngineeringInstitute,AirForceEngineeringUniversity,Xi’an710038)

Abstract　Thispaperintroducesthetheoryandtrainingalgorithmofthesupportvectormachinewhichisappliedinnonlinearclassificationandrecognitionbythewayofbringingintheconceptsuchasstructuralriskminimizationprincipleandoptimalhyperplane,thenasetofnonlinearbinarysamplesaresuccessfullyclassifiedbyusingdifferentkernelfunctions,followedbydiscussiontotheresults.Afterthatcurrentmulti2classclassificationalgorithmsandapplicationareasarereviewed.Finallyfuturedevelopmentsareprospected.

Keywords　supportvectormachine,optimalhyperplane,nonlinearclassification,quadraticprogramming

1　引　言

基于数据的机器分类是现代智能技术中一个非常重要的方面。现有的机器分类方法其共同理论基

础之一是统计学。传统统计学研究的是样本数量趋于无穷大时的渐进理论,现有的方法也多是基于此假设,但在实际问题中,样本数量往往是有限的,因此很多分类方法在实际应用中不尽人意。支持向量机是由Vapnik等人在20世纪90年代中期提出的一种机器学习算法,它以其良好的理论背景,从结构风险最小化原则出发为机器学习提供了一个崭新的方向。支持向量机是从线性可分情况下的最优分类面发展而来的,通过将输入空间映射到一个高维内积空间中,解一个线性约束的二次规划问题得到全

收稿日期:2004202223;改回日期:2004212229

局最优解,有效避免了“维数灾难”,保证了收敛速

度,而且不存在局部极小值问题。因此在解决小样本、非线性及高维模式识别问题中具有特有的优势。本文利用支持向量机技术对解决模式识别中的非线性分类问题进行了应用研究,并综述了现阶段支持向量机分类算法的一些新发展和应用。

2　基于支持向量机的分类

2.1　结构风险最小化原则

传统的分类方法只有在样本数目足够多的前提下,其性能才有理论上的保证。在实际应用中,人们通常采用“经验风险最小化(ERM)原则”,即通过求经验风险最小值来近似代替期望风险最小值。然而仍不能取得理想的效果,这是因为从期望风险最小化

第一作者简介:陆波(1979～　),男。现为空军工程学院信号与信息处理专业硕士研究生。主要研究方向为图像处理与模式识别。

E2mail:[email protected]

1030

中国图象图形学报　第10卷

到经验风险最小化并无可靠的理论依据,只是人们直

[1]

观上合理的想当然的做法。为此,Vapnik等人推出了一种在有限样本情况下的较完善的机器学习理论体系———统计学习理论,它被认为是目前针对小样本统计估计和预测学习的最佳理论。统计学习理论提出了一种新的策略:把指示函数集构造为一个函

[3]

数子集序列,使各个子集按照VC维的大小排列;在每个子集中寻找最小经验风险,在子集间折中考虑

[2]

经验风险和置信范围,以取得实际风险的最小。这种思想被称为“结构风险最小化(SRM)原则”,如图1所示。基于支持向量机的分类方法就是这种思想的具体实现,即设计函数集的某种结构使每个子集中都能取得最小的经验风险,然后选取适当的子集使置信范围最小,则这个子集中使经验风险最小的函数就是

用于分类的最优判别函数。

[2]

图中实心点和空心点分别表示两类训练样本,H为分类线,H1、H2分别为过各类样本中离分类线最近的点且平行于分类线的直线,H1和H2之间的距离叫做分类间隔(图中用margin表示)。所谓最优分类线就是要求分类线不但能将两类无错误地分开,而且要使分类间隔最大。推广到高维空间,最优分类线就成为最优分类面。设分类线方程为x・w+b=0,将其归一化,使得对线性可分样本集(xi,yi),

i=1,…,n;x∈R;y∈{+1,-1},满足:

yi[(xi・w)+b]

-1≥0

(1)

此时分类间隔为2/

w,因此使间隔最大等价于使

w最小,满足式(1)且使w最小的分类面就是最优分类面。过两类样本中离分类面最近的点且平行于最优分类面的超平面H1、H2上的训练样本(即使式(1)中等号成立的样本)叫做支持向量,这是因为它们支撑了最优分类面,如图2中用圆圈标出的点所示。利用Lagrange优化方法可以把上述最优分类面问题转化为其对偶问题:即在以下约束条件下

∑ya

i=1

=0和ai≥0,i=1,…,n

(2)

对ai求解下列函数的最大值

Q(a)=

∑

i=1

ai-aiajyiyj(xi・xj)2i,j=1

∑

(3)

ai为与每个样本对应的Lagrange乘子。这是一个

图1　结构风险最小化示意图

Fig.1　Structureriskminimization

不等式约束下二次函数的寻优问题,存在唯一解,解

中将只有一部分ai不为0,其对应的样本就是支持向量。解上述问题后得到的最优分类函数是:

f(x)=sgn{(w・x)+b}

2.2　最优分类面

支持向量机理论是从线性可分情况下的最优分类面提出的,其基本思想可由图2所示的两类线性可分情况来说明

。

=sgn

∑a

i=1

yi(xi・x)+b

(4)

sgn()为符号函数。由于非支持向量对应的ai均为0,因此式中的求和实际上只对支持向量进行,b是

图2　最优分类面示意图

Fig.2　Optimumseparationplane

分类阈值,可用任一支持向量由式(1)求得。

上述最优分类面是在线性可分的前提下讨论的,而实际情况往往是线性不可分的(某些样本不满足式(1))。此时,可在式(1)中增加一个松弛项ξ≥0,则式(1)变成:

(5)yi[(xi・w)+b]-1+ξi≥0

当样本xi满足式(1)时,ξ为0;否则ξ>0,表示此样本为造成线性不可分的点。对式(5)利用Lagrange乘子法及对偶原理可得到线性不可分条件下的对偶问题:即在以下约束条件下,

∑ya

i=1

=0,0≤ai≤C,i=1,…,n

(6)

　第8期　

陆　波等:支持向量机在分类中的应用

1031

对ai求解式(3)的最大值。用与求解线性可分时同

样的方法求解这一优化问题便可得到线性不可分情况下的最优分类面(也称为广义最优分类面),其结果与线性可分情况下得到的式(4)相同,只是ai的取值范围变为[0,C],其中C为事先选定的大于0的常数,它实际上起着对错分样本控制惩罚程度的作用,实现在错分样本数与算法复杂度之间的折衷,也称为惩罚系数。2.3　非线性分类问题的支持向量机方法

以上讨论得到的最优和广义最优分类函数式(4)中只含有待分类样本与训练样本中的支持向量的内积运算(x・xi)。可见,要解决一个特征空间中的最优线性分类问题,只需进行这个空间中的内积运算即可。由于很多实际模式识别问题在其定义的空间中不是线性可分的,对此可采用一个非线性变换φ将输入映射到一个特征空间z,其中z=φ

(x)。在特征空间z中,数据是线性可分的,故在z

图3　非线性支持向量机的一般结构

Fig.3　Structureofnonlinearsupportvectormachines

K(x,xi)=-

x-xσ22

(10)(11)

　　(3)两层前馈神经网络核函数

)K(x,xi)=tanh(v(x,xi)-θ

2.4　支持向量机的实现

中可找到一个线性分类函数,它对应于输入空间中

的一个非线性分类函数,要求解此时的最优分类函数涉及计算内积(zi・zj)=

k=1

支持向量机的训练本质上是解决一个二次规划

(QP)问题,即上述式(6)、式(7)。该问题可改写成以下矩阵形式:

给定训练样本(xi,yi),i=1,…,n;核函数

K(xi,xj)和调节参数C,求二次型

Q(A)=A1-T

φk(xi)φk(xj),若直∑

接求解,不仅需要知道非线性映射φ的形式,而且

计算量随着特征空间维数的增加呈指数增长,使求解难度加大甚至不能求解。因为优化问题和分类函数中涉及内积运算(zi・zj),根据Hilbert2Schmidt原理,可找到满足Mercer条件的核函数K(xi,xj),使K(xi,xj)=(zi・zj)。则优化函数变为

Q(a)=

[4]

AHA2

(12)

的极小值并满足下列约束条件:

Ay=0,0≤ai≤C

(13)

其中,H=[hij],hij=yiyjK(xi,xj),(i,j=1,…,n);

A=(a1,a2,…,an);y=(y1,y2,…,yn);1为单位阵。

∑

i=1

ai-aiajyiyjK(xi,xj)2i,j=1

∑

(7)

现有的Chunking

[6]

,Osuna

[7]

,SMO

[8]

等训练算

相应的分类函数也变为

f(x)=sgn

法均能有效地求解以上问题。本文采用了Osuna训

∑a

i=1

yiK(xi,x)+b

(8)

练算法。其基本思想为:将一个QP问题分解成一系列较小规模的QP问题迭代求解,每次只处理部

分训练数据,当所求的解都满足最优化(Kuhn2

[9]

Tucker)条件时,便得到了优化问题的最优解。具

这就是解决非线性分类问题的支持向量机,其形式结构近似于神经网络,如图3所示。

不难看出,支持向量机的基本思想可概括为:首先通过非线性变换将输入空间映射到一个高维空间,然后在这个高维空间中求取最优线性分类面,非线性变换是通过定义适当的内积函数(核函数)实现的。选择不同形式的核函数就可以生成不同的支

[5]

持向量机。常用的核函数有以下几种形式:

(1)多项式核函数

K(x,xi)=(1+(x・xi)),p=1,…,n

体步骤如下:

(1)从训练样本集中取出m个(m大于支持向

量的数目)样本构成工作集B,将其余n-m个样本组成的集合记为N,N中所有样本的Lagrange乘子

a均置为0。

(2)用QP方法对B求解最优化问题,得到支持

(

向量(Lagrange乘子a不为0的向量),并构成一个分类器。

(3)用该分类器测试集合N中的样本,若N中

　　(2)高斯径向基核函数

1032

中国图象图形学报　第10卷

所有样本均满足最优化条件或N为空集则结束,否则继续。

(4)将N中至少一个不满足最优化条件的样本放入B中,同时从B中取出同样数量的样本(Lagrange乘子a为0)放入N中;返回步骤2。2.5　实例

数对一组线性不可分的两类样本进行分类识别,得

到的结果如图4所示。两类样本分别用“+”和“3”表示。图中用圆圈圈出的样本为支持向量,可以看出,用支持向量机求得的最优分类线(实曲线)均能将样本正确地划分开。所选用的核函数、参数及分类结果如表1所示

。

在此分别采用多项式核函数和高斯径向基核函

(a)

两类样本数据的分布(b)采用6阶多项式核函数

(P=6,C=Inf

)

(c)高斯径向基核函数(σ=0.5,C=10

)

(d)高斯径向基核函数

(σ=1,C=Inf)

图4　对线性不可分样本的分类结果

Fig.4　Classificationresultsofoverlappingdata

表1　两种支持向量机及不同参数的分类结果

Tab.1　Classificationresults

支持向量机

类型多项式高斯径向基

核函数中的参数

P=3,C=Inf

法

[10]

,在此不作详述。

支持向量个数

282821

测试误差

(%)3.660.040.90

3　多分类算法

由于现实世界中遇到的问题多为多类问题,而且由于支持向量机是针对二分类问题设计的算法,因此如何将多类别问题转化成为二分类的组合就成为支持向量机研究的热点问题

[11～16]

σ=1,C=Infσ=0.5,C=10

由于C值表征的是经验风险与VC维(即推广能力)之间的权衡,而当C取无穷(Inf)时,相当于仅考虑其推广能力。从表中可以看出,在相同的惩罚

C作用下,径向基函数具有更好的分类结果和更佳

。

3.1　一对余型多类支持向量机方法

训练集T={(x1,y1),(x2,y2),…,(xn,yn)},其中xi∈R,yi∈{1,2,…,k},i=1,…,n,算法描述为对于k分类问题,取所有y=i和y≠i的训练样本可以构建M=Ck=k个训练子集Ti。对i=1,…,k,则由第i类和其余(M-1)类训练数据便可训练式(8)

的推广能力,且其卓异的分类精度是传统方法难以企及的。另外,选择不同的参数也将导致分类精度的不同,关于参数的选择可参考Cross2validation方

　第8期　

陆　波等:支持向量机在分类中的应用

1033

所示二值分类器,分别使用SVM二值分类算法对这

M个训练集进行学习,便可以构造M个分类器。

测试阶段,将测试样本输入到M个支持向量机,得到决策函数集{gi(x)}和判别函数集{qi(x)},i=1,…,k,则将其归为决策函数gi(x)最大的所对应的类别指示值。3.2　一对一型多类支持向量机方法

对于k分类问题,取所有y=i和y=j的训练样

本构建M=Ck个训练子集Tij。对i=1,…,k,j=i+1,…,k,则由第i类和第j类数据训练数据便可训练二值分类器,分别使用SVM二值分类算法对这M个训练集进行学习,便可以构造M个分类器。测试阶段的判别采用投票决策法(Votingstrategy),用所有的M个分类器对测试样本x进行分类,在第i类和第j类之间分类时,记vy为投票函数,若该分类器判断x属于i类,则i类的票数加1,否则j类的票数加1。最后将测试样本x归为得票数最多的类别。3.3　DDAG型多类支持向量机方法

对于一对一算法,Plat等人提出了一种新的学习构架:决策导向无环图(decisiondirectedacyclicgraph,DDAG)。对于k分类问题,DDAG也含有

k(k-1)/2个二值分类器,而在对多个一对一分类

以得到一系列的两类问题,总共可以得到L个决策函数集{f1,…,fL}。按照设定的对应规则,可以将每一类与一系列长度为L、值为+1或者-1的编码相对应,按照类别的顺序就可以得到一个k行L列的编码表。

由+1或者-1组成的编码矩阵记为Mk×L,其中,k为类别数,L为编码长度也就是分类器的个数。当mij=+1(-1)时,表示此样本相对于第i类而言是作为正(负)类训练第j个分类器fj。这样就可以得到决策函数集f(x)={f1(x),f2(x),…,fL(x)},而测试过程中,对于测试样本x,只需要计算各个分类器的输出向量与各类别向量的距离,使其最小的类就是样本所属的类。

4　基于支持向量机分类的应用

4.1　与新理论的综合应用

随着混沌理论、小波理论、模糊理论、粗糙集理论等一批新兴的智能学科的兴起,支持向量机算法在应用过程中也出现了一些新的发展趋势。

(1)与混沌理论的综合应用

采用混沌型支持向量机的时序分析框架,利用混沌特征参数选择合适的预测器结构,然后在进行预测分析时取得了很好的效果。

(2)与小波理论的综合应用

基于小波和支持向量机的滚动轴承状态监测方法,利用小波能量提取信号特征,然后利用支持向量机进行分类,取得了较为满意的结果

(3)与模糊理论的综合应用

[17]

器进行组合的过程中,引入了图论中的有向无环图(DAG)的思想。训练方法与一对一方法基本类似,测试时按照DDAG图进行计算。3.4　K类支持向量机方法

K类支持向量机算法与一对多方法类似,它也

是构造k个支持向量机决策函数,不同的是所有支持向量机的参数是通过求解一个二次规划问题获得。

3.5　LS2SVM型多类支持向量机方法

Suykens将二分类LSSVM方法推广到了多类别

。

模糊一对多方法和模糊一对一方法,有效地消除了不可分边界,较好地提高了多类支持向量机的分类精度。

(4)与粗糙集理论的综合应用

采用粗糙集进行特征属性约减的多类支持向量机方法,并将其应用到城市污水监控中去,取得了较好的效果,并具有一定的容错性4.2　应用领域

[22]

[18～21]

问题,本质上还是将二次规划的求解问题转化成为

线性规划问题。

3.6　ECOC型多类支持向量机方法

ECOC编码是由Bose和Chaudhuri在1960年提出的一种分布式输出码,1963年,Duba将其应用于模式识别领域中,1995年Dietterich和Bakiri将ECOC引入到多类别模式识别问题中。

通过一类对余类,或者一类对一类的方式构造二分类问题,当然也可以把奇数类看作是正类(+1),把偶数类看作是负类(-1),或者采用某种特定适宜实际分类问题情况的构造方法,这样就可

。

近来,随着支持向量机理论的完善和快速发展,支持向量机在众多领域得到了广泛的应用,例如手写体识别

[22]

,人脸识别与检测,计算机系统入侵监

[23]

测、文本分类,基因、蛋白质分析,语音识别,图像分类,故障诊断

等。

　第8期　

陆　波等:支持向量机在分类中的应用

1033

所示二值分类器,分别使用SVM二值分类算法对这

M个训练集进行学习,便可以构造M个分类器。

对于k分类问题,取所有y=i和y=j的训练样

对于一对一算法,Plat等人提出了一种新的学习构架:决策导向无环图(decisiondirectedacyclicgraph,DDAG)。对于k分类问题,DDAG也含有

k(k-1)/2个二值分类器,而在对多个一对一分类

4　基于支持向量机分类的应用

4.1　与新理论的综合应用

随着混沌理论、小波理论、模糊理论、粗糙集理论等一批新兴的智能学科的兴起,支持向量机算法在应用过程中也出现了一些新的发展趋势。

(1)与混沌理论的综合应用

采用混沌型支持向量机的时序分析框架,利用混沌特征参数选择合适的预测器结构,然后在进行预测分析时取得了很好的效果。

(2)与小波理论的综合应用

基于小波和支持向量机的滚动轴承状态监测方法,利用小波能量提取信号特征,然后利用支持向量机进行分类,取得了较为满意的结果

(3)与模糊理论的综合应用

[17]

器进行组合的过程中,引入了图论中的有向无环图(DAG)的思想。训练方法与一对一方法基本类似,测试时按照DDAG图进行计算。3.4　K类支持向量机方法

K类支持向量机算法与一对多方法类似,它也

是构造k个支持向量机决策函数,不同的是所有支持向量机的参数是通过求解一个二次规划问题获得。

3.5　LS2SVM型多类支持向量机方法

Suykens将二分类LSSVM方法推广到了多类别

。

模糊一对多方法和模糊一对一方法,有效地消除了不可分边界,较好地提高了多类支持向量机的分类精度。

(4)与粗糙集理论的综合应用

采用粗糙集进行特征属性约减的多类支持向量机方法,并将其应用到城市污水监控中去,取得了较好的效果,并具有一定的容错性4.2　应用领域

[22]

[18～21]

问题,本质上还是将二次规划的求解问题转化成为

线性规划问题。

3.6　ECOC型多类支持向量机方法

。

近来,随着支持向量机理论的完善和快速发展,支持向量机在众多领域得到了广泛的应用,例如手写体识别

[22]

,人脸识别与检测,计算机系统入侵监

[23]

测、文本分类,基因、蛋白质分析,语音识别,图像分类,故障诊断

等。

1034

中国图象图形学报　第10卷

2　VapnikVN.TheNatureofStatisticalIearningTheory[M].New

5　支持向量机的发展趋势

对于支持向量机算法,目前尚存在许多需要解决的问题,主要有以下几方面需要着重研究:

(1)核的选取　目前主要侧重于构造核的方法的研究上,而如何选择合适的核则是支持向量机算法理论上需要解决的主要问题。关于支持向量机的核构造目前有很多文献可以参阅,其中文献[24]有较详细的介绍。

(2)多类(变量)问题的研究　目前对于模式分类问题已有的算法主要有:一对一方法(one2against2one)、一对多方法(one2against2all)、成对分类法(pairwise)、纠错码型(errorcodecorrecting)、决策树型(decisiontree)、无环导向图型(DDAG)以及球形支

York:Springer,1995.

3　VapnikV,LevinE,LeCunY.MeasuringtheVC2dimensionofa

learningmachine[J].NeuralComputation,1994,8(5):51～76.4　BurgesC.

Atutorialonsupportvectormachinesforpattern

recognition[J].DataMiningandKnowledgeDiscovery,1998,2(2):1～47.

5　OsunaE,FreundR.Supportvectormachines[A].In:TrainingandApplications[R],TechnicalReportAlm21602,CambridgeMA,USA:MIT,1997,2:527～531.

6　VapnikV.EstimationofDependenceBasedonEmpiricalData[M],NewYork:SpringerVerlag,1982.

7　OsunaE,FreundR.Animprovedtrainingalgorithmfortraining

supportvectormachines[A].In:ProceedingsofIEEEWorkshoponNeuralNetworksforSignalProcessing[C],NewYork,1997,1:252～256.8　PlattJ.

SequentialMinimalOptimization:AFastAlgorithmfor

TrainingSupportVectorMachines[M].Cambridge:TheMITPress,1998:169～182.9　FletcherR.

PracticalMethodsofOptimization[M].NewYork:

WileyandSonsPress,1987.

10AlexanderSmola.RegressionEstimationwithSupportVectorLearningMachines[EB/OL].http://www.firstgmd.de/smola,2000206205.11AllweinL,RobertE.Reducingmulticlasstobinary:Aunifying

approachformarginclassifiers[J].JournalofMachineLearningResearch,2000,1(1):113～141.12Pairwise.

ClassificationandSupportVectorMachines[M].

Cambridge:TheMITPress,1999.

13PlattJC,CristianiniN,Shawe2TaylorJ.LargemarginDAGsformulticlassclassification[J].

AdvancesinNeuralInformation

ProcessingSystems,2000,12(12):547～553.

14SuykensJAK,VandewalleJ.MulticlassLeastSquaresSupportVectorMachines[R],TR19992012.WashingtonDC,America:WashingtonIstituteofTechnology,1999.

15KindermannJ,LeopoldE,PaassG.Multi2ClassClassificationwith

ErrorCorrectingcodes[EB/OL].http://www.firstgmd.2004211204.

16Chih2WeiHsu,Chih2JenLin.Acomparisonofmethodsformulticlass

supportvectormachines[J].IEEETransactionsonNeuralNetworks,2001,13(2):415～425.17LIYing2hong,

WEIXun2kai,

LIU

Jian2xun.

Engineering

ApplicationsofSupportVectorMachines[M].Beijing:PublishingHouseofOrdnanceIndustry,2004.[李应红,尉询楷,刘建勋.支

持向量机(sphere2structuredSVM),也有一些采用组合支持向量机进行决策分类的新方法,如采用Logistic回归进行SVM组合的方法等。如何选择恰

当的组合方法获得满意的推广性能是支持向量机用于多分类问题中需要深入研究的方向。

(3)模型选择　核函数确定的情况下,目前最常用的支持向量机推广误差的估计方法是K层交叉检验法(cross2validation)和留一法(leave2one2out,LOO),常用的LOO推广误差的评定界主要有:Jiaakkola2Haussler上界、Joachimes上界,以及Vapnik

上界,其中,Vapnik上界由于其计算简单,所以实际使用得比较多,但是这些界都存在一个问题:估计得到的界往往大于实际中的情况,使得有时获得的推广界根本无法使用。这也是支持向量机推广性估计中亟需解决的重要问题。

(4)高效、快速的实现方法　目前主要的支持向量机实现方法有:内点算法(interiorpoint),Newton梯度法,以及求解大型问题的Chunking选块

算法,分解算法(Decomposing),序贯最小优化方法(SMO,sequentialminimaloptimization)等,对于大规模、超大规模数据集这些算法在一定程度上都不能够满足快速计算的要求,因此开发适合于大型、超大型数据集的海量计算方法就显得十分重要。

参考文献(References)

1　BIANZhao2qi,

ZHANGXue2gong.

PatternRecognition[M].

持向量机的工程应用[M].北京:兵器工业出版社,2004.]

18InoueT,AbeS.

Classication[R].

FuzzySupportVectorMachinesforPatternTR20012005,

WashingtonDC,

America:

WashingtonIstituteofTechnology

19LinChunfu,WangShengde.Fuzzysupportvectormachines[J].

IEEETransactionsonNeuralNetworks,2002,13(3):464～471.20HuangHan2Pang,LiuYi2Hung.Fuzzysupportvectormachinesfor

patternrecognitionanddatamining[J].

InternationalJournalof

Beijing:TsinghuaUniversityPress,2000.[边肇祺,张学工.模式识

别[M].北京:清华大学出版社,2000.]

　第8期

FuzzySystems,2002,14(3):25～28.

陆　波等:支持向量机在分类中的应用

2003.]

1035

21FANXi2wei,DUShu2xing.Roughsupportvectormachineandits

applicationtowastewatertreatmentprocesses[J].

Controland

Decision,2004,19(5):573～576.[范昕炜,杜树新.粗SVM分

23WEIXun2kai,LIYing2hong.Applicationsofsupportvectormachines

inaeroenginefaultdiagnosis[J].JournalofAerospacePower,2004,19(6):844～848.[尉询楷,李应红.支持向量机在航空发动机故

类方法及其在污水处理过程中的应用[J].控制与决策,2004,

19(5):573～576.]22WEIXing2guo.

Research

HandwrittenNumericalDigits

RecognitionBasedonKernel2basedLearningAlgorithm[D].Nanjing:NanjingUniversityofScienceandTechnology,2003.[魏兴

障诊断中的应用[J].航空动力学报,2004,19(6):844～848.]

24AyatNE,CherietM.Anewsupportvectormachinekernelfor

patternrecognition,applicationtodigitimagerecognition[A].andRecognition[C],Seattle,USA,2001:1215～1219.

In:

Proceedingsofthe6thInternationalConferenceonDocumentAnalysis

国.基于核方法的手写体数字识别[D].南京:南京理工大学,

第10卷　第8期2005年8月

中国图象图形学报JournalofImageandGraphics

Vol.10,No.8

Aug.,2005

支持向量机在分类中的应用

陆　波　　尉询楷　　毕笃彦

(空军工程大学工程学院,西安　710038)

中图法分类号:TP18　　文献标识码:A　　文章编号:100628961(2005)0821029207

ApplicationsofSupportVectorMachinesinClassification

LUBo,WEIXun2kai,BIDu2yan

(TheEngineeringInstitute,AirForceEngineeringUniversity,Xi’an710038)

Keywords　supportvectormachine,optimalhyperplane,nonlinearclassification,quadraticprogramming

1　引　言

基于数据的机器分类是现代智能技术中一个非常重要的方面。现有的机器分类方法其共同理论基

收稿日期:2004202223;改回日期:2004212229

局最优解,有效避免了“维数灾难”,保证了收敛速

2　基于支持向量机的分类

2.1　结构风险最小化原则

第一作者简介:陆波(1979～　),男。现为空军工程学院信号与信息处理专业硕士研究生。主要研究方向为图像处理与模式识别。

E2mail:[email protected]

1030

中国图象图形学报　第10卷

到经验风险最小化并无可靠的理论依据,只是人们直

[1]

[3]

数子集序列,使各个子集按照VC维的大小排列;在每个子集中寻找最小经验风险,在子集间折中考虑

[2]

用于分类的最优判别函数。

[2]

i=1,…,n;x∈R;y∈{+1,-1},满足:

yi[(xi・w)+b]

-1≥0

(1)

此时分类间隔为2/

w,因此使间隔最大等价于使

∑ya

i=1

=0和ai≥0,i=1,…,n

(2)

对ai求解下列函数的最大值

Q(a)=

∑

i=1

ai-aiajyiyj(xi・xj)2i,j=1

∑

(3)

ai为与每个样本对应的Lagrange乘子。这是一个

图1　结构风险最小化示意图

Fig.1　Structureriskminimization

不等式约束下二次函数的寻优问题,存在唯一解,解

中将只有一部分ai不为0,其对应的样本就是支持向量。解上述问题后得到的最优分类函数是:

f(x)=sgn{(w・x)+b}

2.2　最优分类面

支持向量机理论是从线性可分情况下的最优分类面提出的,其基本思想可由图2所示的两类线性可分情况来说明

。

=sgn

∑a

i=1

yi(xi・x)+b

(4)

sgn()为符号函数。由于非支持向量对应的ai均为0,因此式中的求和实际上只对支持向量进行,b是

图2　最优分类面示意图

Fig.2　Optimumseparationplane

分类阈值,可用任一支持向量由式(1)求得。

(5)yi[(xi・w)+b]-1+ξi≥0

∑ya

i=1

=0,0≤ai≤C,i=1,…,n

(6)

　第8期　

陆　波等:支持向量机在分类中的应用

1031

对ai求解式(3)的最大值。用与求解线性可分时同

(x)。在特征空间z中,数据是线性可分的,故在z

图3　非线性支持向量机的一般结构

Fig.3　Structureofnonlinearsupportvectormachines

K(x,xi)=-

x-xσ22

(10)(11)

　　(3)两层前馈神经网络核函数

)K(x,xi)=tanh(v(x,xi)-θ

2.4　支持向量机的实现

中可找到一个线性分类函数,它对应于输入空间中

的一个非线性分类函数,要求解此时的最优分类函数涉及计算内积(zi・zj)=

k=1

支持向量机的训练本质上是解决一个二次规划

(QP)问题,即上述式(6)、式(7)。该问题可改写成以下矩阵形式:

给定训练样本(xi,yi),i=1,…,n;核函数

K(xi,xj)和调节参数C,求二次型

Q(A)=A1-T

φk(xi)φk(xj),若直∑

接求解,不仅需要知道非线性映射φ的形式,而且

Q(a)=

[4]

AHA2

(12)

的极小值并满足下列约束条件:

Ay=0,0≤ai≤C

(13)

其中,H=[hij],hij=yiyjK(xi,xj),(i,j=1,…,n);

A=(a1,a2,…,an);y=(y1,y2,…,yn);1为单位阵。

∑

i=1

ai-aiajyiyjK(xi,xj)2i,j=1

∑

(7)

现有的Chunking

[6]

,Osuna

[7]

,SMO

[8]

等训练算

相应的分类函数也变为

f(x)=sgn

法均能有效地求解以上问题。本文采用了Osuna训

∑a

i=1

yiK(xi,x)+b

(8)

练算法。其基本思想为:将一个QP问题分解成一系列较小规模的QP问题迭代求解,每次只处理部

分训练数据,当所求的解都满足最优化(Kuhn2

[9]

Tucker)条件时,便得到了优化问题的最优解。具

这就是解决非线性分类问题的支持向量机,其形式结构近似于神经网络,如图3所示。

[5]

持向量机。常用的核函数有以下几种形式:

(1)多项式核函数

K(x,xi)=(1+(x・xi)),p=1,…,n

体步骤如下:

(1)从训练样本集中取出m个(m大于支持向

量的数目)样本构成工作集B,将其余n-m个样本组成的集合记为N,N中所有样本的Lagrange乘子

a均置为0。

(2)用QP方法对B求解最优化问题,得到支持

(

向量(Lagrange乘子a不为0的向量),并构成一个分类器。

(3)用该分类器测试集合N中的样本,若N中

　　(2)高斯径向基核函数

1032

中国图象图形学报　第10卷

所有样本均满足最优化条件或N为空集则结束,否则继续。

(4)将N中至少一个不满足最优化条件的样本放入B中,同时从B中取出同样数量的样本(Lagrange乘子a为0)放入N中;返回步骤2。2.5　实例

数对一组线性不可分的两类样本进行分类识别,得

。

在此分别采用多项式核函数和高斯径向基核函

(a)

两类样本数据的分布(b)采用6阶多项式核函数

(P=6,C=Inf

)

(c)高斯径向基核函数(σ=0.5,C=10

)

(d)高斯径向基核函数

(σ=1,C=Inf)

图4　对线性不可分样本的分类结果

Fig.4　Classificationresultsofoverlappingdata

表1　两种支持向量机及不同参数的分类结果

Tab.1　Classificationresults

支持向量机

类型多项式高斯径向基

核函数中的参数

P=3,C=Inf

法

[10]

,在此不作详述。

支持向量个数

282821

测试误差

(%)3.660.040.90

3　多分类算法

[11～16]

σ=1,C=Infσ=0.5,C=10

由于C值表征的是经验风险与VC维(即推广能力)之间的权衡,而当C取无穷(Inf)时,相当于仅考虑其推广能力。从表中可以看出,在相同的惩罚

C作用下,径向基函数具有更好的分类结果和更佳

。

3.1　一对余型多类支持向量机方法

的推广能力,且其卓异的分类精度是传统方法难以企及的。另外,选择不同的参数也将导致分类精度的不同,关于参数的选择可参考Cross2validation方

　第8期　

陆　波等:支持向量机在分类中的应用

1033

所示二值分类器,分别使用SVM二值分类算法对这

M个训练集进行学习,便可以构造M个分类器。

对于k分类问题,取所有y=i和y=j的训练样

对于一对一算法,Plat等人提出了一种新的学习构架:决策导向无环图(decisiondirectedacyclicgraph,DDAG)。对于k分类问题,DDAG也含有

k(k-1)/2个二值分类器,而在对多个一对一分类

4　基于支持向量机分类的应用

4.1　与新理论的综合应用

随着混沌理论、小波理论、模糊理论、粗糙集理论等一批新兴的智能学科的兴起,支持向量机算法在应用过程中也出现了一些新的发展趋势。

(1)与混沌理论的综合应用

采用混沌型支持向量机的时序分析框架,利用混沌特征参数选择合适的预测器结构,然后在进行预测分析时取得了很好的效果。

(2)与小波理论的综合应用

基于小波和支持向量机的滚动轴承状态监测方法,利用小波能量提取信号特征,然后利用支持向量机进行分类,取得了较为满意的结果

(3)与模糊理论的综合应用

[17]

器进行组合的过程中,引入了图论中的有向无环图(DAG)的思想。训练方法与一对一方法基本类似,测试时按照DDAG图进行计算。3.4　K类支持向量机方法

K类支持向量机算法与一对多方法类似,它也

是构造k个支持向量机决策函数,不同的是所有支持向量机的参数是通过求解一个二次规划问题获得。

3.5　LS2SVM型多类支持向量机方法

Suykens将二分类LSSVM方法推广到了多类别

。

模糊一对多方法和模糊一对一方法,有效地消除了不可分边界,较好地提高了多类支持向量机的分类精度。

(4)与粗糙集理论的综合应用

采用粗糙集进行特征属性约减的多类支持向量机方法,并将其应用到城市污水监控中去,取得了较好的效果,并具有一定的容错性4.2　应用领域

[22]

[18～21]

问题,本质上还是将二次规划的求解问题转化成为

线性规划问题。

3.6　ECOC型多类支持向量机方法

。

近来,随着支持向量机理论的完善和快速发展,支持向量机在众多领域得到了广泛的应用,例如手写体识别

[22]

,人脸识别与检测,计算机系统入侵监

[23]

测、文本分类,基因、蛋白质分析,语音识别,图像分类,故障诊断

等。

　第8期　

陆　波等:支持向量机在分类中的应用

1033

所示二值分类器,分别使用SVM二值分类算法对这

M个训练集进行学习,便可以构造M个分类器。

对于k分类问题,取所有y=i和y=j的训练样

对于一对一算法,Plat等人提出了一种新的学习构架:决策导向无环图(decisiondirectedacyclicgraph,DDAG)。对于k分类问题,DDAG也含有

k(k-1)/2个二值分类器,而在对多个一对一分类

4　基于支持向量机分类的应用

4.1　与新理论的综合应用

随着混沌理论、小波理论、模糊理论、粗糙集理论等一批新兴的智能学科的兴起,支持向量机算法在应用过程中也出现了一些新的发展趋势。

(1)与混沌理论的综合应用

采用混沌型支持向量机的时序分析框架,利用混沌特征参数选择合适的预测器结构,然后在进行预测分析时取得了很好的效果。

(2)与小波理论的综合应用

基于小波和支持向量机的滚动轴承状态监测方法,利用小波能量提取信号特征,然后利用支持向量机进行分类,取得了较为满意的结果

(3)与模糊理论的综合应用

[17]

器进行组合的过程中,引入了图论中的有向无环图(DAG)的思想。训练方法与一对一方法基本类似,测试时按照DDAG图进行计算。3.4　K类支持向量机方法

K类支持向量机算法与一对多方法类似,它也

是构造k个支持向量机决策函数,不同的是所有支持向量机的参数是通过求解一个二次规划问题获得。

3.5　LS2SVM型多类支持向量机方法

Suykens将二分类LSSVM方法推广到了多类别

。

模糊一对多方法和模糊一对一方法,有效地消除了不可分边界,较好地提高了多类支持向量机的分类精度。

(4)与粗糙集理论的综合应用

采用粗糙集进行特征属性约减的多类支持向量机方法,并将其应用到城市污水监控中去,取得了较好的效果,并具有一定的容错性4.2　应用领域

[22]

[18～21]

问题,本质上还是将二次规划的求解问题转化成为

线性规划问题。

3.6　ECOC型多类支持向量机方法

。

近来,随着支持向量机理论的完善和快速发展,支持向量机在众多领域得到了广泛的应用,例如手写体识别

[22]

,人脸识别与检测,计算机系统入侵监

[23]

测、文本分类,基因、蛋白质分析,语音识别,图像分类,故障诊断

等。

1034

中国图象图形学报　第10卷

2　VapnikVN.TheNatureofStatisticalIearningTheory[M].New

5　支持向量机的发展趋势

对于支持向量机算法,目前尚存在许多需要解决的问题,主要有以下几方面需要着重研究:

York:Springer,1995.

3　VapnikV,LevinE,LeCunY.MeasuringtheVC2dimensionofa

learningmachine[J].NeuralComputation,1994,8(5):51～76.4　BurgesC.

Atutorialonsupportvectormachinesforpattern

recognition[J].DataMiningandKnowledgeDiscovery,1998,2(2):1～47.

5　OsunaE,FreundR.Supportvectormachines[A].In:TrainingandApplications[R],TechnicalReportAlm21602,CambridgeMA,USA:MIT,1997,2:527～531.

6　VapnikV.EstimationofDependenceBasedonEmpiricalData[M],NewYork:SpringerVerlag,1982.

7　OsunaE,FreundR.Animprovedtrainingalgorithmfortraining

supportvectormachines[A].In:ProceedingsofIEEEWorkshoponNeuralNetworksforSignalProcessing[C],NewYork,1997,1:252～256.8　PlattJ.

SequentialMinimalOptimization:AFastAlgorithmfor

TrainingSupportVectorMachines[M].Cambridge:TheMITPress,1998:169～182.9　FletcherR.

PracticalMethodsofOptimization[M].NewYork:

WileyandSonsPress,1987.

10AlexanderSmola.RegressionEstimationwithSupportVectorLearningMachines[EB/OL].http://www.firstgmd.de/smola,2000206205.11AllweinL,RobertE.Reducingmulticlasstobinary:Aunifying

approachformarginclassifiers[J].JournalofMachineLearningResearch,2000,1(1):113～141.12Pairwise.

ClassificationandSupportVectorMachines[M].

Cambridge:TheMITPress,1999.

13PlattJC,CristianiniN,Shawe2TaylorJ.LargemarginDAGsformulticlassclassification[J].

AdvancesinNeuralInformation

ProcessingSystems,2000,12(12):547～553.

14SuykensJAK,VandewalleJ.MulticlassLeastSquaresSupportVectorMachines[R],TR19992012.WashingtonDC,America:WashingtonIstituteofTechnology,1999.

15KindermannJ,LeopoldE,PaassG.Multi2ClassClassificationwith

ErrorCorrectingcodes[EB/OL].http://www.firstgmd.2004211204.

16Chih2WeiHsu,Chih2JenLin.Acomparisonofmethodsformulticlass

supportvectormachines[J].IEEETransactionsonNeuralNetworks,2001,13(2):415～425.17LIYing2hong,

WEIXun2kai,

LIU

Jian2xun.

Engineering

ApplicationsofSupportVectorMachines[M].Beijing:PublishingHouseofOrdnanceIndustry,2004.[李应红,尉询楷,刘建勋.支

持向量机(sphere2structuredSVM),也有一些采用组合支持向量机进行决策分类的新方法,如采用Logistic回归进行SVM组合的方法等。如何选择恰

当的组合方法获得满意的推广性能是支持向量机用于多分类问题中需要深入研究的方向。

(4)高效、快速的实现方法　目前主要的支持向量机实现方法有:内点算法(interiorpoint),Newton梯度法,以及求解大型问题的Chunking选块

参考文献(References)

1　BIANZhao2qi,

ZHANGXue2gong.

PatternRecognition[M].

持向量机的工程应用[M].北京:兵器工业出版社,2004.]

18InoueT,AbeS.

Classication[R].

FuzzySupportVectorMachinesforPatternTR20012005,

WashingtonDC,

America:

WashingtonIstituteofTechnology

19LinChunfu,WangShengde.Fuzzysupportvectormachines[J].

IEEETransactionsonNeuralNetworks,2002,13(3):464～471.20HuangHan2Pang,LiuYi2Hung.Fuzzysupportvectormachinesfor

patternrecognitionanddatamining[J].

InternationalJournalof

Beijing:TsinghuaUniversityPress,2000.[边肇祺,张学工.模式识

别[M].北京:清华大学出版社,2000.]

　第8期

FuzzySystems,2002,14(3):25～28.

陆　波等:支持向量机在分类中的应用

2003.]

1035

21FANXi2wei,DUShu2xing.Roughsupportvectormachineandits

applicationtowastewatertreatmentprocesses[J].

Controland

Decision,2004,19(5):573～576.[范昕炜,杜树新.粗SVM分

23WEIXun2kai,LIYing2hong.Applicationsofsupportvectormachines

inaeroenginefaultdiagnosis[J].JournalofAerospacePower,2004,19(6):844～848.[尉询楷,李应红.支持向量机在航空发动机故

类方法及其在污水处理过程中的应用[J].控制与决策,2004,

19(5):573～576.]22WEIXing2guo.

Research

HandwrittenNumericalDigits

RecognitionBasedonKernel2basedLearningAlgorithm[D].Nanjing:NanjingUniversityofScienceandTechnology,2003.[魏兴

障诊断中的应用[J].航空动力学报,2004,19(6):844～848.]

24AyatNE,CherietM.Anewsupportvectormachinekernelfor

patternrecognition,applicationtodigitimagerecognition[A].andRecognition[C],Seattle,USA,2001:1215～1219.

In:

Proceedingsofthe6thInternationalConferenceonDocumentAnalysis

国.基于核方法的手写体数字识别[D].南京:南京理工大学,

支持向量机在分类中的应用

相关文章