四、特征选择

1. 对于一个学习任务，给定了属性集，其中某些属性可能对于学习来说是很关键的，但是有些属性可能就意义不大。

   • 对当前学习任务有用的属性称作相关特征relevant feature 。
   • 对当前学习任务没有用的属性称作无关特征irrelevant feature 。

   从给定的特征集合中选出相关特征子集的过程称作特征选择feature selection。

2. 特征选择可能会降低模型的预测能力。因为被剔除的特征中可能包含了有效的信息，抛弃了这部分信息会一定程度上降低预测准确率。

   这是计算复杂度和预测能力之间的折衷：

   • 如果保留尽可能多的特征，则模型的预测能力会有所提升，但是计算复杂度会上升。
   • 如果剔除尽可能多的特征，则模型的预测能力会有所下降，但是计算复杂度会下降。

4.1 特征选择原理

1. 特征选择是一个重要的数据预处理（data preprocessing）过程。在现实机器学习任务中，获取数据之后通常首先进行特征选择，然后再训练学习器。

   进行特征选择的原因：

   • 首先，在现实任务中经常会遇到维数灾难问题，这是由于属性过多造成的。如果能从中选择出重要的特征，使得后续学习过程仅仅需要在一部分特征上构建模型，则维数灾难问题会大大减轻。

     从这个意义上讲，特征选择与降维技术有相似的动机。事实上它们是处理高维数据的两大主流技术。

   • 其次，去除不相关特征往往会降低学习任务的难度。

2. 特征选择过程必须确保不丢失重要特征，否则后续学习过程会因为重要信息的缺失而无法获得很好的性能。

   • 给定数据集，如果学习任务不同，则相关特征很可能不同，因此特征选择中的无关特征指的是与当前学习任务无关的特征。

   • 有一类特征称作冗余特征redundant feature，它们所包含的信息能从其他特征中推演出来。

     • 冗余特征在很多时候不起作用，去除它们能够减轻学习过程的负担。
     • 但如果冗余特征恰好对应了完成学习任务所需要的某个中间概念，则该冗余特征是有益的，能降低学习任务的难度。

     这里暂且不讨论冗余特征，且假设初始的特征集合包含了所有的重要信息。

3. 要想从初始的特征集合中选取一个包含了所有重要信息的特征子集，如果没有任何领域知识作为先验假设，则只能遍历所有可能的特征组合。

   这在计算上是不可行的，因为这样会遭遇组合爆炸，特征数量稍多就无法进行。

   一个可选的方案是：

   • 产生一个候选子集，评价出它的好坏。
   • 基于评价结果产生下一个候选子集，再评价其好坏。
   • 这个过程持续进行下去，直至无法找到更好的后续子集为止。

   这里有两个问题：如何根据评价结果获取下一个候选特征子集？如何评价候选特征子集的好坏？

4.1.1 子集搜索

1. 如何根据评价结果获取下一个候选特征子集？这是一个子集搜索subset search问题。

2. 解决该问题的算法步骤如下：

   • 给定特征集合 ，首先将每个特征看作一个候选子集（即每个子集中只有一个元素），然后对这 个候选子集进行评价。

     假设 最优，于是将 作为第一轮的选定子集。

   • 然后在上一轮的选定子集中加入一个特征，构成了包含两个特征的候选子集。

     假定 最优，且优于 ，于是将 作为第二轮的选定子集。

   • ….

   • 假定在第 轮时，本轮的最优的特征子集不如上一轮的最优的特征子集，则停止生成候选子集，并将上一轮选定的特征子集作为特征选择的结果。

3. 这种逐渐增加相关特征的策略称作前向forward搜索。

   类似地，如果从完整的特征集合开始，每次尝试去掉一个无关特征，这样逐渐减小特征的策略称作后向backward搜索。

4. 也可以将前向和后向搜索结合起来，每一轮逐渐增加选定相关特征（这些特征在后续迭代中确定不会被去除）、同时减少无关特征，这样的策略被称作双向bidirectional搜索。

5. 该策略是贪心的，因为它们仅仅考虑了使本轮选定集最优。但是除非进行穷举搜索，否则这样的问题无法避免。

4.1.2 子集评价

1. 如何评价候选特征子集的好坏？这是一个子集评价subset evaluation问题。

2. 给定数据集 ，假设所有属性均为离散型。对属性子集 ， 假定根据其取值将 分成了 个子集：

   于是可以计算属性子集 的信息增益：

   

   其中 为集合大小， 为熵。

   信息增益越大，则表明特征子集 包含的有助于分类的信息越多。于是对于每个候选特征子集，可以基于训练数据集 来计算其信息增益作为评价准则。

3. 更一般地，特征子集 实际上确定了对数据集 的一个划分规则。

   • 每个划分区域对应着 上的一个取值，而样本标记信息 则对应着 的真实划分。
   • 通过估算这两种划分之间的差异，就能对 进行评价：与 对应的划分的差异越小，则说明 越好。
   • 信息熵仅仅是判断这个差异的一种方法，其他能判断这两个划分差异的机制都能够用于特征子集的评价。

4. 将特征子集搜索机制与子集评价机制结合就能得到特征选择方法。

   • 事实上，决策树可以用于特征选择，所有树结点的划分属性所组成的集合就是选择出来的特征子集。
   • 其他特征选择方法本质上都是显式或者隐式地结合了某些子集搜索机制和子集评价机制。
5. 常见的特征选择方法大致可分为三类：过滤式filter、包裹式wrapper、嵌入式embedding 。

4.2 过滤式选择

