基于支持向量机的多类分类算法综述

宋召青，陈 垚

（海军航空工程学院a.七系；b.研究生管理大队，山东烟台264001）

基于支持向量机的多类分类算法综述

宋召青a，陈 垚b

（海军航空工程学院a.七系；b.研究生管理大队，山东烟台264001）

作为一种新兴的机器学习方法，基于统计学习理论的支持向量机，最初是用来解决二类分类问题的。对于实际中主要遇到的多类分类问题，目前常用的两大类改进推广方法为“分解—重组”法和“直接求解”法。文章对二类方法进行了介绍和分析，指出其优缺点和未来的改进方向。

支持向量机；多类分类；算法

基于统计学习理论的支持向量机（Support Vector Machine，SVM）自1995年由Vapnik[1]提出以来，由于其对于解决小样本、高维数、非线性等问题有很好的效果，受到了广泛的关注，成为继神经网络之后机器学习领域新的研究热点，并取得了快速的发展。

1 支持向量机

SVM设计之初是用于解决二类分类问题，目标是寻找一个最优超平面，使得其能将二类样本分开，并且与二类样本的距离即分类间隔最大。

考虑如下训练样本集：

对于线性可分问题，分类超平面的求解可以转换为对如下的二次规划（Quadratic Programming，QP）问题的求解[2]：

式中：ω为行向量，是超平面的法向量；b为分类阈值；C为惩罚因子；ξi为松弛变量。

这个二次规划问题可用拉格朗日乘子法求解[3]，最终得到分类函数表达式：

对于线性不可分问题，引入了核函数[4]K(·,·)的概念，将样本从低维空间映射到高维空间，将线性不可分转化为高维空间的线性可分问题，而样本在转化前后的内积保持不变。分类函数表达式变为

核函数有很多种，其中最为常用的是高斯径向基（RBF）核函数：K(α,β)=exp(-‖α-β‖2/2σ2)。

2 多类分类支持向量机

在实际应用中大部分的分类问题都是多类分类问题，用标准的SVM无法直接解决，目前学者采用的方法主要分为两大类。

2.1 “分解—重组”法

第一类是“分解—重组”法，这类方法的主要思想是将多类分类问题拆分成为一系列的二类分类问题，再以一定的决策规则将这些二类分类器重新组合在一起得到分类结果。这类方法常用的包括：“一对多（One-Against-Rest，OAR）法[5]”、“一对一（One-Against-One，OAO）法[6]”、“有向无环图（Directed Acyclic Graph，DAG）法[7]”、“二叉树（Binary Tree）法[8]”、“纠错编码法[9]”、“模糊SVM法[10]”等等。这类方法的应用比较广泛，下面简要介绍几种方法。

OAR法的基本思想是对一个N类分类问题，训练出N个二类分类器，每个分类器用于将某一类与其他所有类区分开，得到N个分类函数。在测试未知样本时，将其代入每个分类函数，得到函数值最大的那类即判定为未知样本的类别。该算法只需训练N个二类分类SVM，速度较快。缺点是：每个分类器的训练都需要所有样本参与，当样本规模较大时训练速度会下降；在每个分类器的训练过程中，正类样本数和负类样本数一般会存在很大的差距，会导致分类超平面的偏斜，从而降低了分类准确度；存在样本不可分的情况，即测试样本被每个分类函数都判为负类。

OAO法的基本思想是在N个类别中的每二类之间均训练一个二类分类器，得到(N-1)N/2个分类器和分类函数。在测试未知样本时，将其分别代入每个分类函数，对各函数判别结果采用投票的方式记录，得票最多的类别判定为未知样本的类别。这种方法的优点是每个二类分类器只需训练二类样本，简单快速。但需要训练的分类器数量较多，特别是N较大时；当不止一类得票最多时，会出现样本的误分类。

