多类支持向量机算法综述

多类支持向量机算法综述

第24卷第4期2005年12月

计　算　技　术　与　自　动　化ComputingTechnologyandAutomation

Vol124,No14

　Dec.2005

文章编号:1003-6199(2005)04-0061-03

多类支持向量机算法综述

黄　勇,郑春颖,宋忠虎

(空军工程大学导弹学院,陕西三原　713800)

摘　要:传统的支持向量机是基于两类问题提出的,如何将其有效的推广至多类问题仍是一个有待研　　

究的问题。本文中作者致力于对现有的几种较有成效的多类支持向量机做一介绍,并比较其优劣,以期对研究者以后的研究能有所启发。

关键词:支持向量机;多类;有向无环图;纠错编码支持向量机中图分类号:TP391　　　　　　文献标识码:A

Multi-classSupportVectorMachinesHUANGYong,ZHENGChun22(MissileInstituteofAirForce713800,China)

Abstract:TraditionalSupport(designedforbinaryclassification.Howtoeffectively

extenditformulti-researchissue.Thispaperwilltypicallyintroduceseveralexistingmulti-classclassifierandanddisadvantage.Theauthorhopesthatthisarticlecangiveinvestigatorssomeillu2minationintheirpresentdayinvestigation.

Keywords:supportvectormachines(SVM);multi-class;DAG;ECOCSVMS

1　引言

机器学习是现代智能技术中十分重要的研究领域,它

通过对已知数据的学习,找到数据内在的相互依赖关系,从而获得对未知数据预测和对其性质的判断能力[1]。支持向量机(SVM)[2]是新型机器学习方法,具有完备的统计学习理论基础,它采用结构风险最小化原则代替传统统计学中的基于大样本的经验风险最小化原则,克服了神经网络受到网络结构复杂性和样本容量的影响大,容易出现过学习或低泛化能力的不足,对于小样本数据分析具有出色的学习能力和推广能力,在模式识别和函数估计中得到了有效的应用[3]。不过,SVM是一种两类分类器,而实际需要解决的一般是多类问题。因此如何将SVM有效的应用于多类分类已成为人们研究的热点[4]。至今,人们对多类支持矢量机求解分类问题的研究虽还有待完善,但也取得了一定的成就,提出了几种卓有成效的方法。下面作者将对几种有见地的多类支持向量机一一做一介绍,并比较其优劣,以便广大研究者在今后的研究中能汲取各种方法之优点,尽量避免现有方法存在的各种弊端,研发更加行之有效的多类分类器。

2　多类支持向量机

传统的SVM是基于两类问题的,而实际需要解决的一般是多类问题。因此将SVM应用于多类问题对挖掘SVM的应用潜力将具有非常重要的意义。目前,利用SVM处理多类分类问题是当前的研究热点之一,研究者们已提出了一些卓有成效的方法,现归纳如下:

2.1　解决n-类问题的直接方法

该方法是以Weston[5]在1998年提出的多值分类算法为代表,这个算法在经典SVM理论的基础上重新构造多值分类模型,通过SV方法对新模型的目标函数进行优化,实现多值分类,它实际上是标准SVM中二次优化问题的一种自然的推广:

)=min<(ω,ξ

2

m=1

∑

n

(ωm ωm)+C

i=1m≠y

ξ∑∑

i

l

m

i

其约束条件为:

(ωy <(xi))+by≥(ωm <(xi))+ii

m

　　bm+2-ξi

mξi≥0,i=1,…,l..　　m,yi∈{1,…,n},由此,得到下面的n类SVM分类器的决策函数:

(1)

收稿日期:2005-04-13

基金项目:陕西省自然科学研究项目(2004F36)

),男,湖南长沙人,研究方向:计算机控制,支持向量机(E-mail:21cnn01@);郑春颖(1979—),女,陕作者简介:黄勇(1973—

西户县人,研究方向:模式识别,支持向量机。

多类支持向量机算法综述

62计算技术与自动化2005年12月

f(x)=argmax[wi <(x)+bi],i=1,…,n

i

显然,该方法的一个明显缺点是选择的目标函数过于复杂,从而导致它的计算复杂度高,但其优点是SV少,训练速度快。

2.2　通过组合多个二值分类器来构造多类分类器

通过组合多个二值分类器来实现对多类分类器的构造,常见的构造方法是“一对一”、“一对多”两种。此外,近年来的改进算法有:纠错编码支持向量机(ECOCSVMS)、层次支持向量机(H-SVMS)、有向无环图支持向量机(DAG-SVMS)等。

[5-7]

(1)“一对多”

在该分类方法中对n个类别仅需构造n个支持向量机,每一个支持向量机分别将某一类的数据从其他类别中分离出来。在测试时,取决策函数输出值最大的类别为测试样本的类别。其第i个SVM可通过解决下面的最优化问题得到:

iiiw,b,ξ

种分布式输出码,1995年Dietterich和Bakiri[5]提出用ECOC解决多类模式识别问题。具体过程如下:由1和0组

QS

成的一个码矩阵,设为M,其中Q为类别数,S为待训练的分类器数,当mqs=1(mqs=0)时表示此样本相对于第q类而言是作为正例(负例)来训练第s个分类器fs的。ECOC的工作分两步:训练和测试。在训练过程中,依上述原则训练分类器f(x)=(f1(x),…,fs(x)),在测试过程中,对于新例x,计算分类器f(x)的输出向量与各类别向量的距离,使其距离最小的类即为x所属的类。即:

k=argmind(Mq,f(x))

q∈(1,Q)

min

i

(wi)Twi+Cξj2j=1

l

∑

:

i

(wi)T<(xj)+bi≥1-ξj,yj=i

i(wi)T<(xj)+bi≤1+ξj,yj≠i

ij≥0,j-1,…,l

解(2)后,得n个决策函数:

(w1)T<(x)+b1　　　…

(wn)T<(x)+bn

则x所属类为:argmax[(wi)T<(x)+bi]

i

(2)

“一对多”SVMS简单、有效,训练时间较短,可用于大规模数据。但其缺点在于:1)当类别数较大时,某一类的训练样本将大大少于其它类训练样本的总和,这种训练样本间的不均衡将对精度产生影响;2)存在误分、拒分区域;3)泛化能力较“一对一”差。

