（应用数学专业论文）基于改进svm和核foleysammon变换的维归约及其应用.pdf

摘要 基于改进s v m 和核f o l e y - s a m m o n 变换的维归约及 其应用 作者姓名： 堕塑巡 学位专业：应用数学 导师姓名：李磊、姚正安教授 摘要 一个数据集可能包含几十甚至几百上千个特征，对于特定的学习任务来说，并不 是每个特征都是必要的：有些特征与学习任务是相关的( r n e v a n t ) ；有些特征与学 习任务无关( i r r e l e v a n t ) ；有些特征是冗余的( r e d u n d a n t ) ；特征与学习任务之间 也不一定线性相关。因此，机器学习的一个中心问题是针对特定的学习任务定义出有 代表性的特征子集。特征子集的确定( 维归约一d i m e n s i o n a f i t yr e d u c t i o n ) 有两种途 径：特征选择( f e a t u r es e l c t i o n ) 方法仅仅保留有用的特征，而丢弃其它的特征；特 征提取( f e a t u r ee x t r a c t i o n ) 方法根据原始的特征构造出新的特征 k t 0 3 j 。本文主要 利用线性支持向量机( s v m q u p p o r tv e c t o rm a c h i n e ) 和统计学习理论中的核方法来 对分类任务( 模式识别) 进行维归约，本文的主要贡献如下： 对于特征选择，本文首先提出了基于改进s v m ( m s v m - m o d i f i e ds v m ) 的 特征选择算法( m f g m s v mb a s e df e a t u r es e i c t i o n ) ，m f s 算法的思想是首先根 据m s v m 的结果( 权重向量) 来确定单个特征的分类能力，然后按照一定的方式( 前 向选择或后向消除) 确定特征子集。m f s 算法的主要缺点是不能很好地处理冗余特 征，因此本文提出基于相关分析( c o r r e l a t i o n ) 和m s v m 的特征选择算法( c m f s c o r r e l a t i o na n dm e v mb a s e df e a t u r es e l c t i o n ) 。c m f s 在m f s 的基础上增加了对冗 余特征的处理在确定特征子集的时候，一个特征是否加入特征子集需要综合考虑 该特征的分类能力以及它与特征子集中其它特征的相关程度。实验表明，与其它的特 征选择算法相比，本文提出的特征选择算法具有更好的性能：能够在比较短的时问内 提取出分类能力比较好的特征。 对于特征提取，本文首先介绍了针对数据描述任务的特征提取方法( p c a p 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 lp c a ) 。对于分类任 务，本文分别介绍了基于s v m 的特征提取和基于f i s h e r 判别( f d f i s h e rd i s c r i m i n a n t ) 的f o l e y s a m m o n 变换( f s 弘f 0 l e y - s a m m o nt r a n s f o r m ) 算法以及核f i s h e r 拍j 第i 页，共9 7 页 别( k f d k e r n e lf d ) 算法。在分析了以上这些特征提取方法的不足之后，结 合核方法和f s t 思想，本文提出了一种新的特征提取算法：核f o l e y - s a m m o n 变换 ( k f s t k e r n e lf o l e y - s a m m o nt r a n s f o r m ) 算法。k f s t 算法在保持f s t 算法的优点 的同时可以提供非常丰富的非线性判定函数( f s t 只能提供线性判定函数) 。此 外，本文对k f s t 算法进行了扩展，提出了k f s t 的两种改进算法：核统计无关f o l e y s a m m o n 变换( k u f s t - k e r n e lu n c o r r e l a t e df o l e y - s a m m o nt r a n s f o r m ：) 算法和核广 义f o l e y s a m m o n 变换( k g f s t - k e r n e lg e n e r a l i z e df o l e y - s a m m o nt r a n s f o r m ) 算法。 其中k f s t 算法可以确保被提取的特征之间是正交的( o r t h o g o n a l ) ；k u f s t 算 法可以确保被提取的特征之间是统计无关的( 共轭正交- c o n j u g a t eo r t h o g o - n a l ) ；k g f s t 算法在保持特征之闻的正交性的同时可以保证被提取的特征集的全 局分类能力。 本文对k f s t 、k u f s t 以及k g f s t 算法思想进行了理论分析，证明了它 们可以转换成一系列相应的广义特征求解问题。在这个基础上，本文提 出了k f s t 、k u f s t 汞k g f s t 的求解办法。本文也讨论了r a y l e i g h 商阎题，发 现k f s t ( f s t ) ，k p c a ( p c a ) 以及其它的一些学习算法都可以统一到r a y l e i g h 商 的框架中来。另外，为了使k f s t 算法可以适用于大规模数据集的问题，本文提出了 基于聚类加权的k f s t 算法( c w k f s t - k f s tw i t hc l u s t e r i n g - w e i g h t e d ) ，该算法 利用聚类思想来缩小问题的规模，从而达到提高求解速度的目的。 大量的实验证明了本文提出的k f s t 及其改进算法可以取得非常好的结果。本文 第五章首先对f s t 和k f s t 、u f s t 和k u s t 以及g f s t 和k g f s t 分别进行了对比，发 现基于核的算法( k f s t 及其改进算法) 比线性算法( f s t 等) 效果好很多- ；然后 对k p c a 和k f s t 进行了对比，发现对于分类任务，k f s t 比k p c a 具有更好的性能； 接着对k f d 、k f s t 、k u f s t ，k g f s t 进行了比较，详细讨论了这几种算法的优点 和不足之处；最后，实验也证明了本文提出的c w k f s t 算法在大规模数据集上具有很 高的效率2 。 最后本文分析了研究中的不足之处，指出了存在的问题以及进一步研究的方向。 关键词：特征提取，核方法，f i s h e r 判别r a y l e i g h 商，特征空间，f o l e y s a m m o n 变换，基于核的f o l e y - s a m m o n 变换 1 数据集在基于核的算法提取的特征上具有更好的几何可分性以及更好的分类准确度 2 与k f s t 相比，c w k f s t 具有相近的分类准确度、相似的空伺分布以及根短的执行时间 第i i 页共9 7 页 m o d i f i e ds v ma n dk e r n e lf o l e y - s a m m o nt r a n s f o f i l l b a s e dd i m e n s i o n a l i t yr e d u c t i o na n da p p l i c a t i o n s n a m e ： m a j o r ： ，c 、h e ，n ，z h e n z 。h o 。u a p p l i e dm a t h e m a t i c s s u p e r v i s o r ： 生! 垦! ! ! 坐! ! 墅圣! ! ! 壁! 望 a b s t r a c t t od e s c r i b eat a s k ，o n em a y b en e e d sh u n d r e d so rt h o u s a n d sf e a t u r e s f o rap a t t i e u l a rt a s k tn o ta l lo ft h e s ef e a t u r e sa r cn e e d e d ：s o m ef e a t u x e sb x et e l e v a n tt oc l a s s ，s o m e f e a t u r e sa r ei r r e l e v a n tt oc l a s sa n ds o m ef e a t u r e sa r er e d u n d a n t 。ac e n t r a lp r o b l e mi n m a c h i n e l e a r n i n g i s i d e n t i f y i n g ar e p r e s e n t a t i v e s e t o f f e a t u r e s f o r a p a r t i c u l a r t a s k t h e r e a r et w ok i n d so fw a y st oi d e n t i f yar e p r e s e n t a t i v es e to ff e a t u r e s ( d i m e n s i o n a l i t yr e d u e t i o n ) o n ek i n di sc a l l e df e a t u r es e l e c t i o nw h i c hk e e p so n l yu s e f u lf e a t u r e sa n dd i s c a r d s t h eo t h e r s t h eo t h e rl d n di sc a l l e df e a t u r ee x t r a c t i o nw h i c hc o n s t r u c t sn e wf e a t u r e s f r o mt h eo r i g i n a lf e a t u r e s i nt h i sp a p e rt h el i n e a rs v m ( s u p p o r tv e c t o rm a c h i n e ) a n d k f s t ( k e r n e lf o l e y - s a m m o nt r a n s f o r m ) a r eu s e dt od od i m e n s i o n a l i t yr e d u c t i o nf o r c l a s s i f i c a t i o nt a s k s t h em a i nc o n t r i b u t i o n so ft h i sw o r kc a l lb es u m m a x i z e da sf o l l o w s f o rf e a t u r es e l e c t i o n if i r s tt h em s v m ( m o d i f i e ds v m ) b a s e df e a t u r es e l e c t i o i j ( m f s ) a l g o r i t h mi sp r o p e s e d t h ec l a s ss e p a r a b i h t yo fs i n g i ef e a t u r ei sr a n k e db yt h e r e s u l t so fm s v ma n dt h ef e a t u r es u b s e ti sf o r n l e da c c o r d i n gt os e q u e n t i a lf o r w a r ds e - l e c t i o no rs e q u e n t i a lb a c k w a r de l i m i n a t i o n t h em a i ud e f i c i e n c yo fm f si st h a tm f s c a n n o td e a lw i t hr e d u n d a n tf e a t u r e sw e l l t h e nc m f s ( c o r r e l a t i o na n dm s v mb a s e d f e a t u r es e l e c t i o n ) a l g o r i t h mi sp r o p o s e d b a s e do nt h em f s ，g m f sc a nd e a lw i t hr e - d u n d a n tf e a t u r e sw e l l ：t h a taf e a t u r ec a l lb ea d d e dt ot h ef e a t u r es e to rn o ti sd e c i d e d b yt h ec l a s ss e p a r a b i l i t yo ft h ef e a t u r ea n di t sc o r r e l a t i o nw i t ht h ea l r e a d yc h o s e nf e a - t u r e sl nt h ef e a t t i r es u b s e t e x p e r i u l e n t so na r t i f i c i a la n dn a t t i r a ld a t a s e t ss h o w e dt h a t c o m p a r e dw i t ho t h e rf e a t u r es e l e c t i o na l g o r i t h m s m r sa n dc m f st y p i c a l l ye l i m i n a t e w e l lm u c hm o r ef e a t u r e sw i t hl e s st i m ea n dh i g h e ra c c u r a c y f o rf e a t u r ee x t r a c t i o n ，f i r s tt h ep c aa n dk p c a ( k e r n e lp c a la r ei n t r o d u e d t h e ns v m ，f s t ( f o l e y - s a n m m nt r a n s f o r m ) a n dk f d ( k e r n e lf i s h e rd i s c r i m i n a n t ) a r e p r e s e n t e d a i t e ra n a l y z i n gt h es h o r t a g e so ff e a t u r ee x t r a c t i o na l g o r i t h m sb a s e do nt h e 第i i i 页，共9 7 页 m e t h o d sa b o v e ，an e wa l g o r i t h mk f s t ( k e r n e lf s t ) i sp r o p o s e di nt h i sp a p e r k e r n e l f u n c t i o n sw i l la l l o wf o rp o w e r f u l ，n o n - l i n e a rd e c i s i o nf u n c t i o n sw h i l es t i l ll e a v i n gu s w i t har e l a t i v e l ys i m p l eo p t i m i z a t i o np r o b l e m ，ag l o b a ls o l u t i o na n das t r a i g h tf o r w a r d i n t e r p r e t a t i o no fw h a to n ei sa c t u a l l yo p t i m i z i n gf o r t w oi m p o r t a n ta n di n t e r e s t i n g v a r i a n t so fk f s t ，r u l m e l yk u f s t ( k e r n e lu n c o r r e l a t e df o l e y - s a m m o nt r a n s f o r m ) a n d k g f s tf k e r n e lg e n e r a l i z e df o l e y - s a m m o nt r a n s f o r m ) ，a r ed e r i v e d f e a t u r e se x t r a c t e d b yk f s ta r eo r t h o g o n a l ，f e a t u r e se x t r a c t e db yk u f s ta s eu n c o r r e l a t e d ( c o n j u g a t e o r t h o g o n a l ) a n df e a t u r e se x t r a c t e db yk g f s t h a v et h eb e s tc l a s ss e p a r a b i l i t yi ng l o b a l s e n s e t h i sp a p e ra l s op r o v e dt h a tk f s ta n di t sv a r i a n t sc a nb ec o n v e r t e dt ot o r t e - s p o n d i n gg e n e r a l i z e de i g e n v a l u ep r o b l e m s f u r t h e r m o r e ，t h i sp a p e rd i s c u s st h ep r o b l e m o fr a y l e i g hq u o t i e t ya u dw ec a ns e et h a tt h ep c a ，k p c a ，f s t ，k f s ta n ds o m eo t h e r m e t h o d sc a nb ed e s c r i b e db yr a y l e i g hq u o t i e t y t oa p p l yk f s to nl a r g es c a l ed a t a s e t ， c w k f s t ( k f s tw i t hc l u s t e r i n g - w e i g h t e d ) i sp r o p o s e d t h ei d e a do fc w k f s ti s r e d u c i n gt h es c a l eo fd a t a s e tu s i n gc l u s t e r i n gf o rs a v i n gt i m e i nal a r g ec o u e c t i o no fe x p e r i m e n t st h i sp a d e rd e m o n s t r a t et h a tk f s ta n di t s v a r i a n t sp r o p o s e dh e r ea r ec a p a b l eo fp r o d u c i n gs t a t eo ft h ea r tr e s u l t s c h a p t e r5f i r s t c o m p a r e dl i n e a ra l g o r i t h m s ( f s t ，u f s t ，g f s t ) w i t ht h e i rk e r n e le x t e n s i o n s ( k f s t ， k u f s t k g f s t la n df o u n dt h a tt h ek e r n e la l g o r i t h m sa r eb e t t e rt h a nl i n e a ra l g o r i t h m s t h e nk p c ai sc o m p a r e dw i t hk f s ta n dw ec a ns e et h a tt h ep e r f o r m a n c eo fk f s ti s b e t t e r t h a to fk p c a k f d k f s t k u f s ta n dk g f s ta r ea l s ob ec o m p a r e da n dt h e i r s a d v a n t a g e sa n dd i f f i c u l t i e sa r ec a r e f u l l yd i s c u s s e d i na d d i t i o n ，t h r o u g he x p e r i m e n t s ，t h i s p a p e ra l s os h o w e dt h a tc w k f s t r a nr u no nl a r g es c a l ed a t a s e tv e r ye f f i c i e n t l y f i n a l l y , t h es h o r t a g e so fo u rr e s e a r c hi sd i s c u s s e da n ds o m ed i r e c t i o n sf o rf u t u r e r e s e a r c ha r es u g g e s t e d k e y w o r d s ：f e a t u r ee x t r a c t i o n ，k e r n e lm e t h o d ，f i s h e rd i s c r i m i n a n t ，r a y l e i g h q u o t i e t y , f e a t u r es p a c e ，f o l e y - s a m m o nt r a n s f o r m ，k e r n e lf o l e y - s a m m o nt r a n s f o r m 第i v 页，共9 7 页 插图目录 插图目录 结构风险最小化归纳原则 分类间隔与v c 维， 核方法的基本思想 二维映射到三维分类例 数据集上的线性s v m 分类和非线性r b f 核s v m 分类 数据点的位置与0 的关系 最终模型中的特征百分比 算法在数据集上的执行时间( 秒) 分类算法在测试集上的性能( 准确度) 主成分分析的例子 核主成分分柝的例子， p c a 提取的第一个特征的分类能力 基于s v m 的特征提取 数据集在不同方向上投影的分类能力 类别可分性例子 两类f i s h e r 判别的例子 经典的x o r 问题( 线性函数无法求解) 样本集t o y 的空问分布：左边是测试样本集，右边是训练样本集 c h m r 数据集中的一个例子 f s t 和k f s t 在数据集i 上的性能比较 f s t 和k f s t 在数据集i i3 上的性能比较 f s t 番i k f s t 在数据集t i t 3 上的性能比较 u f s t f f l i k u f s t 在数据集i i3 上的性能比较 u f s t 和k u f s t 在数据集1 1 1 3 上的性能比较 u f s t 和k u f s t 在数据集3 上的性能比较 g f s t 和k g f s t 在数据集1 i3 上的性能比较 g f s t 和k g f s t 在数据集t t l 3 上的性能比较 g f s t 和k g f s t 在数据集i v 3 上的性能比较一 k p c a 和k f s t 在数据集3 上的性能比较 k p c a 和k f s t 在数据集h 1 3 上的性能比较 k p c a 和k f s t 在数据集i v 3 上的性能比较 k f s t 和c v r k f s t 在数据集1 1 3 上的性能比较 k f s t 和c w k f s t 在数据集i l l 3 上的性能比较 第v i i 页，共9 7 页 9加船m 均幻嬲 甜弛姐 宝够鸺鲫加n似两 h 拢粥叫撕 “姐粥姐 “纰幅似蝣蛳”帖 h弛粥铀硒w鹋锄蛐蛳 表格目录 2 一l 常用的核函数 表格目录 o p t d i g i t s 数据库中各个类在训练集和测试集中所占样本数i i t p e n d i g i t s 数据库中各个类在训练集和测试集中所占样本数目 分类算法在k p c a 和k f s t 所提取特征上的分类准确度 k f d ，k f s t ，k u f s t 和k g f s t 在数据集v 上的分类准确度( p l o y ：3 ) k f s t 和c w k f s t 在数据集i i 上的投影向最比较( r b f ：0 3 ) k f s t 和c w k f s t 在数据集i 上的投影向量比较( r b f ：2 ) k f s t 幂i c w k f s t 在数据集1 1 上的运行速度和分类准确度( r b f ：0 3 ) k f s t 和c w k f s t 在数据集i 上的运行速度和分类准确度( r b f ：2 ) c k f s t 和c w k f s t 在数据集f i l 上的运行速度和分类准确度( r b f ：2 ) 第i x 页，共9 7 页 巧 钳斛n他他船砧似两 1 2 3 4 5 6 7 8 9 5 5 5 5 矗5 5 5 矗 第一章引言 我们生活在一个信息肘代，信息的收集和存储非常容易。不幸的是，随着这些信 息的增加，理解和利用这些信息的能力并没有同步增强。机器学习可以提供对大量数 据进行分析的工具。一个数据集可能包含几十甚至几百上千个特征，对于特定的学习 任务来说，并不是每个特征都是必要的：有些特征与学习任务是相关的( r e l e v a n t ) ； 有些特征与学习任务无关( i r r e l e v a n t ) ；有些特征是冗余的( r e d u n d a a t ) 。因此， 机器学习的一个中心问题是维归约( d i m e n s i o n a l i t yr e d u c t i o n ) 【f b j 0 4 1 针对特 定的学习任务定义出有代表性的特征子集，使学习算法能够集中于数据最有用的部分 ( 特征子集) ，维归约有两种方式：特征选择( f e a t u r es e l c t i o n ) 方法仅仅保留有用 的特征，而丢弃其它的特征；特征提取( f e a t u r ee x t r a c t i o n ) 方法根据原始的特征构 造出新的特征 t o r 0 3 l 。特征选择和特征提取只是方法。而不是目的对于不同的目 的( 学习任务) ，需要不同的特征子集。也就是说，可能需要不同的特征选择和特征 提取算法。本文的主要思想是利用线性s v m 以及统计学习理论中的核方法为分类任务 ( 模式识别) 来进行特征选择和特征提取。 对于特征选择，本文从特征选择的基本思想出发，将特征选择和线性支持向量 机( s v m ) 结合起来，提出了一种基于改进s v m ( m s v m m o d i f i e ds v m ) 的特征 选择算法( m f s - m s v mb a s e df e a t u r es e l c t i o n ) 。m f s 算法能够很好她处理与分类 有关和无关的特征，但却不能很好地处理冗余的特征，因此本文又提出了基于相关 分析( c o r r e l a t i o n ) 和m s v m 的特征选择算法( c m f s c o r r e l a t i o na n dm s v mb a s e d f e a t u r es e l c t i o n ) 。c m f s 在m f s 的基础上增加了对冗余特征的处理在确定特征 子集的时候，一个特征是否加入特征子集需要综合考虑该特征的分类能力以及它与特 征子集中其它特征的相关程度。 对于特征提取，本文在详细讨论f o l e y - s a m m o n 变换思想之后，结合核方 法，提出核f o l e y - s a m m o n 变换( k f s t - k e r n e lf o l e y - s a m m o nt r a n s f o r m ) 算法以 及它的两个改进算法：k u f s t ( k e r n e lu n c o r r e l a t e df o l e y - s a m m o nt r a n s f o r m ) 和k g f s t ( k e r n e lg e n e r a l i z e df o l e y - s a m m o nt r a n s f o r m ) 。其中k f s t 算法可以确 保被提取的特征之间是正交的( o r t h o g o n a l ) ；k u f s t 算法可以确保被提取的特征之 闷是统计无关约( 共轭正交一c o n j u g a t eo r t h o g o n a l ) ；k g 至、s t 算法在保持特征之间 的正交性的同时可以保证被提取的特征的全局分类能力。 另外，本文在讨论每类特征选择和特征提取算法之后都给出了这些算法在不同的 人工数据集和实际数据集上的评估，通过实验证明了本文提出的特征选择和特征提取 第1 页洪9 7 页 第一章引言 算法的有效性。 1 1 研究动机 机器学习就是研究能够根据经验自动提高性能的算法。一个重要的性能是预 测，当一个算法应用到一个任务上时，如果该算法能够改善它对任务的关键特征的 预测能力，那么它被认为是经过学习的。研究表明，没有哪个学习方法在任何情况 下优于其它的学习方法，实际上不同的学习算法经常产生相似的结果 l s g a 。一个影 响学习算法成功与否的重要因素是用来刻画( c h a r a c t e r i z e ) 学习任务的数据的特性 ( n a t u r e ) f h a l l 9 9 1 。如果数据不能显示出机器学习算法所能利用的统计规律性，学习 就会失败。反之，如果对学习算法来说，数据是合适的，那么揭示一个任务的规律性 就会变得非常容易。使得描述任务的数据适合于学习算法的过程被称为维归约。 维归约就是根据一定的目的，从一组给定的特征集合中构造出一个具有代表性的 特征子集，使其保留原特征集的大部分有用的数据信息，从而达到降低特征空间维数 的目的 l w 0 2 。 维归约的目的主要包括：使数据可视化和数据的理解变得简易；减少传输和存 储需求；克服维度灾难( c u r s eo fd i m e n s i o n a l i t y ) ；缩减训练和使用时间来提高预测 性能。并不是所有的维归约算法都能同时达到上述的要求，有些算法可能着重于某 个方面而忽略另一个方面。要构造出一个好的特征子集，一般需要回答以下几个问 题 g e 0 3 ： 是否拥有领域知识? 如果有，构造一个特别的特征子集。 所有的特征是否可比? 如果不可比，对特征进行标准化( n o r m a l i z a t i o n ) 处理。 特征之间是否可能相关? 如果可能，构造联合特征和特征积。 是否需要对单个特征进行评估? 如果需要，那么就要采用特征排序的方法。 是否需要一个预测器? 如果不需要，停止。 是否知道从哪里开始? 如果不知道，那么首先使用线性预测器；如果对一个特征 子集，线性预测器能够达到好的效果，那么对该特征子集可以试一试非线性预测 器。 维归约方法一般分为三类：w a p p e r s 方法、f i l t e r s 方法和e m b e d d e d 方 法 c e 0 3 。w a p p e r s 方法将学习机器作为一个黑箱，根据特征子集的预测能力来 对其进行排序；f i l t e r s 方法将特征选择作为一个预处理步骤，与具体的预测器无 第2 页洪9 7 页 1 2 相关工作 关；e m b 甜d e d 方法在训练的过程中执行特征选择，一般与给定的学习机器相关。 实际上f i l t e r s 和w a p p e r s 两类方法并没有本质的差别，它们的差别仅仅在于前者采用 一些度量指标来评判特征子集的优劣，而后者直接用学习算法的准确率作为评判的 指标。一般来说f i l t e r s 方法的效率比较高，结果与采用的学习算法没有关系，但效 果稍差；w a p p e r s 方法效率比较低，结果依赖于采用的分类算法，效果一般较好。 与f i l t e r s 和w a p p e r s 方法相比，e m b 珧d 方法具有几个方面的优势：它可以利用整个 训练数据而不用将它分为一个训练集和确认集；它可以很快找到解，避免为每个可能 的特征子集再从头开始训练预测器；它具有良好的推广能力，因为它同时考虑了特征 选择和学习机器。本文提出的k f s t 算法就属于e m b e d d e d 方法。 维归约有两种方式：特征选择方法仅仅保留有用的特征，而丢弃其它的特征；特 征提取方法根据原始的特征构造出新的特征 t o z 0 3 。从上面的分析可以看出维归约在 机器学习中占用非常重要的迪位，对维归约算法进行研究有着重要的意义。因此，本 文针对维归约的两种方式分别提出了基于改进s v m 的特征选择算法( m f s ) 和基于 核f o l e y - s a m m o n 变换的特征提取算法( k f s t ) 。 1 2 相关工作 到目前为止，已经有很多经典特征选择算法 l w 0 2 ，k r 9 2 ，n f 9 7 ，l s 9 6 ，j k p 9 4 ， c h e n 0 3 被提出，m d a s h 和h l i u d l 9 对这些算法进行了归类，比较了各种算法的 优缺点。r e l i e f 算法 k r 9 2 是- - 种重要的特征选择算法，它利用统计方法来进行特征 选择，它是由基于实例的学习算法发展而来的一种基于特征权重的算法。r e l i e 蹿法 的一个主要缺点是它不能处理冗余特征，因此在有冗余特征存在的情况下，它不能产 生最优的特征子集。g a i n 算法利用信息增益来判定特征的重要程度，使用信息增益最 大的一些特征来构成特征子集，从而达到特征选择的目的。g a i n 算法所用的信息增益 度量并不是一种很好的度量方法，因为它会使得属性值多的特征的信息增益相对较 大，虽然该特征并不一定是最好的。b & b ( b r a n c h & b o u n d ) i n f 9 7 ，c h e n 0 3 算法是 一种全局最优特征选择算法，它的主要缺点是运行时间很长。 文 b m 9 8 ，j k m c 0 3 提出了利用s v m 进行特征选择的思想。文 j k m c 0 3 描述的 算法首先构建一系列线性s v m s 模型，然后在这些模型产生t p o 权重变量中选择一个 子集来产生最终的非线性模型。这些基于s v m 的特征选择算法都是利用1 一范数形式 的s v m ( “一s v m ) 。而在实际中，有证据表明2 一范数形式的s v m ( 1 2 - s v m ) 的性能 比f 1 一s v m 的更好 s s 9 8 ，w z h 0 5 l ，因此本文利用2 一范数形式的s v m ( m s v m ) 进行特 征选择。 特征选择是一种很好的维归约方式，但仅仅有特征选择是不够的。特征选择只能 第3 页共9 7 页 从已有的特征集上选择特征，不能产生额丧勺联合特征，要产生新的联合特征需要用到 特征提取算法 o m 0 4 、f b j 0 4 1 。一种最常用的特征提取算法是主成分分析( p c a ) 及 其核版本( k p c a ) f m s s m 9 9 ，s i v i s r 9 8 。利用p c a 和k p c a 提取的特征可以很好地 适用于数据描述任务，但对于分类任务来说，这些特征并不一定具有良好的分类能 力。s v m 也可以作为一种特征提取方法，但s v m 是一种两类分类器。对于多类问题， 需要构造多个s v m s ，而这些s v m s 所提取的特征之问不一定无关，而且可能提取过多 的特征。另外一种特征提取算法是基于鼢h e 洌别的f s t 算法f s a m 7 0 ，d l 8 8 ，f s t 算 法只能使用简单的线性判别函数，它的适用范围非常小。还有一种基于f i s h e r 判别的 特征提取方法k f d ( k e r n e lf i s h e rd i s c r i m i u a n t ) m r w s 9 9 ，m r m o l l ，k f d 能够提 供非常丰富的非线性判别函数( 通过使用不同的核函数) ，但它最初也是针对两类问 题提出来的，当它应用到多类问题时，所提取的特征之间并不一定无关。 本文提出的k f s t 算法不仅够提供非常丰富的非线性判别函数，而且可以保证问 题的一个直观解释，同时k f s t 可以有效提取多类问题的特征，能够保证所提取的特 征之间是正交的。 1 3 本文的主要成果 s v m 的提出主要是针对分类和回归学习任务的i s s 9 s ，b u r 9 8 ，虽然它不是作为一 个特征选择工具提出来的，s v m 却可以间接地进行特征选择。本文在特征选择方面的 成果为： 从特征选择的基本概念出发，结合标准的线性s v m ，本文提出了基于改 进s v m ( m s v m ) 的特征选择算法( m f s ) 。 在分析m f s 的不足( 它不能处理冗余特征) 之后，本文又提出了m f s 的一个改 进算法c m f s 一基于相关( c o r r e l a t i o n ) 和m s v m 的特征选择算法。 虽然特征选择对很多问题是有效的，但是对其它一些问题( 图像识别，手写识 别等) 来说，由于特征之间的相互关系，仅仅利用特征选择是不够的特征选择 只能在原始的特征集上选取特征，在这个过程中不能产生新的联合特征，从而无 法更好地适应问题。要产生新的联合特征需要用到特征提取算法。一种重要的特征 提取方法是f i s h e r 判别( f d - f i s h e rd i s c r i m i n u n t ) f i s h e r 3 6 ，f d 主要是为鼹类分类问题 设计的。f o l e y 和s a m m o n 提出了f d 的改进方法，该方法被称为f s t ( f o l e y - s a m m o n t r a n f o r m ) f s t 5 1 ，它能够提取多维特征，并且能够确保被提取的特征之问是正交 的。无论是f d 还是f s t 都只能对原始数据进行线性变换( 实质上就是原始空问坐标轴 第4 页洪9 7 页 1 4 本文的组织 的旋转) ，这就使特征提取受到一定的限制( 只能提取线性特征) 。本文在特征提取 方面的成果为： 为了提取非线性特征，本文利用统计学习理论中的核方法，将数据从原始 空间通过非线性映射到特征空间，在特征空间中执行特征提取，并提出 了k f s t ( k e r n e lf s t ) 算法。k f s t 算法能够保证被提取的特征之间是正交 的。 为了确保被提取的特征之间是统计无关的，本文提出了k f s t 的第一种改 进算法：核统计无关f 硅q s a m m o n 变换( k u f s t k e r n e lu n c o r r e l a t e df o l e y s a m m o nt r a n s f o r m ) 算法。 为了确保被提取的特征具有最好的全局分类能力，本文提出了k f s t 的第二种改 进算法：核广义f o l e y s a m m o n 交换( k g f s - k e 豫e lg e n e r a l i z e df o l e y - s a m m o n t r a n s f o r m ) 算法。 对于k f s t 及其改进算法，本文证明了它们可以转换为相应的特征值求解问题， 可以过求解相应的特征值问题来对算法进行求解。 最后，为了解决k