降维和特征选择

KNN

KNN 是一种常用的监督学习方法。其工作机制非常简单：给定测试样本，基于某种距离度量找出训练集中与其最靠近的 $k$ 个训练样本，基于这 $k$ 个邻居的信息进行预测。

通常，在分类任务中可以使用“投票法”，即选择这 $k$ 个样本中出现次数最多的类别标记为预测结果（朴素方法直接寻找出现次数最多，值域过大可以考虑离散化，可以考虑摩尔投票法）；在回归任务中可使用“平均法”，即将这 $k$ 个样本的实值输出标记的平均值作为预测结果；还可以基于距离远近进行加权平均或加权投票，距离越近的样本权重越大。

KNN 算法的学习有一个与其他算法明显不同之处：它没有显式的学习过程，这被称为懒惰学习。此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理。

与之相对的是急切学习，此类学习技术在训练阶段就对样本进行学习处理。

KNN 分类器中的超参数 $k$ 是一个重要参数，当 $k$ 取不同值时，分类结果会有显著不同。

另一方面，若采用不同的距离计算方式，则找出的“近邻”可能有显著差别，从而也会导致分类结果有显著不同。

下面对最近邻分类器（1NN，即 $k=1$）在二分类问题上的性能做一个简单的讨论。

1NN

给定测试样本 $\boldsymbol{x}$，若其最近邻样本为 $\boldsymbol{z}$，则最近邻出错的概率就是 $\boldsymbol{x}$ 和 $\boldsymbol{z}$ 类别标记不同的概率，即

$$P(err) = 1 - \sum_{c \in \mathcal{Y}} P(c \mid \boldsymbol{x}) P(c \mid \boldsymbol{z})$$

其中，$P(c \mid \boldsymbol{x}) P(c \mid \boldsymbol{z})$ 表示 $\boldsymbol{x}$ 和 $\boldsymbol{z}$ 同属于属性 $c$ 的概率。

假设样本独立同分布，且对任意的 $\boldsymbol{x}$ 和任意小的 $\delta \in \mathbb{R}^+$，在 $\boldsymbol{x}$ 附近 $\delta$ 距离范围内总能找到一个训练样本，令 $c^* = \arg\max_{c \in \mathcal{Y}} P(c \mid \boldsymbol{x})$ 表示贝叶斯最优分类器的结果，有

$$\begin{aligned} P(err) & = 1 - \sum_{c \in \mathcal{Y}} P(c \mid \boldsymbol{x}) P(c \mid \boldsymbol{z}) \\ & \simeq 1 - \sum_{c \in \mathcal Y}{P^2(c \mid \boldsymbol{x})} \\ & \leq 1 - P^2(c^* \mid \boldsymbol{x}) \\ & = (1+P(c^* \mid \boldsymbol{x}))(1-P(c^* \mid \boldsymbol{x})) \\ & \leq 2 \times (1 - P(c^* \mid \boldsymbol{x})) \end{aligned}$$

最近邻分类虽简单，但它的泛化错误率不超过贝叶斯最优分类器错误率的两倍。

低维嵌入

上述讨论基于一个重要的假设：任意测试样本 $\boldsymbol{x}$ 附近的任意小的 $\delta$ 距离范围内总能找到一个训练样本，即训练样本的采样密度足够大。然而，这个假设在现实任务中很难满足。

设属性维数为 1，当 $\delta=0.001$ 时，仅需 1000 个样本点平均分布在归一化后的属性取值范围内，即可使得任意测试样本在其附近 0.001 距离范围内总能找到一个训练样本。若属性维数为 20，则至少需要 $(10^3)^{20} = 10^{60}$ 个样本。现实应用中属性维数经常成千上万，要满足密采样条件所需的样本数目是无法达到的天文数字。许多学习方法都涉及距离计算，而高维空间会给距离计算带来很大的麻烦，例如当维数很高时甚至连计算内积都不再容易。

在高维情形下出现的数据样本稀疏、距离计算困难等问题，是所有机器学习方法共同面临的严重障碍，被称为“维数灾难”（curse of dimensionality）。

为了避免维数灾难，一个重要的途径是降维（dimension reduction），即通过某种数学变换，将原始高维属性空间转变为一个低维“子空间” (subspace)，在这个子空间中样本密度大幅度提高，距离计算也变得更为容易。