DAG法可以看作OAO法的推广，在训练分类器的阶段与OAO法相同，训练(N-1)N/2个分类器。在测试阶段，DAG法则是构造一个有向无环图（图1为N=4时的示意图）。DAG包含(N-1)N/2个节点和N个叶节点，每个节点对应一个二类分类器，每个叶节点对应一个类别。测试未知样本时，样本从根节点的判别函数开始分类判断，根据判断结果来决定下一层的移动方向，直到移动到某个叶子为止，该叶子所对应的类别即为未知样本的类别。DAG法的优点是避免了OAO法中可能存在的样本不可分情况，同时每次测试只需要计算N-1个判别函数，加快了计算速度，减少了测试时间。存在的问题除了和OAO法一样训练过程较长外，一旦某个节点出现了误分类，将无法得到正确的结果，因此在构造DAG时靠上层的节点应选择不易出现误分类的二类分类器。

图1 四类分类问题的DAG示意图Fig.1 ADAG schematic diagram of 4-class classification problem

二叉树法的基本思想是，将包含所有类别的集合划分为2个互斥子集，再将每个子集划分为2个互斥次级子集，以此类推，直到每个集合只包含一个类别为止。将所有集合作为节点，构成倒置的树状结构（图2为N=4时的示意图）。每个节点对应一个二类分类SVM，用于区分其2个子类，这样共需要训练N-1个分类器。测试样本的过程与DAG法相同，都是从上层节点向下单方向进行。这种方法的优点是需要训练的二类分类器少，训练和测试的速度都较快，不存在不可分的样本。缺点是各子节点的划分方法对结果有较大影响，而且同DAG法一样，在某个节点出现误分类后，将无法纠正到正确的结果。

图2 四类分类问题的一种二叉树模型示意图Fig.2 Abinary tree schematic diagram of 4-class classification problem

这类方法将多类分类问题分解后，每次训练的都是标准的二类分类支持向量机，训练过程简单。但也存在一些问题：一是遇到包含类别数较多的问题时，需构造的支持向量机数呈线性甚至几何倍数增长，训练和验证样本的时间都大大增加；二是在构造分类器时大都只是使用了一部分样本，没有考虑到所有样本包含的信息，会对分类的结果造成一定的影响。

2.2 “直接求解”法

第二类是“直接求解”法，这类方法的基本思想是将多类分类问题作为一个整体求解，只要构造一个分类器就可以解决多类分类问题。其优点是构造的分类器数量少，同时构造过程中利用到了所有样本的信息。存在的缺点是没有较统一的构造方法，而且一般训练过程比较慢，分类器结构复杂。相比之下，研究“直接求解”法的学者较少，取得的成果也不多，所以这类方法有很大的研究空间。

3 多类分类支持向量机算法应用

3.1 “分解—重组”法应用

“分解—重组”这类方法由于将多类分类问题拆分成了容易解决的二类分类问题，运算复杂度降低，故受到许多学者的关注和研究，并且在实际中有广泛的应用。

Shiladitya Chowdhury等[11]提出一种加权多类分类支持向量机（Weighted Multi-Class SVM，WMCSVM），并将其应用到人脸识别中。这种方法以“一对多”法为基础，考虑到不同的训练样本对训练最优分类超平面的贡献程度不同，为每个样本引入了不同的权重，并由概率方法进行计算。重要的样本被赋予较大的权重，噪声等无关样本被赋予较小的权重，这样训练出的SVM具有更高的分类精度。WMSCVM在人脸识别问题中取得了很好的效果，比改进前的MCSVM有更高的准确率。

Henry Joutsijoki[12]将“一半对一半”多类分类支持向量机（Half-Against-Half Multi-Class SVM，HAHMCSVM）应用到了大型底栖无脊椎动物图像的自动辨识分类中，这种方法结合了OAR和DAG这2种基本方法，取长补短。作者在文中对2种划分节点的方法——散射法和随机法进行对比，通过大量的实验，得出的结论是2种划分方法均有很高的分类精度，散射法相比之下更优。

Maya Kallas等[13]将核主成分分析法（Kernel Principal Component Analysis，KPCA）与OAR法相结合，提出了一种新的多类分类方法。KPCA法用于特征提取，是主成分分析法（PCA）的改进方法，PCA只能用于线性问题，KPCA通过引入核的概念，将其推广到了非线性问题中。作者将结合后的多类分类方法应用到心电图信号的分类识别中，取得了很好的效果，比普通的OAR和OAO法分类精度更高。

