支持向量机多类分类算法新研究_余辉

２００８，４４（７）支持向量机［１，１９］是２０世纪９０年代中期在统计学习理论［２］基础上发展起来的一种新型机器学习方法。

它在解决小样本，非线性及高维模式识别问题上表现出许多其它机器学习方法不可比拟的优势。

支持向量机最初是针对二类分类问题提出的，但在实际应用中往往是多类分类问题，因此，将支持向量机推广到多类分类成为目前ＳＶＭ研究的热点问题之一。

到目前为止，已提出了许多解决多类分类问题的方法，如“一对一”方法［５，６］，“一对多”方法，ＤＡＧ方法［７］，纠错编码支持向量机［８］，二叉树支持向量机［９，１７］，Ｍ－ａｒｙ支持向量机［１１］和模糊支持向量机［１０，１５］等。

有一些学者对支持向量机多类分类方法进行了总结与分析，如台湾大学的Ｃｈｉｈ－Ｗｅｉ等［３］对“一对多”方法，“一对一”方法和ＤＡＧ方法进行了较详细的研究；刘志刚等人［１６］除了分析上述算法外，还增加了对纠错编码支持向量机和层次支持向量机的研究。

可以将目前已提出的支持向量机多类分类方法分为两类：一类是一次性求解方法，它实际是标准二次优化问题的推广；另一类是将多类问题转化为多个两类问题。

后一种方法无论从训练速度还是从分类精度考虑都优于前者，因此，目前主要的多类分类算法都是基于后一种方法提出的。

本文通过研究发现第二种支持向量机多类分类方法包含两个关键问题，一是分解策略，即如何将多类分类问题转化为多个两类问题；二是组合策略，即在构造出两类分类器后，如何将多个两类分类器进行组合实现多类分类。

这两个关键问题直接影响支持向量机多类分类器的分类性能。

本文首先分析对比了各种支持向量机多类分类方法的特点，并重点分析了各种方法是如何解决上述两个关键问题以及解决方法的优缺点。

另外，本文还通过实验对比分析了各种多类分类方法。

与其它支持向量机多类分类方法综述相比，本文的不同之处，一是提出了影响支持向量机多类分类器性能的两个关键问题，并进行了分析和实验论证；二是对Ｍ－ａｒｙ支持向量机和模糊支持向量机进行了分析和实验对比，目前还没有文献对这两种方法进行过实验分析。

１支持向量机的多类分类方法的对比分析支持向量机具有较好的分类性能，但它只能对两类样本进行分类，而实际应用中往往需对多个类别分类。

