多类支持向量机算法综述(2)

多类支持向量机算法综述

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