第10章：降维与度量学习 — 西瓜书学习笔记

本文是周志华《机器学习》（西瓜书）第10章 降维与度量学习（Dimensionality Reduction）的学习笔记，涵盖本章所有核心知识点，配有通俗类比与公式推导。

01. k 近邻学习（kNN）

最简单的”懒惰学习”算法

🔢 核心思想

**k近邻学习（k-Nearest Neighbor，kNN）是一种懒惰学习（lazy learning）**算法——它不构建显式的模型，而是在预测时直接找到训练集中最近的 $k$ 个样本，用它们的标记来决策。

🍎 通俗理解

你搬到一个新城市，不知道周围的餐厅好不好吃。怎么判断？看最近的几家邻居餐厅的口碑——大家都说好，这家大概也不错。这就是 kNN 的逻辑：我不认识你，但我知道你的邻居，通过邻居来判断你。

📐 kNN 分类规则

给定测试样本 $x$，找其最近的 $k$ 个训练样本构成集合 $N_k(x)$，通过投票决定类别：

$$\hat{y} = \underset{c \in \mathcal{Y} }{\arg\max} \sum_{x_i \in N_k(x)} \mathbb{1}(y_i = c)$$

即：哪个类别在 $k$ 个邻居中出现次数最多，就预测为哪类。

🔢 泛化误差界（重要理论结果）

📐 最近邻分类器的误差界

设最优贝叶斯分类器的误差率为 $\epsilon^*$，则在样本数 $m \to \infty$ 时，最近邻分类器（1NN）的泛化误差满足：

$$\epsilon^{1\text{NN} } \le 2\epsilon^* - \frac{n}{n-1}(\epsilon^*)^2 \le 2\epsilon^*$$

✅ 结论：最近邻分类器的误差率不超过贝叶斯最优误差率的 2 倍。

🍎 通俗理解

就算是最聪明的分类器（贝叶斯最优），由于数据本身的噪声，也会犯一些错误（误差率 $\epsilon^*$）。而最简单的1NN，它的错误率最多是最优分类器的2倍。这说明 kNN 虽然简单，但并不差！

🔢 维数灾难（Curse of Dimensionality）

⚠️ 什么是维数灾难？

在高维空间中，样本变得极度稀疏，任意两个样本之间的距离都趋于相等——这使得”近邻”的概念失去意义！

🍎 通俗理解

一维：把100个人站在100米长的走廊里，平均每米1个人，邻居很近。
二维：100个人散布在100×100的广场上，密度变稀。
三维：100个人散布在100×100×100的大楼里，几乎每人独占一层！

维度越高，相同数量的样本越稀疏，距离度量越不可靠。这就是维数灾难。

🔑 解决方案：降维

降维的目标是在保留数据关键结构的前提下，将高维数据映射到低维空间，缓解维数灾难。有两大类降维方法：

线性降维：PCA、MDS——用线性变换映射

非线性降维：流形学习（Isomap、LLE）——保留非线性结构

02. 低维嵌入与多维缩放（MDS）

保持样本间距离不变的降维

🌐 低维嵌入的目标

在原始高维空间中，样本 $x_i$ 的欧氏距离不能直接反映其真实的相似性（维数灾难）。**低维嵌入（low-dimensional embedding）**的目标是：找到一个低维空间中的表示 $z_i$，使得原本在高维空间中的距离关系在低维空间中尽量保持不变。

🍎 通俗理解

把一张世界地图（三维球面）展开成平面地图——虽然面积会有些失真，但我们尽量保留各城市之间的相对距离关系。这就是低维嵌入的思想：从高维”展开”到低维。

🌐 多维缩放（MDS）

多维缩放（Multi-Dimensional Scaling，MDS）的目标是：在低维空间中，保持样本之间的欧氏距离不变。

📐 MDS 核心推导

