·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.net1 用多个两类分类器实现多类分类 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 卷