[5,6,8,9]

(2)“一对一”

在该分类方法中,各个类别之间构造分类器,对n个类别共需构造n(n-1)/2个分类器,每个分类器函数的训练样本是相关的两个类,组合这些两类分类器并使用投票法,得票最多的类为样本点所属的类。具体的讲,对第i类和第j类之间的分类器,我们通过解下面的最优化问题得到:

ij

(wij)Twij+C∑ξmint

ijjiji2tw,b,ξ

:

ji

(wij)T<(xt)+bij≥1-ξt,yt=i

(3)ij

(wij)T<(xt)+bij≤1+ξt,yt≠i

共构造n(n-1)/2个决策函数,判断max[(wij)T<(x)+

i

b],若属i类,则i得票数加一,否则j得票数加一。最终得

ij

票最多的类即为样本点x所属的类。

该算法的优点是:由于每个SVM只考虑两类样本,故单个SVM容易训练,且其决策边界较“一对多”简单;另外,虽然它的复杂度以类数按平方增长,但就分类速度来说,其并不比传统的“一对多”方法慢;而且其分类精度也较“一对多”高。缺点是:1)如果单个两类分类器不规范化,则整个n类分类器将趋向于过学习;2)推广误差无界;3)分类器的数目随类数急剧增加,导致在决策时速度很慢;4)存在误分、拒分区域。

(3)ECOCSVMS

ECOC是Bose和RayChaudhuri[12]在1960年提出的一

其中,k为x所属类别,d为汉明距(Hsmmingdistance)

S

()(4)d(Mq,f(x))=2s=1

ECOCSVMS的训练速度较“一对多”有明显改进,且当类别数大时仅需要少量的分类器。然而如何根据具体问题确定码本、选择排列顺序以达到最优的分类性能依然有待研究,且其分类效果受错误码的相关性影响很大[13],另外对类别超过10。

