SVM的常用多分类算法概述
摘要：SVM方法是建立在统计学习理论基础上的机器学习方法，具有相对优良的分类性能，是一种非线性分类器。最初SVM是用以解决两类分类问题，不能直接用于多类分类，当前已经有许多算法将SVM推广到多类分类问题，其中最常用两类：OAA和OAO算法，本文主要介绍这两类常用的多分类算法。
关键词：SVM；多分类；最优化
自从90年代初V. Vapnik提出经典的支持向量机理论（SVM），由于其完整的理论框架和在实际应用中取得的很多好的效果，在模式识别、函数逼近和概率密度估计领域受到了广泛的重视。SVM方法是建立在统计学习理论基础上的机器学习方法，具有相对优良的分类性能。SVM是一种非线性分类器。它的基本思想是将输入空间中的样本通过某种非线性函数关系映射到一个特征空间中，使两类样本在此特征空间中线性可分，并寻找样本在此特征空间中的最优线性区分平面。它的几个主要优点是可以解决小样本情况下的机器学习问题，提高泛化性能，解决高维问题、非线性问题，可以避免神经网络结构选择和局部极小点问题。
1. SVM方法
若样本集Q={（x i，y i）|i=1,……,L}∈R d*{-1,+1}是线性可分的。则存在分类超平面w T x+b=0,x∈R d对样本集Q中任一（x i，y i）都满足：
在空间R d中样本x=（x1，…, x d）r到分类超平面的距离d=|w T*x+b|/||w||，其中
||w||= .
当存在x 使得w T x i+b=±1, 则图1中超平面的分类间隔
margin = 2/ ‖w ‖。
使分类间隔margin 最大的超平面即为最优分类超平面。寻找最优分类超平面的问题将转化为求如下一个二次规划问题:
minΦ( w) =1/2‖w ‖
满足约束条件：
y i ( w T x i + b) ≥1 , i = 1 ,2 , ?, L
采用Lagrange 乘子转换为一个对偶问题,形式如下:
满足约束条件:
0≤a i，i=1,……,L ）
其中a i为每一个样本对应的Lagrange 乘子, 根据Kuhn2Tucker 条件,这个优化的解必须满足:
a i (y i [w T x i +b]-1)=0,i=1,……,L
因此多数样本对应 a i将为0 ,少部分不为0 的a i对应的样本就是支持向量。最后得到分类判别函数为:
b*是分类的域值,可以通过两类中任意一对支持向量取中值求得。根据上述易知, 对于空间R d中任意样本x =( x1,……,x d)T ,当|f(x)|< 1 时, 表示此时x 在超平面的分类间隔内, |f(x)|越趋于0 ,则当前分类超平面对于x 的区分能力越差。而|f(x)|≥1 时x 能被超平面正确分类。对于线性不可分的问题, 可以通过引入松弛变量的方法推广最优分类超平面的概念, 更一般的方法是用满足Mercer
条件的核函数K(x1, x j), 就是通过一个非线性映射,在一个高维特征空间中给出一个最优分类超平面。
2. SVM多分类算法
多类分类问题可以形式化地表述为：给定属于k类的m个训练样本(x1，y1)，、．．，(x m，y m)，其中x∈R n，i=1．．．．，m，且y i∈{1，…..,k},要通过上述训练样本构造一个分类函数f,使对未知样本x进行分类时的错误概率(或者造成的损失)尽可能小。最初SVM是用以解决两类分类问题，不能直接用于多类分类，如何有效地将其推广到多类分类问题还是一个正在研究的问题。当前已经有许多算法将SVMs推广到多类分类问题，这些算法统称为“多类支持向量机”(Multi-category SupportVector Machines，M—SVMs)。它们可以大致分为两大类：
(1)通过某种方式构造一系列的两类分类器并将它们组合在一起来实现多类分类；
(2)将多个分类面的参数求解合并到一个最优化问题中，通过求解该最优化问题“一次性”地实现多类分类。
2.1 OAA算法（one-Agains-All decomposition）
用SVM解决多类分类问题最早的方法可能就是OAA SVMs(one-Agains-All)算法。该方法
依次用一个两类sVM分类器(后面简称分类器)将每一类与其它所有类别区分开来，得到k个分类函数。分类时将未知样本分类为具有最大分类函数值的那类。
此算法是对于K类问题构造K个两类分类器，第i个SVM用第i类中的训练样本作为正的训练样本，而将其它的样本作为负的训练样本．这个算法称one-Agains-All方法．最后的输出是两类分类器输出为最大的那一类(此时，两类分类器的判决函数不用取符号函数sgn)．这种方法的优点是，只需要训练K个两类分类支持向量机，故其所得到的分类函数的个数(K个)较少，其分类速度相对较快．这种方法的第一个缺点为每个分类器的训练都是将全部的样本作为训练样本，这样需要求解K个n个变量的二次规划问题，因为每个支持向量机的训练速度随着训练样本的数量的增加急剧减慢，因此，这种方法训练时间较长．第二个缺点是如果以两类分类器的输出取符号函数，则有可能存在测试样本同时属于多类或不属于任何一类的区域，
如图1(a)的阴影部分所示．如果最后的输出是两类分类器输出为最大的那一类(此时，两类分类器的判决函数不用取符号函数sgn)，则人为地将分类超平面偏转，如图1(b)所示，理想分类超平面如图1(C)所示．之所以发生这种情况的原因是因为分类器的输出是一个相对距离，同一分类器的输出具有可比性，而不同分类器由于其相对的标准不同，其输出不具有可比性．比
图1 one-Agains-All方法分类
如说，对于某测试样本x，第一个分类器的输出为d1(x)=3，第二个分类器的输出为d2(x)=1，按OAA方法，由于d1(x)> d2(x)，则此测试样本应当属于第一类．而此测试样本与分类超平面的实际距离为:
D1(x)= d1(x)*|| w1||,D1(x)= d2(x)*|| w2||,|| w1||,|| w2||分别为第一、二个分类超平面法向量的模，故d1(x)> d2(x)并不能代表D1(x)> D2(x)．如果以D1(x), D2(x)作为判断标准，在非线性情况下|| w1||,|| w2||是无法求出的，故D1(x), D2(x)是无法求得的。
2.2 OAO算法（one-Agains-one decomposition）
OAO方法是在每两类间训练一个分类器，因此对于一个k类问题，将有k(k一1)／2个分类函数。当对一个未知样本进行分类时，每个分类器都对其类别进行判断，并为相应的类别“投上一票”，最后得票最多的类别即作为该未知样本的类别。这种策略称为“投票法”。采用上述方法的多类SVMs，简称为OAO SVMs(One- Agains-One)算法。
OAO方法是由Knerr提出的，该算法在K类训练样本中构造所有可能的两类分类器，每类仅仅在K类中的2类训练样本上训练，结果共构造K(K一1)／2个分类器．我们称该方法为OAO(one一against一one)方法．组合这些两类分类器很自然地用到了投票法，得票最多(Max Wins)的类为新点所属的类．U．Krebel用该方法训练多类SVM取得了很好的结果．OAO方法的优点是：其训练速度较OAA要快．OAO方法的缺点是：
1)如果单个两类分类器不规范化，则整个K类分类器将趋向于过学习；
2)推广误差无界；
3)分类器的数目K(K一1)／2随类数K急剧增加，导致在决策时速度很慢。
由于在决策时，此方法采用了投票法，有可能存在多个类投票相同的情况，即有可能存在一个样本同时属于多个类的情况，而使得此方法无法进行很好的决策．如图2所示，阴影部分的样本在l、2、3类的投票均为1，从而无法决策此区域的点属于哪一类。
图2 One- Agains-One方法分类
第二类方法尽管看起来简洁，但是在最优化问题求解过程中的变量远远多于第一类方法，训练速度不及第一类方法，而且在分类精度上也不占优。当训练样本数非常大时，这一问题更加突出。