（模式识别与智能系统专业论文）特征选择技术研究.pdf

华中科技大学硕士学位论文 _ - _ - l _ _ _ - _ - _ i i - l l l _ l _ _ _ - - - - - - l _ _ - - l i - l - - - _ _ _ - _ _ _ l l _ _ _ l l - _ - - - - _ - 摘要 特征选择是模式识别以及信息理论中的一个重要组成部分。本文论述的特征选择 悬期望从特征空间中选择一个较小的空自j ，使得类别之f j 具有最好的区分能力。f 经典 的类别可分性度量是基于类内类问距离、基于概率分柿的最小错误概率或散度、以及 基于信息理论的熵概念的。近几年，对特征选择领域的研究有很多新的成果，这其中 诸如互熵( 或者说互信息) 、多重相关部分相关、模糊理论度量、神经网络以及遗传 ) r r 算法在特征选择中的应用等等。j 本文主要针对当前在特征选择领域的三大热门话题， 即基于模糊理论度量的特征选择技术、基于神经网络的特征选择技术、以及基于遗传 算法的特征选择技术进行了详细论述。并对部分新兴理论做了理论阐述和方法介绍， 对大部分算法进行了实验分析。存运用模糊理论度景进行特征选抒的过程巾，作青一 定义了一种具有良好分析能力的基于f 态分布概率的7 型隶属度函数。然后，在运用 神经网络进行特征选择的过程中，运用上述隶属度函数将特征空间几乎一一映射到隶 属度空间，进而对隶属度空阳j 进行划分识别，并在此意义卜提出了隶属度意义一卜的剪 枝从而取代了传统意义i ：的剪枝，构造了一种伞新的普适的运用神经网络进行特征选 择的方法。尤其，当运用隐层结点不断增大的r b f 神经网络时，”该方法具有良好的 稳定性。 关键词：特征选择类别可分性模糊神经网络遗传算法 华中科技大学硕士学位论文 _ _ _ _ _ _ _ _ _ - _ _ - _ - _ _ _ _ r 1 _ _ 一 a b s t r a c t f e a t u r es e l e c t i o ni sa ni m p o r t a n tp a r to fp a t t e r nr e c o g n i t i o na n d i n f o r m a t i o nt h e o r y w h a tt h i sp a p e rf o c u s e si s t oc h o o s et h em o s ts u i t a b l e f e a t u r e st os e p a r a t ed i f f e r e n tc l a s s e s t h ec l a s s i c a lt h e o r i e so fs e p a r a b i l i t y o fd i f f e r e n tc l a s s e sa r eb a s e do ni n t e r c l a s s i n t r a c l a s sd i s t a n c e s m i n i m a l e r r o ru p p e rl i m i to rd i v e r g e n c e ，a n de n t r o p y t h e s ey e a r s ，t h e r ea r em a n yn o v e l s c i e n t i f i cd e v e l o p m e n t si nf e a t u r es e l e c t i o n ，s u c ha s ，c r o s se n t r o p y ( m u t u a l i n f o r m a t i o n ) ，m u l t i p l ec o r r e l a t i o n p a r t i a lc o r r e l a t i o n ，a n dt h ea p p l i c a t i o n o ff u z z y ，n e u r a ln e t w o r k ，a n dg e n e t i ca l g o r it h mi nf e a t u r es e l e c t i o n ，e t c t h i sp a p e rm a j o r si n3h o t t e s tt o p i c s ，w h i c ha r eb a s e do nf u z z y ，n e u r a ln e t w o r k s a n dg e n e t i ca l g o r i t h mr e s p e c t i v e l y s o m ef r e s ht e c h n i q u e sa n dt h e o r i e sare i n t r o d u c e da n da n a l y z e d ，a n da l s os o m ee x p e r i m e n t s i nf u z z yt h e o r y ，t h ea u t h o r i n t r o d u c e saf r e s h 万m e t h o do fd e f i n i n gt h em e m b e r s h i pb a s e do nt h e p r o b a b i l i t yo fn o r m a ld i s t r i b u t i o n a f t e ra l o m o s t 一1 一t o lm a p p i n gt h ef e a t u r e s p a c et ot h em e m b e r s h i ps p a c e ，t h ea u t h o rd e f i n e san e wu n i v e r s a l m e m b e r s h i p b a s e dn o d e p r u n em e t h o djn s t e a do ff e a t u r e b a s e dn o d e p r u n em e t h o d a n du s e sn e u r a ln e t w o r kt oc l a s s i f yd i f f e r e n tc l a s s e s p a r t i c u l a r l y ，w h e n u s i n gr b fn e u r a ln e t w o r k sw h o s en u m b e ro fh i d d e nn o d e sc a nb ei n c r e a s e ds t e p b ys t e p ，t h i sm e t h o ds h o w sag r e a ts t a b i l i t y k e yw o r d s ：f e a t u r es e l e c t i o n c l a s ss e p a r a b i1 t yf u z z y n e u r a ln e t w o r k g e n o t i ca l g o r i t h m i i 华中科技大学硕士学位论文 1绪言 p l 1 1 课题来源 本课题来自高等学校骨干教师资助计划项目“模块化的目标分类识别神经网络研 究”。 1 2 背景及意义 特征选择是模式识别领域的重要环节。特征选择的基本任务是如何从多维特征中 ：找出那些最有效的特征。就有效性而言，特征选择又分为以下两种：1 ) 从特征空间中 选择一个维数更小的特征子空间以最有效的表达某类物体自身；2 ) 从特征空间中选择 一个维数更小的特征子空间用于最有效的区分不同类物体。本文主要论述的是第二种 特征选择。( 以后如无特别指出，均指第二种特征选择。) 在模式识别过程中，人们总是用多维数据一即所谓的特征，来表达目标；而且 一般情况下，总是提取众多特征以全面的表达目标。盲目地使用全部特征进行目标识 别，不仅会带来识别运算量大、识别速度慢等问题，甚至可能由于不合理地使用了不 能有效区分不同类掰目标的特征而导致识别概率下降。因此，为了提高分类识别算法 的可靠性及效率。需要对特征进行合理的选择，以选择出对该分类器而言最能有效区 分不同类别的特征。 1 3 国内外的发展概况及趋势 就选择有效特征进行分类以别m 者，近些年幽内外自彳技活跃的研究动向。 1 9 9 4 年，s t a n f o r d 人学的g e o r g et t j o h n ，r o nk o h a v i ，k a r lp i l e g e r 就已经 全面讨论了特征选择问题。1 9 9 7 年新加坡国立大学的m d a s h 和h l i u 对在此以 前的特征选择方法进行了总结”，文中m d a s h 和h l i u 依据评判准则和特征选择策 略将特征选择分为1 5 种。其中特征选择评判准则分为：距离测度、信息测度、相关 测度、一致性测度和分类错误率测度( t r a p p e r ) ；特征选择搜索策略分为：启发式策 华中科技大学硕士学位论文 略、完全搜索策略和随机搜索策略。在上述五个评判准则中，从概念上讲，相关测度 只是从另外个角度诠释了距离测度、信息测度；而一致性测度指在用户事先选择某 距离测度或信息测度，设置该测度允许的最大误差范围，继而在不超过这个误差范围 ( 不超过这个误差范围即所谓的一致性) 的情况下，选择出维数更小的特征子集。因此， 总的来说，m d a s h 和h l i u 的特征选择定义基于三种评判准则：距离测度、信息测 度、分类错误率测度和三种特征选择搜索策略：启发式策略、完全搜索策略和随机搜 索策略。 同一时期，m i c h i g a n 大学计算机系的a n ilk a i n 和d o u g l a sz o n g k e r 相继发 表了两篇文章”，进行了各种a d ) 的一组最优特征 来。为此有两个问题要解决，一是选择的标准j ，即要选出使某一可分性j 达最大的 特征组来，这一点在以下各章将进行详细论述。另一问题是要找一个较好的算法，以 便在允许的时间内找h 最优的、或接近最优( 这个最优是t 准则意义下的最优) 的那一 华中科技大学硕士学位论文 组特征：基于对这个问题的考虑，我们将特征选择问题从搜索策略上分为以下几种。 2 5 1 完全搜索策略 1 穷举法 从d 个特征中挑选d 个，所有可能的组合数为： 唧。d = 舞 如果把各种可能的特征组合的j 都算出来再加以比较，从中选择最优的特征子集用于 j 分类识别，这种方法就是穷举法。穷举式特征选择的优点是它不仅能提供最优的特征 子集，而且还可全面了解所有特征对各类之间的可分性信息。但是当测量特征的维数 d 很高时，穷举法的计算量太大而无法实现：如d = 1 0 0 ，d = l o 则q 的数量级是1 0 ”， 若d = 2 0 ，d ：l o ，则q = 1 8 4 7 5 6 。这就使得寻找一种可行的算法变得非常必要。 2 分支定界法 1 9 7 8 年，j k i t t l e r 提出了到目前为止唯一能得最优结果的优化搜索方式是“分 支定界”算法。1 ；它是一种自上而下方法，但具有回溯功能，可使所有的特征组合都 被考虑到。由于合理地组织搜索过程，使得有可能避免计算某些特征组合而不影响结 果为最优。这蕾要是利用了可分离性判据的单调性，即：原模式芹如为门维，从中选 出任意册个特征组成一个历维特征，再从该册维特征选出仔意k 个组成一个k 维特征， 其准则函数满足上正山的条件，则可采用分支定界搜索法来减少选择方案的试探 次数”3 。 将所有可能的特征子集组成树结构，7 维的原模式为根。按特征子集的维数逐个 减小，树的子结点维数亦逐级下降，直到规定维数的模式为终止结点时为止。例如要 将五维模式降为二维，要从5 个特征中任选2 个构成子集，共有c ：= 1 0 种组合方式， 将它的降维过程组成如图2 3 所示的树结构，它的根部为f ( 蜀而氲局噩) ，它的 v 9 华中科技大学硕士学位论文 终止结点为1 0 种可能的二维特征的组合。 x l x 2 x 3 x 4 x 5 圈2 - 3分支定界法搜索树的搜索过程示意 在该例中，分支定界法先计算出树中某种二维模式的准则函数作为初值，例如我 。们用图中右侧第一个终止结点作为初选模式特征胖= ( 置噩) ，其初值庐以胖) ，然后 按图中虚线所示的路线开始回溯搜索。根据准则函数，对维数的单调性，只要某级结 点对应的特征子集满足，( 一”) 历那么以彳为根的了树巾所有结点所对应的 特征子集，都应满足易以下的结点均可不再考虑。另一方面，若在搜索过程中发 现一个二维终止结点具有少虽则可断言，它是当前搜索到的最优二维子集，于是修 改胖和夙然后继续搜索，直到伞树完毕为i 卜。 2 5 2 非完全搜索策略 分支定界法虽然比盲目穷举效率高，但在很多情况下汁算量仍然太人而难以实现， 这时不得不放弃最优解而退而求其次，力图寻找特征选择的次优解。，这又产生了两种 较为流行的优化搜索策略，即启发式搜索策略和随机搜索策略。 1 单独最优策略 最简单的方法是计算各特征单独使用时的判据值并加以排队，取前d 个作为选择 结果。但是即使各特征是统计独立的，这一结果也不一定就是最优结果，只有当可分 f)|) 性判据j 可写成j ( 肖) = j ( 葺) 或j ( 彳) = 丌，( x ，) 时，这种方法才能选出一组最优的 ，一1j _ 1 特征来。 o 华中科技大学硕士学位论文 2 启发式搜索策略 顾序前进法( s e q u e n tialf o r w a r ds eie c tio n s f s ) 这是最简单的自下而上搜索方法，每次从未入选的特征中选择一个特征，艘得它 与已入选的特征组合在一起时所得j 值为最大，直到特征数增加到d 为止。 设已选入k 个特征构成了一个大小为k 的特征组x 。把未入选的d - k 个特征，x 。， j = l ，2 ，d - k ，按与已入选特征组合的j 值大小排列： 若 ，( k + 而) ，( z j + x 2 ) ，( x k + x d i ) - 则下一步的特征组选为k + 。一j i + x l 。 开始时x o = ，直到k = d 为止。 s f s 法考虑了所选特征与已入选特征之间的相关性，一般说来比上面讲的按单独 使用时j 值最大的选择方法好些，主要缺点是一旦某特征已入选，即使由于后加入的 特征使它变为多余，也无法再把它剔除。 把s f s 法推广为每次不止增加一个特征而是增加r 个特征，就成为广义顺序i ；i 进 法( 6 e n e r a l i z e ds e q u e n t i a lf o r w a r ds e l e c t i o n ，g s f s ) 。即每次从未入选的特征 中选择出r 个特征，使得这r 个特征加入后j 值达最大。 s f s 法每次只增加一个特征，它未考虑未入选特征之间的统计相关性，而g s f s 法可以克服这个缺点，当然此时每步有一。个候补特征组需要逐个计算，因而计算量 变大了，相应地，它比s f s 法更可靠，此外它也无法剔除已入选的特征。 顾序后退法( s e q u e n tiaib a c k w a r ds eie c tio n s b s ) 这是一种自上而下的搜索方法，从全体特征丌始每次剔除一个，所剔除的特征应 使仍然保留的特征组的j 值最大。例如，设已剔除了k 个特征，剩下的特征组为置， 将冠中的各特征x j 按下述j 值大小排队，j = l ，2 ，d - k 。 若 ，( j ：一) ，( 瓦一屯) - ，( j ：一x d - k ) 华中科技大学硕士学位论文 - - _ _ - - - _ _ _ _ - - _ _ - _ _ _ _ _ - - _ _ _ | l | l l l l | - _ _ _ - _ _ - - - _ - _ _ - _ - - - _ - _ - _ - - - _ _ _ _ _ - - _ - - - _ - - - _ - _ _ _ _ _ - 贝0 x i “= k 一而 和顺序前进法比较，顺序后退法有两个特点：一是在计算过程中可以估计每去掉 一个特征所造成的可分性的降低，二是由于顺序后退法的计算是在高维空间进行的。 所以计算量比顺序前进法要大。 同样此法亦可推广为广义顺序后退法( g e n e r a l i z e ds e q u e n t i a lb a c k w a r d s e l e c t i o n g s b s ) 。 增l 减r 法( 1 - r 法) 为避免前面方法的一旦选入( 或剔除) 就不能再剔除( 或选入) 的缺点，可在选 择过程中加入局部回溯过程。例如，在第k 步可先用s f s 法一个个加入特征到k + 1 个， 然后再用s b s 法个个剔去r 个特征，我们把这样种算法叫增l 减r 法( 卜r 法) 。 具体步骤如下( 假设已经选了k 个特征。得出了特征组x 。) ： 步骤1 用s f s 法在未入选特征组磊一x k 中逐个选入特征1 个，形成新特征组 x k m 置k = k + l ，以= 五“。 步骤2 用s b s 法从x k 中逐个剔除r 个最差的特征，形成新特征组x n ，置k = k 一，。 若k = d 则终止算法，否则，置x k = x 。转向第一步。 这里要说明下，当， r 时，卜r 法足自上而下的算法，先执行第一步，然后执 行第二步，起始时应置k = o ，x o = 。当， p ( x b ) 的区域，而r t 为p ( x l 峨) p ( x b ) 的区域。 推广到多类c ，可以计算平均b h a t t a c h a r y y a 距离和平均c h e r n o f f 距离作为准则。 平均b h a t t a c h a r y y a 距离的定义为： 以= p ( a o p ( q 川 ( 3 1 2 ) ， j ，i i 平均c h e r n o f f 距离的定义为： 华中科技大学硕士学位论文 c - ic 厶= p ( c o , ) p ( c o j 蛾 ( 3 1 3 ) 选出平均b h a t t a c h a r y y a 距离或平均c h e r n o f f 距离为最小的子集作为c 类的分类特 征，这个方法虽然合理，但不是最优的准则。例如上两式中，j 移五是出多个两类的 以和碟f i t s , ，只要其中有一种类对的b h a t t a c h a r y y a 距离或c h e r n o f f 距离很大，也 就使得平均的错误概率上界降低，掩盖了对b h a t t a c h a r y y a 或c h e r n o f f 距离小的那 些类对的判别，这时往往仍得考杏每一对类别自j 的b h a t t a c h a r y y a 距离或c h e r n o f f 距离值。 采用j e f f r i e s m a t u s i t a ( j - m ) 距离可以改善这一情况，定义j m 距离为。1 以= 【2 ( 1 一e x p ( 一j “) ) 】”2 ( 3 1 4 ) 这里，尸可以指b h a t t a c h a r y y a 距离，也可以指c h e r n o f f 距离。国和两类模式分 离得1 分远时，它们的b h a tl a c h m y y a 距离或c h e r n o r f 距离7 也就变得十分大侗 j m 距离以，最大也只趋向于2 ( 即饱和) ，对尸的变动不敏感。对于b h a t t a c h a r y y a 距离或c h e r n o f f 距离小的情况，j m 距离却对，的变动比较敏感。 用于多类模式判别时，平均j - m 距离山定义为 cc 厶= p ( o , ) p ( c n j ) j 嚣 ( 3 一1 5 ) i * lj * i + l 它比平均b h a t t a c h a r y y a 距离和平均c h e r n o f f 距离有更可靠的可分性判别能力。 对于两类之间的b h a t t a c h a r y y a 距离或c h e r n o f f 距离而言，尸和船的关系是单调的； 但对多类的b h a t t a c h a r y y a 距离或c h e r n o f f 距离来说，五、五和山并不一定是单调的， 即它们并不总是能同时取得极值。 2 散度准则及其变换准则 两类密度函数的似然比或负对数似然比分类来说是一个重要的度量。设有二类珊 华中科技大学硕士学位论文 及，其对数似然比为： f 。( x ) = i n ( 3 - 1 6 ) 它可以提供，及，类的可分性信息。定义脚，类的平均可分性信息应为 似脚叭州= l 雕i q 期瑞出 ( 3 _ 1 7 ) 该式也叫做分布p ( x l q ) 相对于p ( x l q ) 的相对熵( r e l a t i v ee n t r o p y ) 、或互熵 ( c r o s se n t r o p y ) i t s j l l o ) 也叫k u l l b a c k l e i b l e r 距离。 同样对曲，类的平均可分性信息为： 弘脚】= 川q 勋篇出 1 8 ) 因此，可定义散度山为区分q 类和，类的总的甲均值，它等于两类平均可分信息之 和： ，= l + l ，= l | ，( x | q ) 一p ( x l e o ，) l t n 同样，对于多类别的特征选择可用平均散度，即 厶= p ) p ( 哆蝣( 3 - 2 0 ) i - ij - i + 1 与平均b h a t t a c h a r y y a 距离和平均c h e r n o f f 距离相似，山值也存在着数值以大 的项掩盖掉数值小的项的情况，因而采用变换散度。它定义为。1 塌= 1 0 0 x 1 一e x p ( 一碍8 ) 1 ( 3 2 1 ) 和，两类模式分离得十分远时，它们的散度彤也就变得十分人，但变换散度 以，最大也只趋向于1 0 0 ( 即饱和) ，对彤的变动不敏感。对于两类模式距离小的 情况，变换散度以，却对以的变动比较敏感。 9 ) 一) 照阿 型加 华中科技大学硕士学位论文 用于多类模式判别时，平均变换散度定义为 2 2 ) 它比平均散度有更可靠的可分性判别能力。对于两类之间的散度而言，以和瑞 的关系是单调的；但对多类的散度来说，如和而r 并不一定是单凋脚，即它们并不总 是能同时取得极值。 3 j 。、j 。、j d 在正态分布时的表达式“2 1 参数形式时( 例如指数分布) ，则可进一步简化，特别当分布为正态时可给出更明显 假定两类都是d 维正态分夼，q 类j j 技从( “，) ，q 类服从( 厶，j ) 。u p ： 脚，2 面叫l 吖：c 。帕叫。7 k “) p c x l 哆，2 齑。坤 一i 1 。x 一一，7 ：1c x 一一， ( 互) b h a t t a c h a r y y a 上界以表达式 一” 毕卜训专甩伊z s ， ( 至) c h e r n o f f 上界以表达式 ，c=圭sc，一s，c一”，卜，+c，一一，。c一“，+三加龄c。一z一， 散度以表达式 厶：；护 ( ，一，x ，一，) + f r ( ，。+ ，1 ) ( 鸬一一h 一一) ” ( 32 5 ) 华中科技大学硕士学位论文 两类协方差阵相等的情况 8 厶= 而2 厶= j o = ( “一所) 7 _ 1 ( 鸬一一) = 厶 ( 3 2 6 ) 山称为m a h a l n o b i s 距离。 当两类先验概率相等且为正念等协方差阵分稚时，我们可以推导出散度与错误概 率的关系如下“1 ： 只= e 击e x p ( 一爿砂 z ， 。其中o ，的甲方即为m a h a l a n o b i s 距离山。此时山j ：以厶则敞度增加，错误概率减 小。一般情况下还没有得到山与错误概率( 或其上下界) 之i e 的解析关系。 采用3 1 和3 2 中叙述的诸方法u , j ，总是力图寻求一个平均化的度量。更简单的 方法是在c 类中选出最难分离的一对类别，亦即选用对应于c 类中所求准则最小的数 值，来代替平均度量准则。这时，只须采用j 、j ：、k 山、j 。、kj mj 。、j c r 、j o 、 j 盯准则计算出c 类中每一对类别之间的距离值巩，再从多个现值中选出最小值，以 此来代表多类的准则，即 哦= m i n b “c 吐h 小c ( 3 一z s ) 假设一共有种特征子集，历值亦有个，将它按大小排列，从中选出最大的历值， 即 。= m 。a x l 【m 。i n f l d 。j - i 骨x ； 。，。 ( 3 2 9 ) 这种方法称为最大最小距离法，被广泛的应用在特征选择当中1 。 3 3 基于熵函数的类别可分性判据 基于熵函数的可分性判据是信息理论在模式识别中的应用之一。最佳分类器由后 验概率确定，所以可南特征的后验概率分布来衡量它对分类的有效性。显然用具有后 验最小不确定性的那些特征进行分类是有利的。在信息论中用“熵”作为不确定性的 2 1 华中科技大学硕士学位论文 度量，它是p ( q i x ) ，p ：l x ) ，p ( 。i x ) 的函数，即 h = 厶【p ( 。j x ) ，p ( 。i x ) 】 这个函数应该有下列性质”1 ： ( 1 ) 熵为正且对称：( 月，尼，只) 一肛( ， ，只) 一一肛( 尸， 一) 0 ： ( 2 ) 若只严1 ，且伴0 ( 1 j c ，i i o ) ，则成( 月，尼，只) = 0 ； ( 3 ) 总。( 只，尼，尼，o ) = 总( 只，只，只) ； 。 ( 4 ) 对于任意的概率分布，尸，o ，( 仁1 ，c ) ，只= l ，有 i = l 总c 只，尼，只，睨( ，吉，三) ； ( 5 ) 对所有事件，熵函数是连续函数。 满足上述性质的一族信息度量足如下形式的广义熵： 彤【p ( 圳n p ( 珊：，p ( 吐】= ( 2 。口一1 ) - i 喜p 。( 训x ) 一1 ( 3 - 3 0 ) 式中a 是一个实的l 卜参数，r 1 。 不同的a 值可以得到不同的熵分离度量。例如，当a 趋近于1 时，山洛必塔法则 有： 棚m 蝴脚) = 卿雩掣 窆【p a ( qi x ) p ( qi x ) l。 r = 脚旦而百一= 一p ( q l x ) l o g ：p ( a 2 , i x ) (3312 d _ i 一”4 + l n 2 o t = l 1 、“ 。 这就是s h a n n o n 熵。 华中科技大学硕士学位论文 z 【p ( q 盼p ( c 0 2 i x ) ，p ( c oj x ) = 2 1 1 - p 2 ( q m ( 3 3 2 ) ，。l 丁以将熵函数的期望值，( ) = e j c p ( c o , i x ) p ( q l x ) ，j d ( q i x ) 】) 用于对特祉的评 价。熵越大，不确定性越大，则可分性就越差；相反，熵越小，不确定性越小，则可 分性就越好。 以下将s h a n n o n 熵准则记为j 。，平方熵准则记为j 。 3 4 互信息 从以上式( 3 - 1 7 ) 对互熵的定义，我们可以进一步互信息“”( m u t u a l i n f o r m a t i o n ) 。互信息是联合分布与积分布的互熵，即 舭 y ) 。蜘灿g 静 。s ) 当x 、v 独立时，显然上式t ( i ，v ) = 0 。这也就是说，当二者独立时，y 不能给予 我们任何有关x 的信息。又 删2 妒y g 兹黜产 = 缈圳崦祭 = 一j p ( x ，y ) l o g p ( x ) + f v ( x , _ y ) l 。g p ( x l y ) = h ( x ) 一h ( x | j ，) ( 3 - 3 4 ) 该式有着良好的物理解释，即：y 能给予我们有关x 的信息，正是x 自身的不确 定性与山已知y 情况下x 的不确定性的差；灾际上该值就为y 带给x 的确定信息。 由对称性及h ( x ，y ) = h ( x ) + h ( y i x ) ，不难得到 i ( x ，y ) = h ( x ) + h ( y ) 一h ( x ，y ) ( 3 - 3 5 ) 下面，我们来证明 华中科技大学硕士学位论文 一i n ( x ，y ) = 日( 工) + h ( y 1 x ) 定义i ：联合熵 假定x 和y 的联合分布为p ( x ，y ) ，那么联含熵就为i i ( x ，y ) h ( x ，y ) = 一p ( 石，y ) l o g p ( x , y ) d x d y = - e l o g p ( x , y ) iy 定义2 ：条件熵 如果( x ，y ) 服从p ( x ，y ) ，则条什熵 日( y x ) = 一p ( 五y ) l 。g p ( y l z ) d r = - e v ( 。) l o g p ( y i x ) # y 。 亦可写为： 日( y 1 r ) = 一f p ( x ) j p ( _ y l x ) l o g p ( y l x ) c 6 c 咖= 一j p ( z ) h ( y i x = x ) a x 证明：h ( x ，即= 一f p ( x ，y ) t o g p ( x , y ) d x d y = 一l l p t x , y ) l o g p ( x ) p ( y lx ) d x d y = 一l o g p ( x ) p ( x ，y ) d y d x j f p ( x , y ) l 。g p ( y i x ) d x d y = 一f l 。g p ( x ) p ( x ) 出j p ( x ，y ) l o g p ( y i x ) c 6 c 妙 jjy = h ( x ) + h ( y l x ) ( 3 3 6 ) ( 3 - 3 7 ) 得证。 我们可以直接应用互信息来定义两类的可分性。如果我们将p ( x ) 替换为p ( x i q ) ； 而将p ( y ) 替换为p ( x i m ，) ；则两类互信息出( 3 3 3 ) 为： ，= 一f p ( x i a i ) l o g p ( x l q ) a x f p ( x i q ) l 。g p ( x i q ) 出 qq + j - j p ( x l q ，y lc o j ) l o g p ( x l q ，y 1 ) d x d y ( 3 3 8 ) n j 吼 互信息越小，表明y ( x ) 能提供的我们有关x ( y ) 的确定信息就少，也就是这两类概 率分布的差别就越大；互信息越大，表明y ( x ) 能提供的我们有关x ( y ) 的确定信息就 华中科技大学硕士学位论文 _ - _ - _ - _ _ _ - _ l l _ - l 1 1 1 - l _ - 大，也就是这两类概率分布的差别就越小。我们完全可以从这一点出发对特征进行有 效的选择”。，、 3 5 实验结果与分析 实验运用单独最优策略、启发式搜索策略中的s f s 、s b s 等三种特征选择策略对特 征维数不等的4 组特征数据分别进行了j 。、j ：、山、 、j 。、j b 、j b t 、j 。、h 、j b 、j 盯、 j 。、j 。准则下的特征选择。4 组特征数据分别是： 1 经典的4 维i r i s 特征数据；共3 类各类用于特征选择的样本数分别为3 0 。 。 2 一组1 2 维汽车c a r 特征数据：共3 类，各类用于特征选择的样本数分别为2 0 。 3 一组2 7 维由分割后图像提取的z a 2 a 特征数据：共3 类，各类用于特征选择的 样本数分别为4 0 。 4 一组2 7 维由分割前图像提取的z a 2 b 特征数据；共3 类，各类用于特征选择的 样本数分别为4 0 。 1 对第1 组数据 表3 - i 对i r i s 特征数据在3 种策略、1 3 种准则下的特征选择及排序 单独摄优策略 s f ss b s 儿 32 0l320i 32 0l j 223012301230l j 323oj 23ol 2 30 l j 4230l23012301 j 523012 0133l2 0 j b 23ol 23o1 23 0 1 j b t32 0132o1320l j c23ol2301 2301 j c t3 2 0l32 01 32 01 j d230l23o1 230l j d t32 0l320l320l j s h a n n o n l2 03l0 2320i3 j s q u a m 0 3 2l031203l2 华中科技大学硕士学位论文 2 对第2 组数据 表3 2 对_ ：8 3 - 特征数据在3 种策略、1