跳转至

机器学习笔记：稀疏学习与特征学习

内容来源：西瓜书（周志华《机器学习》）

核心观点

机器学习最重要的并不是模型，而是数据。模型上 XGBoost 能够干碎大部分花里胡哨的操作，经济学更是线性回归绝对优势，基本上都是具体问题具体分析再针对性地有所操作。

关键在于信息，在于数据。机器学习与数据科学的强绑定也来自于此。

这主要还是因为机器学习的特性：维数爆炸。要想把握现实中各个事物的关系，其实要考虑很多的变量，将其打包成一个 \(x\) 之后，就很自然的发现这个 \(x\) 是一个维数很高的向量。但归根到底，一个事物往往没有想象中的复杂，变量之所以多，是因为有噪声干扰。

有两种操作可以减小影响：

  1. 降维：直接合成看似复杂的数据
  2. 特征选取：去掉不重要的部分

一、降维

降维实际上就是减少数据的自由度，因为在空间中分布的高维数据很多维度其实是相关的（例如身高与体重、身高与父母身高等）。虽然说形式上写成多个维度而且很多时候是非线性关系，但是确实又是相关的，有一些更本质的内容蕴含在其中。

直接把数据中不重要的维度丢掉就行了吧，但是如何找一个很好的映射，以至于保持其分布不会发生改变。我们希望经过这样一个变换，数据的分布不发生改变——高维空间中隔得远的点也还是那么远，因为原始的高维空间数据分布就代表它们有很大的差距。

甚至我们有时不但要降维，反而还要把原始的数据给投影到高维潜空间之中，目的就是把数据的信息分离出来。当然，我们此时需要做到的，就是平衡信息和计算效率。

1.1 MDS 算法（多维缩放）

算法步骤：

  1. 计算距离矩阵 \(D\)

  2. 对 \(D\) 进行变换，得到内积矩阵 \(B\)，\(B\) 需满足列和、行和、\(\text{tr}(B)\) 均为零：

    \[ b_{ij} = -\frac{1}{2}\left(\text{dist}_{ij}^2 - \text{dist}_{i\cdot}^2 - \text{dist}_{\cdot j}^2 + \text{dist}_{\cdot\cdot}^2\right) \]

    其中：

    • \(\text{dist}_{i\cdot}^2 = \frac{1}{m}\sum_{j=1}^m \text{dist}_{ij}^2\)
    • \(\text{dist}_{\cdot j}^2 = \frac{1}{m}\sum_{i=1}^m \text{dist}_{ij}^2\)
    • \(\text{dist}_{\cdot\cdot}^2 = \frac{1}{m^2}\|D\|_F^2\)

  3. 对 \(B\) 进行特征值分解：\(B = V^T \Sigma V\)

  4. 选取最大的前 \(k\) 个特征值构成：\(Z = \Sigma^{1/2} \tilde{V}\)

\(Z\) 即为所求的降维结果。

1.2 PCA 主成分分析

PCA 是降维界"最高的山"。核心思想：找一个超平面，使得所有样本点尽可能在这个超平面上，而且点在超平面上的投影分得特别开。

这与 SVM 不同：SVM 想要把样本点"隔"开来，而 PCA 是想要把向量放在这个平面上，而且这些点分得尽可能开。

算法推导：

对样本点进行归一化，得到样本 \(\{x_n\}\)。假设经过坐标变换得到新坐标系 \(\{\omega_i\}\)，共 \(d\) 个向量。

投影坐标：\(x_i = \sum_{j=1}^d z_{ji} \omega_j\)