为什么能进行降维？这是因为数据样本虽然是高维的，但与学习任务密切相关的也许仅是某个低维分布，即高维空间中的一个低维“嵌入”(embedding)，因而可以对数据进行有效的降维。

线性降维

一般来说，要获得低维子空间，最简单的是对原始高维空间进行线性变换。给定 $d$ 维空间中的样本 $\mathbf{X}=\left(\boldsymbol{x}_1, \boldsymbol{x}_2, \dots, \boldsymbol{x}_m\right) \in \mathbb{R}^{d \times m}$，变换之后得到 $d' \leq d$ 维空间中的样本 $\mathbf{Z} = \mathbf{W}^\mathrm T\mathbf{X}$，其中 $\mathbf{W} \in \mathbb{R}^{d \times d'}$ 是变换矩阵，$\mathbf{Z} \in \mathbb{R}^{d' \times m}$ 是样本在新空间中的表达。

变换矩阵 $\mathbf{W}$ 可视为 $d'$ 个 $d$ 维属性向量，$\boldsymbol{z}_i$ 是原属性向量 $\boldsymbol{x}_i$ 在新坐标系 $\left\{\boldsymbol{w}_1, \boldsymbol{w}_2, \dots, \boldsymbol{w}_{d'}\right\}$ 中的坐标向量。若 $\boldsymbol{w}_i$ 与 $\boldsymbol{w}_j$（$i \neq j$）正交，则称新坐标系是一个正交坐标系，此时 $\mathbf{W}$ 是一个正交变换。显然，新空间中的属性是原空间中的属性的线性组合。

基于线性变换进行降维的方法称为线性降维方法，对低维子空间性质的不同要求可通过对 $\mathbf{W}$ 施加不同的约束来实现。

主成分分析

主成分分析（Principal Component Analysis，PCA）是最常用的一种降维方法。

对于正交属性空间中的样本点，如果用一个超平面对所有样本进行恰当地表达，它应当具有下列性质：

• 最近重构性：样本点到这个超平面的距离都足够近；
• 最大可分性：样本点到这个超平面上的投影能尽可能分开。

基于最近重构性和最大可分性，能分别得到主成分分析的两种等价推导。

最近重构性

假设数据样本进行了中心化，即 $\sum_i\boldsymbol{x}_i=0$，再假定投影变换后得到的新坐标系为 $\left\{\boldsymbol{w}_1, \boldsymbol{w}_2, \dots, \boldsymbol{w}_d\right\}$，其中 $\boldsymbol{w}_i$ 为标准正交基向量，$||\boldsymbol{w}_i||_2=1$，$\boldsymbol{w}_i^\mathrm T\boldsymbol{w}_j = 0$（$i \neq j$）。

若丢弃新坐标系中的部分坐标，即将维度降低到 $d' < d$，则样本点在低维坐标系中的投影是 $\boldsymbol{z}_i = \left(z_{i1};z_{i2};\dots;z_{id'}\right)$，$z_{ij} = \boldsymbol{w}_j^\mathrm T\boldsymbol{x}_i$ 是 $\boldsymbol{x}_i$ 在低维坐标下的第 $j$ 维的坐标。若基于 $\boldsymbol{z}_i$ 来重构 $\boldsymbol{x}_i$，则会得到

