多分类簇支持向量机方法

开篇：润墨网以专业的文秘视角，为您筛选了一篇多分类簇支持向量机方法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要:针对支持向量机的多分类问题,提出一种新颖的基于非平行超平面的多分类簇支持向量机。它针对k模式分类问题分别训练产生kЦ龇指畛平面,每个超平面尽量靠近自身类模式而远离剩余类模式;决策时,新样本的类别由它距离最近的超平面所属的类决定,克服了一对一(OAO)和一对多(OAA)等传统方法存在的“决策盲区”和“类别不平衡”等缺陷。基于UCI和HCL2000数据集的实验表明,新方法在处理多分类问题时,识别精度显著优于传统多分类支持向量机方法。

关键词:支持向量机;超平面;核函数;手写体汉字识别

中图分类号: TP391.4

文献标志码:A

Multiclass cluster support vector machines

WANG Zhiyi, YANG Yifan

School of Economics Information Engineering, Southwest University of Finance and Economics,Chengdu Sichuan 610074,China

)

Abstract: Based on the idea of nonparallel hyperplanes, a novel multiclass cluster support vector machine method was proposed to settle the multiclass classification problem of support vector machines. For a kclass classification problem, it trained khyperplanes respectively, and each one lay as close as possible to selfclass while being apart from the rest classes as far as possible. Then, labels of new samples were determined by the class of their nearest hyperplane, thus the inherent limitations of OneAgainstOne (OAO) and OneAgainstAll (OAA) methods can be avoided, such as "decision blindarea" and "unbalanced classes". Finally, experiments on UCI and HCL2000 datasets show that the proposed method significantly outperforms traditional OAO and OAA in terms of recognition accuracy.

Key words: Support Vector Machine (SVM); hyperplane; kernel function; handwritten Chinese character recognition

0 引言

支持向量机(Support Vector Machine, SVM)是一种新型的基于统计学习理论的机器学习方法,具有推广能力强、维数不敏感等优点[1]。大量研究表明[2-3],它在处理文本分类、手写体汉字识别、图像检索等高维小样本数据时,识别精度显著优于神经网络、贝叶斯网络、隐马尔可夫模型等传统机器学习方法。然而,SVM在本质上解决的是二值模式分类问题,虽然已提出OAA(OneAgainstAll)、OAO(OneAgianstOne)、ECOC等方法能够将它扩展到多分类问题[4],但是,这些方法尚存在“决策盲区”、“不平衡类”等缺陷,分类器的推广能力受到一定影响。多分类支持向量机方法仍然是机器学习的研究热点之一。

本文将广义特征值支持向量机(Proximal Support Vector Machine via Generalized Eigenvalues,GEPSVM)的非平行超平面的思想引入到多分类问题[5],提出一种新颖的多分类簇支持向量机方法,并推导了它的非线性形式。基于UCI和HCL2000的实验表明,新方法能够取得非常优异的识别精度。

1 支持向量机及其多分类问题

考虑n维实空间Rnе械哪J蕉分类问题[1]:已知mЦ鲅盗费本Ai(i=1,2,…,m)Ш退们的类别标记yi∈{1,-1},а罢乙桓龇掷嗪数使得RnЩ分为两个子空间,两类样本分别属于不同的子空间。这里,Ai=(Ai1,Ai2,…,Ain)∈Rn。г诹嚼嘌本线性可分的情况下,超平面(1)可将它们区分开:

И`•x+b=0(1)

其中,И`∈Rn且b∈R。Э悸堑搅嚼嘌本到超平面都应该有一定的距离,超平面还应该满足如下的不等式约束:

yi(Ai`+b)≥1; i=1,2,…,m(2)

显然,满足要求的分类超平面不止一个。在结构风险最小化准则下,支持向量机寻找最优分类超平面,使得两类之间的分类间隔2`2ё畲,等价于求解如下的二次优化:

И┆Min`,b12`T`(3)

s.t.yi(Ai`+b)≥1; i=1,2,…,m

