特征选择是机器学习非常重要的一环。之所以要考虑特征选择，是因为机器学习经常面临过拟合的问题。
过拟合的表现是模型参数太贴合训练集数据，模型在训练集上效果很好而在测试集上表现不好，也就是在高方差。简言之模型的泛化能力差。过拟合的原因是模型对于训练集数据来说太复杂，要解决过拟合问题，一般考虑如下方法：
- 收集更多数据
- 通过正则化引入对复杂度的惩罚
- 选择更少参数的简单模型
- 对数据降维
其中第1条一般是很难做到的，这篇我们主要梳理第2和第4点
通过正则化：
对于参数模型（parametric model），最简单直接的方法是L1正则化来降维。参数模型是什么？是可由公式表达的、有或
参数的模型。这种模型在训练集上学习得到一个公式表达式，对于新的测试数据，可以直接由表达式算出预测结果，预测的时候不再需要训练集。参数模型的代表有逻辑回归，线性回归，神经网络等。正则化分为L1和L2， L1用L1范数最小化代价函数的SSE，可以把某些特征压缩到0，相当于特征选择了。而L2用L2范数最小化代价函数的SSE，只能把某些特征压缩到很小的值，但不可能是0。
对于非参数模型(nonparametric model) ， 很有用的办法是通过特征选择来降维。
降维有两种方式：特征选择和特征抽取。特征选择是直接选特征子集（本篇写的是特征选择）。特征抽取是把特征映射到低维空间（PCA是代表之一，在另一篇里已经写过了）。
特征选择有三个层面的方法：这里分别介绍。
-
Wrapper方法。属于Wrapper的还有exhaustive search BFS (Breadth First Search), Non-exhaustive search (Branch and Bound Search), heuristic search(SFS, SBS, SDS), Random Search (RGSS) . 总体来讲，Wrapper的实现原理是：基于hold-out方法，对于每一个待选的特征子集，都在训练集上训练一遍模型，然后在测试集上根据误差大小选择出特征子集。
这里重点写heuristic search(SFS, SBS, SDS)里的SBS。 heuristic search一般也被称为Sequential feature selection。这是一种贪婪搜索算法，可以将d维数据筛选到k维。它可以去除无关的特征或嗓音，保留对目标最有用的特征， 它的目标就是减少误差（模型方差），它其中又以Sequential Backward Selection(SBS)为代表。
SBS的工作原理是：从特征全集里逐个去除单个特征，直至剩余的特征子集达到期望的维度。那么如何逐个去除呢？我们先定义一个标准函数J，借助J的变化来判断每一步应该去除哪个特征。一般而言，J就是模型的代价函数，这里记住我们降维的最终目标是让代价函数最优（最小化）。所以最简单的方法可以是：，我们用作为判断标准，每一步的时候哪个特征让这个标准最大化，我们就去除哪个标准。或者可以这样理解，我们在每一步时选择去掉的是最不会导致模型变更差的那个特征。
但是SBS在SKLEARN里没有现成的包。这里给出伪代码：
Screen Shot 2018-09-05 at 10.19.28 AM.png Embedded 方法
故名思义，Embedded是指特征选择算法是学习算法的一部分，已经被整合进学习算法里了。最具代表性的如决策树算法，因为它本身就是基于信息增益的一种算法，一个特征里包括的同一分类的孩子节点越多，这个特征就越显著（白种人里有美英法意等等，黄种人里有中日韩等等，人的分类可以根据肤色往下细分。所以肤色就是决策树首先考虑的一个显著特征）。所以，决策树本身的生成就是在做特征选择。决策树有ID3, C4.5, CART树。其中ID3只用于连续型变量，C4.5和CART树可以用于连续变量也可以用于分类变量。Filter方法
就是对特征打分，再根据阈值选择特征。Filter方法独立于模型本身，它的结果比Wrapper方法更有普适性，计算性能好于Wrapper，所以有时候它被用于Wrapper方法之前的预处理。
Filter方法包括：distance metrics, correlation, mutual information, and consistency metrics
其中correlation方法是计算特征之间的独立性。通常用皮尔逊相关系数为指标。mutual information比correlation更有普适性，它描述了p(x,y)和p(x)*p(y)有多么相关。consistency metrics通常用卡方检验，其思想是找出和预测目标不相关的特征，所以其过程是计算每个特征和预测目标的卡方统计量。
福利：
贪婪搜索算法（greedy search）是局部最优算法。与之对应的是穷举算法 (exhaustive search)，穷举算法是遍历所有可能的组合达到全局最优级，但是计算复杂度是2^n，一般是不太实际的算法。
