2.1　包裹法Warpper

包裹法采用的是搜索特征子集的办法，基本思路是从初始特征集中不断地选择子集合，根据学习器的性能来对子集进行评价，直到选择出最佳的子集。在搜索过程中，我们会对每个子集做建模和训练，如图2.1所示。

基于此，包裹法很大程度上变成了一个搜索的算法问题：搜索一个合适的特征子集（subset search）。在特征极少的时候，我们可以使用穷举（Brute-Force Search），遍历所有可能的子集，找出能够使得泛化性能最佳的特征子集，但是特征一旦增多，就会遇到组合爆炸，在计算上并不可行（若有N个特征，则子集会有2N-1个）。

定理2.1（贪心算法Greedy Algorithm）　如果一个任务可以拆解成若干的子任务，贪心算法是指在每一步都采取最优的选择，在局部最优解可以决定全局最优的情形下，贪心算法是最有效的算法之一，如果局部最优无法代表全局最优，贪心算法在某些情况下也可以得到近似结果。

图2.1　搜索算法找出特征子集，将特征子集进行性能评估再反馈给搜索算法，直到触发中止条件（示意图来源https://jtapiafarias.wordpress.com/about/）

所以在实际应用中我们会使用贪心算法，每次都选择最优的特征子集，以确保得到一个尽可能好的结果。贪心框架下常见的策略有：

（1）前向搜索（Forward Search）：在开始时，我们按照特征数来划分子集并进行评价，每个子集只有一个特征。然后在最优的子集上逐步增加特征，使模型性能提升最大，直到增加特征并不能使模型性能提升为止。

（2）后向搜索（Backward Search）：在开始时，我们将特征集合分别减去一个特征作为子集，每个子集有N-1个特征，对每个子集进行评价。然后在最优的子集上逐步减少特征，使得模型性能提升最大，直到减少特征并不能使模型性能提升为止。

（3）双向搜索（Bidirectional Search）：将前向搜索和后向搜索结合起来。

由于线性模型有着较好的可解释性，我们可以简单地通过每个特征的权重系数来判断特征的重要程度，然后减去若干低权重的特征，继续进行训练，直到达到我们想要的特征数。这种方法叫作特征递归消除（recursive feature elimination），我们将在代码示例中使用它。