然而,完全满足优化问题(3)的精确分类超平面是不经常存在的。因此,考虑到某些训练样本可能不满足约束条件(2),引入松弛变量:

Е篇i≥0; i=1,2,…,m(4)

根据结构风险最小化准则,分类超平面不仅应该使分类间隔最大,同时应保持训练样本分类误差尽可能小。因此,优化问题(3)变为:

ИMin`,b,ζ12`T`+C∑mi=1ζi(5)

s.t.yi(Ai`+b)≥1-ζi;ζi≥0,i=1,2,…,m

其中,CС莆“罚参数”,在分类器的推广能力和误分类率之间进行折中。求解优化(3)或(5)的对偶问题,得到支持向量机的决策函数,如下:

f(x)=sgn(`•x+b)(6)

然而,支持向量机是二值分类器。为解决k模式分类问题(k≥2),OAA和OAO等方法通过组合多个二值分类器进行集体决策来实现多分类[4,6]。

OAA方法总共训练kЦ龆值SVM分类器,其中每个分类器的决策超平面将一类模式与剩余所有类的模式分割开,如图1(a)所示。OAO方法在每一对模式之间都训练一个二值SVM分类器,总共训练k(k-1)2Ц龇掷嗥,如图1(b)所示。进行决策时,二值SVM分类器分别对新样本xЫ行判别,并按照多数投票的方法决策出xУ淖钪绽啾稹

图片

图1 OAA和OAO多分类方法

然而,OAA方法存在以下明显缺陷:

1) 决策“盲区”难以避免(图1的阴影区域)。如果输入样本位于该区域,则OAA方法不容易对它的类别进行正确判别。

2) 容易引起不平衡类的问题。当k取值较大时,任意一类样本与其剩余样本的规模差异很大,使得分类器的推广能力受到影响。

对于OAO方法,它训练的部分二值SVM分类器需要被迫进行错误决策,将致使推广能力下降。例如,图1中在“Ⅰ”和“Ⅲ”类样本上训练的二值分类器为HИⅠ,Ⅲ;如果输入样本x属于“Ⅱ”类,显然,HИⅠ,Ⅲ无论怎样决策,都会做出错误判断。

分析可知,支持向量机强制它的决策超平面И`•x+b=0平分两个边界超平面И`•x+b=±1е间的最大间隔。这对于平衡类情况下的二模式分类问题非常适合,但对多模式分类问题,反而是分类器推广能力下降的主要原因之一。本文将GEPSVM的非平行超平面的思想引入到多分类问题,提出一种新颖的多分类方法(MCSVM)。

┑1期 ┩踔怡等:多分类簇支持向量机方法

┆扑慊应用 ┑30卷

2 多类簇支持向量机

假设A(1)i(i=1,2,…,m1)Ш酮A(2)i(i=1,2,…,m2)Х直鸨硎臼粲凇+1”类和“-1”类的训练样本。GEPSVM方法通过求解两个不平行的超平面xT`(1)+b(1)=0Ш酮xT`(2)+b(2)=0Ч餐对未知样本的类别进行决策。每一个超平面尽量靠近一类样本而尽量远离另外一类样本,并可由以下的优化问题求解[5]:

И┆Min`,b≠0(A(1)`+eb22+δ[`,b]T22)A(2)`+eb22 (7)

其中:A(1),A(2)Х直鹗仟m1×nШ酮m2×n维矩阵,是两类样本的矩阵表示;Е>0是控制超平面复杂度的正则参数。文献[5]指出,去掉超平面的平行限制条件后,分类器的推广能力并不会受到显著影响;相反,由于式(7)是一个典型的广义特征值问题,能够大幅度地提高分类器的训练速度。

本文将非平行超平面的思想扩展到SVM的多分类问题,提出一种新颖的多分类簇支持向量机――MCSVM。它针对k模式的分类问题,同时求解kЦ龀平面,其中每个超平面尽量靠近自身类模式,而远离剩余类的模式(如图2所示)。

图片

图2 多分类簇支持向量机的超平面

设属于第kЮ嗟难本分别用矩阵A(1),A(2),…,A(k)П硎,数量分别为m1,m2,…,mk(且满足m1+m2+…+mk=m)。Т送,令kЦ龀平面分别表示为xT`(i)+b(i)=0,i=1,2,…,k,г蛩们可以通过求解如下的一组二次优化问题得到:

