多类支持向量机算法综述

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。基于此,研究者提出了一些针对具体问题的