[理学]第七章_特征选择ppt课件

1、特征选择特征选择2022-3-26主要内容主要内容引言基于互信息的特征选择方法选取策略2022-3-26引言引言Thousands to millions of low Thousands to millions of low level featureslevel features: select the most relevant one to build better, better, faster, and easierfaster, and easier to understandto understand learning machines.Xnmn2022-3-26引言引言续续

2、Male/female classification1450 images 1000 train, 450 test, 5100 features images 60 x85 pixelsR.G.Bachrach,A.Navot,andN.Tishby,“MarginBasedFeatureSelection-TheoryandAlgorithms,ICML04Relief:Simba:10050010002022-3-26引言引言续续Univariate methodUnivariate method: considers one variable feature at a time.Mul

3、tivariate method:Multivariate method: considers subsets of variables features together.Filter method:Filter method: ranks features or feature subsets independently of the predictor classifier.Wrapper method:Wrapper method: uses a classifier to assess features or feature subsets.2022-3-26引言引言续续Allfea

4、turesFilterFeaturesubsetPredictorAllfeaturesWrapperMultipleFeaturesubsetsPredictor2022-3-26基于互信息的特征选择方法n 离散情况：离散情况：Shannon熵：熵：条件熵：条件熵：互信息：互信息：2022-3-26基于互信息的特征选择方法续互信息的估计方法：直方图法直方图法 R.Nattiti,“Usingmutualinformationforselectingfeaturesinsupervisedneuralnetlearning,IEEETrans.NeuralNetworks,vol.5,no.4

5、,pp.537-550,Jul.1994.Parzen窗法窗法 N.Kwak,C.-H.Choi,“InputfeatureselectionbymutualinformationbasedonParzenwindow,IEEETrans.PatternAnalysisandMachineIntelligence,vol.24,no.12,pp.1667-1671,Dec.2002.2022-3-26基于互信息的特征选择方法续 -直方图法 离散型随机变量的估计： 连续型随机变量的估计：Bin箱柜:2022-3-26基于互信息的特征选择方法续 -直方图法续Bin:nb =numberofsamp

6、lesfallinginbin b 2022-3-26基于互信息的特征选择方法续 -直方图法续熵：熵：条件熵：条件熵：结合熵：结合熵：互信息：互信息：缺点：缺点：bin的个数多少最为适宜？2022-3-26基于互信息的特征选择方法续 -Parzen窗法给定N个样本 ，共有NC个类别标号，对于第c类样本而言，其条件概率密度可以由下式估计得到：其中Jc为c的出现次数，Ic为属于第c类的输入向量构成的集合， 为第c类样本的协方差矩阵。2022-3-26基于互信息的特征选择方法续 -Parzen窗法续高斯窗函数：h为窗函数参数：2022-3-26基于互信息的特征选择方法续 -Parzen窗法续2022

7、-3-26基于互信息的特征选择方法续 -Parzen窗法续2022-3-26基于互信息的特征选择方法续 -Parzen窗法+Renyi熵12121212,G xxG xxdxG xx 用Parzen窗估计的概率密度函数来计算HSX是不可行的用HR2Quadratic Entropy代替HS()( )log( ), MSHXfxfx dxxR 2222112211( )log( )11log(,)(,)1log(,2)RNNijijNNijijHXfx dxG xxIG xxI dxNNG xxIN在最大小化信息熵的准那么下，在最大小化信息熵的准那么下，Shannon熵和熵和Renyi熵是等价熵

8、是等价的的2022-3-26基于互信息的特征选择方法续 -Parzen窗法+Renyi熵续(, )( )(|)I X YH YH Y X( )( )log( )SYYHYfyfy dy |(|)( )( | )log( | )SXY XY XxHY Xfxfy xfy x dy dx ( , )(, )( , )log( )( )XYSXYXYfx yIX Yfx ydxdyfx fy2022-3-26基于互信息的特征选择方法续 -Parzen窗法+Renyi熵续Kullback-Leibler KL 散度Cauchy-Schwartz CS 散度 ( )(,)( ) log( )fxKfgf

9、xdxg x( ,)(,)( ,)log( )( )( ,),( )( )xySxyxyxyxyfx yIX Yfx ydxdyfx fyKL fx yfx fy222( )( )( , )log( ) ( )CSfx dxgx dxIf gf x g x dx2222( , )( )( )( , )log( , )( )( )XYXYCSXYXYfx y dxdyfx fy dxdyIX Yfx y fx fy dxdy2022-3-26基于互信息的特征选择方法续 -Parzen窗法+Renyi熵续2211( , )(,) (,)NXYiiifx yG xxI G yyIN211( )(,)

10、NXiifxG xxIN211( )(,)NYiifyG yyIN2022-3-26基于互信息的特征选择方法续 -Parzen窗法+Renyi熵续 CS-QMI222( , )( )( )2(, )logx yxyCSxyVVVIX YV2222( , )111(,2) (,2)NNijijx yijVG xxI G yyIN222( )1(,2)NNijxijVG xxIN2231(,2) (,2)NNNxyijikijkVG xxI G yxIN2022-3-26选取策略选取策略11. ,.,.,.,.,jminiiif selectionffffff 1,.,;1,.,;,1,.,jab

