（运筹学与控制论专业论文）支持向量机模型和算法研究.pdf

大连理工大学硕士研究生学位论文 摘要 随着计算机和信息技术的快速发展，人们需要花费昂贵的代价收集、存储和处理海 量的数据。如何从中发现有用的信息，已经成为一个迫切需要解决的问题，数据挖掘技 术在这种背景下应运而生数据挖掘就是在数据库中发现有用的、潜在的、最终可理解 的模式的非平凡过程。它是一门交叉学科，涉及机器学习、数学规划、数理统计、模式识 别等相关技术 数学规划在机器学习、网络问题、工程机械学等领域有着广泛的应用。其和数据挖 掘技术的结合已使大规模和高复杂性的问题的解决成为可能，并在特征提取、聚类和回 归等方面有很重要的应用支持向量机是数学规划在数据挖掘领域的一个重要应用，是 由v a p n i k 等人根据统计学习理论提出的一种新的机器学习方法 本文主要研究了支持向量机模型和算法中的几个问题。首先对分类中分离错误最小 化问题的模型进行分析。鉴于它的不可微性，提出利用极大熵函数将问题转化成易于用 现有优化算法直接计算的形式，并通过算法实现得到了较好的逼近效果。 另外目前支持向量机模型性能研究主要集中在一次损失函数的情况，对于二次损失 函数支持向量机性能了解很少本文对两种不同损失函数支持向量机应用于普通分类和 特殊的非平衡分类的性能差别给出了分析，得到了较一般的结论。并基于支持向量机分 类原理的分析提出了一种基于拟牛顿( d f p ) 方法的非平衡分类问题的分类器改进算 法。 关键词：支持向量机；支持向量；极大熵方法；不平衡问题；分离超平面；拟牛顿法 姜翠萍：支持向量机模型和算法研究 s t u d i e so f 必l t h e m a t i c a lm o d e l sa n do p t i m a t i m a la l g o r i t h m s o fs u p p o r tv e c t o rm a c m n e a b s t r a c t 、v i t ht h ed e v e l o p m e n to fc o m p u t e ra n di n f o r m a t i o n a lt e c h n o l o g y , m o r ea n dm o r e p r i c en e e dt ob ep a i df o rc o l l e c t i n g ，s t o r i n ga n dp r o c e s s i n gv a s td a t a c o n s e q u e n t l y , h o wt of i n du s e f u li n f o r m a t i o nf r o ms e t so fd a t ab e c o m e sap r o b l e mn e e dt ob es o i v e d i m m i n e n t l y d a t am i n i n gt e c h n o l o g yc o m e si n t ob e i n gi nt h i sb a c k g r o u n d k d di sa n o n - t r i v i a lp r o c e s ss e a r c h i n gf o ru s e f u l ，p o t e n t i a la n du n d e r s t a n d a b l ef o r mf r o ms e t so f d a t a i ti n v o l v e sal e to fi n t e r e r o s ss u b j e c t sa n dt e c h n o l o g i e ss u c ha sm a c h i n el e a r n i n g ， m a t h e m a t i c a lp r o g r a m m i n g ，s t a t i s t i c s ，p a t t e r nr e c o g n i t i o na n ds o0 1 1 m a t h e m a t i c a lp r o g r a m m i n gi sa ni m p o r t a n tb r a n c ho fo p e r a t i o n a lr e s e a r c h i t sa p - p f i c a t i o n sc a l lb es e e ni nm a n ya r e a s ，s u c ha sm a c h i n el e a r n i n g ，n e t w o r k sp r o b l e m ，m e - c h a n i c s e s p e c i a l l y , c o m b i n i n gi tw i t hd a t am i n i n gm a k e si tp o s s i b l et os o l v el a r g e - s c a l e a n dc o m p l i c a t e dp r o b l e m sa n di th a sa l s ob e e ns u c c e s s f u l l ya p p h e dt of e a t u r es e l e c t i o n ， c l u s t e r i n ga n dr e g r e s s i o n s u p p o r tv e c t o rm a c h i n ei so n eo ft h ei m p o r t a n tr e s u l t so fa p - p i y i n gm a t h e m a t i c a lp r o g r a m m i n gt od a t am i n i n ga n di ti sam a c h i n el e a r n i n gm e t h o d t h a tw a sb r o u g h to u tb yv v a p n i ka c c o r d i n gt os t a t i s t i ct h e o r y t h i sp a p e rm a i n l ys t u d i e st w op r o b l e m so fm a c h i n el e a r n i n g o n eo ft h e mi sa f u n d a m e n t a lp r o b l e mo fm a c h i n el e a m l g ，i e ，m i e c l a s s i f i c a t i o nm i n i m i z a t i o n s i n c et h e o b j e c t i v ef u n c t i o ni sn o td i f f e r e n t i a b l e ，ac o n v e xe n t r o p yf u n c t i o ni su s e dt os o l v et h e p r o b l e m ，a n dt h eb e a u t i f u lp r o x i m a ls o l u t i o ni sa c h i e v e dt h r o u g ht h ea l g o r i t h mo ft h e c o n v e xp r o g r a m m i n g ， t i l ln o w ，t h es t u d i e so fs v mi sm a i n l yo ns t a n d a r dm o d e l ，f e wi s s u e sr e l a t e dt os v m w i t hs q u a r ec o s tf u n c t i o n ，w h i c hi st h eo t h e rp r o b l e ms t u d i e di nt h i sp a p e r ，h a v eb e e n s e e n i nt h i sp a p e r t h ep e r f o r m a n c eo fs v mw i t hs q u a r ec o s tf u n c t i o ni sc o m p a r e dw i t h t h a to ft h es t a n d a r ds v m a n ds o m er e s u l t sa r eo b t a i n e d m e nt h et w o - c l a s sp r o b l e m s a m p l e sa r ev e r yu n b a l a n c e d s v mh a sap o o rp e r f o r m a n c e a c c o r d i n gt ot h ea n a l y s i s o ft h es u p p o r tv e c t o rm a c h i n et h e o r y , a ni m p r o v e ds v mi sp r e s e n t e db a s e do no n eo f q u a s i - n e w t o na l g o r i t h m s ( d f p ) k e yw o r d s ：s u p p o r tv e c t o rm a c h i n e s ；s u p p o r tv e c t o r ；m a x i m u me n t r o p ym e t h o d ； u n b a l a n c e dd a t ac l a s s i f i c a t i o n ；s e p a r a t i o nh y p e r p l a n e ；d f pa l g o r l t h m u 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工作 及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学 或其他单位的学位或证书所使用过的材料。与我一同工作的同志对本研究所 做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名日期： 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文 作者签名 导师签名： 茎望盛 雹髫纷 丝 年! ! 月日 4 7 大连理工大学硕士研究生学位论文 引言 数据挖掘( d a t am i n i n g 简称d m ) 一词首次出现在1 9 8 9 年8 月举行的第1 1 届国际 联合人工智能学术会议上。迄今为止，会议规模由原来的专题讨论会发展到国际学术大 会，研究重点也逐渐从发现方法转向于系统应用，并且注重多种学科之间的相互渗透， 成为当前计算机科学界的一大热点经过十几年的研究和实践，数据挖掘技术已经吸收 了许多学科的最新研究成果从而成为独具特色的研究领域。一批具有挑战性和前瞻性的 问题被提出，吸引越来越多的研究者。 目前，数学规划已经成功地应用于许多数据挖掘问题数学规划思想在解决特征提 取、聚类、分类等问题已经显示了它的影响力。现今新兴起的支持向量机方法( s u p p o r t v e c t o rm a c h i n e 简称s v m ) 就是数学规划在数据挖掘中一个很好的应用，是一种更为 简便也更为重要的的分类方法它是由v a p n i k 领导的实验室研究小组提出的建立在结 构风险最小化原则( s t r u c t u r a lr i s km i n i m i z a t i o ni n d u c t i v ep r i n c i p l e ) 基础之上的一种 新型通用的有监督的机器学习方法。 支持向量机具有很强的学习能力和泛化性能，能够较好地解决小榉本、高维数、非 线性、局部极小等问题，可以有效地进行分类、回归、密度估计等由于有这些优点，支 持向量机已成为机器学习领域的研究热点目前，支持向量机已经成功的应用于三维物 体识别、时间序列分析、文本自动分类、遥感图像分析、人脸检测、手写体数字识别、蛋 白质结构预测等诸多方面 支持向量机作为一门新兴的分类技术，在许多问题上有着其它技术难以比拟的优越 性，并在模式识别、函数逼近和非线性系统控制等方面有很好的应用。但其尚未成熟， 仍有很多方面需要进一步的改进和完善 分离错误最小化是分类问题的个基本问题，在文献【1 ，2 给出了它的原模型，并联 合特征选择建立模型，给出一种逼近算法本文将鉴于其原模型的不可微性，利用极大 熵函数给出一种全局逼近算法，并希望通过数值实验得到很好的数值结果 目前支持向量机用于分类问题模型的研究主要集中在一次损失函数的情况，对二次 损失函数支持向量机模型的性能了解得还较少但损失函数形式的不同必然会在一些问 题上体现出不同的分类效果本文将对于两种不同损失函数的支持向量机在普通分类和 较特殊的非平衡分类究竟哪种模型体现的性能更好一些给出理论分析，得出了两种损失 函数支持向量机分类平面与支持向量分布以及参数c 的选择的关系，得出较一般的结 论。并利用人造数据进行实验验证得出结论的正确性 标准支持向量机因为其优秀的推广能力已被广泛的用于解决复杂分类和回归问题 然而标准的s v m 需要求解费时的二次规划问题，因此很难胜任大样本集的数据挖掘问 题文献f 3 】提出了一种更为简便、快捷的分类器；p s v m 由于p s v m 只需求解线性 等式组，因此分类器算法非常简单，快速，特别适应海量数据。然而对于不平衡分类问题 由于p s v m 对两类的样本误差的惩罚都是一样的，因此如果分类的样本严重不对称，即 1 姜翠萍：支持向量机模型和算法研究 两类的样本点数相差较大时，p s v m 过拟和数据点较多的一类，而低估数据点数较少一 类的错分误差，从而降低p s v m 的整体分类性能为此，文献 4 给出了一种模型改进 方法，只考虑了错分样本对分类面的影响，同时通过两类错分样本数自适应的惩罚来弥 补两类样本点数的差异。邓乃扬老师在数据挖掘的新方法一支持向量机中也提到 了采用对一次损失函数模型中两类集合训练点的松弛项采取不同的惩罚参数的方法来弥 补类别上的差异本文则在修改p s v m 模型的基础上提出了一种基于拟牛顿( d f p ) 算法的提高分类非平衡样本集的性能的新的分类器改进算法( d f p - 2 p s v m ) 。 本文通过模型分析、改进和算法的具体实施，将数学规划，尤其是优化技术应用于 支持向量机分类，提高了效率、速度和可靠性，使得s v m 技术能够更好的用来处理数 据，这是本文的主要目的之一。 2 大连理工大学硕士研究生学位论文 1 数据挖掘 1 1 数据挖掘技术 数据挖掘技术作为新兴的多学科交叉应用领域【5 】，在各行各业的决策支持活动中扮 演越来越重要的角色。它融合了数据库、人工智能、机器学习、统计学等多个领域的理 论知识和技术，利用各种分析工具和在海量数据中发现模型和数据间的关系。使用这些 模型和关系可以进行预测，帮助决策者寻找数据间潜在的关联，发现被忽略的因素，因 而被认为解决当今时代所面临的数据爆炸而信息贫乏问题的一种有效方法。 1 1 1 数据挖掘的起源 随着计算机技术尤其是数据库技术应用的日益普及，人们面临着快速扩张的数据海 洋，如何有效的利用丰富的数据海洋宝藏，已成为信息技术工作者所关注的焦点之一。 人们开始考虑：4 如何才能不被信息淹没，而是从中及时发现有用的知识，提高信息利 用率。”我们希望运用一种技术从这些数据中挖掘出有用的知识来。数据挖掘技术便在这 种情况下应运而生 数据挖掘技术实际是人们长期对数据库进行研究和开发的结果。数据库技术最初用 于实现对大量数据的统一储存，并提供对数据的查询、插入、删除等事务性操作随着 大量历史数据的积累，人们不满足只是简单的查询和修改数据，而是希望能够发现数据 之间的潜在的关系因此，对数据库提出了新的要求，随着一些相关的学科和研究领域 的逐渐成熟，以及现实世界中商业竞争压力的日渐残酷，企业急切的希望通过快速处理 这些数据获得有利于企业进一步发展的决策依据而是否能够最大限度地使用信息资源 来管理和影响企业的决策流程，将决定企业是否能拥有最大程度的竞争优势，数据挖掘 技术于是出现了，并得到快速的应用。 数据挖掘可以应用在各个不同的领域，能够对将来的趋势和行为进行预测，从而很 好的支持人们的决策如银行可以使用数据挖掘发现有价值的客户，保险公司和证券公 司可以使用数据挖掘来检测欺诈行为等等 1 1 2 数据挖掘的概念 数据挖掘( d a t a m i n i n g 简称d m ) ，简单的讲就是从大量的数据库中挖取或抽取出 有用的知识，郎从大量的，不完全的，有噪声的，模糊的，随即的实际应用数据中发现隐 3 姜翠萍：支持向量机模型和算法研究 含的、规律性的、人们事先未知的，但又是潜在的有用的并且最终可以理解的信息和知 识的非平凡过程。 当然，数据挖掘并没有一个完全统一的精确定义。在不同的文献或者应用领域也有 一些其它的定义。如z e k u l i n 定义数据挖掘是一个从大型数据库中提取以前未知的，可以 理解的，可执行的信息，并用它来进行关键的商业决策的过程；f e r r u z z a 定义数据挖掘 是用在知识的发现过程中。来辨识存在于数据中的未知的关系和模式的一些方法；j o h n 则定义数据挖掘是发现数据中有益模式的过程；p a r s a y e 则认为数据挖掘是我们为那些 未知的信息模式而研究大型数据集的一个决策支持过程。这些定义主要从数据挖掘的商 业应用出发，从此角度看，数据挖掘的主要特点是对商业数据库中的大量的事务数据进 行抽取转化分析和模式化处理，从中提取商业决策的关键知识，即从数据库中自动发现 相关商业模式。 数据挖掘是一个利用各种分析工具在海量数据中发现模型和数据间的关系的过程。 通常也称为k d d ( k n o w l e d g ei nd a t a b a s e ) 一数据库中的知识发现。精确的说，在 k d d 中进行知识学习的阶段称为数据挖掘数据挖掘是k d d 中一个非常重要的处理步 骤，但人们通常不加以区别这两个术语 另外数据挖掘也是一门交叉学科，融合了数据库、人工智能、机器学习、统计学等 多个领域的理论和技术数据库、人工智能和数理统计是数据挖掘的三根强大的技术支 柱，数据挖掘的方法和数学工具包括统计学、决策数、神经网络、模糊逻辑、线性规划 等。我们主要关注数据挖掘的数学规划，特别是优化方法当前，许多领域大量不同的 问题可以作为数学规划问题被公式化并有效地得到解决，例如，运筹研究1 6 一、神经网 络问题 s , g l 、博弈理论与经济学1 1 0 ，“、工程机械学 1 2 , 1 s 1 。1 8 世纪伟大的数学家e u l e r 说：“任何宇宙中发生的事件都包含某种极大或极小。”通过数学规划解决数据挖掘问 题成为近几年来新兴的研究领域【1 4 ，1 日 本文主要以统计学习理论为基础，以数学规划为手段，对数据挖掘中的支持向量机 模型和算法进行研究。 1 2 数据挖掘的分类 数据挖掘系统利用的技术越多，得出的结果的精确性就越高原因很简单，对于某 一个技术不适应的问题，其他方法却可能奏效，这主要取决于问题的类型以及数据的类 型和规模。 数据挖掘涉及的学科领域和方法很多，有多种分类方法，根据挖掘的任务主要分为 分类分析( 包括二分类和多分类问题) 、聚类分析、关联分析、偏差分析、统计预测等， 其中分类分析是本文研究的重点。 分类分析 预言模型【1 q 以通过数据库中的某些数据得到另外的数据为目标，若预言的模型是 4 大连理工大学硬士研究生学位论文 离散的这类问题就称为分类分类一直为人们所关注，它是一种有监督的学习方法，即 已知数据的类别是确定的。数据挖掘以往广泛使用的方法有决策树、神经网络、径向基 函数等而现今新兴起的支持向量机方法( s v m ) 是v a p n i k l l 7 , 1 8 等人根据统计学习理 论提出的一种新的机器学习方法，是数学规划在数据挖掘领域的一个重要应用 通过学习算法，支持向量机可以自动寻找那些对分类有较好区分能力的支持向量， 由此构造出的分类器可以最大化类与类的间隔，因而有较好的推广性能和较高的分类准 确率其主要思想是针对两类分类问题给定空间中的两类点的集合，构造模型并对其 求解从而寻找一个超平面作为两类的分割，以保证最小的分类错误率常见的分类问题 有线性可分、线性不可分和非线性可分情况。 通常的分类方法对于非线性分类问题的处理具有一定的局限性而支持向量机一个 重要的优点就是可以处理非线性可分的情况其从原始空间中抽取特征，将原始空间中 的样本映射为高维特征空间中的一个向量，以解决原始空间中非线性问题 对于支持支持向量机的具体理论和算法，将在第二章给出 聚类分析 聚类是把一组个体按照相似性归成若干类别，与分类不同，聚类中没有明显的目标变 量作为数据的属性存在它的目的是使得属于一个类别的个体之间的距离尽可能的小， 而不同类别个体间的距离尽可能的大 关联分析 关联分析描述了这样的一种方法，它的目的在于生成部分数据的概要，例如寻找数 据子集问的关联关系或者一些数据与其数据之间的派生关系本领域最常见的技术是利 用关联规则关联规则是由r - a g r a wa l 等人在文献【1 8 】中提出的最初开始应用于购物 篮分析，在商场或超市对商品进行相关分析 偏差分析 偏差分析也称为孤立点分析，可以在众多的数据、对象或模式中发现与多数数据、 对象或模式有显著差异的、异常的或不一致的数据、对象或模式，偏差分析可以帮助人们 找出异常，进而研究异常后面隐藏的原因偏差分析方法可以分为三类，统计学方法， 偏于距离的方法和基于偏移的方法 统计预测 统计预测是通过以往数据的分析，找到规律，来预计未来的趋势常用方法有时间 序列，回归分析等 1 3 数据挖掘的应用和发展前景 d m 工具和软件已在各个部门得到很好的应用，并收到明显的效益 1 ) 金融方面；银行信用卡和保险行业，预测存贷款趋势，优化存贷款策略，用 d m 将市场分成有意义的群组和部门，从而协助市场经理和业务执行人员更好地集中于 5 姜翠萍：支持向量机模型和算法研究 有促进作用的活动和设计新的市场运动 2 ) 在客户关系管理方面：d m 能找出产品使用模式或协助了解客户行为，从而可以 改进通道管理( 如银行分支和a t m 等) 又如正确时间销售( m g h tt i m em a r k e t i n g ) 就是基于顾客生活周期模型来实旌的。 3 ) 在零售业市场营销方面：这是数据挖掘技术应用最早也是最重要的领域，d m 用于顾客购货篮的分析可以协助货架布置，促销活动时间，促销商品组合以及了解滞销 和畅销商品状况等商业活动通过对一种厂家商品在各连锁店的市场共享分析，客户统 计以及历史状况的分析，可以确定销售和广告业务的有效性 4 ) 在过程控制质量监督保证方面：d m 协助管理大数量变量之间的相互作用， d m 能自动发现出某些不正常的数据分布，暴露制造和装配操作过程中交化情况和各种 因素，从而协助质量工程师很快地注意到问题发生范围和采取改正措施 5 ) 在远程通讯部门；基于d m 的分析协助组织策略变更以适应外部世界的变化， 确定市场变化模式以指导销售计划在网络容量利用方面，d m 能提供对客户组类服务 使用的结构和模式的了解，从而指导容量计划人员对网络设施做出最佳投资决策 6 ) 生物制药行业；从各种文献资料中自动抽取有关化学反应的信息，发现新的 有用化学成分在遥感领域针对每天从卫星上及其它方面来的巨额数据，对气象顼报， 臭氧层监测等起到很大作用 当前，d m 研究方兴未艾，预计在2 1 世纪还会形成更大的高潮，研究焦点可能会 集中到以下几个方面： a ) 研究专门应用于知识发现的数据挖掘语言，也许会像s q l 语言一样走向形式化 和标准化； b ) 寻求数据挖掘过程中的可视化方法，使得知识发现的过程能够被用户理解，也便 于在知识发现过程中的人机交互； c ) 研究在网络环境下的数据挖掘技术，特另日是在i n t e r n e t 上建立d m 服务器，与 数据库服务器配合，实现数据挖掘； d ) 加强对各种非结构化数据的挖掘，如文本数据、图形图像数据、多媒体数据 但是，无论怎样，需求牵引，市场驱动是永恒的，d m 将首先满足信息时代用户的 急需，大量基于d m 的决策支持软件工具产品将会问世 6 大连理工大学硕士研究生学位论文 2 支持向量机 第一章提到了支持向量机( s u p p o r tv e c t o rm a c h i n e 简称s v m ) 是一种新型通用的 机器学习方法【1 9 它建立在结构风险最小化原则基础之上 2 0 1 ，具有很强的学习能力是 数据挖掘中的一项新技术。其主要借助于最优化方法解决数据挖掘中的分类问题，是数 据挖掘技术中个新的研究热点本章先简要介绍支持向量机方法的理论基础，然后对 支持向量机的知识背景、模型的导出与求解以及一些主要的算法给出比较详细的阐述 2 1支持向量机的理论基础 基于数据的机器学习是现代智能技术中的重要方面，研究从观测数据( 样本) 出发 寻找规律，利用这些规律对未来数据或无法观测的数据进行预测包括模式识别、神经 网络等在内，现有机器学习方法共同的重要理论基础之一是统计学传统统计学研究的 是样本数目趋于无穷大时的渐近理论，现有学习方法也多是基于此假设。但在实际问题 中，样本数往往是有限的，因此一些理论上很优秀的学习方法实际中表现却可能不尽人 意。 与传统统计学相比，统计学习理论( 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 ) 是一种专 门研究小样本| 2 1 情况下机器学习规律的理论。v ，v a p n i k 等人从六、七十年代开始致力 于此方面研究，到九十年代中期，随着其理论的不断发展和成熟，也由于神经网络等学 习方法在理论上缺乏实质性进展，统计学习理论开始受到越来越广泛的重视。 它是建立在一套较坚实的理论基础之上的，为解决有限样本学习问题提供了一个统 一的框架它能将很多现有方法纳入其中，有望帮助解决许多原来难以解决的问题( 比 如神经网络结构选择问题、局部极小点问题等) ；同时，在这一理论基础上发展了一种新 的通用学习方法一支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) ，它已初步表现出很 多优于已有方法的性能。一些学者认为，s l t 和s v m 正在成为继神经网络研究之后新 的研究热点，并将有力地推动机器学习理论和技术的发展 2 1 1 机器学习的基本问题 机器学习的目的是根据给定的训练样本求对某系统输入输出之间依赖关系的估计， 使它能够对未知输出作出尽可能准确的预测可以一般地表示为：变量y 与z 存在一定 的未知依赖关系，即遵循某未知的联合概率p ( z ，y ) ( x 和y 之间的确定性关系可以看 7 姜翠萍：支持向量机模型和算法研究 作是其特例) 。 机器学习问题就是根据n 个独立同分布观测样本 ( 石1 ，y 1 ) ，( 勋，珈) ，z 在一组函数，( z ，w ) 中求个最优的函数，( 。，w o ) 对依赖关系进行估计使期望风险【1 9 】 r ( ) = 工( 玑， ，w ) ) d p ( x ，y ) ( 2 1 1 ) 最小。其中，( 茁，”) 称作预测函数集，w 为函数的广义参数，( z ，w ) 可以表示任何函 数集；l ( y ，( z ，伽) ) 为由于用，( 。，w ) 对y 进行预测而造成的损失，不同类型的学习问 题有不同形式的损失函数。 对模式识别问题，输出y 是类别标号，两类情况下y = o ，1 ) 或 1 ，一1 ) ，预测函数 称作指示函数损失函数可以定义为： 砌川删= 篡驾 皿， 学习的目的就是通过选择个参数w ，使得学习系统的输出，( z ，w ) 与期望输出y 之间 的误差概率最小化，即出错率最小化。出错率也称为期望风险( e x p e c t e dr i s k ) ，如下 式定义： r ( w ) = 言js ，一，( 五w ) l d p ( x ，y ) ( 2 1 3 ) 其中尸( z ，y ) 为样本空间的实际概率分布。由于p ( x ，y ) 通常是未知的，因此无法直接计 算r ) 但是，对给定的训练集，其经验风险( e m p i r i c a lr i s k ) 见知) ： 1 z 兄，( u ) = 击l 虮一m 删) i ( 2 1 4 ) 却是确定的。其中( 托，y 1 ) 为训练样本，f 为训练集中样本数，e p uz l 练集规模。由数理统 计中的大数定理可知，随着训练集规模的扩大，见，) 将逐渐收敛于r ( w ) 。 通过上面表述可以看出，学习的目标在于使期望风险最小化，但是由于我们利用样 本信息期望风险并无法计算，而对于给定的样本其经验风险确是给定的，因此我们考虑 用经验风险来作为期望风险的一个估计，设计算法使它最小化。 事实上，用经验风险代替期望风险最小化并没有经过充分的理论论证，只是直观上 合理的想当然做法，但这种思想却在多年的机器学习方法研究中占据了主要地位人们 多年来将大部分注意力集中到如何更好地最小化经验风险上。而实际上，即使可以假定 当n 趋向于无穷大时( 2 1 4 ) 趋近于( 2 1 3 ) 式，在很多问题中的样本数目也离无穷 大相去甚远。那么在有限样本下得到的结果能使真实风险也较小吗? 这是我们需要考虑 的问题 8 大连理工大学硕士研究生学位论文 上面提到的问题不成功的一个例子是神经网络的过学习问题开始，很多注意力都 集中在如何使r e m p ( w ) 更小，但很快就发现。训练误差小并不总能导致好的预测效果， 某些情况下，训练误差过小反而会导致推广能力的下降，即真实风险的增加，这就是过 学习问题之所以出现过学习现象，一是因为样本不充分，二是学习机器设计不合理 这两个问题是互相关联的。 在神经网络中，对有限的样本来说网络学习能力过强，足以记住每个样本，此时经验 风险很快就可以收敛到很小甚至零，但却根本无法保证它对未来样本能给出好的预测。 学习机器的复杂性与推广性之间的这种矛盾同样可以在其它学习方法中看到。文献 2 2 给出了一个实验例子。由此可看出，有限样本情况下： 1 ) 经验风险最小并不一定意味着期望风险最小。 2 ) 学习机器的复杂性不但应与所研究的系统有关，而且要和有限数日的祥本相适 应 我们需要一种能够指导我们在小样本情况下建立有效的学习和推广方法的理论，统 计学习理论便在这种背景下应运而生。 2 1 2 统计学习理论的核心内容【1 8 】 统计学习理论就是研究小样本统计估计和预测的理论【4 】，主要内容包括四个方面 1 ) 经验风险最小化准则下统计学习一致性的条件； 2 ) 在这些条件下关于统计学习方法推广性的界的结论； 3 ) 在这些界的基础上建立的小样本归纳推理准则； 4 ) 实现新的准则的实际方法( 算法) 其中，最有指导性的理论结果是推广性的界与此相关的个核心概念是v c 维 为了研究学习过程一致收敛的速度和推广性1 2 2 ，2 3 ，2 4 1 ，统计学理论定义了一系列有关 函数学习性能的指标，其中最重要的是v c 维【2 5 2 q ( v a p n i kc h e r v o n e n ki sd i m e n s i o n ) 。 模式识别方法中v c 维的直观定义是：对一个指示函数集，如果存在h 个样本能够 被函数集中的函数按所有可能的2 h 种形式分开，则称函数集能够把h 个样本打散；函 数集的v c 维就是它能打散的最大样本数目h 若对任意数目的样本都有函数能将它们 打散，则函数集的v c 维是无穷大有界实函数的v c 维可以通过用一定的阈值将它转 化成指示函数来定义 v c 维反映了函数集的学习能力，v c 维越大则学习机器越复杂( 容量越大) 。遗憾 的是，目前尚没有通用的关于任意函数集v c 维计算的理论，只对一些特殊的函数集知 道其v c 维比如在佗维实数空间中线性分类器和线性实函数的v c 维是凡+ 1 ，而上 一节例子中，( a ) = s i n ( a x ) 的v c 维则为无穷大。对于给定的学习函数集，如何( 用 理论或实验的方法) 计算其v c 维是当前统计学习理论中有待研究的一个问题 统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之间的关 系，即推广性的界。关于两类分类问题，结论是；对指示函数集中的所有函数( 包括使经 9 姜翠萍：支持向量机模型和算法研究 验风险最小的函数) ，经验风险r e m p ( w ) 和实际风险r ( ) 之间以至少l 一仉0 q o 3 7 时这个界肯定是松弛的，当v c 维无穷 大时，这个界就不再成立) 而且，这种界只在对同一类学习函数进行比较时有效，可以 指导我们从函数集中选择最优的函数，在不同函数集之间比较却不一定成立。 风硷 受：_ 弱皴嶷乎集t 受c s i c 岛 v c 箍 l 矗l 如 图2 1 有序风险最小化示意图 从上面的结论看到，在样本有限时我们需要同时最小化经验风险和置信范围i 圳 其实，在传统方法中，选择学习模型和算法的过程就是调整置信范围的过程，如果模型 1 0 大连理工大学硕士研究生学位论文 比较适合现有的训练样本，则可以取得比较好的效果。但因为缺乏理论指导，这种选择 只能依赖先验知识和经验统计学习理论提出了一种新的策略，即把函数集s = ，( z ，w ) 构造为一个函数子集序列t s 1cs 2c 。c 船c 使各个子集按照v c 维的大小排列： 危1 九2 - - 危女 这样在同一个子集中，置信范围就相同。选择经验风险和置信范围之和最小的子集，就 可以使期望风险最小这种思想称作结构风险最小化( 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 支持向量机模型 支持向量机( s u p p o r tv e c t o rm a c h i n e 简称s v m ) 由v a p n i k 等人根据统计学习 理论提出的一种新的机器学习方法，它建立在结构风险最小化原则( s r m ) 基础之上 1 2 8 】，是统计学习理论中最年轻的内容。具有很强的学习能力和泛化性能，能够较好地解 决小样本、高维数、非线性、局部极小等问题，可以有效地进行分类、回归、密度估计等 【3 j 由于有这些优点，支持向薰机已成为机器学习领域的研究热点目前，支持向量机 已经成功的应用于三维物体识男、时间序列分析、文本自动分类、遥感图像分析、人脸 检测、手写体数字识别、蛋白质结构预测等诸多方面 2 2 1 支持向量机的基本思想 前面提到支持向量机是解决分类问题的一种新兴起的方法，但分类问题并不是新问 题，是数据挖掘的迅速发展赋予它新的意义，再次引起人们的注意支持向量机在分类 问题中的优势也逐渐的体现出来 文献 17 】中心脏病诊断的例子提出分类问题的数学描述及支持向量机思想的提出 其本质就是在于寻找一个把掣空间的点分成两部分的规则基本思想由图2 中简单的 现性可分的问题来说明图( 2 2 ) 中，实心点和空心点代表两类样本，h 为分类超平 面，噩，三如分别代表各类中离日最近的样本且平行与日的面，它们之间的距离称为 分类间隔( m a r g i n ) 所谓最优化分类面就是要求不但能将两类正确分开，而且使分类 间隔最大 1 1 姜翠萍：支持向量机模型和算法研究 假定大小为l 的训练样本集 ( z i ，玑) ，甄，鼽 + l ，一1 ) ，i 1 f ) 由两个类别组成，如果x l 尉属于第一类，则标记为正( 玑= 1 ) ，否则，标记为负 ( 玑= - - 1 ) 。支持向量机的目的在于寻找分类超平面日： 叫t z + r = 0 使得样本集满足 y i ( w t 托一r ) 一1 0 ，i 1 ，- 一，z ) ( 2 2 1 ) 则此超平面可以将两类点分开。 点z 到超平面日的距离为 图2 2 线性可分情况下的分类线 地n z ) = 可i ( w r x l ) + r 根据最优分类超平面的定义，分类间隔可以表示为： j 口( 叫，r ) 。r a 蝌i n ，掣十瓴密。，帮 = 盎 使间隔最大等价于使l iw | | 最小则求最优分类超平面问题就转化为求在满足条件( 2 2 1 ) 且使0 甜0 最小的数学规划问题 大连理工大学硕士研究生学位论文 2 2 2 支持向量机模型 a 、线性支持向量机 上面已经提到了线性可分问题，并用来解释了支持向量机的基本原理。在现性可分 的情况下，设( 孔，玑) 2 1 r 4 + 1 ，一1 是二分类问题的训练样本，我们采用最大间隔 的思想得到的数学优化模型： 呼j 伽l 陋2 1 们 f 9 1 s t 玑( 叫t 孔一r ) 1 ，i 1 ，- t ，2 ) 、。 其中伽彤为分类超平面的法向量，r r 为阀值 对于上述优化问题，其最优解可以通过求解它的拉格朗日对偶问题的解得到为此， 可以定义下面的拉格朗日函数： 1 z 三( ”，_ 。) = ；( 甜丁彬) 一。( 虢( 叫2 k - r ) 一1 ) ( 2 2 3 ) 一 i = 1 其中，啦 0 为拉格朗日系数把式( 2 2 3 ) 分另对w 和r 求偏微分并另他们等于0 ， 可以得到； 掣：m 一壹脚i ：0 ( 2 2 4 ) d _ 。 、 掣：壹玑：o a r 厶i = l “。 由( 2 2 4 ) 和( 2 2 5 ) 可得到 将上面两个式子代入( 2 2 3 ) 可得到相应的对偶形式 使得 ( 2 2 5 ) ( 2 2 6 ) ( 2 2 7 ) 警撕，) = 妻一；妻玑协酬) ( 2 z 8 ) f 。i 0 ，啦鼽= o ，f m ，2 t = l 1 3 ( 2 2 9 ) z 玑 。：lf = 叫 0 一一玑 ；谢 姜翠萍：支持向量机模型和算法研究 这样，求最优分类面问题就转化为对啦求解下面的优化问题； m 。i n ；乞：。啦玑巩( 以巧) 一：，d i s ，t 0 ：i 0 ，i 1 ，f ) ( 2 2 1 0 ) ：；1 啦玑= 0 其中血i 是与每一个样本对应的拉格朗日乘子这是一个不等式约束的二次寻优问题，存 在唯一的解o + = ( n ；，；，血；) 。则得到 z w + = 衄+ y i x i ( 2 2 1 1 ) z j 、 i = 1 且由k k t 定理可知，最优解满足： a ；( 玑( ? 如一r ) 一1 ) = 0( 2 2 1 2 ) 因此，对于多数样本将为零，最优解只依赖那些对应的啦+ 0 的输入，他们通常只 占全体样本的很少一部分我f 1 弓l 入下面的定义： 定义2 1 ( 支持向量) 【1 1 称训练样本集t 中输入翰为支持向量，如果它对应的q + 0 。 求解上述问题后得到的最优分类函数是： z ，( $ ) = s g n ( w + t z + r ) = 8 9 n ( + 弘( 筑。) + r 4 ) ( 2 2 1 3 ) i = 1 由于非支持向量对应的嘭均为零，因此式中的求和实际上只对支持向量进行，而，是 分类的域值 从而有如下的算法： 1 ) 设已知训练集t = ( z 1 ，y 1 ) ，( x 2 ，驰) ，( 盈，肌) ) ，妃刷，挑 + 1 ，一1 ) ，i = l ，2 ； 2 ) 构造并求解最优化问题 鲁“j 1 ：j = 1 。 玑协( 墨+ x j ) d 一 ”一 s t 啦0 ， l ，一，z ) ：1 ( 1 i y l 20 求得最优解a + = ( 0 1 + ，a 2 + ，o f + ) ； 3 ) 计算 w + = + 黼 i = 1 选择n + 的一个正分量a t + ，并计算 l r = 如一啦+ 玑( 茹；) 仁= 1 1 4 乞1 0 i 大连理工大学硕士研究生学位论文 4 ) 由此求的决策函数 ，( 。) = s 弘( + t z ) + r + ) 或 z m ) = s 口( a t 玑( ”士) + r 4 ) i = l 上面给出的是线性可分情况下的模型，而在实际情况中训练样本集多为线性不可分 的这时可以在条件中加入一个松弛项6 0 ，样本点满足得条件相应的改为： 玑( 叫t 嗣一r ) + 矗