单玉刚等[14]针对OAO法中存在不可分区域的问题，将基于紧密度判决与OAO法相结合，提出了一种新的多类分类方法。这种方法依据样本到类中心之间的距离和基于kNN（k Nearest Neighbor）的样本分布情况结合的方式构建判别函数，以此来确定不可分样本的类别归属。作者使用了UCI（University of California Irvine）数据集对新算法进行测试，测试结果表明，该算法能有效地解决不可分区域问题，而且分类准确率比传统方法更高。

秦玉平等[15]基于二叉树SVM提出了一种改进的快速MCSVM算法。这种算法以每类样本的数量作为权重，按照Huffman树的构造过程自下向上地构造二叉树，提高了二叉树的生成速度，从而提高的算法的效率。作者采用Reuters 21578标准数据集验证改进的算法，实验结果证明了该算法的有效性。

肖荣等[16]提出一种改进的OAO算法，先通过粗分类快速选出候选类别，再对候选类别按原OAO法进行投票，相当于减少了类别的数量，提高了计算速度，对类别较多的问题效果更好。实验结果显示该方法提高了分类效率，且分类准确率有一定程度的提高。

除此之外还有很多研究成果，如文献[17-27]等。这类方法存在一个共同的问题是在构造分类器时都没有考虑到所有样本所包含的信息。

3.2 “直接求解”法应用

Weston J等[28]提出一种思想上基于OAR方法的直接求解方法。该方法需构造N个二类分类SVM，不同的是通过一个优化问题将N个SVM的参数一次性求解，再通过判别函数对样本进行检测。这种方法减少了优化问题的数量，但大大增加了问题求解的难度，尤其当训练样本较多时，求解速度很难满足要求。

Minkook Cho和Hyeyoung Park[29]针对多类分类问题中训练样本少时存在的泛化能力差的问题提出一种新方法，这种方法训练一个支持向量机来计算样本之间的相似度量，然后与kNN法相结合来判断样本所属类别。实验结果表明新方法比传统多类分类方法有更高的分类准确率和更好的泛化能力。

除此之外如文献[30]等也对“直接求解”这类方法进行过研究。

4 总结和展望

综述了基于支持向量机的多类分类算法，对已有的主要方法进行介绍和分析，讨论了这些方法的优缺点，并列举了国内外的研究应用现状。总结发现，学者主要研究方向都是将多类分类问题转化为二类分类问题进行求解，对直接求解法鲜有关注且没有快速有效的方法提出。

对多类分类支持向量机，研究重点主要包括：

1）对于“分解—重组”法，应将重点放在求解样本规模大、种类多的问题上。样本数量大时应当对非支持向量进行删减，缩小样本规模。可以采用的方法如计算每个样本距离样本中心的几何距离，剔除距离中心最近的样本；或是保留不同类别之间距离最近的若干样本来训练分类超平面；与模糊集合方法相结合，根据隶属度进行筛选等。而样本种类多时首先应尽量不使用OAO法等分类器数受样本类别影响较大的方法，相比之下“二叉树法”需要训练的分类器较少，同时测试样本时也无须用到每个分类器。须要解决的主要是误差累积的问题，在每个节点的划分都应当尽量使得2个子节点中的样本集更易区分。可以采用最大化样本类间几何距离的方法划分各类别，等等。对于OAR、OAO等方法中存在的不可分问题，主要采用几何距离、隶属度等对不可分样本进行归类。

2）对于“直接求解”法，由于研究成果较少，因而仍有很大空间。目的是设计少量的甚至只用一个分类器，就可以对多类样本进行分类，而所设计的分类器在保证分类准确率的前提下应当结构简单易于训练，才能体现其应用价值。设计思路一方面可以考虑将SVM与其他算法相结合；另一方面可以考虑改变思路，对多类分类问题进行变型，利用更简便的算法求解变型后的问题。以这种思想为指导，笔者研究了一种基于支持向量回归机的多类分类算法，这种算法将回归的思想用到了分类问题中，把分类样本直接用支持向量回归机进行回归（其中样本的类标作为回归样本的输出值），得到的回归函数拟合了样本输入和其类标的映射关系，即得到了多类分类问题的分类器。对未知样本进行分类时，由于回归函数的输出是实数，故需要对结果进行取整运算，得到即为被测样本的类别标示。将多类分类问题转化为回归问题进行求解是一次完成的，算法实现简单，运行速度快。而且由于采取了取整运算，加强了算法的鲁棒性，在输入样本有一定噪声的情况下，也可获得正确的分类。这种方法可以作为多类分类算法研究的一种新思路，还需进一步的研究。

