（基础数学专业论文）局部泛化误差模型的改进及其在特征选择中的应用.pdf

摘要摘要网络的泛化误差是描述网络能否对未知样例进行正确分类的一个指标。网络敏感性是度量网络输入及其参数的扰动对网络输出产生影响的指标。这两个指标在指导网络设计、增强网络鲁棒性、度量网络性能等方面都有重要的作用。因此，结合神经网络敏感性和泛化误差进行研究是神经网络研究的热点之一。本文首先介绍了w i n gw yn g 的局部泛化误差模型( l g e m ) ，并指出了w m gw yn g 在l g e m 的理论推导中及w i n gw yn g 将该模型应用到特征选择时的不足之处。本文利用基于范数的思想，重新推导了该模型( n l g e m ) ，并结合实际应用的需要，进一步简化了该模型( l g e m w a ) 。我们也将该模型应用到了特征选择当中。在此基础上我们提出了一种三阶段法来处理日益严重的“维数爆炸 的问题。实验表明，在尽可能不降低网络的测试精度的前提下，本文提出的l g e m w a 模型及处理高维问题的三阶段法在特征选择中的应用非常实用有效。关键词敏感性分析特征选择局部泛化误差模型三阶段法a b s t r a c ta b s t r a c tg e n e r a j i z a t i o ne r r o ri su s e dt od e s 嘶b ew h e t l l e ro rn o t 也ec l a s s i f i e rc o u l dc l a s s i 匆u 1 1 s e e ns 锄叩l e sc o r r e c t l y s e n s i t i v i t yi sa 1 1i 1 1 d e xw 量l i c hm e 嬲u r e st l l er e s p o i l s eo ft l l en c 帆旧r kt ot 1 1 ep e r t u r b a t i o no f l en e 觚o r ki 1 1 p u to rp a r a m e t e r s t h e s et v 旧i n d e x e sa r eb o t l li m p o r t a n tt 0d e s 延mn e t v v o 比e i l l l a n c e 鹏铆o r kr o b 眦圮s s 觚dm e 弱u r em t 、) l ，o r kp e r f 0 m l a i l c e t h e r e f o r e ，t 0s t u d yo ng e n e r a l i z a t i o ne r r o rc o m b i i l e d 砌s e r l s i t i v 时删y s i si so n eo fm er e s e a r c hh o t s p o t so fn e u m ln e t v v or ：k s i i lt l l i sp a p e r w ef i r s ti n t r o d u c ew i n gw yn g sl o c a l i z e dg e n e r a l i z a t i o ne 玎o rm o d e l a n dw ep o 硫o u ts o r n el l i 】a s o n a b l ep o m t si nm o d e ld e r i v a t i o na n di t sa p p l i c a t i o nt 0f e a n 玳l e c t i o n t h e nw ep r o p o s ean o m - b a s e dl o c a l i z e dg e n e r a l i z a t i o ne n d rm o d e l ( n l g e m ) 洫o r d e rt 0a v o i dt l l e f l 鲫v so ft h em o d e lp r o p o s e db yw i n gw ：yn g a c c o r d i i l gt 0t h e嘲u i r e m e n t sf o r 印p l i c a t i o i l s ，w ep r o p o s ean e wl o c a l i z e dg e n e r a l i z a t i o ne r r o rm o d e lb a s e do nw e i 咖a v e r a g e ( l g e m - ，a ) w ea l s o 印p l yt l l i sm o d e it of b a t u r es e i e c t i o l l w eg o 缸t h e rt 0p r o p o s eat 1 1 r e e - p h a s em e 让1 0 di no r d e rt 0o v e r c o m e d i r n e i l s i o n a l i t ) ，c u r s e ”n l es i r n u l a t i i l gr e s u l t ss h o wt h a to u rp r o p o s e d 铆om e t l l o d sb o t l ip l a ye 疏c t i v et h _ a i lm eo t l l e r仃乏l d “i o i 试f e 锄卫- e l e c t i o na l g o r i 1 ：【粥k e y w o r d ss e i l s i t i v 蚵a 1 1 a l y s i s ；f e 叭鹏s e l e c t i o n ；l o c a l i z e dg e n e r a l i z a t i o ne n i o rm o d e l( l - g e m ) ；廿1 r e e - p h a s em e m o d河北大学学位论文独创性声明本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了致谢。作者签名：圣丝筮日期：垄丝年工月二鸯l 日学位论文使用授权声明本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。本学位论文属于1 、保密口，在年月日解密后适用本授权声明。2 、不保密( 请在以上相应方格内打“ )保护知识产权声明本人为申捌蝌学位所提交为量霎蒜釜拳躺的学位论文，是我个人在导师王熙括导并与导师合作下取得的研究成果，研究工作及取得教授的研究成果是在河北大学所提供的研究经费及导师的研究经费资助下完成的。本人完全了解并严格遵守中华人民共和国为保护知识产权所制定的各项法律、行政法规以及河北大学的相关规定。本人声明如下：本论文的成果归河北大学所有，未经征得指导教师和河北大学的书面同意和授权，本人保证不以任何形式公开和传播科研成果和科研工作内容。如果违反本声明，本人愿意承担相应法律责任。声明人：圣垫叁日期：型型l 年月卫日作者签名：圣丝叁导师签名：寻臼匕兰l日期：蚍月卫日第一章绪论1 1 研究工作的来源与意义第一章绪论弟一早殖下匕模式识别o 砒e mr e c o 鲥t i o n ) 是指对表征事物或现象的信息进行处理和分析，以对事物或现象进行描述、辨认、分类和解释的过程，是信息科学和人工智能领域的重要组成部分。而人工神经网络( 血t i 矗c a ln e u h 试n e t 、) l r o 血舢州) 则是模式识别技术中的一种方法。a 卜n 是由简单的信号处理单元组成的并行多分布信息处理器。砧州通过学习外界环境所提供的信号，把学习到的知识储存在网络结构中，并利用学习到的知识来处理新的信号。从计算数学的角度来看，当外界环境所提供的信号表现为一组数据时，学习的过程就是利用计算机对数据进行学习、模拟、逼近的过程，而处理新信号的过程就是预测的过程。在多层前馈型神经网络中，有两种网络应用的最为普遍：多层感知器神经网络( m u l t i l a y e rp e r c 印t i o nn e u r a ln e 铆。比m l p m 叼和径向基函数神经网络( r a d i a lb a s i sf 眦c t i o nn e u r a ln e 时o r k ，i 国f m 吣。在一定条件下，这两种网络都具有逼近任意光滑输入输出映射的能力。因此，对于一个函数逼近或者是模式分类问题，一般来说选择这两类网络模型中的哪一类都是可行的。然而，由于多层感知器神经网络具有收敛到局部极小点的缺点，再加上其训练速度比较慢，而径向基函数神经网络( r b 删不仅能收敛到全局最优点，而且训练速度也快，因此，i 啦孙n 得到了更加广泛的应用，r b 卧烈也是我们的研究重点。对神经网络的评价有多种方法，比如网络精度、泛化误差( 界) 、网络结构是否庞大、网络的敏感性分析等等。一个好的网络应该有好的泛化能力，相对简单的网络结构，网络的抗干扰能力强等特点。网络的泛化误差是一种衡量网络能否对未知样例进行正确分类的指标。但是在无先验知识的情况下，我们无法准确判断网络的泛化误差。通常是利用测试误差来近似或者通过交叉验证( c r o s s v a l i d a t i o n ) 的方法进行估计，也有学者通过理论分析，推导出网络泛化误差的上界【l 】来对网络的泛化能力进行评价。网络敏感性【2 7 】是评价神经网络性能的另一个重要参数。敏感性表征的是网络输入或网络参数的扰动对网络将会产生怎样的影响。它对于指导网络设计，增强网络抗干扰能力、度量网络性能( 如容错和泛化能力) 都有巨大意义。另外，网络敏感性分析也是1 河北大学理学硕十学位论文研究其它网络课题的基础，如网络结构的裁剪和参数的确定等等。特征选择在模式识别领域中扮演着一个极其重要的角色。一方面，在样本有限的情况下，用大量特征来设计分类器，无论是从计算开销还是从分类器性能来看都不合时宜；另一方面，特征和分类器性能之间并不存在线性关系，即当特征数目超过一定限度时，一、会导致分类器性能变坏。因此，进行正确有效的特征选择成为模式识别中必须要解决的问题，在海量数据条件下尤为重要。由于径向基函数神经网络的优越特点以及敏感性分析与泛化误差对网络的重要意义，那么结合径向基函数神经网络和敏感性分析及泛化误差进行研究是目前的研究热点之一，同时也是我们的关注点。例如，2 0 0 5 年，w i n gw y n g 等人在国际机器学习与控制会议( i c m l c 0 5 ) 上，针对径向基函数神经网络提出了局部泛化误差模型( l g e m )【l 】，该模型表明了分类器的局部泛化能力的上界与网络的训练误差和输入随机敏感性有关。但是局部泛化误差模型作为一种新提出来的模型，对其研究的不够深入，有不少地方需要继续讨论，也有地方需要改进。例如( 1 ) 建立模型的某些前提假设是否合理；( 2 )模型分析( 讨论模型适用范围) ；( 3 ) 模型的构成形式是否合理；( 4 ) 模型中半径q 大小的确定；( 5 ) 模型如何应用在特征选择中才合理有效。对高维数据集来说，并没有很好的特征选择算法。因此，我想针对这种情况，利用我们的研究成果提出一种组合式的算法：既要运行效率优于传统w r 印p e r 方法，也要使特征子集的分类精度比f i l t e r 方法高，还要好于当前存在的一般的组合式算法2 1 。1 2 课题的发展现状径向基函数是多维空间插值的传统技术，由p o w e l l 【1 3 】于1 9 8 5 年提出。1 9 8 8 年b r o o n l l l e a d 和l 0 w e 【1 4 】将径向基函数与前馈神经网络做了比较，并将r b f 插值技术用网络的观点给以解释( 即给出r b f 的网络形式：i 也f n n ) 。不同于传统多维空间i 强f 的严格插值技术，径向基神经网络为了处理训练数据中的噪音以及减少计算复杂性，中心的个数小于训练数据的个数，中心的选取也不限定在训练数据集上。后来发展了一系列对l m f n n 的训练方法。i m f n n 训练方、法【1 5 j 一般可分为：一阶段法、两阶段法、三阶段法。其中最常用的是两阶段法，即首先确定r b f n n 隐含层各个参数，然后利用伪逆或线性优化算法求神经元的连接权重。第一章绪论在神经网络设计中，由机器精度引起的权重扰动和噪音输入数据严重的影响了分类器的鲁棒性和泛化能力，这就是敏感性分析所考虑的问题。衡量神经网络的稳定性的重要参数敏感性究竟与神经网络的泛化能力有什么关系，曾一直困扰人们。在2 0 0 5 年，w i n gw y n g 等人在国际机器学习与控制会议( i c m l c 0 5 ) 上，提出了局部泛化误差模型【l l 。该模型表明了分类器的局部泛化能力的上界与输入随机敏感性和训练误差有直接关系，从而从理论的意义上说明了神经网络的泛化性能与输入随机敏感性之间的关系，文章中还结合局部泛化误差模型与r b f n n 的输入随机敏感性给出了一种训练r b 孙m 的方法。同年，在i n t 锄a t i o n a lc o n f 柏l c eo ni n s t n 蛐e n t a t i o n ，c 0 n 仃o l 觚di i l f o 姗a t i o nt e c l l i l o l o g ) ，会议上，d s y e 吼g 和w i n gw y n g 等人将局部泛化误差模型应用于i 强f n n 的特征选择【1 6 1 。关于局部泛化误差的更完善的版本已经于2 0 0 7 年发表在杂志i e e et r a i l s a c t i o n so nn e w a ln e t 、) i r o r k s 【1 7 】上。针对特征选择问题，g e o r g eh j o h n 【竭】等人就已经全面讨论了特征选择问题。m d a s h 和h l i u 【1 9 】对以前的特征选择方法进行了总结。在【1 9 】中，m d a s h 和h l i u 根据特征选择策略和评判准则，将特征选择方法进行分类。其中按评判准则可将特征选择算法分为：距离测度、信息测度、相关测度、一致性测度和分类错误率测度等五种；按搜索策略可将特征选择算法分为：启发式策略、完全搜索策略和随机搜索策略。在上述五个评判准则中，相关测度可以看作是从另外一个角度描述了距离测度、信息测度；而一致性测度是在用户事先选定某种距离测度( 或信息测度) 后，设置该测度允许的最大误差，从而在不超过这个误差范围的情况下，选择出规模更小的特征子集。因此，我们也可以将特征选择算法重新总结成：三种评判准则( 距离测度、信息测度、分类错误率测度) 和三种特征选择搜索策略( 启发式策略、完全搜索策略和随机搜索策略) 。1 3 本文的主要内容虽然局部泛化误差模型已经应用于r b 卧烈神经网络的特征选择问题中，但在实验中已经表现出的效果却并不令人满意，而且在模型的构建方面考虑的不是全面彻底，还有就是半径q 的影响没有给予应有的重视，并且在应用到特征选择算法时还有问题。那么，我的主要工作就是对模型进行改进，去掉模型中不合理的地方，克服或回避原模型应用中的难点，以期使该模型的表达能力更强，在特征选择中有更好的表现。河北大学理学硕+ 学位论文由于局部泛化误差的表现形式是线性加和，敏感性项是随半径q 单调增的而且其影响不可忽略，所以敏感性项可能会过多的影响该模型的表达能力。对此，我所做的工作就是利用加权平均的形式来改进该模型，通过赋予该模型各组成项不同的权重来克服( 回避) 半径q 的影响。该模型的计算量不是很大，但是在面对高维数据时，仍然会显得力不从心。若和传统的f i l t e r 方法相比，就更是相形见绌。现在已有学者采用将f i l t e r 和w r a p p e r 方法组合起来的办法，来利用它们各自的优点并克服其缺点【8 - 1 2 】。虽然取得了定成绩，但是效果并不令人满意：要么特征子集规模过大，要么分类精度过低。对此问题，我提出了一种新的组合方式( 三阶段法) 来克服上述缺点：第一阶段采用r e l i e 心法来去除大量的不相关特征：第二阶段采用p f a 方法去除大量的冗余特征：最后利用改进后的局部泛化误差模型对剩余的特征子集进行精选。这样会尽可能的缩小特征子集的规模，还能保证特征子集的分类精度不会有大的变动。本文的组织结构如下：1 第2 章介绍一些本文在研究中将要用到的基础知识，主要包括径向基函数神经网络( i m f n n ) 的基本原理、网络结构、计算公式、训练策略及特征选择的常用方法。2 第3 章介绍了w i n gw y n g 的局部泛化误差模型( l - g e m ) ，其中包括模型的基本思想、建立以及推导过程，并且给出了该模型在推导过程中存在的不足之处。3 第4 、5 章是本文的核心内容。在第四章，本人给出了一种改进的局部泛化误差模型( n l g e m ) ，并根据实际应用的需求，对其进行了简化( 【广g e m w a ) 。还对w i n gw y n g 所采用的特征选择算法进行改进，并给出了相应的实验证明：虽然，该模型相对于w i n gw y n g 的局部泛化误差模型在时间复杂度及泛化能力上都有不小的提高，但是，当面对高维数据时，仍显力不从心。为此，在第五章，本人根据在高维空间中的特征选择的需要，适时的提出了综合利用f i l t e r 和w r a p p c r 法优点的三阶段法。实验证明该方法是一种有效的特征选择算法，即能尽可能的去除不相关和冗余特征，又能尽可能的保证结果特征子集的泛化能力。第二章预备知识第二章预备知识这一章将介绍在研究过程中用到的一些基本知识：径向基函数神经网络( i m 删的网络结构、计算公式、训练策略及特征选择的常用方法。2 1 径向基函数神经网络( i m f d2 1 1 人工神经网络的发展简史人工神经网络( a n i f i c a ln e i 】r a ln e 附o d ( ，伽、n ) 是人工智能领域的重要分支之一。1 9 4 3 年，心理学家m c c u l l o c h 和数理逻辑学家w p i t t s 【2 0 】共同提出了兴奋与抑制型神经元模型，其目的是通过计算机建立一种模型去模拟人脑的功能。后来，h e b b 提出的神经元连接强度的修改规则，标志着神经科学理论研究时代已然来临。随后，许多学者都对神经网络的发展做出了不可磨灭的贡献。但是到了2 0 世纪6 0 年代，由于感知器本身的某些局限性及其一些其它因素，使得人工神经网络的研究步入了低潮期。直到8 0 年代中后期，由于物理学家h o p f i e l d 【2 l 】提出的h o 西e l d n e u r a l n e 铆o r k ( h n n ) 模型，引入了能量函数的概念，给出了网络稳定性的依据，解决了神经网络发展中的瓶颈问题，这才又一次的使神经网络成为研究的热点。值得一提的是：r u m e l h a n 、h i l l t o n 和w i l l i a m s 【2 2 】于1 9 8 6年共同提出的多层前馈型神经网络的新型训练算法：误差反传( b a c k p r o p a g a t i o 玛b p ) 算法，成功的解决了感知器所不能解决的问题。该算法对神经网络的发展和应用产生了较为深远的影响。在多层前馈型神经网络中，有两种网络应用的最为普遍：多层感知器神经网络( m l p n n ) 和径向基函数神经网络( r b 卧n ) 。在一定条件下，两种网络都具有逼近任意光滑输入输出映射的能力。因此，对于一个函数逼近或者模式分类问题来说，选择这两种网络模型中的哪一种都是可行的。但是，由于m l p n n 不仅有收敛到局部极小的缺点，而且该网络的训练速度也比较慢，而r b n 不仅具有能收敛到全局最优的特点，而且还具有训练速度快的优点，所以，r b 阶烈得到了更广泛的应用。河北大学理学硕十学位论文2 1 2 径向基函数神经网络径向基函数神经网络( r a d i a lb a s i sf u l l c t i o nn e u r a ln e 咐o r k ，r b 孙烈) 是一种源于径向基函数插值技术的非线性前馈神经网络。p o w e n 于1 9 8 5 年构造出了径向基函判1 3 1 ，并且将其应用到了对高维空间中的数值插值技术中，并且还证明了在各种情况下，径向基函数插值技术的效果，都要优于其它插值技术，是最优的插值技术。m i c c h e l l i 也对这种插值技术做出了突出的贡献【2 3 】。径向基函数插值就是利用( 2 1 ) 式所表示的函数，对空间中的数值点进行数值拟合，尽可能地再现数值点所在的曲面。置f ( x ) = w o + w 妒( 卜堋扛i( 2 1 )其中，w o 为阈值，起调节输出的作用。心为伊( ) 的权重。而妒( 1 i | 1 ) 是径向基函数( 即激活函数) ，将n 维实向量映射到实数空间，这里的是n 维实向量空间上定义的一种范数( 比如：e u c l i d 范数) 。吩= ( 。，) 2 吼”是径向基函数的第i 个隐含节点的激活函数的中心向量。r b f 插值技术中，最经常采用的激活函数有：1 m u l t i q u a 血c s 函数缈( ，- ) = ( ，2 + 6 2 ) 2 ，6 o ，吼( 2 2 )2 e r s e 咖l t i q u a 越c s 函数妒( r ) 2 i j j 谤，6 。，孵( 2 3 )3 g a u s s 函数卅，= 唧( - 砉 ，孵眨4 ，其中，高斯函数应用的最为广泛。当径向基函数插值技术的逼近函数采用高斯函数时，( 2 1 ) 式就可以表示为：m h + 喜w 唧 - 呀亿5 ，f ( x ) = + w e x p | - 喾l( 2 5 )扭lil ，fj第二章预备知识基于这种径向基函数插值技术，b r o 伽f l l l e a d 和l o w e 【2 4 】提出了径向基函数神经网络。从公式可以看出，径向基函数神经网络是一种只含有一个隐含层并且隐含层神经元的激活函数采用径向基函数、输出层为线性函数的前馈型神经网络。径向基函数神经网络的典型结构，如图2 1 所示：图2 1 径向基函数神经网络结构图径向基函数神经网络( r b f n n ) 中的不同神经元层在处理信息过程中起着不同的作用。输入层由感知结点组成，是网络与外界环境的联接纽带，接受外界环境提交给网络的输入信号。隐含层由许多非线性神经元组成，将网络接收到的输入信号通过一个非线性转换映射到高维空间中。输出层由线性神经元组成，神经元的个数取决于网络要处理的问题。相邻两层的神经元之间都是全连接，相邻两层之间的信息传递就是通过这些全连接完成。另外，在输出层的阈值，起调整输出的作用。因此，径向基函数神经网络对数据的处理过程可简述为：先对输入的数据进行非线性的变换，接着又进行了一次线性变换，最后由阈值调节大小后输出。2 1 3 径向基函数神经网络的训练策略以激活函数采用g a u s s 函数的r b f 神经网络为例，说明径向基函数神经网络( i m n 烈) 的训练过程( 即确定网络的各个参数的过程) 。由( 2 5 ) 式可知，网络中需要确定的参数有隐含层神经元的个数、中心、宽度以及输出层与隐含层间的连接权重。由于径向基函数神经网络的不同层在网络中起着不同的作用，因此，就要分别采取不同的训练策略来优化隐含层和输出层的各个参数。在隐含层节点数目一定的情况下，径向基函数神经网络参数的训练过程一般可分为两个阶段【l5 】：先利用无监督方法( 例如k - m e a l l s )确定隐含层各个节点的中心“，和宽度盯；，再用线性优化的方法确定连接权重w 。由于在上述两个阶段均存在快速算法，从而使得径向基函数神经网络具有快速的学习速度。7 一河北大学理学硕+ 学位论文径向基函数神经网( r b n 烈) 是一种应用广泛的静态网络，它与函数的逼近理论相吻合，适合于多变量的非线性函数逼近，且具有唯一的最佳逼近点。径向基函数神经网络的特殊性在于它的隐含层神经元结点与输出层神经元结点的完全不同上。径向基函数理论是数值计算学科的一个主要领域【2 5 1 ，它给网络的隐含层结点的构造提供了强大的理论基础；径向基函数神经网络的理论研究也是与径向基函数理论密不可分的。输出层的权重与输出呈现出一种线性关系，并且这些权重的调整规则可以通过线性自适应滤波器来进行调整【2 6 】。2 3 特征选择特征选择是模式识别的重要组成部分之一，主要有两方面的应用：1 ) 从特征空间中选择一个维数更小的特征子空间，以最好的表达某个类自身；2 ) 从特征空间中选择一个维数更小的特征子空间用于更好的区分不同类别。本文主要着眼于特征选择在第2方面的应用，即如何从特征空间中选择一个特征子空间，使其能最优的用于分类识别，获取最高的分类识别率。既然要从特征空间中选择一个维数更小的特征子空间，就必须解决下面两个问题：1 ) 采用怎样的搜索策略，在允许的时间内，以可以忍受的代价找出最小的、最能描述类别的特征组合：2 ) 以怎样的评价标准j ，来衡量特征组合是否最优。因此，一般分两步进行特征获取：先产生特征子集，然后对子集进行评价，如果满足停止条件，则操作完毕，否则重复前述两步直到条件满足为止。下面将从这两方面对特征获取进行分类。2 3 1 按照搜索策略分类按照搜索策略( 特征子集的形成方式) ，特征选择方法可分为穷举法( e 】【l l a u s t i o n ) 、启发法( h e 嘶s t i c ) 和随机法( r a l l d o m ) 三类，如图2 2 所示：( 1 ) 完全搜索策略1 ) 穷举法穷举法就是把所有特征的各种可能的组合的判别准则j 都算出来再加以比较，从中选择最优的特征子集用于分类识别。其优点是不仅能给出全局最优的特征子集，还能全第二章预备知识面了解所有特征对各类之间的可分性信息。缺点是当数据的维数很高时，穷举法的计算量太大无法实现。2 ) 分支定界法1 9 7 7 年，p m n a 舰d r a 和k f u k u n a g a 【硼提出了到目前为止、唯一能得到最优结果的优化搜索方法：“分支定界 算法。特征选择ll、i完全搜索随机搜索不完全搜索i，、，、，、，、穷分遗模监启发式举支传拟独团圆法定算退最界法火优l r 法图2 2 按搜索策略分类的特征选择算法分支定界法是一种自上而下的方法，具有回溯功能，可使所有的特征组合都被考虑到。由于合理地组织搜索过程，使得有可能避免计算某些特征组合且不影响寻找最优结果。但是该方法要求判断准则( 函数) 必须满足单调性，而且分支定界的计算量也很大难于实现，因此分支定界法的应用也受了很大的限制。( 2 ) 不完全搜索策略虽然完全搜索策略可保证找到全局最优的特征子集，但是由于它的时间复杂度太大无法承受，故而我们退而求其次，也就是要找满足一定精度要求的次最优特征子集。找次最优特征子集会用到如下两类搜索策略：1 ) 单独最优策略单独最优就是计算各个特征单独使用时的判据值，并根据其判据值的大小对特征加以排队，取前d 个特征作为选择结果。但是即使各个特征是统计独立的，这一结果也不dd一定就是最优结果。只有当可分性判据j 可写成，( x ) = ，( 五) 或j ( x ) = 兀j ( x ；) 时，这种f = li - l方法才能选出一组最优的特征来。2 ) 启发式搜索算法河北大学理学硕十学位论文顺序前进法( s e q u e n t i 2 1 1f o 刑a r ds e l e c t i o 玛s f s )顺序前进法是最简单的自下而上搜索方法，每次从未入选的特征中选择一个特征，使得它与已入选的特征组合在一起时所得j 值为最大，直到特征数增加到d 为止。一般说来，由于顺序前进法考虑了所选特征与已入选特征之间的相关性，因此它会比上面讲的按单独使用时j 值最大的选择方法好些。其主要缺点是：一旦某个特征已入选，即使由于后加入的特征使它变为多余，也无法再把它剔除。顺序后退法( s e q u e n t i a lb a c k 删s e l e c t i o n ，s b s )与s f s 法恰恰相反，这是一种自上而下的搜索方法。从全体特征开始每次剔除一个，所剔除的特征应使仍然保留的特征组的j 值最大。与顺序前进法比较，顺序后退法的优点是：在计算过程中可以估计每去掉一个特征所造成的可分性的降低。缺点是：由于顺序后退法的计算是在高维空间进行的，所以计算量比顺序前进法要大。( 3 ) 随机搜索策略随机搜索策略的特征选择方法包括：模拟退火法【2 8 】和遗传算澍2 9 】等。其中模拟退火法是利用了材料统计力学中的研究成果，将物理学中的模拟退火思想应用于优化问题；遗传算法受到了达尔文进化论的启发，比完全搜索策略有着更高的搜索效率。同时，它又比其它传统搜索方法具有更加顽强的鲁棒性。由于该策略不是我们研究重点，故此本文不做过多论述。2 3 2 按照特征子集的评价准则j 分类我们根据判断特征子集的评价准则是否利用分类器的信息，将特征选择方法可分为f i l t e r s 和w r a p p e r s 方法。各种方法的关系如图2 3 所示：( 1 ) f i l t e r 方法f i l t e r 方法与分类器无关，只是利用数据集的统计信息来进行特征选择，只依赖于相应的相关性测度的定义。常用的f i l t e r 方法有：r e l i e f 法，f i s h e r 法，属性和类的相关性测度，基于类可分离性测度等等。下面我们只介绍两个常用的算法：1 ) f i s h e r 准则f i s h c r 准则是特征选择的有效方法之一，其主要思想是：鉴别性能较强的特征表1 n 第二章预备知识现为使类内距离尽可能的小，类间距离尽可能的大。这里采用单个特征的f i s h e r 作为准则，对特征进行排序，选出那些鉴别性能较强的特征，从而达到降维并得到较好的识别性能的目的。特征选择判断准则，f i h e re i n b e d e d混合方法w 嘲p p e f sf ，f，fl 岜盘r ，二芏，l ，i瞵的可i 相羹性i 巨霎群1 分离性，ll，l 电e 扣久验证泛化相似性阿分离- 相关性判别式分析模型耩度误差图2 3 按评价准则分类的特征选择算法考虑一个c 类的分类问题。假定每一类训练数据( 向量) 有吩个，即 ，毫， 。类i 的先姗率为号2 袁，第t 类的均值儿。丢喜弓，第i 类数据的协方差矩阵墨= 丢善( 弓一以) ( 弓一鸬) r和c全部数据的均值= b 肛。类内散度( w i t l l c l a s ss c a t t e r ) 矩阵和类间散度( b e t 、) l r e 铋c l 硒ss c a t t e r ) ) 分别cs ，= 鹃f = l最：至露( 以一) ( 雎一) t则相对于第k 个特征的f i s h e r 准则为：( 2 8 )为：( 2 9 )( 2 1 0 )河北大学理学硕七学位论文f i s h e r ( 七) = 斋( 2 1 1 )其中磁”和磷分别为矩阵毛与乱对角线上的第k 个元素。根据每个特征的f i s h e r 值的大小由大到小，将特征排序。我们可以选择前q 个特征或者其f i s h e r 值大于某个阈值的特征作为最终特征选择的结果。2 ) 属性和类的相关性测度( a 嘶b u t e c l a s sc o 玎e l a t i o nm e a s u r e )该准则是用来衡量属性与类之间的相关性的一种方法。相关因子越大，该属性对判断该数据是哪一类的重要性也越大。其定义如下：q = l 乏一讲m 彬( 咒一乃)( 2 1 2 )其中，、工捕分别是第i 与第j 个数据的第k 个属性，且朋咖，= 端亿柳该方法的一个主要的缺点是不能有效的反映输入输出承非线性关系时的情况。f i l t e r 方法的优点是：1 ) 该方法可以很快的排除大量的非关键性的噪音特征，缩小优化特征子集的搜索规模；2 ) 由于该方法只考虑数据本身的统计特性，独立于任何分类器，因此该法获得的结果有更好的推广价值。缺点是：1 ) 一般的情况下，该方法获得的特征子集的规模较大( 在其中可能会包含一些明显的噪音特征) ；2 ) 精度较w 泖p e 塔方法差一些。( 2 ) 、脚a p p e r s 方法该方法把分类器的相关信息应用到特征选择当中。w r a p p e r s 方法中有直接利用验证精度( v a l i d a t i o na c c u r a c y ) 作为判别准则的，也有利用l e a v e o n e o u t 方法估计分类器的泛化误差作为判别准则的方法。1 ) 基于验证精度( v a u d a t i o na c c u r a c y ) 的w r a p p e r 方法a v 鲥k 嬲和m b a c a u s k i e n 2 0 0 2 ) 【3 1 1 就是利用验证精度作为判别准则的。其特征选择过程如下：每删除一个特征( 保留其它特征) ，训练一次网络，使得能计算一次测试误差：选择测试误差最小时所对应删除的特征作为最不重要( 1 e a s ts a l i e n t ) 的特征，彻底删除；重复上述操作，直至特征候选集中已无特征可选。这样就得到了一个按着特征不重要程度由大到小排列的特征序列。由于训练过程中的随机性的影响，故上述求特征第二章预备知识序列的过程可多重复几次，然后根据结果求得一个尽可能反映实际情况的特征序列( e x p e c t e df e a t u r er a i l l ( i n g ) 。最后，根据这个特征序列用神经网络一个特征接一个特征的进行验证，决定取舍。2 ) 基于泛化误差的研a p p e r 方法( l e a v e 叫d n e o u t )由于泛化误差不能直接计算出来，因此大部分情况都是利用交叉验证的方法对其进行估计。而l e a v e o n e - o u t 是b ie ta 1 ( 2 0 0 3 ) 【3 2 】提出的一种搜索策略。该方法在每一步的迭代中，依次只临时删除一个特征，然后利用交叉验证法估计相应分类器的泛化误差；最后再彻底删除与产生最小泛化误差分类器相对应的特征即可。重复上述操作，直至泛化精度急剧下降为止。相对于f i l t e r s 方法，w r a p p e r s 方法的优点有：1 ) 由该方法获得特征子集具有的分类精度要高于f i l t e r s 方法的；2 ) 由于该方法利用泛化精度的信息，因此w a p p 懿方法具有较好的泛化能力；3 ) 特征子集的规模小。其缺点为：1 ) 计算复杂性较大；2 ) 该方法的结果与分类器相关。例如：利用神经网络得到的( 次) 最优特征子集对s v m 来说就不一定是( 次) 最优特征子集。3 ) 混合的方法鉴于f i l t e r s 和w r a p p e r s 方法其各自的优缺点，已有很多学者【8 - 1 2 1 在综合利用f i l t e r s和w r a p p e r s 方法方面做了不少的工作。河北大学理学硕十学位论文第三章局部泛化误差模型w i n gw y n 寸u 指出，由于那些距离已知数据很远的未知数据与已知数据相差悬殊，使得分类器从已知样本中学习到的经验，不足以反映未知样例的相关信息，这就使得预测这样的样本本身就没有多大意义，因此，w i i l gw y n g 指出忽略那些距离训练数据很远的样例，只考察那些在训练样例附近的样例，并以此局部范围( 空间) 作为全空间，估计分类器的泛化能力。在w i n gw y n g 的模型中所采用的局部范围是：在每个训练样例的周围产生一个均值为。的均匀分布的扰动( 毛) = 工ix = 屯+ 缸；i 缸l q ，江1 ，刀 ，( 屯) 所代表的区域就是样例屯的q 邻域。所有样例的q 邻域的并集组成了输入空间的一个子集，就是w i n gw y n g 所考察的局部空间。w i n gw y n g 以此思想为指导，推导出了局部泛化误差模型，并将其应用到了特征选择当中。3 1 训练样例的q 一邻域对每一个训练样例x 。都可以找到一个样例x 的集合，使得l 缸i q v f = l ，刀其中，q 为一给定的非负的常数，n 为样例的特征个数。在这里，缸可以看作是输入向量的服从均值为0 的均匀分布的扰动。则，样例屯的q 一邻域为：( 吃) = x ix = 矗+ 缸；i 鼍l q ，v f = l ，刀)( 3 1 )令为邻域& ( ) 的并集。3 2 局部泛化误差模型( l g e m )令在整个输入空间t 考虑的泛化误差的界为，与之对应的在局部空间q 邻域内考虑的分类器的泛化误差的界为，分类器关于那些被忽略的远离q 一邻域的未知样例1 4 第三章局部泛化误差模型的泛化误差界为如，则有：图3 12 0 个样例的q 邻域的不例说明，其中x 为训练数据，在阴影区域的点为未知样例( q ) 2 r 批一( g )= j 1 0 ( 石( z ) 一f ( z ) 2 只z ) 卜令少= 石( x ) 一石( 毛) ，( ) = 石( 而) 一，( 毛) ，则有= ( 1 ) ( ( 毛) ) 2 ，( ( y ) 2 ) 2 吉善。，( 缈) 2 西出，s = 曰撕而而，其中，a ，b ，n 分别为目标输出的最大值与最小值之差，均方误差( m s e ) 的最大可能值和训练样例的个数。另外，我们假定已知目标输出的值域已知，则a 已知。而b 是可以求得的，因为一旦训练分类器的过程结束，我们就可求得神经网络的所有输出。根据常识，我们认为分类器在未知样例的误差要大于在训练样例的误差，则有在区域( ) 内的未知样例误差的平均值要大于分类器在样例毛上的误差。由h o e 髓i i l g 不等式可知，下面的不等式以概率为l 一7 7 的可能成立：( q ) 专善。，( 厂( 工) 一f ( x ) ) 2 击出+ g：三争ff 厂( 工) 一厂( 毛) + 石( 吃1 上出+ g智。( i f ( 毛) + ，( ) 一，( 功( 2 q ) ”专善“纠击出+ 专喜“吲枷2 击出河北大学理学硕十学位论文+ 专善。，( f ( 吃) 一，( x 炉西出+ 2 顺专善纠击出烩喜c 删2 击却+ 2 扳专砉毗炉击出峙善盹c 砌2 击司+ 2 顶专喜u 埘击出峙善“盹，2 击刁+ 占( 府厄面两a ) 2 + g= 赡( q )其中，f ( x ) 为待求的真实输入输出映射函数，石( x ) 是为估计函数，( 工) 而训练的分类器，9 为在某一定义域的参数集。如( q ) = ( 厨厄面对a ) 2( 3 2 )就是我们要求的局部泛化误差的上界( 简记为l - g e m ) ，其中r 。，为训练误差，e s a ( ( 每) 2 ) 被定义为敏感性，a 为目标输出最大值与最小值之差，即为某个未知的但又确定的值。由于e s q ( ( 少) 2 ) 难于求得，w i n gw y n g 等人又给出了针对i 沿f 神经网络的，从统计的角度求得的计算公式：e s 口( ( 每) 2 ) 三q 2 萋乃+ 警q 4 萋彭( 3 3 )e s 口( ( 少) 2 ) 专q 2 乃+ 詈q 4 彭( 3 3 )这里，纺= ( ) 2 唧( ( 玩，( ) 2 巧) 一( e ( _ ) 巧) ) ，乃= 纺( e ( s ，) 0 ) 和白= 纺嵋。3 3 局部泛化误差模型在特征选择中的应用w i n gw y n g 等人将l - g e m 应用到了结构选择、特征选择和样例选择等三个方面。在本部分，我们只介绍、m n gw y n g ( 2 0 0 6 ) 【1 】提出的基于局部泛化误差模型的特征选择的方法。该方法通过对局部泛化误差界的估计，综合考虑了训练误差与网络敏感性对特征选择的影响。因此从理论上讲，我们对该方法有较大的期望值。1 6 -第三章局部泛化误筹模型总体来说，w i n gw y n g 采用的是顺序后传( s e q u e i l t i a lb a c k w a r ds e l e c t i o n ，s b s )的搜索策略。在每一步的迭代中，与l e a v e o n e o u t 相比，w i n gw y n g 并不在每删除一个特征后，重新训练分类器以估计泛化误差界，他只是简单的把原分类器相应特征的值附为o ，来简化误差界的计算。这样做当然大大的减少了计算复杂度，节省了时间。令c f s 为候选特征子集，疆s 为最不相关特征子集，则其算法具体如下：1 ) 将c f s 初始化为整个特征子集，i f s 为空集；2 ) 用在c f s 中的特征训练分类器；3 ) 为在2 ) 中训练的分类器计算泛化误差的上界硷( q ) ；4 ) 为在c f s 中的每个特征计算南( 一南( q 协) ；5 ) 找到与如( q ) 一瑶( q ，口) ) 的最小值相对应的特征i 。将特征i 从c f s 中删除，并将特征i 加入i f s ；6 ) 如果c f s 非空，返回2 ) ；否则，跳出。3 4 局部泛化误差模型本身及其在特征选择应用当中的缺点通过分析w i n gw y n g 模型的求解过程，我们不难发现：为了克服泛化误差难以求得等困难，w i n gw y n g 做了一些假设并使用了一些数学技巧，推导出一个可以用于估计网络泛化误差的上界，且计算复杂度较低，易于实现。但是，某些假设和技巧存在一些理论上的不足之处，而且在应用到特征选择上时也有些不妥，理由如下：1 过多的使用不等式进行放大，刻意的将结果凑为经验误差、敏感项、常数项三项，缺乏合理性。而且，这样得出的上界太大，与真正的泛化误差有较大出入。2 在敏感性项的计算过程中，w i n gw y n g 假设特征间是独立的，这种假设在很多时候并不成立，尤其是在高维空间时。这种假设势必会影响的模型的适用范围。3 由上一节可知，w i n gw y n g 在将局部泛化误差模型应用到特征选择算法时，采用的是顺序后传( s e q u e i l t i a lb a c k w a r ds e l e c t i o n ，s b s ) 的搜索策略。而且，在每一步的迭代中，与l e a v e - o n e o u t 相比，w i n gw y n g 并不在每删除一个特征后，重新训练分类器以估计计算泛化误差界，他只是简单的把原分类器相应