Fei Ben, Liu Jinbai
Department of Mathematics, Tongji University, Shanghai 200092, China.
IEEE Trans Neural Netw. 2006 May;17(3):696-704. doi: 10.1109/TNN.2006.872343.
We present a new architecture named Binary Tree of support vector machine (SVM), or BTS, in order to achieve high classification efficiency for multiclass problems. BTS and its enhanced version, c-BTS, decrease the number of binary classifiers to the greatest extent without increasing the complexity of the original problem. In the training phase, BTS has N - 1 binary classifiers in the best situation (N is the number of classes), while it has log4/3 ((N + 3)/4) binary tests on average when making a decision. At the same time the upper bound of convergence complexity is determined. The experiments in this paper indicate that maintaining comparable accuracy, BTS is much faster to be trained than other methods. Especially in classification, due to its Log complexity, it is much faster than directed acyclic graph SVM (DAGSVM) and ECOC in problems that have big class number.
为了实现多类问题的高分类效率，我们提出了一种名为支持向量机二叉树（SVM）或BTS的新架构。BTS及其增强版本c-BTS在不增加原始问题复杂度的情况下，最大程度地减少了二分类器的数量。在训练阶段，BTS在最佳情况下有N - 1个二分类器（N是类别数量），而在决策时平均有log4/3 ((N + 3)/4)次二分类测试。同时确定了收敛复杂度的上限。本文的实验表明，在保持相当准确率的情况下，BTS的训练速度比其他方法快得多。特别是在分类方面，由于其对数复杂度，在类别数量较大的问题中，它比有向无环图支持向量机（DAGSVM）和纠错输出码（ECOC）快得多。
