1. 章节主要内容

1）子集搜索和评价

特征选择和降维计算一样，都能有效的减轻维数灾难问题，事实上，特征选择和降维计算是处理高维数据的两大主流技术。但与降维将高维属性投影嵌入到低维空间不同，特征选择是直接将无关的属性去除，这会有效降低学习任务的难度，就像侦探破案一样，将繁杂的因素抽丝剥茧，只留下关键信息，则真相往往更容易看清。

不过需注意的是特征选择过程必须确保不丢失关键信息，否则后续学习过程会由于丢失重要信息而无法获得好的性能。

那么我们如何很好的从初始的特征集合中选取一个包含了所有重要信息的特征子集呢？最保险的方法是遍历所有子集可能，然后分别评估性能并选出性能最好的特征子集，但是这在计算上不可行，会导致组合爆炸（如果穷举法能用的话，还需要设计什么算法呢）。所以和其它任何计算机算法思考逻辑一样，无法确定找到最优解的情况下，我们只能使用贪婪算法找到局部最优，然后通过各种策略使得这个局部最优尽可能的贴近全局最优解。

具体做法是选择一个“候选子集”，然后评价它的好坏，然后基于评价结果产生下一个候选子集，持续这个循环直到没有更好的候选子集为止。显然这里特征选择涉及两个关键环节：如何根据反馈来获取下一个特征子集（子集搜索 subset search）？如何评价候选特征子集的好坏（子集评价 subset evaluation）？

子集搜索可以以一个属性开始进行“前向”搜索，首先，找到性能最好的单个属性，然后在该属性基础上在剩下的属性中进行寻找，找到下一个属性使得两个属性的集合性能最好，以此类推直到没有属性可以添加进入属性子集中使得性能更优时停止。 相对应的，我们也可以以全量属性进行“后向”搜索，每次尝试去掉一个无关属性。

子集评价可以使用“信息增益”（详情请查看第四章决策树）来评估，其本质是比较特征子集 A 对数据集的划分与实际标记信息 Y 对数据集的划分的差别，其它能判断两个划分差异的机制都能用于特征子集评价

不同的特征选择方法实际上是显式或隐式的结合了某种或多种子集搜索和子集评价机制。

例如将前向搜索与信息熵结合起来的特征选择过程就和决策树类似。实际上决策树可用于特征选择，树结点的划分属性所组成的集合就是选择出的特征子集。

常见的特征选择方法大致可分为三类：过滤式（filter）、包裹式（wrapper）和嵌入式（embedding）

2）过滤式特征选择

过滤式方法先对数据集进行特征选择，然后再训练学习器，特征选择过程与后续学习器无关；即先对特征进行“过滤”，然后用过滤后的特征来训练模型。

Relief（Relevant Features）是一种著名的过滤式特征选择方法，该方法设计了一个“相关统计量”来度量特征的重要性。

具体做法是对每个训练样本 xi 找到和它同一个分类的最近邻样本 xj，以及和它不是一个分类的最近邻样本 xk。如果 diff(xi, xj)t 表示 xi 和 xj 在属性 t 上的差值，那么相关统计量计算的就是：diff(xi, xk)的平方 与 diff(xi, xj)的平方的差值在所有样本上的平均

很直观的，一个重要的属性应该使得样本在这个属性上与自己同一分类的样本尽可能接近，而与不同分类的样本尽可能远。所以相关统计量在一个属性上的值越大则说明该属性的分类性能越强

过滤式特征选择的处理逻辑如下图所示：

3）包裹式特征选择

包裹式选择直接把最终将要使用的学习器性能作为特征子集的评价标准；根据学习器选择最有利于性能、“量身打造”的特征子集

一般而言，由于包裹式特征选择方法直接针对给定学习器进行优化，因此从最终的学习性能来看，包裹式方法比过滤式方法更好，当另一方面，由于在特征选择过程中需多次训练学习器，因此包裹式选择的计算开销一般要比过滤式选择大得多

LVW（Las Vegas Wrapper）是一个典型的包裹式特征选择算法。它在拉斯维加斯算法（Las Vegas Method）框架下使用随机策略来进行子集搜索，并以最终分类器的误差作为特征子集评价准则。

具体做法(简化)是：

［1］设置初始最优误差 E 为无穷大，目前最优特征子集为属性全集 A，重复次数 t = 0

［2］随机产生一组特征子集 A'，计算使用该特征子集时分类器的误差 E'

［3］如果 E' 比 E 小，则令 A' = A, E' = E 并重复［2］、［3］步；否则 t++，当 t 大于等于停止控制参数 T 时跳出循环。

LVW算法简单明了，但是由于是使用随机子集筛选，并且每次筛选都要重新计算学习器误差，若 A 和 T 很大时，算法可能会长时间都达不到停止条件。即若有运行时间限制，则可能会得不到解。

包裹式特征选择的处理逻辑如下图所示：

4）嵌入式特征选择

不同于前两种特征选择方式将特征的选择过程和学习器的训练过程分开，嵌入式特征选择是将特征选择过程与学习器训练过程融为一体，两者在同一个优化过程中完成；即在学习器训练过程中自动化的进行了特征选择。

比如决策树在分枝的过程中，就是使用的嵌入式特征选择方法，其内在还是根据某个度量指标对特征进行排序。

