一种高准确度多分类结构选择方法*

陈青锋，秦 拯,何 流，陈 麟

(1.湖南大学信息科学与工程学院，湖南 长沙 410082;2.武汉大学国际软件学院，湖北 武汉 430079;3.湖南省气象技术装备中心，湖南 长沙 410007)

一种高准确度多分类结构选择方法*

陈青锋1，秦 拯1,何 流2，陈 麟3

(1.湖南大学信息科学与工程学院，湖南 长沙 410082;2.武汉大学国际软件学院，湖北 武汉 430079;3.湖南省气象技术装备中心，湖南 长沙 410007)

支持向量机SVM是目前最流行的二分类算法之一。现实生活中数据集大多要求能够进行多分类，而有向无环图DAG方法是将SVM应用扩展到多分类的用得最多的方式之一,它调用分类器次数较少，执行速度快，但是由于有错误向下累积和分类偏向性等情况存在，会影响DAG分类结果的准确度。在使用DAG-SVM的时候，对于k种类别有k！种不同的备选结构，根据数据集特性选择合适的DAG结构能够有效提高结果的准确度。提出使用估计准确度的方法，从备选结构中用穷举法选择出最高准确度估计值的DAG结构，以此作为测试集的结构进行分类。实验结果表明，相较其它方法，测试数据集采用该方法选择的DAG结构后的分类准确性得到显著提高，在对类别数量不太多的数据集进行多类分类时有较好的效果。

支持向量机；多分类；DAG-SVM；结构选择

1 引言

随着机器学习和数据挖掘等领域的发展，越来越多的复杂分类问题需要人们来处理，例如金融市场、天气预报等等都需要大量包含多个特征的互相关联的数据来进行正确地判断。需要正确的将这些数据分类才能用于实际问题的分析。针对不同的模型，有不同的分类器可以选择，现在较流行的有：Bayes分类器、BP神经网络分类器、决策树、支持向量机SVM(Support Vector Machine)算法等。

支持向量机[1]由Vapnik V N在1998年提出，是一种基于结构风险最小化的分类方法。由于其不会陷入局部极小值、对高维度的适应性强、且在统计样本量较少的情况下也能获得良好统计规律的特点，使得SVM倍受学者们的青睐，从而迅速地发展起来。文献[2]对支持向量机算法和相关理论进行了综述。SVM最初设定为一种二分类模型，基本模型定义为特征空间上间隔最大的线性分类器，而实际情况中经常需要针对多类进行分类，因此出现了一对一、一对其余、决策树和有向无环图DAG(Directed Acycline Graph)等SVM的扩展方法。文献[3，4]对主要的SVM多分类方法进行了研究，得出了一对一和DAG的方式分类精度较高，比其它的方式更适合实际应用的结论。

目前提出了有多种针对多类分类的SVM改进方法。Chen P等人[5]提出了一种基于二分决策图表和Huffman编码的DAG结构。易辉等人[6]提出了根据样本数据的空间分布来优化结构的方法。文献[7]从误分成本出发提出了一种对分类成本敏感的模型，降低了误分成本，使得即使出现一些误分结果也能把坏的影响降低到最小，但是没有提高准确度。文献[8]定义类的相似度为类别之间的距离，只对距离超过阈值的两个类别之间训练分类器，从而降低了需要训练的分类器个数，简化了DAG结构。蔡军等人[9]提出了一种改进的DAG拓扑结构构成的DAG-SVM多分类器，用于机器人的手势识别。

除了上述这些基于SVM的多分类学习方法之外，还提出很多其他多分类学习方法。Rokach L等人[10]提出了使用包含所有类别的最小子集集合覆盖问题的多分类估计算法；Jesse R等人[11]提出构造超类分隔区域并且以此训练分类器，将超类作为原始类来决定各个类别的归属；Ricardo N等人[12]给出使用固定大小内存处理实际上大小无限的序列的数据流应用的多分类标记的文本文件的方法；Nicolas R等人[13]给出了基于实例推论的MICBR系统，综合算法时间复杂度和准确度在现有方法中具有优势。Montanes E等人[14]提出增强的二叉树分类模型，有针对性地将配对的二分类器配置在二叉树的相应位置，从而提高多分类效率。

由于在前面已有的各个多分类方法中最终分类准确度受到目标数据集特性的影响较大，以及临场采用方法的随机性影响，分类结果准确性难以保持在较高的程度。本文提出基于DAG-SVM多分类结构准确度的估算方法，从备选结构中用穷举法逐一估算准确度，选择出最高准确度估计值的DAG结构作为结果。实验结果显示，本方法具有一定的可行性。