3）对基本的支持向量机方法进行改进。如近些年出现的双生支持向量机（Twin SVM），不再求解二类样本的最优分类超平面，而是寻找2个超平面分别穿过二类样本，使得二类样本分别与穿过的平面距离最近，从而减少了优化问题的运算时间。利用TSVM代替传统的SVM来求解多类分类问题可以有效的缩短训练时间。而代替后是否会出现新的问题，应当如何解决等都可以作为研究的方向。

[1]VAPNIK V.The nature of statistical learning theory[M]. New York：Springer-Verlag，1995：25-27.

[2]CORTES C，VAPNIK V.Support-vector networks[J].Machine Learning，1995，20（3）：273-297.

[3]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.

[4]AIZERMAN M，BRAVERMAN E M，ROZONOER L. Theoretical foundations of the potential function method in pattern recognition[J].Automation and Remote Control，1964，25（6）：917-936.

[5]KREBEL U H G.Pairwise classification and support vector machines[M].Cambridge，MA：MIT Press，1999：255-268.

[6]BENNETT KRISTIN P.Combining support vector and mathematical programming methods for classification [M].Cambridge，MA：MIT Press，1999：307-326.

[7]PLATT J C，CRISTIANINI N，SHAWE TAYLOR J. Large margin DAGs for multiclass classification[C]//Advances in Neural Information Processing Systems.Cambridge，MA：MIT Press，2000：547-553.

[8]CHEONG S，OH S H，LEE S Y.Support vector machines with binary tree architecture for multi-class classification [J].Neural Information Processing Letters and Reviews，2004，2（3）：47-51.

[9]GHANI R.Using error-correcting codes for text classification[C]//The 17th International Conference on Machine Learning.Sydney：Morgan Kaufmann Publishers，2002：303-310.

[10]SHIGEO ABE，TAKUYA INOUE.Fuzzy support vector machines for multiclass problems[C]//European Symposium on Artificial Neural Networks.Bruges：IEEE，2002：113-118.

[11]CHOWDHURY S，SING J K，BASU D K，et al.Weighted multi-class support vector machine for robust face recognition[C]//International Conference on Communications，Devices and Intelligent Systems.Piscataway，N.J.：IEEE，2012：326-329.

[12]HENRY J.Half-against-half multi-class support vector machines in classification of benthic macroinvertebrate images[C]//International Conference on Computer&Information Science.Piscataway，N.J.：IEEE，2012：414-419.

[13]KALLAS M，FRANCIS C，KANAAN L，et al.Multiclass SVM classification combined with kernel PCA feature extraction of ECG signals[C]//The 19thInternational Conference on Telecommunications.Tahiti，Papeete：IEEE，2012：1-5.

[14]单玉刚，王宏，董爽.改进的一对一支持向量机多分类算法[J].计算机工程与设计，2012，33（5）：1837-1840. SHAN YUGANG，WANG HONG，DONG SHUANG.Improved multi-classifictaion algroithm of one-against-one SVM[J].Computer Engineering and Design，2012，33（5）：1837-1840.（in Chinese）

[15]秦玉平，罗倩，王秀坤.一种快速的支持向量机多类分类算法[J].计算机科学，2010，37（7）：240-242. QIN YUPING，LUO QIAN，WANG XIUKUN.Fast multiclass classification algorithm of support vector machines [J].Computer Science，2010，37（7）：240-242.（in Chinese）

[16]肖荣，李金凤，覃俊.一种改进的一对一多类支持向量机[J].软件导刊，2010，9（10）：109-111. XIAO RONG，LI JINFENG，QIN JUN.An improved oneagainst-one multiclass SVM[J].Software Guide，2010，9（10）：109-111.（in Chinese）

