（运筹学与控制论专业论文）支持向量机中参数选取的一个问题.pdf

大连理工大学硕士学位论文 摘要 随着计算机和信息技术的快速发展，人们需要花费昂贵的代价收集、存储和处理海 量的数据数据挖掘源于数据库技术引发的海量数据和人们利用这些数据的愿望用数 据管理系统存储数据，用机器学习的方法分析数据、挖掘海量数据背后的知识，便促成了 数据挖掘( d a t am i n i n g ) 的产生如何从中发现有用的信息，已经成为一个迫切需要解决 的问题，数据挖掘技术在这种背景下应运而生数据挖掘就是在数据库中发现有用的， 潜在的、最终可理解的模式的非平凡过程它是一门交叉学科，涉及机器学习、数学规 划、数理统计、模式识别等相关技术 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 是数据挖掘中的一项新技术，是借助于 最优化方法解决机器学习问题的新工具它是机器学习领域若干标准技术的集大成者 它集成了最大间隔超平面，m e r c e r 核，凸二次规划、稀疏解和松弛变量等多项技术在 若干挑战性的应用中，获得了目前为止最好的性能在美国科学杂志上，支持向量机以 及核学习方法被认为是“机器学习领域非常流行的方法和成功的例子，并是一个十分令 人瞩目的发展放向。 首先本文给出了一种新的计算支持向量机中正则参数和核参数的方法，与已有的一 些算法不同，它是将c 和，y 作为优化问题中的变量来处理，并通过遗传算法和确定性 算法相结合来解这个平衡约束优化问题，从而求出支持向量机( s v m ) 在分类问题中的 正则参数c 和1 其中遗传算法用来求解以c 和7 为变量的优化问题，而确定性算 法对每一对d 和7 值求解约束 另外通过数值计算将该方法的的结果与已有的g r i ds e a r c h 方法进行比较，可以得 出用文中所述的方法求得的c 和7 值能明显提高支持向量机的泛化性能 关键词； 数据挖掘；支持向量机；正则参数；核参数；遗传算法 支持向量机中参数选取的一个问题 m e t h o d so f0 p t i m a lc o s ta n dk e r n a lp a ra m e t e r ss e l e c t l 0 ni n s u p p o r tv e c t o rm a c h i n e a b s t r a c t w 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 t h ed a t am i n i n g t e c h n o l o g yc o m e sf r o mt h el a r g ea m o u n to fd a t aw h i c ha r ep r o d u c e db yd a t a b a s et e c h - n o l o g y w eu s et h ed a t am a n a g e m e n ts y s t e mt os t o r et h ed a t a ，u s et h em a c h i n es t u d y m e t h o d st oa n a l y s i sa n de x t r a c tt h eu s e f u lk n o w l e d g eo ft h ed a t a c o n s e q u e n t l y , h o wt o e x t r a c tu 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 l v e di m m i o 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 d a t am i n i n gi 8a 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 o to fi n t e r c 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 si n 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 d o n s u p p o r tv e c t o rm a c h i n ei san e wt e c h n o l o g yo fd a t am i n i n g a n do n eo ft h ei m p o r - t a u tr e s u l t so fa p p l 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 g i ti sa l s oam a c h i n e l e a r n i n gm e t h o dt h a tc o n t a i n ss o m et e c h n o l o g y so ft h em a c h i n el e a r n i n gd o m a i n i tc o n - r a i n st h el a r g e s tm a r g i n gh y p e r p l a n e 、m e r c e rk e r n a l 、c o n v e xp r o g r a m m i n g 、s l a c k v a r i b l e sa n ds u c ht e c h o l o g i e s u n t i ln o wi th a sg o tt h eb e s tp r o p e r t i e si ns o m ec h a l - l e n g a b l ea p p l y i n g s s u p p o r tv e c t o rm a c h i n ea n dt h ek e m a lm e t h o d sa r et r e a t e da s 。t h e m o s tp o p u l a ra n ds u c s s s f u le x a m p l eo ft h em a c h i n el e a r n i n gd o m a i n ，a n dad e v e l o p m e n t d i r e c t i o nw h i c ha t t r a c t ss om a n yp e o p l e sc o n c e r n s ”i nt h ea m e r i c a nm a g z i n e s a tf i r s tam e t h o df o rs e l e c t i n go p t i m a lc o s ta n dk e r n a l p a r a m e t e r sca n d1i ns u p - p o r tv e c t o rm a c h i n e ( s v m ) i 8p r e s e n t e d r h ec o s ta n dk e m a lp a r a m e t e r sa r eo b t a i n e d b ys o l v i n gam a t h e m a t i c a lp r o g r a m w i t he q u i l i b r i u mc o n s t r a i n t s ( m p e c ) v i ac o m b i n i n g t h eg e n e t i ca l g o r i t h ma n dd e t e r m i n i s t i ca l g o r i t h m ，b u tca n d ，ya r et r e a t e da sv a r i a b l e s o fo p t i m i z a t i o np r o b l e mi nt h i sp a p e r t h eg e n e t i ca l g o r i t h mi su s e dt os o l v et h eo p t n m i z a t i o np r o b l e mw i t hr e s p e c tt oc a n d - y a n dd e t e r m i n i s t i ca l g o r i t h mi su s e dt oo b t a i n t h ec o n s t r a i n t so fp r o b l e m a n dt h e nt h er e s u l t ss h o wt h a tt h eg e n e r a l i z a t i o np e r f o r m a n c eo ft h es u p p o r tv e c t o r m a c h i n ec a nb ei m p r o v e dc l e a r l yb yt h ep r o p o s e dm e t h o di nt h i sp a p e rc o m p a r e dw i t h t h eg r i ds e a r c hm e t h o dt h r o u g ht h en u m e r i c a le x p e r i m e n t s k e yw o r d s ：d a t am i n i n g ；s u p p o r tv e c t o rm a c h i n e ；c o s tp a r a m e t e r ；k e r n a lp a r a m e t e r ； g e n e t i ca l g o r i t h m u 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工作 及取得研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学 或其他单位的学位或证书所使用过的材料与我一同工作的同志对本研究所 做的贡献均已在论文中做了明确的说明并表示了谢意 作者签名： 日期：迦丕西 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文 版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅本人授权大连理工大学可以 将本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、 缩印或扫描等复制手段保存和汇编学位论文 作者签名： 导师签名： 大连理工大学硕士学位论文 引言 数据挖掘( d a t am i n i n g ，d m ) 是一种有效利用信息的工具，它主要基于人工智能、 机器学习，统计学等技术，高度自动化地分析组织原有的数据，进行归纳性的推理，从中 挖掘出潜在的模式，预测客户行为，帮助组织的决策者正确判断即将出现的机会。调整 策略，减少风险，进行正确的决策当前，很多成功的企业正在应用数据挖掘来帮助它 们更好地制度决策利用功能强大的数据挖掘技术，可以把数据转化为有用的信息以帮 助制定决策，从而在市场竞争中获得优势地位数据挖掘是一个过程一一是一个不断把 商业经验和知识与数据相结合的过程通过数据挖掘，可以更好地认识所面临的问题并 发现新的市场机会，做出更加明智的决定 随着信息技术的发展，人类集聚的数据量呈几何级数递增如何从这些数据中发掘 出有效的信息而不被信息海洋所淹没已经成为迫在眉睫的问题对数据挖掘相关领域的 研究，例如数据分类、聚类、函数模拟和规则抽取等技术，逐渐成为当前计算机基础技术 研究的重心之一支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 方法作为一种解决多维 函数预测的通用工具，一经提出，便成功地应用于函数模拟、模式识别和数据分类等领 域，并取得了极好的成果，成为当前国际上的一个研究热点 s v m 理论源于v a p n i k 在1 9 6 3 年提出的用于解决模式识别问题的支持向量方法t l , 2 1 这种方法从训练集选择一组特征子集，使得对特征子集的线性划分等价于对整个数据集 的分割这组特征子集称为支持向量s v 在此后近3 0 年中，对s v 的研究主要集中在对 分类函数的改进和函数预测上在1 9 7 1 年，k i m e l d o r f 提出使用线性不等约束重新构造 s v 的核空间 3 1 ，解决了一部分线性不可分问题，为以后的s v m 研究开辟了道路 1 9 9 0 年，g r a c e ，b o s e r 和v a p n i k 等人开始对s v m 技术进行研究，并取得突破性进展【4 s 1 1 9 9 5 年v a p n i k 提出统计学习理论，较好地解决了线性不可分问题，正式奠定了s v m 的 理论基础 支持向量机方法是数学规划在数据挖掘中一个很好的应用，是借助于最优化方法解 决机器学习问题的新工具近年来在其理论研究和算法实现方面都取得了突破性进展， 开始成为克服“维数灾难”和。过学习。等传统困难的有力手段它具有很强的学习能力 和泛化性能并且集成了最大间隔超平面，m e r c e r 核、凸二次规划，稀疏解和松弛变量等 多项技术过学习能够较好地解决小样本，高维数、非线性、局部极小等问题，可以有效 地进行分类、回归，密度估计等由于有这些优点，支持向量机已成为机器学习领域的 研究热点，目前，支持向量机已经成功的应用于三维物体识别时间序列分析，文本自 动分类、遥感图像分析，人脸检测，手写体数字识别，蛋白质结构预测等诸多方面 支持向量机也是一种简便重要的的分类方法但是在很多情况下，训练数据集中的 数据是线性不可分的，为了解决这个问题，于是便引入了松弛变量与核函数，引入松弛 变量的方法就是只考虑了错分样本对分类面的影响，同时通过两类错分样本数自适应的 惩罚来弥补两类样本点数的差异邓乃扬老师在数据挖掘的新方法一支持向量机 l 支持向量机中参数选取的一个问题 中也提到了采用对一次损失函数模型中两类集合训练点的松弛项采取不同的惩罚参数的 方法来弥补类别上的差异引入核函数的方法就是使原本线性不可分的数据点通过一个 映射映射到高维空间成为线性可分的在进行处理通过大量数值实验我们发现核参数与 正则参数的选取对数值结果的影响非常的大，因此如何选择合适的正则参数与惩罚参数 成为一个非常重要的问题 本文通过对模型的分析，将正则参数与核参数看作变量，结合遗传算法选取较为合 适的正则参数与核参数，并与已有的参数选取方法g r i ds e a r e h 方法f 6 】作比较 2 大连理工大学硬士学位论文 1 数据挖掘 1 1 数据挖掘简介 数据挖掘技术作为新兴的多学科交叉应用领域吲，在各行各业的决策支持活动中扮 演越来越重要的角色它是一门交叉学科，它把人们对数据的应用从低层次的简单查询 提升到从数据知识提供决策支持在这种需求牵引下，汇聚了不同领域的研究者，尤其 是数据库、人工智能、数理统计、可视化、并行计算等方面的学者和工程技术人员，投身 到数据挖掘这一新兴的研究领域，形成新的技术热点它利用各种分析工具和在海量数 据中发现模型和数据间的关系使用这些模型和关系可以进行预测任务和描述任务等工 作，帮助组织的决策者正确判断即将出现的机会，调整策略、减少风险、进行正确的决 策 1 1 1 数据挖掘的由来 数据挖掘是适应信息处理新需求和社会发展各方面的迫切需要而发展起来的一种新 的信息分析技术，从早期的数据处理手段到它的出现经过了一个进化过程在这个进化 过程中，对于数据的自动化处理和利用，每一步的前进都是建立在上一步的基础上数 据挖掘技术已经可以快速地回答商业上的很多问题 尽管数据挖掘概念正式出现的时间并不长但是，数据挖掘的核心技术伴随着企业 信息化的进程历经了数十年的发展，包括数理统计、人工智能、机器学习等多个领域的 知识今天，这些成熟的技术，加上高性能的关系数据库引擎以及广泛的数据集成，让 数据挖掘技术在当前的数据仓库环境中进入了实用阶段 数据挖掘可以应用在各个不同的领域，能够对将来的趋势和行为进行预测，从而很 好的支持人们的决策如银行可以使用数据挖掘发现有价值的客户，保险公司和证券公 司可以使用数据挖掘来检测欺诈行为等等 1 1 2 数据挖掘的基本概念 数据挖掘( 蚍i 丑i n 吕d m ) ，是指从大量结构化和非结构化的数据中提取的有用的 信息和知识的过程，它是知识发现的有效手段该概念出现的时间并不长，在1 9 8 9 年 举行的第1 1 界国际联合人工智能学术会议上，人们首次提出了基于数据库中知识发现 ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e k d d ) 技术，并且直到1 9 9 5 年，人们才在美国计算 机年会( a s s o c i a t i o nf o rc o m p u t e r i n gm a c h i n e r y a c m ) 上首次提出数据挖掘的概念 3 支持向量机中参数选取的一个问题 数据挖掘是一个处理过程，它利用一种或多种计算机学习技术，从数据库的数据中 自动分析并提取知识数据挖掘会话的目的是确定数据的趋势和模式数据挖掘所获得 的知识是以一个模型或数据概化的形式给出的尽管现在有多种数据挖掘技术，但所有 的数据挖掘的方法都采用基于归纳的学习( i n d u c t i o n - b a s e dl e a m n g ) ，基于归纳的学习是 通过观察所学概念的特定实例形成一般概念的过程 数据库中的知识发现是一个可与数据挖掘互换的、使用频率很高的术语，k d d 是 数据挖掘科学方法的应用除了执行数据挖掘之外，典型的k d d 处理模型包括一个方 法论，它用来提取和准备数据，以及数据挖掘执行后，对所要采取的行动做出决策当一 个特殊的应用涉及到对存储在多个地方的大量数据进行分析时，数据提取和准备就成为 发现过程中最耗时的部分当数据挖掘成为晋级的涵盖面更广的术语时，我们就不必关 心数据挖掘与k d d 之闯明确的界线 当然，数据挖掘并没有一个完全统一的精确定义在不同的文献或者应用领域也有 一些其它的定义如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 则认为数据挖掘是我们为那些 未知的信息模式而研究大型数据集的一个决策支持过程这些定义主要从数据挖掘的商 业应用出发，从此角度看，数据挖掘的主要特点是对商业数据库中的大量的事务数据进 行抽取转化分析和模式化处理，从中提取商业决策的关键知识，即从数据库中自动发现 相关商业模式 本文主要以优化理论为基础，以数学规划为手段，对数据挖掘中的支持向量机中的 参数选取问题进行研究 1 2 数据挖掘的对象 数据挖掘可以针对任何类型的数据库进行，既包括传统的关系数据库，也包括非数 据库组织的文本数据源、w e b 数据源以及复杂的多媒体数据源等 ( 1 ) 关系数据库 关系数据库因为具有坚实的数据基础、统一的组织结构、完整的规范化理论、一体 化的查询语言等优点，成为当前数据挖掘最重要、最流行也是信息最丰富的数据流， 并且也是人们对数据挖掘研究的主要形式之一 ( 2 ) 数据仓库 数据仓库是数据库技术发展的高级阶段它是面向主题的、集成的、内容相对稳定 的、随时间变化的数据集合，可以用来支持管理决策的制度过程数据仓库系统允许将 各种应用系统、多个数据库集成在一起，为统一的历史数据分析提供坚实的平台 数据挖掘需要有良好的数据组织和“纯净”的数据数据的质量直接影响到数据挖掘 4 大连理工大学硕士学位论文 的效果，而数据仓库的特点恰恰最符合数据挖掘的要求，它从各类数据源中抓取数据 经过清洗、集成、选择，转换等处理，为数据挖掘所需要的高质量数据提供了保证可以 说，数据挖掘为数据仓库提供了有效的分析处理手段，数据仓库为数据挖掘准备了良好 的数据源因此，随着数据仓库与数据挖掘的协调发展，数据仓库必然成为数据挖掘的 最佳环境 ( 3 ) 文本数据库 文本数据库所记载的内容均为文字，这些文字并不是简单的关键词，而是长句子、段 落甚至全文文本数据库多数为非结构化的，也有些是半结构化的如h t m l 、e - m a i l 等w e b 网页也是文本信息，把众多的w e b 网页组成数据库就是最大的文本数据库 如果文本数据具有良好的结构，可以使用关系数据库来实现 ( 4 1 复杂型数据库 复杂性数据库是指非纯文本的数据库或能够表示动态的序列数列的数据库，主要有 如下几类 空间数据库主要是指存储空间信息的数据库，其中数据可能以光栅格式提供， 也可能用矢量图形数据表示对空间数据库的挖掘可以为城市规划、生态规划、道路修 建提供决策支持 时序数据库主要用于存放与时间相关的数据，它可以用来反映随时间变化的即 时数据或不同时间发生的不同事件对时序数据的挖掘可以发现事件发展的趋势、事物 的演变过程和隐藏特征这些信息将对事件的计划、决策和预警是非常有用的 多媒体数据库用于存放图像、声音和视频信息的数据库由于多媒体技术的发 展，以及相关研究( 如可视化信息检索、虚拟现实技术) 的成就，多媒体数据库也一样普 及，并应用于许多重要研究领域，目前，多媒体数据的挖掘主要放在对图像数据的检索 与匹配上，随着研究的深入将会拓展到声音、视频信息的挖掘处理 1 3 数据挖掘的任务和面临的挑战 通常，数据挖掘的任务分为下面两大类： ( 1 ) 预测任务这些任务的目标是根据其他属性的值，预测特定属性的值被预测的 属性般称目标变量( t a r g e tv a r i a b l e ) 或因变量( d e p e n d e n tv a r i a b l e ) ，而用来做预测的属 性称说明变量( e x p l a n a t o r yv a r i a b l e ) 或自变量( i n d e p e n d e n tv a r i a b l e ) ( 2 ) 描述任务这里，目标是导出概括数据库中潜在联系模式( 相关、趋势、聚类、 转道和异常) 本质上，描述性数据挖掘任务通常是探查性的并且常常需要后处理技术 验证和解释结果 当面临新的数据集提出的挑战时，传统的数据分析技术常常遇到实际困难下面是 一些挑战是数据挖掘所要面对的 可伸缩由于数据产生和收集技术的进步，数吉字节、数太字节甚至数拍字节的数据集 5 支持向量机中参数选取的一个问题 越来越普遍如果数据挖掘算法要处理这些海量数据集，则算法必须是可伸缩的( s c a l a b l e ) 许多数据挖掘算法使用特殊的搜索策略处理指数性搜索问题，可伸缩可能还需要实现新 的数据结构，以有效的方法访问个别纪录 高维性现在，常常遇到具有数以百计或数以千计属性的数据集，而不是数十年前常 见的只具有少量属性的数据集在生物信息学领域，微阵列技术的进步已经产生了涉及 数千特征的基因表达数据具有时间或空间分量的数据集也趋向于具有很高的维数此 外，对于某些数据分析算法，随着维数( 特征数) 的增加，计算复杂性迅速增加 异种数据和复杂数据通常，传统的数据分析方法只处理包含相同类型属性的数据 集，或者是连续的，或者是分类的随着数据挖掘在商务，科学，医学和其他领域的作用 越来越大，越来越需要处理异种属性的技术近年来，已经出现了更复杂的数据对象 为挖掘这种复杂对象而开发的技术应当考虑数据中的联系，如实间和空间的自相关性、 图的连通性、半结构化文本和x m l 文档种元素之间的父子联系 数据的所有权一分布有时，需要分析的数据并非存放在一个站点，或归属一个单 位，而是地理上分布在属于多个的机构的资源中这就需要开发分布式数据挖掘技术分 布式数据挖掘算法面临的主要挑战包括：( 1 ) 如何降低执行分布式计算所需的通信量? ( 2 ) 如何有效地统一从多个资源得到的数据挖掘结果? ( 3 ) 如处理数据安全问题? 非传统的分析传统的统计方法基于一种假设一一检验模式换句话说，提出一种假 设，设计实验来收集数据，然后针对假设分析数据但是，这一过程劳力费神当前的数 据分析任务常常需要产生和估计数以千计的假设，因此希望自动的产生和评估假设，导 致了一些数据挖掘技术的开发此外，数据挖掘所分析的数据集通常不是精心设计的试 验的结果，并且它们通常代表数据的时机性样本( r a n d o ms a m p l e ) 而且这些数据常常涉 及非传统的数据类型和数据分布 无论怎样，需求牵引，市场驱动是永恒的，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 ) 是一种解决多维函 数的预测的通用工具嘲是数据挖掘中的一项新技术其主要借助于最优化方法解决数 据挖掘中的分类问题，是数据挖掘技术中一个新的研究热点本章先简要介绍支持向量 机方法的一些基本理论，包括支持向量机处理的两类主要问题，然后对支持向量机的基 本思想、模型和支持向量机的研究现状与应用给出比较详细的阐述 2 1 支持向量机的理论基础 基于数据的机器学习是现代智能技术中的重要方面，研究从观测数据( 样本) 出发寻 找规律，利用这些规律对未来数据或无法观测的数据进行预测而支持向量机是在高维特 征空间使用线性函数假设空间的学习系统，它由一个来自最优化理论的学习算法训练， 该算法实现了一个由统计学习理论导出的学习偏置 支持向量机在解决小样本、非线性极高维模式识别问题中表现出许多特有的优势， 并且能够推广到函数逼近和概率密度估计等其他机器学习问题中目前，8 v m 算法在 模式识别、回归估计、概率密度函数估计等方面都有应用例如，在模式识别方面，对于 手写体识别、语音识别、人脸识别、文本分类问题，s v m 算法在精度上已经超过传统的 学习算法或与之不相上下 现有机器学习方法共同的重要理论基础之一是统计学传统统计学研究的是样本数 目趋于无穷大时的渐近理论，现有学习方法也多是基于此假设但在实际问题中，样本数 往往是有限的，因此一些理论上很优秀的学习方法实际中表现却可能不尽人意与传统 统计学相比，统计学习理论( 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 ) 是一种专门研究小样本1 9 j 情况下机器学习规律的理论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 r r 和s v m 正在成为继神经网络研究之后新的研究 7 支持向量机中参数选取的一个问题 热点，并将有力地推动机器学习理论和技术的发展 2 1 1 统计学习理论 ( 1 ) 机器学习 机器学习模型一般表示如下： 设x 是系统的输入空间，y 是输出空间，p ( x ) 为输入空间上的概率密度函数， p ( uiz ) 为输出空间y 上的条件概率密度，学习机就试图用函数f ( x ，w ) 来拟合输入z 和输出y 之间的关系，这种拟合是有风险( 损失) 的，设l ( y ，f ( x ，删) ) 为因采用f ( x ，w ) 对y 进行预测而造成的损失，期望风险为 ， r ( w ) ? l ( y ，f ( z ，w ) ) d p ( x ，y )( 2 1 1 ) 对模式识别问题，输出y 是类别标号，两类情况下y = o ，1 或 1 广1 ) ，预测函数称作 指示函数损失函数可以定义为： 二( 可， ，伽) ) = o , y = f ( x , w 2( 。工z ) 学习的目的就是通过选择一个参数伽，使得学习系统的输出，( $ ，叫) 与期望输出y 之间的 误差概率最小化，即出错率最小化出错率也称为期望风险( e x p e c t e dr j s k ) ，如下式定 义： 冗( 叫) = 互1 旷弛，圳d p ( 础) ( 2 1 - 3 ) 其中p ( x ，y ) 为样本空间的实际概率分布由于p ( x ，y ) 通常是未知的，因此无法直接计 算r ( t 7 ) 但是，对给定的训练集，其经验风险( e m p i r i c a l 弛k ) 玩m p ( 埘) ： ( 咖刍妾沪胞j ( 2 “) 却是确定的其中( 毛，y i ) 为训练样本，z 为训练集中样本数，即训练集规模由数理统 计中的大数定理可知，随着训练集规模的扩大，p “m a w ) 将逐渐收敛于r ) 通过上面表述可以看出，学习的目标在于使期望风险最小化，但是由于我们利用样 本信息期望风险并无法计算，而对于给定的样本其经验风险确是给定的，因此我们考虑 用经验风险来作为期望风险的一个估计，设计算法使它最小化 ( 2 ) 统计学习理论一一支持向量机的理论背景 统计学习理论是研究小样本统计估计和预测的理论在传统的统计模式识别中，我 们将经验风险见。最小化作为解决问题的基本思想，这里存在两个问题： 经验风险见。只有在大数定理的保证下才能与期望风险r 在概率上保持一致但 是实际上我们得到的样本是有限的 8 大连理工大学硕士学位论文 反之，即使我们得到能保证在样本无穷大时一定趋近r 的r 。，也不能保证在样本 有限时仍然能得到好的结果 函数集的v c 维【1 0 】 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 ) 是统计学习理论中一个极其重要的概 念在模式识别中v c 维的直观定义是：对一个预测函数集，若存在h 个样本能够被函 数集中的函数按所有可能的2 “种形式分开，则称函数集能够把h 个样本打散；函数集的 v c 维就是它能打散的最大样本数目h v c 维是机器复杂度的一个度量，v c 维越大则 学习机越复杂 v a p n i k 和c h e r v o n e n k i s 深入研究了期望风险兄( 伽) 和经验风险忍( 镏) 的关系，碍 出如下结论：对预测函数集中的所有函数( 包括使经验风险最小的函数) ，r ) 和疋。) 之间以至少1 一叼，0s 目 1 的概率满足； 广 脚) 疋唧+ 1 型整竽堂 ( 2 1 j 5 ) y 其中h 是函数集的v c 维，n 是样本数从上式可见，必须使经验风险，v c 维与样本 数的比率同时最小化，才能最小化期望风险由于经验风险通常是v c 维h 的减函数， 对给定数目的样本集，应存在最优的h 值，使期望风险最小化 结构风险最小化 传统的经验风险最小化原则在样本数目有限时，并未同时考虑我们需要同时最小化 经验风险和置信范围，根据我们对置信范围圣的认识，提出了所谓的结构风险最小化 首先把函数集s = ，( $ ，t j ) ，w n ) 分解为一个函数子集序列： 研c 岛c c 鼠c s( 2 1 6 ) 是各个子集能够按照v c 维的大小排列，即： h 1 h 2s sh k ( 2 1 7 ) 这样在同子集中的置信范围就相同；然后在每一个子集中寻找