（系统工程专业论文）基于支持向量机的数据挖掘方法.pdf

山东大学硕士学位论文 摘要 支持向量机是基于统计学习理论的新一代机器学习技术。由于使用结构风 险最小化原则代替经验风险最小化原则，使它能较好地处理小样本情况下的学 习问题。又由于采用了核函数思想，使它能把非线性问题转化为线性问题来解 决并降低了算法的复杂度。目前，支持向量机已经成为国际上机器学习领域新 的研究热点。 本论文首先概要介绍了支持向量机的理论背景，结合目前一些主要的支持 向量机方法进行深入研究，提出新的见解。本论文的主要贡献可归纳为如下三 个方面： 1 样本预优算法研究 论文首先介绍了一种可以减少大规模支持向量机训练时间和能减少野 点影响的方法。很多支持向量机的算法都是从一个随机的训练数据的子集 出发开始训练，本论文提出一种新的方法，在高维空间中估计出那些可能 最终成为支持向量的向量集合，继而加速优化的过程同时利用高维空间 定义的距离来发现野点，并在一定程度上消除野点对最终分类面的影响 2 提出高维中心支持向量机( n c s v m ) 方法 支持向量机利用少量数据来建立分类决策面。但是由于分类面只依赖于 少量的支持向量，所以易受噪声数据影响。针对这种情况，本文提出了高 维中心支持向量机( h c s v m ) 方法。该方法利用非线性可分数据映射到高维 线性可分的特性，把数据映射到高维特征空间，将高维中心之间的距离最 小作为优化的原问题。仿真实验表明，该方法在一定程度上减少了噪声数 据对分类面的影响 3 增量算法研究 增量算法已经成为智能知识发现方面一个重要的分类方法。在第五章 中，笔者深入分析了支持向量集的特性，介绍了一般的增量学习算法。通 过分析，指出在增量学习中确定学习参数比较困难，所以本文利用v s v m 第1 页 方法提出一种支持向量机的增量学习策略，可以自动的调整增量训练参数。 同时研究发现可能由于数据分布的不同，下一批数据的经验误差远大于原 来的支持向量的，导致原有的支持向量在增量学习中对最终的分类结果影 响很小，所以在新的训练过程中要加大对原有支持向量的惩罚，以提高最 终分离器的精度。最后我们给出了此方法的原始优化问题、拉格朗日函数 和对偶问题。 文章的最后，笔者总结全文，指出了有待于进一步解决的问题，并对支持 向量机理论的发展前景做出了展望。 关键词：支持向量机；模式分类；增量算法；统计学习理论；邻域算法 第n 页 山东大学硕士学位论文 a b s t r a e t b yu s i n gt h es t a t i s t i c a ll e a r n i n gt h e o r y , s u p p o r tv e c t o rm a c h i n e ( s v m ) i s t h o u g h to f an e wg e n e r a t i o no f l e a r n i n gm a c h i n e t h em a i na d v a n t a g eo fs v m i st h a t i tc a ns e r v eb e t t e ri nt h ep r o c e s s i n go fs m a l l s a m p l el e a r n i n gp r o b l e m sb yt h e r e p l a c e m e n to fe x p e r i e n t i a l 黜s km i n i m i z a t i o nb ys t r u c t u r a l 鼬s km i n i m i z a t i o n m o r e o v e r , s v mc a nl t e a tan o n l i n e a rl e a r n i n gp r o b l e ma sal i n e a rl e a r n i n gp r o b l e m s i n c ei tm a p st h eo r i g i n a ld a t at ot h ek e r n e ls p a c ei nw h i c hw eo n l ys o l v et h el i n e a r p r o b l e m s t h es t u d yo fs u p p o r tv e c t o rm a c h i n ei sb e c o m i n gan e wh o t s p o ti nt h e f i e l do f m a c h i n el e a r n i n g t h ep a p e rf i r s tr e v i e w st h ep r i n c i p l e so fs v m , a n dt h e ni n t r o d u c e ss o m e i m p o r t a n ta n dn e w e s tl e a r n i n ga l g o r i t h m s f o rs o m ep r o b l e m so fs v m ，t h em a i n c o n t r i b u t i o no f t h i sp a p e rl i e si nt h r e ea s p e c t sa sb e l o w ： 1 o p t i m i z et h ep r e p r o c e s so f s v m f i r s t , t h i sp a p e ri n 打o d u c e sam e t h o dt od e c r e a s et h et r a i n i n gt i m eo fl a r g e s c a l es u p p o r tv e c t o rm a c h i n e sa n dr e d u c et h ei n f l u e n c eo fo u t l i n e r s m a n y s u p p o r tv e c t o rm a c h i n e sa l g o r i t h m sn o r m a l l ys t a r tw i t har a n d o ms u b s e t t h e n , am e t h o di sp r o p o s e dt h a tt r yt of i n dab e t t e rt h a nar a n d o ms t a r t i n gs u b s e t ，a n d t h e r e f o r ea c c e l e r a t et h eo p t i m i z a t i o np r o c e s s i te s t i m a t e sw h i c ht r a i n i n gv e c t o r s a r el i k e l yt ob es u p p o r tv e c t o r si nt h eh i g hd i m e n s i o n a lp r o j e c t e ds p a c eo ft h e s v m t h em e t h o di su s e dt of i n do u t l i n e r s ，a n dt oe l i m i n a t et h ei n f l u e n c eo f t h e o u t l i n e r s 2 h i g hd i m e n s i o n a lc e n t e rs u p p o r tv e c t o r s u p p o r tv e c t o rm a c h i n eb u i l d st h eo p t i m a lc l a s s i f i c a t i o nf u n c t i o no n as m a l l p a r to ft h et r a i n i n gs a m p l e s ，t h es u p p o r tv e c t o r s b e c a u s ea l lt h ei n f o r m a t i o n a b o u tc l a s s i f i c a t i o no n l yc a nb er e p r e s e n t e db yt h es u p p o r tv e c t o r s ，s v m b e c o m e ss e n s i t i v et on o i s e so ro u f l i n e r si nt h et r a i n i n gs e t f o rt h i sr e a s o n , a n e wm e t h o d ，h i g hd i m e n s i o n a lc e n t e rs u p p o r tv e c t o r ( h c s v m ) ，i s p r e s e n t e d ， w h i c ht a k e st h ed i s t a n c e sb e t w e e nc e n t e r so fh i g l l l yd i m e n s i o n a ld a t aa st h e o r i g i n a lo p t i m i z a t i o np r o b l e mb yu s i n gt h ep r o p e r t yo fm a p p i n gn o n l i n e a r l y s e p a r a b l ed a t at ol i n e a r l ys e p a r a b l ed a t aw i t hh i g hd i m e n s i o n s i m u l a t i o nr e s u l t s 第页 山东大学硕士学位论文 d e m o n s t r a t et h a tt h em a c h i n e sa r ci e s ss e n s i t i v et on o i s e so ro u t l i n e r sa n dc a n d e a lw i t hn o n l i n e a rp r o b l e m i n c r e m e n t a ls v m l e a r n i n g t h ei n c r e m e n t a ld a t ac l a s s i f i c a t i o nm e t h o dh a sb e e no n eo ft h ek e y t e c h n o l o g i e so fi n t e l l i g e n tk n o w l e d g ed i s c o v e r i n g h o w e v e r , i t sp a r a m e t e r sa g e v e r yd i f f i c u l tt od e t e r m i n e s ow ei n t r o d u c ean e wm e t h o dt h a tu s ev s v mt o a d j u s tt h ep a r a m e t e ra u t o m a t i c a l l y t h eo l ds u p p o r tv e c t o r sh a v el i u l ei n f l u e n c e t ot h er e s u l tb e c a u s et h ee m p i r i c a le r r o ro nt h es e c o n db a t c h d r a s t i c a l l y o u t w e i g h st h ee r r o ro nt h eo l ds v s t om a k eu pf o r t h ep r o b l e mi nt h e i n c r e m e n t a ll e a r n i n ga l g o r i t h m , w em a k ea ne r r o ro nt h eo l ds u p p o r tv e c t o r s ( w h i c hr e p r e s e n tt h eo l dl e a r n i n gs e om o r ec o s t l yt h a na l le r r o ro i lan e w e x a m p l e t h i sm e t h o dc a ni m p r o v ed e g r e eo fa c c u r a c y f i n a l l yw ep r e s e n tt h e o r i g i n a lo p t i m i z a t i o np r o b l e m ，t h el a g r a n g ef u n c t i o na n dt h ed u a ll a g r a n g e f u n c t i o n i nt h ef i n a l ，t h es u m m a r i z a t i o ni sp r e s e n t e da n ds o m e p r o b l e m st ob es o l v e da n d t h ep r o s p e c to fs u p p o r tv e c t o r sm a c h i n e sa r ep o i n t e do u t k e ，w o r d s ：s u p p o r tv e c t o rm a c h i n e ；p a t t e r nr e c o g n i t i o n ；i n c r e m e n t a la l g o r i t h m ； s t a t i s t i c a ll e a r n i n gt h e o r y ；n e i g h b o r h o o da l g o r i t h m 第1 v 页 附件一： 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：壶幽：日期：丝! 互i 翻! 目 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：趔：导师签名，趣日期：塑牡 山东大学硕士学位论文 第一章绪论 1 1 课题背景 数据挖掘( d a t am i n i n g ，简称d m ) 是知识发现( k n o w l e d g ed i s c o v e r y i nd a t a b a s e ，简称k d d ) 的核心环节，就是从大量的、不完全的、有噪 声的，模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、 但又是潜在有用的信息和知识的过程。它是涉及机器学习、模式识别、 统计学、人工智能、数据库管理及数据可视化等学科的边缘学科。用统 计的观点看，它可以看成是通过计算机对大量的复杂数据集的自动探索 性分析。数据挖掘面对的是经初步加工的数据，更专注于知识发现。近 年来出现的数据挖掘技术之所以被认为具有令人兴奋的研究前景，是因 为它能够获得广泛的应用，如用于关键性决策，重要策略的制定等。海 量数据的出现，对数据挖掘应用形成极大的需求，使这一技术迅速得到 发展和完善其中分类技术作为数据挖掘技术重要的一个方面一直备受 研究者的关注 分类方法可以根据下面的评判标准来研究i l 】； 预测的准确率：涉及模型正确的预测新的或者先前未见过的数据的 类标号的能力。 速度：涉及产生和使用模型的计算花费。 强壮性：涉及给定噪声数据或者具有空缺值的数据，模型正确预测 的能力。 可伸缩性：涉及给定大量数据，有效地构造模型的能力。 可解释性：涉及学习模型提供的理解和洞察的层次 在研究分类算法过程中产生了很多好的解决的方法，其中本论文中 重点研究的支持向量机方法就是其中一个有效的分类方法本论文对于 支持向量机方法在分类的准确率以及强壮性等方面提出了改进 本章简要概述数据挖掘的任务和方法，然后指出支持向量机方法的 优点，并和神经网络分类方法作了简单的比较，在总体上表明了支持向 量机方法在数据挖掘分类方法中的地位。 第1 页 山东大学硕士学位论文 1 2 数据挖掘的任务 根据发现知识的不同，我们可以将数据挖掘任务归纳为以下几类1 1 1 ： ( 1 ) 概念描述 一个概念常常是对一个包含大量数据集合总体情况的概述。利用定 性和对比的方法从与学习任务相关的一组数据中提取出关于这些数据 的特征式，这些特征式表达了该数据集的总体特征。 ( 2 ) 分类 分类是用一个函数把各个数据项映射到某个预定义的类，或者说是 得出关于该类数据的描述或模型。数据分类方法有决策树分类方法、统 计方法、神经网络方法、粗集方法、支持向量机方法等。例如，利用当 前病历数据可以建立各种疾病的分类规则，对于新来的病人根据其症状 及分类规则就可以推断病人所患病的种类。 ( 3 ) 关联性分析 关联性分析用来发现一组项目之间的关联关系和相关关系。它们经 常被表达为规则形式。一条形如x + y 的关联规则可以解释为：满足x 的数据库元组也很可能会满足y 。关联性分析广泛应用于交易数据分 析，通过分析结果来指导销售、目录设计及其它市场决策的制定。 ( 4 ) 聚类分析 聚类是一种常见的描述工作，搜索并识别一个有限的种类集合或簇 集合，从而描述数据。简单地说，就是识别出一组聚类规则，将数据分 成若干类。这些种类可能相互排斥而且是穷举的，或者包含了更丰富的 表达形式，例如层次的种类或重叠的种类。经过分类后的数据，实现在 各类之间其相似程度最小，而在同一类内部，其数据的相似性则最大。 聚类分析与分类分析方法明显的不同在于，后者所学习获取分类预 测模型所使用的数据是已知类别归属，属于有教师监督学习方法，而聚 类分析所分析的数据是无类别归属的。 ( 5 ) 预测分析 通过对数据的分析处理，估计一组数据中的某些丢失数据的可能值 或一个数据集合中某种属性值的分布情况一般是利用数理统计的方 法，找出与所要预测的属性值，并根据相似数据的分析估算属性值的分 第2 负 山东大学硕士学位论文 布情况 1 3 数据挖掘常用方法 从统计分析类的角度来说，统计分析技术中使用的数据挖掘方法有 线性分析和非线性分析、回归分析、逻辑回归分析、单变量分析、多变 量分析、时间序列分析、最近邻算法和聚类分析等方法。利用这些技术 可以检查那些异常的数据，然后，利用各种统计模型和数学模型解释这 些数据，解释隐藏在这些数据背后的市场规律和商业机会。知识发现类 数据挖掘技术是一种与统计分析类数据挖掘技术完全不同的挖掘技术， 包括人工神经元网络、支持向量机、决策树、遗传算法、粗糙集、概念 描述和关联规则等。下面就叙述几个数据挖掘中常用的分类和聚类算法 【2 1 ，可以从中简单比较出支持向量机方法和其他方法的异同。 ( 1 ) k m e a n 算法 k m e a n 算法用于数据挖掘中的聚类，它是以k 为参数，把f 个对象 分为k 个簇，在同簇内相似度较高，在不同簇之间的相似度较低，每个 簇用该簇中对象的平均值来表示这个算法尝试找出使平方误差函数最 小的k 个划分，当结果集是密集，簇与簇之间的区别明显时，效果很好。 k m e a n 算法的特点在于处理大数据集时，该算法具有可伸缩性和比较 高的效率。 ( 2 ) a p r i o r i 算法 a p r i o r i 算法用于数据挖掘中的关联规则，是一种最有影响的挖掘 布尔关联规则频繁项集的算法算法使用频繁项集性质的先验知识，通 过逐层搜索的迭代方法，k 项集用于探索k + l 项集。其过程为首先找出 频繁l 项集的集合l l ，再根据l 项集找出频繁2 项集的集合l 2 ，l 2 再 用于寻找l 3 ，如此迭代，直到不能找到频繁k 项集为止，然后在频繁项 集的基础上生成规则 ( 3 ) 人工神经元网络 人工神经元网络模拟人脑神经元结构，以m p 模型和h e b b 学习规 则为基础，建立三大类多种神经元网络，具有非线形映射特性、信息的 分布存储，并行处理和高度的自学习、自组织和自适应能力的种种优点 前馈神经元网络以感知器网络、b p 网络等为代表，可以用于分类和预 第3 页 山东大学硕士学位论文 测等方面；反馈式网络以h o p f i e l d 网络为代表，用于联想记忆和优化计 算；自组织网络以a r t 模型、k o h o n o n 模型为代表，用于聚类。 ( 4 ) 决策树。 决策树学习是一种通过逼近离散值目标函数的方法，通过把实例从 根节点排列到某个叶子节点来分类实例，叶子节点即为实例所属的分 类树上的每个节点说明了对实例的某个属性的测试，该节点的每一个 后继分支对应于该属性的一个可能值，分类实例的方法是从这棵树的根 节点开始，测试这个节点指定的属性，然后按照给定实例的属性值对应 的树枝向下移动。决策树方法主要应用于数据挖掘的分类方面。 ( 5 ) 遗传算法。 遗传算法是一种受生物进化启发的学习方法，通过变异和重组当前 己知的最好假设来生成后续的假设。每一步，通过使用目前适应性最高 的假设的后代替代群体的某个部分，来更新当前群体的一组假设，来实 现各个个体的适应性的提高。遗传算法由三个基本过程组成：繁殖( 选 择) 是从一个旧种群( 父代) 选出生命力强的个体，产生新种群( 后代) 的过 程；交叉( 重组) 选择两个不同个体( 染色体) 的部分( 基因) 进行交换，形成 新个体的过程；变异( 突变) 是对某些个体的某些基因进行变异的过程。 在数据挖掘中，可以被用作评估其他算法的适合度 ( 6 ) 粗糙集 粗糙集能够在缺少关于数据先验知识的情况下，只以考察数据的分 类能力为基础，解决模糊或不确定数据的分析和处理问题。粗糙集用于 从数据库中发现分类规则的基本思想是将数据库中的属性分为条件属 性和结论属性，对数据库中的元组根据各个属性不同的属性值分成相应 的子集，然后对条件属性划分的子集与结论属性划分的子集之间上下近 似关系生成判定规则所有相似对象的集合称为初等集合，形成知识的 基本成分任何初等集合的并集称为精确集，否则，一个集合就是粗糙 的( 不精确的) 。每个粗糙集都具有边界元素，也就是那些既不能确定为 集合元素，也不能确定为集合补集元素的元素粗糙集理论可以应用于 数据挖掘中的分类、发现不准确数据或噪声数据内在的结构联系。 ( 7 ) 支持向量机。 支持向量机( s v m ) 是在统计学习理论的基础上发展出来的一种新 第4 页 山东大学硕士学位论文 的机器学习方法。支持向量机可以应用于数据挖掘的分类、回归、对未 知事物的探索等方面，我们将在下面的章节中着重进行阐述。 1 4 支持向量机方法 1 4 1 支持向量机方法的优点 支持向t 机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 3 , 4 1 是近年来在模式识 别与机器学习领域中出现的新工具，其核心内容从1 9 9 2 年才开始提出， 1 9 9 5 年v a p n i k 的( t h en a t u r eo f s t a t i s t i c a ll e a r n i n gt h e o r y ) 一书的出 版，标志着统计学习理论体系已走向成熟。s v m 以统计学习理论为基 础，基于结构风险最小化原则之上，有效地避免经典学习方法中过学习、 维数灾难、局部极小等传统分类存在的问题，在小样本条件下仍然具有 良好的泛化能力，现已成为训练多层感知器、r b f 神经网络和多项式神 经元网络的替代性方法，因此受到了广泛的关注，而且成功应用到了人 脸识别【5 ，6 1 、文本分类7 1 、基因分析【引、手写体识别i 叭、语音识别【1 0 1 等多 种领域。关于支持向量机方法的具体内容将在下一章详述。下面只是指 出支持向量机作为分类工具的几个优点： 组成网络的结构相对简单。 专门针对有限样本情况，得到的是现有信息下的最优解，而不仅仅 是样本数趋于无穷大时的最优值。 分类性能优良，尤其是泛化能力好 算法具有强大的非线性和高维处理能力。保证了较好的推广能力， 并解决了维数问题，其算法复杂度与样本维数无关，只取决于支持 向量的个数 算法最终转化成为一个约束条件下的凸二次型寻优问题，从理论上 讲，得到的将是全局最优点，解决了在神经网络方法中无法避免的 局部最小化问题 更换核函数可以得到各种不同的分类曲面，可适应不同的数据类型 1 4 2s v m 和神经网络方法简单比较 对于分类问题，单层前向网络可以解决线性分类问题，多层前向网 第5 页 山东大学硕士学位论文 络可以解决非线性问题。但是这些网络仅仅能够解决问题，并不能保证 得到的分类器是最优的，如神经网络分类算法中常用到的b p 算法，由 于其学习的目标是分类误差对所有可能的点都达到极小，因此b p 算法 的目标函数是经验风险，它只能保证分类误差对于有限个样本是极小 的，泛化能力不强。而且神经网络的结构设计( 如隐含层节点数目的选 择) 依赖于设计者的先验知识和经验，缺乏一种有理论依据的严格设计 程序，也没有一种理论定量的说明神经网络的训练过程是否收敛以及收 敛的速度取决于什么条件，因而无法控制是否收敛和收敛的速度。而基 于统计学理论的支持向量机方法能够从理论上实现对不同类别间的最 优分类，拥有最好的泛化性能。 1 5 论文的主要研究内容 在分析前人对于s v m 的算法改进以及参阅关于s v m 的应用的文 章1 3 - 8 1 后，我们发现对于s v m 如何结合不同的数据结构提出相应的理论 方法来处理不同的数据类型是很有必要的。尤其是实际数据中常常出现 野点、噪声数据等，而且现实应用中要求s v m 方法具有增量学习的功 能。下面我们首先将从s v m 理论的几何意义出发，来分析如何减少野 点对最终分类面的影响，并利用高维定义的距离建立一个能够减少噪声 数据影响的s v m 方法的模型。进而在分析序列最小优化算法( s e q u e n t i a l m i n i m a lo p t i m i z a t i o n ，s m o ) 的基础上，深入对s v m 的增量算法进行剖 析，并结合v s v m 方法对其进行改进 1 第一章简要介绍了课题的写作背景，相关方法和支持向量机方法优 点及其与其他分类方法简单的对比。 2 第二章是支持向量机背景理论及其实现算法的综述，概要介绍了支 持向量机的背景理论一一统计学习理论，一般支持向量机方法的原 始优化问题，对偶问题和公认的较为成熟的算法，比较了其优缺点， 为下面提出自己的改进方法做准备。 3 第三章介绍了一种可以减少大规模支持向量机训练时间和能减少野 点影响的方法很多支持向量机的算法都是从一个随机的训练数据的子集 出发开始训练，本论文提出一种新的方法，在高维空日j 中估计出那些可能最 终成为支持向量的向量集合，继而加速优化的过程。同时利用高维空问定义 第6 页 山东大学硕士学位论文 的距离来发现野点，从而在一定程度上消除了野点对最终分类面的影响。 4 第四章提出了高维中心支持向量机( h c s v m ) 方法，利用非线性可分数 据映射到高维线性可分的特性，把数据映射到高维特征空间，将高维中心之 间的距离最小作为优化的原问题。在一定程度上减少了噪声数据对分类 面的影响，在改进s v m 方法中做出有益尝试。 5 第五章首先深入分析了支持向量机的特性，介绍了一般的增量学习 算法。通过分析，我们指出在增量学习中确定学习的参数是比较困 难的，所以我们利用v s v m 方法提出种支持向量机的增量学习策 略，它可以自动的调整增量算法训练参数。同时提出根据不同的数 据分布对于原来支持向量惩罚也应该不同，最后我们给出了此方法 的原始优化闯题，拉格朗日函数和对偶问题。 6 第五章是结束语，指出了有待于进一步解决的问题，并对支持向量 机理论的发展前景做出了展望。 第7 贞 山东大学硕士学位论文 第二章支持向量机理论及其实现算法理论概述 2 1 引言 s v m 的训练问题实质上是一个二次规划( q p ) 问题。在最优化理 论中已有多种成熟算法来解决此问题，如内点法，共轭梯度法但是 传统算法每一步迭代都涉及到核函数矩阵的运算，而核函数矩阵占用 的内存随样本数呈平方增长如计算4 0 0 0 个样本的核函数矩阵就需要 1 2 8 m 内存1 4 ，而且由于迭代误差的积累，也会导致算法精度难以接受。 因此设计适用于针对大量样本的算法就成为近年来s v m 研究的重要 内容，并且提出了很多有效的方法，其中最为著名的就是序列最小优 化( s m o ) 算法。支持向量机有效实现算法的出现也极大地推动了这一 理论的应用但是在分析比较支持向量机方法和神经网络理论时，我 们发现利用支持向量机具有明确的几何意义这一特性和核函数分析的 理论方法可以进一步完善支持向量机方法的理论 本章首先在概述支持向量机理论背景一一统计学习理论的基础 上，介绍了支持向量机的数学模型并对其实现算法进行综述，比较了 支持向量机方法的算法和模型建立上的改进本论文中多个改进措施 的提出都是基于以下理论背景。在以下各章提出改进方法的同时，也 将详细叙述相关的理论背景和思想方法。在本章中我们着重叙述支持 向量机的理论背景、基本原理以及公认比较成熟的改进措施。 2 2 统计学习理论 统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ) 【】是v a p n i k 等人在 7 0 年代末提出并在9 0 年代逐渐完善的一种针对小样本的机器学习理 论。它的核心问题是寻找一种归纳原则以实现最小化风险泛函，从而 实现最佳的推广能力统计学习理论就是研究小样本统计估计和预测 的理论，其核心内容包括四个方面； ( 1 ) 经验风险最小化准则下统计学习一致性的条件； ( 2 ) 在这些条件下关于统计学习方法推广性的界的结论； ( 3 ) 在这些界的基础上建立的小样本归纳推理准则； ( 4 ) 实现新的准则的算法 第9 页 山东大学硕士学位论文 其中，最有指导性的理论结果是推广性的界，与此相关的一个核 心概念是v c 维。 2 2 1 期望风险和经验风险 机器学习的目的是根据给定的训练样本求出对某系统输入输出之 间依赖关系的估计，使它能够对未知输出做出尽可能准确的预测。机 器学习问题就是根据，个独立同分布观测样本： t = ( x i ，y 1 ) ，( x ，”) ) ，其中i j r “，只 1 , - 1 ，i = 1 , 2 ，( 2 1 ) ( ，为样本的数目，卫e 1 , - 1 为类标号) 在一组函数厂( x ，国) ) 中求一个最优的函数扩( x ，) j 使得期望风险： r ( c o ) = i l ( y ，f ( x ，o j ) ) d f ( x ，力 ( 2 2 ) 最小化 其中三f ( x ，硼为由于用，伍) 对y 进行预测而造成的损失，不同 类型的学习问题有不同形式的损失函数r “为函数的广义参数 f ( x ，y ) 代表数据的概率分布，是客观存在的。 但是在实际情况中，由于样本所提供的信息不足，期望胍险无法 计算，因此传统的学习方法采用经验风险最小化( e m p i r i c a lr i s k m i n i m i z a t i o n e r m ) 准则。即利用样本定义经验风险，使得经验风险： 1 _ l r 。, p ( a 0 = 亡( 乃，( x 。，脚) ) ( 2 3 ) 最小化。 但是利用经验风险代替期望风险最小化并没有充分的理论依据。 使得经验风险最小，即训练误差最小并不能总是能够导致好的预测效 果，而且在某些情况下反而会导致推广能力的下降，即真实风险的增 加。如在神经网络中，若对有限的样本来说网络学习能力过强，足以 记住每个样本，此时经验风险很快就可以收敛到很小甚至为零，但却 根本无法保证它对未来样本能给出好的预测，这就是过学习问题 2 2 2 v c 维 为了研究机器学习过程一致收敛的速度和推广性，统计学习理论 中定义了一系列有关函数集学习性能的指标，其中最为重要的是v c 第10 页 山东大学硕士学位论文 维( v a p n i k c h e r v o n e n k i sd i m e n s i o n ) 模式识别方法中v c 维的直观 定义是：对一个指示函数集，如果存在h 个样本能够被函数集中的函数 按所有可能的2 “种形式分开，则称函数集能够把h 个样本打散，函数 集的v c 维就是它能打散的最大样本数目h 。若对任意数目的样本都有 函数能将它们打散，则函数集的v c 维是无穷大。有界实函数的v c 维可以通过用一定的阙值将它转化成指示函数来定义。 v a p n i k 提出了v c 维的概念来标志函数集的复杂程度，并用这个 概念给出了与分布无关的学习机器推广能力的界。这个界由两部分构 成：经验风险和置信范围( 以v c 维为参数) 。学习机器能力过强( v c 维很大) ，虽然能取得小的经验风险，但置信范围会很大；v c 维太小 又会导致大的经验风险一个好的归纳原则必须在二者之间做出权衡。 结构风险最小化原则( 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 ) 正是这样一 种归纳原则。s r m 原则定义了在对给定数据的逼近精度和逼近函数的 复杂性之间的一种折衷 2 2 3 结构风险最小化 由于经验最小化原则在样本有限时是不合理的，我们需要同时最 小化经验风险和置信范围其实，在传统方法中，选择学习模型和算 法的过程就是调整置信范围的过程，如果模型比较适合现有的训练样本 ( 相当于z 值适当) ，则可以取得比较好的效果但因为缺乏理论指导， 这种选择只能依赖先验知识和经验，造成了如神经网络等方法对使用 者经验的过分依赖。统计学习理论提出了一种新的策略，即把函数集 构造为一个函数子集序列，使各个子集按照v c 维的大小( 亦即m 的大 小) 排列；在每个子集中寻找最小经验风险，在子集间折衷考虑经验风 险和置信范围，取得实际风险的最小。如图2 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 ) 统计学习理论 还给出了合理的函数子集结构应满足的条件以及在结构风险最小化准 则下实际风险收敛的性质 实现s r m 原则可以有两种思路，一是在每个子集中求最小经验风 险，然后选择使最小经验风险和置信范围之和最小的子集显然这种 方法比较费时，当子集数目很大甚至是无穷时不可行。因此有第二种 第l1 贝 山东大学硕士学位论文 思路，即设计函数集的某种结构使每个子集中都能取得最小的经验风 险( 如使训练误差为零) ，然后只需选择适当的子集使置信范围最小， 则这个子集中使经验风险最小的函数就是最优函数。支持向量机方法 实际上就是这种思想的具体实现。 维：h ，h ：h 。 数集子集；s 。亡s ：cs3 2 2 4s v m 的基本原理 图2 1 结构风险最小化示意图 s v m 是统计学习理论的重要成果 假定训练数据t = ( x 。，m ) ，( x ，朋) ，其中x r ”，y 。 1 , - 1 ) 待1 , 2 ，( z 为样本的数目) 可以被一个超平面没有错误地分开，与两 类样本点距离最大( 称为边缘最大) 的分类超平面会获得最佳的推广 能力最优超平面将由离它最近的少数样本点( 称为支持向量) 决定， 而与其它样本无关我们用如下形式描述与样本间隔为的分类超平 面： ( w x ) 一b = 0( 2 4 ) 其中，w 表示可调的权重向量，x 表示输入向量，b 表示偏置。 第12 页 山东大学硕士学位论文 y ： + 1 ，! w ：x ：一? 皇 ( 2 5 ) v = 二) j 7 i 一1 ，( w 7 x ) 一西- ”。 其中为一正数，2 力知i i v a p n i k 给出了一个关于a - - 间隔分类超平 面v c 维上界的定理2 1o 如果向量i 属于一个半径为震的球中，那么间隔分类超平面集合的v c 维h 有下面的界： 嘲刁+ ( 2 6 ) 疗表示样本的数量，这样，s v m 首先保证了一个小的经验风险( 在 训练样本可分时就是零) ，并通过选择间隔最大的超平面的方式控制了 函数集的v c 维，这正是s r m 原则所要求的。下面我们将看到s v m 是 最小化l h 0 的值，也就是使得离超平面最近的向量与超平面之间的距离 最大化，从而使得定理2 1 中的尽量大而定理2 1 中的r 是由训练 样本点的分布确定的，是固定的。另外，一般情况下，有妥c 雄。所以， 茁 使得l h l 尽量小，也就是能够使得间隔分类超平面集合的v c 维h 尽量 小，则函数集的泛化能力就强。 2 3 支持向量机的数学模型 2 3 1 线性支持向量机 支持向量机的原理是用分类超平面将空间中两类样本点正确分 离，并得到最大的分类间隔，我们将s v m 最优化问题中的分类超平面 归一化：令a = l ，而w 和6 可以按比例缩放离超平面最近的样本( 支 持向量) 满足： ( 2 7 ) 支持向量到超平面的距离为1 呐0 。原问题就转换成一个有约束非 线性规划问题： m i n i m i z e o ( w ) = 抑2 s t 只( w 7 x j - b ) - i 0 ( 2 8 ) 第13 页 山东大学硕士学位论文 目标函数是严格上凹的二次型，约束函数是下凹的，这是一个严 格凸规划。按照最优化理论中凸二次规划的解法，我们把它转化为 w o l f e 对偶问题来求解，其解可以通过求解拉格朗曰函数的鞍点得到： 构造拉格朗日( l a g r a n g e ) 函数： l ( w , o r , b ) ：要j l w 0 2 一圭吼y ，( w t - x j - - 6 ) + 杰a , - 0 ，江1 ，2 ，t ( 2 9 ) ( 其中瓯是l a g r a n g e 乘子) 在鞍点位置应满足条件： 兰l ( w ，6 ) = o ，昙u w ，6 ) = 0 ( k u h n t u c k e r 条件) d ” ，呷 即w = 口，y , x ，和口弘= o ( 2 1 0 ) 将两式代回l a g r a n g e 函数中，消去w 和b ，经运算得到原最优化 问题的w o l f e 对偶问题： m a x m i z e w e ) = q q y , y j x , 一“ 豇叫= o ( 2 1 1 ) q of = ， 其解是原最优化问题的整体最优解。解出q 后利用w = 0 i y 。x ，确 定最优超平面，其中q s v 表示支持向量组成的向量空间。注意到只有 支持向量所对应的l a g r a n g e 乘子a t 才不是0 。由此可知权向量w 是支 持向量的线性组合，各个支持向量对这个线性组合的贡献就是它们对 应的l a g r a n g e 系数与它们对应的y 值( 1 或者一1 ) 的乘积。 从而得到最优分类超平面的分类规则为如下指示函数： r1 ，( x ) = s i g n l y ( x ，x ) - b l ( 2 1 2 ) l ，e m j 其中，b 。= a ( w x + ( 1 ) ) + ( w - x ( 一1 ) ) 】，x ( 1 ) 是第一类中的任一个支持 向量，i ( 一1 ) 是第二类中的任一个支持向量如果支持向量很多的话， 决策阶段的计算量也将是较大的 利用w o l f e 对偶问题，不但使问题更好处理，而且使样本在新问 题中仅以向量点积的形式出现，正是这一重要特点，使支持向量机方 法能推广到非线性情况。 第14 页 山东大学硕士学位论文 2 3 , 2 非线性支持向量机 把寻找最优超平面最终归结为w o l f e 对偶问题克服了“维数灾 难”：核函数k ( x ，x ，) 就等于i 。和x ，在高维特征空间中的映射之点积， 用k ( x ，x ，) 代替w o l f e 对偶问题中x 和x ，的点积后，计算量将会大大减 少。这样只需在输入空间中计算内积，而不必知道非线性映射的形式， 也不必在高维特征空间中进行计算( 关于核函数的概念我们还将在第 三章阐述) 。 此时输入空间中的判别函数是： r1 厂( x ) = j 酬y i o e j k ( x ，x ) - bi ( 2 1 3 ) 2 3 3 不可分情况的处理 为了使s v m 算法能应用于不可分情况，c o r t e s 和v a p n i k 在1 9 9 5 年引入了软边缘最优超平面的概念，引入非负变量毒，将约束条件放 松为： y 。( w x ，- b ) 一1 皇， i = 1 , 2 ， 同时对目标函数引入惩罚项，并将上式作为约束条件写作： 。何固= 三忡8 2 + c ( 喜舌) 只( w 1 x 。- b ) - i 毒，f = 1 , 2 ，( 2 1 4 ) 求解这个二次规划问题，推导所得的w o l f e 对偶问题为： m a x m i z e 缈( n ) = q 一