支持向量机多分类问题研究*

肖 晓,张 敏

(1.中国矿业大学 信息与电气工程学院,江苏 徐州 221008； 2.淮海工学院 电子工程学院,江苏 连云港 222005)

0 引言

支持向量机(sutopport vector machine,SVM)是Vapnik等人提出的一种针对小样本训练和分类的机器学习理论[1]。它是以VC维理论和结构风险最小化原则为基础的机器学习,在解决高维模式识别、小样本和非线性问题中表现出许多独特的优势,在一定程度上克服了“过学习”和“维数灾难”等传统问题,并且以统计学习理论(SLT)为基础,明确数学模型,因此具有很好的发展前景。

支持向量机最初是针对2类分类问题提出的,不能将其直接应用于多类分类问题。但实际应用中经常需要对多类问题进行分类,如何将支持向量机推广到多类分类问题中并保持其优良的性能,已成为学者们研究的热点[2]。针对支持向量机多类分类算法众多学者提出了不同的有效分类方法[3-5],但不同的方法对大规模分类的适用性尚不明确。基于此,笔者从目前常用的多类分类方法的基本原理及其特点来对比分析其在大规模分类中的适用性,并通过实验仿真分析来加以验证。

1 SVM多类分类方法

多类SVM实现方式可以分为2种[6]。第1种方法是一次性求解多类问题,其是在原有2类SVM基础上,构造多值分类模型,对新模型的目标函数进行最优化，它其实是2类分类问题中二次优化问题的推广。由于这种目标函数过于复杂,效率不高,一般不被采用。第2种方法是通过组合多个二值SVM分类器,实现多类别分类。

1.1 一对多SVM

该算法是最早用于解决多类分类的方法,其基本思想是,解决n类问题需要训练n个支持向量机的2类分类器,构成n个SVM模型。将第i类样本数据看作正样本,不属于第i类的看成负样本。在进行决策类别时,比较函数值中最大者所对应的类别即为数据的类别[7]。第i类SVM就是解决如下问题。

(1)

(2)

这里,φ是将xi映射到高维特征空间的映射函数,C是惩罚系数。

(ωii)Tφ(x)+bi,i=1,2,…,n,

则x属于哪一类就意味着它可以使判别函数最大。

一对多分类方法的优点在于,对于n类问题只需求解n个二次规划问题,所以其分类速度较快。但这种方法每个子分类器的构造都需要所有样本参与训练,当样本规模较大时,会导致训练效率降低。同时,因训练时总是一类样本与剩余的多类别构造分类超平面,这样可能会存在正负类在训练样本数目上极不平衡,进而影响分类器的预测精度。

1.2 一对一SVM

一对一方法的优点在于每个支持向量机子分类器只需训练两类样本,降低了构造每个两类分类器的复杂度,所以其训练速度较一对多快。同时,参加训练的两类样本数量能够达到基本平衡,降低了不平衡性对精度的影响。

1.3 有向无环图支持向量机

该分类方法的优点是在进行判别时,无需遍历所有的二类分类支持向量机。对于n类别问题,只需经过n-1个决策函数就可以得出结果,有效地提高了分类速度,而且,不存在不可分区域。其缺点有两类:一类是存在自上而下的“误差累积”现象,这是DAGSVM的弊端。假如在某个节点上发生分类错误,则会把分类错误延续到该节点的后续节点上,累积误差随着类别数目的增加而增加。而且分类错误在越靠近根节点的地方发生,误差累积效应越明显,将严重影响分类的性能。另一类缺点是该方法最后输出结果对节点的排序依赖性很大,节点的排序不同将会导致不同分类结果,从而降低分类精度。

除上述几种常见方法外,还有二叉树的多类分类方法[11]，一次性求解方法[12]，纠错编码SVM[13-14]，M-ary分类方法[15]，多级支持向量机方法[16]以及其他求解多类别的方法等[11]。这些方法各有优缺点,针对不同问题,采用不同的分类方法。

2 实验仿真分析

2.1 实验环境及数据

表1 实验数据统计

