（信号与信息处理专业论文）特征选择的信息论算法研究.pdf

摘要 模式识别是信号与信息处理的一个重要应用领域随着人工智能存5 ( ) 年代的兴起，模式识别的发 展更为迅速，应用更为广泛。它所研究的理论和方法在很多科学和技术领域中得到了广泛的重视，推动 ，人工智能的发展，扩大了计算机应用的领域。 模式识别就是在面对某一具体事物时将其正确地归入某一类别。基于统计方法的模式识别系统主要 由数据获取、预处理、特征提取和选择、分类决策四部分组成。 特征选择在模式识别中起非常重要的作用。通过特征提取得到的输入特征数据量很大直接用于分 类需要很大的运算量，降低了模式识别的实时性。特征选择的研究任务就是寻找一种好的算法，以便在 允许的时间内找出对分类最有效的一组特征。 现在已经有许多优秀的特征选择算法，如最优搜索算法分支定界算法，次优搜索算法，模拟退 火算法，t u b u 搜索算法，遗传算法t a g u c h 实验法等。 用信息论的方法进行特征选择是近年来提出的一种新方法。用信息论算法进行特征选择要同时考虑 各输入特征对分类类别的重要性和各输入特征之间的相关性，用输入特征和分类类别的互信息反映该输 入特征对分类的重要性，用输入特征之间的互信息反映输入特征之间的冗余性，特征选择的任务就可描 述为：寻找和输出类别互信息大而和其它输入特征互信息小的一组输入特征。本文在研究这种新算法的 基础上，提出一种新的算法并将其应用于几个典型的分类识别问题，实验证明，这种算法确实有较好 的特征选择性能。 关键词：模式识别特征选择信息熵互信息 a b s t r a c t p a t t e r nr e c o g n i t i o ni sa l li m p o r t a n ta p p l i c a t i o ni l ls i g n a la n dp r o c e s s i n gf i e l d sw i t ht h ed e v e l o p m e n to f a r t i f i c i a li n t e l l i g e n c ei nt h e5 0 “c e n t u r y , p a t t e r nr e c o g n i t i o nd e v e l o p e ds p e e d i l ya n da p p l i e dw i d e l y m e t h o d s a n dt h e o r i e sb a s e do ni th a db e e na p p l i e di nm a n ) s c i e n t i f i ca n dt e c h n o l o g i c a lf i e l d s ，i t 、sh a da d v a n c e dt h e d e v e l o p m e n to fa r t i f i c i a li n t e l l i g e n c e ，e x p a n d e dt h eu s a g eo fc o m p u t e r p a h e r nr e c o g n i t i o ni st oc l a s s i c , o n et h i n gt oo n ec l a s sc o r r e c t l y p a t t e r nr e c o g n i t i o nm e t h o d sb a s e do n s t a t i s t i c a lm e t h o di sc o n s i s to fd a t aa c q u i s i t i o n ，p r e p r o c e s s i n g f e a t u r ea b s w a c t i o na n dc l a s s i f vd e c i s i o n m a k i n g f e a t u r es e l e c t i o np l a y sa ni m p o r t a n tr o l ei np a t t e r nr e c o g n i t i o ni tw i l lb eat i m ee o n s m n i n gt h i n gt o c l a s s i f yd i r e c t l yu s i n gt h ed a t a s e tw h i c hi sh u g ea f t e rf e a t u r ea b s t r a c t i n gf e a t u r es e l e c t i o ni st of i n dng o o d a l g o r i t h mm e t h o dt os e l e c tad a t a s e tw h i c hi sa v a i l a b l et oc l a s s i cw i t hf e w - d a t ai np e r m i s s i o nt i m e t h e r ew e r em a n ye x c e l l e n tf e a t u r es e l e c t i o na l g o r i t h m ss u c ha so p t i m a ls e a r c ha l g o r i t h m ，b r a n c ha n d b o u n df e a t u r es e l e c t i o na l g o r i t h m s i m u l a t e da n n e a l i n ga l g o r i t h m ，t u b us e a r c h i n ga l g o r i t h m ，g e n e t i ca l g o r i t h m t a g u c he x p e r i m e n t a lm e t h o da n ds oo n f e a t u r es e l e c t i o nb a s e do ni n f o r m a t i o nt h e o r yi san e w s u b j e c ti nr e c e n ty e a r s t h er e l a t i o n s h i p sn o to n l ) b e b v e e ni n p u tf e a t u r e sa n do u t p u tc l a s s e sb u ta l s ob e t w e e nt h ei n p u tf e a t u r e sm u s tb ec o n s i d e r e di nf e a t u r e s e l e c t i o nb a s e do ni n f o r m a t i o nt h e o r y , t h em u t u a li n f o r m a t i o nb e t w e e na l li n p u tf e a t u r ea n do u t p u tc l a s s e s i n d i c a t e si t sr o l et oc l a s s i f i c a t i o n ，t h em u t u a li n f o r m a t i o nb e t w e e nt w oi n p u tf e a t u r e si n d i c a t e st h e i rr e d u n d a n t ， f e a t u r es e l e c t i o nb a s e do nm u t u a li n f o r m a t i o ni st of i n do u ts o m ef e a t u r e sw i t hb i gm u t u a li n f o r m a t i o nt o o u t p u tc l a s s e sa n ds m a l lm u t u a li n f o r m a t i o nt oo t h e ri n p u tf e a t u r e st h ep r o p o s e da l g o r i t h m si nt h ep a p e ra r e a p p l i e dt os e v e r a lc l a s s i f i c a t i o np r o b l e m sa n dc o m p a r e dw i t ht w op r e v i o u sa l g o r i t h m s ，t h ee x p e r i m e n tr e s u l t s i n d i c a t e dt h a tt h en e wm e t h o d si n c r e a s et h ef e a t u r es e l e c t i o np e r f o n u a n c e ，i tc a nw o r kw e l ln o to n l y i nl i n e a r c l a s s i f i c a t i o np r o b l e m sb u ta l s oi nn o n l i n e a rc l a s s i f i c a t i o no n e s k e y w o r d s ：p a t t e r nr e c o g n i t i o n ，f e a t u r es e l e c t i o n ，e n t r o p y , m u t u a li n f o r m a t i o n 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。 研究生签名：弛塑羔日期：盛赳 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研 究生院办理。 研究生签名：强! 】蔓导师签名：当墼查日期：迦墨j 东南大学硕士学位论文 第一章前言匕 随着计算枫、人工智能的发展。模式识别在6 0 年代己经发展成为一门科学，它所研究的理论和 方法在很多科学和技术领域中得到了广泛的重视，应用领域也越来越广泛，如智能机器人、自动导 航、文字识别、语音识别、图象识别等等。在研究模式识剐的过程中，也产生了许多新的算法，反 过来人工智能的新技术、新算法被应用于其它领域，促进了其它学科的发展。 简单地说模式识别是把具体事物归入某一类的过程。由于不存在纯客观的分类标准，因而我 们必须主观确定分类标准。比如我们撂到一个语音信号，对于一个语音信号。按照男女可分为男音 或女音按音调可分为高音和低音，按发音者的年龄可分为儿童的声音和成年人的声音，对同一信 号，主观的分类不同，分类的标准不同，需要韵特征不同，分类的方法也不一样。 监督模式识别有统计模式识别方法和结构模式识别方法，这两种识别方法都由设计和实现两部 分构成，设计是指用一定数量的样本进行分类器的设计，实现是指用所设计的分类器对待识别的样 本进行分类。 统计模式识别系统由数据获取、预处理、特征提取和选择、分类决策等四部分组成如图l l 所示： 图1 - 1 统计模式识剐系统的组成 l 、信息获取：通过测量、取样、量化得到适合计算机处理的用矩阵或向量表示的二维图象或一 维波形。 2 、预处理：去除噪声，加强有用信息，对信号的疃变进行复原。 3 、特征提取和选择：特征提取通常是对原始数据进行变换将高维的原始数据变换为能反映类 别差别的低维输入特征。这种变换的依据是按照对象的可分性来选择的，也就是说，经过这种变换 后得到的特征可以进行分类。特征选择是对输入特征进一步降维即在提取的输入特征空间中选择 对分类最有效的少数几个特征，以提高分类器的性能。 4 、分类决策：分类决策就是在特征空间中用统计的方法将被识别对象归为某一类。基本做法是 在样本训练集基础上确定某个判决规则按这种判决规则，对被识别对象进行分类所造成的错误概 率最小或引起的损失最小。 1 第一章前言 特征的提取和选择在模式识别中起非常重要的作用。特征提取就是通过某种变换将高维原始数 据通过某种变换将其映射为能反应各类别个性的低维特征向量。尽管通过特征提取得到了比原始 数据少得多的输入特征，但输入特征的数据可能依然很大，直接用于分类仍然需要很大的运算量， 是不现实的。特征选择的基本任务是如何从许多特征中找出那些最有效的特征以达到降低特征空 间维数的目的，进而减少运算量。当原始输入数据维数不大时，特征选择也可以是从原始特征中挑 选一些最有代表性的特征的过程从这意义来说特征提取和特征选择是一回事。 在分类识别中用少数几个特征进行分类器设计，不仅能够减少运算量，提高识别速度还能 改善分类器的总体分类识别性能。因而研究特征选择的方法是非常重要的。 特征选择要解决两个问题，即可分性离判据的选择问题和算法问题。可分离性判据就是衡量一 个输入特征对分类是否有效的标准，有效的标准是什么，可以用可分离性判判据来描述即要找出 使某一可分性最大的判别函数。算法问题是要找一个好的算法，以便在较短的时间内能找出最优或 次优的组特征。 特征的选择过程是由算法决定的，评价分类效果体现了可分离性判据。 可分离性判据就是衡量特征对分类有效性的标准。在特征提取中，把一个高维空间变换为低维 空间的映射有好多种，哪种映射对分类最有效，需要可分离性判据，在特征选择中从n 个原始特 征中选择出k 个特征的各种组合也是很多的，判别哪种组台的分类效果最好，也需用可分离性判据。 统计模式识别中。有两个最基本的可分离性判据，基于错误概率最小的可分离性判据和基于风险最 小的可分离性判据。直接用错误概率和错误风险进行判断有很大的困难，通常是寻找一些更实用的 标准来衡量各类间的可分性，常用的可分离性判据有：基于类内类间距的可分离性判据，基于概率 分布的可分离性判据基于熵函数的可分离性判据等。 特征选择并非一个简单的过程，我们用j 表示可分离性判据，最容易想到的是穷举法，从n 个 特征中选择k 个特征所有可能的组合数为q = c ：，如果把各种可能特征组合的j 都算出来再加以 比较，以选择最优特征组，就是穷举法，穷举法的计算量是非常巨大的无法实现实时处理，虽然 穷举法是最优算法，但穷举法不实用，实际应用中必须寻找更为实用的次优算法。 现在可行的特征选择算法有“自上而下”和“自下而上”两种，若特征数从零逐步增n i j l 称为 “自下而上”。反之，若特征数从d 逐渐减少，则称之为“自上而下”法。具体地有分支定界法、 单独最优组合搜索法、顺序前进法、顺序后退法、l r 法等。 由于特征选择是一个优化问题，因而在特征选择中引入了一些解决优化问题的新算法，如模拟 退火算法、t a b u 搜索算法、遗传算法等。当然特征选择也可以用实验的方法进行，t a g u c h i 矩阵 法就是一种很好的优化组合实验方法。 2 东南大学硕士学位论文 由于特征选择就是选择那些对分娄识别最有效的特征组合也就是寻找对分类最有用的输入特 征。，哪癌特征包含的信息对分类识别最有用以及如何进行优化组台，就是特征选择要解决的问题。 我们知道，相同类别的模式在空间中有较短的距离，从统计分类以及统计信息的观点来看，熵、互 信息是各种情况下可以选用的比较合理的距离量度，因而近年束有学者借助信息论的概念进行特征 选择，提出了新的算法，并取得了一些成果。 第二章特征选择信息论算法的回顾 第二章特征选择信息论算法的回顾 s h a n o n 在1 9 4 8 年发表的通信的数学理论和1 9 4 9 年发表的在噪声中的通信两篇论文奠 定了现代信息论的基础，s h a n o n 也被公认为信息论的刨始人。信息论出现之后在科学界引起了极 大的震动许多科学家在这方面进行了大量的研究取得了大批成果，使信息论发展成为一个相 当成熟和完备的科学体系。信息论不仅促进了通信技术的飞速发展而且吸引了众多领域学者的注 意，竞相应用信息论的概念和方法去理解和解决本领域的问题，使得信息论在生物学、医学、经济、 管理、图书情报等领域得到了广泛的应用。 2 1 信息论的几个基本概念。“ 2 1 _ 1 信息： 按照s h a n n o n 的定义，信息是不确定性的减少量。与信息度量有关的概念有未经统计平均的自 信息量、联合自信息量、条件自信息量：统计平均意义下的熵、条件熵和联合熵。考虑多元信源之 间信息相互包含性的有互信息、条件互信息等。统计模式识别使用统计平均意义下的信息论概念。 2 1 2 一元、二元离散随机变量的信息论概念 为了描述的方便，我们建立一个如图21 的非理想观察模型，假设x 为观察输入( 信源) ，y 为 观察结果( 输出) 。 在信息论中用自信息量来描述随机变量取值的不确定性，用互信息量度量信源信息的大小。 1 ) 未经统计平均的信息论概念 若离散随机变量x 的概率空间为 【量只】：【x ，p ( x ，) 1 i = 1 , 2 ，】 则将x 取值r 的不确定性定义为x ，的自信 息量l ( x ，) ： l ( x ，) = 一l o g p ( x ) 图2 1非理想观察模型 若二维离散随机变量x 和y 的概率空间为： x - r , 】= ( r ，乃) ，p ( x ，y j ) f i = 1 , 2 ，；2 1 ，2 ， 则定义二元符号( t ，y ，) 的联合自信息量，( x ，) ： l ( x ，y ，) = 一l o g p ( x ，y j ) 4 f 21 ) ( 22 ) 至塑奎兰堕主兰堡堕墨 条件自信息量，( 一y ，) 表示在观察得到只后关于r ，的不确定性，定义为： ，( _ j y ，) = 一l o g p ( x ，j y ，) ( 23 ) 按照信息的定义，在对输入x ，观察得到输出y ，后得到的信息量应为观察之前y ，的不确定性 l ( x ，) 减去在观察之后得到y ，而对x ，的不确定性，( r ，i y ，) ，即通过观察获取的信息量为不确定性 的减少量，我们用互信息量，( t ；y ，) 表示观察到j ，得到关于t 的信息量： l ( x ，；y ，) = l ( x ，) 一l ( x ，1 y ，) = ，( y j ) 一l ( y jx ，) ( 2 4 ) ：l 。坠：型 x t l p bi 1 当r 和y 独立时，( x ，y ，) = o 即r ，和y ，独立时他们互相不包含信息。 2 ) 、统计意义下的信息论概念 离散随机变量的统计平均不确定性用离散信息熵描述 离散随机变量的信息熵h ( x 1 定义为： 日( ) = p ( x ，) ，( x ，) ：一j j ) ( ) 1 。烈薯) 但5 熵的物理意义：熵代表了输入随机变量自身的先验平均不确定性。 x 、j ，的联台信息熵定义为： h ( x ，】，) = p ( 一，y ，) ，( x ，y ，) ：一尸( x ，j ，) l 。g 尸( 。，y ，) ( 26 条件熵( i 】，) 描述了在得到观察输出y 后对输入x 的统计平均不确定性，定义为： 日( x 阶= p ( x ，y 。) ，( l y ，) ：一p c x “y ，) l 。g 尸( r ，iy ，) ( 27 ) 条件熵的意义：日( i y ) 描述了在观测到】，后对x 的统计平均不确定性，而h ( y i z ) 描 述了由于观测条件不理想引起的统计平均不确定性。 描述输出y 包含的关于输入j 的统计平均互信息( x ；y ) 定义为： 笫二章 特征选择信息论算法的回顾 l ( x ；y ) = h ( x ) 一h ( xy ) = h ( y ) 一h ( y lx ) = jp ( x i , y j g 篇畿 = 尸( x ，y ，) ，( t ，y ，) ( 28 ) 从非观察的角度看互信息也表示随机变量x 和 ，互相包含的信息量描述了x 和y 的相关 性，或者工和y 的信息冗余程度。 3 ) 、信息熵、联合信息熵、条件熵、互信息之间的关系 ，( ；y ) 2 ( ) 日( i 】，) ( 29 ) = h ( y ) 一h ( y i x ) h ( x ，】，) = ( x ) + - ( y l x ) ( 2l o ) = ( j ，) + h ( x i y ) ，( x ，) = h ( x ) + ( j ，) 一h ( x ，y ) ，( x ：】，) = ，( 】，；x ) i l x j x 、：h l x 、 互信息、信息熵之间的关系如图2 2 ，它们满足相加性。 ( 21 1 ) ( 2 1 2 ) ( 21 3 ) 图2 2 熵、联合信息熵、互信息之间的关系 2 。1 ，3 三元随机变量的几个信息论概念 在特征选择过程中，需要考虑待选输入特征和其它输入特征以及输出类别之间的信息包含情况 涉及三元随机变量的信息论概念。为此我们在二元随机变量信息论概念的基础上引入需要的几个三 元随机变量的信息论概念。 假设三元离散随机变量爿、】，、z 的概率空间为： x y z ， _ ( t ，y ，z 。) ，p ( x ，y ，z t ) l 汪1 , 2 ，= 1 , 2 ，j ；k2 1 , 2 ，k 】 1 ) 未经统计平均的三元信息论概念 6 东南大学硕士学位论文 x ，y 和卸的联合自信启、量，( t ，几，靠) l ( x 。，y i ，zk ) 2 一l o g p ( x ，y i ，z | ) 在条件z ，和y ，下关于气的自信息量，( ： l x , y ，) l ( z ix y ) = 一l o g p ( z ix y j ) ：一l 。g 丝! ：兰i 兰! ! 。尸o ，h ) ，尸( r ，y ，z ) 。p ( x ，) p ( y ，旧) 一l o g p ( x i y l z k ) 。p ( x , y ，) i ( x ，y j , 2 - ) l ( x ，yj ) 在条件z 。下r ，和y ，之间的互信息量，( r ，；y ，iz k ) ，( t ；，jz t ) = ，( 一j ) 一l ( x ，j y ，o ) = 一l o g p ( x ，l ：女) + l o g p ( x ，iy j 2 t ) l o g = l o g j p ( 一i y ，z 女) p ( x ，i 气) p 【( y ”y ，) lz t 户( 一lz k ) p ( y ，i2 女) t 与( y ，以) 之间的互信息量j ( t ；y ，以) ，( t ；y ，靠) = ，( ) 一j 墨iy ，) = 一l o g p ( x ，) + i o g p ( x if 只气) ：l o q 竺型丝型 尸( 葺) ：l o q p ( x , ly j ) p ( x , ly s z , ) p ( 鼍) p ( t1 儿) ：l 。叠整型+ l o g 墼! 笠型 。j p ( t )p ( t i y ，) = 1 ( x f ；y j ) + ，( 一；气i y ，) = ，( t ，) + l ( x ；y j1 4 ) 2 ) 、统计意义下的三元信息论概念 离散话息浦z q ( x ，y ，z ) ( 2 1 4 ) ( 2 】5 ) ( 2 1 6 ) ( 2 1 7 ) 第二章特征选择倍息论算法的回顾 y ( x ，y ，z ) = p ( x y ，o ) ，( t ，y ，z 。) r 、jk = 一p ( x ，y 。，气) l o g p ( x ，y ，z 。) + ik 在条件z 下爿和】，的信息熵 h ( x ，yz ) = ，( x ，y ，z 。) ，( t ，y ，h ) = 一p ( x ，y ，o ) l o g p ( x ，y ，k ) 。尸c x i , y j , g k g 字f 、一p ， = h ( x ，y ，z ) 一片( z ) 在条件x y 下关于z 的条件熵 h ( zx r ) = p ( x ，y j , ：。) ，( z 。h ，y ，) = 一p ( x ，y ，o ) ( ，似，y ，o ) 一l ( x ，y 伪 = h ( x ，y ，z ) 一h ( x y ) 在条件z 下并和y 的统计平均互信息，( x ；yz ) i ( x ；yz ) = p ( x ，y ，z ) ，( 一，y ，k ) 7 k = j d ( t ，y ，卸) 【，( 一f 气) 一，( _ r ，f y l 卸) 7j k = h ( x l z ) 一h ( x l r z ) = 一h ( x ，y ，z ) + h ( y ，z ) + h ( xz ) = 一日( x ，】，z ) + h ( x ，z ) + h ( yz ) = h ( x ，z ) + h ( y ，z ) 一月( x ，y ，z ) 一( z ) 与y z 的统计平均互信息，( x ；y z ) ，( x ；y z ) = p ( r ，y ，z i ) ，( _ ，y ，气) ，jk = p ( x ，y ，= ) 【，( r ，；y ，) + ，( t ，；2 ) 】 r ，j k = j ( y ：y ) + ，( y ；zy ) = ，( x ；z ) + ，( ；yz ) 3 ) 、三元随机变量各信息嫡、互信息之间的关系 h ( x ，y l z ) = h ( x ，y ，z ) 何( z ) h ( zx y ) = 日( ，y ，z ) 一h ( x f ) 8 ( 2 1 8 ) ( 2 1 9 ) ( 2 2 0 ) ( 22 1 ) ( 2 2 2 ) ( 2 2 3 ) ( 22 4 ) 东南大学碗上学位论文 ，( j ；y z ) = i ( x ；y ) + ，( ；zy ) = ，( j ：z ) + ，( x ；y i z ) ，( ；y i z ) = h ( x i z ) 一h ( x y z ) = 一h ( x ，y ，z ) + h ( y ，z ) - k h ( x z ) = 甘( ，j ，z ) + h ( x ，z ) + h ( fz ) = h ( x ，z ) + h ( y ，z ) h ( x ，y ，z ) 一h ( z ) 三元随机变量信息论概念之问的关系也可以用图2 - 3 表示： 其中：h ( x ，y ，z ) 对应于区域：a l + a ：+ a 3 + a 4 + a s + a 6 + a 7 h ( x ，y l z ) 对应于区域a ，+ a 6 + a ， ，( ，y ) h ( zx y ) 对应于区域a ； ，( x ：yz ) 对应于区域a ，( ，y z ) 对应于区域a 】+ a 2 + 彳。 根据对应关系，也可以找出其它概念的对应区域 如区域a ；对应于，( j ，：z l ) 。 ( 22 5 ) ( 22 6 ) 图23 三维信息熵、互信息之间的关系 2 2 用信息论的方法进行特征选择嵋3 22 1 概述 为了描述的方便，我们可以建立一个特征选择的模型，具体描述为： 设原始特征空间为f r 。包含有n 个特征，c 为分类类别，现需要从f r 中选择k 个最有效的 特征，形成一个新的特征空间s 。要求k n 。 把信息论的原理和概念引用到特征选择中我们可以用互信息的概念作为特征选择的可分离性 判据。 要进行特征选择，首先要寻找一个好的判别函数。特征选择就是在满足分类识别要求的前提下 在原始输入特征空间中选择几个少量的输入特征用它们进行分类可以减少分类识别的运算时间 和运算空间，提高分类识别的实时性。由于是多个输入特征共同作用于分类识别，因而在特征选择 过程中，要考虑多个特征组合对分类的有效性。在信息论的概念中，一个输入特征和输出类别的互 信息描述了该输入特征包含的分类信息，该互信息越大，说明该输入特征对分娄越有效，选择该输 入特征越有利予分类识别。如果直接考虑各种特征组合对分类识别的有效性，就需要考虑所有特征 组合对分类的有效性，通过比较才能找出对分类识别最有效的特征组，就是穷举法，尽管穷举法是 最优算法，但这种方法需要非常大的运算空间和运算时间，因而没有实际应用的价值。通常采用分 9 第二章特征选择信息论算法的回顾 别考虑各个输入特征单独作用于分类识别时的有效性，再加以优化组合的方法。按照实际的分类识 别情况可以按照某种规则先选择一个或几个输入特征作为基本特征空间s ，在这个基本特征空间 的基础上考察其它各个输入特征对分类识别作用的积极程度决定取舍。如果特征空间是逐渐递增的， 称为“自下而l ”的选择方法，反之，如果特征空间是逐渐减少的，则称为“自上而下”的选择方 法。 如果采用“自下而上”的特征选择方法总是在己选输入特征空间s 的基础上考虑选择另个 输入特征，对提高分类识别的正确率有多大的作用，因而我们需要考虑，和s 组合对分类的有效 性，这个有效性可以用信息论中的互信息，( f s ：c ) 描述，( f 5 ；f ) 是待选输入特征，和已选输入 特征空间s 联合与输出类别c 的互信息，描述了，和s 共同包含的类男信息。所以。在特征选择 的信息论算法中，( f s ，( _ t ) 可以作为特征选择的判别函数。 按照这种思想，信息论特征选择算法的基本模型是“g r e e d ys e l e c t i o n ”特征选择算法。其步骤 如下： 1 ) 初始化：将原始输入特征空间f r 赋值给f s 置空； 2 ) 对f 中的每一个输入特征厂，计算 3 ) 选择使1 ( f ；( ) 最大的那个，将，加入 到s 中，记为 c ) 寸s - 同时，从f 中去掉z ( 记为 4 ) 重复以下过程、直到选够k 个特征： a ) 对f 中的所有特征，计算j ( f s ：c ) 6 ) 选择使，( f s ；c ) 最大的那个， 图2 4 ：g r e c d ys e l c c t i o n 流程图 f 1 ) 寸s ，f ) 。 对应的算法流程图如图2 - 4 这种算法是一种“自下而上”的顺序”选择方法。前三步完成第一特征的选择，第四步完成 后续特征的选择。 在选择第一特征时，以，( f ；c ) 作为判别函数，单独考虑一个输入特征自身包含的类别信息， ) 东南大学硕士学位论文 ，( f ；c ) 是某个待选输入特征和输出类别c 的互信息，描述了输入特征，中包含的类别信息 ，( 一：；f ) 越大，说明，单独作用于分类识别时对分类越有效。 后续特征的选择瞄，( f s ；c ) 作为判别函数。i ( e s ；c ) 是由所有己选输入特征组成的特征空间 s 和待选输入特征，联合与输出类别c 的互信息，描述了在己选输入特征空间s 的情况下如果再 增加输入特征，它们共同包含的类别信息，该联合互信息越大，说明在已选特征空间s 下选择： 越有利于分类识别。所以可以选择，( f s ；( ) 为判别函数但是，直接按照定义计算，( f s ；c ) 是 非常困难的。目前有两种方法替代，( f 叠f ) 的特征选择信息论算法。 2 2 2 以，( f ；c ) 一( f ：f ) 代替，( f 只c ) 的n i f s 算法 从信息论的观点来考虑特征选择问题，选择一个输入特征，主要考虑两个因素一是该输入特 征自身包含的分类信息；一是该输入特征和其它输入特征的信息冗余。一个输入特征包含的类别信 息越大，说明选择该输入特征对分类越有利。一个输入特征和已选输入特征的互信息越大说明选 择该输入特征引入的信息冗余越多选择该输入特征的意义越小。一个输入特征和其它未选输入特 征的互信息越大说明选择该输入特征舍弃其它输入特征丢失的分类信息越少，越有利于分类识别。 如果，：是输入特征空间f 中的一个未选输入特征，z 是已选特征空间s 中的一个输入特征tc 为输出类别，互信息，( f ；c ) 代表了输入特征z 中包含的类别信息，( f ；f ) 越大，它自身对分类 就越有效：而，( f ；只) 则表示，与六两个输入特征互相包含的信息量大小也就是，和工之间的 冗余信息，或者可以理解为，与，的相关程度，其值越小选择，携带的冗余信息越少，可以携 带更多的分类信息，对分类识别越有利。因而，判决原则应当是选择和输出类别互信息大而和已选 输入特征互信息小的输入特征为晟有效的特征。 m i f s 算法选择，( f ：c ) 一( f ；只) 做判据。采用，( f ；c ) 一( f ；只) 做判据- 只需将 “g r e e d ys e l e c t i o n 选择法的第四步改为： 4 )重复以下过程，直到选够k 个特征： a ) 对f 中的所有特征 ，；计算，( f ：c ) 一，( f ；c ) ： b ) 选择使，( f ；c ) 一芦，( f ；只) 最大的那个z ，i f ) _ s ，f l 1 ，：) u 其中，z ( f ：只) 是待选输入特征z 和一个己选输入特征，的互信息，用，j ，：和每个，互信息的 塑三兰堑堡垄堡堕：! ：堡簦鲨塑旦堕 和，( f ；只) 描述统计意义下f 和所有己选输入特征f 的互信息。p 的人小反映了在特征选择 过程中考虑输入特征之间信息冗余的权重。其取值范围为0 1 ，p = 0 时，特征选择不考虑输入特 征之间的冗余性，选择结果是各个特征单独用于分类时对分类有效性的排队。p 越小，特征选择过 程更多地考虑单个输入特征对分类识别有效性：p 越大，在特征选择中更多地考虑输入特征之间的 信息冗余。这种算法称为m i f s 算法。这种算法仅用二维信息熵、互信息的概念，算法最简单。 m i f s 算法的缺点是当p 取值太大时会因过多地考虑输入特征之间的冗余而不能选择到最佳的 输入特征组。而p 取值太小时特征选择的结果几乎是各个特征单独用于分类识别时有效性的排队 这样的特征组合不一定是最佳特征组，甚至有可能是最不好的特征组。 2 2 3 近似计算，( c ；fi f ) 的m i f s u 算法 我们可以通过考虑待选输入特征z 和基本输入特征空间s 中的各个己选输入特征工组合包含 的分类信息，用统计平均的方法综合考虑待选输入特征- ，：和基本特征空间s 联合对分类识别的有效 性。 为了考察输入特征，和己选输入特征空间s 组合包含的分类信息，可以先考察，和已选输入 特征空间s 中各个己选输入特征组合包含的类别信息，他们包含的类别信息之和在统计意义下反映 了特征组s 和厂联台包含的类别信息。 假设工是某个已选输入特征，f 为待选输入特 征，c 为输出类别按照三维信息论概念它们的信 息熵、互信息、条件熵、条件互信息之间的联系如图 2 - 5 ，其中，( f 只；c ) 是，和，联合与c 的互信息， 对应干区域a 2 + a 3 + a 4t ，( f f ；c ) 越大，说明由 输入特征z 和，组合对分类识别越有效。 ，( f ：f ) 图2 5 三维信息熵、互信息之间 ( f ) ：( ) 按照三维信息论概念，参照式2 1 8 - 22 2 ，如果直接按照定义计算，( f f ：c ) ，需要用到已选输 入特征工、待选输入特征，和输出类别c 的三维联合概率质量函数及条件概率质量函数，这样势 必需要很大的运算空间和运算量。如何用，( f f ；( t ) 反映i ( f , s ；c ) ，以及如何计算，( f 只；f ) 是 信息论特征选择算法的关键。 1 2 东南大学硕士学位论文 法。 针对m i f s 算法的缺点，n o j u nk w a ka n dc h o n g h oc h o i 提出m i f s 的改进算法m i f s u 算 按照互信息的定义，我们知道， ，( f 只；c ) = h c ；e ) + ，( c ：f1 只) ( 22 7 ) 这里，( c ，e ) 是输出类别c 和已选输入特征t 的互信息，对应于图2 - 5 中区域a ! + a ， ，( c ：ff ) 是在已选输入特征z 的条件下待选输入特征，与输出类别c 的互信息，描述了在选定 ，的条件下，对分类识别的重要性，( c ；ff 只) 对应于图2 - 5 中区域a ，。在增加一个输入特征 的过程中由于对每一个待选输入特征，( c ：f ) 都是一样的，因而使，( c ；f1 只) 最大的，必 然使，( 鼻f ；c ) 最大，这样，就可以用，( c ；fl t ) 替代7 ( f e ，c ) 做判别函数由于乒在特征选 择过程中随已选特征的增加是变化的，因而按照定义直接计算，( c ：ff ) 更加困难m i f s - u 用近 似的方法计算h c ；f1 只) 。 由图中可知，条件互信息，( c ；ff ) ( 对应于图2 - 5 中区域4 ；) 可以写为 j ( c ：fi f ) = ，( c ；f ) 一 ，( 只：e ) 一，( e ；fi c ) ) ( 22 8 ) 其中，( f ：f ) 是待选输入特征，与已选输入特征z 的互信息，对应于区域a ，+ a 。 ，( f ；f | c ) ) 是在给定类别c 的条件下待选输入特征z 与已选输入特征工的互信息，对应于区域 a 。， ，( 只；f ) 一，( e ；fi c ) ) 对应于区域a 。 如果以类别c 为条件不改变工的熵与z 和五的互信息之比，即如果满足： 璺篓! 一 ，( e ，f ) 日( fl c ) j ( 只：f 】c ) 黜叫蹦l c ) = 等职 ，( c ：f1 只) = ，( c ；f ) 一 ，( 只；f ) 一，( 只；f | c ) ) 叫c 却一哿蹦) = ，( c 一丝锩产工c 矗j 阿 叫c ；耻掰配：f ) ( 22 9 ) ( 23 0 ) 【2 f 3 1 ) 第二章 特征选择信息论算法的回顾 令，( e s ；c ) _ ( 曩旷莓等她 ( 23 2 ) 】基仟，耽口j 猷将”g r e e x l ys e l e c t i o n 明| 弟叫步暖与刃 4 ) ：重复以下过程，直到选够k 个特征： 删嗍所有特征z 粮把一莩锗旭； b 懈州即m 莓掰把晟煳， c ，f i f i ) 。 比较m 1 f s 算法和m i f s u 算法的判别函数可以发现，m i f s u 算法在后续特征选择过程中，和 m i f s 算法一样考虑两个因素，一是选输入特征，和输出类别c 的互信息，( f ，c ) 一是待选输入 特征和各个已选输入特征工的互信息。b 的意义和m i f s 算法一样，反映了在特征选择过程中 考虑输入特征之间信息冗余的权重。不同的是m i f s u 算法在考虑输入特征之间的信息冗余上 一u 算法多了一个系数掰n 在增选一个特征的过程中，由于鬻仅与正、c 有关也就是仅与已选输入特征空间有 关，而和待选输入特征，投有关系，对每个，( e 只) 和h ( 只) 都是一样的，因而掰可 以看作考虑待选输入特征，和已选输入特征上互信息，c f ，只，权重的一部分一由于簧等孚l 即使b 取相同的值，和m i f s 算法相比，m i f s l i 算法考虑输入特征之间互信息的权重相对更小一些。 掰自动调节输入特征之间互信息在特征选择中的权重，其选择原则是：如果已选输入特 征工包含的类别信息在其自身不确定性中的比倒越大，考虑待选输入特征z 和该己选输入特征正 信息冗余的权重越大，选择和，互信息大的输入特征的意义越小。正是这个自动调节系数，使得 b l l f s u 算法在基本满足条件2 2 9 时表现出了更好的特征选择性能。显然，这种算法适合于信息包 含是一种线性关系的情况，也就是要求一个输入特征包含的类别信息和它自身的信息熵是成正比的， 这就是公式2 2 9 成立的条件。 龇妨两种篮洼的判剐函数百r 以借硼存m i f s i ，算法中，在第一特征选择时已经得到，f f ：c ) 、 1 4 东南大学硕士学位论文 h c ；e ) 和日( 只) m t f s 算法同样需要计算，( c ；只) 和日( 只) 因而两种算法的运算量基本是 样的。在条他2 9 成立时，月，( f 一莩需旭代酬f ；举) ，由于m i f s - u 算法多了一个自动调节输入特征之间互信息冗余的权重系数，在特征选择中有更好的特征选择性能。 和m i f s 算法一样，用已有的二维互信，g a ：l - 算三维互信息减少了直接计算三维互信息的运算量。 第三章 特征选择信息论算法存在的问题 第三章信息论特征选择算法存在的问题 m 1 f s 算法和m i f s u 算法实现了用二维互信息解决需要三维互信息才能解决的问题，使得用信 息论的方法进行特征选择需要的运算空间、运算量大大下降使信息论特征选择算法应用于实际成 为可能。但是，由于这两种算法都是近似算法，在某些情况下，其特征选择性能必然会有所下降。 影响这两种算法特征选择性能的因素主要表现在以下几个方面： 3 1 权重系数的选择问题 m i f s 算法和m i f s - u 算法在进行特征选择的过程中需要考虑输入特征自身包含的分