(4)层支持向量)[5,6,14]、DAG-[5,10,11]

)首先将所有类别,如此循环下,这样就得到一个倒立的,其中两个子类间的分类函数采用SVMS。目前广泛使用的DAG-SVMS既是层次分类法的一个特例,它每步所分成的两个子类几乎是均衡的,所得结构可近似看作一棵正态二叉树。

DAG-SVMS是由Platt提出的决策导向的循环图DDAG导出的,是针对“一对一”SVMS存在误分、拒分现象提出的。算法在训练阶段与“一对一”法同,也要构造每两类间的分类面,既有n(n-1)/2个分类器。但在分类阶段,该方法将所有分类器构成一个两向有向无环图,包括n(n-1)/2个节点和n个叶。其中每个节点为一个分类器,并与下一层的两个节点(或叶)相连。当对一个未知样本进行分类时,首先从顶部的根节点(包含两类)开始,根据根节点的分类结果用下一层的左节点或右节点继续分类,直到达到底层某个叶为止,该叶所表示类别即为未知样本的类别。具体讲,若wijT<(x)+bij≥0,则x不属于j类。

DAG-SVMS简单易行,只需使用n-1个决策函数既可得出结果,较“一对一”方法提高了测试速度,而且不存在误分、拒分区域;另外,由于其特殊的结构,故有一定的容错性,分类精度较一般的二叉树方法高。

然而,由于存在自上而下的“误差累积”现象是层次结构的固有弊端,故DAG-SVMS也逃脱不掉。即如果在某个结点上发生分类错误,则会把分类错误延续到该结点的后续结点上。因此,分类错误在越靠近根的地方发生,由于误差的累积效应,分类性能就越差,尤其在根结点上发生分类错误,将严重影响分类性能。而传统的DAG-SVMS方法:一是根的选择是随机的,二是决策走向依据决策面的值随机选取下一决策面。基于此,研究者引入分离性测度,根据分离性测度来决定决策走向,降低了误差累积效应的影响。目前这方面的研究集中在寻找有效而简便的计算分离性测度的方法。

2.3　SVM与其他模式识别方法融合的多类SVMS

虽然,与传统模式识别技术相比,SVM在解决小样本、非线性及高维模式识别问题中表现出了许多特有的优势。但SVM并不是十全十美的,其他模式识别方法在某些方面仍优于SVM。基于此,研究者提出了一些针对具体问题的

多类支持向量机算法综述

第24卷第4期黄　勇等:多类支持向量机算法综述63

SVM与其他模式识别方法融合的多类分类方法。本节将对两种有创意的方法做一介绍。

(1)模糊多类支撑矢量机

模糊集理论是为了刻画事物的不确定性提出的理论,将模糊集理论应用于模式识别将使识别结果更符合客观事实,有利于提高识别率。最早提出模糊SVM的是Takuyalnoue和ShigeoAbe2001在IJCNN中发表的文章FuzzySupportVectorMachinesforPatternCladdification中提出的,文中尽管给出了模糊支撑矢量机样本类别的隶属函数,但是却没有有效的引用且计算公式比较复杂。因此后来的研究者们致力于对其进行改进。比较有代表性的一个

[16]

是郑春红等提出了一种基于FSVM的雷达多目标识别方法,该法在最优超平面这一概念的基础上,根据该区域样本点的决策函数定义样本类别的模糊隶属度,并在此基础上,提出新的模糊多类支撑矢量机,修正了决策函数,此法能够减少目标的错分和拒分数量,在识别率上有了很大的提高,而且对于高维的雷达距离像不需要做任何的特征提取。同时,当多分类器训练好以后,目标识别仅仅是计算模糊决策函数的值,可以大大地减少识别时间;另一个是李昆仑[17]等提出的一种模糊多类支持向量机模型,即FMSVM。该方法是在Weston等人提出的多类SVM模型中引入模糊成员函数,影响,该模糊成员函数为其赋予不同的值,惩罚值。果影响很小的数据,响。,好。

(2)融合无监督和监督两种学习策略生成多分类决策树方法