И┆Min`(1),b(1),ζ12A(1)`(1)+e1b(1)22+C11ζ(8)

s.t.┆(1)(┆(1)`(1)+1b(1))≥1-ζ,ζ≥0

И┆Min`(k),b(k),ζ12A(k)`(k)+ekb(k)22+Ckkζ(9)

s.t.┆(k)(┆(k)`(k)+kb(k))≥k-ζ,ζ≥0

其中,И(1)П硎居傻冖窭嘀外的所有训练样本构成的数据矩阵,维数为(m-m1)×n;ИИ(1)是其类标记(均视为“-1”类)组成的对角矩阵。Е篇是松弛向量,e1Ш酮И1是全1向量。

上述kЦ鲇呕问题显然是同构的,并且和SVM的优化问题(5)在形式上一致,这是称之为“多类簇支持向量机”的原因。以式(8)为例对它的特点进行分析。

显然,目标函数的第一项表示所有属于第Ⅰ类的样本距离超平面的欧氏距离之和。约束条件要求所有不属于第Ⅰ类的样本与超平面的距离都至少为1。与SVM类似,引入松弛向量Е篇Ф栽际条件进行松弛。目标函数的第二项表示对所有靠近超平面的非第Ⅰ类的样本进行惩罚,以使得它们尽量远离超平面。因此,优化问题(8)求解得到的是靠近第1类样本,而远离剩余所有样本的最优超平面。

注意到,优化问题(8)中只对第Ⅰ类之外的样本进行约束,这种方式避免了多类SVM方法中常见的“类别不平衡”问题。

优化问题(8)的拉格朗日对偶问题为[1]:

