（计算机应用技术专业论文）基于svm的数据挖掘分类技术研究.pdf

摘要 摘要 随着计算机技术和网络通讯技术的日益发展，大量数据涌到人们面前。如何 有效地选择需要的信息成为了越来越突出的问题，数据挖掘技术就是顺应这种需 要而发展起来。 分类技术作为数据挖掘技术的一个重要方面，一直备受研究者的关注，已产 生了很多好的解决方法，其中本论文中研究的支持向量机方法就是一个很有效的 分类方法，它是以统计学习理论为基础而发展起来的一种新的分类方法。它使用 结构风险最小化原则代替经验风险最小化原则，较好地处理小样本情况下的学习 问题。又由于采用了核函数思想，它能把非线性问题转化为线性问题来解决，并 降低了算法的复杂度。 本文首先讨论了统计学习理论的一些基本知识，其中包括了机器学习，v c 维， 推广性的界和结构风险最小化等。接下来重点介绍了支持向量机，包括了它的发 展历史和现状，主要的基本概念和研究内容，并针对当前几种基于支持向量机的 多值分类算法的不足，分析了多值分类的过程，采用基于相对分离度的新的多值 分类算法，最后的数值实验说明算法是可行的、有效的。另外，针对支持向量机 训练速度慢的缺点，分析了支持向量的性质和增量学习的过程，给出了一种新的 增量学习算法，随后的数值实验也表明该法能在保证测试精度的同时有效地减少 了训练时间。 目前国内支持向量机的研究只是限于理论方面，应用方面才刚刚开始。支持 向量机是一种基于应用的技术，因此很多知识和经验还需要我们在实践中进一步 总结和发现。 关键词：数据挖掘分类支持向量机核函数 a b s t r a c t w i t ht h ed e v e l o p m e n to ft h et e c h n o l o g yi nn e t w o r ka n dc o m m u n i c a t i o n , m a s s i n f b n n a t i o nc r o w di no n h o wt oe f f e c t i v e l ys e l e c tw h a tw en e e db e c o m e sm o r e o u t s t a n d i n gt h a ne v e r d a t am i n i n ga sap r o c e s s i n gt e c h n i q u ei sp o p u l a r t ob eu s e dt o m e e tt h en e e d t h ec l a s s i f i c m i o nt e c h n o l o g y , a sa l li m p o r t a n ta s p e c to fd a t am i n i n g ，h a sa l w a y s b e e nt h ec o r t c e mo ft h er e s e a r c h e r s m a n yg o o ds o l u t i o n sh a v eb e e nc r e a t e dd u r i n gt h e c l a s s i f i c a t i o na l g o r i t h mr e s e a r c hp r o c e s s t h es u p p o r tv e c t o rm a c h i n e ，w h i c hi s t h e f o c u so ft h i sp a p e r ，i sav e r ye f f e c t i v ec l a s s i f i c a t i o nm e t h o d i ti st h o u g h to fa n e w g e n e r a t i o ni ) fl e a r n i n gm a c h i n eb a s e do nt h e 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 em a i n a d v a n t a g eo fs v m i st h a ti tc a l ls e r v eb e t t e ri n t 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 g p r o b l e m sb yt h er e p l a c e m e n to fe x p e r i e n t i a l r i s km i n i m i z a t i o nb ys t r u c t u r a lr i s k m i n i m i z a t i o n m o r e o v e r , s v mc a nt r e a t an 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 r l e 锄i n gp r o b l e ms i n c ei tm a p s t h eo r i g i n a ld a t ai n t ot h ek e r n e ls p a c ei nw h i c h w e o n l y s o l v et h el i n e a rl e a r n i n gp r o b l e m a tt h eb e g i n n i n gt h ec o n c e p t s ，t h er e s e a r c hs t a t ei nt h ew o r l d ，t h ea p p l i c a t i o n ，t h e p r o e e s sa i l dt 1 1 eb a s i cm e t h o do fd a t am i n i n ga r ea d d r e s s e d a n d n e x tt h i sp a p e rs t u d i e s t h eb a s i ck n o w l e d g eo fs t a t i s t i c a ll e a r n i n gt h e o r y t h e nt h ep a p e rs t r e s s e st oi n t r o d u c e s v m i n v o l v e do ft h ed e v e l o p m e n th i s t o r y , t h es t a t es of a r , m a i nc o n c e p t sa n dt l l e c o n t e n to fr c s e a r c h n a i v es v m i so n l ya b l et od e a lw i t hb i n a r yc l a s s i f i c a t i o n i nt h i s t h e s i s a r e i d i s c u s s e dt h ec u r r e n tm u l t i c l a s ss v m s ，an o v e l m u l t i - c l a s ss v m c l a s s i f i e rb a s e do nt h er e l a t i v i t ys e p a r a b i l i t ym e a s u r ei sp r o p o s e d a n dt h en u m e r i c a l a n da p p l i c a b l er e s u l t si l l u s t r a t et h a tt h et e c h n i q u ei sf e a s i b l ea n de f f e c t i v ei nt h ee n d o t h e r w i s eb ya n a l y z i n gt h ec h a r a c t e r i s t i c so fs u p p o r tv e c t o r sa n dt h ep r o e e s s m go f i n c r e n l e n t 8 ll e a r n i n g ，an e wa l g o r i t h mo fi n c r e m e n t a ll e a r n i n gm e t h o di sp r e s e n t e di n t h j sp a p e le x p e r i m e n t a lr e s u l t sh a v es h o w nt h a t ，w i t hk e e p i n gt h et e s t i n ga c c u r a c y , t h e n e wm e t h o dd i s c a r d su s e l e s ss a m p l e sa n dr e d u c e st h et r a i n i n gt i m e t h er e s e a r c ho fs v mi nd o m e s t i cj u s tl i m i t si nt h e o r ys of a ra n dt h ea p p l i c a t i o nd o s t a r tj u s tn 0 s v mi sat e c h n o l o g yf o ra p p l i c a t i o n , s ot h e r ea r es t i l lm u c hk n o w l e d g e a n de x p e r i e n c et h a tn e e dt ob ef o u n di np r a c t i c e k e y w o r d ：d a t am i n i n g c l a s s i f i c a t i o n s u p p o r t v e c t o rm a c h i n e k e r n e lf u n c t i o n 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作过的同志对本研究所 做的任何贡献已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：塾l 二蜂 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保 证，毕业后结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大 学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在年解密后适用本授权书。 本人签名： 导师签名： 日期兰竺堡：兰：兰 日期 誓g 。二肇 第一章绪论 第一章绪论 1 1 引言 随着计算机技术和i n t e m e t 的迅速发展，当今世界正处于一个“数据爆炸 的 时代，数据库非常庞大，大量数据涌到人们面前，人们面对的问题不再是缺少数 据而是被数据淹没了，即所谓“人们被数据淹没，却饥饿于知识，【。面对海量数 据，使用传统或经典的方法，即便是使用计算机来提取有用信息和知识，人们也 会感到无能为力。在此需求之下，一个新的研究领域数据挖掘便应运而生， 目前它已成为人工智能、统计学、数据库等领域研究的热点之一。 当前，数据挖掘是涉及数据库和人工智能等学科的一门相当活跃的研究领域， 同时又有广泛可用的、存在于各种数据库中的海量数据。海量数据的出现，对数 据挖掘应用形成极大的需求，使这一技术迅速得到发展和完善。其中，分类技术 作为数据挖掘技术的一个重要方面，一直备受研究者的关注。 在研究分类算法过程中产生了很多好的解决方法，其中本论文中重点研究的 支持向量机方法就是其中一个有效的分类方法。本论文对于支持向量机方法在多 值分类的准确率等方面给出了改进。 本章简要概述了数据挖掘技术，然后指出支持向量机方法的优点，并在总体 上表明了支持向量机方法在数据挖掘分类方法中的地位。 1 2 数据挖掘概述 数据挖掘可以看作是从大型数据库或数据仓库中提取隐含的、未知的、非平 凡的及有潜在价值的信息或模式的动态、交互的过程，其核心模块主要涉及数据 库技术、机器学习、数理统计、人工智能等多个方面。 数据挖掘【l , 2 1 是在1 9 8 9 年8 月于美国底特律市召开的第十一届国际联合人工智 能学术会议上正式形成的。一种比较公认的定义是：数据挖掘是指从数据库的大 量数据中揭示出隐含的、先前未知的、潜在有用的信息的非平凡过程。许多人把 数据挖掘视为另一个常用的术语：数据库中的知识发现的同义词p j 。而另一些人只 是把数据挖掘视为数据库中知识发现过程的一个基本步骤。一般地，数据库中知 识发现的过程由下列步骤组成： 1 数据清理：消除噪声或不一致数据。 2 数据集成：将多种数据库中的数据组合在一起。 2 基于s v m 的数据挖掘分类技术研究 3 数据选择：从数据库中检索与分析任务相关的数据。 4 数据变换：将数据变换或统一成适合挖掘的形式。 5 数据挖掘：使用智能方法提取数据模式。 6 模式评价：根据某种兴趣度度量、识别表示知识的真正有趣的模式。 7 知识表示：使用可视化和知识表示技术，向用户提供挖掘的知识。 广义的数据挖掘是从存放在数据库、数据仓库或者其他信息库中的大量数据 中挖掘有趣知识的过程。在这种观点下，数据挖掘系统具有以下主要成分 2 1 ：数据 库、数据仓库或其他信息库、数据库或数据仓库服务器、知识库、数据挖掘引擎、 模式评估模块和图形用户界面。可以用图1 1 表示： 图1 1 数据挖掘系统的主要成分 根据发现知识的不同，数据挖掘任务可以归纳为以下几种： 1 概念描述 一个概念常常是对一个包含大量数据集合总体情况的概述。利用定性和对比 的方法从与学习任务相关的一组数据中提取出关于这些数据的特征式，这些特征 式表达了该数据集的总体特征。 2 分类 分类是用一个函数把各个数据项映射到某个预定义的类，或者说是得出关于 该类数据的描述或模型。数据分类方法有决策树分类方法、统计方法、神经网络 方法、粗集方法、支持向量机方法等。 3 关联性分析 关联性分析用来发现一组项目之间的关联关系和相关关系。它们经常被表达 为规则形式。一条形如x y 的关联规则可以解释为：满足x 的数据库元组也很可 能会满足y 。关联性分析广泛应用于交易数据分析，通过分析结果来指导销售、目 录设计及其它市场决策的制定。 4 聚类分析 第一章绪论 聚类是一种常见的描述工作，搜索并识别一个有限的种类集合或簇集合，从 而描述数据。简单地说，就是识别出一组聚类规则，将数据分成若干类。这些种 类可能相互排斥而且是穷举的，或者包含了更丰富的表达形式。聚类分析与分类 分析方法明显的不同在于，后者所学习获取分类预测模型所使用的数据是己知类 别归属，属于有教师监督学习方法，而聚类分析所分析的数据是无类别归属的。 5 预测分析 通过对数据的分析处理，估计一组数据中的某些丢失数据的可能值或一个数 据集合中某种属性值的分布情况。一般是利用数理统计的方法，找出与所要预测 的属性值，并根据相似数据的分析估算属性值的分布情况。 1 3 1 研究现状 1 3 支持向量机 随着支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) t 4 j 的提出并展示出其巨大的潜 力，关于它的研究已逐渐被许多从事机器学习【4 5 6 j 的研究机构和学者所重视。随着 理论的不断完善，支持向量机的应用逐渐成为各国研究者的研究热门。目前，支 持向量机算法在模式识别、回归估计、概率密度估计等方面已都有应用。 但是任何一种方法要成功应用于分类规则挖掘，都必须解决几个问题。首先， 数据挖掘的算法必须能处理海量数据，即数十万、上百万甚至更多的数据量。现 有训练算法一般都基于s m o 或其改进算法，己经基本解决了这个问题：其次数据 挖掘在处理海量数据的同时还要有较快的运算速度，这样才有较高的实用价值。 j i a n x i o n gd o n g 开发的h e r o s v m ( 单线程版) 经过特别的优化，在p e n t i u m 41 7 g h z 的c p u 上对一百多万样本的汉王手写数字数据库作训练，只需4 5 分钟即可完成 ( w i n d o w s2 0 0 0p r o f e s s i o n a l ，1 5 gs d r a m ) 7 1 。这样训练速度的问题也基本解决； 最后是预测的问题。当训练得到的支持向量比较多时( 特别是在训练海量数据时) ， 预测的速度会比较慢。c j c b u r g e s 提出了一种简化的支持向量机( s i m p l i f i e d s u p p o r tv e c t o rm a c h i n e ) 碡，9 】，可以大大压缩支持向量的数目，而对预测准确率影响 很小，从而可以加快预测速度。由此我们可以说，支持向量机完全可以成为一种 很好的分类规则挖掘方法。 1 3 2 方法优点 统计学习理论和支持向量机建立了一套较好的有限样本下机器学习的理论框 架和通用方法，有严格的理论基础，其核心思想就是学习机器的复杂性要与有限 4 基于s v m 的数据挖掘分类技术研究 的训练样本相适应，能较好地解决有限样本、非线性、高维数和局部极小点等实 际问题，能建立稳定的预测准确率高的分类器，所以很适合应用于分类规则挖掘， 也受到了广泛的关注，而且成功应用到了人脸识别、文本分类、基因分析、手写 体识别、语音识别等多种领域【l 们。其中，最经典的应用研究是贝尔实验室对美国 邮政手写数字库识别的实验，人工识别的平均错误率是2 5 ，用决策树方法识别 错误率是1 6 2 ，两层神经网络中错误率最小的是5 9 ，专门针对该识别问题设计 的五层神经网络( l e n e t l ) 的错误率为5 1 ，而用核函数分别为多项式、r b f 、感知 器所形成的三种支持向量机方法得到的错误率分别为4 0 ，4 1 和4 2 。这一例 子一方面说明了在分类精度方面，支持向量机方法较其它方法有明显的优势，同 时也反映了由支持向量机设计的主观依赖性相对神经网络而言要小一些。支持向 量机在有效性和通用性两方面的表现可见一斑，它已成为数据挖掘中的一个新方 法。 关于支持向量机的具体内容将在下一章详述。下面只是指出其作为分类工具 的几个优点： 1 组成网络的结构相对简单。 2 专门针对有限样本情况，得到的是现有信息下的最优解，而不仅仅是样本 数趋于无穷大时的最优值。 3 。分类性能优良，尤其是泛化能力好。 4 算法具有强大的非线性和高维处理能力，保证了较好的推广能力，并解决 了维数问题，其算法复杂度与样本维数无关，只取决于支持向量的个数。 5 算法最终转化成为一个约束条件下的凸二次型寻优问题，从理论上讲，得 到的将是全局最优点，解决了在神经网络方法中无法避免的局部最小化问题。 6 更换核函数可以得到各种不同的分类曲面，可适应不同的数据类型。 1 4 本文研究内容及章节安排 支持向量机技术是以统计学习理论为基础而发展起来的一种新的分类方法， 对小样本数据训练出的分类器仍有较高的分类精度，而且具有很好的推广性能。 本文对支持向量机在数据挖掘领域的研究主要是以下两个方面： 1 支持向量机方法是针对二类别分类问题而提出的，如何将其扩展到多类别 分类是支持向量机研究的重要内容之一。分析了现有的多分类支持向量机的现状， 采用基于相对分离度的二叉树多分类支持向量机方法，在u c i 和s t a t l o g 数据集上的 实验结果表明，该方法对分类精度有明显提高。 2 。支持向量机在小样本学习上具有优势，但是支持向量机的训练速度很慢， 样本数量越多，速度下降越明显。然而在数据挖掘的实际应用中，面对的往往是 第一章绪论 大样本问题，因此有必要提高支持向量机的训练速度，一个有效的解决办法便是 增量学习技术。本文对支持向量机的增量学习技术做了深入研究，分析了支持向 量在构建增量算法中的关键作用以及在增量学习过程中引入新的样本后支持向量 的转化问题；分析了已有的支持向量机增量算法，并给出一种新的支持向量机增 量算法。 全文分为六章： 第一章：绪论。 第二章：统计学习理论的经验风险最小化原理、v c 维和结构风险最小化原理， 这些是支持向量机的理论基础。 第三章：支持向量机的原理、核心思想核函数等，同时也介绍了支持向 量机的主要研究内容。 第四章：多值分类支持向量机。介绍了现有的利用支持向量机来解决多分类 问题的方法，并采用基于相对分离度的二叉树多分类支持向量机，并在数据集上 对各种方法进行了比较。 第五章：深入分析了支持向量的特性，介绍了一般的增量学习算法，并给出 一种新的支持向量机增量学习算法。 第六章：对全文的总结和对将来研究的展望。 第二章统计学习理论 7 第二章统计学习理论 与传统统计学相比，统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y , s l t ) 是一种专 门研究小样本情况下机器学习规律的理论。v a p n i k 等人从二十世纪六、七十年代 开始致力于此方面研究，到二十世纪九十年代中期，随着其理论的不断发展和成 熟，也由于神经网络等学习方法在理论上缺乏实质性进展，统计学习理论开始受 到越来越广泛的重视。 统计学习理论是建立在一套较坚实的理论基础之上的，为解决有限样本学习 问题提供了一个统一的框架。它能将很多现有方法纳入其中，有望帮助解决许多 原来难以解决的问题( 比如神经网络结构选择问题、局部极小点问题等) ；同时， 在这一理论基础上发展了一种新的通用学习方法支持向量机( s u p p o r tv e c t o r m a c h i n e ，s v m ) ，它已经初步表现出很多优于已有方法的性能，在解决小样本、非 线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用到函数拟合 等其他机器学习问题中。虽然统计学习理论和支持向量机尚有很多问题需要进一 步研究，但很多学者认为，它们正在成为机器学习领域新的研究热点，并将推动 机器学习理论和技术重大的发展。 2 1 机器学习问题的基本问题 2 1 1 机器学习问题的数学表示 基于数据的机器学习是现代智能技术中的重要方面，研究从观测数据( 样本) 出发寻找规律，利用这些规律对未来数据或无法观测的数据进行预测，包括模式 识别、神经网络等在内，现有机器学习方法共同的重要理论基础之一是统计学。传 统统计学所研究的是渐近理论，即当样本数目趋向于无穷大时的极限特性，统计 学中关于估计的一致性、无偏性和估计方差的界等，以及分类错误率的诸多结论， 都属于这种渐近特性。但在实际问题中，样本数目往往是有限的，当问题处在高 维空间时尤其如此，因此一些理论上很优秀的学习方法实际中表现却可能不尽人 意。 基于数据的机器学习的目的是根据给定的训练样本求输入输出之间的依赖关 系的估计，使它能够对未知输出作出尽可能准确的预测【1 1 1 。一般地，变i t y 与x 存 在一定的未知依赖关系，即遵循某一位置的联合概率p ( x ，y ) ，x 与y 之间的确定性 关系可视作是其特例。监督学习问题就是根据价独立分布观测样本： 8 基于s v m 的数据挖掘分类技术研究 ( 五，m ) ，( 恐，耽) ，( 而，弘) ，( 而，乃) ，西r ，y t r 式( 2 - 1 ) 在一组函数 厂( x ，w ) ) 中求一个最优的函数f ( x ，w o ) ，使期望风险 r ( w ) = l l ( y ，f ( x ，w ) ) d p ( x ，夕)式( 2 - 2 ) 最小。其中 f ( x ，w ) 称为预测函数集，也称为学习函数、学习模型或学习机器，w 为函数的广义参数， f ( x ，川) 可以表示任何函数集；l ( y ，f ( x 们) 是损失函数，它 表示由于f ( x ，w ) 咖进行估计而造成的偏差。 有三类基本的机器学习问题，即模式识别、函数逼近和概率密度估计。不同 类型的学习问题有不同形式的损失函数。 对模式识别问题，输出y 是类别标号，两类情况b = 0 ，1 ) 或 l ，- 1 ，预测 函数称作指示函数，损失函数可以定义为 坳胞叫0 孑多：裟暑? 蛔， 使风险最小就是b a y e s 决策中使错误率最小。在函数逼近问题中。y 是连续变 量( 这里假设为单值函数) ，损失函数可定义为 l ( y ，f ( x ，w ) ) = ( j ，一f ( x ，w ) ) 2式( 2 - 4 ) 即采用最小平方误差准则。而对概率密度估计问题，学习的目的是根据训练样本 确定x 的概率密度。记估计的密度函数为p ( x ，w ) ，则损失函数可以定义为 三 ，f ( x ，w ) ) = - l o g p ( x ，w )式( 2 - 5 ) 经常采用的损失函数有以下几种： 1 二次型损失函数 l ( y ，f ( x ，w ) ) = ( y f ( x ，w ) ) 2式( 2 6 ) 2 绝对值损失函数 l ( y ，f ( x ，川) = i j ，一f ( x ，w ) i 式( 2 - 7 ) 3 h u b e r 损失函数 l ( y ，f ( x ，w ”= 4 s 不灵敏损失函数 l ( y ，f ( x ，w ) = y - f ( x ，w ) l 。 式( 2 9 ) 式 0 0、，、 w， w b 一 ， 扩 矿 ) 、， 协 m ， r t o 丫 八 厂 一 ；、 y 第二章统计学习理论 9 其中 l y - f ( x ，w ) i 。= m a x ( o ，l y - f ( x ，忉l _ g )式( 2 1 0 ) 上述的损失函数如图2 1 表示： i j 二次型损失函数 绝对值损失函数 h u b e r - 刮损失函数 不灵敏损失函数 图2 1 损失函数曲线图 在上述四种损失函数中，二次型损失函数比较常用，数学处理起来比较简单； 绝对值损失函数比二次型损失函数对大的损失误差更不敏感；h u b e r 损失函数的鲁 棒性较强，当训练样本的概率分布未知时，它可以得到很好的学习效果；s 不灵 敏损失函数能够提高学习机解的稀疏性和泛化能力。 2 1 2 复杂性与推广能力 在早期神经网络研究中，人们总是把注意力集中在如何使如。( w ) 更小，但很 快便发现，一味追求训练误差小并不是总能达到好的预测效果。人们将学习机器 对未来输出进行正确预测的能力称作推广性。某些情况下，当训练误差过小反而 会导致推广能力的下降，这就是几乎所有神经网络研究者都曾遇到的所谓过学习 ( o v e r f i t t i n g ) i h - 题。从理论上看，模式识别中也存在同样的问题，但因为通常使用 的分类器模型都是相对比较简单( 比如线性分类器) ，因此过学习问题并不像神经 网络中那样突出。 之所以出现过学习现象，一是因为学习样本不充分，二是学习机器设计不合 理，这两个问题是互相关联的。只要设想一个很简单的例子，假设我们有一组训 练样本( x ，y ) ，x 分布在实数范围内，而y 取值在 0 ，1 】之间。那么不论这些样本是 1 0 基于s v m 的数据挖掘分类技术研究 依据什么函数模型产生的，只要我们用一个函数f ( x ，a ) = s i n ( a x ) 去拟合这些样点， 其中a 是待定参数，总能够找到一个a 使训练误差为零，如图2 2 所示。 图2 2 过学习现象示意图 但显然得到的这个“最优函数 不能正确代表原来的函数模型。出现这种现 象的原因，就是试图用一个复杂的模型去拟合有限的样本，结果导致丧失了推广 能力。在神经网络中，如果对于有限的训练样本来说网络的学习能力过强，足以 记住每一个训练样本，此时经验风险很快就可以收敛到很小甚至零，但我们却根 本无法保证它对未来新的样本能够得到好的预测。这就是有限样本下学习机器的 复杂性与推广性之间的矛盾。 在很多情况下，即使我们已知问题中的样本来自某个比较复杂的模型，但由 于训练样本有限，用复杂的预测函数去学习对样本进行学习的效果通常也不如用 相对简单的预测函数，当有噪声存在时就更是如此。 从这些讨论我们可以得出以下基本结论：在有限样本情况下 1 经验风险最小并不一定意味着期望风险最小； 2 学习机器的复杂性不但与所研究的系统有关，而且要和有限的学习样本相 适应。 有限样本情况下学习精度和推广性之间的矛盾似乎是不可调和的，采用复杂 的学习机器容易使学习误差更小，但却往往丧失推广性。因此，人们研究了很多 弥补办法，比如在训练误差中对学习函数的复杂性进行惩罚，或者通过交叉验证 等方法进行模型选择以控制复杂度等等，使一些原有方法得到了改进。但是，这 些方法多带有经验性质，缺乏完善的理论基础。在神经网络研究中我们对具体问 题可以通过合理设计网络结构和学习算法达到学习精度和推广性的兼顾，但却没 有任何理论指导我们如何做。而在模式识别中，人们更趋向于采用线性或分段线 性等较简单的分类器模型。 第二章统计学习理论 2 2 统计学习理论 统计学习理论【1 2 , 1 3 , 1 4 】1 的一个突出特点就是其概念明确，结论是建立在严格的证 明之上，它被认为是目前针对小样本估计和预测学习的最佳理论。其理论主要包 括四个方面【6 j ： 1 经验风险最小化准则下统计学习一致性的条件： 2 在这些条件下关于统计学习方法推广性的界的结论； 3 在这些界的基础上建立的小样本归纳推理准则； 4 实现新的准则的实际方法。 其中，最有指导性的理论结果是推广性的界，与此紧密相关的一个核心概念 是v c 维。 2 2 1 经验风险最小化与学习的一致性 在上面的学习问题表述中，学习的目标在于使期望风险最小化，但是由于可 以利用的信息只有有限的样本数据，一般不知道样本空间的概率分布，这样式( 2 2 ) 的期望风险实际上无法计算，因此传统的学习方法例如神经网络学习方法中采用 了所谓经验风险最小化准则【4 ，1 5 ，16 1 ，即用样本来定义经验风险： 1， r 呷= ( 厂( 乃，厂( 五，w ) ) 式( 2 1 1 ) i = l 作为对式( 2 2 ) 的近似估计，并设计学习算法使它最小化。 经验风险如。( w ) 在什么条件下收敛到真实风险尺( 川? 这也称为学习的一致性 ( c o n s i s t e n c y ) 。为了研究学习机在经验风险最小化原则下的学习一致性问题和一致 性收敛的速度，统计学习理论提出了学习过程的四个里程碑的定理。它们在不同 程度上回答了学习理论最基本的问题，即在什么条件下，一个遵循经验风险最小 化原则的学习机器或算法，当样本数趋向无穷大时收敛于期望风险最小的最优解， 而且收敛的速度是快的。 定理( 1 ) ：e r m 原则一致性的充分必要性条件是：经验风险如口( w ) 在如下意义 上一致收敛于实际风险尺( w ) ： 1 i m p s u p ( r ( w ) 一( w ) ) s 】_ o ，v 占 0 式( 2 1 2 ) 定理( 2 ) ：学习机学习过程双边一致收敛的充分必要条件是l i m - ，( 1 ) ：0 ，其中 ，o ， 肌j ) 为指示函数集在样本，上的v c 熵。 1 2 基于s v m 的数据挖掘分类技术研究 定理( 3 ) ：学习机学习过程收敛速度快的充分条件是 i m 皇毒盟：0 ，其中 l _ o f 玩。( ，) 为退火的v c 熵。 定理( 4 ) ：学习机学习过程一致收敛的充分必要条件是：对任意的样本分布都 l ，i m 鱼竽：0 ，这时学习过程收敛速度一定是快的。其中g ( ，) 为函数集的生长函 。 f 数。 指示函数集的v c 维【1 7 】定义如下：设f 为一个从n 维向量瓤0 0 ，1 j 的函数族， 则f 的v c 维为确子集e 的最大元素数，其中e 满足：对于任意s e ，总存在函数 z = f ，使得当x s 时x ( x ) = 1 ，x 萑s ，但x e 时z ( x ) = 0 。 2 2 2v c 维 为了研究学习过程一致收敛的速度和推广性，统计学习理论定义了有关函数 集学 - - j 性能的指标，其中最重要的是v c 维( 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 ) 1 7 】。模 式识别方法中v c 维的直观定义是：对一个指示函数集，如果存在h 个样：茌能够被函 数集中的函数按所有可能的2 6 种形式分开，则称函数集能够把h 个样本汀散；函数 集的v c 维就是它能够打散的最大样本数目h 。若对任意数目的样本都有函数能将 它们打散，则函数集的v c 维是无穷大。有界实函数的v c 维可以通过用一定的阈 值将它转化成指示函数来定义。v a p n i k 给出了一个很直观的解释：当一个函数集 合的v c 维为n 时，那么存在一个点集以，所有可能的( 两类) 组合即2 ”种组合全 部都可以用该函数集合分割开，而对于任何大于的点集x 。( m 刀) 都：不能满足上 述条件，即其所有可能的组合不再可能用该函数几何分割开。 v c 维反映了函数集的学习能力，v c 维越大则学习机器越复杂。遗感的是，目 前尚没有通用的关于任意函数集v c 维计算的理论，只对一些特殊的函数集知道其 v c 维。比如在n 维实数空间中线性分类器和线性实函数的v c 维是n + 1 ，而上一节例 子中f ( x ，口1 = s i n ( a x ) 的v c 维则为无穷大。对于一些比较复杂的学习机器( 如神 经网络) ，其v c 维除了与函数集( 神经网络) 有关外，还受到学习算法等的影响， 其确定更加困难。对于给定的学习函数集，如何( 用理论或实验的方法) 计算v c 维是当前统计学习理论中有待研究的一个问题。 第二章统计学习理论 图2 3 在二维平面中3 个样本点被打散的示意图 2 2 3 泛化能力的界 在训练样本有限的情况下，期望风险最小化并不能简单地用经验风险最小化 替代。针对这一问题，统计学习理论建立了有关学习风险的收敛速度及其上界的 一系列结论，希望它们能够指导如何设计学习机器。其中一个最重要的是有关经 验风险和期望风险之间的关系，称为泛化能力的界，它是分析学习机器性能和发 展新的学习算法的重要基础。v a p n i k 证明，期望风险r ( w ) 满足一个上界，即任取 0 r 1 ，下列边界以概率1 一r 成立 r ( 叻( 叻+ h ( 1 n ( 2 1 4 ) + 1 ) - h a ( r 4 ) 式( 2 1 3 ) 其中k ( 叻是经验风险，办是学习机的v c 维，是训练样本的数目。对于线性 分类器，满足 h马i t o | 1 2j 5 c 2 + l 式( 2 - 1 4 ) 其中r 为包络训练数据的最小球半径。机器学习过程不仅要使经验风险最小， 还要使v c 维尽量小，对未来样本才会有较好的推广能力，这是结构风险最小化准 则的基本思想。 统计学习理论首次从理论上说明了学习机器的期望风险存在上界，并且上界 由两部分组成，一部分为训练样本的经验风险，另一部分被称为置信范围。期望 风险的上界不仅与经验风险有关，而且还和学习机器的v c 维与训练样本数目有关。 这种关系可以简单地表示为： 尺( 叻8 嘲一+ ( 乃，) 式( 2 1 5 ) 1 4 基于s v m 的数据挖掘分类技术研究 由式( 2 - 1 5 ) 可以看出，在有限的学习样本下，学习机器的v c 维越高，则置信范 围就越大，导致期望风险与经验风险之间的偏差越大。对于同一类学习机器，不 但要使经验风险最小化，还要使v c 维尽量小，从而缩小置信范围，使期望风险最 小。神经网络等学习机之所以出现过学习现象，就是因为其网络结构或算法设计 不合理，导致虽然经验风险较小，但因为置信范围过大导致泛化能力下降。 2 2 4 结构风险最小化 从上面的结论看到，e r m 原则在样本有限时是不合理的，我们需要同时最小 化经验风险和置信范围。其实，在传统方法中，选择学习模型和算法的过程就是 调整置信范围的过程。如果模型比较适合现有的训练样本( 相当于i v n 值适当) ， 则可以取得比较好的效果。但是因为缺少理论指导，这种选择只能依赖先验知识 和经验，造成了如神经网络等方法对使用者“技巧 的过分依赖。 风黢 丽数榘于榘：s t c s 奎c 5 赢 v c 缝l a i 2 h a 图2 4 结构风险最小化原理图 统计学习理论提出了一种新的策略，即把函数集构造为一个函数子集序列， 使各个子集按照v c 维的大小( 亦即矽的大小) 排列：在每个子集中寻找最小经 验风险，在子集间折衷考虑经验风险和置信范围，取得实际风险的最小，如图2 4 所示，这种思想称作结构风险最小化( 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 准则i l 引。统计学习理论还给出了合理的函数子集结构应满足的条件及在s r m 准 则下实际风险收敛的性质。 实现s r m 原则可以有两种思路【1 9 1 。一是在每个子集中求最小经验风险，然后 选择使最小经验风险和置信范围之和最小的子集。这种方法比较费时，当子集数 目很大甚至是无穷时不可行。因此有第二种思路，即设计函数集的某种结构使每 个子集中都能取得最小的经验风险( 如使训练误差为0 ) ，然后只需选择适当的子 第二章统计学习理论 集使置信范围最小，则这个子集中使经验风险最小的函数就是最优函数。支持向 量机方法实际上就是这种思想的具体实现。 2 3 本章小结 传统统计学研究的主要是渐近理论，只有在无穷多的样本前提下，其算法才 是合理的。但是现实中的样本通常是有限的，因此传统统计学在解决学习问题时 存在一定的局限性。统计学习理论专门研究有限样本情况下机器学习的规律，它 从理论上证明了实际风险的界是由经验风险和置信范围两部分构成的，给出了控 制置信范围的方法，并在此基础上提出了结构风险最小化原理，为建立具有好的 推广性能的学习机器提供了坚实的理论基础。 第三章支持向量机 1 7 第三章支持向量机 二十世纪九十年代以来，随着统计学习理论自身的不断发展和成熟，在这一 理论基础上发展了一种新的通用学习方法支持向量机，它已经初步表现出很 多优于已有方法的性能，在解决小样本、非线性及高维模式识别问题中表现出许 多特有的优势，并能够推广应用到其他机器学习问题中。支持向量机最初产生于 模式识别问题中的两类分类问题，并被推广到函数估计等其他机器学习问题。虽 然统计学习理论和支持向量机方法中还有很多问题需要进一步研究，但很多学者 认为，它们正在成为机器学习领域新的研究热点，并将推动机器学习理论和技术 进一步发展。 3 1 支持向量机的发展历史 早在二十世纪六十年代v v a p n i k 就开始了统计学习理论的研究，1 9 7 1 年， v v a p n i k l l 3 1 和a c h e r v o n e n k i s 提出了s v m 的一个重要的理论基础v c 维理论。 1 9 8 2 年，v v a p n i k l l 2 进一步提出了具有划时代意义的结构风险最小化原理。 1 9 9 2 年，b o s e r l 2 ，g u y o na n dv a p n i k 提出了最优边界分类器。 1 9 9 3 年，c o r t e s 2 1 1 和v 却m k 进一步探讨了非线性最优边界的分类问题。 1 9 9 5 年，v v a p n i k 完整地提出了s v m 分类【4 】。 1 9 9 7 年，v v a p n i k ，s g o k o w i c h 和a s m o l a ，详细介绍了基于s v m 方法的回归 算法和信号处理方法【2 2 1 。 由于s v m 算法的潜在应用价值，吸引了国际上众多的知名学者，出现了许多 发展和改进的支持向量机算法和有关非线性支持向量机中核的研究方法。值得一 提的是：s m o l a 彪d 在他的博士论文中详细研究了支持向量机算法中各种核的机理 和应用，为进一步完善非线性支持向量机算法做出了重要的贡献。 支持向量机在模式识别已经有了一些应用，如手写体数字识别【2 3 1 ，人脸识别 与人脸检i 贝 j 【2 4 1 ，以及文本分类【1 0 ，2 5 1 等各种领域。此外，支持向量机还很好地应用 于时间序列分析和回归分析等领域的研究。例如，m i t 、b e l ll a b 和微软研究所等 已成功地将支持向量机应用于动态图像的人脸跟踪，信号处理，语音识别，图象 分类和控制系统等诸多领域。 1 8 基于s v m 的数据挖掘分类技术研究 3 2 1 最优分类面 3 2 支持向量机的原理 s v m 4 , 5 , 2 6 , 2 7 j 是从线性可分情况下的最优分类面提出来的，其基本思想可用图 3 1 所示的二维两类线性可分情况来说明。图中实心点和空心点分别表示两类的训 练样本，h 为把两类没有错误地分开的分类线，h i ，h 2 分别为过各类样本中离分 类线最近的点且平行于分类线的直线，h i 和h 2 之间的距离叫做两类的分类空隙或 分类间隔( m a r g i n ) 。所谓最优分类线就是要求分类线不但能将两类无错误地分开， 而且要使两类的分类空隙最大。前者是保证经验风险最小，而通过后者的讨论可 以看到，使分类空隙最大实际上就是使推