11、injmiiab a bmFF2022-3-26选取策略选取策略N个特征，2N个可能的特征子集!2022-3-26选取策略选取策略续续n 全局最优搜索 分支定界法Branch and Bound思路：思路： 定义一个评价函数，该评价函数必须满足单调性条件，即对两个子集S1和S2，假如S1是S2的子集，那么S1所对应的评价函数必须小于S2所对应的评价函数值。树根是所有特征的集合，从树根往下，树的每级分支都舍弃一个特征，而后根据可分性判据值和事先定义的最正确特征子集的特征数目，搜索满足条件的特征子集2022-3-26选取策略选取策略续续分支定界法的缺点：分支定界法的缺点：由于该算法无法对所有的特征

12、根据其重要性进展排序，如何事先确定优化特征子集当中特征的数目就成了一个很大的问题，该问题影响到算法的求解规模；符合问题要求的满足单调性的可分判据很难设计，这里的符合问题要求指可以让最后选择出的特征子集符合决策的要求，获得较高的决策正确率；1. 当处理高维度多类问题时，算法要运行屡次，算法运算效率低下的问题将非常明显。2022-3-26选取策略选取策略续续n 采用随机搜索策略的特征选择算法 模拟退火算法、禁忌搜索算法、遗传算 法、随机重采样算法Bootstrap问题：问题：大量的时间消耗；1. 假如在该类算法中采用的是统计得分的方式，那么仅能对所有特征的重要性进展排序，很难确定一个最优的特征子集

13、。2022-3-26选取策略选取策略续续n 采用启发式的特征选择算法8种单独最优特征组合：单独最优特征组合： 该方法依靠计算各特征单独使用时的数据值对特征排队，取前d个特征作为满足条件的特征组。缺点：缺点： 仅当单个特征的数据值满足加和性或乘性条件时才能选择出一组最优的特征； 大多数情况下，该算法甚至可能取到最差的特征组合。2022-3-26选取策略选取策略续续n 采用启发式的特征选择算法8种序列前向选择方法序列前向选择方法SequentialForwardSelection： 也称为集合增加法，它是自下而上的搜索方法，先把所需要的特征集合初始化为一个空集，每次向特征集合中增加一个特征，当所需

14、要的特征集合到达要求时所得到的特征集合作为算法运行的结果。缺点：缺点：特征之间的统计相关性没有得到充分的考虑，从这个角度出发的搜索方式仅能合适一小部分满足特殊条件的特征集合。2022-3-26选取策略选取策略续续n 采用启发式的特征选择算法8种广义序列前向选择方法广义序列前向选择方法GeneralizedSequentialForwardSelection： 该方法是SFS方法的加速方法，它可以根据准那么函数一次性向特征集合中增加r个特征。也就是在没有入选优化特征子集的剩余特征集中，寻找一个规模为r的小特征集Yr，使得JXd1+Yr最大缺点：缺点：该方法相对于SFS在特征统计相关性上要稍好些，

15、但是计算量相对SFS增大许多，且在SFS中出现的问题照旧难以防止。2022-3-26选取策略选取策略续续n 采用启发式的特征选择算法8种序列后向选择方法序列后向选择方法SequentialBackwardSelection： 它是自上而下的搜索方法，该方法在运行之初假定整个特征集合就是所需要的优化特征集，而后在算法的每步运行过程中删除一个对准那么函数毫无奉献的特征，直到剩余特征个数符合集合基数要求。缺点：缺点：相对于SFS计算量大。优点：优点：充分考虑特征之间的统计相关特性，因此在采用同样合理的准那么函数的时候，它的实际计算性能和算法的鲁棒性要大大优于SFS算法。2022-3-26选取策略选取

16、策略续续n 采用启发式的特征选择算法8种广义序列后向选择方法广义序列后向选择方法GeneralizedSequentialBackwardSelection： 该方法是SBS方法的加速方法，它根据准那么函数在算法的每次循环当中，一次性删除特征一定个数的无用特征。它是一种可应用于实际过程的快速特征选择方法优点：优点：速度较快，性能相对较好。缺点：缺点：特征消除操作进展太快，容易丧失重要的变量，导致找不到最优的特征组。2022-3-26选取策略选取策略续续n 采用启发式的特征选择算法8种增增l去去r选择方法：选择方法： 该方法允许在特征选择过程中进展回溯，假如lr，那么该算法是自下而上的方法，用S

17、FS方法将l个特征参加到当前特征集中，然后再用SBS方法删除r个最差的特征，这种方法消除嵌套问题，因为某一步获得的特征集不一定是下一步特征集的子集，假如lr，那么算法为自上而下的方法，从一个完好特征集开场，依次删除r个特征，再增加l个特征直到获得满足条件个数的特征。 该方法实际上是SBS和SFS方法的一种折衷，他的运算速度比SBS快，运算效果比SFS好。2022-3-26选取策略选取策略续续n 采用启发式的特征选择算法8种广义增广义增l去去r选择方法：选择方法： 该方法在增l去r选择方法的根底上，用GSFS和GSBS分别代替SFS和SBS。 前面讨论过的所有算法都可以看作它的特例。因此它包含极其广泛的理论意义。缺点：缺点： 操作极为复杂，难以制定实际规那么加以利用。2022-3-26选取策略选取策略续续n 采用启发式的特征选择算法8种浮动搜索方法：浮动搜索方法： 该方法改变上述一系列算法固定l、r