文档介绍：特征选择常用算法综述Postedon2011・01・0214:40苍梧阅读(11252)评论(11)编辑收藏1综述什么是特征选择特征选择(FeatureSelection)也称特征子集选择(FeatureSubsetSelection,FSS),或属性选AttributeSelection),是指从全部特征屮选取一个特征子集,使构造出来的模型更好。为什么要做特征选择在机器学****的实际应用屮,特征数量往往较多,其屮可能存在不相关的特征,特征之间也可能存在相互依赖,容易导致如下的后果:<!supportLists]-->>特征个数越多,分析特征、训练模型所需的吋间就越长。v!・・[if!supportLists]-->>特征个数越多,容易引起"维度灾难”,模型也会越复杂,其推广能力会下降。特征选择能剔除不相关(irrelevant)fiJc亢叙redundant)的特征,从而达到减少特征个数,提高模型精确度,减少运行时间的FI的。另一方面,选取出真正相关的特征简化了模型,使研究人员易于理解数据产生的过程。。首先从特征全集屮产生出一个特征子集,然后用评价函数对该特征子集进行评价,评价的结果与停止准则进行比较,若评价结果比停止准则好就停止,否则就继续产生下一组特征子集,继续进行特征选择。选出来的特征子集一般还要验证其有效性。综上所述,特征选择过程一般包括产生过程,评价函数,停止准则,验证过程,这4个部分。产生过程(GenerationProcedure)产生过程是搜索特征子集的过程,负责为评价函数提供特征子集。搜索特征子集的过程有多种,。评价函数(EvaluationFunction)评价函数是评价一个特征子集好坏程度的一个准则。。⑶停止准则(StoppingCriterion)停止准则是与评价函数相关的,一般是一个阈值,半评价函数值达到这个阈值后就可停止搜索。⑷验证过程(ValidationProcedure)在验证数据集上验证选出来的特征子集的有效性。()。plete),启发式搜索(Heuristic),随机搜索(Random)3人类,如图2所示。pleteExhaustive/\Non・ExhaustiveBestBeamHirstSearchForward bined Instance*Selection SelectionF/B BasedTypeITypeIIBreadthHrxlBranch&&b」M)(bfk)(bs)PQSS fReliefBDS IRelieGFMooc94Jv '()下面对常见的搜索算法进行简单介绍。(Exhaustive)与非穷举搜索(Non-Exhaustive)W类。广度优先搜索(BreadthFirstSearch)算法描述:广度优先遍历特征子空间。算法评价:枚举了所有的特征组合,属于穷举搜索,吋间复杂度是0(2)实用性不高。分支限界搜索(BranchandBound)算法描述:在穷举搜索的基础上加入分支限界。例如:若断定某些分支不可能搜索出比为前找到的最优解更优的解,则可以剪掉这些分支。(3)定向搜索(BeamSearch)算法描述:首先选择N个得分最高的特征作为特征子集,将其加入一•个限制最大长度的优先队列,每次从队列小取出得分最高的子集,然后穷举向该子集加入1个特征后产生的所有特征集,将这些特征集加入队列。⑷最优优先搜索(BestFirstSearch)算法描述:与定向搜索类似,唯一的不同点是不限制优先队列的长度。⑴序列前向选择(SFS,SequentialForwardSelection)算法描述:特征子集X从空集开始,每次选择一个特征x加入特征子集X,使得特征函数J(X)最优。简单说就是,每次都选择-•个使得评价函数的取值达到最优的特征加入,其实就是一种简单的贪心算法。算法评价:缺点是只能加入特征而不能去除特征。例如:特征A完全依赖于特征B与C,可以认为如果加入了特征B与C则A就是多余的。假设序列前向选择算法首先将A加入特征集,然后又将B与C加入,那么特征子集小就包含了多余的特征A。(2)序列后向选择(SBS,Sequential