因而需要将ＳＶＭ推广到多类分类的问题中去，这些支持向量机多类分类算法基于两种方式：一种是将所有类别的样本组合在一起进行分类，称为一次性求解法；另一种是分解重构法，即将多类问题转化为多个两类问题，其中心思想是每次将工作集划分（或选支持向量机多类分类算法新研究余辉１，赵晖１，２ＹＵＨｕｉ１，ＺＨＡＯＨｕｉ１，２１．新疆大学信息科学与工程学院，乌鲁木齐８３００４６２．北京科技大学信息学院，北京１０００８３１．ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ，ＸｉｎｇｊｉｎａｇＵｎｉｖｅｒｓｉｔｙ，Ｕｒｕｍｑｉ８３００４６，Ｃｈｉｎａ２．ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙＢｅｉｊｉｎｇ，Ｂｅｉｊｉｎｇ１０００８３，ＣｈｉｎａＥ－ｍａｉｌ：ｙｕｈｕｉ＿０＠１６３．ｃｏｍＹＵＨｕｉ，ＺＨＡＯＨｕｉ．Ｎｅｗｒｅｓｅａｒｃｈｏｎｍｕｌｔｉ－ｃｌａｓｓｉｆｉｃａｔｉｏｎｂａｓｅｄｏｎＳｕｐｐｏｒｔＶｅｃｔｏｒＭａｃｈｉｎｅｓ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２００８，４４（７）：１８５－１８９．Ａｂｓｔｒａｃｔ：ＳｕｐｐｏｒｔＶｅｃｔｏｒＭａｃｈｉｎｅｓ（ＳＶＭｓ）ｉｓｏｒｉｇｉｎａｌｌｙｄｅｓｉｇｎｅｄｆｏｒｂｉｎａｒｙｃｌａｓｓｉｆｉｃａｔｉｏｎ．Ｈｏｗｔｏｅｘｔｅｎｄｉｔｆｏｒｍｕｌｔｉ－ｃａｔｅｇｏｒｙｃｌａｓｓｉｆｉｃａｔｉｏｎｉｓｏｎｅｏｆｈｏｔｒｅｓｅａｒｃｈｉｓｓｕｅｓ．ＴｈｉｓｐａｐｅｒｅｍｐｈａｓｉｚｅｓｏｎａｎａｌｙｚｉｎｇｄｅｃｏｍｐｏｓｉｎｇａｎｄｒｅｃｏｎｓｔｉｔｕｔｉｏｎｍｅｔｈｏｄｏｌｏｇｙｏｆＳＶＭｍｕｌｔｉ－ｃｌａｓｓｉｆｉｃａｔｉｏｎａｌｇｏｒｉｔｈｍｓ，ａｎｄｄｉｓｃｕｓｓｅｓｔｗｏｋｅｙｆａｃｔｏｒｓｗｈｉｃｈａｆｆｅｃｔｐｅｒｆｏｒｍａｎｃｅｓｏｆｃａｔｅｇｏｒｉｅｓｉｎｄｅｔａｉｌ：ｄｅｃｏｍｐｏｓｉｎｇｓｔｒａｔｅｇｙａｎｄｃｏｍｐｏｓｉｎｇｓｔｒａｔｅｇｙ．Ｔｈｅｐａｐｅｒｄｏｅｓｅｘｐｅｒｉｍｅｎｔｓｔｏｖａｌｉｄａｔｅａｕｔｈｏｒｓ’ｏｐｉｎｉｏｎｓａｎｄｔｈｅｎｃｏｍｐａｒｅｓａｌｌｋｉｎｄｓｏｆＳＶＭｍｕｌｔｉ－ｃａｔｅｇｏｒｙｃｌａｓｓｉｆｉｃａｔｉｏｎ，ｉｎｃｌｕｄｉｎｇＭ－ａｒｙＳＶＭｓａｎｄｆｕｚｚｙＳＶＭｓ．Ｋｅｙｗｏｒｄｓ：ＳｕｐｐｏｒｔＶｅｃｔｏｒＭａｃｈｉｎｅ；ｍｕｌｔｉ－ｃｌａｓｓｉｆｉｃａｔｉｏｎ；ｄｅｃｏｍｐｏｓｉｎｇａｎｄｒｅｃｏｎｓｔｉｔｕｔｉｏｎｍｅｔｈｏｄｏｌｏｇｙ摘要：支持向量机最初是针对两类分类问题提出的，如何将其推广至多类分类问题是当前ＳＶＭ研究中的热点问题之一。

主要针对支持向量机多类分类方法中的分解重构法进行了深入分析，详细讨论了影响分类器性能的两个关键因素：分解策略和组合策略，并通过实验验证了该观点。

最后，通过实验对比了包括Ｍ－ａｒｙ支持向量机和模糊支持向量机的ＳＶＭ多类分类方法。

关键词：支持向量机；多类分类；分解重构法文章编号：１００２－８３３１（２００８）０７－０１８５－０５文献标识码：Ａ中图分类号：ＴＰ３９１作者简介：余辉（１９８２－），男，硕士研究生，主要研究方向：人工智能、模式识别；赵晖（１９７２－），女，博士后，副教授，硕士研究生导师，主要研究方向：数据挖掘、人工智能、信息检索。

收稿日期：２００７－０６－１８修回日期：２００７－０９－１０ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用１８５ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用２００８，４４（７）取）不同的两个类别，在此基础上构造出支持向量机两类分类器，最后根据某一组合策略将分类器进行组合实现多类分类。

下面就对目前主要的ＳＶＭ多类分类算法作一介绍。

１．１一次性求解方法一次性求解方法是一种通过一个优化问题解决多类分类问题的方法。

实际是对标准ＳＶＭ中二次优化问题的一种推广。

该方法可表示为如下二次规划问题：ｍｉｎ!，ｂ，"１２ｎｍ＝１!（!ｍ・!ｍ）＋Ｃｌｉ＝１!ｍ≠ｙｉ!"ｍｉｓｔ．（!ｙｉ・!（ｘｉ））＋ｂｙｉ≥（!ｍ・!（ｘｉ））＋ｂｍ＋２－"ｎｉ"ｎｉ≥０，ｉ＝１，２，…，ｌｍ，ｙｉ∈｛１，２，…，ｎ｝于是可得到ｎ类ＳＶＭ分类器决策函数：ｆ（ｘ）＝ａｒｇｍａｘ［!ｉ・!（ｘ）＋ｂｉ］，ｉ＝１，２，…，ｎ从式中可以很容易看出一次性求解方法选择的目标函数十分复杂，计算复杂度高，不适于实际问题的应用。

