另外一种降低模型复杂度从而解决过拟合问题的方法是通过特征选择进行降维（dimensionality reduction），该方法对未经正则化处理的模型特别有效。降维技术主要分为两个大类：特征选择和特征提取。通过特征选择，我们可以选出原始特征的一个子集。而在特征提取中，通过对现有的特征信息进行推演，构造出一个新的特征子空间。在本节，我们将着眼于一些经典的特征选择算法。第5章会介绍几种特征抽取技术，以将数据集压缩到低维的特征子空间。
序列特征选择算法系一种贪婪搜索算法，用于将原始的d维特征空间压缩到一个k维特征子空间，其中k<d。使用特征选择算法出于以下考虑：能够剔除不相关特征或噪声，自动选出与问题最相关的特征子集，从而提高计算效率或是降低模型的泛化误差。这在模型不支持正则化时尤为有效。一个经典的序列特征选择算法是序列后向选择算法（Sequential Backward Selection，SBS），其目的是在分类性能衰减最小的约束下，降低原始特征空间上的数据维度，以提高计算效率。在某些情况下，SBS甚至可以在模型面临过拟合问题时提高模型的预测能力。
与穷举搜索算法相比，贪心算法可以在组合搜索的各阶段找到一个局部最优选择，进而得到待解决问题的次优解。不过在实际应用中，由于巨大的计算成本，往往使得穷举搜索算法方法不可行，而贪心算法则可以找到不那么复杂，且计算效率更高的解决方案。
SBS算法背后的理念非常简单：SBS依次从特征集合中删除某些特征，直到新的特征子空间包含指定数量的特征。为了确定每一步中所需删除的特征，我们定义一个需要最小化的标准衡量函数J。该函数的计算准则是：比较判定分类器的性能在删除某个特定特征前后的差异。由此，每一步中待删除的特征，就是那些能够使得标准衡量函数值尽可能大的特征，或者更直观地说：每一步中特征被删除后，所引起的模型性能损失最小。基于上述对SBS的定义，我们可以将算法总结为四个简单的步骤：
1）设k＝d进行算法初始化，其中d是特征空间Xd的维度。
2）定义x-为满足标准x-＝argmaxJ（Xk-x）最大化的特征，其中x∈Xk。
3）将特征x-从特征集中删除：Xk-1＝Xk-x-，k＝k-1。
4）如果k等于目标特征数量，算法终止，否则跳转到第2步。
如果想更多了解序列特征选择算法的相关问题，请参阅文献：Comparative Study of Techniques for Large Scale Feature Selection,F.Ferri,P.Pudil,M.Hatef,and J.Kittler.Comparative study of techniques for large-scale feature selection.Pattern Recognition in Practice IV,pages 403——413，1994。
遗憾的是，scikit-learn中并没有实现SBS算法。不过它相当简单，我们可以使用Python来实现：
在前面的实现中，我们使用参数k_features来指定需返回的特征数量。默认情况下，我们使用scikit-learn中的accuracy_score去衡量分类器的模型和评估器在特征空间上的性能。在fit方法的while循环中，通过itertools.combination函数创建的特征子集循环地进行评估和删减，直到特征子集达到预期维度。在每次迭代中，基于内部测试数据集X_test创建的self.scors_列表存储了最优特征子集的准确度分值。后续我们将使用这些分值来对结果做出评价。最终特征子集的列标被赋值给self.indices_，我们可以通过transform方法返回由选定特征列构成的一个新数组。请注意，我们没有在fit方法中明确地计算评价标准，而只是简单地删除了那些没有包含在最优特征子集中的特征。
现在，来看一下我们实现的SBS应用于scikit-learn中KNN分类器的效果：
在SBS的实现中，已经在fit函数内将数据集划分为测试数据集和训练数据集，我们依旧将训练数据集X_train输入到算法中。SBS的fit方法将建立一个新的训练子集用于测试（验证）和训练，这也是为什么这里的测试数据集被称为验证数据集的原因。这也是一种避免原始测试数据集变成训练数据集的必要方法。
我们的SBS算法在每一步中都存储了最优特征子集的分值，下面进入代码实现中更为精彩的部分：绘制出KNN分类器的分类准确率，准确率数值是在验证数据集上计算得出的。代码如下：
通过下图可以看到：当我们减少了特征的数量后，KNN分类器在验证数据集上的准确率提高了，这可能归因于在第3章中介绍KNN算法时讨论过的“维度灾难”。此外，图中还显示，当k＝{5，6，7，8，9，10}时，算法可以达到百分之百的准确率。
为了满足一下自己的好奇心，现在让我们看一下是哪五个特征在验证数据集上有如此好的表现：
使用上述代码，我们从sb.subsets_的第9列中获取了五个特征子集的列标，并通过以pandas的DataFrame格式存储的葡萄酒数据对应的索引中提取到了相应的特征名称。
下面我们验证一下KNN分类器在原始测试集上的表现：
在上述代码中，我们在训练数据集上使用了所有的特征并得到了大约为98.4%的准确率。不过，在测试数据集上的准确率稍低（约为94.4%），此指标暗示模型稍有过拟合。现在让我们在选定的五个特征集上看一下KNN的性能：
当特征数量不及葡萄酒数据集原始特征数量的一半时，在测试数据集上的预测准确率提高了两个百分点。同时，通过测试数据集（约为96.3%）和训练数据集（约为96.0%）上准确率之间的微小差别可以发现，过拟合现象得以缓解。
scikit-learn中的特征选择算法
scikti-learn提供了许多其他的特征选择算法，包括：基于特征权重的递归后向消除算法（recursive backward elimination based on feature weights）、基于特征重要性的特征选择树方法（tree-based methods to select features by importance），以及单变量统计测试（univariate statistical tests）。对特征选择方法进行更深入的讨论已经超出了本书的范围，对这些算法的总结性描述及其示例请参见链接：http://scikit-learn.org/stable/modules/feature_selection.html。