第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 ·