$$\hat{\boldsymbol{x}}_i=\sum\limits_{j=1}^{d'}{z_{ij}\boldsymbol{w}_j}$$

考虑整个训练集，原样本点 $\boldsymbol{x}_i$ 与基于投影重构的样本点 $\hat{\boldsymbol{x}}_i$ 之间的距离为

$$\begin{aligned} \sum_{i=1}^{m}\left\|\sum_{j=1}^{d^{\prime}} z_{i j} \boldsymbol{w}_{j}-\boldsymbol{x}_{i}\right\|_{2}^{2} & =\sum_{i=1}^{m} \boldsymbol{z}_{i}{ }^{\mathrm{T}} \boldsymbol{z}_{i}-2 \sum_{i=1}^{m} \boldsymbol{z}_{i}^{\mathrm{T}} \mathbf{W}^{\mathrm{T}} \boldsymbol{x}_{i}+\text { const } \\ & \propto-\operatorname{tr}\left(\mathbf{W}^{\mathrm{T}}\left(\sum_{i=1}^{m} \boldsymbol{x}_{i} \boldsymbol{x}_{i}^{\mathrm{T}}\right) \mathbf{W}\right) \end{aligned}$$

其中 const 是一个常数。

已知 $\mathbf{W}^\mathrm T \mathbf W = \mathbf I$，$\boldsymbol{z}_i = \mathbf{W}^\mathrm T \boldsymbol{x}_i$，则

$$\begin{aligned} \sum_{i=1}^{m}\left\|\sum_{j=1}^{d^{\prime}} z_{i j} \boldsymbol{w}_{j}-\boldsymbol{x}_{i}\right\|_{2}^{2}&=\sum_{i=1}^{m}\left\|\mathbf{W} \boldsymbol{z}_{i}-\boldsymbol{x}_{i}\right\|_{2}^{2} \\ &=\sum_{i=1}^{m}\left(\mathbf{W} \boldsymbol{z}_{i}-\boldsymbol{x}_{i}\right)^{\mathrm{T}}\left(\mathbf{W} \boldsymbol{z}_{i}-\boldsymbol{x}_{i}\right) \\ &=\sum_{i=1}^{m}\left(\boldsymbol{z}_{i}^{\mathrm{T}} \mathbf{W}^{\mathrm{T}} \mathbf{W} \boldsymbol{z}_{i}-\boldsymbol{z}_{i}^{\mathrm{T}} \mathbf{W}^{\mathrm{T}} \boldsymbol{x}_{i}-\boldsymbol{x}_{i}^{\mathrm{T}} \mathbf{W} \boldsymbol{z}_{i}+\boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{i}\right) \\ &=\sum_{i=1}^{m}\left(\boldsymbol{z}_{i}^{\mathrm{T}} \boldsymbol{z}_{i}-2 \boldsymbol{z}_{i}^{\mathrm{T}} \mathbf{W}^{\mathrm{T}} \boldsymbol{x}_{i}+\boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{i}\right) \\ &=\sum_{i=1}^{m} \boldsymbol{z}_{i}^{\mathrm{T}} \boldsymbol{z}_{i}-2 \sum_{i=1}^{m} \boldsymbol{z}_{i}^{\mathrm{T}} \mathbf{W}^{\mathrm{T}} \boldsymbol{x}_{i}+\sum_{i=1}^{m} \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{i} \\ &=\sum_{i=1}^{m} \boldsymbol{z}_{i}^{\mathrm{T}} \boldsymbol{z}_{i}-2 \sum_{i=1}^{m} \boldsymbol{z}_{i}^{\mathrm{T}} \mathbf{W}^{\mathrm{T}} \boldsymbol{x}_{i}+\text { const } \\ &=\sum_{i=1}^{m} \boldsymbol{z}_{i}^{\mathrm{T}} \boldsymbol{z}_{i}-2 \sum_{i=1}^{m} \boldsymbol{z}_{i}^{\mathrm{T}} \boldsymbol{z}_{i}+\text { const } \\ &=-\sum_{i=1}^{m} \boldsymbol{z}_{i}^{\mathrm{T}} \boldsymbol{z}_{i}+\text { const } \\ &=-\sum_{i=1}^{m} \operatorname{tr}\left(\boldsymbol{z}_{i} \boldsymbol{z}_{i}^{\mathrm{T}}\right)+\mathrm{const} \\ &=-\operatorname{tr}\left(\sum_{i=1}^{m} \boldsymbol{z}_{i} \boldsymbol{z}_{i}^{\mathrm{T}}\right)+\text { const } \\ &=-\operatorname{tr}\left(\sum_{i=1}^{m} \mathbf{W}^{\mathrm{T}} \boldsymbol{x}_{i} \boldsymbol{x}_{i}^{\mathrm{T}} \mathbf{W}\right)+\text { const } \\ &=-\operatorname{tr}\left(\mathbf{W}^{\mathrm{T}}\left(\sum_{i=1}^{m} \boldsymbol{x}_{i} \boldsymbol{x}_{i}^{\mathrm{T}}\right) \mathbf{W}\right)+\text { const } \\ &\propto-\operatorname{tr}\left(\mathbf{W}^{\mathrm{T}}\left(\sum_{i=1}^{m} \boldsymbol{x}_{i} \boldsymbol{x}_{i}^{\mathrm{T}}\right) \mathbf{W}\right) \\ \end{aligned}$$

根据最近重构性，上式应当被最小化，考虑到 $\boldsymbol{w}_j$ 是标准正交基，$\sum_i \boldsymbol{x}_i\boldsymbol{x}_i^\mathrm T$ 是协方差矩阵，有

$$\begin{aligned} &\min_{\mathbf{W}}{-\operatorname{tr}(\mathbf{W}^\mathrm T\mathbf{X}\mathbf{X}^\mathrm T\mathbf{W})} \\ &\text{ s.t. } \mathbf{W}^\mathrm T\mathbf{W} = \mathbf I \end{aligned}$$

这就是主成分分析的优化目标。

最大可分性

样本点 $\boldsymbol{x}_i$ 在新空间中超平面上的投影是 $\mathbf{W}^\mathrm T\boldsymbol{x}_i$，若所有样本点的投影尽可能分开，则应该使得投影后样本点的方差最大化。

投影后样本点的方差是 $\sum_i{\mathbf{W}^\mathrm T\boldsymbol{x}_i\boldsymbol{x}_i^\mathrm T \mathbf W}$，于是优化目标可写为

$$\begin{aligned} &\max_{\mathbf W}{\operatorname{tr}(\mathbf{W}^\mathrm T\mathbf{X}\mathbf{X}^\mathrm T\mathbf{W})} \\ &\text{ s.t. } \mathbf{W}^\mathrm T\mathbf{W} = \mathbf I \end{aligned}$$

显然与最近重构性推导得到的最优化问题等价。

对任一优化式使用拉格朗日乘子法可得

$$\mathbf X \mathbf{X}^\mathrm T \mathbf W = \boldsymbol{\lambda} \mathbf W$$

只需对协方差矩阵 $\mathbf X\mathbf{X}^\mathrm T$ 进行特征值分解，并将求得的特征值排序：$\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_d$，再取前 $d'$ 个特征值对应的特征向量构成 $\mathbf W = \left(\boldsymbol{w}_1, \boldsymbol w_2, \dots, \boldsymbol w_{d'}\right)$，这就是主成分分析的解。

