（计算机应用技术专业论文）基于支持向量机的图像分割方法的研究.pdf

摘要随着社会和经济的发展，人们对身份鉴别的准确性、安全性与实用性提出了更高的要求。基于信物或口令的传统身份鉴别方式存在容易丢失、遗忘、被复制及盗用的隐患，已不能满足现代社会高度信息化的要求。通过辨识人的生理和行为特征进行身份认证的生物识别技术提供了一个方便可靠的解决方案。生物识别技术以生物征为基础，以信息处理技术为手段，将生物技术和信息技术有机结合在一起。在众多的生物识别技术中，指纹识别技术以方便易用、高准确率和成本低等诸多优势备受关注，已经成为身份认证的最有效手段，在电子商务、犯罪识别、信息安全等领域得到广泛的应用。图像分割是指纹图像预处理过程中的一个重要部分，有效地分割既可以减少后续处理的时间，又可以大大增强特征提取的可靠性。本文在分析前人算法的基础上，提出了一种基于支持向量机的指纹图像分割方法。将指纹图像分块，并根据图像块的对比度特征进行初分割，以去除灰度变化比较小的白背景块；对剩下的图像块提取灰度均值、灰度方差、对比度、梯度一致性及主能量比构成特征向量；采用有监督的支持向量机分类器进行分类，选取样本点对其进行训练，使用较少的训练样本得到泛化性能较好的分类器；使用支持向量机分类器将把初分割后剩下的图像块分成前景和背景两类，从而达到指纹图像的分割的目的；最后，采用形态学方法进行后处理，以减少分割错误。在f v c 指纹库上对算法进行仿真实验，结果证明了算法的有效性和鲁棒性。关键词：指纹，图像分割，主能量比，支持向量机t h er e s e a r c ho fi m a g es e g m e n t a t i o nb a s e do ns u p p o r tv e c t o rm a c h i n eh a ox i a o w e i ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y )d i r e c t e db yp r o f z h ul i a n z h a n g ，z h a o s h i j u na b s t r a c tw i t ht h ed e v e l o p m e n to fs o c i a la n de c o n o m y ，t h ea c c u r a c y ，s e c u r i t ya n du t i l i t yo fp e r s o n a li d e n t i f i c a t i o nm e t h o d sa l ep u tf o r w a r dah i g h l yr e q u i r e m e n t t h et r a d i t i o n a lp e r s o n a li d e n t i f i c a t i o nm e t h o d sb a s e do nt o k e no rp a s s w o r dh a v et h eh i d d e nt r o u b l e s t h et o k e no rp a s s w o r di sp r o n et ob el o s t ，f o r g o t t e n ，c o p i e da n ds t o l e n t h et r a d i t i o n a lp e r s o n a li d e n t i f i c a t i o nm e t h o d sc a n n o ts a t i s f yt h es e c u r i t yr e q u i r e m e n to f0 1 1 1 h i g h l yi n t e r c o n n e c t e di n f o r m a t i o ns o c i e t y b i o m e t r i c sb a s e do nt h ep h y s i o l o g i c a lo rb e h a v i o rt r a i t si d e n t i f i c a t i o np r o v i d e sac o n v e n i e n ta n dr e l i a b l es c h e m e a m o n gt h ei d e n t i f i c a t i o nt e c h n o l o g i e s ，t h et e c h n i q u eo ff i n g e r p r i n ti d e n t i f i c a t i o nh a sb e c o m eo n eo ft h ew i d e s t u s e db i o m e t r i ci d e n t i f i c a t i o nt e c h n i q u e sd u et oi t sc o n v e n i e n c e ，h i g ha c c u r a c ya n dl o wc o s t i th a sb e e nw i d e l yu s e di ne l e c t r o n i cc o m m e r c e ，c r i m i n a li d e n t i f i c a t i o n ，i n f o r m a t i o ns a f e t ye t c i m a g es e g m e n t a t i o ni sa ni m p o r t a n tp a r to ft h ei m a g ep r e - p r o c e s s i n g ，e f f e c t i v es e g m e n t a t i o nn o to n l yc a nr e d u c et h ef o l l o w - u pp r o c e s s i n gt i m eb u ta l s oe n h a n c et h er e l i a b i l i t yo ft h ef e a t u r ee x t r a c t i o n i nt h i sp a p e r , w ea n a l y z ep r e v i o u sa l g o r i t h m sa n dp r e s e n taf i n g e r p r i n ti m a g es e g m e n t a t i o na l g o r i t h mb a s e do ns u p p o r tv e c t o rm a c h i n e ( s v m ) a tf i r s t ，t h ei m a g ei sp a r t i t i o n e di n t ob l o c k sa n dt h el o w 铲a yv a r i a n c eb a c k g r o u n db l o c k sw e r es e g m e n t e db yt h ec o n t r a s t a f t e rt h a t ，t h eg r a ym e a n ，t h eg r a yv a r i a n c e ，t h ec o n t r a s t ，t h ec o h e r e n c ea n dt h em a i ne n e r g yr a t i ow e r ee x t r a c t e do nt h er e m a i n i n gb l o c k s w eu s es u p e r v i s e ds v mt oc l a s s i f yp a t t e r n sa n ds e l e c tt y p i c a lp a t t e r n st ot r a i nt h ec l a s s i f i e r t h eb l o c k st h a tc a nn o tb ed e c i d e db yt h ef i r s ts e g m e n t a t i o nw e r es e g m e n t e db yas v mc l a s s i f i e r f i n a l l y , m o r p h o l o g yw a sa p p l i e da sp o s t p r o c e s s i n gt or e d u c et h en u m b e ro fc l a s s i f i c a t i o ne r r o r s t h es i m u l a t i o n sw e r e d o n et ot h ep r o p o s e da l g o r i t h m so nf v cd a t a b a s e ，a n dt h ee x p e r i m e n t ss h o wt h a tt h ep r o p o s e dm e t h o di se f f e c t i v ea n dr o b u s t k e yw o r d s ：f i n g e r p r i n t ；i m a g es e g m e n t a t i o n ；m a i ne n e r g yr a t i o ；s v mn关于学位论文的独创性声明本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外，本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志对研究所做的任何贡献均已在论文中作出了明确的说明。若有不实之处，本人愿意承担相关法律责任。学位论文作者签名：日期：叫年归日学位论文使用授权书本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他复制手段保存学位论文。保密学位论文在解密后的使用授权同上。学位论文作者签名：妊l 垂美f 丕指导教师签名：l 连孽1 塞敛日期：彬游月日吼_ 年尹月占日中国石油大学( 华东) 硕士学位论文第一章前言弟一早刖苗近些年来，信息技术的高速发展为人类相互交流提供了更为快捷与便利的手段，它大大地推动了现代社会的进步和发展，但也给各个国家和社会管理者带来一个全新的重要课题：在高科技的信息时代如何及时准确和有效地验证每个社会成员的身份，以保障人们的合法权益和各种社会活动的合法性和有效性，及时打击与遏制各种违法犯罪活动，维护国家安全和社会稳定。传统的身份识别技术大致分为基于标志的认证和基于知识的认证两类。基于标志的认证主要是验证该人是否持有有效的证明文件或信物 j a i n 等，2 0 0 0 来确认身份。从本质上来说这种方法验证的是该人持有的某种物而不是验证其本人，只要物的有效性得到确认，则持有该物的人的身份也就随之得到确认。这种以物认人的办法的漏洞是显而易见的。首先，合法的人如果遗失验证其身份的物( 如密码、钥匙等) ，则合法的人本身得不到合法的验证；其次，各种伪造证件信物以及密码被破译或盗用，又使非法的人得到合法的验证，例如一些罪犯通过伪造证件进入机密场所以窃取机密信息或伪造签证和护照非法入境或移民。基于知识的认证主要是用所知道的事物来确认身份，最常见的是“用户i d + 密码”的方式。现行的许多计算机系统中，包括许多非常机密的系统都是使用“用户i d + 密码”的方法来进行用户的身份认证和访问控制的 j a i n 等，2 0 0 0 】。实际上，这种方案隐含着一些问题，例如密码容易忘记，也容易被别人窃取。上述这些问题表明，传统的依赖于信物或口令的系统安全性技术已经面临严峻的挑战。尽管它们具有简单并且方便集成的优点，但随着信息时代的到来和电子商务的日趋普及，在安全性以及方便性上都己难以满足现实需求。人们迫切需要能够更好的确保系统的安全性和方便性的其他技术，而由于人体特征具有不可复制的优点，目前已经成为安全技术研究的热点。1 1 课题的提出、目的及意义常见的生物特征识别手段主要有d n a 识别、耳型识别、人脸识别、脸部热量、指纹识别、步态识别、手形识别、手部血管识别、虹膜识别、视网膜识别、手写体识别和声音识别等 刘振安等，2 0 0 0 ；d a u g m a n ，1 9 9 3 ；c a m p b e l l ，1 9 9 7 ：m i l e r ，1 9 9 4 ；n a l w a ，1 9 9 7 ；w i l d e s1 9 9 7 ；z h a n g 等，1 9 9 7 ；h s u 等，2 0 0 2 。作为生物识别技术的分支之一，近年来指纹识别技术发展迅速，己经有不少成熟的第一章前言产品问世，并在商业、军事、公共安全等领域得到应用。指纹本身具有两个重要特性：( 1 ) 不变性一个人的指纹终生不变：( 2 ) 唯一性两个指纹完全相同的概率很小，可以认为世界上没有两个指纹是完全相同的，同一个人的两个指纹也是如此。这使得通过指纹验证人的身份成为可能。与其它生物识别技术相比，指纹识别是目前对人体最不造成侵犯，且方便、实用、可靠的的一种技术手段【王波涛等，2 0 0 1 ，它也是目前最具有代表性和最有前景的生物识别技术。基于指纹特征点匹配的算法是指纹识别中最常用的一类算法，它分成预处理和匹配两个阶段，其中匹配算法是决定系统性能的关键，但预处理能否准确提取用于匹配的指纹特征点对匹配的效果有重要影响。指纹预处理是指纹特征提取前的一个非常重要的环节，主要用于突出指纹图像中的纹理、方向信息，消除或者减弱噪声等无用信息。指纹图像与处理包括指纹图像分割、图像增强、二值化、细化等。准确、可靠地将指纹从背景区域中分割出来，对于缩短图像的处理时间、提高特征提取的准确率都具有极为重要的意义，特别是对非理想采集条件下的指纹分割显得尤为重要。指纹图像分割是自动指纹识别中一个非常困难，同时也是一个非常值得深入研究的问题，本文就此提出一种使用支持向量机进行指纹图像分割的方法。1 2 国内外研究现状指纹图像的分割，第一是将图像分成背景区和指纹前景区：第二是将前景区分成清晰区和模糊区。在此只考虑前景和背景的分割问题。指纹图像的背景区不包含有用信息，还会形成假特征点，所以必须从图像中分割掉；同时，预处理中的滤波等操作若只在前景区进行，则可以大大节省预处理的时间。已经有许多学者提出了多种指纹分割方面的算法。国外对指纹图像分割的研究有很多，主要有以下研究成果：1 、m e h t r e m e h t r e 等，1 9 8 9 等提出将指纹图像分成许多互不重叠的块，分析块中象素梯度方向的统计特性，并结合灰度方差进行分割；2 、r a t h a r a t h a 等，1 9 9 5 计算图像块内象素灰度在块方向上投影的方差，对于前景区，该方差在垂直方向较大，而平行方向上则较小；3 、c h i k k e r u r c h i k k e r u r 等，2 0 0 5 采用图像块傅立叶变换的频谱能量特征来分割图像；4 、b a z e n b a z e 等，2 0 0 ： 以象素为处理单位，采用图像的局部域灰度均值、局部标2中国石油大学( 华东) 硕士学位论文准差和局部梯度一致性作为特征，采用感知器进行分类。由于感知器仅适用于线性可分的情况，所以分类器训练迭代难以收敛，分类错误率高；5 、r o s s r o s s ，2 0 0 3 等用灰度均值和g r a h a m 的拟凸算法分割指纹背景。近些年来，国内对指纹图像分割的研究突飞猛进，主要有以下研究成果：l 、l i n l i n 等，1 9 9 8 1 使用每个图像块在其垂直方向上的投影信号的波峰波谷高度差、信号频率和方差，采用聚类的方法对图像块进行分类，由于其投影窗为重叠的，类别间特征向量的各分量并不独立，类间距离小，采用非监督学习的方法分类性能难以保证；2 、王森 w a n g 等，2 0 0 3 提出图像块对比度、局部主能量比、局部标准差和局部一致性作为特征，再采用r b f 神经网络分类。其中，对比度是局部方差与局部灰度均值的比值，局部主能量比则反映了局部图像中主频率上的能量与不含直流分量的局部平均能量的比值，但是该方法没有兼顾准确性与算法效率之间的平衡；3 、c h e n c h e n 等，2 0 0 4 等提出灰度聚类度特征，结合块内灰度均值、方差，采用基于最小错分样本数准则的线性分类器进行样本分类，但灰度聚类度特征与块内灰度均值分割特点相似，分类性能有限，且最小错分样本数准则分类器易陷入局部极小点，在小样本条件下易出现过学习；4 、祝恩 z h u 等，2 0 0 6 等提出利用神经网络进行方向图估计和指纹图像分割的方法，网络输入节点达到1 1 个，整个处理过程非常耗时；5 、赵衍运 赵衍运等，2 0 0 6 1 等提出方差和对比度为特征，训练用于分割背景的支持向量机，并用拟凸算法修正支持向量机的分割结果；6 、魏鸿磊 魏鸿磊等，2 0 0 7 等提出将指纹图像分块，并根据图像块的对比度特征进行初分割，以去除灰度变化较小的白背景块，对剩下的图像块提取方向偏差和频率偏差，并根据对比度、方向偏差和频率偏差三个特征分割出特征明显的前景块和背景块，采用支持向量机将经前两次分割不能判决的图像块分为前景和背景两类。1 3 本文的主要工作和行文结构本文在分析了指纹图像各种特征的分割性能的基础上，提出由指纹图像块内梯度一致性、灰度均值、灰度方差、主能量比、对比度五个特征组合在一起作为表征图像块的特征向量，可以很好地表达指纹前景区的特点；支持向量机最初是针对二类分类问题提出的，可以在小样本的情况下获得比较好的泛化性能，并且可以避免神经网络易陷入局部极值点以及容易出现过学习等问题。指纹图像的分割的目的是将指纹区域从背景区域3第一章前言中区分出来，可以看做是前景、背景的二类分类问题，因此可以用支持向量机的方法进行分割。本文由此提出了一种基于支持向量机的图像分割方法：将图像规格化后并分块，然后计算对比度并利用对比度进行初分割，对初分割后不能识别的图像子块提取其灰度均值、灰度方差、对比度、主能量比和梯度一致性作为表征该图像块的特征向量，采用训练好的支持向量机分类器进行判决，分为前景或背景两类，并结合形态学方法进行后处理，以进一步降低分割错误率。本文共分为六章，分别为：第一章主要介绍本课题的提出背景、目的及意义，对指纹图像分割技术的国内外研究现状进行总结，并介绍了本文所做的主要工作与行文结构。第二章介绍了统计学习理论，主要对机器学习问题的表示、经验风险最小化、复杂性与推广能力、学习机器的v c 维、推广性的界、结构风险最小化的相关内容进行了介绍，并对最优化的相关理论做了简单介绍。第三章介绍了支持向量机理论，主要介绍了支持向量机的思想、基本理论和特点、算法实现以及目前支持向量机算法的研究进展等。第四章介绍了图像分割的相关内容，对目前指纹图像分割的主流算法了做了介绍，并分析了其优缺点。第五章介绍了本文提出的一种基于支持向量机的图像分割方法，对方法的思路、流程做了详细介绍，并对方法的效果进行了实验验证。最后的结论总结了本文工作和创新之处，并针对存在的不足之处提出了未来的研究方向。4中国石油大学( 华东) 硕士学位论文第二章统计学习理论基于数据的机器学习是现代智能技术中的一个重要方面，研究从观测数据( 样本) 出发寻找规律，利用这些规律对未来数据或无法观测的数据进行预测，包括模式识别、神经网络等在内。现有机器学习方法共同的重要理论基础之一是统计学。传统统计学研究的是样本数目趋于无穷大时的渐进理论，现有学习方法也多是基于此假设。但在许多实际问题中，样本数往往是有限的，并且有时候还不知道数据之间内在相关性，因此常常使得一些理论上很优秀的学习方法在实际中的表现却差强人意。与传统统计学相比，统计学习理论( s t a t i s t i c a ll e a n i n gt h e o r y ，简称s t l ) 是一种专门研究小样本情况下机器学习规律的理论，该理论针对小样本统计问题建立了一套新的理论体系，在这种体系下的统计推理规则不仅考虑了对渐进性能的要求，而且追求在现有有限信息的条件下得到最优结果。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 ) 。支持向量机是在统计学习理论的基础上发展起来的一种新的机器学习方法，它基于结构风险最小化原则和v c 维理论，能有效的解决过学习问题，具有良好的推广性能和较好的分类精确性。它已初步表现出很多优于已有方法的性能。一些学者认为，s t l 和s v m 正在成为继神经网络研究之后新的研究热点，并将有力地推动机器学习理论和技术的发展。本章将对其基本理论进行概要的介绍【张学工，2 0 0 0 ；v a p n i k ，1 9 9 5 1 。2 1 机器学习的基本问题2 1 1 机器学习问题的表示机器学习的目的是通过某种训练方法，对某系统的输入与输出之间的依赖关系进行估计，并且期望这一估计能够对任意给定输入尽量准确地进行输出预测【边肇棋等，2 0 0 0 】。5第二章统计学习理论该闯题可以一般的表示为：变量y 与x 存在一定的未知依赖关系，即遵循某一未知的联合概率f ( x ，y ) ( x 和y 之间的确定性关系可以看作是其特例) ，机器学习问题就是根据n 个独立同分布观测样本( x l ，y 1 ) ，( x 2 ，y 2 ) ，( x n ，y n )( 2 1 )在一组函数 f l ( x ，w ) ) 中求一个最优的函数f ( x ，w o ) 对依赖关系进行估计，使期望风险r ( 叻= il ( y ，f ( x ，w ) ) d f ( x ，j ，)( 2 - 2 )最小，其中， f ( x ，w ) ) 称为预测函数集，w 为函数的广义参数， f ( x ，w ) 可以表示任意函数集；l ( y ，f ( x ，w ) ) 为由于用f ( x ，w ) 对y 进行预测而造成的损失，不同类型的学习问题有不同形式的损失函数。预测函数也称作学习函数、函数逼近或学习机器。有三类基本的机器学习问题，即模式识别、函数逼近和概率密度估计。对模式识别问题，输出y 是类别标号，两类情况下y = 0 ，l 或y = 一1 ，1 ) ，预测函数称作指示函数，损失函数可以定义为坳胞舻1 莎y 麓：，；矿，【x ，m使风险最小就是b y a e s 决策中使错误率最小。在函数逼近问题中，y 是连续变量( 这里假设为单值函数) ，损失函数可定义为l ( y ，f ( x ，夕) ) = ( y - f ( x ，w ) ) 2( 2 4 )即采用最小平方误差准则。而对于概率密度估计问题，学习的目的是根据训练样本确定x 的概率密度，记估计的密度函数为p ( x ，w ) ，则损失函数可以定义为l ( y ，f ( x ，y ) ) = 一l o g ( p ( x ，川)( 2 - 5 )2 1 2 经验风险最小化在上面的问题表述中，学习的目的在于使期望风险最小，但是，我们可以利用的信息只有式( 2 1 ) ，这使得式( 2 1 ) 的期望风险无法计算，因此传统的学习方法采用了所谓的经验风险最小化( e m p i r i c a lm s km i n i m i z a t i o n ，简称e r m ) 准则，假设概率分布是均匀的，即用样本数据来定义经验风险 张学工，2 0 0 0 1 。r e 坤( 们= 吉善三( 乃，厂( 薯，川) ( 2 - 6 )6中国石油大学( 华东) 硕士学位论文作为对式( 2 2 ) 的估计，设计学习算法使它最小化。对损失函数( 2 3 ) ，经验风险就是训练样本错误率；对式( 2 4 ) 的损失函数，经验风险就是平方训练误差；而采用式( 2 5 )损失函数的e r m 准则就等价于最大似然方法。事实上，用e r m 准则代替期望风险最小化并没有经过充分的理论论证，只是直观上合理的想当然做法，但这种思想却在多年的机器学习方法研究中占据了主要地位，即使可以假定当n 趋向于无穷大时，式( 2 6 ) 式趋近于式( 2 2 ) 式，在很多问题中的样本数目也离无穷大相去甚远，那么在有限样本下e r m 准则得到的结果就很难说能使真实风险也较小。2 1 3 复杂性与推广能力人们将学习机器对未来输出进行正确预测的能力称作推广能力。在传统学习理论中，人们总是把注意力集中到如何使经验风险最小，但是，训练误差小并不总能得到好的预测效果。在某些情况下，训练误差过小反而会导致推广能力的下降，即真实风险的增加，这就是神经网络中的过学习问题。之所以出现过学习现象，主要有两个原因：一是因为样本不充分，二是因为学习机器设计不合理，这两个问题是互相关联的。理论表明，经验风险与期望风险之间具有一定的差异，在小样本情况下，这种差异尤其明显。由于训练样本数的限制，基于经验风险最小化准则的学习机器在实际应用中普遍存在推广能力不足的问题。设想一个简单的例子，假设有一组实数样本( x ，y ) ，y 取值在【o ，1 】之间，那么不论样本是依据什么模型产生的，只要用f ( x ，a ) = s i n ( a x ) 去拟合它们( a 是待定参数) ，总能够找到一个a 使训练误差为零，但显然得到的“最优 函数并不能正确代表真实的模型。究其原因，是试图用一个十分复杂的模型去拟合有限的样本，以致丧失了推广能力。在神经网络中，若对有限的样本来说，网络学习能力过强，足以记住每个样本，此时，经验风险很快就可以收敛到很小甚至为零，但却根本无法保证它对未来样本能给出好的预测。学习机器的复杂性与推广能力之间的这种矛盾同样可以在其他学习方法中看到。文献 c h e r k a s s k y 等，1 9 9 7 给出了一个实验例子，在有噪声条件下用模型y = x 2 产生1 0 个样本，分别用一个一次函数和一个二次函数根据e r m 原则去拟合，结果显示，虽然真实模型是二次的，但由于样本数有限且受噪声的影响，用一次函数预测的结果更好。同样的实验进行了1 0 0 次，7 1 的结果是一次拟合好于二次拟合。由此可见，有限样本情况下：7第二章统计学习理论( 1 ) 经验风险对机器的性能有一定的影响，但不起决定作用，经验风险最小并不意味着期望风险最小；( 2 ) 复杂度高的学习机器，往往具有较低的经验风险。因此经验风险最小化准则的结果，将使学习机器变得越来越复杂；( 3 ) 学习机器的复杂性对其性能有较大的影响，学习机器的复杂性不但应与所研究的系统有关，而且要和有限数目的样本相适应。因此，如何根据实际问题，在学习机器的经验风险与模型复杂度之间取得合理的折衷，从而使机器学习具有更高的推广能力，需要一种能够指导我们在小样本情况下建立有效的学习和推广方法的理论。2 2 统计学习理论统计学习理论的重要结论之一就是关于推广性的界，与此相关的一个核心概念是v c 维。v c 维是描述函数集或学习机器的复杂性或者说是学习能力的一个重要指标，在此概念基础上发展出了一系列关于统计学习的一致性、收敛速度、推广性能等的重要结论。2 2 1 学习机器的v c 维经验风险模型在早期的机器学习问题中起到了非常重要的作用。传统的学习方法大部分以经验风险最小化作为模型，如最小二乘法、最大似然法、神经网络等方法，但理论上的固有缺陷决定了其无法解决“过学习”和“小样本学习问题 。经验风险模型片面追求最小的风险误差，算法难免会滑入“过学习 的陷阱。经验风险模型最小化的一致条件是在样本数量为无穷大时才成立，而事实上这种情况在现实世界中是不存在的，一个“过学习”的模型，其训练误差可能非常小，但泛化能力却有可能很差。现实世界里的学习样本都是有限的，建立有限样本情况下的机器学习问题模型才符合世界的本来面目。v a p n i k 等人在2 0 世纪6 0 年代开始研究有限样本情况下的机器学习问题，1 9 7 1年，v a p n i k 和c h e r v o n e n k i s 在文献 v a p n i k 等，1 9 7 1 1 中，提出了一个重要的理论基础一- v c 维理论，但它是建立在经验风险最小化原则基础之上，即：以训练的平均误差为最小的模型作为期望的最终模型。因此，直到9 0 年代初期，v c 维理论还没有得到很好的应用，在文献 c h e r k a s s k y ，1 9 9 9 ；v a p n i k ，1 9 9 9 1 q b ，v 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 n ，简称s r m 原则) ，在此基础上，8中国石油大学( 华东) 硕士学位论文v a p n i k 和他的a t & tb e l l 实验室小组提出了支持向量机方法，进一步丰富和发展了统计学习理论，使抽象的学习理论转化为通用的实际算法。到9 0 年代，逐渐形成了较完善的理论体系统计学习理论，在统计学习理论的基础之上发展出一种新方法一支持向量机，在解决小样本机器学习问题中表现出许多特有的优势，开始成为克服“维数灾难”和“过学习 等传统困难的有力手段。为了研究学习过程一致收敛的速度和推广性，统计学习理论定义了一系列有关函数集学习性能的指标，其中最重要的是v c 维概念。模式识别方法中v c 维的直观定义是：对一个指示函数集，如果存在h 个样本能够被函数集中的函数按所有可能的2 h 种形式分开，则称函数集能够把h 个样本打散；函数集的v c 维就是它能打散的最大样本数目h 。若对任意数目的样本都有函数能将它们打散，则函数集的v c 维是无穷大。有界实函数的v c 维可以通过用一定的阈值将它转化成指示函数来定义。v c 维反映了函数集的学习能力，v c 维越大则学习机器越复杂( 容量越大) 。遗憾的是，目前尚没有通用的关于任意函数集v c 维计算的理论，只对一些特殊的函数集知道其v c 维。比如在刀维实数空间中线性分类器和线性实函数的v c 维是r + 1 ，而上一节例子中 ，a ) = s i n ( a x ) 的v c 维则为无穷大。对于一些比较复杂的学习机器( 如神经网络) ，其v c 维除了与函数集有关外，还受学习算法等的影响，确定更加困难。对于给定的学习函数集，如何( 用理论或实验的方法) 计算其v c 维是当前统计学习理论中有待研究的一个问题 张学工，2 0 0 0 。2 2 2 推广性的界统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之间的关系，即推广性的界 v a p n i k ，1 9 9 5 。关于两类分类问题，结论是：对指示函数集中的所有函数( 包括使经验风险最小的函数) ，经验风险re m p ( w ) 和实际风险r ( w ) 之间以至少l - r 的概率满足如下关系 n a l w a , 1 9 9 7 ：r ( 川r 。卵( w ) + 以h ( 1 n ( 2 n h ) + 1 ) - l n ( r 4 ) ( 2 7 )其中，h 是函数集的v c 维，玎是样本数。这一结论从理论上说明了学习机器的实际风险是由两部分组成的：一是经验风险( 训练误差) ，另一部分称作置信范围，它和学习机器的v c 维及训练样本数有关，可以简单地表示为：第二章统计学习理论r ( 们r 。叩( 叻+ ( 办刀)( 2 8 )上式中置信范围中随h n 增加，单调上升。即当h n 较大时，置信范围中较大。用经验风险近似实际风险就存在较大的误差，因此，采用经验风险最小化原则，取得的最优解可能具有较差的推广性；如果样本数目较多，h n 较小，则置信范围就会很小，采用经验风险最小化原则，求得的最优解就接近实际的最优解。公式( 2 2 ) 表明，在有限训练样本情况下，当样本数1 1 固定时，学习机器的v c 维越高( 复杂性越高) ，则置信范围越大，导致真实风险与经验风险之间可能的差别越大。这就是为什么会出现过学习现象的原因。机器学习过程不但要使经验风险最小，还要使v c 维尽量小以缩小置信范围，才能取得较小的实际风险，即对未来样本有较好的推广性。需要指出，推广性的界是对于最坏情况的结论，在很多情况下是较松的，尤其当v c 维较高时更是如此( 当h n o 3 7 时这个界肯定是松弛的，当v c 维无穷大时这个界就不再成立 b u g r e s ，1 9 9 8 】) 。而且，这种界只在对同一类学习函数进行比较时有效，可以指导我们从函数集中选择最优的函数，在不同函数集之间比较却不一定成立。v a p n i k指出寻找更好地反映学习机器能力的参数和得到更紧的界是学习理论今后的研究方向之一 v a p n i k ，1 9 9 5 。2 2 3 结构风险最小化e r m 原则是目前绝大多数模式识别方法的基础，其定义为训练集上的平均错误率，用于对整个样本集的期望风险进行估计，它建立在样本数目足够多的前提下，致使各种方法只有在样本数目趋于无穷大时，其性能才有理论上的保证。而在样本有限时，e r m原则是不合理的，我们需要同时最小化经验风险和置信范围。其实在传统方法中，选择学习模型和算法的过程就是调整置信范围的过程，如果模型比较适合现有的训练样本( 相当于h n 值适当) ，则可以取得比较好的效果。但因为缺乏理论指导，这种选择只能依赖先验知识和经验，造成了如神经网络等方法对使用者“技巧的过分依赖【张学工，2 0 0 0 】。统计学习理论提出了一种新的策略即把函数集构造成为一个函数子集序列，使各个子集按照v c 维的大小排列；在每个子集中寻找最小经验风险，在子集间折衷考虑经验风险和置信范围，取得实际风险的最小，如图2 1 所示。这种思想称作结构风险最小化( s t r u c t u r er i s km i n i m i z a t i o n ，简称s r m ) 准则。统计学习理论还给出了合理的函数子集1 0中国石油大学( 华东) 硕士学位论文结构应满足的条件及在s r m 准则下实际风险收敛的性质 v a p n i k ，19 9 5 。风险函数集子集：铂吃缟险险v c 维：啊缟缟图2 - 1 结构风险最小化原理示意图f i g2 - 1s c h e m a t i cd i a g r a mo fs t r u c t u r a lr i s km i n i m i z a t i o np r i n c i p l e实现s i w 原则可以有两种思路：一是在每个子集中求最小经验风险，然后选择使最小经验风险和置信范围之和最小的子集。显然，这种方法比较费时，当子集数目很大甚至是无穷大时是不可行的。因此有第二种思路，即设计函数集的某种结构使得每个子集中都能取得最小的经验风险( 如使得训练误差为0 ) ，然后只需选择适当的子集使得置信范围最小，则这个子集中使经验风险最小的函数就是最优函数。支持向量机方法实际上就是这种思想的具体实现。c h e r k a s s k y c h e r k a s s k y ，1 9 9 7 对一些函数子集结构的例子和如何根据s r m 准则对某些传统方法进行改进的问题做了讨论。2 3 最优化问题及其基本理论最优化是人们在工程技术、科学研究、经济管理、交通运输和国防等诸多领域中经常遇到的问题，它讨论决策问题的最佳选择特性，构造寻求最佳解的计算方法 谢政第二章统计学习理论2 0 0 3 。早在1 7 世纪，n e w t o n 和l e i b n i z 发明微积分的时代，已经提出函数的极限问题，后来又出现了l a g r a n g e 乘子法，c a u c h y 的最速下降法。直到2 0 世纪3 0 年代，最优化的理论和方法才得以迅速发展，并不断完善，逐步成为- l - j 系统的学科。1 9 4 7 年，d a n t z i g提出了求解线性规划的单纯形法 d a n t z i g ，1 9 5 1 ，为线性规划的理论和算法奠定了基础。1 9 5 1 年，由k u l m 和t u c k e r 完成了非线性规划的基础性工作。到2 0 世纪7 0 年代，最优化方法无论在理论和算法上，都有了很大的发展，特别是计算机技术为最优化方法起了巨大的促进作用。2 3 1 最优化问题最优化问题 业宁，2 0 0 5 表示为如下形式：艘m i nf(sx(2-9)其中x = ( x t ，x 2 ，洳) 7 r ”为决策变量，f i x ) 为目标函数，ssr ”为约束集或可行域，它是所有可行解的集合。s = 缸l 蜀( x ) o ，江1 ，2 ，mh j ( x ) = o ，j = 1 ，2 ，( 2 - 1 0 )当目标函数和约束函数均为变量x 的线性函数时，公式( 2 9 ) 的问题为线性规划问题，当目标函数和约束函数至少有一个变量x 为非线性函数时，公式( 2 9 ) 的问题为非线性规划问题。支持向量机的求解问题最终归结为一个二次规划问题，二次规划是指目标函数为二次函数，约束条件是线性等式或线性不等式的规划问题。约束二次规划问题表示为：j m i n m 一1 ， 托。( 2 - 1 1 )l j j a x = 6 ，( 或 b ， b )其中，q 尺脓”且对称，c r ”，b r 肌，彳r 卅”，r a n k a - - m ( 3 1 )t = 1式( 3 1 ) 就是支持向量机在分类情况下的形式，其中，为支持向量对应的非零支持值，b 为偏置值。支持向量机的一个重要特征就是解的稀疏性，即求解得到的大多数都为0 ，只有少数的口，不为o 。因此在应用中只要少量样本( 支持向量) 就可以构成最优分类器，从而使样本数据大大压缩。3 2 支持向量机假定大小为，的训练样本集 ，y j ，i - - - 1 ，2 ，) 由二类模式组成：如果x i e r n属于第1 类，则标记为正( 胪1 ) ；如果属于第2 类，则标记为负( y , - - 1 ) 。学习的目标是构造一个判别函数，将两类模式尽可能正确地区分开来。下面针对训练样本集为线性可分、非线性可分两种情况分别加以讨论。3 2 1 线性支持向量机如果训练样本集是线性可分的，则存在分类超平面w x + b = 0( 3 - 2 )使得：耋：麓乃y j 三1 - 1m 心zp 3 ，w 薯+ 6 1 ，=、7其中，w x 表示向量w 与x e 的内积。式( 3 2 ) 和式( 3 3 ) 中的w r ，x r 都进行了规范化。每类样本集中与分类超平面距离最近的数据点满足式( 2 9 ) 的等式要求。对于式( 3 - 3 ) ，可写成如下紧凑形式：y i ( w 。x ，+ b ) 1 ，i = l ，2 ，( 3 - 4 )由统计学习理论知，如果训练样本集没有被超平面错误分开，并且距超平面最近的样本数据与超平面之间的距离最大，则该超平面为最优超平面( 如图3 - 2 所示) ，由此得1 6中国石油大学( 华东) 硕士学位论文到的决策函数oow x 士b =f 【x ) = s g n ( w x + b )w + b = - 1图3 - 2 最优超平面f i g3 - 2o p t i m a lh y p e r p l a n e线性支持向量机可以归结为下面的( 二次规划) 优化问题：蚵n 趟2第一类o第二类( 3 - 5 )靠近两个边界面的向量为支持向量w x + b = - 1s t ：p ( w f + b ) 1 ，i = 1 ，2 ，( 3 - 6 )引入l a g r a n g e 乘子口，可以得到如下对偶形式的优化公式：1f，m 去刚口缈( x y ，) 一口oi = l 2 l2 is t ：o , i = l ，2 ，z( 3 - 7 )o e y i = 03 2 2 非线性支持向量机在输入空间中构造最优分类面的方法类似于经典的感知器( 单个神经元) 方法。这种1 7第三章支持向量机方法仅当样本集为线性可分时才能使经验风险等于零。由于许多问题都不是线性可分的，因此用这种方法求得的解常常由于经验风险过大而失去意义。解决这个问题的一个方法是利用多层感知器，其实质就是将近似函数集由简单线性指示函数扩展成由许多线性指示函数叠加成的一个更为复杂的近似函数集，再用s 形函数来近似指示函数中的单位阶跃函数( 或符号函数) ，从而得到使经验风险极小化的一种容易操作的算法。但是，这种方法存在着容易陷入局部极小点，网络结构设计依赖于先验知识以及泛化能力较差这些问题。另外一种方法是将输入向量映射到一个高维的特征向量空间，并在该特征空间中构造最优分类面，这就是支持向量机方法，它能够避免在多层前向网络中无法克服的一些缺陷。并且经过证明可以得到如下结论：如果选用适当的映射函数，大多数输入空间线性不可分的问题在特征空间可以转化为线性可分问题来解决。在支持向量机的训练过程以及决策过程中，样本点是以内积的形式出现的。在支持向量机理论中，实现这一推广的重要手段是应用一个非线性的映射特征映射中，把样本从输入空间映射到某个高维的特征空间f ：r n 寸f( 3 - 8 )然后，在特征空间中对样本向量进行类似的操作，即支持向量机的训练与决策过程只依赖于特征空间中向量的内积运算，即( ) 矽( x j ) 。如果存在一个核函数k ( x i x j ) ，使得下式成立k ( x i x j ) = 矽( x ，) ( ) = ( ( x ，) ，( ) )( 3 9 )则只需在学习机的训练过程以及决策过程中，利用核函数来代替样本向量的内积，而无需知道映射中的具体表达式。将核函数k ( x i 均) 代入原规划问题以及对偶规划问题的表达式中，即可得到用于分类的非线性的支持向量机( 如图3 3 所示) ：幽警+ c p lp s t ：y t ( w 矽( x j ) + b ) l 一善，孝f 0 ，i = 1 ，2 ，以及它的对偶问题：1 8中国石油大学( 华东) 硕士学位论文m i n 去口，口t y j j y _ f k ( 。) 【j