1. 总述
(1) 什么是特征挑选
特征挑选 ( Feature Selection )也称特征子集挑选( Feature Subset Selection , FSS ) ，或特色挑选( Attribute Selection ) ，是指从悉数特征中选取一个特征子集，使结构出来的模型更好。
(2) 为什么要做特征挑选
在机器学习的实践运用中，特征数量往往较多，其间或许存在不相关的特征，特征之间也或许存在相互依赖，简略导致如下的成果：
特征个数越多，剖析特征、练习模型所需的时刻就越长。
特征个数越多，简略引起“维度灾祸”，模型也会越杂乱，其推行才能会下降。
特征挑选能除掉不相关(irrelevant)或亢余(redundant )的特征，然后到达削减特征个数，进步模型精确度，削减运转时刻的意图。另一方面，选取出真实相关的特征简化了模型，使研究人员易于了解数据发生的进程。
2. 特征挑选进程
2.1 特征挑选的一般进程
特征挑选的一般进程可用图1表明。首要从特征全集中发生出一个特征子集，然后用点评函数对该特征子集进行点评，点评的成果与中止原则进行比较，若点评成果比中止原则好就中止，不然就持续发生下一组特征子集，持续进行特征挑选。选出来的特征子集一般还要验证其有效性。
综上所述，特征挑选进程一般包含发生进程，点评函数，中止原则，验证进程，这4个部分。
(1) 发生进程( Generation Procedure )
发生进程是查找特征子集的进程，担任为点评函数供给特征子集。查找特征子集的进程有多种，将在2.2末节打开介绍。
(2) 点评函数( Evaluation Function )
点评函数是点评一个特征子集好坏程度的一个原则。点评函数将在2.3末节打开介绍。
(3) 中止原则( Stopping Criterion )
中止原则是与点评函数相关的，一般是一个阈值，当点评函数值到达这个阈值后就可中止查找。
(4) 验证进程( Validation Procedure )
在验证数据集上验证选出来的特征子集的有效性。
图1. 特征挑选的进程 ( M. Dash and H. Liu 1997 )
2.2 发生进程
发生进程是查找特征子空间的进程。查找的算法分为彻底查找(Complete)，启发式查找(Heuristic)，随机查找(Random) 3大类，如图2所示。
图2. 发生进程算法分类 ( M. Dash and H. Liu 1997 )
下面临常见的查找算法进行简略介绍。
2.2.1彻底查找
彻底查找分为穷举查找(Exhaustive)与非穷举查找(Non-Exhaustive)两类。
(1) 广度优先查找( Breadth First Search )
算法描绘：广度优先遍历特征子空间。
算法点评：枚举了一切的特征组合，归于穷举查找，时刻杂乱度是O(2n)，实用性不高。
(2)分支限界查找( Branch and Bound )
算法描绘：在穷举查找的基础上参与分支限界。例如：若判定某些分支不或许查找出比当时找到的最优解更优的解，则能够剪掉这些分支。
(3) 定向查找 (Beam Search )
算法描绘：首要挑选N个得分最高的特征作为特征子集，将其参与一个约束最大长度的优先行列，每次从行列中取出得分最高的子集，然后穷举向该子集参与1个特征后发生的一切特搜集，将这些特搜集参与行列。
(4) 最优优先查找 ( Best First Search )
算法描绘：与定向查找相似，仅有的不同点是不约束优先行列的长度。
2.2.2 启发式查找
(1)序列前向挑选( SFS , Sequential Forward Selection )
算法描绘：特征子集X从空集开端，每次挑选一个特征x参与特征子集X，使得特征函数J( X)最优。简略说便是，每次都挑选一个使得点评函数的取值到达最优的特征参与，其实便是一种简略的贪心算法。
算法点评：缺陷是只能参与特征而不能去除特征。例如：特征A彻底依赖于特征B与C，能够以为假如参与了特征B与C则A便是剩余的。假定序列前向挑选算法首要将A参与特搜集，然后又将B与C参与，那么特征子集中就包含了剩余的特征A。
(2)序列后向挑选( SBS , Sequential Backward Selection )
算法描绘：从特征全集O开端，每次从特搜集O中除掉一个特征x，使得除掉特征x后点评函数值到达最优。
算法点评：序列后向挑选与序列前向挑选正好相反，它的缺陷是特征只能去除不能参与。
别的，SFS与SBS都归于贪心算法，简略堕入部分最优值。
(3) 双向查找( BDS , Bidirectional Search )
算法描绘：运用序列前向挑选(SFS)从空集开端，一起运用序列后向挑选(SBS)从全集开端查找，当两者查找到一个相同的特征子集C时中止查找。
双向查找的起点是 。如下图所示，O点代表查找起点，A点代表查找方针。灰色的圆代表单向查找或许的查找规模，绿色的2个圆表明某次双向查找的查找规模，简略证明绿色的面积必定要比灰色的要小。
图2. 双向查找
(4) 增L去R挑选算法 ( LRS , Plus-L Minus-R Selection )
该算法有两种方式:
1> 算法从空集开端，每轮先参与L个特征，然后从中去除R个特征，使得点评函数值最优。( L > R )
2> 算法从全集开端，每轮先去除R个特征，然后参与L个特征，使得点评函数值最优。( L R )
算法点评：增L去R挑选算法结合了序列前向挑选与序列后向挑选思维， L与R的挑选是算法的要害。
(5) 序列起浮挑选( Sequential Floating Selection )
算法描绘：序列起浮挑选由增L去R挑选算法开展而来，该算法与增L去R挑选算法的不同之处在于：序列起浮挑选的L与R不是固定的，而是“起浮”的，也便是会改变的。
序列起浮挑选依据查找方向的不同，有以下两种变种。
1>序列起浮前向挑选( SFFS , Sequential Floating Forward Selection )
算法描绘：从空集开端，每轮在未挑选的特征中挑选一个子集x，使参与子集x后点评函数到达最优，然后在已挑选的特征中挑选子集z，使除掉子集z后点评函数到达最优。
2>序列起浮后向挑选( SFBS , Sequential Floating Backward Selection )
算法描绘：与SFFS相似，不同之处在于SFBS是从全集开端，每轮先除掉特征，然后参与特征。
算法点评：序列起浮挑选结合了序列前向挑选、序列后向挑选、增L去R挑选的特色，并弥补了它们的缺陷。
(6) 决策树( Decision Tree Method , DTM)
算法描绘：在练习样本集上运转C4.5或其他决策树生成算法，待决策树充沛成长后，再在树上运转剪枝算法。则终究决策树各分支处的特征便是选出来的特征子集了。决策树办法一般运用信息增益作为点评函数。
2.2.3 随机算法
(1) 随机发生序列挑选算法(RGSS, Random Generation plus Sequential Selection)
算法描绘：随机发生一个特征子集，然后在该子集上履行SFS与SBS算法。
算法点评：可作为SFS与SBS的弥补，用于跳出部分最优值。
(2) 模拟退火算法( SA, Simulated Annealing )
模拟退火算法可参阅 大白话解析模拟退火算法 。
算法点评：模拟退火必定程度克服了序列查找算法简略堕入部分最优值的缺陷，可是若最优解的区域太小(如所谓的“高尔夫球洞”地势)，则模拟退火难以求解。
(3) 遗传算法( GA, Genetic Algorithms )
遗传算法可参阅 遗传算法入门 。
算法描绘：首要随机发生一批特征子集，并用点评函数给这些特征子集评分，然后经过穿插、骤变等操作繁衍出下一代的特征子集，并且评分越高的特征子集被选中参与繁衍的概率越高。这样经过N代的繁衍和优胜劣汰后，种群中就或许发生了点评函数值最高的特征子集。
随机算法的一起缺陷：依赖于随机因素，有试验成果难以重现。
2.3 点评函数
点评函数的作用是点评发生进程所供给的特征子集的好坏。
点评函数依据其作业原理，首要分为挑选器(Filter)、封装器( Wrapper )两大类。
挑选器经过剖析特征子集内部的特色来衡量其好坏。挑选器一般用作预处理，与分类器的挑选无关。挑选器的原理如下图3：
图3. Filter原理(Ricardo Gutierrez-Osuna 2008 )
封装器实质上是一个分类器，封装器用选取的特征子集对样本集进行分类，分类的精度作为衡量特征子集好坏的规范。封装器的原理如图4所示。
图4. Wrapper原理 (Ricardo Gutierrez-Osuna 2008 )
下面简略介绍常见的点评函数。
(1) 相关性( Correlation)
运用相关性来衡量特征子集的好坏是根据这样一个假定：好的特征子集所包含的特征应该是与分类的相关度较高(相关度高)，而特征之间相关度较低的(亢余度低)。
能够运用线性相关系数(correlation coefficient) 来衡量向量之间线性相关度。
( 2) 间隔 (Distance Metrics )
运用间隔衡量进行特征挑选是根据这样的假定：好的特征子集应该使得归于同一类的样本间隔尽或许小，归于不同类的样本之间的间隔尽或许远。
常用的间隔衡量(相似性衡量)包含欧氏间隔、规范化欧氏间隔、马氏间隔等。
(3) 信息增益( Information Gain )
假定存在离散变量Y，Y中的取值包含{y1，y2，….，ym} ，yi呈现的概率为Pi。则Y的信息熵界说为：
信息熵有如下特性：若调集Y的元素散布越“纯”，则其信息熵越小;若Y散布越“紊乱”，则其信息熵越大。在极点的情况下：若Y只能取一个值，即P1=1，则H(Y)取最小值0;反之若各种取值呈现的概率都持平，即都是1/m，则H(Y)取最大值log2m。
在附加条件另一个变量X，并且知道X=xi后，Y的条件信息熵(Conditional Entropy)表明为：
假定存在特征子集A和特征子集B，分类变量为C，若IG( C|A ) > IG( C|B ) ，则以为选用特征子集A的分类成果比B好，因而倾向于选用特征子集A。
(4)一致性( Consistency )
若样本1与样本2归于不同的分类，但在特征A、 B上的取值彻底相同，那么特征子集{A，B}不应该选作终究的特搜集。
(5)分类器错误率 (Classifier error rate )
运用特定的分类器，用给定的特征子集对样本集进行分类，用分类的精度来衡量特征子集的好坏。
以上5种衡量办法中，相关性、间隔、信息增益、一致性归于挑选器，而分类器错误率归于封装器。
挑选器因为与详细的分类算法无关，因而其在不同的分类算法之间的推行才能较强，并且核算量也较小。而封装器因为在点评的进程中运用了详细的分类算法进行分类，因而其推行到其他分类算法的作用或许较差，并且核算量也较大。