设原始空间中样本 $x_i, x_j$ 的距离为 $\text{dist}_{ij}$，目标是找低维表示 $z_i \in \mathbb{R}^{d'}$，使 $\|z_i - z_j\| = \text{dist}_{ij}$。

定义内积矩阵 $B$，其中 $b_{ij} = z_i^T z_j$，则：

$$\text{dist}_{ij}^2 = \|z_i\|^2 + \|z_j\|^2 - 2z_i^Tz_j = b_{ii} + b_{jj} - 2b_{ij}$$

通过令样本中心化（$\sum_i z_i = 0$），可以从距离矩阵 $D$ 计算出内积矩阵 $B$：

$$b_{ij} = -\frac{1}{2}\left(\text{dist}_{ij}^2 - \frac{1}{m}\sum_j\text{dist}_{ij}^2 - \frac{1}{m}\sum_i\text{dist}_{ij}^2 + \frac{1}{m^2}\sum_{i,j}\text{dist}_{ij}^2\right)$$

对 $B$ 进行特征值分解 $B = V\Lambda V^T$，取最大的 $d'$ 个特征值，得到低维嵌入 $Z = \Lambda_{d'}^{1/2}V_{d'}^T$。

MDS Algorithm
输入：距离矩阵 D（m×m），目标维度 d'
输出：低维嵌入矩阵 Z（m×d'）

// 1. 计算双中心化内积矩阵 B
B[i][j] = -1/2 · (dist²ᵢⱼ - avg_row_i - avg_col_j + avg_all)

// 2. 对 B 进行特征值分解
B = V · Λ · Vᵀ  (Λ 是特征值对角矩阵，降序排列)

// 3. 取前 d' 个最大特征值/向量
Λ_d' = diag(λ₁,...,λ_d')，V_d' = [v₁,...,v_d']

// 4. 输出低维嵌入
Z = Λ_d'^(1/2) · V_d'ᵀ

03. 主成分分析（PCA）

最重要的线性降维方法

📊 两种等价理解

🎯 视角1：最大可分性

找到一个投影方向，使得样本在该方向上的方差最大（投影后的点尽量散开，信息损失最少）。

🎯 视角2：最小重构误差

找到一组低维坐标轴，使得用低维表示重构回高维时的误差最小（最能”还原”原始数据）。

🍎 通俗理解 PCA

想象你有一团在三维空间中散布的数据点，但它们大体上分布在一个斜面上（其实是二维的）。PCA 就是找到这个斜面最主要的两个方向（主成分），把所有点”压平”到这个斜面上，用二维坐标来表示它们。方差最大的方向就是数据变化最多、信息最丰富的方向。

📊 PCA 推导

📐 最大方差推导

设数据矩阵为 $X$（已中心化，$\sum_i x_i = 0$），投影方向为单位向量 $w$，则投影后的方差为：

$$\text{Var}(w) = \frac{1}{m}\sum_{i=1}^m (w^T x_i)^2 = w^T \left(\frac{1}{m}\sum_{i=1}^m x_i x_i^T\right) w = w^T \Sigma w$$

其中 $\Sigma = \dfrac{1}{m}\sum_{i=1}^m x_i x_i^T = \dfrac{1}{m}X^TX$ 是协方差矩阵（样本已中心化）。

约束 $\|w\|=1$ 下最大化方差，用拉格朗日乘数法：

$$\Sigma w = \lambda w$$

即 $w$ 是协方差矩阵 $\Sigma$ 的特征向量，$\lambda$ 是对应的特征值！最大方差方向对应最大特征值的特征向量。

📐 最小重构误差（等价视角）

设用 $d'$ 个方向来重构，则重构误差为：

$$\min_{W} \sum_{i=1}^m \|x_i - W W^T x_i\|^2$$

