（计算机软件与理论专业论文）特征选择新算法研究.pdf

磐1 7摘要【iiiiiiiitii iii iq11 1111iiitiii18 8 9 3 12特征选择是模式识别和数据挖掘领域中的关键环节之一，按照和后续分类算法结合的不同方式，特征选择算法可以分为嵌入式、封装式、过滤式三种模型。过滤式( f i l t e r )算法凭借其算法较强的通用性和较低的复杂度等优势成为研究领域的热门，涌现出了大量的基于过滤式模型的特征选择算法。但是f i l t e r 模型的特征选择过程独立于分类过程，导致采用f i l t e r 模型特征选择算法所选出的特征与后续分类算法的性能有较大的偏差，会产生一定程度上的错分。许多特征选择算法在进行特征评价时由于缺乏对特征间相关性的考虑而产生了特征冗余，使得算法的效率降低并由于特征冗余影响到分类识别率。这就要求我们提出有效的改进算法进一步的降低f i l t e r 算法的错分率和去除特征子集中存在的特征冗余，最终得到无论是基于分类还是特征相关性都有效的特征子集。本文从这两方面着手展开工作，主要包括以下三个方面的内容：1 、迹比算法是典型的f i l t e r 模型的特征选择算法，该算法采用一种全新的迭代方式直接计算特征子集一级的得分，以此为依据得到最终的特征子集。算法区别于计算特征一级得分的传统算法，在较短的时间内得到较为优秀的特征子集，但是由于f i l t e r 模型算法的缺陷，该算法得到的特征子集所指导的分类会产生一定程度上的错分。本文采用一种基于错分区域的特征选择算法对迹比算法进行改进，通过特征空间的映射在当前特征空间的补空间中寻找对正确区分错分样本贡献最大的特征，加入到特征子集中构成最优特征子集。该整合后的新特征选择算法有效的降低了错分率，在基于错分区域的处理中，对于特征的再选择使用前向搜索和+ l r 两种方法，并进行实验比较两种改进算法的性能。+。2 、为了有效应对特征冗余问题，本文对特征选择问题中特征间的相关性和特征与类的相关性做了详细的研究，给出了传统的基于特征相关性的特征选择算法的步骤和流程。并采用基于k n n 聚类的非搜索特征选择算法对迹比算法进行改进，以特征间相关性度量为出发点，剔除特征子集中的冗余特征，在保证分类算法识别率的前提下有效地降低了数据维度。算法经由o r l 人脸数据和u c i 数据集的w i n e 、a u s t r a l i a n 验证，证明了改进算法有效的去除了特征冗余，程度略有不同。3 、本文对r e l i e f 算法进行了研究和改进，从改善错分和剔除冗余两个角度对算法进行改进。r e l i e f 算法是典型的f i l t e r 算法，其选出的特征子集在指导后续分类算法时会产生错分数据，为了对其算法进行改进，我们使用基于错分区域的+ l r 算法对错分区域进行处理；r e l i e f 算法在特征的选择过程中强调特征与类的关联，并以此作为特征评价的标准，算法在选择特征的时候缺少对特征之间关联性的考虑，我们结合之前的改进算法提出了一种双重改进r e l i e f f 的优化算法，通过u c i 数据集的实验证明新算法的特征子集优于原始单一改进算法的特征子集。关键词：特征选择；迹比算法；特征相关度；k n n 特征选择算法；r e l i e f 算法a b s t r a c ta b s t r a c tf e a t u r es e l e c t i o ni so n eo ft h ec o r ei s s u e si nt h ea r e ao fp a r e mr e c o g n i t i o na n dd a t am i n i n g f e a t u r es e l e c t i o nc a nb ed i v i d e di n t ot h r e ec a t e g o r i e sa sf i l t e rm o d e l ，w r a p p e rm o d e la n de m b e d d e dm o d e la c c o r d i n gt ot h ec o m b i n a t i o no fd i f f e r e n tc l a s s i f i e r s f i l t e rm o d e lh a si t so w na d v a n t a g ea sg o o dc o m m o n a l i t ya n dc o m p a r a t i v e l yl o w e rt i m e c o s t ，s of i l t e rm o d e li st h em o s tp o p u l a rm o d e li nt h er e s e a r c ho ff e a t u r es e l e c t i o ni nt h e s ey e a r s b u ti nf i l t e rm o d e l ，t h ep r o c e s so ff e a t u r es e l e c t i o ni si n d e p e n d e n to ft h ep r o c e s so fc l a s s i f i c a t i o n s e l e c t e df e a t u r e - s u b s e th a so f f s e tt ot h ec l a s s i f i e rn e e d s 1 1 1 ee r r o r - r a t eo fc l a s s i f i e rw i l ln o ts a t i s f y , a n db e c a u s eo fi t sl a c ko fc o n s i d e r a t i o no ff e a t u r e r e l e v a n c ei n d e xt h ef i n a ls u b s e te x i s t sf e a t u r er e d u n d a n c y s ow en e e dp u tf o r w a r dan e wi m p r o v ea l g o r i t h mt ol o w e re r r o r - r a t eo ff i l t e rm o d e la n de l i m i n a t ef e a t u r er e d u n d a n c y , f i n a l l yo b t a i nab e s ts u b s e tw h i c hn o to n l yf i tt h ec l a s s i t i e rn e e d sb u ta l s om e e tt h en e e do ff e a t u r e r e l e v a n c ei n d e x t 1 1 i sa r t i c l em a i n l yc o n t a i n st h r e ep a r t sb a s e do nt h ei d e a s ：1 t r a c er a t i oc r i t e r i o na l g o r i t h mi sac l a s s i c a lf i l t e rm o d e la l g o r i t h m i tu s e san e wi t e r a t i v ep r o c e d u r et od i r e c t l yo p t i m i z et h es u b s e t - l e v e ls c o r ef m d i n gt h eg l o b a lo p t i m a lf e a t u r es u b s e t t r a c er a t i oc a no b t a i nar e l a t i v e l yg o o ds u b s e ti nas h o r tt i m e b u tb e c a u s eo fs h o r t c o m i n go ff i l t e rm o d e l ，a c c u r a t e r a t eb a s e do nt h i sm o d e li sn o ts a t i s f i e d i no r d e rt oa c h i e v eab e t t e ra c c u r a t ec l a s s i f i c a t i o nr a t e ，an e wf 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 dw h i c hc o m b i n e st r a c er a t i oc r i t e r i o na n de r r o rr e g i o ns e l e c t i o n ，a n dt h e na d ds o _ n l _ en e wf e a t u r e sw h i c hc a nc o r r e c te r r o r - s a m p l eo n c ei nat i m e f i n a l l yt h ee r r o r - r a t eo fc l a s s i f i e rc a nb ed e c r e a s e de f f i c i e n t l y w r ep r o p o s et w om e t h o d si ne r r o rr e g i o ns e l e c t i o n , o n ei ss f sa n dt h eo t h e ro n ei s + l rs e l e c t i o n 2 a sf o rt h ef e a t u r e r e d u n d a n c y , t h i sa r t i c l ea n a l y s e sf e a t u r e f e a t u r er e l e v a n c ea n df e a t u r e c l a s sr e l e v a n c ei n d e x ，b a s e do nt h er e s e a r c ho fr e l e v a n tf e a t u r es e l e c t i o n ，w ep r o p o s ean e wi m p r o v ea l g o r i t h m u s ek n ns e l e c t i o nt oi m p r o v et r a c er a t i oa l g o r i t h m ，w ef o c u so nt h ef e a t u r e f e a t u r er e l e v a n c et oe l i m i n a t ef e a t u r er e d u n d a n c y , l o w e rt h ed i m e n s i o no fs u b s e tw h i l ec l a s s i f i e rs t i l lk e e ph i g ha c c u r a t e - r a t e w r eu s eu c id a t a b a s e st op r o o fo u ra l g o r i t h ma v a i l a b l e t 1 1 ed a t a b a s e sw ec h o s ea r e0 r l w i n ea n da u s t r a l i a n 3 a r t i c l ea l s od o e sal o to fr e s e a r c ho ni k l i e fa l g o r i t h ma n di t se x t e n da l g o r i t h mr e l i e f f r e l i e fa n dr e l i e f fa r ec l a s s i c a lf i l t e rm o d e lf e a t u r es e l e c t i o n , c l a s s i f i c a t i o nr a t eb a s e do nt h i sm o d e li sn o ts a t i s f i e d w eu s ee r r o rr e g i o nf e a t u r es e l e c t i o nt oi m p r o v er e l i e fa n dr e l i e f fa l g o r i t h mi nt h ef i r s tp l a c e 1 0 w e re r r o r - r a t eo fc l a s s i f i e re m c i e n t l y r e l i e fa n dr e l i e f fa l g o r i t h mf o c u so nf e a t u r e c l a s sr e l e v a n t , s of e a t u r es u b s e tp r o d u c e db yr e l i e fa n dr e l i e f fa r ee f f i c i e n tf o rc l a s s i f y i n g ，b u tt h ef e a t u r es u b s e tm a yh a v er e d u n d a n c y s ot h e nw eu s ek n nm e t h o db a s e do nf e a t u r e f e a t u r er e l e v a n ti n d e xt oi m p r o v er - e l i e fa n dr e l i e f fa l g o r i t h m n e wi m p r o v ea l g o r i t h ml o w e rt h ed i m e n s i o no fs u b s e te f f i c i e n t l yw h i l ec l a s s i f i e rs t i l lh a v eag o o dp e r f o r m o u re x p e r i m e n t sp r o o ft h ea l g o r i t h ma v a i l a b l eb yu c id a t a b a s e s k e y w o r d s ：f e a t u r es e l e c t i o n ；t r a c er a t i oc r i t e r i o n ；f e a t u r er e l e v a n c e ；k n nf e a t u r es e l e c t i o n ；r e l i e ff e a t u r es e l e c t i o ni i目录目录摘要ia b s t r a c t i i第一章绪论11 1 特征选择算法概述及其研究意义11 2 特征选择算法及分类11 2 1 特征选择算法的分类21 2 2 特征选择研究的历史与现状41 3 本文的研究工作51 4 本文研究内容安排6第二章特征选择框架及基本特征选择算法介绍72 1 引言72 2 特征选择各要素分析72 2 1 特征子集的生成72 2 2 特征子集评价- 82 2 3 停止条件92 2 4 结果验证92 3 基本特征选择算法92 3 1 分支定界选择算法_ 1 02 3 2 向前及向后搜索选择算法1 12 3 3 + l - r 搜索算法1 22 4 实验结果与分析：1 42 5 本章小结1 5第三章迹比准则算法及其改进算法1 63 1 引言“1 63 2 迹比准则特征选择算法1 63 2 1 计算特征一级得分的传统特征选择算法1 83 2 2 计算子集一级得分的迹比准则算法1 93 3 基于错分区域的特征选择2 23 3 1 基于错分区域的前向改进算法2 23 3 2 基于错分区域的+ l _ r 改进算法2 63 4 实验结果分析2 73 4 1 迹比算法实验结果与分析2 83 4 2 基于错分区域的前向选择改进迹比算法结果及分析3 13 4 3 基于错分区域的+ l - r 选择改进迹比算法结果及分析3 23 5 本章小结3 4目录第四章基于特征相关性的特征选择算法3 54 1 引言3 54 2 特征的相关性3 54 2 1 特征相关性分析的概念3 54 2 2 特征相关性的分类3 64 2 3 特征之间的冗余问题3 74 3 基于特征相关性的特征选择3 74 4k n n 非搜索特征选择算法3 84 5 基于特征相关性的迹比改进算法4 04 6 改进算法实验结果4 14 7 本章小结4 6第五章r e l i e f 算法及其改进算法研究4 75 1 引言4 75 2r e l i e f 和r e l i e f f 算法4 75 3 基于错分区域的特征选择对r e l i e f 及r e l i e f f 算法的改进4 95 4 基于特征相关性和错分区域选择的双重改进r e l i e f 及r e l i e f f 算法5 05 5 改进算法实验结果：5 25 6 本章小结5 5第六章总结与展望5 66 1 总结，5 66 2 未来的研究课题5 6致谢5 8参考文献5 9附录：作者在攻读硕士学位期间发表的论文6 4i i第一章绪论第章绪论1 1 特征选择算法概述及其研究意义特征选择是模式识别、数据挖掘、机器学习领域中的一项重要技术。随着人工智能、信息化技术、计算机科学的高速发展及广泛应用，模式识别技术在人们的生活中占据的比例逐步增加，越来越多的场合和物品都在应用模式识别技术，比如带有指纹识别的笔记本电脑、互联网应用中的人脸识别技术、通过瞳孔识别的保险箱设计等诸多领域。近几年，特征选择方法得到了较大发展，涌现出很多优秀的特征选择算法，并在实际应用中发挥了巨大的作用。通常测量空间得到的初始样本维度往往非常高，在这样高维的环境下对数据进行训练要花费很长的时间，我们希望通过某些算法能够有效地减少训练时间，其中一种有效的方法就是特征选择。简言之，特征选择就是在原始样本包含的海量特征中选出对分类贡献最大的一组特征，这些特征是最能反映样本本质的一组特征，并且尽可能的去掉数据中的冗余信息和无效特征，最后得到满意的特征子集，借由这组特征子集我们将原始的测量空间转变为特征空间，之后进行训练，让分类器在特征空间上进行分类，大大减少了任务在时间和空间上的消耗。在分类问题中样本属于哪个类取决于样本特征包含的信息，这些特征所提供的信息是否完整，是否有冗余，是否含有和分类十分相关或者说和分类毫不相关的信息都决定了后续分类算法的成功与否。特征子集往往会包含一定程度的特征冗余，冗余信息的产生往往是因为算法忽略了特征间的关联性，因为对于有着强关联的两个特征，只要有一个特征被包含于最终特征子集中就可以很好的起到识别作用，所以特征冗余增加了数据的维度从而降低了算法的效率。随着科技水平的进步，我们获取到的信息数据量越来越大，维度也越来越高，虽然这使得数据直观看来更加清晰，但是对分类器的设计也提出了更高的要求，相应的特征冗余和无关信息也几何倍数的增加了。这就需要有更加优秀、高效的特征选择算法对数据进行处理，最大限度的筛选出对分类最有用的特征，除去冗余和无效特征。选用合适的特征选择算法能够很好的在不影响分类识别率的前提下降低数据的维度，去除冗余和无用信息，大大减少系统运行的时间。由于上述原因特征选择越来越受到人们的关注。1 2 特征选择算法及分类特征选择和特征提取是模式识别领域中最重要的两种降维方法，通过文献 1 】的定义，特征提取( f e a t u r ee x t r a c t i o n ) 是指在输入的特征空间上通过某种变换得到新的特征空间，这种变换方式有很多种，以后在这个空间中选取特定的某些特征作为对样本的描述，特征提取总体上来说是种空间变换技术。特征提取可以和特征选择同时使用，大部分的特征提取算法都是在特征选择算法之前进行的。对于特征提取和特征选择的使用问题上，采用哪种算法，最终还是取决于应用领域和现有训练集的情况。特征提取得到的特征空间可能有着很强的分类能力，但是由原始特征的线性或非线性组合而产生的新的特征失去了原有样本的物理意义。特征选择的优势在于节省了存储空间、减少了采集江南大学硕士学位论文数据的消耗( 有一些特征被去掉而不必测量) ，更重要的是，特征选择保留了被选特征的原始物理意义，这一点对于理解数据的产生和分类模型的结构是非常重要的【l 】。特征选择的定义很多，我们会遇到很多特征选择问题，实际问题的不同，定义的侧重点就不同，我们先看下面几个由d a s h 和l i u 总结定义【2 】【3 】：1 寻找一个对目标概念( t a r g e tc o n c e p t ) 必要和充分的元素个数最小的特征子集1 4 。2 选择一个原始特征集合的特征子集，使得所对应类别的条件概率分布，在只给定所选特征的条件下，和原来给定所有特征条件下的类别的条件概率分布尽可能的接近垆j 。3 在包含d 个特征的集合中选取d 个特征，得到特征子集，d d ) 的一组最优特征。其包括两大方面的问题，一是选择的标准，即在实际问题中什么特征是优秀的特征，比如可以使用前面介绍的可分离判据作为某些算法对特征的评价标准；另一个问题是对特征的选择过程采用何种算法，实际问题要求我们要在可9江南大学硕士学位论文以容许的时间复杂度情况下得到最优的特征子集，时间和空间的花销问题某种意义上讲也是评价一个特征选择算法优劣的指数之一。在d 个特征中挑选d 个特征的所有可能为：g = = 岳( 2 - 1 )如d = 1 0 0 ，d = l o ，则q 的数量级为1 0 1 3 ，可见如果把各种可能的可分离判据值j 都算出来是多么复杂的工程，这种想法是无法实现的。下面我们看几种基本的特征选择算法，这些算法的思想是很多高级算法的理论基础。2 3 1 分支定界选择算法分支定界算法( b r a n c h & b o u n d ) 是一种能够得到最优结果的搜索方法，是一种自上而下的方法，但具有回溯功能，这就保证了子集的最优化。整个搜索过程可用树表示出来，图2 2 为从6 个特征中选择2 个特征的例子，节点处标示的数目为去掉的特征序号。级数表示已去掉的特征数，所以要在6 个特征中选择2 个4 级就够了，点a 表示去掉第2 、3 号特征后的特征组( x l ，x 2 ，x 3 ，x 4 ) 。456566566656666图2 - 2 分支定界算法示意图f i g 2 2e x a m p l eo fb r a n c h & b o u n da l g o r i t h m当算法进行时，有一支已经搜索到底，达到了d d 级，此时计算得到的可分离判据为，g d d ) = b 。此时如果发现树中的一点，比如说a 的可分离判据值为j 。b ，则a以下各点都可以不用再考虑了，因为根据单调性，其后面的节点的j 值都不会大于b ，这其实正是该算法同传统的枚举算法的最大不同之处。在搜索树形成的每一级，我们都进行j 值的计算，对于最右边的一支来说，它总是大于我们所设置的界值，一旦到达叶节点，就用相应的j 值代替原来的界值。到达叶节点后就要向上回溯，在回溯的过程中，每次向上一级回溯时，就把向上回溯时的原来节点所舍弃的特征集合和这个到达的节点所舍弃的特征合并。1 0第二章特征选择框架及基本特征选择算法介绍该算法由于考虑了所有特征组合的情况，因而属于最优搜索算法，其时间和空间的消耗也不是很大，下面给出算法的具体步骤：已知：q = ( 爿+ 1 ，x ：t + l ，x ；1 ) 表示第i 级的当前讨论节点g j 个后继节点所舍弃的特征。j 。表示处于第i 级的当前讨论节点在舍弃掉i 个特征后所具有的特征集，仍表示处于第i 级的当前讨论节点的后继节点可以舍弃的特征集合，表示这个集合中元素的数目。全部过程从0 级开始，从最右边的一支开始计算。1 、计算吼，使用q ，= - ( d - d - i - i ) ；2 、计算q = ( x ：+ 1 ，x ：i + 1 ，砖1 ) ，根据j ( z 一而i “) j ( z z 1 ) s ，( z x 著1 ) j ( z x ? 1 ) ，l + 1 仍( 2 2 )并从鲲中去掉q 及修改，仍+ l = 仍一q+ l2 一吼一3 、和后继节点对应的可分离判据值是否小于界值b ，若q ，= 0 ，则转向步骤5 ；否则，若，( z x ) b ，令，= q ，然后转到步骤4 ，否则从z 中去掉x 形成冠+ l ，即z + 。= z x 2 1 ，若i + l = d - d ，则转到步骤6 ；否则，令i - - i + l ，然后转到步骤1 。4 、栅x q “t 1 放回仍+ l 中，即织+ 1 = 仍+ l + x q “t 1 ，+ i = + l + 1 ，令，= ，一1 ，q f = q j 一1 ，若，= 0 ，则转向步骤3 ，否则重复步骤4 。5 、回溯，令仍= 仍+ l = ，f = i - 1 ，若f _ - 1 ，则终止算法；否则，把x ；1 放入当前特征集，即冠= 冠+ 。+ x ，令z = 1 ，转向步骤46 、修改界值，令b = j ( 磊一) ，k d 为当前最好的特征组，令z = q ，转向步骤4 。但是虽然分支界定法属于最优搜索算法，其还有自身的局限性，虽然只计算一部分的可能组合就得到全局最优子集比枚举算法节省了大量的时间，但是由于除了计算元一d 特征组合之外还要计算所有的毛一，j = 1 , 2 ，d - d ，当实际问题涉及到图像等高维数据时，时间的消耗仍然很大，并且此算法的前提是其可分离判据j 满足单调性，实际问题中可分离判据有时必须用样本去估计，这就可能破坏了单调性，算法无法保证得到最优解。2 3 2 向前及向后搜索选择算法分支界定算法虽然比盲目穷举效率高，但是在有些情况下计算量仍然很大，因而有时候难以实现，大部分时候不得不放弃这种最优算法而选择次优搜索算法以减少计算量。我们下面看两个经典特征选择算法，分别是顺序前进法s f s ( s e q u e n t i a lf o r w a r ds e l e c t i o n ) 和顺序后退法s b s ( s e q u e n t i a lb a c k w a r ds e l e c t i o n ) 。1 、顺序前进法( s e q u e n t i a lf o r w a r ds e l e c t i o n ，s f s ) ，最简单同时也是最基本的自下而上搜索方法，每次从未入选的特征中选择一个特征，使得它与已入选的特征组合在江南大学硕士学位论文一起时所得j 值最大，直到特征数增加到我们选定的d 时。用丘表示特征子集，下面给出算法的具体步骤：1 ) 、初始化x k = x 0 ，随机选择一个特征；2 ) 、未入选的d k 个特征x ，( ，= 1 , 2 ，d 一七) ，计算j ( 砭+ j c l ) j ( 丘- i - x 2 ) j ( 以+ b 一七)( 2 3 )3 ) 、按与已入选特征组合后的j 值大小将序排列，更新以+ l = x k + x l ；直到k = d ；得到最优特征子集x 。我们知道在进行特征选择的时候，特征并不是彼此独立的，特征和特征间会发生相互作用，某些特征本身并不优秀，但是当与特定的特征结合在一起的时候就会发挥其作用；同样有些特征虽然暂时被认为是优秀特征，但是当后续有些特征加入特征子集后，其就会失去作用，也就是我们所说的冗余特征，冗余现象在很多特征选择算法中都有出现。s f s 算法虽然考虑了所选特征与已入选特征之间的相关性，但是对于入选特征，一旦该特征被选入子集就无法被剔除，可能的情况是后续的特征与之前几轮的某一特征会产生冗余，该算法就无法有效的应对这一问题。在数据量不是很大的情况下我们可以采用广义的s f s 算法( g s f s ) 解决这个问题，即每次不只增加一个特征而是增加r 个特征，当然此时每步有c 缸个候补特征组需要逐个计算。2 、顺序后退法( s e q u e n t i a lb a c k w a r ds e l e c t i o n ，s b s ) ，是一种自上而下的方法，从全体特征开始每次剔除一个特征，所剔除的特征应使得仍然保留的特征组的j 值最大，直到特征子集包含的特征数为d 。己知原始样本包含d 个特征，用来保存特征子集的矩阵为冠( 剔除了k 个特征的特征集合) ，算法具体步骤如下：1 ) 、初始化冠= 元；循环：2 ) 、将冠中包含的各特征x ，如下计算：，( 翼r 七一x 1 ) j ( j ，七一x 2 ) j ( 五一x d - k ) ( 2 - 4 )3 ) 、根据以上计算更新冠+ 。= 冠一x ，直到k = d d得到最优特征子集冠，s b s 算法同样有着类似前面s f s 算法的劣势，即特征一旦被剔除就不能加入，再应对某些实际问题时无法得到最优解，我们仍然可以使用广义的s b s 方法( g s b s ) 来处理这一问题，同样面临着计算量大幅增加的问题。2 3 3 + l - r 搜索算法1 2第二章特征选择框架及基本特征选择算法介绍为了避免前面方法存在的问题，即特征一旦被选入( 或剔除) 就不能再剔除( 或选入) 。我们很自然的想到在算法中加入回溯过程。比如说我们做几步s f s 后再对整体做s b s ，也就是说我们加入了l 个特征，此时特征集合包含的特征数为k 斗- l ，之后我们对其进行s b s 操作，去除相对不好的一些特征，进行r 步从k + l 中剔除了r 个特征，此时特征集合包含的特征数为k + l - r 。下面表2 1 给出具体步骤：表2 - 1 + l - r 算法具体步骤t a b l e 2 1p r o c e s so f + l - ra l g o r i t h m输入：用来保存特征子集的冠( 剔除了k 个特征的特征集合)想要得到的特征数d输出：最优特征子集算法步骤：l 、初始化x t = x 0循环循环( s f s )2 、未入选的d k 个特征x j ，( j = 1 ，2 ，d k ) ，计算j ( 置+ j c l ) j ( j + x 2 ) j ( x k + x d 一)3 、按与已入选特征组合后的j 值大小降序排列更新x k + l = x k + 而直到加入了l 个特征k = k + l循环( s b s )4 、将x 。中各特征x ，如下计算j ( x k - x 1 ) j ( 爿i - - x 2 ) j ( j 0 一x d i )5 、根据以上计算更新x k + 1 = 五一而直到剔除了r 个特征k = - k r直到k = d得到最优特征子集以。实际应用中一般采用的是广义的+ l r 算法，即使用g s f s 和g s b s 代替上述算法中的s f s 和s b s 。令厶，江1 , 2 9 0 * o $ - ，t 及r ，= 1 , 2 ，z 詹，具体的就是每次加入特征时不是只加入一个特征，而是加入厶个特征，总共加入l 个特征，再用g s b s 法提出特征，每次剔除r 。个特征。对于分几步加入l 个特征和分几步剔除r 个特征是该算法的关键问题，不同实际情况的要求不一样，无法确定到底要分几步进行，其原则是既要考虑到入选( 或剔除) 特征之间的相关性，又不至于因此引起计算量过大。江南大学硕士学位论文2 4 实验结果与分析我们对本章介绍的几种基本特征选择算法进行了实验比较，包括前向搜索算法( s f s ) 、后向搜索算法( s b s ) 和增l 减r ( + l r ) 算法。对于样本分类来说，类间距离越大，类内距离越小，则类别之间可分离度就越大，我们采用类内类间距离作为评测标准，对水仙花数样本( i r i s ) 和酒类数据样本( w i n e ) 进行试验，观察在特征子集包含的特征数不同的情况下，不同算法得到的特征子集中样本的最优类间类内距离比。样本信息如表2 2 所示：t l b l e2 - 2d a t a s c to fw i n ea n di r i s数据集类别数特征数样本数类另q1类别2类别3w i n e31 35 97 14 8样本数i r i s341 5 0表2 3 给出在w i n e 数据集下三种算法所得到的最优类间类内距离比：表2 - 3w i n e 数据集下+ l - r 、s f s 和s b s 算法效果比较t a b l e2 - 3c o m p a r i s o no f + l - r ，s f sa n ds b su s i n gw i n ed a t a s e t类间类内距离类间类内距离f e a t u r ef e at u l en u m b e r+ l rs f ss b sn u m b e r+ l rs f ss b sl3 6 23 6 23 2 486 4 06 4 56 3 524 7 54 7 54 1 596 7 56 6 16 5 735 3 05 3 04 8 81 06 8 36 7 26 7 845 5 65 5 65 3 91 17 1o6 9 06 9 955 9 25 9 25 7 51 27 107 1 07 1 066 1 26 1 75 6 01 37 1 07 1 07 1 076 3 96 3 86 1 0通过对表2 3 的观察，我们看出+ l r 算法的结果要略优于s f s 和s b s 两者，+ l r算法有效的克服了s f s 和s b s 算法的弊端，在三者比较中得到的类间类内距离比最优。但是就仿真试验的速度上来看，s f s 和s b s 都要优于+ l r ，s f s 和s b s 的运行速度很快，而+ l r 就相对慢一些。表2 4 给出这三种算法在i r i s 数据集下的实验的对比结果，其结果与在w i n e 数据集1 4第二章特征选择框架及基本特征选择算法介绍下进行的实验结果类似，+ l r 算法在性能上优于s f s 和s b s ，而在时间复杂度上则是s f s 和s b s 更加出色。表2 - 4i r i s 数据集下+ l r s f s 和s b s 算法效果比较t a b l e2 - 4c o m p a r i s o n0 f + l r ，s f sa n ds b su s i n gi r i sd a t a s e t类问类内距离类间类内显巨离f e a t u r ef e a t u r en u m b e r+ l rs f s$ b sn u m b e r+ l rs f ss b $l4 7 64 7 64 3 035 3 45 2 65 1 624 9 84 9 94 6 745 4 55 4 55 4 52 5 本章小结本章系统介绍了特征选择框架，对特征选择问题中包含的各个组成部分进行了研究和分析，并基于这个框架对几种经典的特征选择搜索算法和评价标准给出了介绍和归纳。该特征选择框架提出一种特征选择算法包括“特征子集生成”、“特征子集评价”、“停止条件 、“结果验证 四个步骤。之后本章对几种经典的特征选择搜索算法进行了详细的介绍，分别是决策树搜索算法、前向搜索算法、后向搜索算法和+ l - r 搜索算法。随着特征选择算法需求的不断增加，我们需要对新算法和经典算法加以整合，取长补短，针对不同的问题对特征选择算法进行必要的改进。后面章节中我们将使用本章节中介绍的几种基本算法对迹比算法( t r a c er a t i o ) 和r e l i e f 算法等进行改进和结合，总结出新的特征选择算法，更好的解决复杂的特征选择问题。1 5江南大学硕士学位论文3 1 引言第三章迹比准则算法及其改进算法使用迹的比值这一方法进行数据降维最初是在特征提取上应用的【3 4 】，当时由于样本包含的特征个数太大，无法应用在特征选择中，因为特征个数的增加意味着使用这些特征排列组合得到的特征子集的个数更大，逐一计算每个可能的特征子集的优劣要花费大量的时间，所以传统的特征选择方法仅通过计算单个特征的得分来评价特征的优劣，选择得分最高的特征组成特征子集，但是用该方法得到的特征子集并不是最好的，因为有些特征只有组合在一起时才能发挥特征的能量，这就需要我们考虑具体特征子集一级的得分。迹比算法提出一种新的迭代方法直接计算子集一级的得分，由于参加迭代过程的判定标准是子集一级的，所以保证了选出的特征子集为最优特征子集，同时保证了相对理想的时间复杂度。但是迹比算法是典型的f i l t e r 模型特征选择算法，特征选择的过程独立于分类，特征子集包含的信息和后续分类算法的性能有一定的偏差，本章采用一种基于错分区域的特征再选择方法对迹比算法给予有效的改进，并采用o r l 人脸数据集，检测其效果，对比采用不同监督方法时的差别及算法优劣，并分析其性能。3 2 迹比准则特征选择算法假设我们的原始高维数据x r d ，也就是说每个样本包含的特征数是d 。我们的任务是通过一定的准则找到一个最优映射矩阵w r 喇( 通常d ，其中向量i是 l ，2 ，d 的转置。相似的我们定义r v , = w 1 0 ) , w t ( 2 ) ，( 由】，其中的w 和公式( 3 3 )中的形式是一样的。我们的任务就是通过y = w r x 将原始数据集x 降维得到新数据集y 。在许多有关机器学习的研究中，用图来体现数据间的关系是一种常用的方法，也是一种很自然的想法，并且该方法有着很高的效率，比如一些聚类算法、半监督学习、子空间学习等方法。对于特征选择，我们首先基于已知的原始数据构造两个加权无向图瓯，和g 。图瓯反映数据的类内关系，即同一类数据间的紧密程度；g 反映了数据的类间1 6第三章迹比准则算法及其改进算法关系，即不同类别数据间的紧密程度。在实际应用中我们分别用矩阵几和a 。来表示g 。和g 。总的来说，由于矩阵以用来描述数据的类内关系，那么对于毛和x ，属于同一类或者彼此的关系很近时，( a 。) 玎的值就要相对的大，否则，如果毛和x ，分属两类或者数据差别很大，则( 也) 盯的值就相对很小，因此我们在选择特征子集的时候所遵循的一个原则就是使得，l | m - y j1 1 2 l 的值尽可能的小。同样道理，由于矩阵a b 用来描述数据的类间关系，那么对于毛和x ，不属于同一类或者彼此的差别很大，( a 。) 的值就要相对的大，否则，如果_ 和x ，数据同类或者数据关系很近的话，则( ) 盯的值就相对很小，因此我们在选择特征子集的时候所遵循的另一个原则就是使得，i l y 广y 川2 0 。) f 的值尽可能的大。根据以上两条原则，我们的特征子集的评价标准就出来了，形式如下咿端2a阻4 ，即奶) = 焉鞣( 3 - 5 )其中l 和厶为拉普拉斯矩阵( l a p l a c i a n ) ，由l = 仇一以得出，其中仇是对角矩阵形如( 仇) = ，( 凡) ，同理厶= d 6 - a 。，见为对角矩阵( 见) 打= ，( 4 ) 。为了使公式在形式上得到简化，我们定义b = x l b x r r t m d 和e = 甄x r r 执d 则公式( 3 5 ) 的准则可以改写为奶) = 焉锑( 3 - 6 )基于公式( 3 - 5 ) 给出的准则，特征子集( j ) 的得分可以如下计算泐坤) = 焉器( 3 - 7 )对于迹比准则特征选择算法，我们的任务就是找到一组得分最高的特征子集，其具体的数学描述如下州d = 黑锯( 3 - 8 )公式( 3 4 ) 的准则为我们解决特征选择问题给出了判定原则，构造权值矩阵以和4的方法有很多种，不同的构造方法对应着不同的特征选择算法，决定着该算法是有监督学习方法还是半监督学习方法还是无监督学习方法。f i s h e r 得分和l a p l a c i a n 得分是有代表性的两种方法，分别对应着有监督学习和无监督学习。我们之前提到过，根据样本中1 7江南大学硕士学位论文是否含有类别信息，特征选择可分为有监督的特征选择和无监督的特征选择。无监督的特征选择是指在数据集中，通过数据集中特征自身之间的关系进行特征选择的方式；有监督的特征选择是指在给定类别的前提下，利用特征之间的和特征与类别之间的关系对特征集进行选择的过程。在f i s h e r 得分算法中，权值矩阵a 和4 的定义为c 舢= 胃州i fc 盼( i ) = 础c ( ，j )( 3 9 )i 三一上，i fc ( f ) ：c ( 歹( 4 ) 驴= 甩，( 3 1 0 i二，i 7 rc ( i ) c ( ，)l力其中c ( f ) 是每个样本一的类别号，琢是第i 类样本包含的样本个数。在l a p l a c i a n 得分算法中，权值矩阵以和4 的定义为驴一和x j 相邻( 3 11 )其它铲南d w l l 包( 3 - 1 2 )通过上面的公式我们可以看出，f i s h e r 得分用到了类别的信息来构造权值矩阵，所以采用f i s h e r 得分的算法为有监督学习算法，l a p l a c i a n 得分没有用到已知的类别信息，故采用l a p l a c i a n 得分的算法为无监督学习算法。3 2 1 计算特征一级得分的传统特征选择算法在特征数增多的情况下，其组合而成的特征子集的数量是呈几何倍数增长的，如果我们能够考虑到所有特征子集的分类能力，那么我们一定能够找到一个最优的特征子集，但是这样的做法显然是不可取的，实际问题中，比如像o r l 人脸数据集，特征集所包含的特征数往往很大，其组合而成的特征子集数就更是天文数字，所以通常我们不是将每个子集都计算其优劣，而是计算每个特征的得分，选择最好的特征组成特征子集，这就是传统的特征选择算法。基于上面的图像特征选择框架和已知信息，在公式( 3 - 4 ) 的准则下，第i 个特征的得分计算方法如下s c o r 巳( 互) ：萼警( 3 1 3 )w , - 厶由上一小节的介绍及公式( 3 - 4 ) 我们给出基于计算特征一级得分的特征选择算法的步骤：1 8第三章迹比准则算法及其改进算法输入：要选择的特征个数d ，及b r 队d a n d e r 阻d ；输出：最优特征子集。l 、用公式( 3 - 1 3 ) 计算每个特征e 的得分，形式如下：黝( = 舞w酣( f ；1 , 2 3