机器学习特征选择常用算法
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 )
该算法有两种形式:
算法从空集开始，每轮先加入l个特征，然后从中去除r个特征，使得评价函数值最优。( l > r )
算法从全集开始，每轮先去除r个特征，然后加入l个特征，使得评价函数值最优。( l ig( c|b ) ，则认为选用特征子集a的分类结果比b好，因此倾向于选用特征子集a。
(4)一致性( consistency )
若样本1与样本2属于不同的分类，但在特征a、 b上的取值完全一样，那么特征子集{a，b}不应该选作最终的特征集。
(5)分类器错误率 (classifier error rate )
使用特定的分类器，用给定的特征子集对样本集进行分类，用分类的精度来衡量特征子集的好坏。
以上5种度量方法中，相关性、距离、信息增益、一致性属于筛选器，而分类器错误率属于封装器。
筛选器由于与具体的分类算法无关，因此其在不同的分类算法之间的推广能力较强，而且计算量也较小。而封装器由于在评价的过程中应用了具体的分类算法进行分类，因此其推广到其他分类算法的效果可能较差，而且计算量也较大。
墨粉
MIPS CPU多线程技术解析
美国金融监管局表示区块链技术为各种工业应用提供了潜力
移动机器人视觉定位方法的研究
非隔离型降压式电源设计分析
机器学习特征选择常用算法
浅析重锤式料位计常见故障及产生的原因
机器人伴侣正在降临人间,2045年人类将有可能与机器人结婚？
如何实现电子密码锁的设计
RFID超高频在服装行业的信息化管理
这摄像头略moto 乐视Pro3双摄AI版发布
基于微控制器的DS28E40解决方案
zircon微内核启动代码分析
新区企业拥抱“智造”引入物联网请来机器人
iPhone8手机将携手这款iPad登陆，满屏占比OLED屏
顺造双速冲击钻上架小米有品 售价249元
新海马S5到底如何？真的逆袭了吗？
激光+焦点监控技术在AR/VR眼镜焊接中的应用
纽约提出用无人机检查检筑物质量，想实现得修改法律
Linus Torvalds：Linux内核、社区多元化和开发者的未来
特征选择 ( 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 )
该算法有两种形式:
算法从空集开始，每轮先加入l个特征，然后从中去除r个特征，使得评价函数值最优。( l > r )
算法从全集开始，每轮先去除r个特征，然后加入l个特征，使得评价函数值最优。( l ig( c|b ) ，则认为选用特征子集a的分类结果比b好，因此倾向于选用特征子集a。
(4)一致性( consistency )
若样本1与样本2属于不同的分类，但在特征a、 b上的取值完全一样，那么特征子集{a，b}不应该选作最终的特征集。
(5)分类器错误率 (classifier error rate )
使用特定的分类器，用给定的特征子集对样本集进行分类，用分类的精度来衡量特征子集的好坏。
以上5种度量方法中，相关性、距离、信息增益、一致性属于筛选器，而分类器错误率属于封装器。
筛选器由于与具体的分类算法无关，因此其在不同的分类算法之间的推广能力较强，而且计算量也较小。而封装器由于在评价的过程中应用了具体的分类算法进行分类，因此其推广到其他分类算法的效果可能较差，而且计算量也较大。
墨粉
MIPS CPU多线程技术解析
美国金融监管局表示区块链技术为各种工业应用提供了潜力
移动机器人视觉定位方法的研究
非隔离型降压式电源设计分析
机器学习特征选择常用算法
浅析重锤式料位计常见故障及产生的原因
机器人伴侣正在降临人间,2045年人类将有可能与机器人结婚？
如何实现电子密码锁的设计
RFID超高频在服装行业的信息化管理
这摄像头略moto 乐视Pro3双摄AI版发布
基于微控制器的DS28E40解决方案
zircon微内核启动代码分析
新区企业拥抱“智造”引入物联网请来机器人
iPhone8手机将携手这款iPad登陆，满屏占比OLED屏
顺造双速冲击钻上架小米有品 售价249元
新海马S5到底如何？真的逆袭了吗？
激光+焦点监控技术在AR/VR眼镜焊接中的应用
纽约提出用无人机检查检筑物质量，想实现得修改法律
Linus Torvalds：Linux内核、社区多元化和开发者的未来