本文的结构如下：第2节介绍DAG-SVM及分类偏见问题；第3节介绍模型准确度计算方法与原则;第4节给出实验结果；最后一节给出结论。

2 基本概念

2.1 有向无环图支持向量机DAG-SVM

DAG方法最初是由Platt J C等人[15]提出的，DAG-SVM训练阶段采用一对一的方式，在判别阶段采用有向无环图方式，它的优点在于能够避免冗余决策、样本失衡及盲区问题，因此经常在多分类中被使用。但是，对于k类分类问题，使用DAG-SVM方法会存在k!种不同的结构，有可能导致不同的分类结果。因此，使用DAG-SVM时的关键在于如何根据需要选择合适的结构。

有向无环图支持向量机(DAG-SVM)是由Platt J C提出的决策导向的无环图DAG导出，是针对一对一SVM存在误分、拒分现象而提出的。该方案在训练阶段训练(k(k-1))/2个分类器，在预测阶段构造一个具有(k(k-1))/2个节点和k个叶子节点的有向无环图结构，图中每个普通节点代表一个SVM分类器，每个叶子表示一个类别。当对测试样本预测时，从根节点开始预测，根据结果选择下一层中的左节点和右节点继续预测，直到到达叶子节点，得出预测结果。

与一对一方法不同，DAG-SVM预测时一共只需要k-1步，比一对一的(k(k-1))/2步次数少，因此分类速度较快。但是，DAG-SVM作为层次型结构，若在分类的某个高层节点中出现错误，则在低层无法得到纠正，因此选择合适的DAG结构、提高DAG-SVM的准确度，是一个值得研究的问题。

2.2 DAG分类偏见问题

在DAG-SVM方法中，一个k类分类问题需要用到分布在有向无环图中k层的(k(k-1))/2个二分类器。在这个结构中，每个节点对应一个SVM分类器，第i层有i个分类器。令“ai-aj”表示一个针对类别ai和aj的分类器，则DAG-SVM第一层节点为“a1-ak”,第k-1层的节点为“a1-a2”,“a2-a3”,…,“ak-1-ak”且i层的第j个节点(i,j)为“aj-ak+j-i”。如图1所示。

Figure 1 DAG-SVM decision structure

测试样本可以经过k-1次分类后得到分类结果。但是，因为叶子节点ai(i=1，…，k)互相之间的位置可以变动，因此DAG-SVM的决策结构并不是唯一的，不同的结构可能导致不同的分类结果，称之为决策偏见[4,6]。

令A(a,i,j)为类别a使用分类器SVM(i,j)分类正确的概率，p为SVM二分类器准确度。给定如下定义：

则分类结果概率:

(1)

对于k=4，且样本空间类别为a1的情况，路径概率如图2所示，可以计算对于类别1、2、3、4的分类准确度。

R1=R4=p3

R2=A(2,1,4)*A(2,1,3)*p

R3=A(3,1,4)*A(3,2,4)*p

可见各个叶子节点之间存在分类偏见，使得不同位置分类的正确率一般情况下并不相同，在各类别分布不均的情况下，对总体的分类准确性有较大影响。因此，需要进行适当的结构选择，来平衡DAG的分类偏见，以获取更高的分类准确性。

Figure 2 Probability of the path when k=4,sample space type=a1

3 叶子节点正确率问题

3.1 DAG-SVM准确率计算

3.2 算法实现

步骤2读取路径矩阵中的数值temp[x][y]，然后比较i和当前m、n的值。若i不等于m和n中任一个，则E=E*A(i,m,n)，且若temp=0，m不变，则n=n-1。若temp=1,则m=m-1,n不变；若i=m且temp=0或者i=n且temp=1,则E=pE；若i=m且temp=1或者i=n且temp=1，则E=(1-p)E。无论属于哪种情况，temp读取的位置y=y+1。

4 实验

为了评估本方法的实际作用，采用UCI库中的数据集来进行实验，分别为Iris、Wine、Poker-hand、Glass、Vehicle、Segment和Letter。实验环境为PC机(CPU:I5-2520M,2.50 GHz,内存4.00 GB),比较对象使用Matlab工具箱LIBSVM提供的1-v-1、1-v-r、DAG算法和文献[17]中的MBSVM算法。MBSVM是一种通过提前避免为相似度低于规定阈值的两个类别训练分类器，从而降低了训练时间的方法。在这三个数据集中使用高精确化方案进行准确度估值处理，从所有结构中选出具有最高精确度的备选项，然后与1-v-1、1-v-r，原始DAG-SVM方案及MBSVM作准确性和运行时间的比较。

