第10章 降维与度量学习

🎯 学习目标

• 理解降维的动机和高维数据的挑战
• 掌握PCA的原理和实现过程
• 了解度量学习的基本思想
• 理解流形学习的概念

10.1 k近邻学习

🎯 k近邻算法（k-NN）

k近邻（k-Nearest Neighbor, k-NN） 是一种基本的分类与回归方法，基于"物以类聚"的直观想法：给定测试样本，找到训练集中与其最接近的k个样本，通过这k个"邻居"的信息进行预测。

算法流程：

1. 计算测试样本与训练集中所有样本的距离
2. 选出距离最小的k个训练样本
3. 分类任务：投票法，选择k个样本中出现最多的类别
4. 回归任务：平均法，取k个样本标记的平均值

• 优点：简单直观易于理解和实现、无需训练过程（懒惰学习）、适合多分类问题
• 缺点：预测开销大（需计算所有距离）、对高维数据效果差（维度灾难）、对样本不平衡敏感

🔑 关键参数

• k值：k太小容易过拟合（受噪声影响），k太大容易欠拟合（决策边界过于平滑）
• 距离度量：欧氏距离、曼哈顿距离、闵可夫斯基距离、马氏距离等

10.2 低维嵌入

为什么需要降维

高维数据在机器学习中面临诸多挑战，这被称为 "维度灾难"（Curse of Dimensionality）：

• 计算复杂度随维度指数增长
• 高维空间中数据变得稀疏，距离度量失效
• 容易过拟合，需要更多样本
• 可视化困难

降维（Dimensionality Reduction） 通过某种数学变换，将高维数据投影到低维空间，同时尽可能保留数据的内在结构和重要信息。

多维缩放（MDS）

多维缩放（Multi-Dimensional Scaling, MDS） 要求降维后样本间的距离尽可能保持不变。

目标函数：

$$min\sum _{i=1}^n\sum _{j=1}^n(\parallel z_i-z_j\parallel -d_{ij}{)}^2$$

其中 $d_{ij}$ 是原空间中样本 $i$ 和 $j$ 的距离，$\parallel z_i-z_j\parallel$ 是降维后的距离。

💡 经典MDS算法步骤

1. 计算原始空间中样本间的距离矩阵 $D$
2. 构造内积矩阵 $B=-\frac{1}{2}HD{H}^T$（$H$ 是中心化矩阵）
3. 对 $B$ 进行特征值分解：$B=V\mathrm{\Lambda }{V}^T$
4. 取前 $d^{\prime }$ 个最大特征值对应的特征向量，得到降维结果

MDS通过保持距离关系来降维，适合数据可视化和探索性分析。

10.3 主成分分析

🎯 PCA基本思想

主成分分析（Principal Component Analysis, PCA） 是最常用的降维方法，通过线性变换将数据投影到方差最大的方向上。

两种理解角度：

1. 最大化投影方差：找到投影方向，使得数据在该方向上的投影方差最大，保留最多的信息量
2. 最小化重构误差：找到投影方向，使得原始数据与降维重构数据之间的平方误差最小

PCA算法步骤：

1. 对数据进行中心化：$x_i\leftarrow x_i-\mu$（$\mu$ 是样本均值）
2. 计算样本协方差矩阵：$C=\frac{1}{m}X{X}^T$
3. 对协方差矩阵进行特征值分解：$C=V\mathrm{\Lambda }{V}^T$
4. 取前 $d^{\prime }$ 个最大特征值对应的特征向量构成投影矩阵 $W$
5. 对样本进行投影：$z=W^{T}x$

💡 如何选择主成分数量 $d^{\prime }$

常用方法：

• 方差贡献率：选择累积方差贡献率达到85%-95%的主成分
• 交叉验证：通过下游任务性能选择最优维度
• 碎石图（Scree Plot）：观察特征值曲线的"拐点"

• 优点：完全无参数易于实现、各主成分正交消除相关性、有明确的数学解释、可用于数据压缩和去噪
• 缺点：只能进行线性变换、对异常值敏感、主成分可解释性差、假设方差大=信息量大

PCA降维交互演示

3D可视化PCA主成分分析，旋转视角观察数据分布和主成分方向。

水平旋转: 17°

垂直旋转: 17°

显示主成分 显示投影

方差解释比例

X方向0.0%

Y方向0.0%

Z方向0.0%

第一主成分（PC1）解释：0.0%

原始数据点

第一主成分（PC1）

第二主成分（PC2）

投影点

PCA原理：

1. 中心化：将数据平移使均值为0
2. 计算协方差矩阵：衡量特征间的相关性
3. 特征值分解：找到方差最大的方向（主成分）
4. 选择主成分：保留前k个最大特征值对应的特征向量
5. 投影：将数据投影到主成分构成的子空间

