【概述】

对一个学习任务来说，给定属性集，其中有些属性可能很关键、很有用，另一些属性则可能没什么用，这些属性被称为特征（Features）

在现实的机器学习任务中，获得数据后通常要先进行数据预处理（Data preprocessing）然后再进行模型训练，而特征选择（Feature selection）就是数据预处理中一个重要的过程，其是在给定的特征集合中，选择出相关特征子集的过程

进行特征选择有两个十分重要的原因：

缓解由于特征过多而造成的维数灾难问题
降低学习任务难度

事实上，若能选择出重要的特征，使得后续学习过程仅需在一部分特征上构建模型，这会极大的减缓维数灾难问题，从这一角度来说，特征选择与降维有相似的动机，它们是处理高维数据的两大主流技术

需要注意的是，特征选择的过程必须确保不丢失重要特征，否则在后续学习过程中，会因为重要信息的缺失而无法获得好的性能

对于给定的数据集，若学习任务不同，则相关特征也可能不同，因此对当前学习任务有用的特征，称为相关特征（Relevant feature），而对于当前学习任务无用的特征，则称为无关特征（Irrelevant feature）

还有一类特征被称为冗余特征（Redundant feature），它们所包含的信息能从其他特征中推演出来，在很多时候不起作用，去除它们会减轻学习过程的负担，但有时使用冗余特征会降低学习任务的难度，更确切地说，若某个冗余特征恰好对应了完成学习任务所需的中间概念，那么这个冗余特征就是有益的

欲从初始的特征集合中选取一个包含了所有重要信息的特征子集，若没有任何领域知识作为先验假设，那么只能遍历所有可能的子集

然而这在计算上却是不可行的，因为这样做会遭遇组合爆炸，在特征个数较多的情况下就无法进行

可行的方法是产生一个候选子集（Candidate subset），然后评价出它的好坏，并基于评价结果产生下一个候选子集，再对其进行评价，不断重复这个过程，直到无法找到更好的候选子集为止

显然，这涉及到两个关键环节：

子集搜索（Subset search）：如何根据评价结果获取下一个候选特征子集
子集评价（Subset evaluation）：如何评价候选特征子集的好坏

将特征集的候选子集搜索机制与子集评价机制相结合，即可得到特征选择方法，常见的特征选择方法大致可分为三类：

过滤式（Filter）：先用特征选择过程对初始特征进行过滤，再用过滤后的特征来训练模型
包裹式（Wrapper）：直接将模型的性能作为特征子集的评价准则，换言之，就是为模型选择最有利其性能的特征子集
嵌入式（Embedding）：将特征选择过程与模型训练过程融合，两者在同一个优化过程中完成，即在模型训练过程中自动进行特征选择

【子集搜索】

给定特征集合 $\{f_1,f_2,\cdots,f_d\}$，将每个特征看作一个候选子集，对这 $d$ 个候选单特征子集进行评价

在第一轮中，假定 $\{f_2\}$ 最优，于是将 $\{f_2\}$ 作为第一轮的选定集

在第二轮中，向选定集中加入一个特征，构成 $d-1$ 个包含两个特征的候选子集，假定在这 $d-1$ 个候选两特征子集中 $\{f_2,f_4\}$ 中最优，且优于 $\{f_2\}$，那么将 $\{f_2,f_4\}$ 作为第二轮的选定集

以此类推，直到第 $k+1$ 轮时，这一轮的选定集不如上一轮的选定集，则停止生成候选子集，并将上一轮具有 $k$ 个特征的选定集作为最终候选子集

上述这种逐渐增加相关特征的策略被称为前向搜索（Forward search），类似的，若从完整的特征集合开始，每次尝试去掉一个无关特征，这样逐渐减少特征的策略被称为后向搜索（Backward search）

此外，还可以将前向搜索与后向搜索结合起来，每一轮逐渐增加选定相关特征，同时减少无关特征，这样的策略被称为双向搜索（Bidirectional search）

显然，上述的三种搜索策略都是贪心的，因为它们仅考虑了使本轮的选定集最优，例如第三轮假定选择 $f_5$ 优于 $f_6$，于是选定集为 $\{f_2,f_4,f_5\}$，然而在第四轮却可能是 $\{f_2,f_4,f_5,f_6\}$ 比所有的 $\{f_2,f_4,f_5,f_i\}$ 都更优，但显然，若不进行穷举搜索，这样的问题是无法避免的

【子集评价】

对于每个候选子集，可以基于训练集来计算其信息增益以作为子集评价准则

给定数据集 $D$，假设其样本的特征均是离散型，且具有 $|\mathcal{Y}|$ 种，第 $i$ 类样本所占的比例为 $p_i$，对于特征子集 $A$，假定根据其取值将 $D$ 分为 $V$ 个子集 $\{D_1,D_2,\cdots,D_V\}$，每个子集中的样本在 $A$ 上取值相同，那么即可计算特征子集 $A$ 的信息增益：

$\text{Gain}(A)=\text{Ent}(D)-\sum_{v=1}^V \frac{|D_v|}{|D|}\text{Ent}(D_v)$

其中，$\text{Ent}(D)$ 为 $D$ 的信息熵，即：

$\text{Ent}(D)=\sum_{i=1}^{|\mathcal{Y}|} p_i\log_2 p_i$

信息增益 $\text{Gain}(A)$ 越大，意味着特征子集 $A$ 包含的有助于分类的信息越多

更一般的来说，特征子集 $A$ 实际上确定了对数据集 $D$ 的一个划分，每个划分区域对应着 $A$ 上的一个取值，而样本标签 $Y$ 则对应着对 $D$ 的真实划分，通过估算这两个划分的差异，就能对 $A$ 进行评价，与 $Y$ 对应的划分的差异越小，则说明 $A$ 越好

信息熵仅是判断这个差异的一种途径，其他能判断这两种划分差异的机制，均能用于特征子集评价