L(`(1),b(1),ζ,α,β)=12A(1)`(1)+e1b(1)22+

C11ζ-αT((1)((1)`(1)+1b(1))-1+ζ)-βTζ(10)

其中,Е=(α1,α2,…,α(m-m1))TШ酮Е=(β1,β2,…,β(m-m1))T是大于0的拉格朗日乘子。根据约束优化问题取极值时的KKT条件,函数Lвβ足以下条件:

ИL氮`(1) = A(1)T(A(1)`(1) + e1 b(1))-(1)T(1)α = 0(11)

ИLb(1)=eT1(A(1)`(1)+e1b(1))-T1(1)α=0(12)

ИL郸=C11-α-β=0(13)

И(1)T((1)`(1)+1b(1))≥1-ζ,ζ≥0(14)オ

Е联T((1)T((1)`(1)+1b(1))-1+ζ)=0,βTζ=0(15)

Е痢0,β≥0(16)オ

定义新矩阵P=[A(1) e1]Ш酮Q=[(1) 1],以及向量uT=[`(1)T b(1)],Ш喜⑹(11)和(12),得到:

PTPu-QT(1)α=0u=(PTP)-1QT(1)α(17)

由式(13)和(16)容易推得:

0≤α≤C1(18)

将式(13)和(17)代入函数L,Ь过整理得到优化问题(8)的Wolfe对偶问题:

И┆Maxα T1 α-12αTQPTP-1QTα(19)

s.t. 0≤α≤C1

实矩阵PTP是(n+1)×(n+1)Ы装胝定,PTP>0时则逆矩阵存在;若出现PTP=0У那榭,可以采用岭回归的方法,用(PTP+εI)У哪嫣娲[7]。其中,Е>0是非常小的实数。

显然,优化(19)与标准SVM的对偶问题在形式上完全一致,许多成熟的算法可以对它进行求解[1]。

求解出Е联У闹岛,代入式(17),立即可以第1类样本的超平面方程xT`(1)+b(1)=0。Ф杂谑S嗟莫k-1Ц龀平面,可以按照类似的方法求出它们的超平面方程,即:

xT`(i)+b(i)=0,i=1,2,…,k(20)

此后,多类簇支持向量机的决策函数为:

f(x)=┆argMini=1,2,…,kxT`(i)+b(i)(21)

也即,MCSVM将新样本xУ睦啾鹋卸衔其最靠近的超平面所在的类别。相比于OAA和OAO方法通过多数投票来决定x所属的类别,MCSVM能够有效避免“决策盲区”的发生(见图1)。

3 非线性核函数的情况

核函数在现代机器学习中起着重要作用。满足Mercer条件的核函数能够将n维输入空间Rnе械难本映射到某个高维特征空间F,Ъ捶窍咝杂成洫Е:x|φ(x)使得样本在Fе懈容易被分类[1]。通过引入核函数K(x,z)=φ(x)•φ(z),Ф远嗬啻刂С窒蛄炕进行扩展。

假设MCSVM在高维空间Fе械莫kЦ龀平面为:

K(x,BT)ψ(i)+b(i)=0; i=1,2,…,k(22)

其中,BT=[A(1)T (1)T]是全部样本的数据矩阵。显然,当核函数为线性函数K(x,z)=xTz时,令И`(i)=BTψ(i)П憧苫指闯龉式(20)的线性超平面。

容易得出非线性核函数情况下的多类簇支持向量机的原始优化问题:

ИMinv(1),b(1),ζ12K(A(1)T,BT)ψ(1) + e1 b(1)22+ C1 1 ζ(23)

s.t. (1)(K((1)T,BT)ψ(1) + 1 b(1))≥1 -ζ,ζ≥0オ

ИMinv(k),b(k),ζ12K(A(k)T,BT)ψ(k) + ek b(k)22+ Ck k ζ(24)

s.t. (k)(K((k)T,BT)ψ(k) + kb(k))≥k-ζ,ζ≥0オ

与前面类似,通过拉格朗日对偶方法对(23)进行求解。经过整理,得到其对偶问题:

И┆MaxαT1 α-12αTG(HTH)-1GTα(25)

s.t. 0≤α≤C1

其中,H= [K(A(1)T,BT)e1]和G = [K((1)T,BT) 1 ];Ф向量v=[ψ(1)T b(1)]T满足:

v=[ψ(1)T b(1)]T=(HTH)-1GT(1)α(26)

因此,求解出二次优化问题(25)后,即可得到第Ⅰ类样本在高维空间Fе械某平面方程。对于剩余的k-1Ц龀平面,可以按相同的方法得到。

4 实验与结果分析

为了验证本文提出的多类簇支持向量机方法的性能,首先在7个UCI评测数据集上分别采用MCSVM、OAA、OAO和ECOC[4]方法训练分类器,并比较它们取得的识别精度。其中,ORHD和PRHD分别表示数据集“optical recognition of handwritten digits”和“penBased recognition of handwritten digits”。

公平起见,实验中所有分类器均采用高斯核函数,支持向量机的罚参数和核参数通过5fold交叉验证方法选取。表1给出了4种多分类方法获得的测试精度。

表格(有表名)

表1 UCI数据集上获得的测试精度比较%

数据集MCSVMOAAOAOECOC

segment97.8196.1796.2996.32

heart86.6884.0783.8185.92

vehicle89.3087.0587.4788.66

letter88.8986.2186.3488.04

waveform90.5588.5488.7688.60

ORHD99.1398.2698.2098.73

PRHD99.2098.0398.3199.02

实验结果表明,在所有数据集上,MCSVM训练分类器获得的测试精度显著优于OAA和OAO方法,平均提升了约1.90%和1.77%。而ECOC方法相对不稳定,在segment和waveform数据集上的精度明显偏低。

进一步,将MCSVM方法应用在金融手写体汉字自动识别系统中,检验其训练多分类器时的性能。训练数据取自北京邮电大学手写汉字样本库HCL2000的21个金融汉字(如图3所示)。

图片

图3 常用的21个金融手写体汉字

每个汉字随机抽取800个图像样本(前500个用于训练,后300个用于测试)。图像经预处理后,分别采用弹性网格骨架方向特征(EM_TDF)、弹性网格轮廓方向特征(EM_CDF)、弹性网格边缘方向特征(EM_EDF)和弹性网格轮廓方向角特征(EM_CDAF)、弹性网格笔画方向特征(EM_SDF)5种特征提取方法产生5组不同的数据集,每个样本含256维特征。

在生成的5个数据集上,分别采用MCSVM、OAA、OAO、ECOC方法训练多类分类器,模型参数仍通过5fold交叉验证方法选取。表2给出高斯核函数情况下,4种多分类方法获得的测试精度。

显然,将MCSVM应用于金融汉字识别问题能取得较好的识别精度,相比其他3种多类支持向量机方法,平均识别精度提高了1.13%~1.64%。其中,在“弹性网格轮廓方向角特征”数据集上,采用高斯核函数的MCSVM取得99.68%的最高测试精度,高于剩余3种方法中最高的98.76%。

表格(有表名)

表2 HCL2000数据集上获得的测试精度比较%

数据集MCSVMOAAOAOECOC

EM_TDF97.8196.3396.4996.62

EM_CDF97.2995.5695.4395.97

EM_EDF99.0397.7198.0298.30

EM_CDAF99.6898.3098.2498.76

EM_SDF98.4697.3797.5098.03

基于UCI和HCL2000数据集上的实验结果表明,MCSVM由于采用了非平行超平面去逼近不同类样本的分布区域,避免了OAA、OAO等方法存在的“决策盲区”和“不平衡类”等不足,能够很好地解决传统支持向量机在处理多分类问题时的困难。

5 结语

本文针对OAA和OAO等多分类支持向量机方法存在的“决策盲区”和“类别不平衡”等问题,提出一种新颖的基于非平行超平面的多类簇支持向量机方法,并利用拉格朗日函数推导了它的对偶二次优化形式进行求解。基于UCI和HCL2000数据集的实验结果表明,新方法能够获得非常高的识别精度,明显优于传统的多类支持向量机方法。

参考文献:[1] VAPNIK V N. 统计学习理论的本质[M].张学工,译. 北京:清华大学出版社,2000.

[2]高学, 金连文, 尹俊勋. 一种基于支持向量机的手写汉字识别方法[J].电子学报,2002,30(5):651-654.

[3]DONG J X, KRZYZAK A, SUEN C Y. An improved handwritten Chinese character recognition system using support vector machine[J]. Pattern Recognition Letters, 2005,26(12):1849-1856.

[4]HSU C W, LIN C J. A comparison of methods for multiclass support vector machines[J]. IEEE Transactions on Neural Networks, 2002,13(2): 415-425.

[5]MANGASARIAN O L, WILD E W. Multisurface proximal support vector machine classification via generalized eigenvalues[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005,27(12):1-6.

[6] WANG Y C, CASASENT D. New support vectorbased design method for binary hierarchical classifiers for multiclass classification problems[J]. Neural Networks, 2008,21(4):502-510.

[7] SAUNDERS C, GAMMERMAN A, VOVK V. Ridge regression learning algorithm in dual variables[C]// Proceedings of the 15th International Conference on Machine Learning.San Francisco: Morgan Kaufmann Publishers, 1998: 515-521.