5）稀疏表示与字典学习

数据集可以以矩阵表示，每一行为一个样本，每一列为一个属性。特征选择所考虑的问题是特征具有“稀疏性”，即矩阵中的许多列与当前学习任务无关，我们需要通过特征选择去除这些列。

我们现在考虑另一种稀疏性：在数据集 D 所对应的矩阵中存在很多零元素，但这些零元素并不是以整列、整行形式存在的。当样本具有稀疏表示时，对学习任务有不少好处，比如稀疏表示的数据更容易线性可分。同时，稀疏表示的数据在存储上的负担不大。

那么我们可以通过将数据转换为“恰当稀疏”的形式，获得稀疏表示的好处，简化学习任务。这种为普通稠密表达的样本找到合适的字典，将样本转化为稀疏表示形式，从而使学习任务得以简化，模型复杂度得以降低，通常称为“字典学习”（dictionary learning），亦称“稀疏编码”（sparse coding）。

这两个称谓稍有差别，“字典学习”更侧重于学得字典的过程，而“稀疏编码”更侧重于将样本稀疏表达的过程，不过这两者都是算法同一个优化求解过程中完成的，因此可以不做进一步区分。

稀疏表示的具体的过程简单描述如下：

［1］确定映射字典的词汇量 k，并初始化字典 B，d＊k，其中 d 为样本属性数

［2］固定住字典 B，求得样本集 X 通过字典映射后的稀疏表示 Z

［3］固定住 Z 来更新字典 B

［4］反复第［2］、［3］步，最终可得合适的字典 B 和样本 X 的稀疏表示 Z

在上述字典学习过程中，用户能通过设置词汇量 k 的大小来控制字典的规模，从而影响稀疏程度

6）压缩感知（compressed sensing）

在现实任务中，我们常希望能根据部分信息来恢复全部信息。会拥有这种需求的原因是因为，在实践中为了便于数据的传输、存储，人们通常会将数据进行压缩，这有可能会损失一部分信息，而传输的过程中又可能会丢失一部分信息。这时候拥有根据接收到的受损的数据来恢复全部数据的能力就很重要了，而压缩感知为解决此类问题提供了新思路。

压缩感知的核心思想是：一般来说丢失了部分信息的数据是无法恢复为原始数据的，但是如果将原始数据通过字典学习表示成稀疏表示时，却可以比较好的进行复原。这是因为稀疏性使得未知因素的影响大大的减少。

与特征选择、稀疏表示不同，压缩感知关注的是如何利用信号本身的稀疏性，从部分观测样本中恢复原信号。通常认为，压缩感知分为“感知测量”和“重构恢复”这两个阶段。

“感知测量”关注如何对原始信号进行处理以获得其稀疏表示，这方面涉及我们前边提的特征选择、稀疏表示等内容

“重构恢复”关注的是如何从少量观测中恢复原信号，这才是压缩感知的精髓，当我们谈到压缩感知时，通常是指这部分。

2. 基础知识

1）拉斯维加斯方法

拉斯维加斯方法是一类随机方法的统称。这类方法是通过随机采样和一个评估函数来进行数据筛选的，本章介绍的 LVW 算法就是基于该方法的具体实现。它的特点是，随着采样次数的增多，得到的正确结果的概率逐渐加大，如果随机采样过程中已经找到了正确结果，该方法可以判别并报告，但在放弃随机采样，而采用类似全采样这样的确定性方法之前，不保证能找到任何结果（包括近似结果）

2）奈奎斯特采样定理

如果对某一时间连续信号（模拟信号）进行采样，当采样速率达到被测信号最大频率的两倍时，那么，根据这些采样值就能准确地确定原信号

3. 总结

1）特征选择和降维计算是处理高维数据的两大主流技术

2）特征选择涉及两个关键环节：如何根据反馈来获取下一个特征子集（子集搜索 subset search）？如何评价候选特征子集的好坏（子集评价 subset evaluation）

3）子集搜索是通过贪婪算法每次以一定的策略对特征子集进行添加或删除以使得新的子集能对性能进行提升。当没有更好的选择能使性能提升时，停止子集搜索过程

4）子集评价的本质是比较特征子集 A 对数据集的划分与实际标记信息 Y 对数据集的划分的差别，其它能判断两个划分差异的机制都能用于特征子集评价

5）不同的特征选择方法实际上是显式或隐式的结合了某种或多种子集搜索和子集评价机制

6）过滤式方法先对数据集进行特征选择，然后再训练学习器，特征选择过程与后续学习器无关；即先对特征进行“过滤”，然后用过滤后的特征来训练模型

7）包裹式选择直接把最终将要使用的学习器性能作为特征子集的评价标准；根据学习器选择最有利于性能、“量身打造”的特征子集

8）从学习性能上来看，包裹式特征选择比过滤式特征选择好许多，但是计算开销前者要比后者大得多

9）这种为普通稠密表达的样本找到合适的字典，将样本转化为稀疏表示形式，从而使学习任务得以简化，模型复杂度得以降低，通常称为“字典学习”（dictionary learning），亦称“稀疏编码”（sparse coding）

10）压缩感知的核心思想是：将原始数据通过字典学习表示成稀疏表示时，可以比较好的利用其稀疏性复原原始数据进