表1为各数据集的详细情况，其中Attributes为具有的属性个数，Instances是样本集总数，Training是样本集用于训练的样本数，Class是样本具有的类别个数。对于每个数据集，先产生相关类别数的全排列0-1矩阵，然后使用本文的方法计算加权准确度，选出最高的估计分类正确数情况下的DAG结构。

Table 1 Description of the dataset表1 数据集描述

表2和表3中的数据为测试集20次实验结果的平均值。从表2可以观察得到，对于实验中的七个数据集，本方法和其它的方法相比都能够提升分类结果的准确度。对于本身分类性能较好的数据集来说，分类结果会得到略微的提升，而对于本身分类性能较差的Glass和Vehicle两个数据集，使用Improved-DAG分类后对准确度的提升较大。

对于表3，总体上MBSVM由于需要训练的分类器比其它方案少，因此运行时间最快。而本方案需要在使用DAG-SVM方法前建立路径概率矩阵及进行遍历，因此比1-v-1、原始DAG和MBSVM方法耗时略多，比1-v-r方法速度要快。从类别数量看，类别数量较多的Letter数据集，可以看出实验时间消耗较其他方法明显要多，而同样为样本数较大的Poker-hand由于不同类别数仅有10个，所以由于构建路径矩阵所耗时的增加量相对于庞大的记录条数反而不明显，因此在类别数较少的数据集中，记录数即使很大也不会对Improved-DAG方法有较大影响，而如果类别数过多则本方法不适用。

Table 2 Accuracy result of the experiment表2 实验准确度结果 %

Table 3 Executing time of the experiment表3 实验时间结果 ms

实验结果显示，与其他三种方法相比，对于特性不同的七种实验数据集，在使用本文提出的Improved-DAG方法后准确度都得到了提升。对于本方法，最适合的应用场景是类别数较少且数据集规模较大的情况，此时对整体准确度的提升较大，且对时间的消耗增加不明显。

5 结束语

DAG-SVM是目前最常使用的SVM多分类策略之一。作为一种k层k！种结构的分类方法，它的性能则主要由对象数据集特性和本身的结构来决定。考虑到DAG-SVM的分类偏见问题，如何针对特定的需要来选择合适的DAG结构，是应用DAG-SVM时面对的主要问题。本文以提高分类准确率为目的，提出了一种新的DAG-SVM结构选择方法，通过计算DAG叶子节点的分类准确度来估计整体分类准确度，从而选择出最优DAG结构。在UCI库提供的七个数据集上的实验表明，采用此方法能够有效提升分类准确率，在准确度上领先于现有的其他结构选择方案。

虽然本方案已经被证明可行，但是仍有可改进之处：训练阶段需要生成类别相关个数的路径矩阵，耗时受到类别数影响，以及训练样本与测试样本数据直接的特征差异会对本方案的效果有一定影响。接下来的工作是优化路径矩阵的产生与遍历过程，减少训练过程的时间消耗，降低对训练样本结果的依赖性。

[1] Vapnik V N.Statistical learning theory[M].New York:Wiley,1998.

[2] Ding Shi-fei, Qi Bing-juan, Tan Hong-yan. An overview on theory and algorithm of support vector machines[J]. Journal of University of Electronic Science and Technology of China, 2011,40(11):2-10.(in Chinese)

[3] Hsu C W,Lin C J. A comparison of methods for multiclass support vector machines[J].IEEE Transactions on Neural Networks,2002,13(2):415-425.

[4] Abe S.Analysis of multiclass support vector machines[C]∥Proc of CIMCA,2003:385-396.

[5] Chen P, Liu S.An improved DAG-SVM for multi-class classification[C]∥Proc of the 5th International Conference on Natural Computation, 2009:460-462.

[6] Yi H,Song X, Jiang B, et al.Support vector machine based on nodes refined decision directed acyclic graph and its application to fault diagnosis[J].Acta Automatic Sinica,2010,36(3):427-432.

[7] Yi Hui, Song Xiao-feng, Jiang Bin. Structure selection for DAG-SVM based on misclassification cost minimization[J].International Journal of Innovative Computing, Information and Control,2011,7(2):5133-5143.