由于所使用的iris数据没有测试集,笔者任意选择100组样本数据进行训练,剩余50组样本作为测试集,共测试10次取其均值。实验所用数据都归一化到[-1,1],这样做可以减少取值范围大的属性特征值对取值范围小的属性特征值产生的影响,以提高训练精度和测试精度。剩下两组数据划分为训练集和测试集两部分,实验时采用5折交叉验证进行测试,这样既保证提供足够的数据用于模型学习,又能够验证模型的效果。

2.2 实验结果与分析

实验分析表明,一对一方法、有向无环图方法在测试精度上相差不大,但一对多方法精度较差;除此之外,参数的选择也是比较关键的,试验中用了交叉验证的方法来选择最优的参数(C,g)(见表2)。

表2 多类分类方法实验结果对比

以上得到结果是多次试验得到的最好结果,是否有比这更好的参数还有待进一步的研究。还可以看出当样本数目较大时,有向无环图的分类准确率最高,一对一多类分类方法次之,一对多的分类准确率稍差些,这可能是正负类样本在训练数目上的不平衡影响到预测精度。因此,为了获得较高的分类准确率，应该优先选择有向无环图多类分类方法。

对表3中数据分析表明，有向无环图的决策时间相对来说较快些,因为决策有向无环图无需遍历所有的分类器,对于一般规模的数据样本具有理想的训练和分类效率。一对多方法也较好,两种多类分类方法的训练时间相差不大。此外, 一对一方法在训练和测试时所耗费的时间都较其他两类高,其原因可能在于在训练和测试两个阶段都需要经历较多的子分类器。

表3 多类分类时间对比

3 结束语

笔者通过对比分析支持向量机常用多类分类算法 (一对多方法、一对一方法和有向无环图多分类方法)的优缺点,认为对小样本数据进行识别时,3种方法的训练时间与测试时间相差无几,但随着样本数量的增多,常用的一对多方法、一对一方法训练速度与分类速度都将大大降低,而有向无环图简单易行,具有理想的训练速度,分类速度略慢,但都快于一对一和一对多方法。因此有向无环图对于一般大规模的多类分类问题是一种有效的分类方法,可以为大规模样本的识别提供参考,具有一定的实用价值。

参考文献:

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

[2] 丁然.支持向量机多分类算法研究[D].哈尔滨:哈尔滨理工大学，2012.

[3] 刘太安,梁永全,薛欣.一种新的模糊支持向量机多分类算法[J].计算机应用研究,2008,25(7):2041-2042.

[4] 徐启华,杨瑞.一种新的软间隔支持向量机分类算法[J].计算机工程与设计,2005,26(9):2316-2318.

[5] 单玉刚,王宏,董爽.改进的一对一支持向量机多分类算法[J].计算机工程与设计,2012,33(5):1837-1842.

[6] 刘志刚,李德仁,秦前清,等.支持向量机在多类分类问题中的推广[J].计算机工程与应用，2004，40(7):10-14.

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

[8] 白鹏,张喜斌,张斌,等.支持向量机理论及工程应用实例[M].西安:西安电子科技大学出版社，2008：48-49.

[9] SEBALD D J, BUCHLEW J A. Support vector machine and the multiple hypothesis test problem[J]. IEEE Transactions on Signal Processing, 2001, 49(11): 2865-2872.

[10] PLATT J C, CRISTIANINI N, SHAWE T J. Large margin DAGs for multiclass classification[J]. Advances in Neural Information Processing Systems, 2000,12(3): 547-553.

[11] 黄琼英.支持向量机多类分类算法研究及应用[D].天津:河北工业大学,2005.

[12] 余辉,赵晖.支持向量机多类分类算法新研究[J].计算机工程与应用,2008,44(7):185-194.

[13] 孔波,郑喜英.支持向量机多类分类方法研究[J].河南教育学院学报:自然科学版,2010,19(2):9-13.

[14] 赵春晖,陈万海,郭春燕,等.多类支持向量机方法的研究现状与分析[J].智能系统学报,2007,2(2):11-18.

[15] 包建,刘然.用纠错编码改进的M-ary支持向量机多类分类算法[J].计算机应用,2012,32(3):661-664.

[16] 邢红杰.多级支持向量机[D].保定:河北大学,2003.