因而，在解决多类问题时一般不使用该方法。

１．２“一对多”方法支持向量机多类分类最早使用的算法就是“一对多”方法。

该算法的分解策略是从工作集中挑出一类作为正类，剩下的所有类别作为负类，再对分好的两个集合训练构造出两类分类器，这样对于ｋ个类别共需构造ｋ个分类器。

在对未知样本进行测试时，“一对多”方法使用的组合策略是最大优选策略，即ｋ个ＳＶＭ对未知样本测试，共有ｋ个决策函数值，取决策函数输出值最大的类别为测试样本所属类别。

“一对多”方法在测试阶段只使用ｋ个分类器，其分类速度相对较快，但由于每次构造分类器都要将整个工作集作为训练样本，当工作集过大时，会影响训练速度。

“一对多”方法所采用的最大优选策略会产生多个最大值情况，这使得分类器会判断测试样本点同时属于多个类别或不属于任何一个类别，从而影响分类精度。

１．３“一对一”方法“一对一”方法的分解策略是每次从工作集的ｋ个类别中挑选出两个不同类别。

对这两类进行训练构造两类分类器。

这样共构造出ｋ（ｋ－１）／２个分类器。

在对未知样本进行测试时，“一对一”方法使用的组合策略是投票选举法。

ｋ（ｋ－１）／２个分类器分别对未知样本作出判决，将其所判断的类别投票数增加一，最终将得票最多的类别为未知样本所属的类。

“一对一”方法在训练过程中虽然构造ｋ（ｋ－１）／２个分类器，但每次训练样本只取工作集中的两类，训练速度比“一对多”方法快。

但是，如果单个两类分类器不规范化，会导致整个ｋ类分类器趋于过学习。

由于对未知样本作ｋ（ｋ－１）／２次决策，当类别数ｋ增加时就会影响分类速度。

决策阶段采用投票法，可能存在多个类的票数相同的情况，从而使未知样本同时属于多个类别，影响分类精度。

此外，“一对一”方法还有泛化误差无界的缺点。

１．４ＤＡＧ方法ＤＡＧ方法是由ｐｌａｔｔ在提出的决策导向循环图ＤＤＡＧ导出的，是针对“一对一”方法上的一些缺陷提出的。

ＤＡＧ方法在训练阶段的分解策略与“一对一”方法相同，但在分类阶段，它的组合策略是通过构造有向无环图实现多类分类的。

图中ｋ（ｋ－１）／２个节点（分类器）和ｋ个叶（输出的类别），对未知样本测试时，首先从顶部根节点开始，根据分类结果用下一层左节点或右节点继续分类，直至达到底层某个叶为止，该叶所表示的类为未知样本所属的类。

ＤＡＧ方法只需使用ｋ－１个决策函数就可以得出结果，分类速度较“一对多”方法和“一对一”方法快，而且不存在误分、拒分区域。

此外，由于分类的特殊结构，使其有一定的容错性，而且分类精度比一般的“二叉树”方法高。

但是，ＤＡＧ方法根节点选择不同，会使分类结果可能不同，导致结果的不确定性。

１．５“纠错编码”方法Ｄｉｅｔｔｅｒｉｃｈ提出对类别进行二进制编码将多类分类问题转化为多个两类分类问题。

“纠错编码”方法的分解策略是针对ｋ个类别的分类问题构造出一个ｋ行Ｌ列的矩阵，其中Ｌ是构造出的ＳＶＭ的个数。

矩阵的每一行都是一个长度为Ｌ的二进制编码，而每一列都只有０和１。

“纠错编码”方法就是将所有的０归为一类，而所有的１归为另一类。

这样就将多类问题转化为多个两类问题解决。

在分类阶段，当对未知样本作测试时所采用的组合策略是：Ｌ个ＳＶＭ分类器分类结果是一个二进制编码ｄ，计算出码本内ｋ个编码同ｄ的汉明距离，而距离最小的所代表的类别是未知样本所属类别。

“纠错编码”方法的训练速度较“一对多”方法有明显的改进，当类别数太大仅需少量的分类器，然而如何根据具体问题确定码本，选择排列顺序达最优的分类性能依然有待研究，而且分类效果错误码相关性也很大。

１．６“二叉树”方法“二叉树”方法是将支持向量机和二叉树相结合，以获得最优二叉树结构［１３］，它首先将所有类别划分成两个子类，再将子类进一步划分成两个次级子类，如此循环直至所有节点只包含一单独类别为止。