[8] Luckner M,Szyszko K.RBF ensemble based on reduction of DAG structure[C]∥Proc of the 2013 Federated Conference on Computer Science and Information Systems,2013:99-105.

[9] Cai Jun, Li Xiao-juan, Zhang Yi, et al. An improved DAGSVM hand gesture recognition approach and its application[J]. Control Engineering of China, 2013,41(5):957-959.(in Chinese)

[10] Rokach L,Schclar A,Itach E.Ensemble methods for multi-label classification[J].Expert Systems with Applications,2014,16(41):7507-7523.

[11] Jesse R,Concha B,Pedro L.Multi-dimensional classification with super-classes[J].IEEE Transactions on Knowledge and Data Engineering,2014,26(7):1720-1733.

[12] Ricardo N,Ilias F, Nello C.Efficient classification of multi-labeled text strems by clashing[J].Expert Systems with Application,2014,41(11):5431-5450.

[13] Nicolas R,Sancho-Asensio A,Golobardes E,et al.Multi-label classification based on analog reasoning[J].Expert Systems with Applications,2013,40(15):5924-5931.

[14] Montanes E,Barranquero J,Diez J,et al.Enhancing directed binary trees for multi-class classification[J].Information Sciences,2013,223:42-55.

[15] Platt J C, Cristianini N, Shawe-Taylor J. Large margin DAG’s for multiclass classification[C]∥Proc of Advances in Neural Information Processing Systems,2000:547-553.

[16] Huang Zhen-long, Zheng Jun,Hu Wen-xin. Text classification based on inter-class separability DAG-SVM[J]. Journal of East China Nornal University(Natural Science),2013(3):209-218.(in Chinese)

[17] Zhi Xia-yang, Yuan Hai-shao, Xiang Sun-zhang. Multiple birth support vector machine for multi-class classification[J].Neural Computer & Application,2013,22(1):153-161.

附中文参考文献：

[2] 丁世飞，齐丙娟，谭红艳.支持向量机理论与算法研究综述[J].电子科技大学学报,2011,40(1):2-10.

[9] 蔡军，李晓娟，张毅，等.一种改进的DAGSVM手势识别方法及其应用[J].控制工程,2013,41(5):957-959.

[16] 黄振龙，郑骏，胡文心.基于类间可分性DAG-SVM的文本分类[J].华东师范大学学报(自然科学版),2013(3):209-218.

陈青锋(1988-),男，湖南长沙人，硕士生，研究方向为机器学习。E-mail:654603923@qq.com

CHEN Qing-feng,born in 1988,MS candidate,his research interest includes machine learning.

秦拯(1969-),男,湖南长沙人，博士，教授，研究方向为网络与信息安全、大数据处理和云计算。E-mail:zqin@hnu.edu.cn

QIN Zheng,born in 1969,PhD,professor,his research interests include network and information security，big data processing，and cloud computing.

A highly accurate structure selection method for multi-class classification

CHEN Qing-feng1,QIN Zheng1,HE Liu2,CHEN Lin3

(1.School of Information Science and Engineering,Hunan University,Changsha 410082;2.International School of Software,Wuhan University,Wuhan 430079;3.Hunan Meteorological Equipment Center,Changsha 410007,China)

Support vector machine is one of the most popular binary classification algorithms,but data sets in the real world require multi-classification. Directed Acycline Graph (DAG) is one of the most used ways that expand SVM to support multi-class classification.DAG calls the classifiers less frequently and works faster than other methods.However,the accumulated mistakes cannot be cleared, and it has k! kinds of decision structures when dealing with k-class problems.Therefore structure selection becomes a key problem while using DAG-SVMs.In this paper we propose a highly accurate DAG structure selection method that uses the classificatory percentage in the training data sets to estimate the accuracy of the test data sets, and chooses the DAG structure with the highest accuracy. Experimental results show that compared with other methods,the proposed method can improve the classification accuracy of test data set dramatically and has a better effect in performing multi-class classification of the data sets without too many different types.

support vector machine;multi-classification;DAG-SVM;structure selection

1007-130X(2015)09-1777-06

2014-09-30;

2014-12-29基金项目：国家自然科学基金资助项目(61472131,61272546)

TP181

A

10.3969/j.issn.1007-130X.2015.09.029

通信地址：410082 湖南省长沙市湖南大学信息科学与工程学院

Address:School of Information Science and Engineering,Hunan University,Changsha 410082,Hunan,P.R.China