1、子集搜索与评价

特征选择的难点在于现有特征集合的子集数量关于特征是指数增长的，因此会有组合爆炸的问题。因此我们只能利用贪心的思想来产生候选集，评价其好坏，再基于好的候选集来产生下一个候选集，持续重复此过程，直至无法找到更好的候选集为止。

毫无疑问，这样的策略找到的候选集可能并不是最优的。实际上，要保证找到全局最优的特征子集，只有穷举，而这样的计算代价往往是不可承受的。

那么现在我们就面临两个问题：

• 如何根据评价结果选择下一个特征子集？

• 如何评价候选集的好坏？

2、过滤式选择

过滤式方法先对数据集进行特征选择，然后再训练学习器，特征选择过程与与后续的学习过程无关，两者是完全分开的。

3、包裹式选择

与过滤式选择不同，包裹式选择直接把最终将要训练的学习器的性能作为特征子集的评价标准。因为其直接把学习器性能作为评价标准，因此包裹式选择后训练得到的学习器性能往往优于过滤式得到的学习器性能。但包裹式选择在特征选择过程中要多次训练学习器，因此计算开销比过滤式选择要大。

4、嵌入式选择与L1正则化

嵌入式选择将特征选择过程和学习器的训练过程融为一体。也就是说在学习器训练过程中自动加入了特征选择。

5、稀疏表示与字典学习

首先，我们先解释一下什么是“稀疏性”。假设数据集D的一行表示一个样本，一列表示一个特征，则“稀疏性”表示有很多列与当前学习任务无关。通过特征选择去除这些列，可以使学习的难度降低，计算和存储开销减小，模型可解释性增强。另一种稀疏性则是D中有很多元素为0，但这些元素并不是以整行或整列的形式出现的。

6、压缩感知

（略）