（通信与信息系统专业论文）机器学习中的特征选择算法研究.pdf

机器学习中的特征选择算法研究 摘要 特征选择是目前机器学习领域的研究热点之一，基因工程，文本分类，图像 检索等大规模机器学习问题的不断涌现，迫切需要准确性和运行效率等综合性能 较好的特征选择算法以及机器学习算法。近年来的研究表明许多机器学习算法受 不相关或冗余特征的负面影响，而通过选择合适的特征选择算法，可以有效的去 除不相关的特征和冗余特征，提高学习算法的泛化性能和运行效率，得到更加简 单和容易理解的学习模型。 本文首先介绍了特征选择的基础知识，并简要介绍了两种典型的特征选择算 法。特征选择算法主要分为f i l t e r 和w r a p p e r 两大类，f i l t e r 算法运行速度快、而 w r a p p e r 算法准确率高。为了充分利用两者的优点，本文提出了一种基于互信息 和遗传算法的特征选择算法，即m i g a 算法，实验表明该算法的运行速度较快， 得到的特征子集维数较小，并且分类器在该算法得到的子集上具有较高的分类准 确率。 集成学习也是近年来机器学习的研究热点，提高个体分类器的精度，增加个 体分类器间的差异，可以有效的提高集成学习的泛化性能。而特征选择是提高分 类器精度并增加个体分类器差异的有效方法，因此本文将特征选择应用到集成学 习中，提出了一种基于交叉验证和r e l i e f f 的集成学习算法( c v r e e n ) ，通过在 u c i 数据集上的实验，表明了该算法可以有效的提高集成学习的泛化性能。 特征选择主要集中在监督学习中，无监督的特征选择研究还不多，本文对无 监督的特征选择算法进行了初步的总结，并对一种典型的f i l t e r 无监督特征选择 算法做了较为详细的介绍。 本文最后对研究工作进行了总结，并指出了今后进一步的研究方向。 关键词：特征选择互信息遗传算法集成学习无监督学习 r e s e ar c ho nf e a t u res eie c t o na g o r t h m s e s e ar c l le a u ree etio nio rit 1 1 i l l sl inm a c hir el e a rnin g a b s t r a c t f e a t u r es e l e c t i o nh a sb e e nt h ef o c u so fr e s e a r c hi nm a c h i n el e a r n i n g w i t ht h e e m e r g e n c eo fl a r g e s c a l em a c h i n el e a r n i n gf i e l d ss u c ha sg e n o m ep r o j e c t s ，t e x t c a t e g o r i z a t i o na n di m a g er e t r i e v a l ，t h e r e i sa nu r g e n tn e e df o rf e a t u r es e l e c t i o n a l g o r i t h m sa n dm a c h i n el e a r n i n ga l g o r i t h m sw h i c hh a v eb e t t e ra c c u r a c ya n d e f f i c i e n c y i nr e c e n ty e a r s ，s t u d i e sh a v es h o w nt h a tm a n ym a c h i n el e a r n i n ga l g o r i t h m s a r ea d v e r s e l ya f f e c t e db yb o t hi r r e l e v a n ta n dr e d u n d a n tf e a t u r e s a n df e a t u r es e l e c t i o n h a sb e e ns h o w nv e r ye f f e c t i v ei nr e m o v i n gi r r e l e v a n ta n dr e d u n d a n tf e a t u r e s ， i n c r e a s i n ge f f i c i e n c y i n l e a r n i n gt a s k s ，i m p r o v i n gl e a r n i n gp e r f o r m a n c e l i k e p r e d i c t i v ea c c u r a c y , a n de n h a n c i n gc o m p r e h e n s i b i l i t yo fl e a r n e dr e s u l t s t h i st h e s i s f i r s t l yr e v i e w st h eb a s i ck n o w l e d g eo ff e a t u r es e l e c t i o n ，a n d i n t r o d u c e st w ot y p i c a lf e a t u r es e l e c t i o na l g o r i t h m s f e a t u r es e l e c t i o na l g o r i t h m sc a n b r o a d l yf a l li n t ot h ef i l t e rm o d e lo rt h ew r a p p e rm o d e l t h ef i l t e rm o d e lr u n sf a s ta n d t h ew r a p p e rm o d e lc a ng i v eb e t t e rr e s u l t s i no r d e rt of u l l ye x p l o i tt h ea d v a n t a g e so f b o t h ，t h et h e s i sp r o p o s e saf e a t u r es e l e c t i o na l g o r i t h mb a s e do nm u t u a li n f o r m a t i o n a n dg e n e t i ca l g o r i t h m s ，t h a ti s ，m i g aa l g o r i t h m e x p e r i m e n t ss h o wt h a tt h e a l g o r i t h mh a sg o o dc o m p r e h e n s i v ep e r f o r m a n c ew i t hr e s p e c t st oa c c u r a c y , s i z eo f f e a t u r es u b s e t s ，a n de f f i c i e n c y e n s e m b l el e a r n i n gi sa l s oah o tr e s e a r c ht o p i ci nm a c h i n el e a r n i n g b o t h t h e o r e t i c a la n de m p i r i c a lr e s e a r c hh a sd e m o n s t r a t e dt h a tag o o de n s e m b l ei so n e w h e r et h eb a s ec l a s s i f i e r si nt h ee n s e m b l ea r eb o t ha c c u r a t ea n dt e n dt oe r ri nd i f f e r e n t p a r t so ft h ei n s t a n c es p a c e o n ee f f e c t i v ea p p r o a c hf o rg e n e r a t i n ga l le n s e m b l eo f a c c u r a t ea n dd i v e r s eb a s ec l a s s i f i e r si st ou s ed i f f e r e n tf e a t u r es u b s e t s ，o rs o - c a l l e d e n s e m b l ef e a t u r es e l e c t i o n s ot h et h e s i sp r o p o s e sa ne n s e m b l el e a r n i n ga l g o r i t h m b a s e do nc r o s s v a l i d a t i o na n dr e l i e f f , a p p l y i n gf e a t u r es e l e c t i o nt oe n s e m b l el e a r n i n g e x p e r i m e n t ss h o wt h a t t h ea l g o r i t h mc a ne f f e c t i v e l ye n h a n c et h eg e n e r a l i z a t i o n p e r f o r m a n c eo f t h ee n s e m b l e 1 1 f e a t u r es e l e c t i o ni s p o p u l a ri ns u p e r v i s e dl e a r n i n g ，b u t t h e r ei sn o tm u c h r e s e a r c hi nu n s u p e r v i s e dl e a r n i n g t h et h e s i sp r e l i m i n a r i l ys u m m a r i z e su n s u p e r v i s e d f e a t u r es e l e c t i o na l g o r i t h m sa n di n t r o d u c e sat y p i c a lu n s u p e r v i s e df e a t u r es e l e c t i o n i nt h ee n d ，t h et h e s i ss u m m a r i z e st h er e s e a r c ha n di n d i c a t e st h ef u t u r ew o r k k e y w o r d s ：f e a t u r es e l e c t i o n ，m u t u a l i n f o r m a t i o n ，g e n e t i ca l g o r i t h m s ， e n s e m b l el e a r n i n g ，u n s u p e r v i s e dl e a r n i n g i i i 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含未获得 ( 洼! 麴递直基丝盂蔓壁型直盟数：奎拦卫窒2 或其他教育机构的学位或证书使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 学位论文作者虢墓布宁签字吼加u 产f 月乡日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人 授权学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用 影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学技术信息 研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向社会公 众提供信息服务。( 保密的学位论文在解密后适用本授权书) 了 否日互护“ 名年 黼俨 誊 加文期沦日位字 学签 机器学习中的特征选择算法研究 1 引言 1 1 研究意义、目的及研究背景 机器学习的一个重要问题是针对一个学习任务，选择一组具有代表性的特 征，构建一个模型。从原始特征集合中选择一个具有代表性的子集，即特征选择， 对机器学习领域中的许多问题都有重大意义【1 】，包括文本分类，数据挖掘，基因 工程，计算机视觉，信息检索等。特征选择通常选择与类别相关性强、且特征彼 此间相关性弱的特征子集，具体的特征选择算法通过定义合适的子集评价函数来 体现这一点，因此特征选择的一种定义就是从原始特征集中选择使某种评估标准 最优的特征子集。 机器学习所关注的问题是：计算机算法如何随着经验积累自动提高性能【2 j 。 研究表明没有任何一个学习算法完全优于其它算法，实际上不同的学习算法经常 产生相似的结果【3 1 。对一个学习任务有重要影响的因素是数据本身的性质，如果 数据没有包含对学习任务来说重要的信息，学习就可能失败。反之，如果数据适 合某个学习算法，学习任务就会容易的多，并且通过特征选择去除不相关和冗余 特征，可以有效减少学习时间。 近年来的研究表明许多机器学习算法受不相关和冗余特征的负面影响。例如 最近邻算法对不相关的特征很敏感，要达到给定的预测准确率，样本个数随不相 关特征的增加成指数增长【4 1 。朴素贝叶斯分类器容易受冗余特征的影响，因为朴 素贝叶斯分类器假定各特征间相互独立【5 】。决策树算法有时会对训练集过适应， 产生过于复杂的树，移除不相关和冗余特征可以产生一颗较小、容易理解的树。 由此，特征选择的作用主要有：去除不相关特征、冗余特征、甚至噪声特征，提 取关键特征，提高学习算法的泛化性能和运行效率，得到更加简单和容易理解的 学习模型【6 朋。 最早的特征选择研究是上个世纪6 0 年代开始的，当时的研究通常集中于统 计学及信号处理问题，而且一般涉及到的特征较少，并且通常假定特征间相互独 立【8 j o 自9 0 年代以来，许多应用领域，如基因工程【9 】，文本分类【1 0 1 ，图像检索【1 1 】 等，大规模数据的处理问题不断涌现，大规模数据的特征选择也对现有的特征选 机器学习中的特征选择算法研究 择算法提出了严峻的挑战，特征选择引起机器学习领域学者广泛的研究兴趣。 k i r a 和r e n d e l l 于1 9 9 2 年提出了一种著名的特性选择算法一r e l i e f 【1 2 】，该 算法属于一种特征权重算法( f e a t u r ew e i g h t i n ga l g o r i t h m s ) ，根据各个特征和类 别的相关性赋予特征不同的权重，权重小于某个阈值的特征将被移除。a l m u a l l i m 和d i e t t e r i c h 于1 9 9 2 年提出了利用信息论度量度来选择相关特征【1 3 1 。1 9 9 4 年，s t a n f o r d 大学的g e o r g ehj ，r o nk 和k a r lp 全面讨论了特征选择问题【1 4 l 。 1 9 9 7 年新加坡国立大学的d a s h 和l i u 对在此以前的特征选择方法进行了总结 扣】，d a s h 和“u 依据评判准则和搜索策略对特征选择算法进行了系统的分类。 其中特征选择的评判准则分为：距离测度、信息测度、关联测度、一致性测度以 及分类错误率测度( w r a p p e o ：特征选择的搜索策略分为：完全搜索策略、启发式 策略以及随机搜索策略。2 0 0 2 年，l u i scm 等对各种不同的特征选择算法，做 了全面的比较和评价【1 5 】。 近年来，集成学习成为机器学习领域中的研究热点之一，特征选择在集成学 习中的运用主要涉及到个体分类器的产生过程，特征选择一方面可以提高个体分 类器的精度，另一方面可以增强个体间的差异性，从而提高集成学习的泛化能力 【1 6 】。h o 提出了一种称为随机子空间法( r a n d o m s u b s p a c e ) 的集成学习算法【1 7 】， 利用随机产生的不同的特征子集，训练多个个体。o p i t z 则提出了一种利用遗传 算法搜索特征子集的集成学习算法【1 6 】，其中遗传算法的个体适应度函数综合考 虑了个体分类器的准确率和个体间的差异性，o p i t z 通过在u c i 数据集上的实验 证明了该算法优于b a g g i n g 和b o o s t i n g 算法。 特征选择领域的研究已经取得了很大进展，但由于特征选择是一个非常复杂 的问题，还需要进行大量深入的研究，目前的研究热点和待解决的问题包括以下 几个方面【1 8 j ： 1 ) 研究f i l t e r 算法和w r a p p e r 算法相结合的特征选择算法。f i l t e r 算法运行 速度快但准确率低，w r a p p e r 算法效率低但准确率高，这两种方法具有 很强的互补性，因此将f i l t e r 算法和w r a p p e r 算法综合起来，充分利用 两者的优点，是一个很有潜力的研究方向。 2 ) 研究特征选择和学习算法之间的关系。f i l t e r 特征选择算法认为特征和后 续的学习算法是独立的，即一个好的特征子集在任何学习算法上都应该 2 机器学习中的特征选择算法研究 可以取得较好的效果；w r a p p e r 算法认为特征选择不仅和数据集以及目 标函数有关，还和后续学习算法密切相关，因此采用学习算法本身的性 能作为选择特征子集的评估标准。目前对特征选择和学习算法之间的关 系尚无定论。 3 ) 集成学习中的特征选择问题。集成学 - 3 也是近年来机器学习领域中的研 究热点，集成学习中的特征选择不但要提高个体分类器的精度，而且要 寻找使得个体分类器间差异度大的一组特征子集【1 6 】。如何在集成学习中 选择一组特征子集，提高个体分类器的精度并增强个体间的差异性，来 提高集成学习的泛化能力，是集成学习的研究热点之一。 4 ) 无监督学习中的特征选择。监督学习中的特征选择算法，无论是f i l t e r 算法还是w r a p p e r 算法，都需要类别标签提供指导，而在没有类别标签 的情况下，如何进行特征选择，即无监督的特征选择，目前研究还不多， 但该方向也是一个很有潜力的研究方向。 1 2 研究内容与主要工作 本文首先介绍了特征选择的基本概念、一般过程以及典型的特征选择算法， 然后重点研究了f i l t e r 和w r a p p e r 相结合的组合式特征选择算法以及集成学习中 的特征选择问题，最后对无监督的特征选择方法做了初步的研究。本文的主要工 作包括： 1 ) 提出了一种基于互信息和遗传算法的组合式特征选择算法( m i g a ) 。 针对特征选择算法中f i l t e r 算法运行速度快、w r a p p e r 算法准确率高的特点， 提出了一种f i l t e r 和w r a p p e r 相结合的特征选择算法，即m i g a 算法，其中互 信息用于快速去除大量不相关的特征，并且指导遗传算法的种群初始化，遗传算 法用来搜索最优的特征子集。通过在u c i 数据集上的实验，表明了该算法具有 良好的综合性能。 2 ) 提出了一种基于交叉验证和r e l i e f f 的集成学习算法( c v r e e n ) 集成学习是近年来机器学习领域的研究热点之一，集成学习往往能够取得比 单个分类器更好的分类性能。理论和大量实验证明，集成学习的泛化能力与个体 分类器的精度以及个体分类器间的差异密切相关。提高个体分类器的精度，增加 3 机器学习中的特征选择算法研究 个体分类器间的差异，可以有效的提高集成分类器的性能。由此，本文将特征选 择应用到集成学习中，提出了一种基于交叉验证和r e l i e f f 的集成学习算法 ( c v r e e n ) ，用于提高集成学习的泛化能力，取得了比较好的实验效果。 3 ) 对无监督的特征选择算法作了初步的研究。 目前对特征选择的研究大多集中在监督学习中，而无监督的特征选择研究还 不多。本文对无监督的特征选择算法做了初步的总结，介绍了进行无监督的特征 选择应注意的问题以及一种典型的无监督特征选择算法，为今后该方面的深入研 究打下基础。 1 3 论文组织结构 本文第一章介绍特征选择的研究意义、目的和背景。 第二章全面介绍了特征选择的基本概念和一般过程，并介绍了两种和本文相 关的典型特征选择算法以及特征选择算法的选用。 第三章在简要介绍互信息和遗传算法的基础上，提出了一种基于互信息和遗 传算法的组合式特征选择算法，并和r e l i e f f 算法以及基于遗传算法的w r a p p e r 方法进行了实验比较和分析。 第四章首先对集成学习进行了基本概述，然后将特征选择算法应用到集成学 习的个体生成过程中，提出了一种基于交叉验证和r e l i e f f 的集成学习算法，在 u c i 数据集上对该算法进行了实验和分析。 第五章对无监督学习中的特征选择算法做了初步的总结。 最后一章总结论文中的主要工作和结论，并对进一步的工作方向做了展望。 4 机器学习中的特征选择算法研究 2 机器学习中的特征选择概述 2 1 特征选择基本概念和一般过程 至今为止，很多学者从不同角度对特征选择进行过定义，以下是几种比较有 代表性的定义： 1 ) 理想化的定义：寻找一个对目标概念必要和充分的元素个数最小的特征 子集【1 2 j 。 2 ) 经典的定义：从原始的n 个特征中选出一个由m 个特征组成的特征子 集，其中m 事先给定，m 类内散度矩阵 设有m 个类别，q l ，一，q 肘，f 2 i 类样本集 x ? ，x ! ，x 赋) ，q ；类的散 度矩阵定义为： s 。( i ) f f i 击荟i v , o _ m ( o o _ m ( o ) r 协1 ， 式( 2 1 ) 中，m ( 表示q ：类内样本的均值。 总的类内散度矩阵为： 机器学习中的特征选择算法研究 和善m 尸( q 删= 荟mp ( q 。) 击叁( x 卜m ( 0 ) ( x 卜m ) r 2 ， & = 尸( q r ) s l 善p ( q r ) 砉荟( x 2 一 ) ( x ? 一m p ) 1 ( 2 2 ) 类间散度矩阵 第i 个类别和第个类别之间的散度矩阵定义为： s 一咖( ) 一小( j ) ( 聊( 一小( ，) r ( 2 3 ) 总的类间散度矩阵定义为： 品= 主萋p ( q ) 善mp ( q ) 露) = 三萋p ( q ) ；mp ( g ) ( 一订一一q ( 一订一一1 ( 2 _ 4 ) m 令：m 为总体均值，m e p ( - r ) m n ，则有： s 口：mp ( q ，) ( m ( j l m ) ( f ) 一臃) r ( 2 5 ) 芦思谇散发怒阵 总体散度矩阵的定义为： 品= i 薯( x l - m x x ，一历尸 其中n 为总的样本数。 由此，基于几何距离的评估标准通常有： j l = t r ( s w l s 口) 小斟 r t r ( s 口) 屯2 而 ( 2 。6 ) ( 2 7 ) ( 2 8 ) ( 2 9 ) 基于概率距离的评估标准有k u l l b a k l i e b l e r 距离【3 2 j ，简称k - l 距离，其局 限性在于需要已知各个类别类概率密度函数，但是对很多实际问题来说各类别的 概率分布情况是无法预先知道的。 信息度量：信息度量是把信息论中基于熵的评估标准应用得到特征选择中， 1 0 机器学习中的特征选择算法研究 如最小描述长度( m i n i m u md e s c r i p t i o nl e n g t h ) 1 3 3 1 、互信息( m u t u a l i n f o r m a t i o n ) 1 3 4 1 、信息增益( i n f o r m a t i o ng a i n ) 3 0 l 等。 关联性度量：主要考察特征和类别的关联度以及特征间的关联度，即通常所 说的相关性和冗余性。关联性度量有线性关联( 如线性相关系数) 和非线性 关联( 如基于信息熵的互信息、对称的不确定性等【3 5 】) 一致性度量：试图找到与全集相同分类能力的最小特征子集。不一致性定义 为如果两个样本在选定的特征子集上取值相同，却属于不同的类【5 1 。 过滤式特征选择算法的优缺点分别是： 优点：算法的通用性强；省去了分类器的训练步骤，算法复杂性低，因而适 用于大规模数据集；可以快速去除大量不相关的特征，作为特征的预筛选器非常 合适。 缺点：由于算法的评价标准独立于特定的学习算法，所选的特征子集在分类 准确率方面通常低于w r a p p e r 方法。 3 1 封装式特征选择 封装式特征选择即w r a p p e r 方法利用学习算法的性能来评价特征子集的优 劣。因此，对于一个待评价的特征子集，w r a p p e r 方法需要训练一个分类器，根 据分类器的性能对该特征子集进行评价。w r a p p e r 方法中用以评价特征的学习算 法是多种多样的，例如决策树、神经网络、贝叶斯分类器、近邻法以及支持向量 机等等。h u swh 【3 6 】提出了一种利用遗传算法作为搜索策略、决策树的分类准确 性作为子集评价准则的w r a p p e r 方法。l i “3 7 】等人用遗传算法结合人工神经网络 进行特征选择和分类，并取得了较好的实验效果。i n z a 【3 8 】等则利用贝叶斯网络的 性能作为子集评价标准。这些方法都是直接利用分类器的分类性能来评价特征子 集的优劣。 封装式特征选择算法的优缺点分别是： 优点：相对于f i l t e r 方法，w r a p p e r 方法找到的特征子集分类性能通常更好。 缺点：w r a p p e r 方法选出的特征通用性不强，当改变学习算法时，需要针对 该学习算法重新进行特征选择；由于每次对子集的评价都要进行分类器的训练和 测试，所以算法计算复杂度很高，尤其对于大规模数据集来说，算法的执行时间 很长。 机器学习中的特征选择算法研究 2 3 典型特征选择算法介绍 2 3 1f i l t e r 类 在f i l t e r 类特征选择算法中，本节介绍一下后面章节要用到的r e l i e f 系列算 法。 r e l i e f 为一系列算法，它包括最早提出的r e l i e f 以及后来拓展的r e l i e f f 和 r r e l i e f f ，其中r r e l i e f f 算法是针对目标属性为连续值的回归问题提出的，下面 仅介绍一下针对分类问题的r e l i e f 和r e l i e f f 算法。 1 ) r e l i e f 算法 r e l i e f 算法最早由k i r a 1 2 】提出，最初局限于两类数据的分类问题。r e l i e f 算 法是一种特征权重算法( f e a t u r ew e i g h t i n ga l g o r i t h m s ) ，根据各个特征和类别的 相关性赋予特征不同的权重，权重小于某个阈值的特征将被移除。r e l i e f 算法中 特征和类别的相关性是基于特征对近距离样本的区分能力。 算法从训练集d 中随机选择一个样本r ，然后从和r 同类的样本中寻找最近 邻样本h ，称为n e a rh i t ，从和r 不同类的样本中寻找最近邻样本m ，称为n e a r m i s s ，然后根据以下规则更新每个特征的权重：如果r 和n e a rh i t 在某个特征上 的距离小于r 和n e a rm i s s 上的距离，则说明该特征对区分同类和不同类的最近 邻是有益的，则增加该特征的权重；反之，如果r 和n e a rh i t 在某个特征的距 离大于r 和n e a rm i s s 上的距离，说明该特征对区分同类和不同类的最近邻起负 面作用，则降低该特征的权重。以上过程重复m 次，最后得到各特征的平均权 重。特征的权重越大，表示该特征的分类能力越强，反之，表示该特征分类能力 越弱。r e l i e f 算法的运行时间随着样本的抽样次数m 和原始特征个数n 的增加 线性增加，因而运行效率非常高。具体算法如下所示： 算法：r e l i e f 算法 输入：训练数据集d ，样本抽样次数m ，特征权重的阈值6 输出：特征权重大于阂值6 的特征组成的特征子集t 。 1 置所有特征权值为0 ，t 为空集。 2 f o ri = lt omd o 1 ) 随机选择一个样本r ； 1 2 机器学习中的特征选择算法研究 2 ) 从同类样本集中找到r 的最近邻样本h ，从不同类样本集中找 到最近邻样本m ； 3 ) f o ra = i t ond o 形似) = w ) 一d i g 似，r ，n ) l m + d i f f 似，r ，m ) m ；( 2 1 0 ) 3 f o r a = 1t ond o i f 矽) 芑6 把第a 个特征添加到t 中。 4 e n d ； 2 ) r e l i e f f 算法 r e l i e f 算法比较简单，运行效率高，并且结果也比较令人满意，因此得到广 泛应用，但是其局限性在于只能处理两类别数据，因此1 9 9 4 年k o n o n e i l l ( o 【3 9 】对 其进行了扩展，得到了r e l i e f f 作算法，可以处理多类别问题。1 9 9 7 年k o n o n e k n o 扩展了r e l i e f f 算法得到r r e l i e f f 算法，该算法用于处理目标属性为连续值的回 归问题。本文仅涉及到分类问题，因此仅描述r e l i e f f 算法。 r e l i e f f 算法在处理多类问题时，每次从训练样本集中随机取出一个样本r ， 然后从和r 同类的样本集中找出r 的k 个近邻样本( n e a rh i t s ) ，从每个r 的不同 类的样本集中均找出k 个近邻样本( n e a rm i s s e s ) ，然后更新每个特征的权重，如 式( 2 1 1 ) 所示： o ) = 形o ) 一 a i r y ( a ，r ，h ，) 沏七) + 羡 五盟杰d i f f ( a , r , m ) ) 】炳尼) ( 2 _ 1 1 ) p ( c l a s s ( r ) )c 磁( r ) 。1 一 角 p “一7 在式( 2 1 1 ) 中，d i g 似，r ，r ：) 表示样本r 和样本尺：在特征a 上的差，其 计算公式如式( 2 1 2 ) 所示：m ，( c ) 表示类c 中的第j 个最近邻样本。 1 3 机器学习中的特征选择算法研究 d f f o ，r 1 ，r 2 ) = 幽丝! 二垒刨；矿彳西c 删淞 m a x ( a ) 一m i n ( a ) 。 0 ；i fa 括d i s c r e t e a n dr 1 陋】= r 2 降】 ( 2 1 2 ) 1 ；矿彳括d i s c r e t e a n dr 阳】r 2 m 】 r e l i e f f 算法具体的伪代码如下所示： 算法：r e l i e f f 算法 输入：训练数据集d ，样本抽样次数m ，特征权重的阈值6 ，最近邻样本个 数k 。 输出：特征权重大于阈值6 的特征组成的特征子集t 。 1 置所有特征权重为0 ，t 为空集。 2 f o ri = lt omd o 1 ) 从d 中随机选择一个样本r ； 2 ) 从r 的同类样本集中找到r 的k 个最近邻日，( 歹= 1 ，2 ，k ) ，从 每一个不同类样本集中均找出k 个最近邻m ，( c ) ； 3 ) f o ra = it on d o 似) = o ) 一幽箩印，r ，h ，) 女) + 墓【丙艘一蠢研鸠( c ) ) 】m k p ( c l a s s ( r ) )咄惫( 聊1 一角“一。卜”一 7 3 f o r a = 1t ond o i f 形似) 6 把第a 个特征添加到t 中。 4 e n d ； r e l i e f 系列算法运行效率高，对数据类型没有限制，属于一种特征权重算法， 算法会赋予所有和类别相关性高的特征较高的权重，所以算法的局限性在于不能 有效的去除冗余特征【3 5 】。 1 4 机器学习中的特征选择算法研究 2 3 2 w r a p p e r 类 这一节介绍一种基于遗传算法的w r a p p e r 方法。遗传算法是一种自适应随机 搜索方法，待解决的问题通过编码由多个基因构成的染色体来描述，染色体也称 作个体，每个个体对应于问题的一个可行解，多个个体的集合称为种群，利用合 理的适应度函数对每个个体进行评估，并在此基础上进行选择、交叉、变异等遗 传操作生成新的种群，并且每次都按照优胜劣汰的规则将适应度较高的个体更多 地遗传到下一代，逐步提高种群的平均性能，这样最终在群体中将会得到一个优 良的个体。 在基于遗传算法的w r a p p e r 特征选中，遗传算法的每个个体表示一个特征子 集。种群初始化时，通常随机产生一组不同的个体，代表不同的特征选择方案。 适应度函数通常由分类器的分类准确率和所选特征子集的大小两部分组成，分类 器的分类准确率越高，特征子集的维数越小，则该个体的适应度值越大，因此有 较大的机会遗传到下一代。遗传算法通过选择、交叉、变异等算子得到下一代种 群，如此迭代下去，直到满足终止条件而结束，然后输出适应度值最高的个体作 为最优的特征子集。 m a r t i n 4 0 i 、y a n g 4 1 】等利用遗传算法寻找最优特征子集，取得了满意的实验 结果。遗传算法对问题依赖性小，只需要利用适应度函数对个体进行评估，且其 全局搜索能力强，因此在特征选择中得到较多的应用，但是当应用于大规模数据 时，直接采用遗传算法的w r a p p e r 式结构，运行效率较低。 遗传算法基本框架及其在特征选择中的应用，将在本文第三章做详细的介 绍。 2 4 特征选择算法的选用 目前特征选择的应用范围越来越广，随着特征选择的研究不断深入，特征选 择的算法也越来越多，因此如何针对具体的问题，选择合适的特征选择算法，成 为一个重要的问题。 一般来说，特征选择算法的选用需要考虑下因素： 1 ) 分类器的性能。要显著提高学习算法的性能，可以采用w r a p p e r 模型。例如 1 5 机器学习中的特征选择算法研究 可以选用采用启发式搜索策略的s b s s l a s h 算法【4 2 1 ，或基于遗传算法的 w r a p p e r 方法( g a ) 1 4 3 j 。 2 ) 能否去除冗余特征。如果只是要去除不相关的特征，可以采用r e l i e f 系列算 法【1 2 】【3 9 】、互信息法( m i ) 或s y m m e t r i cu n c e r t a i n t y 3 5 1 ，这些算法可以有效的 去除和类别不相关的特征，但是无法去除冗余特征。若要同时除去不相关的 和冗余特征，可采用c f s 算法或f c b f 3 5 1 。另外还可以考虑多种算法的结 合，例如先用r e l i e f 算法快速去除不相关的特征，然后采用一种w r a p p e r 方 法去除冗余特征。 3 ) 数据集的规模。对于小规模数据，可以采用使用完全搜索策略的f i l t e r 模型 或w r a p p e r 模型，例如b b 2 9 1 、b f f 4 5 1 、b o b r o 4 6 1 。对于大规模数据，一般采 用运行速度快的f i l t e r 模型，例如r e l i e f 系列算法及f c b f 。 4 ) 类别信息。目前非监督的特征选择算法还比较少，在样本类别未知的情况下， 需要选用无监督的特征选择算法，例如d a s h 等提出的一种基于熵的f i l t e r 模型【4 7 1 。 5 ) 数据集的数据类型。r e l i e f 系列算法可以处理数值的( n u m e r i c ) 或名词性的 ( n o m i n a l ) 属性。互信息( m i ) 、f c b f 在处理连续的数值属性时，需要预 先对特征离散化。b b 、b f f 及b o b r o 等则不能处理名词性的属性 2 5 本章小结 本章系统介绍了特征选择的基本理论，包括特征选择的基本概念和一般过 程，特征选择的搜索策略和子集评价标准，f i l t e r 模型和w r a p p e r 模型各自的优 缺点，并简要介绍了两种典型的特征选择算法，最后对特征选择算法的选用做了 阐述。 1 6 机器学习中的特征选择算法研究 3 一种基于互信息和遗传算法的组合式特征选择算法 上一章对机器学习中的特征选择进行了概要综述，根据特征选择子集评估准 则和后续学习算法的关系，特征选择算法可分为f i l t e r 和w r a p p e r 两大类，这两 类算法各有自己的优缺点，具有很强的互补性。在这一章中，将首先介绍信息论 中的几个基本概念，讨论如何用信息度量来衡量数据内在的规律性，然后介绍遗 传算法的基本框架，综合考虑f i l e r 类和w r a p p e r 类算法的优缺点，提出了一种 基于互信息和遗传算法的组合式特征选择算法。该算法首先利用互信息对特征排 序，并且为后续遗传算法提供启发信息，加速遗传算法的搜索过程，最后用遗传 算法搜索最优的特征子集。在u c i 数据集上的实验表明，该算法运行效率较高， 并且可以获得较高的分类准确率。 3 1 信息论度量 信息论是人们在长期通信工程的实践过程中，由通信技术与概率论、随机过 程和数理统计相结合而逐步发展起来的一门科学。通常人们公认信息论的奠基人 是美国科学家香农( s h a n n o nc e ) ，s h a n n o n 在1 9 4 8 年发表了著名的论文通信 的数学理论 4 8 i ，奠定了现代信息论的基础。半个多世纪以来，以通信理论为 核心的经典信息论，正以信息技术为物化手段，向高精尖方向迅猛发展，随着信 息理论的迅猛发展和信息概念的不断深化，信息论所涉及的内容早已超越了狭义 的通信工程范畴，信息论与自动控制、系统工程、人工智能、仿生学、电子计算 机等学科互相渗透、互相结合，形成了- - i - j 综合性的新兴学科一信息科学【4 9 1 。 下面几节对信息论中的几个基本概念做简要的介绍。 3 1 1 信息熵 香农对信息的定义是：信息是事物运动状态或存在方式的不确定性的描述。 在信息理论中，通常用x 代表信源，信息熵h ( 为是从平均意义上来表征信源的 总体信息测度的一个量。熵的计算公式是由s h a n n o n 首次提出的，对于离散信源 x ，若它的可能取值f f g a l ，a 2 ，a n ) ，对应的概率分别为 p ( a 1 ) ，p ( a 2 ) ， 1 7 机器学习中的特征选择算法研究 p ( a n ) ，则信源x 的信息熵定义为： 4 ( x ) = 善np ( 啪g z 。雨1 ( 3 - 1 ) 信息熵h ( x ) 具有以t - - - 种物理含义： 1 ) 信息熵h ( x ) 是表示信源输出后，每个消息( 或符号) 所提供的平均信息 量。 2 ) 信息熵h ( x ) 是表示信源输出前，信源的平均不确定性。h ( ) ( ) 越大，信 源x 的平均不确定性越大，其平均信息量越大。 3 ) 用信息熵h ( x ) 表示变量x 的随机性。 因此，将熵引入到机器学习领域中，可以用于衡量属性或变量x 的纯度， 一个属性x 的熵越小，表明该属性的平均不确定越小，即属性中的数据在属性 域上的分布越不均匀，则这个数据集合越纯，极端情况下如果一个属性的所有数 据都属于同一属性值，那么这个属性的熵就为o 。反之，一个属性的熵越大，说 明该属性的平均不确定越大，数据在属性域上的分布越均匀，那么这个数据集合 也就越不纯。用一句话概括，熵是属性x “不纯度”大小的度量。 3 1 2 条件熵 一个属性x 的不纯度可以用x 的信息熵来表示，而条件熵则是衡量在另一 个属性y 己知的情况下，该属性的不确定性程度，通常用t - ( xl y ) 来表示。 在给定y 条f 牛- f ，条件熵h ( xl y ) 的计算公式为： 日( xl 】，) 2 p ( a ) h ( x1 6 ，) ( 3 2 ) 其中p ( a 。，) 是口i 和岛的联合概率，p ( a ，l a ，) 是给定6 ，条件下色的概率。 从信息论的角度看，若x 代表信源，y 代表信宿，则h ( x ) 是在接收到y 之 1 8 、， i 、一、0， 一 一 一h p 一 侈、一 一口 双一口 寿慧 l l 2 2 g g o o 、，、j 6 6 口 口 p p 。x 鲁 。x 白 。x 智 。v 智 = = 机器学习中的特征选择算法研究 前，关于输入变量x 的先验不确定性的度量，所以称为先验熵。h ( x i y ) 这个条 件熵称为信道疑义度，它表示在输出端接收到y 之后，对于输入变量x 尚存在 的平均不确定性，这个对x 尚存在的不确定性是由于干扰( 噪声) 引起的。在 一般情况下，条件熵小于无条件熵，即h ( x i y ) 滤掉和类别标签不相关的特征，初步减小原始特征集的维数。尤其对于 高维数据来说，往往存在大量不相关的特征，滤掉不相关的特征后，可 以大大降低后续遗传算法的搜索空间，提高w r a p p e r 阶段的运行效率。 在筛选之后的特征集中，参照文献 1 8 中的做法，按照互信息大小对特 征加权，目的是使得遗传算法的初始种群中含有较好的初始点，从而使 遗传算法可采用小的进化代数和小规模种群搜寻到较优的特