1. 过滤式方法先对数据集进行特征选择，然后再训练学习器，特征选择过程与后续学习器无关。

   这相当于先用特征选择过程对初始特征进行过滤，再用过滤后的特征来训练模型。

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

   • 该统计量是一个向量，其中每个分量都对应于一个初始特征。特征子集的重要性则是由该子集中每个特征所对应的相关统计量分量之和来决定的。

   • 最终只需要指定一个阈值 ，然后选择比 大的相关统计量分量所对应的特征即可。

     也可以指定特征个数 ，然后选择相关统计量分量最大的 个特征。

3. 给定训练集 。 对于每个样本 :

   • Relief 先在 同类样本中寻找其最近邻 ，称作猜中近邻near-hit 。

   • 然后从 的异类样本中寻找其最近邻 ，称作猜错近邻near-miss 。

   • 然后相关统计量对应于属性 的分量为：

     

     其中 为两个样本在属性 上的差异值，其结果取决于该属性是离散的还是连续的：

     • 如果属性 是离散的，则：

       

     • 如果属性 是连续的，则：

       

       注意：此时 需要标准化到 [0,1] 区间。

4. 从公式

   

   可以看出：

   • 如果 与其猜中近邻 在属性 上的距离小于 与其猜错近邻 的距离，则说明属性 对于区分同类与异类样本是有益的，于是增大属性 所对应的统计量分量。
   • 如果 与其猜中近邻 在属性 上的距离大于 与其猜错近邻 的距离，则说明属性 对于区分同类与异类样本是起负作用的，于是减小属性 所对应的统计量分量。
   • 最后对基于不同样本得到的估计结果进行平均，就得到各属性的相关统计量分量。分量值越大，则对应属性的分类能力越强。

5. Relief 是为二分类问题设计的，其扩展变体 Relief-F 能处理多分类问题。

   假定数据集 中的样本类别为： 。对于样本 ，假设 。

   • Relief-F 先在类别 的样本中寻找 的最近邻 作为猜中近邻。

   • 然后在 之外的每个类别中分别找到一个 的最近邻 作为猜错近邻。

   • 于是相关统计量对应于属性 的分量为：

     

     其中 为第 类的样本在数据集 中所占的比例。

4.3 包裹式选择

1. 与过滤式特征选择不考虑后续学习器不同，包裹式特征选择直接把最终将要使用的学习器的性能作为特征子集的评价准则。其目的就是为给定学习器选择最有利于其性能、量身定做的特征子集。

   • 优点：由于直接针对特定学习器进行优化，因此从最终学习器性能来看，效果比过滤式特征选择更好。
   • 缺点：需要多次训练学习器，因此计算开销通常比过滤式特征选择大得多。

2. LVW:Las Vegas Wrapper是一个典型的包裹式特征选择方法。它是Las Vegas method框架下使用随机策略来进行子集搜索，并以最终分类器的误差作为特征子集的评价标准。

3. LVW算法：

   • 输入：

     • 数据集
     • 特征集
     • 学习器 estimator
     • 迭代停止条件

   • 输出： 最优特征子集

   • 算法步骤：

     • 初始化：令候选的最优特征子集 ，然后学习器 estimator在特征子集 上使用交叉验证法进行学习，通过学习结果评估学习器 estimator的误差 。

     • 迭代，停止条件为迭代次数到达 。迭代过程为：

       • 随机产生特征子集 。
       • 学习器 estimator在特征子集 上使用交叉验证法进行学习，通过学习结果评估学习器 estimator的误差 。
       • 如果 比 更小，或者 但是 的特征数量比 的特征数量更少，则将 作为候选的最优特征子集： 。
     • 最终 。

4. 由于LVW算法中每次特征子集评价都需要训练学习器，计算开销很大，因此算法设置了停止条件控制参数 。

   但是如果初始特征数量很多、 设置较大、以及每一轮训练的时间较长， 则很可能算法运行很长时间都不会停止。即：如果有运行时间限制，则有可能给不出解。

4.4 嵌入式选择

1. 在过滤式和包裹式特征选择方法中，特征选择过程与学习器训练过程有明显的分别。

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

2. 以线性回归模型为例。

   给定数据集 。 以平方误差为损失函数，则优化目标为：

   

   • 如果使用 范数正则化，则优化目标为：

     

     此时称作岭回归ridge regression `。

   • 如果使用 范数正则化，则优化目标为：

     

     此时称作LASSO:Least Absolute Shrinkage and Selection Operator 回归。

3. 引入 范数除了降低过拟合风险之外，还有一个好处：它求得的 会有较多的分量为零。即：它更容易获得稀疏解。

   于是基于 正则化的学习方法就是一种嵌入式特征选择方法，其特征选择过程与学习器训练过程融为一体，二者同时完成。

4. 正则化问题的求解可以用近端梯度下降Proximal Gradient Descent:PGD算法求解。

   对于优化目标： ，若 可导且 满足L-Lipschitz条件，即存在常数 使得：

   

   则在 附近将 通过二阶泰勒公式展开的近似值为：

   

   其中 是与 无关的常数项。

   • 若通过梯度下降法对 进行最小化，则每一步梯度下降迭代实际上等价于最小化二次函数 。

   • 同理，若通过梯度下降法对 进行最小化，则每一步梯度下降迭代实际上等价于最小化函数：。

     则每一步迭代为：

     

     其中 为 的第 次迭代的值。

     该问题有解析解，因此通过PGD能够使得LASSO和其他基于 范数最小化的方法能够快速求解。

5. 常见的嵌入式选择模型：

   • 在Lasso中， 参数控制了稀疏性：

     • 如果 越小，则稀疏性越小，则被选择的特征越多。
     • 如果 越大，则稀疏性越大，则被选择的特征越少。

   • 在SVM和logistic-regression中，参数C控制了稀疏性

     • 如果C越小，则稀疏性越大，则被选择的特征越少。
     • 如果C越大，则稀疏性越小，则被选择的特征越多。