一种改进的支持向量机多类分类方法

摘 要:提出一种新的基于二叉树结构的支持向量机(SVM)多类分类方法。该方法解决了现有主要算法中存在的不可分区域问题,具有简单、直观、重复训练样本少的优点。为了提高分类模型的推广能力,必须使样本分布好的类处于二叉树的上层节点,才能获得更大的划分空间。因此,该算法采用类间散布度量与类内散布度量的比值作为二叉树的生成算法。采用UCI标准数据集实验,实验结果表明该算法具有一定的优越性。

关键词:支持向量机;多类分类;二叉树;多类支持向量机

中图分类号:TP391文献标识码:A

文章编号:1004-373X(2009)20-143-04

Improved Multiclass Classification Methods for Support Vector Machine

GUO Yaqin1,WANG Zhengqun2

(1.ZiLang Vocational Technical College,Nantong,226002,China;2.School of Information Engineering,Yangzhou University,Yangzhou,225009,China)

Abstract:The multiclass SVM methods based on binary tree are proposed.The new method can resolve the unclassifiable region problems in the conventional multiclass SVM method,it is simple and has little duplicating training samples.To maintain high generalization ability,the most widespread class should be separated at the upper nodes of a binary tree.The ratio of between-class scatter and within-class scatter is used to be rules of constructing binary tree.Numerical experiment results show that the multiclass SVM methods are suitable for practical use.

Keywords:support vector machines;multiclass classification;binary tree;multiclass support vector machine

0 引 言

支持向量机(Support Vector Machine,SVM)方法最初是针对二类模式分类而提出的,如何将其有效地推广到多类别分类仍是当前支持向量机研究的重要内容之一。目前,对于多类分类问题,SVM的解决途径有两种:

(1) 通过构造多个SVM二值分类器并将它们组合起来实现多类分类,例如one-versus-rest[1],one-versus-one和DAGSVM[2],虽然这三种方法是目前最常用且性能较优的,但one-versus-rest和one-versus-one方法的泛化误差是无界的。再者one-versus-one所需构造的子分类器的数量关于类别数k成超线性增长,共k(k-1)/2个,且在分类阶段,都必须计算所有子分类判据函数。one-versus-one方法还有一个最明显的缺点是,每个子分类器都要非常仔细的调整,如果某个子分类器不规范化,则整个分类系统将趋于过学习。DAGSVM方法解决了不可分区域问题,而且不一定要计算所有的子分类判决函数,但各个子分类器在有向无环图中的位置也会对分类系统产生较大的影响。

(2) 直接在一个优化公式中同时考虑所有子分类器的参数优化。严格的讲,它的思想类似于one-versus -rest方法,只不过是把k个二值SVM优化问题放在一个最优化公式中同时优化,所以它也存在one-versus-rest方法相同的缺点。另外,这种思想尽管看起来简洁,但在最优化问题求解过程中的变量远远多于第1种,训练速度不及第1种,且在分类精度上也不占优[3]。当训练样本数非常大时,这一问题更加突出。因此,在对现有主要的SVM多类分类算法作简单介绍的基础上,提出了新的基于二叉树的SVM多类分类方法,该方法采用类间散布度量与类内散布度量的比值作为二叉树的生成算法,并通过一系列实验分析、比较了各种算法的特点。

1 多类SVM分类和基于二叉树的多类SVM

1.1 多类SVM分类方法简介

利用SVM解决多类分类问题,目前主要有两种途径:把多个2-类SVM分类器进行组合,研究的内容包括对组合方式的改进以及对每个2-类SVM分类器的改进;利用Weston等人提出的将2-类SVM从优化公式直接进行推广,研究的内容包括如何将2-类SVM的一些有效的改进措施引入到这种方法。目前,在解决多类问题时,一对多(one-versus-rest)和一对一(one-versus-one)[1]方法应用较为广泛。

(1) 一对多 (one-versus-rest,1-v-r)

对于k-类分类问题,构造k个2-类SVM分类器,每一类对应其中的一个,将它与其他的类分开;其中第i个2-类SVM分类器是把第i类中的样本都标记为+1,而其他所有的样本都标记为-1。也就是说,第i个2-类SVM分类器所构造的分类超平面(separating hyperplane),把第i类与其他的(i-1)类分割开。这种类型的多类SVM一般称为1-v-r(它是one-versus-rest的缩写形式)型SVM。分类时,将待识样本模式分别计算对应于各个2-类分类器的决策函数值,并选择最大的函数值所对应的类别为待识样本模式的所属类别。

(2) 一对一 (one-versus-one,1-v-1)

首先构造所有可能的2-类SVM分类器,每一个分类器的训练数据集都只取自相应的两类。这时共需要构造N=k(k-1)/2个2-类SVM分类器。在构造第i类与第j类之间的2-类SVM分类器时,训练集中的数据只来自相应的两类,并将第i类与第j类内的点分别标记为+1和-1。在分类时,将待识样本模式分别代入上述的N=k(k-1)/2个2-类分类器进行分类,累计各类别的得分,选择得分最高者所对应的类别为待识样本模式的所属类别。