目标：在降低维度的同时最大化保留数据的方差（信息量）

10.4 核化线性降维

传统PCA只能进行线性降维。核主成分分析（Kernel PCA, KPCA） 通过核技巧将数据映射到高维特征空间，再在该空间中进行PCA，从而实现非线性降维。

🎯 KPCA核心思想

1. 映射：通过映射 $\varphi$ 将样本从原始空间映射到高维空间
2. 核技巧：不显式计算 $\varphi (x)$，而是通过核函数 $\kappa (x_i,x_j)=\varphi (x_i{)}^T\varphi (x_j)$
3. 特征分解：对核矩阵 $K$ 进行特征值分解
4. 投影：利用特征向量进行降维

常用核函数

• 线性核：$\kappa (x,z)=x^{T}z$（退化为标准PCA）
• 多项式核：$\kappa (x,z)=(x^{T}z+c{)}^d$
• 高斯核（RBF）：$\kappa (x,z)=\exp (-\parallel x-z{\parallel }^2/2{\sigma }^2)$

💡 KPCA vs PCA

KPCA能够捕捉数据的非线性结构，适合处理非线性分布的数据。但计算复杂度更高（需要计算和存储核矩阵），且新样本投影需要保留训练数据。

10.5 流形学习

流形（Manifold） 是局部具有欧氏空间性质的几何体。流形学习（Manifold Learning） 假设高维数据实际上分布在低维流形上，目标是找到这个低维流形结构。

等度量映射（Isomap）

Isomap认为低维流形嵌入在高维空间中，样本间的 测地线距离（沿流形表面的距离）才能真实反映相似度。

1. 构建k近邻图，计算邻域内样本的欧氏距离
2. 用最短路径算法（如Dijkstra）计算任意两点的测地线距离
3. 对测地线距离矩阵应用MDS进行降维

局部线性嵌入（LLE）

LLE假设每个样本可以由其近邻样本线性表示，降维时保持这种局部线性关系。

1. 找到每个样本的k个近邻
2. 计算重构权重 $W$，使得 $x_i\approx \sum _j{w}_{ij}{x}_j$（邻域内线性重构）
3. 保持权重 $W$ 不变，在低维空间中求解坐标 $Z$，使得 $z_i\approx \sum _j{w}_{ij}{z}_j$

t-SNE

t-分布随机邻域嵌入（t-SNE） 专门用于数据可视化，能够在二维或三维空间中很好地展示高维数据的簇结构。

核心思想：在高维空间中用高斯分布建模样本相似度，在低维空间中用t分布建模，通过KL散度优化，使得高维和低维的概率分布尽可能接近。

⚠️ 注意

流形学习方法通常计算复杂度高，不适合大规模数据；且很多方法（如LLE、Isomap）难以处理新样本（out-of-sample）。

10.6 度量学习

在许多机器学习任务中，距离度量至关重要（如k-NN、聚类）。度量学习（Metric Learning） 旨在学习一个合适的距离度量，使得同类样本距离近、异类样本距离远。

马氏距离

$$dis{t}_M^2(x_i,x_j)=(x_i-x_j{)}^{T}M(x_i-x_j)$$

其中 $M$ 是半正定矩阵。当 $M=I$（单位矩阵）时退化为欧氏距离。度量学习的目标就是学习合适的矩阵 $M$，使得距离度量符合任务需求。

典型度量学习方法

📊 近邻成分分析（NCA）

通过优化k-NN分类器的留一法准确率来学习线性变换矩阵。使用随机近邻的概率模型，最大化正确分类的概率。

📊 大间隔最近邻（LMNN）

目标：使每个样本的k个同类近邻尽可能接近，同时异类样本保持足够距离（间隔）。同时优化两个目标：1）拉近目标近邻（target neighbors）；2）推开不同类的入侵者（imposters）。

📊 深度度量学习

使用深度神经网络学习嵌入空间（embedding space），常用的损失函数包括：

• 对比损失（Contrastive Loss）：成对样本
• 三元组损失（Triplet Loss）：锚点、正样本、负样本
• N-pair Loss：同时考虑多个负样本

💡 应用场景

• 人脸识别：学习人脸特征空间，使同一人的不同照片距离近
• 图像检索：学习语义相似度度量
• 推荐系统：学习用户和物品的嵌入表示
• 零样本学习：通过度量学习泛化到未见过的类别

📝 本章小结

总结

• ✅ 维度灾难是高维数据面临的核心挑战，降维是重要的解决手段
• ✅ PCA通过最大化投影方差实现线性降维，是最常用的降维方法
• ✅ 核PCA通过核技巧扩展PCA以处理非线性结构
• ✅ 流形学习方法（Isomap、LLE、t-SNE）适合非线性降维和数据可视化
• ✅ 度量学习通过学习距离函数来改善分类和检索性能