取前 \(d'\) 个分量：\(x_i' = \sum_{j=1}^{d'} z_{ji} \omega_j\)

目标：让 \(\sum_{i=1}^n \|x_i' - x_i\|_2^2\) 尽可能小

设 \(W = [w_1, w_2, \ldots, w_{d'}]\)，\(z = [z_1, z_2, \ldots, z_{d'}]^T\)

\[ \|Wz - x\|_2^2 = z^T W^T W z - 2x_i^T W z + \|x_i\|^2 \]

去掉常数，即最小化：\(\sum_{i=1}^n z_i^T z_i - 2\sum_{i=1}^n x_i^T W z_i\)

由 \(z_i = W x_i\)，原式化为：

\[ \min -\text{tr}(W^T X X^T W) \]

其中 \(X = [x_1, x_2, \ldots, x_n]\)，且 \(W^T W = I\)（正交约束）。

结论：选取 \(X X^T\) 的最大特征值，\(w\) 依次选取特征向量。

PCA 的局限：

  • 高维投影或许本身具有特定的结构
  • 损失了一维的信息
  • 低维嵌入是线性的近似，维度之间可能没有线性关系

1.3 核 PCA

采用非线性映射 \(\phi\)，将非线性分布的数据投影到超平面上：

\[ \min -\text{tr}(W^T X X^T W), \quad X = [\phi(x_1), \phi(x_2), \ldots, \phi(x_n)] \]

1.4 流形学习

非线性问题主要解决：将高维数据投影到低维平面，所生成的很多路径实际上是"不可达的"。就像是一根螺旋线，投影到地面上就是重叠，但是在三维上仍有信息，但毕竟这根线依然是一维的，我们实际上可以"贴地走"，把这种距离信息保留下来。

等度量嵌入（Isomap）：

采取局部欧式假设：假设样本点周围的几个点是符合欧式距离的，大致处于同一个低维平面之中。

算法步骤：

  1. 计算任意两点 \(x, y\) 的距离：

    • 计算 \(x\) 的 \(k\) 邻域
    • 邻域内的点按欧式距离计算
    • 邻域外的两点通过最短路径计算（使用 Dijkstra 算法）—— 这是一种"测地线"的度量

  2. 使用 MDS 算法，压缩维度后保持这种距离性质

局部线性嵌入（LLE）：

假设数据被前 \(k\) 个数据线性表示，即需要得到一组权重：

\[ \min_w \sum_{i=1}^n \left\|x_i - \sum_{j=1}^n w_{ij} x_j\right\| \]

其中 \(w_{ij}\) 满足稀疏性条件，仅在离 \(x_i\) 最近的 \(k\) 个点处赋值，且 \(\sum_{j \in Q_i} w_{ij} = 1\)。

降维后依然能被线性表示：

\[ \min_z \sum_{i=1}^n \left\|z_i - \sum_{j=1}^n w_{ij} z_j\right\|, \quad Z^T Z = I \]

转化为：\(\min \text{tr}(Z^T M Z)\)，其中 \(M = (I - W^T)(I - W)\)。

1.5 度量学习

降维的目的是正确认识数据，用更简单的方法衡量之间的关系。这实际上就是要靠度量。

k-近邻算法（KNN）：

假设数据仅仅与周围的 \(k\) 个数据点有关。给定训练数据集，对于新加入的点，找出离它最近的 \(K\) 个元素，哪个类别多就选哪个。

两个关键：

  1. 如何衡量"远近" —— 选取度量
  2. \(k\) 的大小 —— \(k\) 越大，误差越大，方差相对减小；\(k\) 越小，模型越"复杂"，越容易捕获复杂边界

近邻成分分析（NCA）：

兼听则明，不均等听取少数人的建议：

\[ p_{ij} = \frac{\exp(-\|x_i - x_j\|_M)}{\sum_{l=1}^m \exp(-\|x_i - x_l\|_M)} \]

第 \(i\) 个样本分类正确的概率：

\[ p_i = \sum_{j \in \Omega_i} p_{ij} \]

目标：\(\arg\min_M 1 - \sum_{i=1}^n \sum_{j \in \Omega_i} p_{ij}\)

即适当选取度量：\(\|x\|_M = \sqrt{x^T M x}\)。

二、特征筛选

特征筛选分为两种：

  1. 一个个把重要的特征挑出来
  2. 一个个把不重要的特征筛掉

这是一种贪心的策略，因为 \(n\) 个数据中找最优的 \(k\) 个是 NP-hard 操作。

信息增益：

\[ \text{Gain}(D, a) = \text{Ent}(D) - \sum_{v} \frac{|D^v|}{|D|} \text{Ent}(D^v) \]

2.1 特征筛选策略

策略 说明
Filter 过滤式，先特征选择再训练
Wrapper 包裹式，用学习器性能作为评价
Embedding 嵌入式，训练过程中自动选择

2.2 嵌入式特征选择（L1 正则化）

Lasso 的统计设定、软阈值、基本不等式与慢/快速率见 Ch8 稀疏回归与 Lasso。本节只保留特征筛选视角。

通过直接采取某种损失函数的操作间接实现"减少特征数目"的效果。采取 \(L^1\) 正则会让最终选取的结果落在边界上，实现减小特征的操作。

对于线性回归问题：

\[ \min \|y_i - w x_i\|_2^2 + \lambda \|w\|_1 \]

几乎任何问题都可以塞入一个 \(L_1\) 正则项，但问题会变得难解很多。

近端梯度下降（Proximal Gradient Descent）：

  1. 考虑光滑项的极小化：\(z_t = w_t - \eta \nabla f(w_t)\)

  2. 在 \(w\) 的领域内选取极小化：

    \[ w_{t+1} = \arg\min_w \frac{1}{2\eta} \|w - z_t\|_2^2 + \lambda \|w\|_1 \]

    转化为一个一维的问题，每个 \(w\) 的分量都是独立的。

2.3 稀疏表示与字典学习

预先假定数据分布是"稀疏"的，只有少数几个 basis 组成。

模型：

\[ \min_{B, \alpha} \|x_i - B \alpha_i\|_2^2 + \lambda_i \|\alpha_i\|_1 \]

其中：

  • \(B \in \mathbb{R}^{d \times k}\) 是字典矩阵
  • 每个 \(n\) 维向量 \(x_i\) 由 \(B\) 的 \(k\) 个字符线性组合而成
  • 每个元素只由少数几个元素稀疏表示

这是一个复合优化问题：

  1. 固定字典 \(B\)，为每个样本找到合适的 \(\alpha_i\)
  2. 固定 \(\alpha_i\)，依次更新每一列的字典 \(b_i\)

使用 KSVD 保证稀疏性不会被破坏。

总结

方法 核心思想 适用场景
MDS 保持距离结构 距离已知
PCA 最大方差投影 线性降维
核 PCA 非线性映射 非线性结构
Isomap 测地线距离 流形结构
LLE 局部线性表示 局部线性流形
度量学习 学习距离度量 分类任务
L1 正则化 稀疏约束 特征选择
字典学习 稀疏表示 信号处理

归档时间：2026-03-09
来源：知乎文章
分类：数据科学 / 机器学习 / 降维与特征选择