其中 $W = [w_1, w_2, \ldots, w_{d'}]$ 是投影矩阵（列正交）。此优化问题的解恰好也是协方差矩阵 $\Sigma$ 前 $d'$ 个最大特征值对应的特征向量。两种视角殊途同归！

📊 PCA 算法步骤

1. 中心化：对所有样本减去均值 $\bar{x} = \frac{1}{m}\sum_i x_i$，使 $\sum_i x_i = 0$
2. 计算协方差矩阵：$\Sigma = \frac{1}{m}X^T X$（或用 SVD 分解 $X$）
3. 特征值分解：对 $\Sigma$ 求特征值 $\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_n$ 及对应特征向量 $w_1, w_2, \ldots, w_n$
4. 选主成分：取前 $d'$ 个特征向量构成投影矩阵 $W^* = [w_1, \ldots, w_{d'}]$
5. 降维投影：每个样本的低维表示 $z_i = W^{*T} x_i \in \mathbb{R}^{d'}$

PCA Algorithm
输入：数据集 D={x₁,...,xₘ}，目标维度 d'
输出：投影矩阵 W*，降维后的数据

// 1. 中心化
x̄ = (1/m) Σᵢ xᵢ
xᵢ ← xᵢ - x̄ (for all i)

// 2. 计算协方差矩阵
Σ = (1/m) · XᵀX

// 3. 特征值分解（或等价的 SVD）
Σ = VΛVᵀ,  λ₁ ≥ λ₂ ≥ ... ≥ λₙ

// 4. 取前 d' 个特征向量
W* = [w₁, w₂, ..., w_d']

// 5. 投影
return W*,  zᵢ = W*ᵀ xᵢ

🔑 如何选择 d’（降维目标维数）

通常设置方差解释率阈值（如 95%），选最小的 $d'$ 使得前 $d'$ 个主成分的方差占总方差的 95% 以上：

$$\frac{\sum_{i=1}^{d'} \lambda_i}{\sum_{i=1}^{n} \lambda_i} \ge 0.95$$

⚠️ PCA 的局限

• 只能捕捉线性结构，对于非线性流形效果差
• 对离群点敏感（协方差矩阵会被少量极端值影响）
• 降维后特征失去可解释性（主成分是原始特征的线性组合）

04. 核化线性降维（KPCA）

用核技巧扩展 PCA 到非线性

🔮 核心思想

PCA 只能做线性降维。核化 PCA（KPCA）利用核技巧（kernel trick）：先用非线性映射 $\phi: \mathcal{X} \to \mathbb{F}$ 将样本映射到高维特征空间 $\mathbb{F}$，再在该空间中做 PCA。由于核技巧的存在，不需要显式计算 $\phi(x)$，只需要核函数 $k(x_i, x_j) = \phi(x_i)^T\phi(x_j)$。

📐 KPCA 的解

在高维特征空间中，协方差矩阵 $\hat{\Sigma} = \frac{1}{m}\sum_i \phi(x_i)\phi(x_i)^T$，PCA 的特征向量满足：

$$\hat{\Sigma} w = \lambda w \Rightarrow w = \sum_{i=1}^m \alpha_i \phi(x_i)$$

代入可得核矩阵 $K$（$K_{ij} = k(x_i, x_j)$）的特征方程：

$$K\alpha = \lambda m \alpha$$

新样本 $x$ 的投影为：$z_j = w_j^T \phi(x) = \sum_{i=1}^m \alpha_i^j k(x_i, x)$

🍎 通俗理解

如果数据在二维中呈圆形分布（非线性），PCA 会失效。KPCA 的做法是：先把数据映射到三维（如 $\phi(x,y) = (x, y, x^2+y^2)$），在三维中数据变成了线性可分的，再做 PCA 降回低维。核函数让这个过程不用真的计算三维坐标，直接通过”内积”完成。

05. 流形学习

Isomap 与 LLE：保留流形结构的非线性降维

🌀 流形假设

**流形（Manifold）**是指高维空间中的一个低维连续曲面。流形假设认为：高维数据实际上分布在一个低维流形的附近，降维的目标是找到这个低维流形的坐标。

🍎 经典案例：瑞士卷

把一张纸卷成螺旋形（瑞士卷）后随机撒点，数据是三维的，但真正的结构是二维的（纸本身是平面）。
欧氏距离会认为卷的两端很近，但沿纸面走其实很远——流形学习就是要”展开”这张纸，恢复真实的二维结构。

🌀 等度量映射（Isomap）

Isomap 的核心想法：用测地线距离代替欧氏距离，然后对测地线距离矩阵做 MDS。

📐 测地线距离的近似

无法直接计算流形上的测地线，Isomap 用最短路径来近似：

1. 建立 $k$ 近邻图（每个点连接最近的 $k$ 个邻居）
2. 在图中用 Dijkstra/Floyd 算法计算所有点对的最短路径，作为测地线距离的近似 $d_G(x_i, x_j)$
3. 对测地线距离矩阵做 MDS，得到低维嵌入

Isomap Algorithm
输入：数据 D，近邻数 k，目标维度 d'
// 1. 建近邻图
for each xᵢ: 连接最近的 k 个邻居，边权 = 欧氏距离
// 2. 计算最短路径（测地线近似）
用 Floyd/Dijkstra 算法计算所有点对的最短路径距离 d_G
// 3. 对测地线距离矩阵做 MDS
return MDS(d_G, d')

⚠️ Isomap 的局限

• 无法处理短路问题：若 $k$ 太大或数据有噪声，近邻图会出现”短路”（把两个流形上较远的点连成邻居），破坏测地线估计
• 时间复杂度高：$O(m^2 \log m)$
• 无法直接处理新样本（需要重新计算）

🌀 局部线性嵌入（LLE）

LLE 的想法：每个样本可以用其邻居的线性组合来近似表示。降维后，这种线性组合关系应该保持不变。

📐 LLE 两步优化

Step 1：学习重构权重

对每个 $x_i$，找邻居 $Q_i$，最小化重构误差：

$$\min_{w_{ij} } \sum_i \left\|x_i - \sum_{j \in Q_i} w_{ij} x_j\right\|^2 \quad \text{s.t.} \sum_{j \in Q_i} w_{ij} = 1$$

Step 2：保持权重不变，求低维坐标

给定权重 $w_{ij}$，求低维坐标 $z_i$ 使得：

$$\min_{z_i} \sum_i \left\|z_i - \sum_{j \in Q_i} w_{ij} z_j\right\|^2$$

此优化等价于对矩阵 $M = (I-W)^T(I-W)$ 进行特征值分解，取最小的 $d'$ 个非零特征值对应的特征向量。

🍎 通俗理解 LLE

在流形上，每个人的位置可以用他的几个邻居加权平均来近似描述（就像”你的位置 = 0.3×A + 0.5×B + 0.2×C”）。LLE 先学出这些权重，然后在低维空间中尽量重现这些”邻居关系”，就得到了展开后的低维坐标。

✅ LLE 的优点

• 只考虑局部结构，不受全局失真影响，更鲁棒
• 计算效率较高（稀疏矩阵操作）
• 适合局部结构规则的流形

06. 度量学习

从数据中学习合适的距离度量

📐 为什么需要度量学习？

欧氏距离假设所有特征维度同等重要，但实际上不同维度的重要性不同。度量学习（Metric Learning）的目标是从数据中学习一个马氏距离，使得学到的距离更适合当前任务。

📐 马氏距离（Mahalanobis Distance）

$$\text{dist}_M(x_i, x_j) = \sqrt{(x_i - x_j)^T M (x_i - x_j)}$$

其中 $M$ 是半正定矩阵。当 $M=I$ 时退化为欧氏距离；当 $M$ 为对角矩阵时等价于对各维度加权的欧氏距离。

可以将 $M$ 分解为 $M = P^T P$（$P$ 是线性变换矩阵），则：

$$\text{dist}_M(x_i, x_j) = \|P(x_i - x_j)\|$$

即：度量学习等价于学习一个线性变换 $P$，在变换后的空间中用欧氏距离。

🍎 通俗理解

普通欧氏距离就像用一把一视同仁的尺子量距离。而马氏距离就像根据实际情况对不同维度伸缩/旋转——比如判断两个人是否相似时，身高差1cm可能比体重差1kg更重要，度量学习会自动找到这个权重。

📐 度量学习的约束与目标

📐 “必连”与”勿连”约束

典型的度量学习设置：给定样本集 $D$，以及：

• 必连集合 $\mathcal{S}$：$(x_i, x_j) \in \mathcal{S}$ 表示 $x_i, x_j$ 应该相似（同类），学到的距离应尽量小
• 勿连集合 $\mathcal{D}$：$(x_i, x_k) \in \mathcal{D}$ 表示 $x_i, x_k$ 应该不相似（异类），学到的距离应尽量大

优化目标（以 LMNN 为例）：最小化同类邻居间的距离，同时让异类样本的距离大于同类样本距离 + 间隔 $\gamma$。

💡 度量学习 vs 特征选择

• 特征选择：选哪些维度用（0/1选择）
• 度量学习：每个维度用多少权重（连续调整）
• 两者都是为了找到更好的特征表示，但度量学习更灵活

07. 对比总结

方法	类型	保持的性质	核心操作	适用场景
MDS	线性	样本间欧氏距离	矩阵双中心化 + 特征分解	已有距离矩阵，想做可视化
PCA	线性	最大方差 / 最小重构误差	协方差矩阵特征分解	数据线性结构明显，去相关
KPCA	非线性	高维特征空间中的方差	核矩阵特征分解	数据有非线性结构，需核方法
Isomap	非线性（流形）	测地线距离	近邻图最短路 + MDS	全局流形结构规则
LLE	非线性（流形）	局部线性重构权重	稀疏特征值分解	局部结构规则，大规模数据
度量学习	有监督	类内距离小、类间距离大	学习半正定矩阵 M	有类别信息，需定制距离

🔑 考试高频考点

• 📌 PCA 的两种等价解释（最大方差 vs 最小重构误差）及推导
• 📌 PCA 算法步骤：中心化→协方差→特征分解→取前d’个
• 📌 维数灾难的概念和成因
• 📌 Isomap vs LLE：全局vs局部，测地线vs重构权重
• 📌 马氏距离的形式和度量学习的目标
• 📌 kNN 误差界：≤ 2倍贝叶斯误差