1.2 基于二叉树的多类SVM

基于二叉树的多类SVM是先将所有类别分成两个子类,再将子类进一步划分成两个次级子类,如此循环下去,直到所有的节点都只包含一个单独的类别为止,此节点也是决策树中的叶子。该方法将原有的多类问题同样分解成了一系列的两类分类问题,其中两个子类间的分类函数采用SVM。二叉树方法可以避免传统方法的不可分情况,并且只需构造k-1个SVM分类器,分类时并不一定需要计算所有的分类器判别函数,从而可节省分类时间。

二叉树的结构对整个分类模型的分类精度有较大的影响。图1是一个4类问题的不同的二叉树法构造示意图。在图1(a)中,第1个分割面是由第1类和第2、第3、第4类构成,第2个分割面是由第2类和第3、第4类构成,最后一个分割面是由第3类和第4类构成;而图1(b)的分割顺序是第2类,第1类,第3类。从此例可看出,分割顺序不一样,每个类的分割区域也不同。因此,多类SVM方法的每个类的区域依赖于二叉树的结构,主要是二叉树节点所代表的二值SVM分类器的位置。

图1 四类问题的不同划分顺序

二叉树的结构有两种:一种是在每个内节点处,由一个类与剩下的类构造分割面;另一种是在内节点处,可以是多个类与多个类的分割。这里只考虑前一种情况,即每次分割只分割出一个类。基于二叉树的多类SVM,在测试阶段类似DAGSVM,从根节点开始计算决策函数,根据值的正负决定下一节点如此下去,直到到达某一叶节点为止,此叶节点所代表的类别就是测试样本的所属类别。

目前,基于二叉树的多类SVM分类方法已有学者提出,文献[4-7]的基本思想都是基于二叉树的分类。但这些方法不是随机地生成二叉树,就是采用二叉树生成算法并不能很好地提高整个分类模型的推广能力。从前面的分析可看出,越上层节点的分类性能对整个分类模型的推广性影响越大。因此在生成二叉树的过程中,应该让最易分割的类最早分割出来,即在二叉树的上层节点处分割。基于此,提出根据训练样本在属性空间的分布情况来生成二叉树的方法,从而建立一个推广性高的多类SVM分类模型。由于支持向量机的思想是在样本的属性空间中构造最优超平面,线性SVM的属性空间等价于输入空间,但非线性的SVM却无法得到具体的属性空间表达式。事实上,样本在输入空间中的物理联系在属性空间也同样存在。所以,只需在输入空间中考虑样本的分布情况。

2 改进的多分类二叉树法

节点的位置。为了提高分类模型的推广能力,必须利用合理的策略来生成二叉树结构。所以,提出以类样本分布情况作为二叉树的生成算法,从而构造推广能力好的基于二叉树的SVM多类分类模型。改进算法的基本思想就是在每次生成二叉树内节点时,选择最易分割的情况来构造当前节点的二值SVM。

分割顺序不一样,每个类的分割区域是不同的,先分割出来的类更容易有较大的分割区域。为了让分布好的类拥有较大的分割区域,就应把这些类最先分割出来。因为各类数据的真实分布无法得知,所以用有限样本数据的分布来对真实分布做近似估计。样本分布情况的度量采用了类间分布度量与类内分布度量的比值作为判别标准。图2(a)为3类样本数据的二维输入空间分布图,直观上看,最好的分割顺序为:先以第1类与其他类构造分割超平面,然后是第2与第3类构造分割超平面,这主要是考虑到各类样本在空间的分布情况。

图2 样本分布和分割示意图

定义1(类内散布度量) 设类S有n个d维样本向量x1,x2,…,xn,xi∈Rd,m为类S的样本均值向量,类内分布度量为:

Dw=1n∑ni=1xi-m(1)

式中,•表示欧式距离,其中m=1n∑ni=1xi。

二叉树多类分类法的每个类的区域依赖于二叉树的生成顺序,主要是二值SVM分类器所在的类。

定义2(类间散布度量) 设样本类别数为k,样本均值向量分别为m1,m2,…,mk,对于第i类样本类间分布度量为:

Db=1C-1∑k-1j=1mi-mj,且i≠j(2)

定义3(类散布度量) 设样本类别数为c,第i类样本的分布度量为:

Di=Dib/Diw(3)

式中:Dib和Diw分别表示第i类样本的类间散布度量和类内散布度量。

具体的算法流程为:

Step 1:根据式(3)计算各类样本数据的类散布度量Di(i=1,2,…,k);

Step 2:根据各类的散布度量由大到小的顺序,对类别进行排序。当存在两个或两个以上的类别具有相同类散布度量时,把类标号小的类排在前面。最后得到所有类别的排列n1,n2,…,nk;此处ni∈{1,2,…,k},i=1,2,…,k为类标号;

Step 3:利用二值分类的SVM训练算法构造二叉树各内节点的最优超平面。在根节点处,从样本集中选择第n1类样本为正样本集,其他样本为负样本集,利用SVM训练算法构造最优超平面,然后把属于第n1类的样本从样本集中删除。在第2个节点处从样本集中选择第n2类样本为正样本集,其他剩余的样本为负样本集,利用SVM训练算法构造最优超平面,然后把属于第n2类的样本从样本集中删除。依次下去,最终可得到基于二叉树的多类别SVM分类模型;