该方法有邱德红[15]等提出的。它首先利用无监督聚类方法能够发现待分类样本之间的内在联系和规律的特点,确定出最为符合多类样本分布特征的决策树的树型,继而利用监督学习支持向量机的方法对样本进行准确的分类。该方法具有灵活解决问题的能力,实现了策略之间的优势互补,在解决多分类问题上体现了问题产生的刺激机制和人们区分多种类别时先易后难的思维习惯,实现了比较高的计算效率和分类效果。

Binary:AUnifyingApproachforMarginClassifiers[J].JournalofMachineLearningResearch1(2000)113141:118～129.[2]　李国正等,译.支持向量机导论[M].北京:电子工业出版社,2004.

[3]　边祺,张学工,等.模式识别[M].北京:清华大学出版社,

2004,(8):176～226.[4]　王建芳,等.支持向量机在大类别数分类中的应用[J].北京

理工大学学报,2001,2(2):225～227.[5]　刘志刚,等.支持向量机在多类分类问题中的推广[J].计算

机工程与应用,2004,(7):10～13.[6]　赵晶,等.基予支持向量机的多类形状识别系统[J].合肥工

业大学学报,2004,27(1):23～26.[7]　萧嵘,等.一种具有容噪性能的SVM多值分类器[J].计算机

研究与发展,2000,37(9):1071～1075.[8]　孙即祥,等.现代模式多类识别[M].长沙:国防科技大学出

版社,2002.[9]　U.H.-G.Kre?el,Pairwiseclassificationandsupportvector

machines.InB.Sch¨olkopf,C.J.C.Burges,andA.J.Smo2la,editors,AdvancesinKernelMethods:[J]SupportVectorLearning:255～268.[10]　J.C.,N.,rge

GsInS.A.Solla,T.K.-,editors[J].AdvancesinNeuralSystems12:547～sivakul.Multiclasssupportvectorma2

chinesusingadaptivedirectedacyclicgraph[D].InProceedingsofInternationalJointConferenceonNeuralNetworks(IJCNN2002):980～985.[12]　吴成东,等.基于误差修正码的支持向量机大类别分类方法

[J].沈阳建筑工程学院学报(自然科学版),2004,20(1):66～70.

[13]　FrancescoRicciandDavidW.Aha.EorrorCorrectingOutput

CodesforlocalLearners[J].ChenitzGermany.April1998:21～24.[14]　J.WestonandC.Watkins.Supportvectormachinesformulti

-classpatternrecognition[D].InProceedingsof7thEuropeanSymposiumonArtificialNeuralNetworks(ESANN’99):219～224.[15]　邱德红,等.融合无监督和监督学习策略生成的多分类决策

树[J].小型微型计算机系统,2004,25(4):555～558.[16]　郑春红,等.基于FSVM的雷达多目标识别[J].系统工程与

电子技术,2003,25(11):1358～1361.[17]　李昆仑,等.模糊多类支持向量机模型[J].电子学报,2004,

32(5)830～832.[18]　徐义田,等.基于SVM的分类算法与聚类分析[J].烟台大

学学报,2004,17(1):9～13.[19]　永杰,等.分级聚类支持向量机在汽轮机故障诊断中的应用

[J].华北电力大学学报,2003,30(6):25～29.[20]　廖闻剑,等.基于多分类器决策融合的印签真伪鉴别方法

[J].南京航空航天大学学报,2002,34(4):368～371.[21]　史朝晖.SVM算法研究及在HRRP分类中的应用[D].空军

工程大学导弹学院学位论文,2005,(1):52～54.

3　结论

SVM是基于两类问题提出的,将其应用于多类分类问题必须对SVM进行扩展使它适合于多类分类,这就需一定的策略。综上,我们有以下结论:对一个多类SVM,要么需组合几个二值分类器,要么需构造一个更大的最优化问题。因此,一般地说,多类问题的解决要比具有同样数据量的两类问题的解决复杂得多。现存的各种多类支持向量机虽已应用到实际中并取得了不错的效果,但每种方法都多多少少存在一定的缺陷,更进一步的研究还有待研究者们的继续努力。

参考文献

[1]　ErinL.Allwein,RobertE.Schapire.ReducingMulticlassto

本文来源：https://www.bwwdw.com/article/gvoj.html