·78· 智能系统学报 第3卷 据映射到高维空间，从而将原低维空间的线性不可 是一个不等式约束下二次函数极值问题，存在唯一 分问题转化为高维空间上的线性可分问题，然后在 解.且根据KKT条件，这个优化问题的解必须满 这个新空间中求取最优分类面 足： 支持向量机分类的目标就是根据结构风险最小 a(w[(w·x)+b1-1+)=0 化原则，构造一个目标函数，寻找一个满足分类要求 i=1,2,“,n 的最优超平面，即寻找最优线性判别函数.设{x}∈ 因此，对多数样本的a将为0，对分类问题不 R为两类的样本数据，∈(+1，·1}为相应的类 起什么作用，只有取值不为0的a对应的样本才 别标号，i=1,2,n.如果x属于第1类，则= 决定最终分类结果，这样的样本称之为支持向量，它 1;如果x,属于第2类，则=-1.线性判别函数的 们通常只是全体样本中的很少一部分 一般形式为g(y=w·x+b,相应的分类面为x· 求解上述问题后得到最终的判别函数为 x+b=0.为了使待分样本尽可能好地分开，要求分 f(signf oy.K(x+b. (5) 类间隔何表示为2/wW最大，这相当于使lwⅡ 最小.寻找最优分类面可转化为求解数学形式的优 根据∫()的结果来确定x属于哪一类 化问题，通常可分为3种情况1 2现有的多类支持向量机算法 1)线性可分问题 针对线性可分情况，问题的目标函数的数学形 目前对于多类分类问题，支持向量机的解决途 式为 径有2种23)：一种是通过构造多个两类SVM分类 min支kwP 器并将它们组合起来实现多类分类，将多类问题转 1) 化为两类分类问题，第2种是一次性解决多类分类 2)线性不可分问题. 问题，即把所有子分类器的参数直接放在一个最优 在处理线性不可分问题时，引人松弛变量￡， 化方程里同时优化，这种思想尽管看起来简洁，但在 i=1,2,,n和惩罚因子C,对错分样本进行条件控 最优化问题求解过程中的变量远远多于第1种，训 制.这样，式1)可重新描述为 练速度及分类精度也不占优势，因此目前多采用第 1种方法，文中介绍的这几种多类支持向量机都属 m2Jw,9=wP+c∑e 2 于第1种方法 s.t.y[w·x)+b1-1+e≥0， 2.11-ar SVM算法 e≥0，i=1,2,…n,C>0 2) I~xr(o ne-against-rest),SVM算法是解决多类 3)非线性可分问题. 分类问题的最早的方法，对于k(k2)类SVM分类 对于非线性情况，引人核函数(x)将原数据空 问题，把其中一类作为第1类，其余类视为另一类， 间的非线性问题转化为高维特征空间的线性问题， 自然地将k分类问题转化为k个两类分类问题，得 即把x替换为(x),其相应的内积x·x替换为 到k个两类分类器，分类时未知样本最后的输出是 K(x·x=rx)Tx,式2)变为 两类分类器输出为最大的那一类 2.21-x1SVM算法 mnJw,9=之IwF+c2。 I-ar1(one-against-one)SVM算法是在每两类 s.t.[(w·tx)+b1-1+￡≥0， 之间训练一个分类器，因此对于一个k类问题，训练 e≥0，i=1,2,,n,C>0. (3) 阶段共构造C个两类分类器，每个分类器是取任意 对于上述凸优化问题，可引入拉格朗日乘子a 2个类别的数据进行训练.在测试阶段可以采用不 (i=1,2,,d,根据目标函数及约束条件建立La 同的方式测试样本属于哪一类，最常用的一种方法 grange函数并将其转化为下面的对偶问题，即满足 是“最大投票法”，即每个两类分类器都对样本的类 约束条件 别进行判断，采用投票机制为其相应的类别“投上一 票”，最后得票最多的类别即是该未知样本的所属 Da,=0,0≤a≤C,1=1,2,n 类.因此，文中在此算法的基础上，提出了一种改进 对4求解下列函数的最大值 的多类支持向量机分类方法。 3二次分类的多类支持向量机 式中：a=[a4…an严.设此矩阵方程的解为a.这 支持向量机应用于实际植被的模式识别时，常 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net据映射到高维空间 ,从而将原低维空间的线性不可 分问题转化为高维空间上的线性可分问题 ,然后在 这个新空间中求取最优分类面. 支持向量机分类的目标就是根据结构风险最小 化原则 ,构造一个目标函数 ,寻找一个满足分类要求 的最优超平面 ,即寻找最优线性判别函数. 设{ xi} ∈ R D 为两类的样本数据 , yi ∈{ + 1 , - 1} 为相应的类 别标号 , i = 1 , 2 , …, n. 如果 xi 属于第 1 类 ,则 yi = 1 ;如果 xi 属于第 2 类 ,则 yi = - 1. 线性判别函数的 一般形式为 g ( x) = w ·x + b,相应的分类面为 x · x + b = 0. 为了使待分样本尽可能好地分开 ,要求分 类间隔(可表示为 2/ ‖w ‖) 最大 ,这相当于使 ‖w ‖ 最小. 寻找最优分类面可转化为求解数学形式的优 化问题 ,通常可分为 3 种情况[1 ] . 1) 线性可分问题. 针对线性可分情况 ,问题的目标函数的数学形 式为 min 1 2 ‖w ‖2 . (1) 2) 线性不可分问题. 在处理线性不可分问题时 , 引人松弛变量εi , i = 1 ,2 , …, n 和惩罚因子 C ,对错分样本进行条件控 制. 这样 ,式(1) 可重新描述为 min w, b,ε J (w,ε) = 1 2 ‖w ‖2 + C ∑ n i = 1 εi , s. t. yi[ (w ·xi) + b] - 1 +εi ≥0 , εi ≥0 , i = 1 ,2 , …, n , C > 0. (2) 3) 非线性可分问题. 对于非线性情况 ,引人核函数 <( x) 将原数据空 间的非线性问题转化为高维特征空间的线性问题 , 即把 xi 替换为 <( xi) ,其相应的内积 xi ·xi 替换为 K ( xi ·xi) = <( xi) T <( xi) ,式(2) 变为 min w , b,ε J (w,ε) = 1 2 ‖w ‖2 + C ∑ n i = 1 εi , s. t. yi[ (w ·<( xi) + b] - 1 +εi ≥0 , εi ≥0 , i = 1 ,2 , …, n , C > 0. (3) 对于上述凸优化问题 ,可引入拉格朗日乘子αi ( i = 1 ,2 , …, n) ,根据目标函数及约束条件建立 La2 grange 函数并将其转化为下面的对偶问题 ,即满足 约束条件 : ∑ n i =1 yαi i = 0 ,0 ≤αi ≤C, i = 1 ,2 , …, n. 对αi 求解下列函数的最大值 : Q(α) = ∑ n i = 1 αi - 1 2 ∑ n i , j =1 ααi j y i y j K ( xi ·xj) . (4) 式中 :α= [α1α2 …αn ] T . 设此矩阵方程的解为α3 i . 这 是一个不等式约束下二次函数极值问题 ,存在唯一 解. 且根据 KKT 条件 , 这个优化问题的解必须满 足 : αi ( yi[ (w ·<( xi) ) + b] - 1 +εi) = 0 , i = 1 ,2 , …, n. 因此 ,对多数样本的α3 i 将为 0 ,对分类问题不 起什么作用 ,只有取值不为 0 的α3 i 对应的样本才 决定最终分类结果 ,这样的样本称之为支持向量 ,它 们通常只是全体样本中的很少一部分. 求解上述问题后得到最终的判别函数为 f ( x) = sign{ ∑ n i =1 α3 i y i K ( xi , x) + b 3 } . (5) 根据 f ( x) 的结果来确定 x 属于哪一类. 2 现有的多类支持向量机算法 目前对于多类分类问题 ,支持向量机的解决途 径有 2 种[223 ] :一种是通过构造多个两类 SVM 分类 器并将它们组合起来实现多类分类 ,将多类问题转 化为两类分类问题 ;第 2 种是一次性解决多类分类 问题 ,即把所有子分类器的参数直接放在一个最优 化方程里同时优化 ,这种思想尽管看起来简洁 ,但在 最优化问题求解过程中的变量远远多于第 1 种 ,训 练速度及分类精度也不占优势 ,因此目前多采用第 1 种方法 ,文中介绍的这几种多类支持向量机都属 于第 1 种方法. 2. 1 12a2r SVM 算法 12a2r (one2against2rest) SVM 算法是解决多类 分类问题的最早的方法 ,对于 k ( k ≥2) 类 SVM 分类 问题 ,把其中一类作为第 1 类 ,其余类视为另一类 , 自然地将 k 分类问题转化为 k 个两类分类问题 ,得 到 k 个两类分类器 ,分类时未知样本最后的输出是 两类分类器输出为最大的那一类. 2. 2 12a21 SVM 算法 12a21 (one2against2one) SVM 算法是在每两类 之间训练一个分类器 ,因此对于一个 k 类问题 ,训练 阶段共构造 C 2 k 个两类分类器 ,每个分类器是取任意 2 个类别的数据进行训练. 在测试阶段可以采用不 同的方式测试样本属于哪一类 ,最常用的一种方法 是“最大投票法”,即每个两类分类器都对样本的类 别进行判断 ,采用投票机制为其相应的类别“投上一 票”,最后得票最多的类别即是该未知样本的所属 类. 因此 ,文中在此算法的基础上 ,提出了一种改进 的多类支持向量机分类方法. 3 二次分类的多类支持向量机 支持向量机应用于实际植被的模式识别时 ,常 · 87 · 智 能 系 统 学 报 第 3 卷