[17]JI YOU，SUN，SHILIANG，LU，YUE.Multitask multiclass privileged information support vector machines[C]// 21stInternational Conference on Pattern Recognition.Piscataway，N.J.：IEEE，2012：2323-2326.

[18]JU XUCHAN，TIAN YINGJIE，LIU DALIAN，et al. Nonparallel hyperplanes support vector machine for multi-class classification[J].Procedia Computer Science，2015，51：1574-1582.

[19]LAJNEF T，CHAIBI S，RUBY P，et al.Learning machines and sleeping brains：automatic sleep stage classification using decision-tree multi-class support vector machines[J].Journal of Neuroscience Methods，2015，250：1-12.

[20]LI LEI，GAO ZHIPING，DING WENYAN.Fuzzy multiclass support vector machine based on binary tree in network intrusion detection[C]//International Conference on Electrical and Control Engineering.Piscataway，N.J.：IEEE，2010：1043-1046.

[21]LIU SHUANG，CHEN PENG，LI KEQIU.Multiple subhyper-spheres support vector machine for multi-class classification[J].International Journal of Wavelets Multiresolution&Information Processing，2014，12（3）：75-85.

[22]NASIRI J A，MOGHADAM CHARKARI N，JALILI S. Least squares twin multi-class classification support vector machine[J].Pattern Recognition，2015，48（3）：984-992.

[23]POOYAN N，SHAHBAZIAN M，SALAHSHOOR K，et al.Simultaneous fault diagnosis using multi class support vector machine in a dew point process[J].Journal of Natural Gas Science&Engineering，2015，23：373-379.

[24]SONGSIRI P，PHETKAEW T，KIJSIRIKUL B.Enhancement of multi-class support vector machine construction from binary learners using generalization performance[J]. Neurocomputing，2015，151：434-448.

[25]TOMAR D，AGARWAL S.A comparison on multi-class classification methods based on least squares twin support vector machine[J].Knowledge Based Systems，2015，81：131-147.

[26]YANG X Y，LIU J，ZHANG M Q，et al.A new multiclass SVM algorithm based on one-class SVM[C]//Proceedings of the 7thinternational conference on Computational Science.Berlin：Springer，2007：677-684.

[27]赵亮.一种改进的基于支持向量机的多类分类方法[J].计算机应用与软件，2014，31（12）：233-236. ZHAO LIANG.An improved SVM-based multi-class classification algorithm[J].Computer Applications and Software，2014，31（12）：233-236.（in Chinese）

[28]WESTON J，WATKINS C.Support vector machines for multi-class pattern recognition[C]//The European Symposium onArtificial Neural Networks.Bruges，Belgium：ESANN，1999：219-224.

[29]CHO M，PARK H.A robust SVM design for multi-class classification[C]//Advances in Artificial Intelligence.Berlin：Springer，2005：1335-1338.

[30]ARENAS GARCIA J，PEREZ CRUZ F.Multi-class support vector machines：a new approach[C]//International Conference on Acoustics，Speech，and Signal Processing. Piscataway，N.J.：IEEE，2003：6-10.

An Overview of Multi-Class Algorithm Based on Support Vector Machine

SONG Zhaoqinga,CHEN Yaob
（Naval Aeronautical and Astronautical University a.No.7 Department; b.Graduate Students’Brigade,Yantai Shandong 264001,China）

As a new machine learning method,the support vector machine which is based on statistical learning theory,is used to solve binary classification problem originally.However,most of the classification problems in practice contain more than two classes,and there were two major types of methods to extend the binary SVM to multi-class SVM which are‘Decomposition-Reorganization’method and‘Direct solving’method.In this paper,the two methods were introduced and analyzed and the advantages,disadvantages and the improvement direction in the future are pointed out.

support vector machine;multi-class classification;algorithm

TP391.41

A

1673-1522（2015）05-0442-05

10.7682/j.issn.1673-1522.2015.05.009

2015-06-11；

2015-07-26

国家自然科学基金资助项目（61433011）；山东省优秀中青年科学家科研奖励基金资助项目（BS2012DX007）；上海博士后科研资助计划资助项目（12R21414300）

宋召青（1969-），男，教授，博士。