（计算机软件与理论专业论文）relieff特征估计在流形学习中的应用.pdf

ad i s s e r t a t i o ns u b m i t t e dt og u a n g d o t e c h n o l o g yf o rt h ed e g r e eo f m a s t e ro f a p p l i c a t i o no fr e l i e f ff e a t u r ee v a l l e a r n i n g m a s t e rc a n d i d a t e ：y i n g y il i a n g s u p e r v i s o r ：a s s o c i a t eproftaizheupervisor：associate r o ia l z n e ia n m a y2 0 1 0 f a c u l t yo fc o m p u t e r g u a n g d o n gu n i v e r s i t yo ft e c h n o l o g y g u a n g z h o u 。g u a n g d o n g ，p r c h i n a ，5 1 0 0 9 0 特征提取是数据挖掘、 的是删除无关信息、冗余信 度以及提高模型泛化能力等 流形学习的基础上引入r e l i e f f 特征估计方法。主要研究工作有： ( 1 ) r e l i e f f 特征估计方法与流形学习的结合。本文提出的改进算法r e l i e f f m 针 对流形学习存在的对噪声敏感、易受缺失值影响问题以及现实世界数据的结构复杂性 和稀疏程序大等问题，引入了r e lj e f f 特征估计以改进流形学习方法的不足。实验结 果表明，改进算法不仅能够抗噪声、处理缺失值，而且也提高了特征选取后数据集的 分类准确率。 ( 2 ) 本文使用了流形学习中有代表性的局部线性嵌入算法，r e l i e f f 特征估计方 法，u c l 中的a c e n e 数据集，l i b s v m 分类器以及w e k a 数据挖掘工具进行实验。分四种 情况：一是不使用特征提取方法；二是仅使用r e l i e f f 特征估计方法；三是仅使用局 部线性嵌入算法；四是使用r e l i e f f m 算法。通过一系列的实验结果分析比较，得出改 进算法的分类准确率分别比单纯使用r e li e f f 特征估计方法和局部线性算法都要高。 ( 3 ) 设计并实现了一个r e l i e f f m 系统。该系统能够对给定的数据集首先进行特征 估计，然后对特征选择结果进行流形学习，最后使用i i b s v m 分类器并加以1 0 层交叉 验证。该系统的实现有利于对特征提取后的数据集进行后期分析和处理。 关键词：特征提取，维度归约，r e l i e f f ，流形学习 广东工业大学硕士学位论文 i i i i a b s t r a c t a bs t r a c t f e a t u r es e l e c t i o ni so n eo ft h ek e yi s s u e si nt h er e s e a r c ho fd a t am i n i n g ，m a c h i n e l e a r n i n ga n dp a t t e rr e c o g n i t i o n t h ea i mi st or e m o v ei r r e l e v a n ta n dr e d u n d a n ti n f o r m a t i o n ， r e d u c et h ed i m e n s i o n a l i t yo ft h e f e a t u r es p a c ea n dt h es t o r a g e ，r e d u c en o i s ea n d c o m p u t a t i o n a lc o m p l e x i t y ，a n di m p r o v et h eg e n e r a l i z i n gc a p a b i l i t yo ft h em o d e l t h e p a p e rr e s e a r c h e s o nan e wf i l t e r - w r a p p e rm o d e lf e a t u r e s e l e c t i o nm e t h o d ，t h a ti st o i n t r o d u c er e l i e f ff e a t u r ee v a l u a t i o ni n t om a n i f o l dl e a r n i n g i t sm a j o rw o r ki sa sf o l l o w i n g ： ( 1 ) t h ec o m b i n a t i o no fr e l i e f ff e a t u r ee v a l u a t i o na n dm a n i f o l dl e a r n i n g t h ei m p r o v e d a l g o r i t h m r e l i e f f mi nt h e p a p e ra p p l y r e l i e f ft om a n i f o l d l e a r n i n ga g a i n s t i t s n o i s e - s e n s i t i v ep r o b l e m ，v u l n e r a b l et ot h em i s s i n gv a l u e s ，t h ec o m p l i c a t e ds t r u c t u r eo fd a t a i nt h er e a lw o r l d ，t h el a r g es p a r s e n e s sa n ds oo n ，i no r d e rt oi m p r o v em a n i f o l dl e a r n i n g a l g o r i t h m s t h ee x p e r i m e n t a lr e s u l ts h o wt h a tt h ei m p r o v ea l g o r i t h mc a nn o to n l yh a n d l e n o i s e ，m i s s i n gv a l u e s ，b u ta l s oi n c r e a s et h ec l a s s i f y i n ga c c u r a c ya f t e rs e l e c t i n gf e a t u r e sf r o m t h eo r i g i n a ld a t as e t ( 2 ) t h er e s e a r c ha p p l i e st h er e p r e s e n t a t i v el o c a l l yl i n e a re m b e d d i n g i nm a n i f o l d l e a r n i n g ，r e l i e f ff e a t u r ee v a l u a t i o n ，t h ea c e n e d a t as e ti nu c i ，t h ei i b s v mc l a s s i f i e ra n dt h e w e k ad a t am i n i n gt o o lt ot h ee x p e r i m e n ti nf o u rc a s e s ：f i r s t ，w i t h o u ta n yf e a t u r es e l e c t i o n m e t h o d ；s e c o n d ，w i t ho n l yr e l i e f ff e a t u r ee v a l u a t i o n ；t h i r d ，w i t ho n l yl o c a l l y l i n e a r e m b e d d i n ga l g o r i t h m ；w i t hb o t hr e l i e f ff e a t u r ee v a l u a t i o na n dl o c a l l yl i n e a re m b e d d i n g a l g o r i t h m b ya n a l y z i n ga n dc o m p a r i n g as e r i e so fe x p e r i m e n t a lr e s u l t s ，t h ei m p r o v e d a l g o r i t h mi sh i g h e r t h a nr e l i e f ff e a t u r ee v a l u a t i o na n dl o c a l l yl i n e a re m b e d d i n g r e s p e c t i v e l yi nt h ec l a s s i f y i n ga c c u r a c y ( 3 ) d e s i g na n di m p l e m e n tar e l i e f f ms y s t e m g i v e na d a t as e t ，t h es y s t e mw i l lf i r s t l y e v a l u a t et h eq u a l i t yo ff e a t u r e sw i t hr e l i e f f ；a n dt h e ni tw i l l l e a r n t h em a n i f o l da f t e r s e l e c t i n gf e a t u r e sa c c o r d i n gt ot h eq u a l i t yo ft h e m ；f i n a l l yi tw i l lu s et h el i b s v mc l a s s i f i e r w i t h10 f o l dc r o s sv a l i d a t i o n t h er e a l i z a t i o no fs y s t e mi sc o n d u c t i v et ot h ea n a l y s i sa n d p r o c e s s i n ga f t e rf e a t u r es e l e c t i o nw i t hr e l i e f f m i i i 广东工业大学硕士学位论文 k e y w o r d s ：f e a t u r es e l e c t i o n ，d i m e n s i o n a lr e d u c t i o n ，r e l i e f f ，m a n i f o l dl e a r n i n g i v 目录 目录 摘要i 目录。v 第一章绪论1 1 1 研究目的和现状1 1 1 1特征选择1 1 1 2数据降维1 1 1 3流形学习2 1 2本文的工作2 1 3论文的组织结构3 第二章特征选择的理论基础5 2 1统一框架5 2 2子集生成7 2 2 1搜索方向7 2 2 2 搜索策略8 2 3评价标准1 0 2 3 1距离度量1 0 2 3 2信息量度量1 l 2 3 3依赖性度量1 l 2 3 4一致性度量1 1 2 3 5分类错误率度量1 2 2 4分类方法1 3 2 4 1f i l t e r 模型l3 2 4 2 w r a p p e r 模型1 4 2 5本章小节15 第三章- - 种r e l i e f f 特征估计方法在流形学习中的应用17 3 1特征估计1 7 3 1 1i 沁l i e f 1 7 v 广东工业大学硕士学位论丈 3 1 2r e l i e f f 18 3 2流形学习。1 9 3 2 1流形概念1 9 3 2 2流形学习1 9 3 3经典线性降维方法。1 9 3 3 1主成分分析( p c a ) 1 9 3 3 2多维尺度变换( m d s ) 2 0 3 4 无监督流形学习2 1 3 4 1 等距映射( i s o m a p ) 2 2 3 4 2局部线性嵌入( l l e ) 2 3 3 4 3拉普拉斯特征映射( l e ) 2 5 3 4 4半正定嵌入( s d e ) 2 7 3 4 5基于h e s s i a n 矩阵的l l e ( h l l e ) 2 8 3 4 6局部切空间排列( l t s a ) 2 9 3 5 有监督流形学习3 1 3 5 1 有监督等距映射( s i s o m a p ) 3 1 3 5 2 有监督局部线性嵌入( s l l e ) 3 2 3 6降维方法总结3 2 3 7改进算法r e l i e f f m 3 4 3 8实验部分3 5 3 9 1数据来源。j 3 5 3 9 2实验步骤3 6 3 9 3结果及分析3 6 3 9r e l i e f f m 系统3 9 3 1 0 本章小节4 1 总结与展望4 3 参考文献4 5 攻读学位期间发表的相关学术论文4 9 独创性声明5 l 致谢5 3 v i c o n t e n t s c o n t e n t s a b s t r a c t i i i c o n t e n t s v i i c h a p t e r1 i n t r o d u c t i o n 1 1 1 p u r p o s ea n dc u r r e n ts i t u a t i o n 1 1 1 。1f e a t u r es e l e c t i o n 1 1 1 2d i m e n s i o n a lr e d u c t i o n 1 1 1 3m a n i f o l dl e a r n i n g 2 1 2t h em a i nr e s e a r c hw o r k 2 1 3t h ep a p e rs t r u c t u r e 3 c h a p t e r2 b a s i ct h e o r yo ff e a t u r es e l e c t i o n 5 2 1b a s i cf r a m e w o r k 。5 2 2s u b s e ts e l e c t i o n 7 2 2 1 r e s e a r c h i n go r i e n t a t i o n 7 2 2 2 r e s e a r c h i n gs t r a t e g y 8 2 3c r i t e r i ao f m e a s u r e m e n t 1 0 2 3 1d i s t a n c em e a s u r e 1 0 2 3 2 i n f o r m a t i o nm e a s u r e 11 2 3 3 d e p e n d a n c ym e a s u r e 11 2 3 4 c o n s i s t e n c ym e a s u r e 11 2 3 5c l a s s i f i c a t i o ne r r o rr a t em e a s u r e 1 2 2 4 c a t e g o r y 1 3 2 4 1 f i l t e rm o d e l 13 2 4 2 w r a p p e rm o d e l 。1 4 2 5 s u m m a r y 1 5 c h a p t e r3a p p l i c a t i o no f r e l i e f ff e a t u r ee v a l u a t i o ni nm a n i f o l dl e a r n i n g 17 3 1 f e a t u r ee v a l u a t i o n 17 3 1 1 r e l i e f 17 3 1 2 r e l i e f f 18 3 2m a n i f o l dl e a r n i n g 1 9 v i i ：兰耋竺耋型兰丝鳖刍一 3 2 1 c o n c e p t i o n 1 9 3 2 2m 撕f o l dl e a r n i n g 1 9 3 3c l a s s i cl i n e a rd i m e n s i o n a lr e d u c t i o n 1 9 3 3 1 p r i n c i p a lc o m p o n e n ta n a l y s i s 1 9 3 3 2m u l t i d i m e n i o n s a ls c a l e 2 0 3 4 u n s u p e r v i s e dm a n i f o l dl e a r n i n g 2 1 3 4 1 i s o m e t r i cm a p p i n g 2 2 3 4 2 l o c a l l yl i n e a re m b e d d i n g “2 3 3 4 3 l a p l a c i a ne i g e n m a p 2 5 3 4 4s e m i d e f i n i t ee m b e d d i n g 2 7 3 4 5h e s s i a nl l e 2 8 3 4 6 l o c a lt a n g e n ts p a c ea l i g n m e n t 2 9 3 5 s u p e r v i s e dm a n i f o l dl e a r n i n g 3 1 3 5 1 s u p e r v i s e di s o m a p ”3 1 3 5 2 s u p e r v i s e dl l e 3 2 3 6 s l l m m a r yo f d i m e n s i o n a lr e d u c t i o n ”3 2 3 7t 1 1 ei m p r o v e da l g o r i t h mr e l i e f f m “：3 4 3 8 e x p e r i m e n t a lp r o c e d u r e 3 5 3 9 1 d a t as o u r c e s 3 5 3 9 2 e x p e r i m e n t a lp r o c e d u r e 3 6 3 9 3r e s u i ta n da n a l y s i s 3 6 3 9t h er e l i e f f ms y s t e m 3 9 3 1 0s u m m a r y 4 1 c o n c l u s i o na n dp e r s p e c t i v e 4 3 r e f e r e n c e s 4 5 p u b l i c a t i o nd u r i n gm s c e d u c a t i o n 4 9 s t a t e m e n to fo r i g i n a l i t y 5 1 a c k n o w l e g m e n t 5 3 v i i i 第一章绪论 1 1 研究目的和现状 第一章绪论弟一早珀v 匕 计算机与互联网的发展使得数据呈指数级增长、高维度、非线性结构，如全球气 候模式、航天遥感数据、恒星光谱、消费市场数据、人的基因分布以及图像数据。但 是，人类所能够获取的信息量却不是以同等速度增长，从大量的数据中发现的知识有 限而且有时并不能满足要求。在这样一个时代背景之下，人工智能、机器学习、数据 挖掘、模式识别等学科的发展为解决数据降维和知识发现提供了有利的方法。其中， 数据降维、特征选择和流形学习就是这样一些有效的工具。 1 1 1 特征选择 特征选择在数据挖掘中处在数据预处理阶段，成为继数据清理( 填充缺失值、光 滑噪声并识别离群点和纠正不一致性) n 1 之后知识发现的以一重要步骤；而在模式识别 中，特征选择是在设计分类器和分类决策前必需进行的一个环节；在图像处理中，特 征的概念就变为比较具体，比如人脸、眼睛、指纹等，与前二者特征选择的结果形式，一 上也许会存在着差异。特征选择的好处不仅可以降低计算复杂度，提高分类准确度， 而且有助于寻找更精简易理解的算法模型。因此，特征选择引起越来越多学者的兴趣。 1 1 2 数据降维 数据降维的概念最初是为了解决“维度灾难”问题而提出的。尽管当时已经存在 着一些降维方法，比如主成分分析( p r i n c i p a lc o m p o n e n ta n a l y s i s ，简称p c a ) 2 1 、 线性判别分析( l i n e a rd i s c r i m i n a t e da n a l y s i s ) 、多维尺度变换( m u l t i d i m e n s i o n a l s c a l e ) 口1 等，但这些方法只适用于有线性关系的数据空间，面对高维数据空间中的大 多数稀疏点是非线性的情形也不能等到满意的效果。于是，非线性的数据降维技术， 如核主成分分析( k e r n e lp r i n c i p a lc o m p o n e n ta n a l y s i s ，简称k p c a ) 、核线性判别 分析( k e r n e ll i n e a rd i s c r i m i n a n ta n a l y s i s ，简称k e r n e l l d a ) 、诸多流形学习方 法等随之出现。非线性降维方法的研究仍然是目前模式识别、机器学习、数据挖掘中 广东工业大学硕士学位论文 的热点，是因为非线性降维技术更适用于现实世界中的数据，更能解决现实中的问题。 1 1 3 流形学习 2 0 0 0 年s e u n g 等人在( s c i e n c e ) 杂志上提出感知以流形方式存在，视觉记忆也是 以稳态的流形( 也称为连续吸引子) 存储h 1 。这些学者认为，人脑神经元对输入信号 能够做非线性处理是因为神经元是由输入信号的内在低维流形结构所控制。这为流形 学习提供了理论基础。同年，t e n e n b a u m 等人提出等距映射( i s o m e t r i cm a p p i n g ，简 称i s o m a p ) 嘲“蜘以及s a u l 和r o w e l s 提出局部线性嵌入( l o c a l l yl i n e a re m b e d d i n g ，简 称l l e ) p 1 两种流形学习方法。随后，流形学习这类非线性降维方法的研究得到广泛的 关注和发展，比如拉普拉斯映射( l a p l a c i a ne i g e n m a p ，简称l e ) 、半正定嵌入 ( s e m i - d e f i n i t ee m b e d d i n g ，简称s d e ) 、基于h e s s i a n 矩阵的局部线性嵌入( h e s s i a n b a s e dl l e ，简称h l l e ) 、局部切空间排列( l o c a lt a n g e n t s p a c ea 1 i g n m e n t ，简称 l t s a ) 等方法羽巾1 h 1 0 1 的提出。流形学习的理论基础研究涉及微分几何、图论、矩 阵分析、概率、随机过程等数学分支，作为一种非线性降维和数据可视化的方法，已 经在人脸、手写数字图像处理取得了较好的效果。 1 2 本文的工作 流形学习近年来得到了越来越多机器学习爱好者的关注和实际中的应用。因为流 形学习能够在一个高维度的数据空间中寻找到低维的流形嵌入，而且这种流形很好地 解释了数据的结构特征，在分类和可视化方面有着很好的效果。r e l i e f f 特征估计方法 在算法上简单易懂且运行效率高、实时效果好，被认为是一种成功的特征选择方法。 本文的工作是在各种流形学习方法的基础之上引入r e l i e f f 特征估计，把两种降维方 法融合在一起，通过实验证明了该种改进方法的有效性。同时，论文的相关工作还有 设计了一个数据降维系统，把现有的各种数据降维技术或特征选择方法集成到一起， 并增加部分功能使之与广泛应用的w e k a 工具交互。 本文的创新之处在于分析了各种流行学习方法和r e l i e f f 特征估计方法的缺点以 及融合了两种学习方法的优点之后，提出一种改进的学习方法并实现了一个可以应用 的系统。 2 第一章绪论 1 3 论文的组织结构 论文主要是研究对特征选择中过滤式和包装式两种方法结合的有效性，围绕这一 目的，组织结构如下： 第一章介绍论文的研究目的和现状，特征选择在机器学习、数据挖掘、模式识别 等方面的研究状况以及流形学习在国内外的研究进展。 第二章主要介绍特征选择的统一框架、子集生成、评价标准和分类方法。 第三章提出一种r e l i e f f 特征估计在无监督和有监督流形学习中的应用方法，简 要介绍了流形学习的方法，包括流形的概念、流形学习及其各种方法，并分析了这些 方法的优缺点，并采用u c i 中的标准数据集进行实验及分析，得出实验结论。 最后，论文对r e l i e f f 特征估计在无监督和有监督流形学习中应用的工作进行总 结，并对将来需要继续的工作进行展望。 广东工业大学硕士学位论文 4 第二章特征选择的理论基础 第二章特征选择的理论基础 特征选择在机器学习、数据挖掘、模式识别等领域中一直都是研究的热点问题之 一。原因在于，特征选择结果的好坏决定于后续处理方法的可靠性、有效性和强健性。 本章将从机器学习中特征选择的统一框架开始讨论，然后大体上介绍特征选择的策略 以及一些评价标准，最后涉及特征选择方法中的两种模型- f i l t e r ( 过滤式) 和w r a p p e r ( 封装式) 。 2 1 统一框架 特征选择是根据特征选择度量从样本集的初始特征集中选出相关的特征起到压 缩数据处理规模的作用。这个过程中冗余的和不相关的特征被删除。特征选择是学习 算法的前处理，良好的特征集可以提高学习的准确性，减少学习的时间以及简化学习 结果，相反，有些算法由于不相关的、冗余的、干扰性的特征而使得学习结果很差而 失败。特征选择可以看作是一个组合优化和搜索过程，一个特征选择算法的搜索空间 如图所示，设f = z ，五，石，工) 。但是，得到一个最优的特征子集是一个n p 困难问 题。g u 提出了s a t 问题的局部搜索求解方法和全局优化算法，以及多维空间搜索算 法。 d 1 的一组最优特征以达到降维的目的。在数学中解决组合优化问题的一个最直 接的方法就是搜索，对于特征选择来说，d 个特征可以有2 d 一1 个不同的特征组合( 特 征子集) ，搜索的目的就是在这些候选的特征子集中选取最优的那一个。至于如何在 所有的候选子集中搜索的问题就是搜索策略的问题，一种最简单的策略就是穷举法， 即考虑所有可能的候选，选择其中最好的一个子集作为最后的输出。这种穷尽搜索的 方法简单但是在实际中很不实用，因为它的运算量和存储量是随着特征维数的增加而 指数递增的，实际中经常会碰到维数超过几十甚至上百的情况，这种时候穷尽搜索的 效率是非常低的。因此穷尽搜索的办法在实际中并不经常用，通常可以采用避免穷尽 搜索的完全搜索，或者牺牲全局最优特性的局部最优搜索，以降低搜索的计算复杂 度。 d a s h 和l i u ( 1 9 9 7 ) 提出了一个特征选择的基本框架n 羽，认为一个基本的特征选择 方法由以下四个步骤组成： 图2 - 2 特征选择的基本步骤 f i g u r e2 - 2g e n e r a lp r o c e d u r e so ff e a t u r es e l e c t i o n 由以上四个步骤组成的一个完整的特征选择是一个循环搜索的过程： 步骤l ：“子集生成 的方式决定了搜索的策略，包括搜索的起始点、方向、产生 下一个子集的策略。搜索的起始点可以是不含任何特征的空集，包括所有特征的全 集，也可以是任意的一个子集。搜索的方向可以是前向( 特征依次增多) 、后向( 特征 依次减少) 或者双向( 有时递增，有时递减) 。从当前子集产生下一个子集的策略可以 有依次增加或减少一个特征、随机产生等方式。 步骤2 ：“子集评价 模块的作用是根据一定的评价标准对“子集生成”模块产生 的子集进行优劣评价，这一过程称为评价函数的计算。每进行一次特征子集的优劣评 价，将新的评价值和之前保存的最好的评价值进行比较，如果发现新的子集优于之前 最好的子集，那么更新当前的最优子集。这里面非常关键的一点是评价标准的确定， 对于整个特征选择方法的有效性具有决定性的意义。 6 第二章特征选择的理论基础 步骤3 ：对子集评价完之后要进行“停止条件 的判断，如果没有停止条件，搜 过程将无尽的一直进行下去。通常的停止条件有： ( 1 ) 达到事先指定的特征数目； ( 2 )循环次数超过了预先给定的数值； ( 3 )增加或减少特征不能使子集的评价函数值有所提高； ( 4 ) 找到了评价函数的最优解： ( 5 ) 评价函数值超出了预先设定的阈值。 步骤4 ：最后要对选择出来的特征子集进行验证。验证通常用选定的特征子集对人 工的或实际的数据集进行训练和预测，将训练和预测的结果和没有进行特征选择而在 原始数据集上的结果进行比较，这种比较包括训练和预测所花费的时间，模型的复杂 程度，分类器的正确率。 以上这四个步骤就构成了本文研究特征选择的一个基本框架。在四个步骤中， 对特征选择整体性能影响最大的是搜索策略和评价标准的确立，停止条件基本上是根 据问题来决定或者由搜索策略和评价标准来确定的。以下，在这两个方面进行详细地 分析。 2 2 子集生成 特征子集的产生实际上是一个搜索过程，而搜索有其起始点、方向和最重要的 环节：搜索策略。 2 2 1 搜索方向 特征选择搜索方向是指特征选择算法采用何种方向进行特征选择。首先必须决 定搜索的起始点。理论上任何一个特征子集都可以作为搜索的初始子集，但通常这是 由搜索方向来决定的。常见的几种产生特征子集的方向有： 1 前向生成：以一个不含任何特征的空集作为初始子集，然后在每一次循环中 依次在剩下的特征中选择一个特征，这个特征的选择以使评价函数值最大为准则，直 到满足停止条件为止。 2 后向生成：和前向生成相反，以包含全部特征的子集开始，依次去掉一个特 征，选择去掉的标准同样是使评价函数最大，直到整个搜索过程停止。 3 双向搜索：同时从两个方向开始搜索，一般搜索到特征子集空间的中部时， 7 广东工业大学硕士学位论文 需要评价的子集数将会急剧增加。当使用单向搜索时，如果搜索要通过子集空间的中 部就会消耗掉大量的搜索时间，所以双向搜索是比较常用的搜索方法。 4 随机生成：这里初始子集是随机产生的，下一步的特征子集也是随机产生 的，随机的方法有时候可以避免陷入局部最优点。这样的一个特征选择算法多次运行 的结果可能会不一样。 t 2 2 2 搜索策略 决定了搜索的起始点和方向后，下一步很重要的一个问题就是搜索策略。特征 选择搜索策略是指特征选择算法采用何种方法从特征搜索空间中找到符合特征评价判 据的特征子集。由于搜索空间的大小不同，所使用的搜索策略也不同。因此，搜索的 结果可能是最优的，也可能是次优，可能是一个，也可能是一组特征。基于对这个问 题的考虑，把搜索策略可以大致分为三种： 1 完全搜索：可以保证获得对于给定的评价准则是最优的特征子集，例如穷尽 搜索就是一种完全搜索。但是，并不是说所有的完全搜索都是穷尽搜索，某些启发式 评价函数可以用来减少搜索空间并能保证获得最优特征子集。相应的算法有分支限界 法( b r a n c hb o u n d ) n 3 1 h 3 和b s ( b e a ms e a r c h ) 算法。 2 启发搜索：是在搜索的最优性和计算量之间做了一个折中的搜索策略。启发 式特征选取的算法很多，例如：顺序前向搜索( s f s ) 、顺序后向搜索( s b s ) ，以及 广义的顺序前向搜索( g s f s ) 和广义的顺序后向搜索( g s b s ) 等。这些算法复杂度低， 搜索过程可以很快的就收敛。该类算法的缺点是，特征一旦被加入或删除，以后便不 会改变，因此容易陷入局部极值，为克服此缺点，出现了增，减，法，即搜索方向不 再是单向加或者减，可以根据评估函数灵活的浮动，其问题在于，和，的大小难以确 定。p u d i l 等提出了顺序浮动前向搜索( s f f s ) 和顺序浮动后向搜索算法( s f b s ) n 5 1 ， 算法变固定的增，减，法为浮动的，减少了不必要的回溯并在需要时增加回溯的深 度。 3 随机搜索：和前面的几种策略不同，随机搜索的下一个特征子集的产生是随 机的，和当前的特征子集无关。这种方法可以设定一个循环次数的上限，一达到这个 上限就停止搜索，输出目前为止所找到的最优特征子集。随机搜索算法的可控性比较 好，如果资源充足的话，可以增加循环次数的上限值，那么所遍历的搜索空间必然更 加完备，找到的结果也会更接近全局最优解。在文献 1 6 】中的l v f 算法就是采用随机搜 8 g _ - 章特征选择的理论基础 索的算法，用遗传算法和模拟退火算法来做特征选择的方法使用的搜索策略也属于随 机搜索。 以上介绍了几种主要的搜索策略，表2 - 1 为各种特征选择搜索算法的总结。在决 定搜索策略的时候通常需要在计算复杂性和全局最优性之间根据实际问题来寻找一个 最佳平衡。直观上也非常容易理解，花更多的时间在更大的搜索空间中搜索自然能找 到比较正确的解。穷尽搜索可以保证全局最优，但是搜索效率却非常低以至于在实际 场合中很少有应用。b r a n c hb o u n d 算法也可以找到全局最优解，但是尽管它比穷尽搜 索可以节省很