特征值分解：

1. 先求 $A$ 的特征多项式 $f(\lambda) = |A - \lambda E| = |A - \Lambda|$，其中 $\Lambda$ 是一个主对角线上全为 $\lambda$ 的方阵；
2. 求特征方程 $|A - \lambda E| = 0$ 的全部解，他们就是 $A$ 的全部特征值；
3. 对于一个特征值 $\lambda_i$，求出相应的特征方程组 $(A - \Lambda_i)X = 0$ 的一组特解 $\xi_1, \xi_2, \cdots, \xi_t$，则这组解对应的向量即为一个特征向量。

降维后低维空间的维数 $d'$ 通常是由用户事先指定，或通过在 $d'$ 值不同的低维空间中对 k 近邻分类器（或其他开销较小的学习器）进行交叉验证来选取较好的 $d'$ 值。对 PCA，还可以还可从重构的角度设置一个重构阈值，例如 $t = 95\%$，然后选取使下式成立的最小 $d'$ 值：

$$\dfrac{\sum_{i=1}^{d'} \lambda_i}{\sum_{i=1}^d{\lambda_i}} \geq t$$

PCA 仅需保留 $\mathbf W$ 与样本的均值向量，即可通过简单的向量减法和矩阵-向量乘法将新样本投影至低维空间中。

降维虽然会导致信息的损失，但一方面舍弃这些信息后能使得样本的采样密度增大，另一方面，当数据受到噪声影响时，最小的特征值所对应的特征向量往往与噪声有关，舍弃可以起到去噪效果。

数据预处理

为什么进行预处理

现实世界中绝大部分的数据是“脏的”：

• 不完整：缺少数据值；缺乏某些重要属性；仅包含汇总数据；
• 有噪声：包含错误或孤立点；
• 数据不一致：
  • 在编码或者命名上存在差异
  • 过去的等级： “1,2,3”, 现在的等级： “A, B, C”
  • 户籍系统中的身份证号前后不一致

为什么会变“脏”

• 数据不完整的成因
  • 数据收集的时候就缺乏合适的值
  • 数据收集时和数据分析时的不同考虑因素
  • “人为/硬件/软件”的问题
• 噪声数据（不正确的值）的成因
  • 数据收集工具的问题
  • 数据输入时的“人为/计算机”造成的错误
  • 数据传输中产生的错误
• 数据不一致性的成因
  • 不同的数据源
  • 违反了某种一致性原则

数据预处理为什么是重要的？

• 没有高质量的数据，就没有高质量的挖掘结果。
  • 高质量的决策必须依赖高质量的数据，例如重复值或者空缺值将会产生不正确的挖掘结果。
• 数据预处理是数据挖掘过程中占工作量最大的一个步骤。(60%的工作量)

数据质量的多维度量

一个广为认可的多维度量观点：

• 精确度
• 完整度
• 一致性
• 可信度
• 附加价值
• 可解释性

数据预处理的主要任务

• 数据清理：填写空缺的值，平滑噪声数据，识别、删除孤立点，解决不一致性。
• 数据集成：集成多个数据库或文件。
• 数据变换：规范化——将数据规范化到统一的范围内。
• 数据规约：得到数据集的压缩表示，它比原始数据集小得多，但可以得到相同或相近的挖掘结果。

数据清理

• 填写空缺的值
  引起空缺值的原因：

  • 设备异常
  • 与其他已有数据不一致而被删除
  • 因为误解而没有被输入的数据
  • 在输入时，有些数据应为得不到重视而没有被输入
  • 对数据的改变没有进行日志记载

  补充空缺值可行的方法：

  • 人工填写空缺值：工作量大
  • 使用属性的平均值填充空缺值
  • 使用与给定元组属同一类的所有样本的平均值

• 识别离群点和平滑噪声数据
  引起噪声的原因：

  • 数据收集工具的问题
  • 数据输入错误
  • 数据传输错误
  • 技术限制
  • 命名规则的不一致

  如何处理噪声数据：

  • 计算机和人工检查结合：计算机检测可疑数据，然后对它们进行人工判断；效率较低
  • 回归：通过让数据适应回归函数来平滑数据
    
  • 聚类：监测并且去除孤立点，落在簇集合之外的值被视为孤立点。
    

• 纠正不一致的数据

• 解决数据集成造成的冗余

数据集成

数据集成是将多个数据源中的数据整合到一个一致的存储中的过程；可能产生数据冗余。

• 集成多个数据库时，经常会出现冗余数据
  • 对象识别：同一属性或对象在不同的数据库中会有不同的字段名（性别：字段名可能是 sex 或者 gender）；
• 结论：如果能够仔细地将多个数据源中的数据集成起来，将减少或避免结果数据中的冗余与不一致性，从而可以提高挖掘的速度和质量。

数据变换

数据变换是将数据转换成适合挖掘的统一形式。

规范化是将数据按比例缩放，使之落入一个小的特定区间。下面介绍 min-max 规范化和 z-score 规范化。

min-max 规范化适合于已知最大、最小值时使用，将一个值规范化至 $[p, q)$ 区间的公式为

$$v' = \dfrac{v - \min_A}{\max_A - \min_A}(q - p) + p$$

z-score 规范化适合于最大、最小值未知时使用：

$$v' = \dfrac{v - \mu}{\sigma}$$

其中 $\mu$ 为整组数据的均值，$\sigma$ 为整组数据的标准差。

数据规约

数据归约可以用来得到数据集的归约表示，它能够比原始数据集小得多，但可以产生相同的（或几乎相同的）挖掘结果。

为什么要进行数据规约？

• 数据集中往往存有海量数据；
• 在整个数据集上进行复杂的数据分析与挖掘需要很长时间。

常用的数据归约策略：

• 维归约，e.g. 移除不重要的属性
• 数据压缩
• 数值归约，e.g. 使用模型来表示数据

注意：用于数据归约的时间不应当超过或“抵消”在归约后的数据上执行挖掘节省的时间。

特征选择

我们将属性称为“特征”，对当前学习任务有用的属性称为“相关特征”，没什么用的属性称为“无关特征”。

从给定的特征集合中选择出相关特征子集的过程，称为“特征选择”。在现实机器学习任务中，获得数据之后通常要先进行特征选择，之后再训练学习器。原因有二：

• 选择出重要的特征可以使得后续学习过程仅需在一部分特征上构建模型，维数灾难问题会大为减轻；
• 去除不相关特征往往会降低学习任务的难度。

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

如何选择特征？朴素的想法是进行深搜，遍历所有可能的子集，但复杂度过高（$\mathcal O(2^n)$），计算上遭遇组合爆炸，不可行。

一种可行的方法是，先产生一个初始的候选子集，评价候选子集的好坏，基于评价结果产生下一个候选子集，这个过程持续进行下去，直到无法找到一个更好的候选子集为止。显然，这里涉及两个关键环节：如何根据评价结果获取下一个候选特征子集？如何评价候选特征子集的好坏？

子集搜索

由于我们希望特征的数量尽可能少，于是包含 $k$ 个特征的特征集一定不劣于包含 $k+1$ 个特征的特征集。基于此，我们可以设计一个贪心的策略，来选择包含重要信息的特征子集：

假设给定特征集合 $\left\{a_1, a_2, \dots, a_d\right\}$

• 前向搜索：对这 $d$ 个候选单特征子集进行评价，选择一个最优的作为第一轮的选定集；然后，在上一轮的选定集中加入一个特征，构造一个包含两个特征的候选子集；这个过程持续进行下去，直到第 $k+1$ 轮时，最优的 $(k+1)$ 个特征的子集劣于上一轮的选定集，则停止生成候选子集，并将上一轮的 $k$ 个特征的子集作为特征选择结果，最差复杂度为 $\Theta\left(\sum\limits_{i=n}^1 i\right) = \mathcal O(n^2)$，平均复杂度为 $\mathcal O(n)$。
• 后向搜索：从完整的特征集合开始，每次尝试去掉一个无关特征，直到找到最优的子集；
• 双向搜索：每一轮逐渐增加选定相关特征，同时减少无关特征。

事实上，这个问题并不满足贪心的局部最优性，假定第三轮中选择 $a_5$ 优于 $a_6$，则选定集为 $\left\{x, y, a_5\right\}$，但可能在第四轮中出现 $\left\{x, y, a_6, z\right\}$ 优于所有的 $\forall_{v \in D \setminus \left\{x, y, a_5\right\}}\left\{x, y, a_5, v\right\}$，当数据范围较小时，可以通过状压 dp 进行解决，但遗憾的是，数据范围通常很大，若不进行穷举搜索则这种问题无法避免。

子集评价

特征子集确定了对数据集的一个划分，每个划分区域对应着特征子集的某种取值；而样本标记对应着对数据集的真实划分。通过估算这两个划分的差异，就能对特征子集进行评价；与样本标记对应的划分的差异越小，则说明当前特征子集越好。

给定数据集 $D$，假定 $D$ 中第 $i$ 类样本所占的比例为 $p_i$（$i = 1, 2, \dots, |\mathcal Y|$）。为便于讨论，假定样本属性均为离散型，对属性子集 $A$，假定根据其取值将 $D$ 分成了 $V$ 个子集 $\left\{D^1, D^2, \dots, D^V\right\}$，每个子集中的样本在 $A$ 上取值相同，于是我们可以计算属性子集 $A$ 的信息增益

$$\operatorname{Gain}(A) = \operatorname{Ent}(D) - \sum\limits_{v=1}^V\dfrac{|D^v|}{|D|} \operatorname{Ent}(D^v)$$

其中,信息熵定义为

$$\operatorname{Ent}(D) = -\sum\limits_{i=1}^{|\mathcal Y|} p_i\log_2 p_i$$

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

特征选择方法

将特征子集搜索机制和子集评价机制相结合，即可得到特征选择方法。常见的特征选择方法大致可分为三类：过滤式、包裹式和嵌入式。

过滤式选择

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

Relief（Relevant Features）是一种著名的过滤式特征选择方法，该方法设计了一个“相关统计量”来度量特征的重要性。该统计量是一个向量，其每个分量分别对应着一个初始特征，则特征子集的重要性可由各个元素对应的相关统计量的分量之和决定。

于是最终只需指定一个阈值 $r$，然后选择比 $r$ 大的相关统计量分量对应的特征即可；也可以指定欲选取的特征个数 $k$，然后选择相关统计量分量最大的 $k$ 个特征。

不难发现，Relief 的关键在于如何确定相关统计量。给定训练集 $\left\{(\boldsymbol{x}_1, y_1), (\boldsymbol{x}_2, y_2), \dots, (\boldsymbol{x}_m, y_m)\right\}$，Relief 先在 $\boldsymbol{x}_i$ 的同类样本中寻找其最近邻 $\boldsymbol{x}_{i, nh}$，称为“猜中近邻”；再从 $\boldsymbol{x}_i$ 的异类样本中寻找其最近邻 $\boldsymbol{x}_{i, nm}$，称为“猜错近邻”，则相关统计量对应于属性 $j$ 的分量为

$$\delta^j = \sum_{i}-\operatorname{diff}(x_i^j, x_{i, nh}^j)^2 + \operatorname{diff}(x_i^j, x_{i, nm}^j)^2$$

其中 $x_i^j$ 表示样本 $\boldsymbol{x}_i$ 在属性 $j$ 上的取值；若属性 $j$ 为离散值，则 $\operatorname{diff}(a, b) = a \bigoplus b$；若为连续值，则 $\operatorname{diff}(a, b) = |a - b|$，注意二者应当已经规范化到 $[0, 1]$ 区间。

相关统计量越大，则属性 $j$ 上猜对近邻比猜错近邻更近，该属性对区分对错越有用。Relief 方法的时间开销随采样次数以及原始特征数线性增长，运行效率很高。

容易发现，Relief 方法是为二分类问题设计的，但也可以自然地推广到多分类问题中，称为 Relief-F 方法。

假定数据集中的样本来自 $|\mathcal Y|$ 个类别，其中 $\boldsymbol{x}_i$ 属于第 $k$ 类，则猜中近邻为第 $k$ 类中 $\boldsymbol{x}_i$ 的最近邻 $\boldsymbol{x}_{i, nh}$，猜错近邻为第 $k$ 类之外的每个类中找到一个 $\boldsymbol{x}_i$ 的最近邻，记为 $\boldsymbol{x}_{i, l, nm}$（$l = 1, 2, \dots, |\mathcal Y|$；$l \neq k$），则相关统计量对应于属性 $j$ 的分量为

$$\delta^j = \sum_{i}-\operatorname{diff}(x_i^j, x_{i, nh}^j)^2 + \sum_{l \neq k}\left(p_l \times \operatorname{diff}(x_i^j, x_{i, l, nm})^2\right)$$

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

包裹式选择

包裹式特征选择直接把最终将要使用的学习器的性能作为特征子集的评价准则。从最终学习器的性能来看，包裹式特征选择比过滤式特征选择更好，但另一方面，由于特征选择过程中需要多次训练学习器，因此包裹式特征选择的计算开销通常要比过滤式特征选择大得多。

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

基本步骤：

• 在循环的每一轮随机产生一个特征子集；
• 在随机产生的特征子集上通过交叉验证（留出法）推断当前特征子集的误差；
• 进行多次循环，在多个随机产生的特征子集中选择误差最小的特征子集作为最终解，如果有运行时间限制，则该算法有可能无法给出解。

嵌入式选择

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

考虑最简单的线性回归模型，以平方误差为损失函数，并引入 L2 正则化项防止过拟合，则有

$$\min_{\boldsymbol{w}}\sum\limits_{i=1}^m{(y_i - \boldsymbol{w}^\mathrm T \boldsymbol{x}_i)^2 + \lambda \|\boldsymbol{w}\|_2^2}$$

其中正则化参数 $\lambda > 0$，上式称为“岭回归”，能显著降低过拟合的风险。

若将 L2 范数替换为 L1 范数，则有

$$\min_{\boldsymbol{w}}\sum\limits_{i=1}^m{(y_i - \boldsymbol{w}^\mathrm T \boldsymbol{x}_i)^2 + \lambda \|\boldsymbol{w}\|_1}$$

其中正则化参数 $\lambda > 0$，上式称为 LASSO。

LASSO 易获得稀疏解，即它求得的 $\boldsymbol{w}$ 会有更少的非零分量，是一种嵌入式特征选择方法。

为了理解这一点，假定 $\boldsymbol{x}$ 只有两个属性，则 $\boldsymbol{w}$ 只有两个分量 $w_1$ 和 $w_2$，我们将其作为坐标轴，然后画出平方误差项、L1 范数和 L2 范数的等值线，如下：

可以发现，L1 范数的等值线与平方误差项的等值线的交点“常”出现在坐标轴上，即产生一个 $w_1$ 或 $w_2$ 为 0 的稀疏解，而 L2 范数的等值线与平方误差项的等值线的交点“不太可能”出现在坐标轴上，$w_1$ 和 $w_2$ 都非 0。

于是，求解 L1 范数正则化的结果是得到了仅采用一部分初始特征的模型；换言之，基于 L1 范数正则化学习方法就是一种嵌入式特征选择方法。