Step 4:算法结束。

3 实验比较

3.1 实验数据

为了比较多种SVM算法的性能,在UCI机器学习库[8]中选用了7个数据集,分别是zoo,iris,wine,waveform,Segment,Backup,Glassdata,选用的7个数据集中,既有多类别大样本数据集,又有多类别小样本数据集。表1列出了实验使用的每个数据集的实例个数、类个数、属性个数等数据信息。

表1 数据集的构成描述

数据集实例个数类个数属性个数

zoo101717

iris15035

wine178314

wave5 000322

Segment2 100719

GlassData214610

Backup3051836

3.2 实验结果与分析

实验中,惩罚参数C=100,核函数使用径向基核函数K(xi,xj)=exp(-xi-xj2/2γ2)。为了使实验更具有说服力,每个算法在实现过程中,核函数中的参数使用几个不同的值,采用5倍交叉验证法进行比较,表2列出了这3种方法的识别率和分类时间的比较,由实验结果可以看出,基于二叉树的多类分类算法与one-versus-one和one-versus-rest相比,识别率都有了提高。

表2中时间是5次实验的平均值,时间是以程序运行的CPU时间为准,单位为s。从表2可以看出,本文算法的时间与one-versus-one和one-versus-rest相比,都有了明显减少,因为二叉树测试样本时并不需要计算所有的二值分类器。one-versus-one方法的支持向量个数远远多于其他的算法,这是因为其每个子分类器都需利用到所有的训练样本,构造的分类面较其他算法复杂。one-versus-one和one-versus-rest的时间相对较长,是因为这两种方法必须计算所有的二值SVM分类器判别函数,且one-versus-one的总支持向量数较多,使得其时间更长。

表2 三种方法的实验结果

数据集参数

1-v-r1-v-1本文方法

识别率分类时间/s识别率分类时间/s识别率分类时间/s

zoo

0.195.130.0795.670.1497.290.05

0.594.590.0993.510.1593.510.06

1.083.240.0888.100.1686.480.05

iris

0.194.030.0594.380.0694.380.03

0.593.680.0693.680.0893.680.04

1.091.920.0691.920.0791.920.04

wine

0.142.610.1442.890.1355.360.07

0.542.610.1041.150.1254.780.06

1.041.150.1041.150.1252.840.06

wave

0.184.6047.7984.6088.3087.4641.65

0.540.2052.3038.9983.3856.2540.20

1.031.7946.8933.4482.8052.8438.65

Segment

0.133.3316.0939.4022.3040.269.37

0.535.9115.9020.1921.5130.829.27

1.035.3615.5016.6320.4031.939.35

Glassdata

0.163.610.2668.190.2871.560.13

0.560.960.2866.500.3567.950.15

1.057.100.2864.810.2966.750.15

Backup

0.183.190.9289.411.7489.390.61

0.573.441.2156.131.7177.900.73

1.053.611.3042.521.7553.940.72

4 结 语

这里首先分析了当前使用得较多的几种SVM多类分类算法的特点以及存在的一些问题。在此基础上,提出基于二叉树的SVM多分类算法。新的二叉树生成算法可以使得分布好的类别在属性空间中获得更大的划分区域,从而提高多分类模型的推广性能。最后,通过几个实验,对这些算法进行了比较,实验结果表明本文算法可以明显的减少分类时间,且分类精度也较理想。 基于本文的方法还有许多需要研究的问题,选取更好的生成二叉树方法,这将是下一步研究的方向。

参考文献

[1]方景龙,陈铄,潘志庚,等.复杂分类问题支持向量机的简化[J].电子学报,2007(11):78-82.

[2]徐晓燕,王昱,张斌.一种集成logistic回归与支持向量机的判别分析规则[J].系统工程理论与实践,2007(5):126-131.

[3]Hsu C,Lin C.A Comparison of Methods for Multiclass Support Vector Machines[J].IEEE Trans.on Neural Networks,2002,13(2):415-425.

[4]Takahashi F,Abe S.Decision-Tree-Based Multiclas Support Vector Machines[A].Proc of the 9th Int.Conf.on Neural Information Processing[C].Singapore,2002(3):1 418-1 422.

[5]Sungmoon C,Sang H O,Soo-Young L.Support Vector Machines with Binary Tree Architecture for Multi-class Classification[J].Neural Information Processing-Letters and Reviews,2004,2(3):47-51.

[6]颜根廷,李传江,马广富.支持向量分类器的模糊积分集成方法[J].哈尔滨工业大学学报,2008,40(7):1 017-1 020.

[7]张永,迟忠先,米滢.一类直接构造的模糊多类支持向量分类器[J].计算机工程与应用,2008,44(8):12-15.

[8]UCI Repository ofMachine Learning Databases and Domain Theories[EB/OL].ftp:// ftp.ics.uci.edu/pub/machine-learning-databases.