特征选择综述.docx

特征选择常用算法综述一.什么是特征选择(Featureselection )特征选择也叫特征子集选择 ( FSS , Feature SubsetSelection ) 。是指从已有的M个特征(Feature)中选择N个特征使得系统的特定指标最优化。需要区分特征选择与特征提取。特征提取 ( Feature extraction )是指利用已有的特征计算出一个抽象程度更高的特征集，也指计算得到某个特征的算法。特征提取与特征选择都能降低特征集的维度。 评价函数 ( Objective Function ) ，用于评价一个特征子集的好坏的指标 。这里用符号J ( Y )来表示评价函数，其中Y是一个特征集，J( Y )越大表示特征集Y越好。评价函数根据其实现原理又分为2类，所谓的Filter和Wrapper 。 Filter（筛选器） ： 通过分析特征子集内部的信息来衡量特征子集的好坏，比如特征间相互依赖的程度等 。Filter实质上属于一种无导师学习算法。Wrapper（封装器） ： 这类评价函数是一个分类器，采用特定特征子集对样本集进行分类，根据分类的结果来衡量该特征子集的好坏。Wrapper实质上是一种有导师学习算法。二.为什么要进行特征选择？获取某些特征所需的计算量可能很大，因此倾向于选择较小的特征集特征间的相关性，比如特征A完全依赖于特征B，如果我们已经将特征B选入特征集，那么特征A是否还有必要选入特征集？我认为是不必的。特征集越大，分类器就越复杂，其后果就是推广能力（generalization capability）下降。选择较小的特征集会降低复杂度，可能会提高系统的推广能力。Less is More !三.特征选择算法分类 精确的解决特征子集选择问题是一个指数级的问题。常见特征选择算法可以归为下面3类：第一类：指数算法 ( Exponential algorithms ) 这类算法对特征空间进行穷举搜索（当然也会采用剪枝等优化），搜索出来的特征集对于样本集是最优的。这类算法的时间复杂度是指数级的。第二类：序列算法 ( Sequential algorithms )这类算法实际上是一种贪心算法，算法时间复杂度较低，但是可能会陷入局部最优值，不一定能找到全局最优解。第三类：随机算法 ( Randomized algorithms )随机算法属于一种近似算法，能找出问题的近似最优结。随机算法在近似求解NP完全问题上显示出突出的优势，可尝试用在特征选择上。四.指数算法1. 穷举搜索( Exhaustive Search ) 算法描述：穷举所有满足条件的特征子集，从中选择最优。若不限定选取特征的个数，则特征子集有2M个。算法评价：该算法理论上可以找出最优特征子集，但其复杂度是指数级的，而实际上使用的特征数一般比较多，因而通常是不可取的。2. 分支限界搜索( Branch and Bound )在穷举基础上加上了分支限界，例如可以剪掉不可能搜索出比当前已找到的最优解更优的解的分支。 使用分支限界进行特征选择需要先引入一个单调性假设(monotonicity assumption)：J(Y) R ，算法从空集开始，每轮先加入L个特征，然后从中去除R个特征，使得J(Y)最大。当LR ，算法从全集开始，每轮先去除R个特征，然后加入L个特征，使得J(Y)最大。算法评价：增L去R选择算法结合了序列前向选择与序列后向选择思想， L与R的选择是算法的关键。5. 双向搜索( BDS , Bidirectional Search ) 算法描述：使用序列前向选择(SFS)与序列后向选择(SBS)分别从两端开始搜索，两者搜索到一个相同的特征子集Y才停止搜索。 双向搜索的出发点是O(2*N(k/2) O(Nk)，如下图所示，O点代表搜索起点，A点代表搜索目标。灰色的圆代表单向搜索可能的搜索范围，绿色的2个圆表示某次双向搜索的搜索范围，容易证明绿色的面积必定要比灰色的要小。图1. 双向搜索为了确保序列前向选择与序列后向选择会搜索到相同的子集，需要确保：(1) 被SFS选中的特征SBS就不能去除(2) 被SBS去除的特征SFS就不能选择算法评价：BDS结合了SFS与SBS，其时间复杂度比SFS与SBS小，但是兼有SFS与SBS的缺点。6. 序列浮动选择( Sequential Floating Selection )算法描述：序列浮动选择由增L去R选择算法发展而来，该算法与增L去R选择算法的不同之处在于L与R不是固定的，而是“浮动”的，也就是变化的。序列浮动选择同样有以下两种变种。(1) 序列浮动前向选择( SFFS , Sequential Floating Forward Selection )算法描述：从空集开始，每轮在未加入的特征中选择一个集合x，使得J(Y+x)达到最优，将x加入Y，然后在已选择特征集中选择集合z，使得J(Y-z)达到最优，然后再Y中剔除z。(2)序列浮动后向选择( SFBS , Sequential Floating Backward Selection )算法描述：与SFFS类似，不同之处在于SFBS是从全集开始，每轮先去除特征，然后加入特征。六.随机算法1. 随机产生序列选择算法(RGSS, Random Generation plus Sequential Selection) 算法描述：首先随机产生一个特征子集，然后在该子集上执行SFS与SBS算法。 算法评价：作为SFS与SBS的补充