第2卷第2期 智能系统学报 Vol.2№2 2007年4月 CAAI Transactions on Intelligent Systems Apr.2007 多类支持向量机方法的研究现状与分析 赵春晖，陈万海，郭春燕 (哈尔滨工程大学信息与通信工程学院，黑龙江哈尔滨150001) 摘要：支持向量机(SVM)是建立在统计学理论基础上的一种小样本机器学习方法，最初应用于解决两类分类问 题.然而在解决实际问题中遇到的多为多分类问题，如何有效的将其推广到多类分类问题是一个正在研究的问题。 该文对现有的多类支持向量机方法从组合多个两类分类器层次结构、一次性优化问题和纠错编码等4个角度进行 了综合归纳和分析，详细介绍了每种方法的代表性算法，并比较其优劣。 关键词：多类支持向量机；两类分类器；层次结构；一次性优化；纠错编码 中图分类号：TP391文献标识码：A文章编号：1673-4785(2007)02-0011-07 Research and analysis of methods for multiclass support vector machines ZHAO Chumhui,CHEN Wamhai,GUO Chumyan (College of Information and Communication Engineering,Harbin Engineering University,Harbin 150001,China) Abstract:The SVM is a limited sample learning method which was developed from statistical theory,and o- riginally designed for binary classification.However,many practical problems are multi-classification ones.How to effectively extend binary classification to multi-classification is an ongoing research issue. This paper generalizes and analyzes multiclass support vector machines from four angles:combination of several binary classifiers,hierarchical structures,one-off optimization and error correcting codes.Several representative algorithms for various methods are introduced in detail and their advantages and disadvanta- ges are compared. Key words:multiclass support vector machine;binary classifier;hierarchical structure;one-off optimiza- tion;error correcting code 1992~1995年，Vapnik在统计学习理论的基 上的线性可分问题，然后在这个新空间中求取最优 础上发展出了一种新的模式识别方法支持向量机 分类面」 (support vector machine,SVM)I,它采用结构风 最初支持向量机是用于解决2类分类问题，不 险最小化原则代替了传统机器学习方法中的经验风 能直接用于多类分类.而实际应用中遇到的多为多 险最小化原则，在解决小样本、非线性及高维模式识 分类问题，如何有效地将其推广到多类分类问题仍 别问题中表现出许多特有的优势.支持向量机的基 是当前支持向量机研究的重要内容之一，文中把支 本思想可概括为：寻找一个最优分类超平面，使得训 持向量机应用到多类分类问题中的算法统称为多类 练样本中的2类样本点能被无错误的分开，并且要 支持向量机.目前人们对多类支持向量机的研究虽 使2类的分类间隔最大；而对线性不可分问题，通过 还有待于完善，但也取得了一定的成就.至今已经有 核函数将低维输入空间的数据映射到高维空间，从 几种卓有成效的方法将SVM推广到多类分类问 而将原低维空间的线性不可分问题转化为高维空间 题2).下面根据多类支持向量机的不同实现方法 把它分成4大类来详细介绍，并比较其优劣，以便读 收稿日期：200611-14。 基金项目：国家自然科学基金资助项目(60672034)：高校博士点基金 者在今后的研究中尽量避免这些方法所存在的各种 资助项目(20060217021)，黑龙江省自然科学基金资助项 弊端，发展出更多有效的多类支持向量机算法 目（刀G20606-01). 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 2 卷第 2 期 智 能 系 统 学 报 Vol. 2 №. 2 2007 年 4 月 CAA I Transactions on Intelligent Systems Apr. 2007 多类支持向量机方法的研究现状与分析 赵春晖 ,陈万海 ,郭春燕 (哈尔滨工程大学 信息与通信工程学院 ,黑龙江 哈尔滨 150001) 摘 要 :支持向量机(SVM)是建立在统计学理论基础上的一种小样本机器学习方法 ,最初应用于解决两类分类问 题. 然而在解决实际问题中遇到的多为多分类问题 ,如何有效的将其推广到多类分类问题是一个正在研究的问题. 该文对现有的多类支持向量机方法从组合多个两类分类器、层次结构、一次性优化问题和纠错编码等 4 个角度进行 了综合归纳和分析 ,详细介绍了每种方法的代表性算法 ,并比较其优劣. 关键词 :多类支持向量机 ;两类分类器 ;层次结构 ;一次性优化 ;纠错编码 中图分类号 : TP391 文献标识码 :A 文章编号 :167324785 (2007) 0220011207 Research and analysis of methods for multiclass support vector machines ZHAO Chun2hui , CH EN Wan2hai , GUO Chun2yan (College of Information and Communication Engineering , Harbin Engineering University , Harbin 150001 , China) Abstract :The SVM is a limited sample learning met hod which was developed from statistical t heory , and o2 riginally designed for binary classification. However , many practical problems are multi2classification ones. How to effectively extend binary classification to multi2classification is an ongoing research issue. This paper generalizes and analyzes multiclass support vector machines from four angles: combination of several binary classifiers , hierarchical struct ures , one - off optimization and error correcting codes. Several representative algorithms for various met hods are introduced in detail and t heir advantages and disadvanta2 ges are compared. Keywords :multiclass support vector machine ; binary classifier ; hierarchical struct ure ; one2off optimiza2 tion ; error correcting code 收稿日期 :2006211214. 基金项目 :国家自然科学基金资助项目(60672034) ;高校博士点基金 资助项目(20060217021) ;黑龙江省自然科学基金资助项 目(ZJ G20606 - 01) . 1992～1995 年 ,Vap nik 在统计学习理论的基 础上发展出了一种新的模式识别方法 —支持向量机 (support vector machine ,SVM) [1 ] ,它采用结构风 险最小化原则代替了传统机器学习方法中的经验风 险最小化原则 ,在解决小样本、非线性及高维模式识 别问题中表现出许多特有的优势. 支持向量机的基 本思想可概括为 :寻找一个最优分类超平面 ,使得训 练样本中的 2 类样本点能被无错误的分开 ,并且要 使 2 类的分类间隔最大 ;而对线性不可分问题 ,通过 核函数将低维输入空间的数据映射到高维空间 ,从 而将原低维空间的线性不可分问题转化为高维空间 上的线性可分问题 ,然后在这个新空间中求取最优 分类面. 最初支持向量机是用于解决 2 类分类问题 ,不 能直接用于多类分类. 而实际应用中遇到的多为多 分类问题 ,如何有效地将其推广到多类分类问题仍 是当前支持向量机研究的重要内容之一 ,文中把支 持向量机应用到多类分类问题中的算法统称为多类 支持向量机. 目前人们对多类支持向量机的研究虽 还有待于完善 ,但也取得了一定的成就. 至今已经有 几种卓有成效的方法将 SVM 推广到多类分类问 题[2 - 5 ] . 下面根据多类支持向量机的不同实现方法 把它分成 4 大类来详细介绍 ,并比较其优劣 ,以便读 者在今后的研究中尽量避免这些方法所存在的各种 弊端 ,发展出更多有效的多类支持向量机算法
·12 智能系统学报 第2卷 对未知样本x进行分类时，判断符号函数 1用多个两类分类器实现多类分类 f(x)=sign((w)x+), 4) 1.1 1-ar SVM 若x属于第i类则第i类的票数加1，反之第j类加 l-ar SVM(one-against-rest)lo算法是用支 1.x属于最后票数最多的那一类 持向量机解决多类分类问题的最早的方法，对于k 由于每个SVM只考虑2类样本，故单个SVM (k2)类SVM分类问题，构造k个两类分类器，自 容易训练；另外，虽然它的复杂度以类数按平方增 然地将k分类问题转化为k个两类SVM分类问 长，但就分类速度来说，其并不比传统的1r 题.第i个SVM分类问题是把第i类作为一类，其 SVM方法慢；而且分类精度也比1-a-r SVM高， 余k-1类视为另一类.设有n个训练数据为(x1, 但是这种方法也存在缺点：分类器的数目随类 n),xm,ym),其中x,∈RP,∈1，k为x 数急剧增加，导致决策时速度降低，在测试阶段，采 的类别标号，i=1,2,,n第i个SVM需要解决下 用最大投票法时，如果2个类别的票数一致时则产 面的最优化问题： 生不可分情况，便存在误分、拒分区域， m即支w)+C,w, 2用层次型两类分类器实现多类分类 (w)Trx)+b≥1-号，ify=i, 这种组合形式也是建立在两类分类器的基础上 的，与上面介绍的方法的不同之处在于，这种方法的 (w)TMx)+6≤1+号，ify≠i, 测试阶段都是采用层次结构即树形结构，然而在每 号≥0，j=1,n 1) 个节点上仍用两类SVM进行分类，因此文中称之 求解式1)得到k个决策函数： 为用层次型两类分类器实现多类分类 (W)Tx)+6, 2.1有向无环图SVM 有向无环图SVM(directed acyclic graph SVM,DA GSVM)l.)是Platt1针对1-a1 SVM (w)x)b 存在的误分拒分现象提出的一种新算法.这种方法 测试时x属于决策函数输出值最大的那一类： 在训练阶段采用1a1SVM的任意两两组合训练 class of x =arg max ((w)+B).(2) 方式，同样也需要构造C个子分类器，但是在分类 这种方法简单、有效，训练时间较短，可用于大 决策过程中，DAG将所用子分类器构造成有向无环 规模数据.但其缺点是当类别数较大时，某一类的训 图如图1所示 练样本将大大少于其他类的训练样本的总和，这种 SVM 训练样本的不均衡将对精度产生影响，且存在误分、 拒分区域 非1 非4 1.2 1-a1 SVM SVM SVM1 2.4 (11、》 1-ar1SVM算法(one-against-one)是在每2类 非2 1作4 非3 之间训练一个分类器，因此对于一个k类问题，训练 阶段共构造C个两类分类器，每个分类器是取任意 SVM2 2个类别的数据进行训练.对于第1类和第j类之间 非2 非3非 的训练，需要解决下面的两类分类问题： wwcw w)Tx)+P≥1-，ify=i 图1 DAGSVM4分类的树权结构 (W')Tx+P≤1+9，ify,= Fig.I Tree structure of DAGSVM four-classification 9≥0 (3) 它包括C个内部节点和k个叶子节点，其中每 在测试阶段有不同的方法确定样本属于哪一 个内部节点都是一个两类分类的子分类器，并与下 类，最常用的一种方法是“最大投票法”，即每个两类 一层的2个内部节点相连.当对未知样本分类时，首 分类器都对样本的类别进行判断，采用投票机制为 先从根节点开始，根据根节点的分类结果用下一层 其相应的类别投上一票，最后得票最多的类即是该 中的左节点或者右节点继续分类，直到达到底层某 未知样本的所属类 个叶节点为止，该叶子节点就是未知样本所属的类 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
1 用多个两类分类器实现多类分类 1. 1 12a2r SVM 12a2r SVM (one2against2rest) [1 ][6 ] 算法是用支 持向量机解决多类分类问题的最早的方法 ,对于 k ( k ≥2) 类 SVM 分类问题 ,构造 k 个两类分类器 ,自 然地将 k 分类问题转化为 k 个两类 SVM 分类问 题. 第 i 个 SVM 分类问题是把第 i 类作为一类 ,其 余 k - 1 类视为另一类. 设有 n 个训练数据为 ( x1 , y1 ) , …, ( x n , y n ) ,其中 xi ∈R D , yi ∈{ 1 , …, k} 为 xi 的类别标号 , i = 1 ,2 , …, n. 第 i 个 SVM 需要解决下 面的最优化问题 : min w , b i ,εi 1 2 (w i ) T w i + C ∑ n j =1 εi j (w i ) T , (w i ) T <( xi) + b i ≥1 - εi j ,if yj = i , (w i ) T <( xi) + b i ≤- 1 +εi j ,if yj ≠i , εi j ≥0 , j = 1 , …, n. (1) 求解式(1) 得到 k 个决策函数 : (w 1 ) T <( x) + b 1 , … (w k ) T <( x) + b k . 测试时 x 属于决策函数输出值最大的那一类 : class of x ≡arg max i = 1 , …, k ( (w i ) T <( x) + b i ) . (2) 这种方法简单、有效 ,训练时间较短 ,可用于大 规模数据. 但其缺点是当类别数较大时 ,某一类的训 练样本将大大少于其他类的训练样本的总和 ,这种 训练样本的不均衡将对精度产生影响 ,且存在误分、 拒分区域. 1. 2 12a21 SVM 12a21 SVM 算法 (one2against2one) 是在每 2 类 之间训练一个分类器 ,因此对于一个 k 类问题 ,训练 阶段共构造 C 2 k 个两类分类器 ,每个分类器是取任意 2 个类别的数据进行训练. 对于第 i 类和第 j 类之间 的训练 ,需要解决下面的两类分类问题 : min w ij , b ij ,εij 1 2 (w ij ) T w ij + C ∑t εij t (w ij ) T ; (w ij ) T <( xt) + b ij ≥1 - εij t , if yt = i; (w ij ) T <( xt) + b ij ≤- 1 +εij t ,if yt = j. εij t ≥0 (3) 在测试阶段有不同的方法确定样本属于哪一 类 ,最常用的一种方法是“最大投票法”,即每个两类 分类器都对样本的类别进行判断 ,采用投票机制为 其相应的类别投上一票 ,最后得票最多的类即是该 未知样本的所属类. 对未知样本 x 进行分类时 ,判断符号函数 f ( x) = sign ( (w ij ) T <( x) + b ij ) , (4) 若 x 属于第 i 类则第 i 类的票数加 1 ,反之第 j 类加 1. x 属于最后票数最多的那一类. 由于每个 SVM 只考虑 2 类样本 ,故单个 SVM 容易训练 ;另外 ,虽然它的复杂度以类数按平方增 长 , 但就分类速度来说 , 其并不比传统的 12a2r SVM 方法慢 ; 而且分类精度也比 12a2r SVM 高. 但是这种方法也存在缺点 :分类器的数目随类 数急剧增加 ,导致决策时速度降低 ,在测试阶段 ,采 用最大投票法时 ,如果 2 个类别的票数一致时则产 生不可分情况 ,便存在误分、拒分区域. 2 用层次型两类分类器实现多类分类 这种组合形式也是建立在两类分类器的基础上 的 ,与上面介绍的方法的不同之处在于 ,这种方法的 测试阶段都是采用层次结构即树形结构 ,然而在每 个节点上仍用两类 SVM 进行分类 ,因此文中称之 为用层次型两类分类器实现多类分类. 2. 1 有向无环图 SVM 有 向 无 环 图 SVM ( directed acyclic grap h SVM ,DA G2SVM) [ 1 ,6 - 7 ]是 Platt [10 ]针对 12a21 SVM 存在的误分拒分现象提出的一种新算法. 这种方法 在训练阶段采用 12a21 SVM 的任意两两组合训练 方式 ,同样也需要构造 C 2 k 个子分类器 ,但是在分类 决策过程中 ,DA G将所用子分类器构造成有向无环 图如图 1 所示. 图 1 DA G2SVM 4 分类的树杈结构 Fig. 1 Tree structure of DA G2SVM four2classification 它包括 C 2 k 个内部节点和 k 个叶子节点 ,其中每 个内部节点都是一个两类分类的子分类器 ,并与下 一层的 2 个内部节点相连. 当对未知样本分类时 ,首 先从根节点开始 ,根据根节点的分类结果用下一层 中的左节点或者右节点继续分类 ,直到达到底层某 个叶节点为止 ,该叶子节点就是未知样本所属的类 · 21 · 智 能 系 统 学 报 第 2 卷
第2期 赵春晖，等：多类支持向量机方法的研究现状与分析 ·13· 别 面便会把第2类排除掉：然后序列更新为1-3-4， DAGSVM简单易行，每个未知样本只需使用 1vs4的超平面则把第4类从序列中去掉：最后序列 k-1个决策函数即可得出结果，较“1x1SVM”方 变为1-3,1vs3的超平面把样本点x归属于第1 法提高了测试速度，而且不存在拒分区域」 类.这个例子说明DAG中不同的节点顺序会导致 这种方法有2个主要的缺点：一个是存在自上 部分样本的分类结果不同，从而降低了分类精度 而下的“误差累积”现象.这是层次结构的固有弊端， 2.2自适应DA GSVM 故DAGSVM也逃脱不掉，即如果在某个结点上发 针对DAG存在的误差累积效应，文献[2]提出 生分类错误，则会把分类错误延续到该结点的后续 了一种自适应DAGSVM(adaptive directed acyclic 结点上.若采用该方法处理一个20类的问题，每个 graph SVM,ADA GSVM)方法.该方法是在DAG 未知样本所属的真实类别需要和其他类别经过19 的基础上改进的，是倒三角结构的DAG. 次两类测试才能得到最后结果.假设每个两类分类 对于k类分类问题，在训练阶段仍采用1x1 器的错分概率为1%，那么该未知样本累积的错分 SVM的任意两两组合训练方式，构造C个子分类 的概率为1-0.999=17.38%，由此可以看出累积器.测试阶段，ADAG包括k-1个内部节点，其中 误差随着类别数目的增加而增加.而且分类错误在 每个内部节点都是一个两类分类的子分类器，节点 越靠近根结点的地方发生，误差的累积效应越明显， 的排列是一个倒三角的结构，在最顶层有M2个节 分类性能就越差，尤其在根结点上发生分类错误，将 点，第2层有W2个节点，以此类推，最底层就是最 严重影响分类性能.另一个缺点是该方法的最后输 后的输出结果即叶节点，其结构如图3所示 出结果对节点的排列顺序的依赖性很大，用一个二 维的4类分类问题的图例来说明一下这个问题，如 图2所示 自适应层A B1 B2 BlvsB2 自适应层B 输出类 输出层 图38类ADAG分类结构图 Fig.3 Framework of eight sorts of ADA G classification 用ADAG进行分类，顶层有M2个两类分类 图2DAG输出取决于不同节点序列 器，每个分类器输出的结果参与下一层的分类，在第 Fig.2 DA Goutput depends on different node sequence 2层分类时，分类器减少到从2个，以此类推，每循 图2中1’，2’，3'和4’是类别符号，图中阴 环一层分类器将会减少一半，直到达到最底层.和 影部分的数据最后的输出类别取决于DAG不同的 DAG算法一样，未知样本也需要计算k-1个决策 节点序列，节点的排序不同，未知样本的输出结果也 函数得到最后的结果.但是未知样本的真实类别只 会不一样.以图中样本点x为例，当节点的序列为 需要和其他类别计算lok次或更少，和DAG的 1·2-3-4时，首先1vs4分类超平面会把类4给否 k-1次相比减小了很多，这样就可以在很大程度上 决掉，因为样本点x不在类4的那一边；然后序列变 减少了误差的累积 成1-2-3,1vs3超平面把类3从序列中排除掉；最 2.3重新排序ADAGSVM 后序列变为1-2,1vs2的超平面会把样本点x的类 针对DAG的节点序列的依赖性，文献[3]在文 别定为第2类. 献[2]的基础上提出了一种重新排序的ADAG(re 改变一下节点的排列顺序，则会得到另外一种 结果.若序列为2.1-3-4，首先2vs4的分类超平 ordering adaptive directed acyclic graph SVM, 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
别. DA G2SVM 简单易行 ,每个未知样本只需使用 k - 1个决策函数即可得出结果 ,较“12a21 SVM”方 法提高了测试速度 ,而且不存在拒分区域. 这种方法有 2 个主要的缺点 :一个是存在自上 而下的“误差累积”现象. 这是层次结构的固有弊端 , 故 DA G2SVM 也逃脱不掉 ,即如果在某个结点上发 生分类错误 ,则会把分类错误延续到该结点的后续 结点上. 若采用该方法处理一个 20 类的问题 ,每个 未知样本所属的真实类别需要和其他类别经过 19 次两类测试才能得到最后结果. 假设每个两类分类 器的错分概率为 1 % ,那么该未知样本累积的错分 的概率为 1 - 0. 99 19 = 17. 38 % ,由此可以看出累积 误差随着类别数目的增加而增加. 而且分类错误在 越靠近根结点的地方发生 ,误差的累积效应越明显 , 分类性能就越差 ,尤其在根结点上发生分类错误 ,将 严重影响分类性能. 另一个缺点是该方法的最后输 出结果对节点的排列顺序的依赖性很大 ,用一个二 维的 4 类分类问题的图例来说明一下这个问题 ,如 图 2 所示. 图 2 DA G输出取决于不同节点序列 Fig. 2 DA G output depends on different node sequence 图 2 中‘1’‘, 2’‘, 3’和‘4’是类别符号 ,图中阴 影部分的数据最后的输出类别取决于 DA G 不同的 节点序列 ,节点的排序不同 ,未知样本的输出结果也 会不一样. 以图中样本点 x 为例 ,当节点的序列为 1 - 2 - 3 - 4时 ,首先 1vs4 分类超平面会把类 4 给否 决掉 ,因为样本点 x 不在类 4 的那一边 ;然后序列变 成 1 - 2 - 3 ,1vs3 超平面把类 3 从序列中排除掉 ;最 后序列变为 1 - 2 ,1vs2 的超平面会把样本点 x 的类 别定为第 2 类. 改变一下节点的排列顺序 ,则会得到另外一种 结果. 若序列为 2 - 1 - 3 - 4 ,首先 2vs4 的分类超平 面便会把第 2 类排除掉 ;然后序列更新为 1 - 3 - 4 , 1vs4 的超平面则把第 4 类从序列中去掉 ;最后序列 变为 1 - 3 ,1vs3 的超平面把样本点 x 归属于第 1 类. 这个例子说明 DA G 中不同的节点顺序会导致 部分样本的分类结果不同 ,从而降低了分类精度. 2. 2 自适应 DA G2SVM 针对 DA G存在的误差累积效应 ,文献[ 2 ]提出 了一种自适应 DA G2SVM (adaptive directed acyclic grap h SVM ,ADA G2SVM) 方法. 该方法是在 DA G 的基础上改进的 ,是倒三角结构的 DA G. 对于 k 类分类问题 ,在训练阶段仍采用 12a21 SVM 的任意两两组合训练方式 ,构造 C 2 k 个子分类 器. 测试阶段 ,ADA G 包括 k - 1 个内部节点 ,其中 每个内部节点都是一个两类分类的子分类器 ,节点 的排列是一个倒三角的结构 ,在最顶层有 k/ 2 个节 点 ,第 2 层有 k/ 2 2 个节点 ,以此类推 ,最底层就是最 后的输出结果即叶节点 ,其结构如图 3 所示. 图 3 8 类 ADA G分类结构图 Fig. 3 Framework of eight sorts of ADA G classification 用 ADA G进行分类 ,顶层有 k/ 2 个两类分类 器 ,每个分类器输出的结果参与下一层的分类 ,在第 2 层分类时 ,分类器减少到 k/ 2 2 个 ,以此类推 ,每循 环一层分类器将会减少一半 ,直到达到最底层. 和 DA G算法一样 ,未知样本也需要计算 k - 1 个决策 函数得到最后的结果. 但是未知样本的真实类别只 需要和其他类别计算 log2 k 次或更少 ,和 DA G 的 k - 1次相比减小了很多 ,这样就可以在很大程度上 减少了误差的累积. 2. 3 重新排序 ADA G2SVM 针对 DA G的节点序列的依赖性 ,文献[ 3 ]在文 献[2 ]的基础上提出了一种重新排序的 ADA G(re2 ordering adaptive directed acyclic grap h SVM , 第 2 期 赵春晖 ,等 :多类支持向量机方法的研究现状与分析 · 31 ·
·14· 智能系统学报 第2卷 RADA GSVM)方法，该方法是根据权系数向量为 未知样本寻找最佳的节点序列，以克服DAG中节 点序列产生的分类误差， 支持向量机分类原理是寻找最优分类面，不但 初始化表 能将两类无错误的分开，而且要使两类的分类间隔 初始化项 最大，分类间隔就是两类样本中离分类面最近的两 4863725 个样本之间的距离即2/Iw‖.也就是说权系数向 量w川越小，分类间隔越大，两类样本之间的可分 分类新例 性就越大.因此川wI的值在一定程度上会影响数 A1A2A3A4 据的分类精度，文献[3]把这一现象应用到分类节点 心录表 分类和记录项 的选择上以解决DAG中节点排序不同而产生分类 T1 37 误差的问题 AIA2A3A4 对于k类分类问题，在训练阶段仍采用1x1 SVM的任意两两组合训练方式，构造C个两类分 BIB2 最后分类器 类器.测试阶段和ADAG一样包括k·1个内部节 点，每个节点都会否定一个类别，不同之处在于节点 回 输出项 输出类 序列的初始化以及每一层节点的排列顺序 首先，利用权向量最小值的最佳匹配算法把个 图48类RADAG分类结构图 类别按最佳排列顺序初始化为一个列表，第2步，顶 Fig.4 Framework of eight sorts of RADA G classification 层分类的每个节点的类别组合是根据初始化列表进 一个包含多个类别的节点上的分类器都将其中类别 行排列的，列表中的第一个类别和最后一个类别组 合成第一个决策节点，第2个类别和列表中倒数第 均分为2类，这样的结构称为“正态树”.下面主要介 2个类别组合成第2个决策节点，以此类推；第3 绍一下偏态树的分类原理」 步，顶层分类器的输出结果排除了一部分类别，剩下 的类别将参与第2层分类.在第2层分类之前，仍需 要利用权向量最小值的最佳匹配算法把这些类别重 新排序.不同的测试样本在这一层会得到不同的序 列，这依赖于上一层分类的结果.重复第2步和第3 步直到最后一层只剩下一个类别.RADAG分类结 构如图4所示 权向量最小值的最佳匹配算法是根据不同的 川w‖值选择最佳的两类构造子分类器，以减少错 (a)8类问概的权向量 (b)一个两类分类器构造子集 分样本提高分类精度，Iw‖值越小两类样本之间 的可分性就越大.如图5(a)所示，每两个类别构成 图58类问题的权向量图和其中一个两类分类器构造子集 的分类器都有存在一个‖w‖值.权向量最小值的 Fig.5 Weight vector of eight sorts of problems and 最佳匹配算法就是选择一个权向量和最小的一个子 Structuring subset of a twoclassification classifier 集来构造一系列的两类分类器如图5(b) 给定一个由n个学习样本组成的k类分类问 题，学习样本为(x,y,其中x∈RP,i=1,2,n, 2.4二叉树多级SVM y,∈{1，为x的类别标号，设m第类学习样本 针对I-rSVM和1x1SVM中存在的无法 数目为nm.该算法的核心思想是在训练阶段构造 识别的区域，文献[4]提出了二叉树多级SVM(bi k-1个两类SVM,其中第m个(m=1,2,,k-1) nary tree multistage support vector machine,BT- 两类SVM的学习样本仅有分类标号≥m的样本 MSVM)4剧.根据其层次结构的形态不同该方法又 子集组成，且将原第m类的样本的分类标号改为 可分为2种情况：1)从顶层开始，每一个包含多个类 +1,其余k-m类的样本的分类标号改为-1，即 别的节点上的分类器只将一个类别与其他类别分 +1,y:=m 开，这样的结构称之为“偏态树”；2)从顶层开始，每 (5 1.(y:>m) 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved. http://www.cnki.net
RADA G2SVM) 方法 ,该方法是根据权系数向量为 未知样本寻找最佳的节点序列 ,以克服 DA G 中节 点序列产生的分类误差. 支持向量机分类原理是寻找最优分类面 ,不但 能将两类无错误的分开 ,而且要使两类的分类间隔 最大 ,分类间隔就是两类样本中离分类面最近的两 个样本之间的距离即 2/ ‖w ‖. 也就是说权系数向 量 ‖w ‖越小 ,分类间隔越大 ,两类样本之间的可分 性就越大. 因此 ‖w ‖的值在一定程度上会影响数 据的分类精度 ,文献[ 3 ]把这一现象应用到分类节点 的选择上以解决 DA G中节点排序不同而产生分类 误差的问题. 对于 k 类分类问题 ,在训练阶段仍采用 12a21 SVM 的任意两两组合训练方式 ,构造 C 2 k 个两类分 类器. 测试阶段和 ADA G 一样包括 k - 1 个内部节 点 ,每个节点都会否定一个类别 ,不同之处在于节点 序列的初始化以及每一层节点的排列顺序. 首先 ,利用权向量最小值的最佳匹配算法把个 类别按最佳排列顺序初始化为一个列表 ;第 2 步 ,顶 层分类的每个节点的类别组合是根据初始化列表进 行排列的 ,列表中的第一个类别和最后一个类别组 合成第一个决策节点 ,第 2 个类别和列表中倒数第 2 个类别组合成第 2 个决策节点 ,以此类推 ;第 3 步 ,顶层分类器的输出结果排除了一部分类别 ,剩下 的类别将参与第 2 层分类. 在第 2 层分类之前 ,仍需 要利用权向量最小值的最佳匹配算法把这些类别重 新排序. 不同的测试样本在这一层会得到不同的序 列 ,这依赖于上一层分类的结果. 重复第 2 步和第 3 步直到最后一层只剩下一个类别. RADA G 分类结 构如图 4 所示. 权向量最小值的最佳匹配算法是根据不同的 ‖w ‖值选择最佳的两类构造子分类器 ,以减少错 分样本提高分类精度 , ‖w ‖值越小两类样本之间 的可分性就越大. 如图 5 (a) 所示 ,每两个类别构成 的分类器都有存在一个 ‖w ‖值. 权向量最小值的 最佳匹配算法就是选择一个权向量和最小的一个子 集来构造一系列的两类分类器如图 5 (b) . 2. 4 二叉树多级 SVM 针对 12a2r SVM 和 12a21 SVM 中存在的无法 识别的区域 ,文献[ 4 ]提出了二叉树多级 SVM ( bi2 nary tree multistage support vector machine ,B T2 MSVM) [4 ,8 ] . 根据其层次结构的形态不同该方法又 可分为 2 种情况 :1) 从顶层开始 ,每一个包含多个类 别的节点上的分类器只将一个类别与其他类别分 开 ,这样的结构称之为“偏态树”;2) 从顶层开始 ,每 图 4 8 类 RADA G分类结构图 Fig. 4 Framework of eight sorts of RADA G classification 一个包含多个类别的节点上的分类器都将其中类别 均分为 2 类 ,这样的结构称为“正态树”. 下面主要介 绍一下偏态树的分类原理. 图 5 8 类问题的权向量图和其中一个两类分类器构造子集 Fig. 5 Weight vector of eight sorts of problems and Structuring subset of a two2classification classifier 给定一个由 n 个学习样本组成的 k 类分类问 题 ,学习样本为( xi , yi) ,其中 xi ∈R D , i = 1 ,2 , …, n , yi ∈{ 1 , …, k}为 xi 的类别标号 ,设 m 第类学习样本 数目为 nm . 该算法的核心思想是在训练阶段构造 k - 1个两类 SVM ,其中第 m 个 ( m = 1 , 2 , …, k - 1) 两类 SVM 的学习样本仅有分类标号 yi ≥m 的样本 子集组成 ,且将原第 m 类的样本的分类标号改为 + 1 ,其余 k - m 类的样本的分类标号改为 - 1 ,即 yi = + 1 , ( yi = m) , - 1 , ( yi > m) . (5) · 41 · 智 能 系 统 学 报 第 2 卷
第2期 赵春晖，等：多类支持向量机方法的研究现状与分析 ·15 1)训练阶段： 类11.该方法类似于1 ar SVM,针对k类问题，需 第1步：令m=0,选择合适的核函数K(x,x) 要构造k个两类分类函数，其中第m个函数 及有关参数， w(x+b是用来把第m类与其他类别区分开的. 第2步：令m=m+1, 这k个分类函数用一个最优化问题来解决，公式描 第3步：构造第m个两类SVM的学习样本集 述如下： 合Lm:(x,y),X∈R”,i=1,2,n,y∈{+1， -1y,n=∑n,针对学习样本Lm求解两类分类 mi2w.+C,王ww+ 问题： b,≥w(x+bn+2- 第4步：建立Lm的最优决策超平面： "≥0，i=1,…1,m∈f1,…k八y4. 8) f"(W=sgn∑yK(x·W+b 求解式(8)得到的决策函数为 6 第5步：若m=k-1,则训练结束：否则转至第 arg maxw+b) (9) 2步继续训练。 2)测试阶段 该方法尽管看起来简洁，但是在最优化问题的 根据式(6)计算未知样本在每个两类SVM中 求解过程中变量过多，选择的目标函数过于复杂，从 f(xy(m=1,2,,-1)的决策输出值，并按式(7) 而导致它的计算复杂度高，分类精度上也不占优势 做出分类决策： 当训练样本数目非常大的时候，这一问题更加突出 f(x) 因此，这一类方法在实际应用中并不常用」 m,若f(xy=f(xy=…=fm1(y= 4纠错编码SVM -1且fm(y=+1, 、k,若f(y=f产(x=…=f1(W=.1. 该方法是对类别进行二进制编码将多类问题转 (7) 化为多个两类问题.采用具有纠错能力的编码对类 BTM-SVM的分类结构图如图6所示 别进行编码，并将SVM作为码位分类器，这种多类 分类方法称之为纠错编码支持向量机(error correc- SVM':/'x) ting codes,ECC-SVM)17 +1 对于k类分类问题，给每一个类别赋予长度为 SVM2:fx) L的二进制编码，形成一个k行L列的码本如表 1).对于其中第i∈1,2，L列，将码字为“0”的 所有类别作为一类，码字为“1”的类别作为另一类 因此在每个码位上对应着一个两类分类问题.这样 就将k类分类问题转化为L个两类分类问题.当对 SVM: 一个未知样本分类时，L个SVM分类器的分类结 果构成一个编码5，然后计算码本中k个标准编码 与s之间的汉明距离，距离最小者所代表的类别即 为该样本所属的类别： Dietterich和Bakiri给出了一个好的纠错码 图6类二叉树多级SVM分类结构 应该满足的条件： Fig.6 Structure of -sort two-branch multicalss 1)行n(i=1,…与行50=1，k:j≠之 SVM classification 间不相关： 3用一个最优化问题一次性实现多类 2)列c(i=1,…L)与列Gj=1,…,L;j≠) 及其补G之间不相关： 分类 3)没有全为“0”或全为“1”的列 这种方法和上述的方法的不同之处在于它是采 根据上述条件对于一个k类分类问题，纠错码 用将多个分类面的参数求解合并到一个最优化问题 长度L的取值范围是1ogk,2.1·1.当L=l0g2k 中，通过求解该最优化问题“一次性”的实现多类分 时，编码失去纠错功能 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
1) 训练阶段 : 第 1 步 :令 m = 0 ,选择合适的核函数 K( x , xi) 及有关参数; 第 2 步 :令 m = m + 1 ; 第 3 步 :构造第 m 个两类 SVM 的学习样本集 合 L m : ( x m i , y m i ) , xi ∈R D , i = 1 , 2 , …, n m , yi ∈{ + 1 , - 1} , n m = ∑ k j = m nj , ,针对学习样本 L m 求解两类分类 问题; 第 4 步 :建立 L m 的最优决策超平面 : f m ( x) = sgn ∑ n i = 1 αm i y m i K ( x m i ·x) + b m . (6) 第 5 步 :若 m = k - 1 ,则训练结束;否则转至第 2 步继续训练. 2) 测试阶段 根据式(6) 计算未知样本在每个两类 SVM 中 f m ( x) ( m = 1 ,2 , …, k - 1) 的决策输出值 ,并按式(7) 做出分类决策 : f ( x) = m ,若 f 1 ( x) = f 2 ( x) = … = f m- 1 ( x) = - 1 且 f m ( x) = + 1 , k ,若 f 1 ( x) = f 2 ( x) = … = f k- 1 ( x) = - 1. (7) B TM2SVM 的分类结构图如图 6 所示. 图 6 类二叉树多级 SVM 分类结构 Fig. 6 Structure of k2sort two2branch multicalss SVM classification 3 用一个最优化问题一次性实现多类 分类 这种方法和上述的方法的不同之处在于它是采 用将多个分类面的参数求解合并到一个最优化问题 中 ,通过求解该最优化问题“一次性”的实现多类分 类[1 ,6 ] . 该方法类似于 12a2r SVM ,针对 k 类问题 ,需 要构 造 k 个 两 类 分 类 函 数 , 其 中 第 m 个 函 数 w T m <( x) + b是用来把第 m 类与其他类别区分开的. 这 k 个分类函数用一个最优化问题来解决 ,公式描 述如下 : min w , b,ε 1 2 ∑ k m =1 w T mwm + C ∑ l i = 1 m∑≠y i εm i w T y i <( xi) + by i ≥w T m <( xi) + bm + 2 - εm i , εm i ≥0 , i = 1 , …, l , m ∈{ 1 , …, k}\ yi . (8) 求解式(8) 得到的决策函数为 arg max m =1 ,2 , …, k (w T m <( x) + bm ) . (9) 该方法尽管看起来简洁 ,但是在最优化问题的 求解过程中变量过多 ,选择的目标函数过于复杂 ,从 而导致它的计算复杂度高 ,分类精度上也不占优势. 当训练样本数目非常大的时候 ,这一问题更加突出. 因此 ,这一类方法在实际应用中并不常用. 4 纠错编码 SVM 该方法是对类别进行二进制编码将多类问题转 化为多个两类问题. 采用具有纠错能力的编码对类 别进行编码 ,并将 SVM 作为码位分类器 ,这种多类 分类方法称之为纠错编码支持向量机(error correc2 ting codes , ECC2SVM) [ 7 ] . 对于 k 类分类问题 ,给每一个类别赋予长度为 L 的二进制编码 ,形成一个 k 行 L 列的码本 (如表 1) . 对于其中第 i ∈{ 1 , 2 , …, L } 列 ,将码字为“0”的 所有类别作为一类 ,码字为“1”的类别作为另一类 , 因此在每个码位上对应着一个两类分类问题. 这样 就将 k 类分类问题转化为 L 个两类分类问题. 当对 一个未知样本分类时 , L 个 SVM 分类器的分类结 果构成一个编码 s,然后计算码本中 k 个标准编码 与 s 之间的汉明距离 ,距离最小者所代表的类别即 为该样本所属的类别. Dietterich 和 Bakiri [7 ] 给出了一个好的纠错码 应该满足的条件 : 1) 行 ri ( i = 1 , …, k) 与行 rj ( j = 1 , …, k ; j ≠i) 之 间不相关; 2) 列 ci ( i = 1 , …, L) 与列 cj ( j = 1 , …, L ; j ≠i) 及其补 cj 之间不相关; 3) 没有全为“0”或全为“1”的列. 根据上述条件对于一个 k 类分类问题 ,纠错码 长度 L 的取值范围是 log2 k , 2 k - 1 - 1. 当 L = log2 k 时 ,编码失去纠错功能. 第 2 期 赵春晖 ,等 :多类支持向量机方法的研究现状与分析 · 51 ·
·16· 智能系统学报 第2卷 表18类分类问题的L=5的纠错编码 函数.提出了将多种分类方法结合到一起组成混合 Table 1 Error-correcting codes of eight sorts of 分类器的思想.由于实际应用中需要解决大量的多 problems for L=5 类别的分类问题，如何有效地运用方法解决多类分 类别 码 字 类问题将会受到越来越多的重视.该文总结了现有 编号 2 3 4 J 的主要的多类支持向量机及其优缺点，希望在这方 1 0 0 0 1 面起到一点承前启后的作用，以便读者更好地学习、 2 0 0 1 0 1 掌握和运用多类支持向量机技术 3 0 1 0 0 4 0 1 1 0 0 参考文献： 5 0 0 [1]HSU C W LIN CJ.A comparison of methods for multi- 6 1 class support vector machines[J].IEEE Transactions on 0 Neural Networks,2002,13(2):415-425 0 [2 KUSIRKUL B,USSIVA KUL N.Multiclass support vector machines using adaptive directed acyclic graph 纠错编码支持向量机在分类过程中所需分类器 [A].Proceedings of the 2002 International Joint Confer- 的个数等于纠错编码的位数L,当类别大的时候仅 ence on Neural Networks C].Honolulu,HI,USA, 需要较少的分类器，但是如何根据具体问题确定码 2002,1(5):980-985. 本选择排列顺序以达到最优的分类性能依然有待 [3]PHETKAEW T,KUSIRIKUL B.RIVEPIBOON W. 研究 Reordering adaptive directed acyclic graphs:an improved algorithm for multiclass support vector machines A]. 5结束语 Proceedings of the 2003 International Joint Conference on Neural Networks[C].Portland,OR,USA,2003. 该文总结了现有多类支持向量机的4种主要结 [4]TIAN X,DENG F Q.An improved multi-class SVM algo- 构形式，并详细介绍了其代表性算法，对各种方法进 rithm and its application to the credit sooring model[A].Pro- 行了性能优劣的比较.用多个两类分类器实现多类 ceedings of the fifth World Congress on Intelligent Control and 分类是最早发展起来的多类支持向量机，其代表算 Automation[C].Hangzhou,China,2004. [5]ANGUITA D,RIDELLA S,STERPI D.A new method 法是1-a-r SVM和1-a1SVM.和1-arSVM相比， for multiclass support vector machines[A].Proceedings 1a1SVM不仅提高了训练速度而且改善了误分、 of the 2004 International Joint Conference on Neural Net- 拒分区域范围，但在采用投票机制进行决策时仍存 works[C].Budapest,Hungary,2004. 在一些无法分类的样本.当类别数目过大时，这种方 [6]黄勇，郑春颖，宋忠虎.多类支持向量机算法综述[U] 法的训练速度和分类速度都会大幅度的降低，因此 计算技术与自动化，2005,24(4)：61-63 比较适用于小类别的分类研究： HUANG Yong,ZEN G Chunyin,SONG Zhonghu.Mul- ticlass support vector machines algorithm summari-zation 经过进一步研究，人们提出了几种层次结构的 [J ]Computing Technology and Automation,2005,24 SVM,与第一种方法不同之处在于，这种方法的测 (4):61-63. 试阶段采用树形结构，在每个节点上仍用两类SVM [7]刘志刚，李德仁，秦前清，史文中，支持向量机在多类 进行分类，其代表算法有DAGSVM和BTM-SVM 分类问题中的推广U】.计算机工程与应用，2004(7)： 等.这种方法简单易行，在分类速度和精度上也有一 10-13. 定的改善，对于一般规模的多分类问题，是一种有效 LIN Zhigang,LI Deren,QIN Qianqing,SHI Wenzhong. An analytical overview of methods for multi-category 的方法.用一个最优化问题实现多分类问题的计算 support vector machines[J].Computer Engineering and 复杂度比较高，因此一般实际应用中都不采用.纠错 Applications,2004(7):10-13. 编码SVM在如何选择码本及排列顺序以达到最优 [8]TA KA HASHI F.Decisiorrtree-based multi-class sup- 的分类性能上还有待于进一步的理论研究 port vector machines[A].Proceedings of the 9th Inter- 随着研究的深入，提出了模糊支持向量机，它是 national Conference on Neural Information Processing 针对SVM多类问题中存在不可分区域的现象提出 [C].Orchid Country Club,Singapore,2002. [9]PLATT J,CRISTIANINI N,SHAWE TA YLOR J. 的.当一些样本不能被确切地定义为属于某一类时， Large margin DA Gs for multiclass classification A]. 文中所述的多类方法便会把此类样本硬性分配给某 Proceedings of Neural Information Processing Systems 一类别，而模糊支持向量机则是引入了模糊隶属度 [C].[s.1.]Cambridge,2000. 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
表 1 8 类分类问题的 L = 5 的纠错编码 Table 1 Error2correcting codes of eight sorts of problems for L = 5 类别 编号 码 字 1 2 3 4 5 1 0 0 0 1 1 2 0 0 1 0 1 3 0 1 0 0 1 4 0 1 1 0 0 5 1 0 0 1 0 6 1 1 0 1 1 7 1 1 1 0 1 8 1 1 1 1 0 纠错编码支持向量机在分类过程中所需分类器 的个数等于纠错编码的位数 L ,当类别大的时候仅 需要较少的分类器 ,但是如何根据具体问题确定码 本、选择排列顺序以达到最优的分类性能依然有待 研究. 5 结束语 该文总结了现有多类支持向量机的 4 种主要结 构形式 ,并详细介绍了其代表性算法 ,对各种方法进 行了性能优劣的比较. 用多个两类分类器实现多类 分类是最早发展起来的多类支持向量机 ,其代表算 法是 12a2r SVM 和 12a21 SVM. 和 12a2rSVM 相比 , 12a21 SVM 不仅提高了训练速度而且改善了误分、 拒分区域范围 ,但在采用投票机制进行决策时仍存 在一些无法分类的样本. 当类别数目过大时 ,这种方 法的训练速度和分类速度都会大幅度的降低 ,因此 比较适用于小类别的分类研究. 经过进一步研究 ,人们提出了几种层次结构的 SVM ,与第一种方法不同之处在于 ,这种方法的测 试阶段采用树形结构 ,在每个节点上仍用两类 SVM 进行分类 ,其代表算法有 DA G2SVM 和 B TM2SVM 等. 这种方法简单易行 ,在分类速度和精度上也有一 定的改善 ,对于一般规模的多分类问题 ,是一种有效 的方法. 用一个最优化问题实现多分类问题的计算 复杂度比较高 ,因此一般实际应用中都不采用. 纠错 编码 SVM 在如何选择码本及排列顺序以达到最优 的分类性能上还有待于进一步的理论研究. 随着研究的深入 ,提出了模糊支持向量机 ,它是 针对 SVM 多类问题中存在不可分区域的现象提出 的. 当一些样本不能被确切地定义为属于某一类时 , 文中所述的多类方法便会把此类样本硬性分配给某 一类别 ,而模糊支持向量机则是引入了模糊隶属度 函数. 提出了将多种分类方法结合到一起组成混合 分类器的思想. 由于实际应用中需要解决大量的多 类别的分类问题 ,如何有效地运用方法解决多类分 类问题将会受到越来越多的重视. 该文总结了现有 的主要的多类支持向量机及其优缺点 ,希望在这方 面起到一点承前启后的作用 ,以便读者更好地学习、 掌握和运用多类支持向量机技术. 参考文献 : [ 1 ] HSU C W ,L IN C J. A comparison of methods for multi2 class support vector machines[J ]. IEEE Transactions on Neural Networks , 2002 , 13 (2) : 415 - 425. [ 2 ] KIJ SIR KUL B , USSIVA KUL N. Multiclass support vector machines using adaptive directed acyclic graph [A ]. Proceedings of the 2002 International Joint Confer2 ence on Neural Networks [ C ]. Honolulu , HI , USA , 2002 ,1 (5) : 980 - 985. [3 ] PHET KAEW T , KIJ SIRIKUL B , RIV EPIBOON W. Reordering adaptive directed acyclic graphs: an improved algorithm for multiclass support vector machines [ A ]. Proceedings of the 2003 International Joint Conference on Neural Networks[C]. Portland , OR , USA , 2003. [4 ] TIAN X,DENG F Q. An improved multi2class SVM algo2 rithm and its application to the credit scoring model[A]. Pro2 ceedings of the fifth World Congress on Intelligent Control and Automation[C]. Hangzhou , China ,2004. [5 ]AN GUITA D , RIDELLA S , STERPI D. A new method for multiclass support vector machines[ A ]. Proceedings of the 2004 International Joint Conference on Neural Net2 works[C]. Budapest , Hungary , 2004. [6 ]黄 勇 ,郑春颖 ,宋忠虎. 多类支持向量机算法综述[J ]. 计算技术与自动化 , 2005 , 24 (4) : 61 - 63. HUAN G Yong , ZEN G Chunyin , SON G Zhonghu. Mul2 ticlass support vector machines algorithm summari2zation [J ]. Computing Technology and Automation , 2005 , 24 (4) : 61 - 63. [7 ]刘志刚 , 李德仁 , 秦前清 , 史文中. 支持向量机在多类 分类问题中的推广[J ]. 计算机工程与应用 , 2004 (7) : 10 - 13. L IN Zhigang , L I Deren , QIN Qianqing , SHI Wenzhong. An analytical overview of methods for multi2category support vector machines[J ]. Computer Engineering and Applications , 2004 (7) : 10 - 13. [ 8 ] TA KA HASHI F. Decision2tree2based multi2class sup2 port vector machines[ A ]. Proceedings of the 9th Inter2 national Conference on Neural Information Processing [C]. Orchid Country Club , Singapore , 2002. [ 9 ] PLA TT J , CRISTIANINI N , SHAWE2TA YLOR J. Large margin DA Gs for multiclass classification [ A ]. Proceedings of Neural Information Processing Systems [C]. [s. l. ] , Cambridge , 2000. · 61 · 智 能 系 统 学 报 第 2 卷
第2期 赵春晖，等：多类支持向量机方法的研究现状与分析 ·17 [10]PAUL G.Cox,Reza Adhami.Multi-class support vector [21]唐发明，王仲东，陈绵云.支持向量机多类分类算法研 machine classifier applied to hyper-spectral data [A ] 究0].控制与决策，2005,20(7)：746-749 Proceedings of the Thirty-Fourth Southeastern Sympo TANG Faming,WANG Zhongdong,CHEN Mianyun.On sium on System Theory [C].Huntsville,Alabama, multiclass classification methods for support vector machines 2002」 [J ]Control and Decision,2005,20(7)746-749. [11]FRANC V,HLAVAC V.Multi-class support vector [22]郑勇涛，刘玉树.支持向量机多分类问题研究J].计 machine [A].Proceedings of the 16th International 算机工程与应用，2005,41(23)：190-192 Conference on Pattern Recognition [C].Quebec City, ZHENG Yongtao,LIU Yushu.An analysis of multi- Canada2002 class support vector machines[J ]Computer Engineer- [12]L IN Chunfu,WAMG Shengde.Fuzzy support vector ing and Applications,2005,41(23):190-192 machines[J ]IEEE Transactions on Neural Networks, [23]祁亨年.支持向量机及其应用研究综述U].计算机工 2002,13(2):464-471. 程，2004,30(10)：6-9. [13]LI Kunlun,HUANG Houkuan,TIAN Shengfeng.A novel QI Hengnian.Support vector machines and application multiclass SVM classifier based on DDA G[A ]Proceedings research overview[J].Computer Engineering,2005,41 of the 2002 International Conference on Machine Learning (23):190.192 and Cybernetics[C].Beijing,China ,2002. [24]宋晓宁，束鑫.一种改进的模糊支持向量机的人脸识 [14 ARENAS-GARCIA J,PEREZ-CRUZ F.Multi-class 别方法U].微机发展，2005,15(3)：23.25. support vector machines:a new approach[A].Proceed- SONG Xiaoning,SHU Xin.An improved fuzzy support ings of the 2003 IEEE International Conference on A- vector machine and its application to face recognition[J]. coustics,Speech and Signal Processing [C].Hong Microcomputer Development,2005,15(3):23-25. Kong,China,2003. [25]刘江华，程君实，陈佳品.支持向量机训练算法综述 [15 ]L IU Yi,ZHENG Y F.One-against-all multi-Class SVM [U].信息与控制，2002,31(1)：45-50. classification using reliability measures[A].Proceed- LIU Jlanghua,CHENGJunshi,CHEN Jiapin.Support ings of the 2005 International Joint Conference on Neu- vector machine traning algorithm:a review [J].Infor- ral Networks[C].Montreal,Canada,2005. mation and Control,2002,31(1):45-50 [16]LU Baoliang,WANG Kaian,UTIYAMA M.A part- [26]张学工.关于统计学习理论与支持向量机0].自动化 versuspart method for massively parallel training of 学报，2000,26(1)：32.42 support vector machines[A].Proceedings of the 2004 ZHANG Xuegong.Introduction to statistical learning International Joint Conference on Neural Networks[C]. theory and support vector machines[J].Acta Automati- Budapest,Hungary,2004. ca Sinica,2000,26(1):32-42. [17]XIN Dong,WU Zhaohui,PAN Yunhe.A new multi- 作者简介： class support vector machines [A ]IEEE International 赵春晖，男，1965年生，博士，教授 Conference on Systems,Man and Cybernetics[C].Tuc- 博士生导师，主要研究方向为智能信息处 s0n,USA,2001. 理技术、图像处理.获省部级科技进步奖 [18]童学锋，石繁槐.FSVM在有限集脱机手写体汉字识 5项，发表论文180多篇，出版著作3部. 别中的应用U].计算机工程，2003,29(3)：109.111. Email zhaochunhui @hrbeu.edu.cn. TONG Xuefeng,SHI Fanhuai.Application Of FSVM for limited-set off-line handwritten chinese characters recognition[J ]Computer Engineering,2003,29(3): 陈万海，男，1963年生副教授，信号 109.111. 与信息处理专业博士研究生，主要研究 [19]李昆仑，黄厚宽，田盛丰.一种基于有向无环图的多类 方向为超光谱遥感图像处理技术，发表 SVM分类器D].模式识别与人工智能，2003,16(2)： 论文8篇 164-168. LI Kunlun,HUANG Houkuan,TIAN Shengfeng.A novel multi-class SVM classifier based on DDAG[J ] Pattern Recognition and Artificial Intelligence,2003,16 (2):164-168. 郭春燕，女，1984年生，硕士研究 [20]安金龙，王正欧，马振平.一种新的支持向量机多类分 生，主要研究方向为超光谱遥感图像处 类方法U].信息与控制，2004,33(3)：262-267. 理技术、目标分类 AN Jinlong,WANG Zhengou,MA Zhenping.A new SVM multiclass classification method [J ]Information and Control,2004,33(3):262.267 1994-2008 China Academie Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
[10 ] PAUL G. Cox ,Reza Adhami. Multi2class support vector machine classifier applied to hyper2spectral data [ A ]. Proceedings of the Thirty2Fourth Southeastern Sympo2 sium on System Theory [ C ]. Huntsville , Alabama , 2002. [11 ] FRANC V , HLAVAC V. Multi2class support vector machine [ A ]. Proceedings of the 16th International Conference on Pattern Recognition [ C ]. Quebec City , Canada ,2002. [12 ] L IN Chunfu , WAM G Shengde. Fuzzy support vector machines[J ]. IEEE Transactions on Neural Networks , 2002 , 13 (2) :464 - 471. [13 ]LI Kunlun , HUANG Houkuan , TIAN Shengfeng. A novel multi2class SVM classifier based on DDAG[A]. Proceedings of the 2002 International Conference on Machine Learning and Cybernetics[C].Beijing , China ,2002. [ 14 ] ARENAS2GARCIA J , PEREZ2CRUZ F. Multi2class support vector machines: a new approach[ A ]. Proceed2 ings of the 2003 IEEE International Conference on A2 coustics , Speech and Signal Processing [ C ]. Hong Kong ,China ,2003. [15 ]L IU Yi ,ZHEN G Y F. One2against2all multi2Class SVM classification using reliability measures [ A ]. Proceed2 ings of the 2005 International Joint Conference on Neu2 ral Networks[C]. Montreal , Canada ,2005. [16 ]LU Baoliang , WAN G Kaian , U TIYAMA M. A part2 versus2part method for massively parallel training of support vector machines[ A ]. Proceedings of the 2004 International Joint Conference on Neural Networks[C]. Budapest , Hungary ,2004. [17 ] XIN Dong , WU Zhaohui , PAN Yunhe. A new multi2 class support vector machines[ A ]. IEEE International Conference on Systems , Man and Cybernetics[C]. Tuc2 son , USA ,2001. [18 ]童学锋 , 石繁槐. FSVM 在有限集脱机手写体汉字识 别中的应用[J ]. 计算机工程 , 2003 , 29 (3) : 109 - 111. TON G Xuefeng , SHI Fanhuai. Application 0f FSVM for limited2set off2line handwritten chinese characters recognition[J ]. Computer Engineering , 2003 , 29 (3) : 109 - 111. [19 ]李昆仑 , 黄厚宽 , 田盛丰. 一种基于有向无环图的多类 SVM 分类器[J ]. 模式识别与人工智能 , 2003 , 16 (2) : 164 - 168. L I Kunlun , HUAN G Houkuan , TIAN Shengfeng. A novel multi2class SVM classifier based on DDA G[J ]. Pattern Recognition and Artificial Intelligence , 2003 , 16 (2) : 164 - 168. [20 ]安金龙 , 王正欧 , 马振平. 一种新的支持向量机多类分 类方法[J ]. 信息与控制 , 2004 , 33 (3) : 262 - 267. AN Jin1ong , WAN G Zhengou , MA Zhenping. A new SVM multiclass classification method [J ]. Information and Control , 2004 , 33 (3) : 262 - 267. [21 ]唐发明 , 王仲东 , 陈绵云. 支持向量机多类分类算法研 究[J ]. 控制与决策 , 2005 , 20 (7) : 746 - 749. TANG Faming , WANG Zhongdong , CHEN Mianyun. On multiclass classification methods for support vector machines [J ]. Control and Decision , 2005 , 20(7) : 746 - 749. [22 ]郑勇涛 , 刘玉树. 支持向量机多分类问题研究[J ]. 计 算机工程与应用 , 2005 , 41 (23) : 190 - 192. ZHEN G Yongtao , L IU Yushu. An analysis of multi2 class support vector machines[J ]. Computer Engineer2 ing and Applications , 2005 , 41 (23) : 190 - 192. [23 ]祁亨年. 支持向量机及其应用研究综述[J ]. 计算机工 程 , 2004 , 30 (10) : 6 - 9. QI Hengnian. Support vector machines and application research overview[J ]. Computer Engineering , 2005 , 41 (23) : 190 - 192. [ 24 ]宋晓宁 , 束 鑫. 一种改进的模糊支持向量机的人脸识 别方法[J ]. 微机发展 , 2005 , 15 (3) : 23 - 25. SONG Xiaoning , SHU Xin. An improved fuzzy support vector machine and its application to face recognition [J ]. Microcomputer Development , 2005 , 15 (3) : 23 - 25. [25 ]刘江华 , 程君实 , 陈佳品. 支持向量机训练算法综述 [J ]. 信息与控制 , 2002 , 31 (1) : 45 - 50. L IU J Ianghua , CHEN GJ unshi , CHEN Jiapin. Support vector machine traning algorithm : a review [J ]. Infor2 mation and Control , 2002 , 31 (1) : 45 - 50. [26 ]张学工. 关于统计学习理论与支持向量机[J ]. 自动化 学报 , 2000 , 26 (1) : 32 - 42. ZHAN G Xuegong. Introduction to statistical learning theory and support vector machines[J ]. Acta Automati2 ca Sinica , 2000 , 26 (1) : 32 - 42. 作者简介 : 赵春晖 ,男 ,1965 年生 ,博士 ,教授 , 博士生导师 ,主要研究方向为智能信息处 理技术、图像处理. 获省部级科技进步奖 5 项 ,发表论文 180 多篇 ,出版著作 3 部. E2mail :zhaochunhui @hrbeu. edu. cn. 陈万海 ,男 ,1963 年生 ,副教授 ,信号 与信息处理专业博士研究生 ,主要研究 方向为超光谱遥感图像处理技术 ,发表 论文 8 篇. 郭春燕 ,女 , 1984 年生 , 硕士研究 生 ,主要研究方向为超光谱遥感图像处 理技术、目标分类. 第 2 期 赵春晖 ,等 :多类支持向量机方法的研究现状与分析 · 71 ·