（计算机软件与理论专业论文）特征选择算法研究及其在孤立性肺结节诊断中的应用.pdf

重庆大学硕士学位论文中文摘要 摘要 在数据挖掘、机器学习、统计模式识别等相关领域中，特征选择作为数据预 处理的一种重要而常用的方式，是监督学习算法的一个重要组成步骤。随着计算 机科学和技术的发展，图像处理、生物信息学等大规模问题不断涌现，对已有的 特征选择算法提出了严峻的挑战，迫切需要适应大规模数据的准确性和运行效率 等综合性能较好的特征选择算法。本文在大规模数据的特征选择以及特征选择在 孤立肺结节计算机辅助诊断中的应用开展了一些研究工作，主要做了以下几部分 的工作。 首先，对目前特征选择的研究现状和问题进行了具体而深入的研究，分析了 特征选择的定义、过程、分类以及常规的特征选择算法模型，提出了特征选择算 法的选用技巧。 其次，提出了一种新的基于粗集( r s ) 与遗传算法( g a ) 的特征选择算法。该方 法将遗传算法( g a ) 与粗集限s 思想有机结合进行特征选择，引入粗集中相关属性 依赖度，设计了适应度函数和遗传算子，以提高算法的时间效率，并获得良好的 搜索结果。同时，将该特征选择方法应用于图像特征分析，实验表明该方法达到 了满意的效果，具有较高的效率。 另外，基于f i l t e r 和w r a p p e r 各自的优缺点，提出了一种基于蚁群算法的组 合式特征选择算法。该算法将蚁群算法用于特征选择，将特征作为位置点，采用 支持向量机分类器评价特征子集的性能，对特征( 点) 进行信息素的计算和更新， 为特征与特征子集的选择提供了依据，避免了盲目搜索，使搜索算法能够快速收 敛。在8 组实际数据集中的实验结果表明，从分类正确率、特征子集大小以及运 行时间等多个角度考察，该算法具有良好的综合性能。 然后，把特征选择算法应用于孤立肺结节的计算机辅助c t 诊断。系统地介 绍了孤立肺结节计算机辅助诊断系统，描述了系统知识库的建立，研究了特征对 于孤立肺结节诊断的重要性并提出了特征的层次化结构，同时将本文提出的两个 特征选择算法在人工数据集上做了实验，选择的特征较真实地反映了医学诊断依 据并获得不错的分类效果。 本文最后对研究工作进行了总结，提出了今后进一步的研究方向。 关键词：特征选择算法，孤立肺结节，粗集，遗传算法，蚁群算法 重庆大学硕士学位论文英文摘要 a b s t ra c t i nt h ef i e l do fd a t am i n i n g , m a c h i n el e a r n i n ga n ds t a t i s t i c a lp 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 , a sa ni m p o r t a n tw a yo fd a t ap r c p r o c e s s i n g 。i sa l le s s e n t i a ls t e po f s u p e r v i s e dl e a r n i n ga l g o r i t h m w i t ht h ed e v e l o p m e n to fc o m p u t e rs c i e n c ea n d t e c h n o l o g y , t h ee m e r g e n c eo fh i g h d i m e n s i o n a ld a t ap r o b l e m ss u c ha si m a g e p r o c e s s i n ga n db i o i n f o r m a t i c sp r o p o s et h es t e r nc h a l l e n g et ot h ee x i s t i n gf e a t u r e s e l e c t i o na l g o r i t h m s t h i sd i s s e r t a t i o nm a i n l yf o c u s e so nf e a t u r es e l e c t i o na l g o r i t h m f o rh i g h - d i m c a s i o n a ld a t am a di t sa p p l i c a t i o ni nc o m p u t e ra i d e dd i a g n o s i so fs o l i t a r y p u l m o n a r yn o d u l e s t h ec o n t r i b u t i o n so f t h i sd i s s e r t a t i o nm a i n l yi n c l u d et h ef o l l o w i n g p a r t s f i r s t l y , t h i sp a p e rm a k e sas p e c i f i ca n di n - d e p t hr e s e a r c ho nc u r r e n tf o c u sa n d p r o b l e m so ff e a t u r es d c c t i o na l g o f i t h m , a n da n a l y s e s t h ed e f i n i t i o n , p r o c e s s ， c l a s s i f i c a t i o na n dt h er o u t i n ea l g o r i t h mm o d e l so ff e a t u r es e l e c t i o n 。i ta l s op u t s f o r w a r dt h es k i l l so f u s i n gt h ea l g o r i t h m s e c o n d l y , an g wf 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 nr o u g hs e ta n dg e n e t i c a l g o r i t h m i s p r o p o s e d i t c o m b i n e st h er o u g hs 呱r s ) t h e o r yw i mg e n e t i c a l g o r i t h m ( g a ) p r o p e r l y , r e l a d v ea t t r i b u t ed e p e n d e n c yo fr o u g hs e tt h e n r yi su s e dt o d e s i g nt h ef i t n e s sf u n c t i o na n dg e n e t i co p e r a t o r s t h ea p p r o a c hi st h e na p p l i e dt o i m a g ef e a t u r es e l e c t i o n e x p e r i m e n t a l l y , t h en o wm e t h o di l l u s t r a t e st h eh i g ha l g o r i t h m e f f i c i e n c ya n de x c e l l e n tr e s u l t s i na d d i t i o n , o nt h eb a s eo fm e r i t sa n dd e m e r i t so ff i l t e ra n dw r a p p e rm o d e l ，a h y b r i df e a t u r es e l e c t i o na l g o r i t h mi sp r o p o s e db a s e d0 1 1a n tc o l o n yo p t i m i z a t i o ma n t c o l o n ya l g o r i t h mi su s e dt os e l e c tf c a t u r e aw h i l es u p p o r tv e c t o rm a c h i n ei sa p p l i e dt o e v a l u a t et h ep e r f o r m a n c eo ff e a t u r es u b s e t s ，t h e nf e a t u r ep h e r o m o n ei sc o m p u t e da n d u p d a t e db a s e do nt h ee v a l u a t i o nr e s u l t s t h ep r i n c i p l ei sp r o v i d e df o rf e a t u r ea n d f e a t u r es u b s e ts d e c t i o nb a s e d0 1 1t h em e t h o d sa b o v e s e a r c ha l g o r i t h mc a v o i db l i n d s e a r c h i n ga n dc o n v e r g e n c eq u i c k l y e x p e r i m e n tr e s u l t so n8p r a c t i c a ld a t a s e t ss h o w t h a tt h ea l g o r i t h mh a s9 0 0 dc o m p r e h e n s i v ep e r f o r m a n c e 、i t l lr e s p e c tt oa c c u r a c y , s i z e o 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 a f t e r w a r 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 r ea p p l i e dt oc o m p u t e ra i d e dd i a g n o s i so f s o l i t a r yp u l m o n a r yn o d u l e s i nt h i ss e c t i o n , c o m p u t e ra i d e dd i a g n o s i ss y s t e mo f s o l i t a r yp u l m o n a r yn o d u l e si si n t r o d u c e db r i e f l ya n dt h ef o u n d a t i o no fk n o w l e d g e 重庆大学硕士学位论文英文摘要 d a t a b a s ei sd e s c r i b e d t h eh i e r a r c h i c a ls h c t i l l 譬o ff e a t u r e si sp r o p o s e db a s e do nt h e i m p o r t a n o so ff e a t u r e sf o rs p n sd i a g n o s i s m e a n w h i l e , b o t ho ft h et w of e a t u r e s e l e c t i o na l g o r i t h m sa b o v ea r eu s e dt oc a l s s i f yt h ea r t i f i c i a ld a t a s c t s e x p e r i m e n tr e s u l t s s h o wt h a tt h ef e a t u r es u b s e ts d c c t e db yt h ea l g o r i t h m si so fn o to n l yt h eg o o d c l a s s i f i c a t i o np e r f o r m a n c e ，b u ta l s oc o n s i s t e n c yw i t hr e a df a c t sf o rm e d i c a ld i a g n o s i s i nt h ee n d ，t h i sp a p e rc o n c l u d e sb ys u m m a r i z i n gt h er e s e a r c ha n di n d i c a t i n gi t s f 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 na l g o r i t h m , s o l i t a r yp u l m o n a r yn o d u l e s ，r o u g hs e t , g e n e t i c a l g o r i t h m , a n tc o l o n y a l g o r i t h m m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重庆太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：蓼杰蓼 签字日期： 渺7 年j 月哗e t 学位论文版权使用授权书 本学位论文作者完全了解重庆太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重庆太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( ) 。 ( 请只在上述一个括号内打“”) 学位论文作者签名：诛杰蔓 签字日期：沙- 年罗月1 仁e t 翩张婀吖辛 签字目期：婶j 月钟日 重庆大学硕士学位论文 1 绪论 1 绪论 1 1 问题的提出及研究意义 随着数据库技术的飞速发展，大型数据库系统已经在各行各业普及，因而积 累了大量数据。在大量的数据背后隐藏着许多重要信息，而这些重要信息可以很 好地支持人们的决策。用于数据分析的数据可能包含成千上万的特征，数据集的 大小可以从两方面衡量：特征的数目n 和样本的数e lp ，n 和p 可能很大，而庞大 的n 中可能有大部分特征都是不相关的或是冗余的，而且有时会把有用的主要分 类特征淹没在大量无用特征之中，从而引起罐数灾难”问题。 数据降维常用的两类方法是特征选择和特征变换。特征变换是指将原有的特 征空间进行某种形式的变换，以得到新的特征。以主成分分析方法为代表，该类 方法的降维效果明显，但是特征的理解性很差。另外，由于特征变换的新特征通 常由全部原始特征变换得到，从数据收集角度看，并没有减少工作量。 特征选择是指从原始特征集中选择使某种评估标准最优的特征子集。以求获 得最小的特征子集，使得任务如分类、回归等达到和特征选择前近似甚至更好的 效果。理论分析和实践证明：通过删除一些和任务无关或者冗余的特征，简化的 数据集常常会得到更精确的模型，也更容易理解。 特征选择是统计学领域的经典问题，也是机器学习领域的重要问题【1 1 。在机 器学习领域，学习算法方面已经开展了大量的研究，但特征选择方面的研究则相 对较少。上个世纪9 0 年代以来涌现的大规模机器学习问题f 2 1 ，使得已有的特征 选择算法受到严峻的挑战，迫切需要适应大规模数据的准确性和运行效率等综合 性能较好的特征选择算法。特征选择引起机器学习领域学者广泛的研究兴趣，主 要原因有以下两个方面【3 】： 1 ) 许多学习算法的性能受到不相关或冗余特征的负面影响。 已有的研究结果表明，大多数学习算法所需训练样本的数目随不相关特征的 增多成指数性增长【4 】，选择好的特征不仅可以减小计算复杂度，提高分类准确度， 而且有助于寻找更精简更易理解的算法模型。 2 ) 大规模数据处理问题的不断出现。所谓大规模，一方面指样本数目的庞大， 另一方面指描述样本的特征维数高。数据挖掘的发展对大规模数据处理的研究提 出了迫切的要求，如信息检索。 由于上述原因，特征选择作为机器学习、数据挖掘和统计学领域的重要问 题，受到了广泛的重视。特征选择已广泛应用到文本分类，数据挖掘，生物信 息学，计算机视觉，信息检索，时间序列预测等方面。 重庆大学硕士学位论文1 绪论 近年来随着数字图像处理领域新理论和新算法的不断涌现，从图像中获取的 特征数量也呈现不断增长的趋势，这一方面为图像的分类识别提供了有利的条 件。同时，随着特征数量的增长，计算机用来提取特征的时间增长：而且某种 意义上讲，过多的特征量也会对分类器的设计带来困难。本文就是基于以上情 况，结合图像的特点，对于特征选择的方法进行了研究。 在图像处理识别领域，数字图像的特征复杂多样，有自然特征还有人工特征， 简要的划分有幅度特征、直方图特征、变换系数特征、光亮度边缘特征、彩色边 缘特征、像点和线段特征、纹理特征等，这些复杂的特征中常常存在着过多特征 而产生很多的冗余，造成所谓特征维数灾难”。 图像识别是一个异常高维识别问题。即使对于低分辨率的图像也常常会产生 非常高维的数据( 如1 0 0 x 2 0 0 像素的图像位于2 0 0 0 0 维空间中) 。高维数据所带来的 高计算复杂度和高存储容量增加了识别的困难。然而，有意义图像空间( 如指纹 图像、脸谱图像、c t 图像等) 的特征维数是相对较低的即高维图像数据存在相对 低维的特征表达空间，存在将高维图像识别问题向低维转化的可能性。高维数据 的降维处理作为减少“维数灾难”的有效手段，己经引起了人们的广泛注意，并在 实际应用中获得了巨大的成功，广泛应用于与数据处理有关的金融、医疗、生物、 图像、计算机网络等邻域。因此，特征选择是图像识别中一个至关重要的问题， 也是一个迫切需要解决的问题。特征选择使得图像识别问题可以在较低的维数上 来进行，从而可减少计算的复杂度，提高识别的精度，便于进行图像的识别、搜 索等进一步的处理。 因此，研究特征选择算法具有重要的学术意义和实用价值。 1 2 研究现状简介 本文主要用分类问题来说明采用的特征选择算法。理论上说，较多的特征数 据会对问题的描述越详细，因此可以提供的分类能力也越强，但在实际的应用中 并不如此，特征空间的维数不宜过高，这已经是模式识别领域中一条经验性的“公 理”。对于在训练样本数目有限的情况下，过高的特征空间维数不仅会影响分类器 的学习效率，同时也会导致分类器对训练样本过度适应的闯题，特别是那些与类 别无关的特征和冗余特征，更会误导分类器的学习。 特征选择可以从两个方面提高系统性能：一是分类速度，通过特征选择可以 大大减少特征集合中的特征数，简化计算，防止过度拟合，提高系统运行速度。 二是准确率，通过适当的特征选择，不但不会降低系统准确性，反而会使系统精 度提高p j 。 最早的特征选择研究是6 0 年代初开始的 6 1 ，早期的研究是在特征间独立的假 2 重庆大学硕士学位论文 1 绪论 设下，单独研究每一个特征的类可分性和熵，然后取效果好的组合在一起，没有 考虑特征之间的相互作用，且一般涉及的特征较少【l 】。c o v e r 指出即使满足相互独 立的条件，两个单独使用最好的特征组合起来，也不能保证得到最好的组合，在 极端情况下，反而可能成为最差的组合【j n 。 此后，一些基于近似最优解的启发式搜索方法纷纷被提出，典型的有顺序前 进法( s f s ) 、顺序后退法( s b s ) ，以及广义顺序前进法( g s f s ) ，广义顺序后退法 ( g s a s ) 等，这些算法考虑了特征的相互作用，但是缺点是：特征一旦被加入或者 被剔除，以后将不再改变，因此容易陷入局部最优。为克服该缺点，s o m o l 提出 了自适应浮动选择算法等，在一定程度上缓解了该问题。 上世纪9 0 年代以来，涌现出了大规模机器学习问题【2 胴，使得已有的特征 选择算法受到严峻的挑战，迫切需要适应大规模数据的准确性和运行效率等综合 性能较好的特征选择算法。k i r a 和r e n d e l l 于1 9 9 2 年提出了一种有效的特性选择 算法r c l i 以该算法的特征选择标准是特性相关性，该标准适用于数字的和名义 上的特征，r e l i e f 算法最大的局限性是在相关特征集中不能识别出冗余特征【9 】。 a i m u a l l i m 和d i o t t e r i c h 于1 9 9 2 年提出了利用信息论度量度来选择相关特征，该 算法对噪音数据的适应能力较差【l o 】。c a r u a n a 和f r c i t a g 于1 9 9 4 年提出了一个改 进的基于w r a p p e r 模型的贪心算法，但用于学习算法的度量却大大地增加整个程 序的计算时间l j “。 特征选择引起机器学习领域学者广泛的研究兴趣，国内外的各大研究机构如 c m u ，s t a n f o r d ，w a s h i n g t o n ，南京大学，哈尔滨工业大学，北京工业大学等都开 展了相关研究吲【1 3 】【1 4 】。 近十几年来，特征选择研究呈现出多样化和综合性的趋势。各种新搜索算法 和评估标准都应用于特征选择算法中。如粗糙集算法用于特征选择【h 1 6 1 ，t a b u s e a r c h 算法应用于特征选择1 ；, l e t s 】，神经网络剪枝法进行特征选择，支持向量机的 评估标准用于特征选择【1 9 1 ，特征集的模糊熵评价 2 0 1 1 2 1 1 等。并且除监督式学习的特 征选择研究外，也开展了关于非监督式学习的特征选择研究。另外出现了关于特 征选择的算法融合性的研究，如关于f i l t e r 方法和w r a p p e r 方法结合的研究。 虽然特征选择领域的研究近年来取得了很大进展，但由于特征选择问题和实 际对象的复杂性，还需要进行大量深入的研究，目前研究热点和需要解决的问题 包括以下方面。 1 ) 使用具有代表性的研究数据。目前，大部分关于特征选择的研究采用u c i 机器学习数据库作为研究平台，而u c i 数据多是由特定领域内的专家提供的，剔 除了数据库中不相关的特征，而且数据量一般也不是很大。为研究特征选择算法 在大规模数据集上的性能，可以选择特征数目较多、数据量较大的实际研究对象 3 重庆大学硕士学位论文1 绪论 作为实验平台。另外，使用人工数据，研究者可以根据需要指定参数，而专门研 究具体因素对特征选择算法的影响。 2 ) 研究过滤式和w r a p p e r 相结合的特征选择算法。过滤式方法快但准确率 低，w r a p p e r 方法慢但准确率高，目前关于此方面研究尚处于起步阶段，因此将 过滤式方法和w r a p p e r 方法结合起来以得到综合两者优点的特征选择方法是一个 很有潜力的研究方向。 3 ) 研究特征选择和学习算法之间的关系。 过滤式特征选择算法认为特征和后边的学习算法是独立的，即一个好的特征 子集在任何学习算法上都应该取得较好的效果；w r a p p e r 算法认为特征选择不仅 和数据集以及目标函数有关，还和后边的学习算法的性能密切相关，因此要用学 习算法本身的性能作为选择特征子集的评估标准。目前对特征选择和学习算法之 间的关系仍无定论，k o h a v i 用几个实例证明了过滤式算法的不足【1 2 】，但是s a n m a y 认为k o h a v i 所举的都是很特殊的假想例子【2 2 1 ，在实际情况中一个好的特征子集 能使任何学习算法得到好的结果。进一步深入研究特征选择和学习算法之间的关 系对于指导特征选择算法的构造有重要意义。 1 3 论文主要工作 本文研究的主要内容：一是特征选择算法的综合研究；二是两种具体特征选 择算法的设计与研究，并做出了实验及结果评价；三是特征选择算法在基于c t 图像的s p n 计算机辅助诊断中的研究。 在特征选择的研究方面，针对目前图像识别中原始特征数量大、不相关特征 多以及冗余等现象，提出了一种于改进的r s g a 特征选择算法。将遗传算法( g a ) 与粗集假s ) 思想有机结合进行特征选择，在粗集算法属性约简的思想上，利用遗 传算法的自适应搜索进行最优属性约简的搜索。接着在此基础上，针对粗集约简 n p 难的问题引入粗集中相关属性依赖度的定义，又设计了适应度函数和遗传算 子，以提高算法时间效率和获得最佳搜索结果。随后，将该特征选择方法应用于 图像，并选择了特征数目2 0 以上且不同规模的数据集进行实验，结果表明该基于 改进的r s g a 特征选择方法达到了满意的效果，并具有较高的算法效率。 另外。在特征选择算法研究方面，在分析特征选择算法的f i l t e r 和w r a p p e r 模式基础上，综合比较了两者的优缺点，提出了一种基于蚁群算法的组合式特征 选择算法，将基础蚁群算法改进用于特征选择，以特征为位置点，对特征点进行 信息素的计算和更新，同时引入了支持向量机分类器评价特征子集的性能，在蚂 蚁选择特征和迭代中选择特征子集都有了依据，避免了盲目搜索，使搜索算法能 够快速收敛。然后选择了8 组实际数据集对算法进行实验验证，结果表明该基于 4 重庆大学硕士学位论文l 绪论 蚁群算法的组合式算法不仅能够提高分类正确率，而且整个算法的运行速度较快。 在s p n s 计算机辅助诊断的研究方面，分析了目前s p n s 的研究现状和意义， 建立了系统知识库，并手工获取医学专家知识规则将特征重要性进行了初步分级； 然后介绍了一种目前比较常用的实验性能评估标准，最后利用本文第四章提出的 特征选择算法在人工数据集上进行了实验分析，对图像特征进行维数约简，结果 表明本文特征选择算法在一定程度上提高了孤立肺结节的计算机辅助诊断性能， 并反应了实际医学专家知识。 1 4 论文组织结构 本文共分5 章。各章具体安排如下： 第一章介绍了机器学习中商维数据特征选择问题的提出及研究背景和意义， 以及特征选择算法研究的历史现状。 第二章全面介绍了特征选择的基本概念和一般过程，典型的特征选择算法， 以及特征选择算法的挑选及应用等。 第三章对粗糙集的有关理论和遗传算法的基本知识进行了简单的介绍，重点 介绍了本文提出的改进的r s g a 特征选择算法的设计，并在实际数据集上通过实 验比较分析了该特征选择算法性能。 第四章简单介绍了蚁群算法的思想和应用，重点介绍了本文提出的基于蚁群 算法的组合式选择方法，在各种实际数据集上进行了大量实验，验证了算法的性 能，并总结了几种常用的分类方法。 第五章对孤立肺结节计算机辅助系统进行了简单的介绍，并以图像数据为引 导介绍了知识库的建立和特征选择方法在自制数据上的实验效果，同时也介绍了 一种目前比较常用的实验性能评估标准，评价特征选择算法对系统性能的改善。 最后一章总结论文中的主要工作和结论，并展望迸一步工作方向。 5 重庆大学硕士学位论文2 机器学习中特征选择算法的介绍 2 机器学习中特征选择算法的介绍 特征选择是数据预处理的主要内容之一，也是本论文研究工作的重点，本章 介绍了特征选择的基本概念和分类，给出了目前一些典型算法进行描述，并分析 了选用合适的特征选择算法所需要考虑的因素。 2 1 特征选择的基本概念 2 1 1 特征选择的定义 机器学习中的特征选择可定义为：已知一特征集，从中选择一个子集使评价 标准最优【2 3 1 。该定义可以表述为：给定一个学习算法l ，一个数据集s ，数据集 s 来自一个具有n 个特征x 1 ，x 2 , x 3 ，x n ，具有类别标记y ，以及符合分布d 的例子空间，则一个最优特征子集x o p t 是使得某个评价标准j - j ( l ，s ) 最优的特征 子集。 由特征选择的定义可见，在给定学习算法，数据集，以及特征集的前提下，各 种评价准则的定义和优化技术的应用将构成特征选择的重要内容。图2 1 显示了 包含特征选择的机器学习系统基本组成部分，可见，整体上来说，特征选择是机 器学习算法的前处理阶段。 图2 1 机器学习系统的基本构成 f i g2 1b a s i cf o r mo fm a c h i n el e a r n i n gs y s t e m 特征选择和特征提取是数据降维的两个重要方式，这两个常同时出现在同一 文献当中，但意思上却是不同的，为了避免混扰，现对这两个名词进行一些相关 说明。 特征提取( f e a t u r ee x t r a c t i o n ) ：当样本处于高维空间的时候，通过映射( 或变 换) 的方法可以用低维空间来表示样本，这个过程明傲特征提取。映射后的特征 叫二次特征，它们是原始特征的某种组合。特征提取在广义上就是指一种变换。 若y 是测量空间，x 是特征空间，则变换a ：y - x 就叫做特征提取器。用于图 像处理的特征提取主要方法：主成分分析p c a ( p r i n e i p a lc o m p o n e n ta n a l y s i s ) 、核 6 重庆大学硕士学位论文2 机器学习中特征选择算法的介绍 函数主成分分析t k c m e lp c a ) 、独立主成分分析法( i c a ) 脚】、奇异值分解 s v d ( s i n g u l a rv a l u ed e c o m p o s i t i o n ) 、自组织映射s o m ( s c l f - o r g a n i z i n gm a p ) 、 f a s t m a p 、多尺度方法( m u l t i d i m e n s i o n a ls c a l i n g ) 等，主成分分析是这类方法中最著 名的算法。在b 1 0 b w o r l d 系统中采用s v d 对直方图进行降维；在i m a g e r o v e r 系 统中，利用p c a 降维；在l c p d 系统中利用k l 变换来降维。 特征选择( f e a t u r es e l e c t i o n ) ：主要研究一组原始特征中挑选出一些最有效的特 征以达到降低特征空间维数的目的，这个过程叫做特征选择【2 5 】。其目的是根据一 些准则选出最小的特征子集，使得任务如分类、回归等达到和特征选择前近似甚 至更好的效果。通过特征选择，一些和任务无关或者冗余的特征被删除，简化的 数据集常常会得到更精确的模型。 从两者的说明可以总结出来区别：特征提取得到的结果是新的组合特征， 这些组合特征往往只具有数学意义，而从物理上很难理解；而用特征选择所得到 特征实际上就是原始的特征，往往具有很明显的物理意义。由特征提取所得到 的特征往往是多个原始特征的组合。在很多情况下，当用这些组合特征进行模式 识别的时候实际上还是需要对所有的原始特征进行测量。而特征选择的结果则是 指示出一些必要测量的重要的原始变量，而其余冗余的或是噪音性质的原始特征 就可以忽略不计了，也就是使用较少的测量变量达到精确决策的目的。 2 1 1 特征选择过程 l i u 和m o t o d a 在1 9 9 8 年提出了一个统一的通用特征选择模型，该模型将特 征选择过程分为四个部分；特征子集的产生、特征评估、终止标准和特征子集测 试，图2 2 描述了这种特征选择模型。特征选择涉及其中两个关键问题：一个是 有效的特征搜索策略，另一个就是合适的评价标准。首先在原始特征集中按照某 种搜索策略产生特征子集成为候选特征子集，然后利用选用的评估准则来评价候 选子集产生局部最佳特征子集，判断终止条件，逐步迭代形成最终的最佳特征子 集。 图2 2 特征选择框架 f i 9 2 2f r a m e w o r ko f f e a t u r es e l e c t i o n 7 重庆大学硕士学位论文 2 机器学习中特征选择算法的介绍 1 ) 子集的产生 这是一个搜索过程，通过一定的搜索策略产生候选的特征子集。包含搜索的 开始点和搜索策略两部分。搜索策略包括完全搜索( c o m p l e t es e a r c h ) 、顺序搜索 ( s e q u e n t i a ls e a r c h ) 和随机搜索( r a n d o ms e a r c h ) ，总结如表2 1 所示。 表2 1 特征选择的搜索算法总结 t a b l e 2 1s e a r c ha l g o r i t h ms u m m a r i z eo f f e a t u r es e l e c t i o n 算法名称算法描述 s f s 顺序前向搜索算法( s e q u e n t i a lf o r w a r ds c a r o h ) 顺序后向搜索算法 s b s ( s e q u e n t i a lb a c k w a r ds e a r c h ) s f s 从空集开始，先选择评估最好 的一个特征k ，然后在选择包括k 的评估最好的疆个特征。如此 继续，特点是选中的特征就不会被删掉。s b s 从全集开始，不断删 除特征，特点是删掉了就不会再被选中 g s f s ( g )广义的顺序前向搜索算法和顺序后向搜索算法( g e n e r a ls e q u e n t i a l g s b s ( g ) f o r w a r d b a c k w a r ds e a r c h ) 每次评价大小为g 的特征子集，每步操 作为g 个特征被加入( 前向搜索) 或者删除( 后向搜索) p t a ( i 曲加l 减r 法p l u s l t a k e a w a y r ，前行l 步( 通过s f s 方法加入1 g p t a ( ! 曲个特征) ，后退r 步( 通过s b s 方法减掉r 个特征) ，g p t a ( i , r ) 选用g s f s ( i ) 方法加特征，o s b s ( 0 方法减特征 s f f s p t a ( 1 , r ) 方法的浮动模式。和p t a ( 1 , r ) 不同，s f f s s b f s 不限定前 s b f s 行后退的步数，s f f s 和s b f s 方法可以无限制的回溯，只要回溯 可以找到比目前的特征更好的特征。s f f s 和s b f s 的不同之处在 于算法的搜索空间的起点不同。s f f s 从空集开始，而s b f s 从全 集开始 b a b ，分支界限法及其扩展系列，一般需要评价函数单调，可以找到最优 b a b +解 b a b + + 等 g a 遗传算法不能保证找到最优解但是搜索空间较大，速度较快，不易 陷入局部极值 s a 模拟退火搜索算法，计算量较大，初始温度以及每个温度值下的迭 代次数难以设定 完全搜索：可以保证获得对于给定的评价准则是最优的特征子集，例如穷尽 搜索就是一种完全搜索。但是，并不是说所有的完全搜索都是穷尽搜索，某些启 发式评价函数可以用来减少搜索空间并能保证获得最优特征子集。相应的算法有 分支限界法( b o u n db r a n c h ) 2 s 埽钉b s ( b e a l t ls e a r c h ) 算法【2 9 1 。 顺序搜索：包括贪心爬山法的各种变化，如顺序前向搜索( s f s ) ，顺序后向 搜索( s b s ) ，以及广义的顺序前向搜索( g s f s ) 和广义的顺序后向搜索( o s b s ) 等。 该类算法的缺点是，特征一旦被加入或删除，以后便不会改变，因此容易陷入局 8 重庆大学硕士学位论文 2 机器学习中特征选择算法的介绍 部极值。为克服此缺点，出现了增1 减r 法，即搜索方向不再是单向加或者减，可 以根据评估函数灵活的浮动，其问题在于l 和r 的大小难以确定。p u d i l 等提出了顺 序浮动前向搜索( s f f s ) 和顺序浮动后向搜索算法( s f b s ) 口“，算法变固定的增l 减r 法为浮动的，减少了不必要的回溯并在需要时增加回溯的深度，s o m o l 等进一步 提出了自适应浮动搜索算法【蚓，根据当前特征子集的大小和目标特征子集的大小 来控制搜索空问的大小，这种方法减小了陷入局部极值的可能性。 随机搜索：包括遗传算法、模拟退火等。遗传算法在特征选择中的应用研究 很多，并且显示出良好的性能d ”。 关于各搜索算法的优劣并没有一致的意见，但根据j a i n 和k u d o 的实验，自适 应浮动搜索算法和遗传算法是众多搜索算法中性能较好的算法鲫【3 3 l 。 2 1 子集评价 每一个候选的特征子集都根据一定的评价准则进行评价并与先前最优的特 征子集进行比较。根据特征选择与学习算法的相关可以将特征的评价标准大致分 为关联准则和独立准则两类。 a ) 关联准则：通常应用在封装器模型的特征选择算法中，先确定一个学习 算法并利用学习算法的性能作为评价准则。在髓督特征选择中，分类准确率为常用 的关联准则；在非监督特征选择中；常利用特定的聚类算法在所选择的子集上的 聚类质量来评价特征子集。这类评价标准的缺陷是一般时问开销较大。 b 1 独立准则：通常应用在过滤器模型的特征选择算法中，试图通过训练数 据的内在特性来对所选择的特征子集进行评价，独立于特定的学习算法。 通常包括：距离度量、信息度量、关联性度量、一致性度量。 距离度量：又包括类间距离度量和概率距离度量。类间距离度量中又有欧式 距离，马氏距离( m a h a l a b o b i sd i s t a n c e ) 等；概率距离度量有b h a 妇吐a 珊距离和 k u l l b a k - l i e b l e 艟离等；类似的还有概率相关度量。下面给出部分常用距离公式。 欧式距离： ，( 置，) = ，( j 一勺j ) 2 yj e ， 马氏距离： ，( f ) = o - 一“z ) 7 乏： ，一) - 1 b 曲t t a e h a r y y a ：j ( f ) = 一i l o g 、 p ( fic 1 ) 尸( ，ic 2 ) d r k u l l b a k - l i e b l e r ：，( f ) = j t p ( f ic i ) 一p ( f jc 2 ) 】l o g 船 信息度量：主要计算特征的信息增益。常用的有基于信息熵的各种评估标准， 如信息增益( i n f o r m a t i o ng a i n ) 、最小描述长度( l i n i n l e l n 2d e s c r i p t i o nl e a g d l ) 、互信 息( m u t u a li n f o m 埘o n ) 等。 9 重庆大学硕士学位论文2 机器学习中特征选择算法的介绍 关联性度量：主要是度量以一个变量的取值去获取另一个变量的能力。在监 督特征选择中，主要关注特征与类的关联性。非监督特征选择中，主要考虑特征 之间的关联性。 一致性度量：试图找到与全集相同分类能力的最小特征子集。不一致性定义 为如果两个样本在选定的特征子集上取值相同，却属于不同类。常用的有在f o c u s 特征选择算法中提出的不一致度。 3 )终止条件：与子集的产生过程有关和选用的评价准则有关。 结果验证：根据一定的先验知识或通过合成现实数据集的测试来证明所选择 的特征子集的性能。而在实际应用中，这种先验知识是无法获得的，于是就通过 特征子集对学习算法的性能影响来验证所选择特征子集的质量。 2 1 2 特征选择分类 特征选择和机器学习算法两者存在紧密地联系。根据特征选择和后续学习算 法的结合方式可分为嵌入式( e m b e d d e d ) 、过滤式( f i l t o r ) 和封装式( w r a p p e r ) 式三种 伫7 】。 e m b e d d e d 特征选择 在嵌入式特征选择结构中，特征选择算法本身作为组成部分嵌入到学习算法 里。最典型的算法即决策树算法。如b r e i m a a 的c a r t 算法，算法在每一节点选 择分类最强的特征，然后基于选中的特征进行子空间分割，继续此过程，直到满 足终止条件，可见决策树生成的过程也就是特征选择的过程。 f i l t e d 征选择 过滤式特征选择的评估标准独立于学习算法，直接由数据集求得。过滤式特 征选择的评估依赖于数据集本身，通常是选择和目标函数相关度大的特征或者特 征子集，一般认为相关度较大的特征或者特征子集会对应得到后续学习算法较高 的准确率。 优：通用性强，算法复杂性低，运行效率较高适用于大规模数据集。 缺；由于忽略了所选特征子集在分类算法上的性能，选出的特征子集也许 不能最优。 w 瑚p p e r 特征选择 其核心思想：将学习算法的性能作为特征选择的评估标准。和学习算法无关 的过滤式特征评价会和后续的分类算法产生较大的偏差，而学习算法基于所选特 征子集的性能是更好的特征评价标准。w r a p p e r 特征选择算法中用以评估特征的 学习算法是没有限制的。如j o h n 等选用决策树【4 3 1 ，i n z a 等则利用贝叶斯网络性能 指导贪心的前向搜索算法】。 优：对于特定的分类器来说可找到最优的特征子集，算法准确率高。 l o 重庆大学硕士学位论文2 机器学习中特征选择算法的介绍 缺：由于每一次对子集的评价都要进行分类器的训练，所以计算的复杂度很 高。过适应问题，该问题主要发生在训练数据规模较小的情况。 基于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 优点的组合式特征选择算法。如h u a n g 提出的一种两阶段组合式特征选择算法 1 3 1 ，d a s 提出的组合式算法2 2 1 。 2 2 部分典型特征选择算法介绍 下面介绍几种典型的特征选择算法。 2