第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.net1) 训练阶段 : 第 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 ·