知识框架
本章从 kNN 引出距离、维数灾难和降维问题。重点包括 k 近邻、多维缩放、PCA、核 PCA、Isomap、LLE、度量学习、马氏距离和近邻成分分析。
k 近邻学习
kNN 是典型懒惰学习：训练阶段主要存储样本，预测阶段找最近邻。
- 分类：取 $k$ 个近邻的多数类。
- 回归：取 $k$ 个近邻标记均值或加权均值。
- $k$ 小：模型复杂，低偏差高方差。
- $k$ 大：模型平滑，高偏差低方差。
kNN 强依赖距离度量和特征尺度，使用前通常需要标准化。
维数灾难
高维空间中样本会变得稀疏，距离差异可能失去区分性，局部邻域难以可靠估计。降维希望保留主要结构，减少噪声和冗余，提高计算效率与泛化能力。
多维缩放 MDS
MDS 目标是在低维空间中尽量保持样本间距离。设距离矩阵平方为 $\mathbf{D}^{(2)}$，中心化矩阵
\[
\mathbf{J}=\mathbf{I}-\frac{1}{m}\mathbf{1}\mathbf{1}^\top.
\]
内积矩阵可由双中心化得到：
\[
\mathbf{B}=-\frac{1}{2}\mathbf{J}\mathbf{D}^{(2)}\mathbf{J}.
\]
对 $\mathbf{B}$ 特征分解，取最大 $d'$ 个特征值及对应特征向量构造低维坐标。
主成分分析 PCA
PCA 有两种等价理解：
- 最近重构性：低维表示重构回原空间的误差最小。
- 最大可分性：投影后样本方差最大。
计算步骤：
- 中心化：$\tilde{\mathbf{x}}_i=\mathbf{x}_i-\mathbf{\mu}$。
- 求协方差矩阵：$\mathbf{\Sigma}=\frac{1}{m}\tilde{\mathbf{X}}^\top\tilde{\mathbf{X}}$。
- 求特征值和单位特征向量。
- 按特征值从大到小选主成分。
- 投影：$\mathbf{z}_i=\mathbf{W}^\top(\mathbf{x}_i-\mathbf{\mu})$。
方差贡献率：
\[
\frac{\lambda_j}{\sum_{\ell}\lambda_\ell}.
\]
只保留前 $r$ 个主成分的信息损失比例为
\[
1-\frac{\sum_{j=1}^{r}\lambda_j}{\sum_{\ell}\lambda_\ell}.
\]
核化降维与流形学习
- 核 PCA
- 通过核函数在高维特征空间执行 PCA，可处理非线性结构。
- Isomap
- 构造近邻图，用图上最短路径近似测地线距离，再做 MDS。
- LLE
- 对每个样本用近邻线性重构，并在低维空间保持重构权重不变。
PCA 假设全局线性子空间，Isomap 和 LLE 更强调低维流形结构。
度量学习
马氏距离：
\[
d_{\mathbf{M}}(\mathbf{x}_i,\mathbf{x}_j)=
\sqrt{(\mathbf{x}_i-\mathbf{x}_j)^\top\mathbf{M}(\mathbf{x}_i-\mathbf{x}_j)}.
\]
为保证距离非负，$\mathbf{M}$ 应为半正定矩阵。若 $\mathbf{M}=\mathbf{I}$，退化为欧氏距离。度量学习的目标是根据任务学习一个更合适的 $\mathbf{M}$，使相似样本更近、不相似样本更远。
常见问法
- 给二维或三维样本，中心化、求协方差矩阵、特征值和特征向量。
- 指出第一主成分方向，计算投影和方差贡献率。
- 解释只保留部分主成分时的信息损失。
- 比较 PCA、MDS、Isomap、LLE 的保持对象。
- 分析 kNN 中 $k$ 和距离度量对分类边界的影响。
- 写出马氏距离并说明半正定约束的意义。