DAGSVM 多分类技术研究

沈 洋，戴月明

（江南大学物联网工程学院，无锡 214122）

1 引言

DAG-SVM（Directed Acyclic Graph-Support Vector Machine）是Platt 教授于1999年根据有向无环图（DAG）提出的另外一种基于SVM 的多类别分类器，它引入了OVO 分类器中利用每两个类别作为基础二类分类器的方法，保证了分类的准确率，而且采用了有向无环图结构，使得每次分类只需要k-1个分类器，大大提升了分类的效率。但是由于采用了层次结构，也保留了层次结构固有的的缺陷：误差累积，在上层的节点产生的错误会一直保留下来，因此，距离根节点越近的节点，对整个结构的分类结果影响越大。而DAG-SVM 的节点选取方式采用了随机的方式，这就使得最终的分类结果十分的不稳定。另外，由于采用了与一对一相同的训练方式，使得训练耗费的时间比较长，这都是需要改进的。

2 有向无环图支持向量机的原理

DAG-SVM 是一种以SVM 分类器作为基础分类器，以有向无环图作为拓扑结构的组合多类别分类器，它通过从全体类别集合中不断的删除不可能的类别，得到最终的结果。DAG-SVM 的具体分类过程如如图1所示，根节点a 表示当前类别集合为全体类别{1，2，3，4}，经过分类器1-vs-4作用后，节点走到第二层，由于排除了一个类别4，因此当前类别集合为{1，2，3}，经过分类器1-vs-2作用后，节点走到了第三层d{1，3}，再经过分类器1-vs-3作用后，走到最后的叶节点类别1，因此，类别1即为最终的结果。

图1 DAG-SVM拓扑图

3 有向无环图支持向量机的缺陷

DAGSVM 虽然通过特殊的层次结构[1]实现了分类速度的提升，但是也由于层次结构，使得它的准确率受到了一定的影响；另外，它在训练阶段使用了与一对一分类器同样的方式，导致了分类的时间过长，下面将对这两个问题进行详细介绍。

3.1 误差累积

所谓误差累积，是指高层次所造成的错误会一直保留到最后的叶子结点，不会随着层次的增加而消失，这是所有层次结构的缺陷。目前来说，克服误差累积有两种常用的方法：

（1）提高每个二分类器的准确率。因为我们在进行层次分类时，如果没有特殊的策略，那么每个二分类器最终被放置的位置是随机的，因此我们没办法针对特殊的二分类器进行一些提高准确率的操作，这时候我们只有将所有二分类器的性能都进行优化，使得所有的二分类器都有比较高的准确率，这样可以保证不管什么样地排列方式最终的效果都是不错的。

（2）优化节点的选择顺序。不管是有向无环图结构，还是树结构[2]，它们的特点都是从根结点向下进行深度搜索，这就使得节点越靠上，被使用的几率越大，例如，根节点每次分类都要被用到，使用率为1；而叶子结点只有最终归属该类别才会被使用到，（k 为类别总数）所以它的使用率为1/k。因此，我们只要对层次结构节点的选择顺序进行优化[3]，在那些经常被使用的位置上放置正确率比较高的二分类器就会使得整个的分类器模型具有不俗的分类效果。但是，传统的DAGSVM 恰恰对于节点的划分没有制定任何的规则，只是随意组合，这也导致了最终的结果高低不一。

3.2 训练时间过长

除了误差累积之外，DAG-SVM 的训练时间也需要改善，因为DAG-SVM 的基础分类器采用的是一对一分类器，这就使得每次都要训练k（k-1）/2个分类器，当类别数目较大时，耗费的时间就会很多。

经过实验证明：SVM 分类器针对全部样本训练一次所需要的时间为：

式中，v 是一个常数，它取决于SVM 分类器采用的是那种分类算法；m 代表当前样本的总数；c 也表示一个常数。OVR 模式由于训练每个分类器都要用到所有的样本，那么训练k 个分类器一共所耗费的时间为：

OVO 模式与DAG-SVM 模式训练时所采用的方式是一样的，即每两个类别训练一个分类器，每次训练用到2m/k 的样本，共需训练k（k-1）/2个分类器，所以它们所用的时间为：

如上所示，当我们的算法采用的是SMO 时，v 的值大约为2，此时公式（3）等于2cmv，也就是代表DAG-SVM 与OVO 训练所需的时间大约是2次SVM 单独训练的时间，与OVR 相比有很大的优势，但是还是不够，因为DAG-SVM 处理的对象是大规模数据，所以当类别数很多时，k（k-1）/2的分类器个数还是太过庞大。现在针对于DAGSVM的训练时间过长没有太好的解决方法，因为它独特的有向无环图结构只能使得分类器个数较多。

4 结束语

本文对于有向无环图支持向量机的原理进行了阐述，分析了它的优点，并针对它的两个缺陷进行了详细的介绍，而且说明了解决的方法。