（运筹学与控制论专业论文）不均衡支持向量机参数选取的两种优化方法.pdf

大连理工大学硕士学位论文 摘要 支持向量机是建立在统计学习理论和数学规划基础之上的一种数据挖掘的新方法。 数学规划是运筹学的一个重要分支，在机器学习、网络问题、工程机械学等领域有着广 泛应用。它和数据挖掘技术的结合己使大规模和高复杂性的问题的解决成为可能，并在 特征提取、聚类和回归等方面有很重要的应用。支持向量机是数学规划在数据挖掘领域 的一个重要应用，是由v a p n i k 等人根据统计理论提出的一种新的机器学习方法。 本文主要研究了不均衡支持向量机中参数的优化选取问题。支持向量机在各行各业 中的应用已经取得了良好的效果；支持向量机的参数选取是支持向量机研究中的一类重 要问题，参数选取的不同，对支持向量机的泛化性能影响很大；不均衡支持向量机的参 数优化选取的研究较少，本文针对不均衡问题，建立了参数选取的模型，设计了算法， 并进行了数值实验。 本文给出了不均衡支持向量机的两个参数选取模型。首先针对不均衡问题的数据上 特殊性，摒弃传统的性能评价指标，给出了一个适合不均衡问题的f 一指标；通过最小 化f 一指标来建立优化参数的模型，并用s p m 蛐软件包求解。数值实验结果表明算法的 有效性。另外，建立了一个具有光滑目标函数的m p e c 参数选取模型。该模型是一个具 有光滑目标函数的且带有互补约束的非线性规划问题，并在l i n g o 中编写程序进行数值 实验，初步证明了该模型的有效性。 关键词；数据挖掘；支持向量机；不均衡；评价指标；参数选取 不均衡支持向量机参数选取的两种优化方法 t w oo p t i m a lm e t h o d sf o rp a r a m e t e rs e l e c t i o ni ns u p p o r tv e c t o r m a c h i n e sf o ru n b a l a n c e dd a t as e t s 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 e wa p p r o a c ho fd a t am i n i n gb a s e do nt h es t a t i s t i c a l l e a r n i n gt h e o r ya n dm a t h e m a t i c a lp r o g r a m m i n g m a t h e m a t i c a lp r o g r a m m i n gi s a l li m p o r t a n t b r a n c ho f o p e r a t i o n a lr e s e a r c h i th a sb e e ne x t e n s i v e l ya p p l i e dt oa r e a so f m 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 ma n dm 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 gi n a k e si t p o s s i b l et os o l v el a r g e s c a l ea n dc o m p l i c a t e dp r o b l e m sa n di t h a sa l s ob e e ns u c c e s s f u l l y a p p l i 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 e i m p o r t a n 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 ga n di ti sam a c h i n e l e a r n i n gm e t h o dt 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 g t 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 b d i e st h eo p t i m a lm e t h o d sf o rp a r a m e t e rs e l e c t i o ni ns u p p o r tv e c t o r m a c h i n e sf o ru n b a l a n c e dd a t as e t s s u p p o r tv e c t o rm a c h i n eh a sb e e nu s e di nv a r i o u sf i e l d s a n dh a so b t a i n e dg o o de f f e c t s ；t h ep a r a m e t e rs e l e c t i o ni ns u p p o r tv e c t o rm a c h i n ei sa n i m p o r t a n tr e s e a r c hd i r e c t i o n , d i f f e r e n tp a r a m e t e r sr e s u l ti nd i f f e r e n tg e n e r a l i z a t i o n ；t h e s t u d i e so fp a r a m e t e rs e l e c t i o ni ns u p p o r tv e c - - c f o rm a c h i n ef o ru n b a l a n c e dd a t as e t si sf e w e r f o ru n b a l a n c e dd a t as e t s ，t h i sp a p e rp r e s e n t st h ep a r a m e t e rs e l e c t i o nm o d e li ns u p p o r tv e c f f o r m a c h i n ea n da l g o r i t h m , d ot h en u m e r i c a le x p e r i m e n t s t h i sp a p e rp r e s e n t st w oo p t i m a lm o d e l sf o rp a r a m e t e rs e l e c t i o ni ns u p p o r tv e c t o r m a c h i n ef o ru n b a l a n c e dd a t as e t s f i r s t l y ，f o ru n b a l a n c e dd a t as e t s ，t r a d i t i o n a lq u a l i t ym e a s u r e i sa b a n d o n e d , a n df - m e a s u r ei sp r e s e n t e dw h i c hi ss u i t e df o ru n b a l a n e e dd a t as e t s b y m l n m u z m gf - m e a s u r e ap a r a m e t e rs e l e c t i n gm o d e li s b u i l tw h i c hi ss o l v e db y s 蹦“幽 n u m e r i c a le x p e r i m e l l t sr e s u l t ss h o wt h a tt h i sm o d e li se f f e c tf o rc h o o s i n gt h ec o s tp a r a m e t e r s e c o n d l y ，t h en e wm o d e li sf o r m u l a t e di nt h ef o r mo fo n eo fm p e cp r o b l e m sw i t hs m o o t h o b j e c t i v ef i m e t i o mi ti san o n l i n e a rp r o b l e mw h i c hh a ss m o o t h e do b j e c t i v ef u n c t i o na n dw i t h c o m p l e m e n t a r yc o n s t r a i n t s n u m e r i c a le x p e r i m e n t sa r es o l v e db yl i n g oa n dt h er e s u l t ss h o w t h ee f f e c ti n i t i a l l y 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 ；u n b a l a n c e dd a t as e t s ；q u a l i t ym e a s u r e ； p a r a m e t e rs e l e c t i o n i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名： 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名 社 聊絮恭罴擎f 大连理工大学硕士学位论文 引言 数据挖掘( d a t am i n i n g 简称d m ) 这一术语首先出现在1 9 8 9 年8 月举行的第l1 届国际联合人工智能学术会议上。迄今为止，会议规模由原来的专题讨论发展到了国际 学术大会，研究重点也逐渐从发现方法转向系统应用，并且注重在各个学科之间的交叉 渗透。经过几十年的研究和实践，数据挖掘技术已经吸收了许多学科的最新研究成果从 而转化成为独具特色的研究领域。大量的具有重大应用意义的问题被不断提出，吸引了 不同领域的优秀学者。 数学领域中的数学规划问题已经成功地应用到了数据挖掘领域，数学规划思想在解 决聚类、分类和特征提取等问题上已经被成功应用。本文所研究的支持向量机( 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 r t 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 数据挖掘 1 。1 数据挖掘介绍 对大型的、复杂的、信息丰富的数据集的理解实际上是所有的商业、科学、工程 领域的共同需要，在商务领域，公司和顾客的数据逐渐被认为是一种战略资产。在当今 的竞争世界中，吸取隐藏在这些数据后面的有用的知识并利用这些知识的能力变的越来 越重要。数据挖掘技术作为新兴的多学科交叉应用领域【1 】，在各行各业的决策活动中扮 演越来越重要的角色。 1 1 1 数据挖掘的起源 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据越来 越多。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高层次的分析， 以便更好地利用这些数据。目前的数据库系统可以高效地实现数据的录入、查询、统计 等功能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋 势。缺乏挖掘数据背后隐藏的知识的手段，导致了“数据爆炸但知识贫乏”的现象。数据 挖掘技术便在这种情况下应运而生。 数据挖掘实际上是人们长期对数据库进行研究和开发的结果。随着大量历史数据的 积累，人们不满足简单的查询和修改数据，而是希望发现数据之间的潜在关系。随着计 算机技术的日益普及和提高，人们应用计算机和数据库技术，采用机器学习的方法来分 析数据，挖掘大量数据背后的知识，并快速地应用到企业决策中去，将决定企业是否能 拥有最大程度的竞争优势，数据挖掘技术便出现了，并得到了快速的应用和发展。 数据挖掘可以应用到各个不同的领域，能够对未来的趋势和行为进行预测，从而很 好的支持人们的决策。如银行可以使用数据挖掘发现有价值的客户，保险公司和证券公 司可以使用数据挖掘来检测欺诈行为等等。 1 1 2 数据挖掘的概念 数据挖掘( d a t a m i n i n g 简称d m ) ，简单地讲就是从大量的数据库中挖取或抽取出 有用的知识，即从大量的、不完全的、有噪音的、模糊的、随机的实际应用数据中发现 隐含的、有规律的、人们事先未知的，但又是潜在的有用的并且最终可以理解的信息和 知识的非平凡过程。 数据挖掘是一门涉及面很广的交叉学科，包括机器学习、数理统计、神经网络、数 据库、模式识别、粗糙集、模糊数学等相关技术。由于数据挖掘是一门受到来自各种不 不均衡支持向量机参数选取的两种优化方法 同领域的研究者关注的交叉性学科，因此导致了很多不同的术语名称。其中，最常用的 术语是”知识发现”和”数据挖掘”。相对来讲，数据挖掘主要流行于统计界( 最早出现于 统计文献中) 、数据分析、数据库和管理信息系统界；而知识发现则主要流行于人工智 能和机器学习界。数据挖掘可租略地理解为三部曲：数据准备( d a t ap r e p a r a t i o n ) 、 数据挖掘，以及结果的解释评估( i n t e r p r e t a t i o na n de v a l u a t i o n ) 。 从商业角度讲，数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据 库中的大量业务数据进行抽取、转换、分析和其它模型化处理，从中提取辅助商业决策 的关键性数据。 简而言之，数据挖掘其实是一类深层次的数据分析方法。数据分析本身已经有很多 年的历史，只不过在过去数据收集和分析的目的是用于科学研究，另外，由于当时计算 能力的限制，对大数据量进行分析的复杂数据分析方法受到很大限制。现在，由于各行 业业务自动化的实现，商业领域产生了大量的业务数据，这些数据不再是为了分析的目 的而收集的，而是由于纯机会的( o p p o r t u n i s t i c ) 商业运作而产生。分析这些数据也 不再是单纯为了研究的需要，更主要是为商业决策提供真正有价值的信息，进而获得利 润。但所有企业面临的一个共同问题是：企业数据量非常大，而其中真正有价值的信息 却很少，因此从大量的数据中经过深层分析，获得有利于商业运作、提高竞争力的信息， 就像从矿石中淘金一样，数据挖掘也因此而得名。因此，数据挖掘可以描述为：按企业 既定业务目标，对大量的企业数据进行探索和分析，揭示隐藏的，未知的或验证已知的 规律性，并进一步将其模型化的先进有效的方法。 由于数据挖掘技术涉及到多种学科技术，如数据库技术、统计学、机器学习、高性 能计算、模式识别、神经网络、数据可视化、信息检索、图象和信号处理以及空间数据 分析等等，因此，数据挖掘被信息产业界认为是数据库系统最重要的前沿之一，是信息 产业最有前途的交叉学科。随着数据挖掘技术的不断发展，它将会被广泛而深入得应用 于人类生活的各个领域。我们主要关注数据挖掘的数学规划，特别是优化方法。当前， 许多领域大量问题可以作为数学规划问题被公式化并有效地解决，例如，运筹研究l 、 神经网络问题1 4 棚、博弈理论与经济学6 t 7 】、工程机械学。通过数学规划解决数据挖 掘成为近几年来新兴的研究领域 1 0 j l 】。 1 2 数据挖掘的功能 数据挖掘通过预测未来趋势及行为，做出前摄的、基于知识的决策。数据挖掘的目 标是从数据库中发现隐含的、有意义的知识，它的主要功能主要分为分类分析( 包括二 - 4 - - 大连理工大学硕士学位论文 分类和多分类问题) 、关联分析、聚类分析、概念描述、偏差分析等，其中分类分析是 本文的研究重点。 分类分析 预言模型1 1 2 】以通过数据库中的某些数据得到另外的数据为目标，若预言的模型是离 散的这类问题就是分类。分类一直为人们所关注，它是一种有监督的学习方法，即已知 数据的类别是确定的。数据挖掘以往广泛使用的方法有决策树、神经网络、径向基函数 等。而现今新兴起的支持向量机( s v m ) 是v a p n i k 1 a , 1 4 1 等人根据统计学习理论提出的一 种新的机器学习方法，是数学规划在数据挖掘领域的一个很重要的应用。 通过学习算法，支持向量机可以自动寻找那些对分类有较好区分能力的支持向量， 由此构造出的分类器可以最大化类与类的间隔，因而有较好的推广性能和较高的分类准 确率。其主要思想是针对两分类的问题。给定空间中的两类点的集合，构造模型并对其 求解从而寻找一个超平面作为两类的分割，以保证最小的分类错误率。常见的分类问题 有线性可分、线性不可分和非线性可分情况。 通常的分类方法对于非线性分类问题的处理具有一定的局限性。而支持向量机一个 重要的优点就是可以处理非线性可分的情况。其从原始空间中抽取特征，将原始空间中 的样本映射为高维特征空间中的一个向量，以解决原始空间中的非线性问题。 关联分析 数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量的取值 之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、因果关联。关联 分析的目的是找出数据库中隐藏的关联网。有时并不知道数据库中数据的关联函数，即 使知道也是不确定的，因此关联分析生成的规则带有可信度。 聚类分析 数据库中的记录可被化分为一系列有意义的子集，即聚类。聚类增强了人们对客观 现实的认识，是概念描述和偏差分析的先决条件。聚类技术主要包括传统的模式识别方 法和数学分类学。8 0 年代初，m e h a l s k i 提出了概念聚类技术，其要点是，在划分对象 时不仅考虑对象之间的距离，还要求划分出的类具有某种内涵描述，从而避免了传统技 术的某些片面性。 概念描述 概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。概念描述 分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者描述不同类对象之 间的区别。生成一个类的特征性描述只涉及该类对象中所有对象的共性。生成区别性描 述的方法很多，如决策树方法、遗传算法等。 不均衡支持向量机参数选取的两种优化方法 偏差分析 数据库中的数据常有一些异常记录，从数据库中检测这些偏差很有意义。偏差包括 很多潜在的知识，如分类中的反常实例、不满足规则的特例、观测结果与模型预测值的 偏差、量值随时间的变化等。偏差检测的基本方法是，寻找观测结果与参照值之间有意 义的差别。 1 3 数据挖掘的未来研究方向及热点 1 3 1 数据挖掘的未来研究方向 当前，数据挖掘研究方兴未艾，其研究与开发的总体水平相当于数据库技术在7 0 年代所处的地位，迫切需要类似于关系模式、d b m s 系统和s q l 查询语言等理论和方 法的指导，才能使数据挖掘的应用得以普遍推广。预计在本世纪，数据挖掘的研究还会 形成更大的高潮，研究焦点可能会集中到以下几个方面： 1 ) 发现语言的形式化描述，即研究专门用于知识发现的数据挖掘语言，也许会像 s o l 语言一样走向形式化和标准化； 2 ) 寻求数据挖掘过程中的可视化方法，使知识发现的过程能够被用户理解，也便 于在知识发现的过程中进行人机交互； 3 ) 研究在网络环境下的数据挖掘技术( w e b m i n i n g ) ，特别是在因特网上建立d m k d 服务器，并且与数据库服务器配合，实现w e bm i n i n g ： 4 ) 加强对各种非结构化数据的开采( d a m m i n i n g f o r a u d i o v i d e o ) ，如对文本数 据、图形数据、视频图像数据、声音数据乃至综合多媒体数据的开采； 处理的数据将会涉及到更多的数据类型，这些数据类型或者比较复杂，或者是结构 比较独特。为了处理这些复杂的数据，就需要一些新的和更好的分析和建立模型的方法， 同时还会涉及到为处理这些复杂或独特数据所做的费时和复杂数据准备的一些工具和 软件。 5 ) 交互式发现； 6 ) 知识的维护更新。 1 3 2 数据挖掘的热点 就目前来看，将来的几个热点包括网站的数据挖掘( w e bs i t ed a t am i n i n g ) 、生物 信息或基厌q ( b i o i n f o r m a f i c s g e n o m i c s ) 的数据挖掘及其文本的数据挖掘( t e x t u a lm i n i n g ) 。 下面就这几个方面加以简单介绍。 1 ) 网站的数据挖掘 6 一 大连理工大学硕士学位论文 随着w e b 技术的发展，各类电子商务网站风起云涌，建立起一个电子商务网站并 不困难，困难的是如何让您的电子商务网站有效益。要想有效益就必须吸引客户，增加 能带来效益的客户忠诚度。电子商务业务的竞争比传统的业务竞争更加激烈，原因有很 多方面，其中一个因素是客户从一个电子商务网站转换到竞争对手那边，只需点击几下 鼠标即可。网站的内容和层次、用词、标题、奖励方案、服务等任何一个地方都有可能 成为吸引客户、同时也可能成为失去客户的因素。而同时电子商务网站每天都可能有上 百万次的在线交易，生成大量的记录文件( l o gf i l e s ) 和登记表，如何对这些数据进行 分析和挖掘，充分了解客户的喜好、购买模式，甚至是客户一时的冲动，设计出满足于 不同客户群体需要的个性化网站，进而增加其竞争力，几乎交得势在必行。若想在竞争 中生存进而获胜，就要比你的竞争对手更了解客户。 2 ) 生物信息或基因的数据挖掘 生物信息或基因数据挖掘则完全属于另外一个领域，在商业上很难讲有多大的价 值，但对于人类却受益非浅。例如，基因的组合千变万化，得某种病的人的基因和正常 人的基因到底差别多大? 能否找出其中不同的地方，进而对其不同之处加以改变，使之 成为正常基因? 这都需要数据挖掘技术的支持。 对于生物信息或基因的数据挖掘和通常的数据挖掘相比，无论在数据的复杂程度、 数据量还有分析和建立模型的算法而言，都要复杂得多。从分析算法上讲，更需要一些 新的和好的算法。现在很多厂商正在致力于这方面的研究。但就技术和软件而言，还远 没有达到成熟的地步。 3 ) 文本的数据挖掘 人们很关心的另外一个话题是文本数据挖掘。举个例子，在客户服务中心，把同客 户的谈话转化为文本数据，再对这些数据进行挖掘，进而了解客户对服务的满意程度和 客户的需求以及客户之间的相互关系等信息。从这个例子可以看出，无论是在数据结构 还是在分析处理方法方面，文本数据挖掘和前面谈到的数据挖掘相差很大。文本数据挖 掘并不是一件容易的事情，尤其是在分析方法方面，还有很多需要研究的专题。目前市 场上有一些类似的软件，但大部分方法只是把文本移来移去，或简单地计算一下某些词 汇的出现频率，并没有真正的分析功能。 随着计算机计算能力的发展和业务复杂性的提高，数据的类型会越来越多、越来越 复杂，数据挖掘将发挥出越来越大的作用。 大连理工大学硕士学位论文 2 支持向量机 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 1 5 1 是由v a p n i k 领导的a t & t 实验小组 在上世纪九十年代中期，基于统计学习理论，提出的以凸二次规划为基本模型的一种处 理小样本的机器学习方法，它是一种通用的有监督的学习方法，是数据挖掘技术中的一 个新的研究热点。本章先简要介绍支持向量机方法的理论基础，然后对支持向量机的知 识背景、模型的导出与求解以及一些主要的算法给出比较详细地阐述。 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 ) 。s l t 是一种专门研 究小样本f l 川情况下机器学习规律的理论。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 ) 。 2 1 1 机器学习的基本问题 机器学习的目的是根据给定的训练样本求对某系统输入输出之间的依赖关系的估 计，使它能够对未知输出作出尽可能准确的预测。可以一般地表示为：变量y 与x 存在 一定的未知依赖关系，即遵循某一未知的联合概率p ( x ，y ) ( x 和y 之间的确定性关系可 以看作是其特例) 。 不均衡支持向量机参数选取的两种优化方法 机器学习问题就是根据珂个独立同分布观测样本 ( 鼍，y 0 ，( 而，y 2 ) ，( ，) ) 在组函数f ( x ，c o ) 中求一个最优的函数f ( x ，t o o ) 对依赖关系进行评估使期望风险1 丑( ) = l l ( y ，f ( x ，c o ) ) d p ( x ，y ) ( 2 1 ) 最小。其中，f ( x ，国) 称作预测函数集，为函数的广义参数，f ( x ，) 可以表示任何函 数集；l ( y ，f ( x ，c o ) ) 为由于用，o j ) 对y 进行预测而造成的损失，不同类型的学习问题 有不同形式的损失函数。 对模式识别问题，输出y 是类别标号，两类情况下y = o , 1 ，或 1 ，一1 ，预测函数称 作指示函数。损失函数可以定义为 地f ( x , c o ”= 世；三凳： ， 学习的目的就是通过选择一个参数f o ，使得学习系统的输出f ( x ，c o ) 与期望输出y 之间 的误差概率最小化，即出错率最小化。出错率也称为期望风险( e x p e c t e d lr i s k ) ，如下 式定义 胄( c o ) = l 陟- f ( x ，c o ) d p ( x ，力( 2 3 ) 其中p ( x ，y ) 为样本空间的实际概率分布，由于p ( x ，j ，) 通常是未知的，因此无法直接计 算l e ( o d ) 。但是，对给定的训练集，其经验风险( e m p i r i c a lr i s k ) j i 。 ) ( ) = 寺k - f ( x , ，c o ) i ( 2 4 ) 却是确定的。其中( 五，乃) 为训练样本，z 为训练集中样本数，a p r i l 练集规模。由数理统 计中的大数定理可知，随着训练集规模的扩大，k ) 将逐渐收敛于r ( ) 。 通过上面的表述可以看出，学习的目标在于使期望风险最小化，但是由于我们利用 样本信息的期望风险并无法计算，而对于给定的样本其经验风险却是给定的，因此我们 考虑用经验风险来作为期望风险的一个估计，设计算法使它最小化。 事实上，用经验风险代替期望风险最小化并没有经过充分的理论论证，只是直观上 合理的想当然做法，但这种思想却在多年的机器学习方法研究中占据了主要地位。人们 多年来将大部分注意力集中到如何更好地最小化经验风险上。而实际上，即使可以假定 当”趋向于无穷大时( 2 4 ) 趋近于( 2 3 ) 式，在很多问题中的样本数目也离无穷大相去甚远。 那么在有限样本下得到的结果能使真实风险也较小吗? 这是我们需要考虑的问题。 上面提到的问题不成功的一个例子是神经网络的过学习问题。开始，很多注意力都 大连理工大学硕士学位论文 集中在如何使j 乇。( 国) 更小，但很快就发现，训练误差小并不总能导致好的预测效果， 某些情况下，训练误差过小反而会导致推广能力的下降，即真实风险的增加，这就是过 学习问题。之所以出现过学习现象，一是因为样本不充分，二是学习机器设计不合理。 这两个问题是相互关联的。 在神经网络中，对有限的样本来说网络学习能力过强，足以记住每个样本，此时经 验风险很快就可以收敛到很小甚至零，但却根本无法保证它对未来样本能给出好的预 测。学习机器的复杂性与推广性之间的这种矛盾同样可以在其他学习方法中看到。文献 2 0 给出了一个实验例子。由此可以看出，有限样本情况下： 1 ) 经验风险最小并不一定意味着期望风险最小。 2 ) 学习机器的复杂性不但应与所研究的系统有关，而且要和有限数目的样本相适 应。 我们需要一种能够指导我们在小样本情况下建立有效的学习和推广方法的理论，统 计学习理论便在这种背景下应运而生。 2 1 2 统计学习理论简介 统计学习理论就是研究小样本统计估计和预测的理论1 2 l l ，主要内容包括四个方面： 1 ) 经验风险最小化准则下统计学习一致性的条件； 2 ) 在这些条件下关于统计学习方法推广性的界的结论； 3 ) 在这些界的基础上建立的小样本归纳推理准则； 4 ) 实现新的准则的实际算法。 其中，最有指导性的理论结果是推广性的界。与此相关的一个核心概念是v c 维。 为了研究学习过程一致收敛的速度和推广性【”，2 捌，统计学理论定义了一系列有关 函数学习性能的指标，其中最重要的是v c 维f “矧。 模式识别方法中v c 维的直观定义是：对一个指示函数集，如果存在h 个样本能够被 函数集中的函数按所有可能的2 矗种形式分开，则称函数集能够把h 个样本打散；函数集 的v c 维就是它能打散的最大样本数目h 。若对任意数目的样本都有函数能够将它们打 散，则函数集的v c 维是无穷大。有界实函数的v c 维可以通过用一定的阀值将它转化成 指示函数来定义。 v c 维反映了函数集的学习能力，v c 维越大则学习机器越复杂( 容量越大) 。遗憾 的是，目前尚没有通用的关于任意函数集v c 维计算的理论，只是一些特殊的函数集知 道其v c 维。比如在h 维实数空间中线性分类器和线性实函数的v c 维是胛+ 1 ，而上一节 例子中厂( x ，爿) = s i n ( a x ) 的v c 维则为无穷大。对于给定的学习函数集，如何( 用理论和 不均衡支持向量机参数选取的两种优化方法 实验的方法) 计算其v c 维是当前统计学习理论中有待研究的一个问题。 统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之间的关 系，即推广的界。关于两类分类问题，结论是；对指示函数集中的所有函数( 包括使经 验风险最小的函数) ，经验风险乙。( ) 和实际风险r ( 砩之间以至少1 一叼，0 0 ，f l ，) ( 2 2 3 ) ：。y t a ，= o 其中口。是与每一个样本对应的拉格朗日乘子。这是一个不等式约束的二次寻优问题，存 在唯一的解a = ( a ：，口；，口j ) ，则得到 国= a ，y , x t ( 2 2 4 ) 且由k k t 定理可知，最优解满足 a j ( 只( 7 而- r ) - i ) = 0 ( 2 2 5 ) 因此，对于多数样本口将为零，最优解只依赖那些对应的a 0 的输入，他们通常只占 全体样本的很少的一部分。我们引入下面的定义： 定义2 1 ( 支持向量) 1 1 3 1 称训练样本集丁中输入置为支持向量，如果它对应的a 0 。 求解上述问题后得到的最优分类函数是； _ ，i 力= s g n ( x + r ) = s g n ( a ：儿( 一膏) + r ) ( 2 2 6 ) 由于非支持向量对应的a 均为零，因此式中的求和实际上只对支持向量进行，而r 是分 类的域值。 从而有如下的算法： 1 ) 设已知训练集t = ( 五，乃) ，( x 2 ，耽) ，( x t ，乃) ) ，五r d , 以 + l ，一1 ) ，i 1 舶 2 ) 构造并求解最优化问题 呼i 1 乙u t 。l y , y j a ，a 舟，_ ) 一一2 2 。l 口，n i 乙f 。l a f a 【五，) 一。l 口 s 8 a i 0 ，i 1 b - 只q = o 求得最优解口= ：，口；，口；) ； 3 ) 计算 t ， 2 乙口，”毛 不均衡支持向量机参数选取的两种优化方法 选择a 的一个正分量口：，并计算 ，= 乃一口j 乃( 蕾一) ； 4 ) 由此求得决策函数 毽) = s g n ( o d ”x + r ) 或 ，( 力= s 弘( a 江 z ) + r 。) 上面给出的是线性可分情况下的模型，而在实际情况中训练样本集对为线性不可分 的。这时可以在条件中加入一个松弛项盏0 ，样本点满足的条件相应地改为 y , ( c 0 1 耳一r ) + 皇1 ，f 1 f 目标函数改为求 i 1 r + c 毛 的最小值。可以建立下面的标准模型 卿三矿c 0 + c z e , 2 m ，毒 ，1 1 s t 只( 国7 五- r ) + 磊2 l ，f ( 1 ，( 2 2 7 ) 盏0 ，i 1 母 其中c 为惩罚参数，c 越大表示对错误分类的惩罚越大。二为松弛变量，为分 类超平面的法向量，r 为阀值。 目标函数前一项反映的是置信范围，后一项反映的是训练误差，前后两项体现了结 构风险最小化原则。其最优分类面的对偶问题与线性可分情况下几乎完全相同；根据优 化理论得到 警酗一圭善m 聃吣，勺) 盯0 s a 。s c ，f l 毋 ( 2 2 s ) 以口= o ，f 1 毋 只是拉格朗日乘子的约束条件为0 a 。c 。求解( 2 2 s ) 等价于求解下面的问题 n 班吉：乒，乃乃q q ( 而，_ ) 一二a ，n i 乙r 。l 乃乃q q 【而，) 一乙。l l a ， s ，- 1 只a ，= o ( 2 2 9 ) 0 a f c ，f l _ 其最优解a 满足k k t 互补条件为 大连理工大学硕士学位论文 口j ”x t - r ) 一】+ 茧) = o ，i 1 o ( c - a ) 善= 0 ，i l n 此时，可以通过任意岱0 求得，这时广义最优线性分类器( 也称为决策函数) 是 八x ) = s g n ( c o 叩x + r ) = s g n ( a ；y , c x , x ) + ，) ( 2 3 0 ) 其中满足a ， 0 的样本称为支持向量。对这种情况同样有算法： 1 ) 设己知训练集r = ( 而，乃) ，( 而，弘) ，( 而，乃) ) ，x t r 4 ，只p l ，一l ，f 1 ， ； 2 ) 构造并求解最优化问题 乎 ：，一乃q 哆( 五，x j ) x j ) 一咿i 己，。l 一乃口，哆( 五， 一己a s j z i - 1 y i a 。= 0 0 口，c ，i 1 ，) 求得最优解口= ( 口：，a ：，口? ) ； 3 ) 计算 = a , y f x j 选择口的一个正分量0 口 c ，并计算 r 。= ”一口j 只( t x j ) ； 4 ) 由此求得决策函数 f ( x ) = s g n ( c o 7 x + r + ) 或 ，( x ) = s 印( a t y , ( x , 功十，) 除了上述的标准模型外，还有一种非标准的支持向量机模型应用也十分广泛 2 s , z 9 1 卿土2 + c 茧2 + 三，2 2 口，z 鲁” m i 乃( ，t 一，) + 盏2 1 ，f l 毋( 2 3 1 ) 茧0 ，i l 毋 该模型利用f f 洄，r ) f 1 2 代替原来的置信范围恼8 2 ，使用2 - 范数平方的训练误差来代替1 范 不均衡支持向量机参数选取的两种优化方法 数的训练误差。这样得到了一个对分类结果影响很小的强凸的目标函数，任何算法 在该目标函数上通常具有比标准模型更快的收敛速度。 b 非线性支持向量机 我们注意到上面讨论的线性分类函数，最终的分类判别函数中只包含待分类样本与 训练样本中的支持向量的内积运算x ) ，它的求解过程中只涉及训练样本间的内积运 算( 五x ，) ，可见要解决一个特征空间的最优线性分类问题，只需要知道这个空间中的内 积运算即可。 对于给定的样本点不能用一个超平面分离或近似分离时，为了提高分类的准确度， 可以利用变换将其映射到维数更高的空间，就是将样本x 映射到某个高维特征空间 hb o , 3 1 ，也就是变换 o ：x o ( 功= ( m 1 ( ，2 ( x ) ，m ( 工) ) ( 其中h 是高维空间目的维数) ，而在高维特征空间日中训练样本的象有较好的分离性， 也就是说，在高维特征空间日中训练样本可以被线性分离。此时模型( 2 2 9 ) 转化为 ，l 呼一寺y , y a ，a 似) ，中( _ ) ) 一t=l l 。产l s t 0 s a ，c ，( 2 3 2 ) ， ”a ，= 0 ，f 0 - - 0 f i l 得到的分类函数为 ， 厂( 力= s g n ( r 0 7 ( x ) + ，) = s g n ( 口只( m ( x ) f 西( z ) ) + r ) ( 2 3 3 ) t = l 从上面两式