（应用数学专业论文）基于支持向量机的多分类方法研究.pdf

中文摘要 摘要 支持向量机是由a t & tb e l l 实验室的v a p n i k 等人提出的一种针对分类和回归 问题的新型机器学习方法，是借助于最优化方法解决机器学习问题的新工具支 持向量机方法基于统计学习理论与结构风险最小化原理，具有良好的推广性和较 高的准确率它集成了最优分类超平面、核技巧、凸二次规划等多项技术，能有效 地解决“过学习”、“维数灾难”和局部极小点等问题由于出色的学习性能， 支持向量机已经成为当前机器学习界的研究热点，并在很多领域得到了广泛的应 用，包括模式识别、回归估计等方面由于支持向量机方法最初是针对二类别的 分类问题提出的，如何将二类别分类方法扩展到多类别分类是支持向量机研究的 一个重要内容 本文主要做了以下个方面的工作： 1 对机器学习、统计学习理论以及支持向量机的发展和研究现状进行了介绍 对支持向量机的理论和算法进行了详细的介绍同时，还对核函数理论、参数选 择等热点问题进行了讨论 2 对支持向量机二分类问题的特征选择进行了研究提出了提高支持向量机 分类性能的特征选择方法，并通过实验验证了所提方法的有效性 3 总结了目前常用的基于支持向量机的多分类方法，包括一类对余类方法、 一类对一类方法、决策二叉树方法、决策导向无环图方法、纠错输出编码方法等 对比讨论了各种方法的优缺点针对决策二叉树支持向量机多分类方法存在的弊 端，综合考虑了类距离与类的分布对类间可分离性的影响，采用层次聚类方法建 立新的树结构，以提高多分类器的决策速度与准确率实验结果验证了所提方法的 有效性 关键词：统计学习理论；结构风险最小化；支持向量机；多分类 英文摘要 r e s e a r c ho fm u l t i c l a s sc l a s s i f i c a t i o nm e t h o d sb a s e d0 1 1s u p p o r t v e c t o rm a c h i n e a b s t r a c t s u p p o r tv e c t o rm a c h i n ei san o v e lm a c h i n el e a r n i n gm e t h o dp r o p o s e db yv a p n i k a n dh i sg r o u pa ta t & tb e l ll a b o r a t o r yf o rc l a s s i f i c a t i o na n dr e g r e s s i o nq u e s t i o n s i ti sa n e wt o o lt os o l v ep r o b l e m so fm a c h i n el e a r n i n gb a s e do no p t i m i z a t i o nt e c h n i q u e s u p p o r t v e c t o rm a c h i n eb a s e do ns t a t i s t i c a ll e a r n i n gt h e o r ya n ds t r u c t u r a lr i s k m i n i m 娩a t i o np r i n c i p l eh a sg o o de x t e n s i o na n db e t t e ra c c u r a c y i tc h a r a c t e r i z e db yt h e u s eo fo p t i m a lc l a s s i f i c a t i o nh y p e r p l a n e ，t e c h n i q u eo fk e r n e l sa n dc o n v e xq u a d r a t i c p r o g r a m m i n gc a n s o l v es o m ep r o b l e m ss u c ha so v e rs t u d y , d i m e n s i o nd i s a s t e ra n dl o c a l m i n i m i z a t i o ne f f e c t i v e l y s u p p o r tv e c t o rm a c h i n eh a sb e c a m er e s e a r c hh o t s p o tf o ri t s e x c e l l e n ts t u d y i n gp e r f o r m a n c ei nm a c h i n el e a r n i n gd o m a i n , a n di sw i d e l ya p p l i e di n m u c hr e g i o n ss u c ha sp a t t e r nr e c o g n i t i o n ，r e g r e s s i o ne s t i m a t i o na n ds oo n t r a d i t i o n a l s u p p o r tv e c t o rm a c h i n ei sd e v e l o p e df o rb i n a r yc l a s s i f i c a t i o np r o b l e m s h o wt oe x t e n d i tf o rm u l t i c l a s sc l a s s i f i c a t i o ni sas i g n i f i c a n ti s s u e i nt h i sp a p e r , t h em a i nw o r kr e s e a r c h e di sa sf o l l o w s ： 1 m a c h i n el e a r n i n g , s t a t i s t i c a ll e a r n i n gt h e o r y , t h ed e v e l o p m e n ta n dr e s e a r c h a c t u a l i t yo fs u p p o r tv e c t o rm a c h i n ea r ei n t r o d u c e d t h et h e o r ya n da l g o r i t h m o fs u p p o r t v e c t o rm a c h i n ea r ee x p o u n d e d a n dt h et h e o r yo fk e r n e lf u n c t i o n , p a r a m e t e r ss e l e c t i o n a n do t h e rh o t s p o ti s s u e sa r ed i s c u s s e ds i m u l t a n e o u s l y 2 f e a t u r es e l e c t i o no fs u p p o r tv e c t o rm a c h i n e0 1 1b i n a r yc l a s s i f i c a t i o ni s i n v e s t i g a t e d an e w f e a t u r es e l e c t i o nm e t h o do fi m p r o v i n gt h ep e r f o r m a n c eo fs u p p o r t v e c t o rm a c h i n ei sp r o p o s e d t h ev a l i d i t yo ft h em e t h o di sp r o v e db ye x p e r i m e n t s 3 c o m m o nm u l t i c l a s sc l a s s i f i c a t i o nm e t h o d si n c l u d i n go n ev e r s u sr e s t , o n e v e r s u so n e ，b i n a r yt r e e ，d e c i s i o nd i r e c t e da c y c l i cg r a p ha n de r r o rc o r r e c t i n go u t p u tc o d e a r es u m m a r i z e d t h ea d v a n t a g ea n dd i s a d v a n t a g eo ft h e s em e t h o d sa r ec o m p a r e d a i m i n ga tt h es h o r t c o m i n go fb i n a r yt r e es u p p o r tv e c t o rm a c h i n e , n e wb i n a r yt r e e sa r e e s t a b l i s h e dt oi m p r o v et h ed e c i s i o ns p e e da n dt h ea c c u r a c yo f m u l t i c l a s s i f i e rb a s e d0 1 1 英文摘要 t h ee f f e c to fd i s t r i b u t i o no fc l a s s e st oi n t e r - c l a s ss e p a r a b i l i t ya n dh i e r a r c h i c a lc l u s t e r i n g t h e e f f i c i e n c yo fi m p r o v e dm e t h o d sa r ep r o v e db yr e s u l t so fe x p e r i m e n t k e yw o r d s ：s t a t i s t i c a ll e a r n i n gt h e o r y ；s t r u c t u r a lr i s km i n i m i z a t i o n ；s u p p o m v e c t o rm a c h i n e ；m u l t i - c l a s sc l a s s i f i c a t i o n 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文= = 基王塞挂囱量扭数多盆粪左洼婴究：。除论文中已经注 明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确 方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发表或 未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：韵务刚1 聊锌驴7 日 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法，同意大连海事大学保留并向国家有关部门或机构送交学位 论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或 扫描等复制手段保存和汇编学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于： 保密口 不保密口( 请在以上方框内打“ ) 论文作者签名：务砌7导师签名：哆蠢之交 日期：础萨弓月猡f t 、 基丁：支持向量机的多分类方法研究 第1 章绪论 支持向量机【( s u p p o r tv e c t o rm a c h i n e ，s v m ) 是由a t tb e l l 实验室的 v a p n i k 等人提出的一种机器学习技术，它基于统计学习理论( s t a t i s t i c a ll e a r n i n g t h e o r y ) 1 7 , 8 1 ，是针对小样本分类和回归问题的新型机器学习方法支持向量机以 结构风险最小化原理( s t r u c t u r a lr i s km i n i m i z a t i o n ，s r m ) 7 , 8 1 为准则，能有效地解 决“过学习 、“维数灾难”和局部极小点等问题，具有良好的准确性与推广能 力目前，支持向量机已经成为机器学习领域的一个新的研究热点，在模式识别【3 1 、 回归估计【4 】等领域获得了出色的学习性能，并将在更多领域得到更为广泛的应用 支持向量机根据结构风险最小化原理，尽量提高学习机器的推广能力，使得 在有限的训练样本集上训练得到的学习机器在独立的测试集上仍能保持较小的误 差支持向量机具有以下特点： 1 以结构风险最小化原理为准则，在特征空间中构造最优分类超平面，保证 了学习机器具有良好的推广能力 2 应用核技巧，将输入空间中的非线性问题，通过非线性函数映射到高维特 征空间中，在高维空间中构造线性判别函数来实现原空间中的非线性判别函数i 在保证学习机器具有良好的推广能力的同时，巧妙地解决了“维数灾难”问题 3 专门针对小样本情况，所求的最优解是基于已有的样本信息，而不是样本 数趋于无穷大时的最优解 4 算法最终转化为一个凸二次规化问题，保证了解的全局最优性，避免了局 部极小点问题 5 基于统计学习理论，具有严格的理论基础 支持向量机作为一种新型机器学习方法，具有比较完善的理论基础，已经引 起人们的广泛关注，但它仍然存在一些亟待解决的问题，并且随着其应用领域的 不断扩大，其理论也有待进一步完善和发展 本文主要就支持向量机的一些理论与应用进行讨论和研究 第1 章绪论 1 1 支持向量机的发展历史与研究现状 1 1 1 支持向量机的发展历史 早在上世纪六十年代，v a p n i k 就开始了统计学习理论的研究，于上世纪六十 至七十年代建立了统计学习理论的基本理论框架 1 9 7 1 年，v a p n i k 和c h e o n e n k i s 【8 j 提出v c 维理论 1 9 8 2 年，v a p n i k t l 0 1 提出结构风险最小化原理 1 9 9 2 年，b o s c r ，g u y o n 和v a p n i k t l l 】提出最优边界分类器 1 9 9 5 年，v a p n i k 2 】等人提出支持向量机概念 1 9 9 7 年，v a p n i k ，g o l o w i e h 和s m o l a 1 2 】介绍了基于支持向量机方法的回归算 法和信号处理方法 由于支持向量机表现出的良好的准确性与推广能力，以及潜在的应用价值， 得到了众多学者的广泛关注，近年来出现了许多发展和改进的算法f 1 3 ，4 1 1 1 2 支持向量机的研究现状 支持向量机方法基于统计学习理论与结构风险最小化原理，具有较好的理论 基础，在一些领域的应用中表现出了良好的推广性能近年来，许多关于支持向 量机的研究，包括算法本身的改进和算法的实际应用，都陆续提了出来尽管支 持向量机算法的性能在许多实际问题的应用中得到验证，但是传统的支持向量机 算法在计算上存在着一些问题，包括训练算法速度慢、算法复杂而难以实现以及 检测阶段运算量大、支持向量机抗击噪音以及孤立点能力差及多类分类问题等等 1 提高支持向量机训练速度方面的研究 支持向量机的训练速度是限制它的应用的主要方面传统的利用标准二次优 化技术解决对偶问题的方法是训练算法慢的主要原因近年来，人们针对方法本 身的特点提出了许多算法来解决对偶寻优问题这些算法的一个共同思想就是循 环迭代：将原始问题分解为若干子问题，按某种迭代策略，通过求解子问题，最 终求得原始问题的最优解 1 9 9 5 年，c o r t e s 和v a p n i k 【2 1 提出块算法它的出发点是：删除矩阵中对应于 基于支持向量机的多分类方法研究 l a g r a n g e 乘子为零的行和列不会对最终结果产生影响因此，块算法的目标就是 通过某种迭代方式逐步排除非支持向量具体的作法是：选择一部分样本构成工 作样本集进行训练，剔除其中的非支持向量，并用训练结果对剩余样本进行检验， 将不符合训练结果( 一般是指违反k k t 条件) 的样本( 或其中的一部分) 与本次 结果的支持向量合并成为一个新的工作样本集，然后重新训练当支持向量的数 目远远小于训练样本数目时，块算法显然能够大大提高运算速度然而，如果支 持向量的数目本身就比较多，随着算法迭代次数的增多，工作样本集会越来越大， 算法依旧会变得十分复杂 1 9 9 7 年，o s l l i l a 【1 3 1 等人提出分解算法，后来j o a c h i m s 1 4 1 等人又对其进行了改 进分解算法的基本思想是：把问题分解成为固定样本数的子问题，即把工作样 本集的大小固定在算法速度可以容忍的限度内，迭代过程中只是将剩余样本中部 分“情况最糟 的样本与工作样本集中的样本进行等量交换，使支持向量的个数 不超过工作样本集的大小，也不改变工作集的规模，而只对支持向量中的一部分 进行优化 p l a t t e l 5 a 6 等人在分解算法的基础上提出顺序最小优化算法( s e q u e n t i a lm i n i m a l o p t i m i z a t i o n , s m o ) ，将工作样本集的规模减到最小( 两个样本) 之所以需要两 个样本是因为等式线性约束的存在使得同时至少有两个l a g r a n g e 乘子发生变化 由于只有两个变量，而且应用等式约束可以将其中一个用另一个表示出来，迭代 过程中每一步的子问题的最优解可以直接用解析的方法求出来这样，算法就避 开了复杂的数值求解优化问题的过程s m o 算法在速度方面表现出良好性能子 问题的规模和迭代的次数是一对矛盾，s m o 将工作样本集的规模减少到2 ，一个 直接的后果就是迭代次数增加所以s m o 实际上是将求解子问题的耗费转嫁到迭 代上，然后在迭代上寻求快速算法 2 支持向量机在多分类方面的研究 支持向量机最初是为两类分类问题而设计的，如何有效地将其应用到多分类 问题是当前支持向量机研究的一个重要方面【1 7 9 1 目前，构造s v m 多值分类器的 方法主要是通过组合多个二值子分类器来实现对多类分类器的构造常用的方法 第1 章绪论 有：一类对余类法【2 0 1 、一类对一类法【2 1 2 2 、决策二叉树法【2 3 。3 1 1 、决策导向无环图 法【3 2 1 、纠错输出编码法【3 3 3 4 】等 一类对余类法的思想为：对于k 类别的多分类问题，构造k 个分类器，第i 个 分类器用第i 类中的训练样本作为正的训练样本，而将其它的样本作为负的训练样 本最后的输出是两类分类器输出最大的那一类 一类对一类法的思想为：在k 类训练样本中构造所有可能的两类分类器，每 个分类器仅在k 个类别中的两类训练样本上训练，结果共构造k ( k 一1 ) 2 个分类器 组合这些两类分类器很自然地用到了投票法，得票最多的类为新点所属的类 决策二叉树法先将所有类别划分为两个子类，每个子类又划分为两个子子类， 以此类推，直到划分出最终类别每次划分后，两类分类问题的规模逐级下降 决策导向无环图法是：对于k 类别的多分类问题，该方法在训练阶段与一类 对一类法相同在决策阶段，使用从根节点开始的决策导向无环图，具有 k ( k 一1 ) 2 个内部节点以及k 个叶子节点，每个内部节点都是一个二类分类器，叶 子节点为最终的类别 纠错输出编码法是将x 个类别转化为个两类分类问题，从而每个类别对应一 个长为三的编码决策时，一个新样本对应一个长为的码字，与其汉明距离最小 的类即为该样本的类别 3 支持向量机在回归方面的研究与应用 支持向量机最初是为分类问题而设计的近些年来，支持向量机的回归算法 也得到了很多关注，其在应用方面也表现了极好的性斛4 ，5 ，3 ，3 5 州 占一不敏感损失函数由v a p n i k 8 】提出，在此基础上建立了g 一支持向量回归机 此后，s c h 6 1 k o p i f 4 】等提出了y 一支持向量回归机和支持向量机的分类算法相似， 支持向量机的回归算法最终也转化为一个求解凸二次规划问题，并且其二次规划 的规模为同样样本数量下分类问题的二倍因此，支持向量机回归同样面临着当 样本较多时计算量大，训练速度慢的缺点因此提高训练速度便成为支持向量机 回归研究的一个重要方面许多提高训练速度的改进算法也相继被提出，如块算 基丁支持向量机的多分类方法研究 法，分解算法，顺序最小优化算法等 目前，对支持向量回归算法的研究还远不如分类算法完整，有待进一步的研 究 1 2 本文的主要工作与全文结构 本文主要对支持向量机这种新型机器学习方法进行分析研究支持向量机本 身是针对二类别分类问题而提出，将其推广到多类别分类问题是支持向量机研究 的一个重点另外，提高支持向量机的训练与决策速度，同时保持较高的准确率 也是支持向量机研究所追求的一个目标进行合理的特征选择是提高支持向量机 性能的一个有效途径本文针对这些问题进行了探讨与研究 论文的结构安排如下： 本文第一章绪论，简要介绍了支持向量机的发展历史和研究现状第二章机 器学习与统计学习理论概述，对支持向量机的应用背景机器学习以及它的理 论基础统计学习理论进行了简要介绍第三章支持向量机，详细地介绍了支 持向量机的理论，并对支持向量机算法进行了详细的推导对核函数理论、参数 选择以及特征选择等热点问题进行了讨论将特征选择与支持向量机方法相结 合，改善了二分类问题的分类效率进行了基于标准数据集的仿真实验，对所提 方法的有效性进行了验证第四章基于支持向量机的多分类方法，对几种常用的 支持向量机多分类方法进行了分析与总结，讨论了各种方法的优缺点提出了针 对决策二叉树支持向量机多分类方法所存在弊端的改进算法，并通过仿真实验验 证了改进方法的有效性第五章为结论与展望 第2 章机器学习与统计学习理论概述 第2 章机器学习与统计学习理论概述 2 1 机器学习 人类智慧中一个很重要的方面是从实例中学习的能力：通过对已知的事实进 行分析，总结出规律，预测出不能直接观测的事实在这种学习中，重要的是掌 握规律，不但可以较好地解释已知的实例，而且能够对未来的现象或无法观测的 现象作出正确的预测与判断，这种能力叫做推广能力自上世纪中叶以来，由于 计算机的迅猛发展，人们在对机器智能的研究中，希望能够用计算机来模拟这种 学习能力，这就是基于数据的机器学习 2 1 1 机器学习问题的一般表示 机器学习的目的是：根据给定的训练样本，求对某系统输入输出之间依赖关 系的估计，使它能够对未知输出作出尽可能准确的预测其基本模型可由图2 1 表 示 i 输入x i j地i硼4 2 l ” - 礞测辅 一一警又耔t 耩一 图2 1 机器学习问题的基本模型 f i g 2 1e l e m e n t a r ym o d e lo f m a c h i n el e a r n i n g 图1 1 中：系统是研究对象，它在给定的输入工下得到输出y 变量y 与工存在 一定的未知依赖关系，即遵循某一未知的联合概率f ( x ，y ) 机器学习问题就是根 据力个独立同分布观测样本 ( 五，乃) ，( j r 2 ，儿) ，( ，只)( 2 1 ) 在一组函数矿( x ，国) 中求一个最优的函数f ( x ，) 对依赖关系进行估计，使期望风 险 基1 二支持向量机的多分类方法研究 尺( 讲) = i ( y ，f ( x ，) ) c z f ( 工，y ) ( 2 2 ) 最小其中，矿( 工，缈) 称作预测函数集，国为函数广义参数；l ( y ，f ( x ，) ) 为由于用 f ( x ，国) 对y 进行预测而造成的损失预测函数也称作学习模型或学习机器 有三类基本的机器学习问题，即模式识别、函数逼近和概率密度估计 对模式识别问题，输出y 是类别标号在两类情况下，j ， l ，一l ，预测函数称 作指示函数，损失函数可以定义为 c y ，c 工，缈，= 0 ：萋；二； 二l ： c 2 3 ， 使风险最小就是b a y e s 决策中使错误率最小 2 1 2 经验风险最小化 在上面的问题表述中，学习的目标在于使期望风险最小化但是，由于可以 利用的信息只有样本( 2 1 ) ，式( 2 2 ) 表示的期望风险并无法计算因此，传统的学习 方法中采用了所谓经验风险最小化( e m p i r i c a lr i s km i n i m i z a t i o n ，e r m ) 准则，即 用样本定义经验风险 ( 缈) = 工( 咒，厂( 而，国) ) ( 2 4 ) 作为对( 2 2 ) 式的估计，设计学习算法使它最小化对损失函数( 2 3 ) ，经验风险就是 训练样本错误率 事实上，用e r m 准则代替期望风险最小化并没有经过充分的理论论证，只是 直观上合理的想当然做法但这种思想却在多年的机器学习方法研究中占据了主 要地位人们多年来将大部分注意力集中到如何更好地最小化经验风险上而实 际上，即使可以假定当刀趋向于无穷大时( 2 4 ) 式趋近于( 2 2 ) 式，在很多问题中样本 数目也离无穷大相去甚远那么在有限样本下，由e r m 准则得到的结果能使真实 风险也较小吗? 第2 章机器学习与统计学习理论概述 2 j1 3 复杂性与推广能力 开始，很多注意力都集中在如何使似) 更小但很快就发现，训练误差小 并不总能导致好的预测效果某些情况下，训练误差过小反而会导致推广能力的 下降，即真实风险的增加，这就是“过学习”问题 之所以出现“过学习现象，一是因为样本不充分，二是学习机器设计不合 理这两个问题是相互关联的设想一个简单的例子【3 ，8 】：假设有一组实验样本 x ，j ， ，y 取值在【o ，1 1 2 f 司那么，不论样本是依据什么模型产生的，只要用函数 f ( x ，a ) = s i n ( a x ) 去拟合它们，总能够找到一个口使训练误差为零但显然得到的 “最优 函数并不能正确代表真实的函数模型究其原因，是试图用一个十分复 杂的模型去拟合有限的样本，导致丧失了推广能力 由此可看出，有限样本情况下： 1 经验风险最小并不一定意味着期望风险最, t j x ； 2 学习机器的复杂性不但应与所研究的系统有关，而且要和有限数目的样本 相适应 因此，需要找到一种理论，使得能够在小样本情况下建立有效的学习和推广 方法 2 2 统计学习理论的基本内容 统计学 - - jn 论【7 ，8 1 是一种专门研究小样本情况下机器学习规律的理论v a p n i k 等人从六、七十年代开始致力于此方面研究到九十年代中期，随着其理论的不 断发展和成熟，统计学习理论开始受到越来越广泛的重视其主要内容包括四个 方面： 1 关于统计推断一致性的充分必要条件的一系列概念； 2 在这些概念基础上的反映学习机器推广能力的界； 3 在这些界的基础上的针对小样本数的归纳推理原则； 4 实现这种新的推理的方法 其中，最有指导性的理论结果是推广性的界，与此相关的一个核心概念是v c 基于支持向量机的多分类方法研究 维 2 2 1v c 维 为了研究学习过程一致收敛的速度和推广性，统计学习理论定义了一系列有 关函数集学习性能的指标，其中最重要的是v a p n i k - c h e r v o n e n k i s 维( v c 维) 在 模式识别方法中，v c 维的直观定义是：对一个指示函数集，如果存在h 个样本能 够被函数集中的函数按所有可能的2 种形式分开，则称函数集能够把h 个样本打 散；函数集的v c 维就是它能打散的最大样本数目h 如图2 2 ，在二维实数空间 中，由定向直线构成的函数集能将平面上不在同一直线上的三个点的任意分布分 开，从而二维实数空间中线性实函数集的v c 维是3 若对任意数目的样本，函数 集都能将它们打散，则函数集的v c 维是无穷大 o l 。 。r 矽彳1 二 图2 2 二维平面上的3 个点被定向直线分开 f i g 2 2t h r p o i n t si nr 2 ，s h a t t e r e db yo r i e n t e dl i n e s v c 维反映了函数集的学习能力，v c 维越大则学习机器越复杂遗憾的是， 目前尚没有通用的关于任意函数集v c 维计算的理论，只对一些特殊的函数集知道 其v c 维比如，在疗维实数空间中，线性分类器和线性实函数集的v c 维是刀+ l ； 而对于上一节的例子，函数集f ( x ，口) = s i n ( 纵) 的v c 维则为无穷大对于给定的学 习函数集，如何( 用理论或实验的方法) 计算其v c 维是当前统计学习理论中有待 研究的一个问题 _一b一二 o 第2 章机器学习与统计学习理论概述 2 2 2 推广误差的界 统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之 间的关系，即推广性的界关于两类分类问题，结论是：对指示函数集中的所有 函数( 包括使经验风险最小的函数) ，经验风险( ) 和实际风险r ( 国) 之间以至 少1 一，7 的概率满足如下关系【7 ，8 】： r ( 功) 尽唧( ) + i ( h ( i n ( 2 n h ) + 1 ) - l n ( r l 4 ) ) n ( 2 5 ) 其中，j | i 是函数集的v c 维，刀是样本数 这一结论从理论上说明了学习机器的实际风险是由两部分组成的：一是经验 风险( 训练误差) ( 缈) ，另一部分称作置信范围，( h ( 1 n ( 2 n h ) + 1 ) - i n ( r 4 ) 1 ，它 v 、 ， ， 与学习机器的v c 维与训练样本数有关可以简单表示为： 尺( 柳( 缈) + ( 刀| i i )( 2 6 ) 其中，( 行| i i ) 为置信范围，它随训练样本数的增加而减小，随v c 维的增加 而增加这表明：在有限训练样本下，学习机器的v c 维越高( 复杂性越高) ，则 置信范围越大，导致真实风险与经验风险之间可能的差别越大，就会出现“过学 习 现象机器学习过程不但要使经验风险最小，还要使v c 维尽量小以缩小置信 范围，才能取得较小的实际风险，对未来样本有较好的推广性 2 2 3 结构风险最小化原理 由以上对推广性的界的讨论可知，e r m 原则在样本数有限时是不合理的，经 验风险和置信范围应该同时进行最小化在传统方法中，选择学习模型和算法的 过程就是调整置信范围的过程如果模型比较适合现有的训练样本，则可以取得 比较好的效果但因为缺乏理论指导，只能依赖先验知识和经验 统计学习理论提出了一种新的策略，称作结构风险最小化归纳原则( s t r u c t u r a l r i s km i n i m i z a t i o n , s r m ) ( 图2 3 ) f 7 潮s r m 原则定义了在对给定数据逼近的精度 和逼近函数的复杂性之间的一种折衷即把函数集构造为一个函数子集序列，使 基丁支持向量机的多分类方法研究 各个子集按照v c 维的大小排列；在每个子集中寻找最小经验风险，在子集问折衷 考虑经验风险和置信范围，取得实际风险的最小支持向量机方法实际上就是这 种思想的具体体现统计学习理论还给出了合理的函数子集结构应满足的条件及 在s r m 原则下实际风险收敛的性质 图2 3 结构风险最小化原理图 f i g 2 3s t r u c t u r a lr i s km i n i m i z a t i o n 第3 章支持向量机 第3 章支持向量机 3 1 支持向量机基本方法 支持向量机是近年来在机器学习领域中出现的新工具支持向量机以统计学 习理论为基础，有效地避免了经典学习方法中存在的“过学习 、“维数灾难” 以及局部极小点等问题，在小样本条件下仍然具有良好的推广能力因此，支持 向量机受到广泛的关注，已经成功应用于人脸识别【3 7 1 、文本分类2 7 , 3 8 , 3 9 1 目标识别【2 9 】 信誉率预测【删以及语音识别【4 1 1 等众多模式识别领域 支持向量机的理论最初来自于对数据分类问题的处理该方法的机理可以简 单地描述为一个数据二值分类问题：寻找一个满足分类要求的最优分类超平面 3 1 1 最优分类超平面 对于包含两个类别的分类问题，设训练数据 ( 而，乃) ，( x 2 ，儿) ，( 而，乃) ，x r n , y - 1 ，+ l ( 3 1 ) 可以被一个超平面分开即存在( 缈，b ) ，使 妒而+ 6 0 ，苎乃_ + 1 ( 3 2 ) 缈毛+ b 1 ，数据点落到分类 面的错误一侧 这样，就需要在目标函数中为分类误差分配一个额外的代价函数，即引入错 误惩罚分量所以，现在的目标函数变为： r a 础i 。n ，扣2 + c ( 善i 毒) ( 3 1 8 ) 第3 章支持向鼙机 s 工 ! 缈。毛+ 6 ) 1 一盏， ( 3 1 9 ) s f i j 【缶0 i = 1 ，2 ， 、 其中：c 0 是一个常数，它控制对错分样本的惩罚程度，控制机器的复杂性 和不可分离点数之间的平衡；c 越大表示对错误的惩罚越重这样，式( 3 1 8 ) 与结 构风险最小化原则完全吻合 使用l a g r a n g e 乘子方法，可以得到线性不可分模式对偶问题的表示如下： m 。a x 啦一寺q 吩咒乃( t - ) ( 3 2 0 ) l = il 。，刮【 妣j 善鹏- 0( 3 2 1 ) 【0 嘭c ，i = l ，2 ，7 其k k t 条件被定义为： 鼍唑缈妥+ 6 ) 。1 + 茧】_ 0， ( 3 2 2 ) l 磊( q c ) = 0 ， i = l ，2 ， 、7 从上面的介绍可以看出，线性不可分情况和线性可分情况的差别就在于可分 模式中的约束条件q o 在不可分模式中换为了更为严格的条件o q c 除了 这一修正，在线性不可分情况的约束最优化问题中，权值c o 和阈值b 的最优值的计 算都和线性可分情况中的过程是相同的线性可分情况的最优化问题可以视作一 种特殊性情形，包含在线性不可分的情况的最优化问题之中在式( 3 1 9 ) 和式 ( 3 2 2 ) 中对所有i 令毒= o ，即可得到相应的线性可分情况时的形式 3 1 3 非线性支持向量机 对于非线性的问题，支持向量机实现的是如下思想：通过某种事先选择的非 线性映射，将输入向量x 映射到一个高维特征空间中，然后在此高维空间中构建最 优分类超平面如图3 2 所示经过证明，可以得到如下结论【8 l ：如果选用适当的 映射函数，大多数在输入空间中的非线性问题在特征空间可以转化为线性问题来 解决 基于支持向量机的多分类方法研究 。熙照 图3 2 输入空间到高维特征空间的映射 f i g 3 2m a p p i n gf r o mo r i g i n a ls p a c et of e a t u r es p a c e 将输入x 作变换： ：r 4 专日 x ( x ) = ( 破( z ) ，唬( 石) ，谚( 石) ，) r( 3 2 3 ) 其中：是原始输入空间，日是高维特征空间，力( x ) 是实函数以特征向量 ( 工) 代替工，则得到特征空间日中的分类函数为： 一 i f ( ( x ) ) = s g n ( 缈( 工) + 6 ) = s g n ( 呸咒西( 五) ( 工) + 6 ) ( 3 2 4 ) 一般来说，在低维输入空间向高维特征空间映射过程中，空间维数急速增长， 使得在大多数情况下，在特征空间中直接计算最优分类超平面变得非常复杂支 持向量机通过采用核技巧，巧妙地将这一问题转化到输入空间中进行( 图3 3 ) 【7 朋， 其具体机理如下： 在上面的对偶问题中，目标函数和决策函数都只涉及到内积运算因此，可 以假设有非线性映射：彤_ h 将输入空间的样本映射到高维特征空间日中当 在特征空间中构造最优分类超平面时，训练算法仅使用特征空间中的点积，即 ( 而) ( 工，) 所以，若能找到一个函数置( ，) 使得k ( x ，工) = ( 功( 工) ，则在高维空 间中只需进行函数运算，而不必知道变换的具体形式此时的拉格朗日函数变 为： l ( c o , b ，口) ：昙8 彩 1 2 - 圭q 【乃( 彩西( 五) + 6 ) 一l 】 ( 3 2 5 ) 第3 章支持向量机 把上述问题转化为对偶问题即： 吁x 喜嘶一三毫q q y ，y j k c ， 求解上述问题后得到的最优分类函数是： ( 3 2 6 ) ，( x ) = s 乒 咒q k ( 毛，x ) + 6 ) ( 3 2 7 ) j ；i 式( 3 2 7 ) d p ，m 为支持向量的数目。由于最终判别函数中只包含支持向量的内 积以及求和，因此识别时的计算复杂度取决于支持向量的个数 图3 3 支持向量机示意图 f i g 3 3s u p p o r tv e c t o rm a c h i n e 3 1 4 支持向量机 根据是否引入核函数和是否引入惩罚参数，可将支持向量机分为四种：线性 可分支持向量机、线性不可分支持向量机、非线性可分支持向量机和非线性不可 分支持向量机它们之间的关系如图3 4 所示： 线扮可分支持向鹫机 忭小可分支持翻蜒 线性町分支掩向量 喾线性不可分支持囱鳝机 图3 4 四种支持向量机之间的关系 f i g 3 4r e l a t i o no ff o u rc a s e so fs u p p o r tv e c t o rm a c h i n e 基于支持向量机的多分类方法研究 下面给出应用最广泛的非线性不可分支持向量机( 支持向量机) 算法 算法3 1 ( 支持向量机) 【1 】： 步骤1 设已知训练集r = ( 五，舅) ，( x 2 ，y 2 ) ，( 再，乃) ) r ”y ，其中y = - 1 ，+ 1 ) ， f = l ，2 ，： 步骤2 选取适当的核函数k ( x ，x ) 和惩罚参数c ，构造并求解约束最优化问题 m 。i ni 1 己6 只以呸口，k ( 毛，x j ) 一口， ( 3 2 8 ) “ 二i = lj = lj - i 珐j 善鹏- 0( 3 2 9 ) 【0 q c ，i = l ，2 ，7 求得最优解矗= ( 西，西) r ； 步骤3 选取口的一个正分量o 吩 o 展开成 k ( u , v ) = 。( “) 哦( v ) 形式的充分必要条件是：对所有满足f 9 2 ( “) 如 o , c o ) 得到的支持向量机是一个两层感知器神经网络 ( 3 3 0 ) ( 3 3 1 ) ( 3 3 2 ) ( 3 3 3 ) ( 3 3 4 ) ( 3 3 5 ) ( 3 3 6 ) 基丁二支持向量机的多分类方法研究 3 3 参数选择 3 3 1 参数选择的意义 支持向量机的核心是结构风险最小化原则一方面对于确定v c 维的函数子 集，s v m 算法可以找到经验风险最小的函数；另一方面，对于给定的最小经验风 险，s v m 得到的决策函数还要使得置信范围最小，即能达到这个经验风险的最简 单的函数由于s r m 原则是针对特征空间的一个子空间而言的，不同子空间中数 据分布不同，经验风险随v c 维的变化与图2 3 不同，导致在不同子空间得到的最 优s v m 不同，这就是对s v m 核参数和误差惩罚参数同时进行优化的意义即除 了在同一子空间中优化惩罚参数c 以获得最优s v m 外，还要优化核参数以获得全 局最优的s v m 统计学习理论中发展了许多估计风险上界的方法，在每一种参数 的组合上均能求得对实际风险上界的估计，通过比较不同参数组合的风险上界， 就可以找到适合可用数据的最好的s v m 如图2 3 中的h 。处，s v m 的经验风险和 置信范围接近最佳的组合，既不会出现“过学习 现象，也不会出现“欠学习 现象，因而s v i 具有很好的推广能力 3 3 2 参数的作用与影响 惩罚参数c 实现在错分样本的比例和算法复杂度之间的折衷，即在确定的特 征子空间中调节学习机器的置信范围和经验风险的比例，使学习机器的推广能力 最好在确定的特征子空间中，c 的取值较小表示对经验误差的惩罚小，学习机 器的复杂度小而经验风险值较大；如果c 取，则所有的约束条件都必须满足， 这意味着训练样本必须要准确地分类每个特征子空间至少存在一个合适的c 使 得s v m 的推广能力最好当c 超过一定值时，s v m 的复杂度达到了特征子空间 允许的最大值，此时经验风险和推广能力几乎不再变化 s v m 的性能优劣还直接受核参数的影响因为核函数、映射函数以及特征空 间是一一对应的，确定了核函数，就隐含地确定了映射函数和特征空间核参数 的改变实际上是隐含地改变映射函数从而改变样本特征子空间分布的复杂程度 对于一个具体问题，如果核参数取值不合适，s v m 就无法达到预期的学习效果特 第3 章支持向量机 征子空间的维数决定了能在此空间构造的线性分类面的最大v c 维，也就决定了线 性分类面能达到的最小经验误差同时，每一个特征子空间对应唯一的推广能力 最好的分类超平面，如果特征子空间维数很高，则得