上一章：机器学习09——聚类
下一章：机器学习11——特征选择与稀疏学习
机器学习实战项目：【从 0 到 1 落地】机器学习实操项目目录：覆盖入门到进阶，大学生就业 / 竞赛必备

一、k近邻学习（kNN）

k近邻学习是一种简单的监督学习方法，核心是基于距离度量找到测试样本的近邻，通过近邻的标签预测结果。

（一）基本原理

• 核心步骤：

  1. 确定训练样本和距离度量（如欧氏距离）；
  2. 对测试样本，找到训练集中距离最近的k个样本；
  3. 分类任务用“投票法”（取k个样本中最多的类别），回归任务用“平均法”（取k个样本输出的平均值）；也可基于距离加权，近邻权重更大。

• 关键参数：

  • k值：k=1时为最近邻分类器，k越大模型越简单（欠拟合风险增加），k越小越容易过拟合；
  • 距离度量：不同度量会导致“近邻”定义不同，直接影响分类结果。

• 学习类型：

  • “懒惰学习”：训练阶段仅存储样本，无训练开销，测试时才计算距离（如kNN）；
  • “急切学习”：训练阶段即学习模型（如SVM、决策树）。

• 性能分析：
  最近邻分类器（k=1）的泛化错误率不超过贝叶斯最优分类器错误率的两倍，前提是训练样本“密采样”（任意测试样本附近都有训练样本）。

二、维数灾难与降维

高维空间中样本稀疏、距离计算困难的问题称为“维数灾难”，降维是主要解决途径，核心是将高维数据映射到低维子空间。

（一）维数灾难的表现

• 高维空间中，满足“密采样”所需样本数呈指数增长（如1000个样本可满足1维密采样，20维则需$10^{60}$个样本）；
• 距离计算可靠性下降，甚至内积计算都变得困难。

（二）降维的可行性

高维数据往往隐含低维结构（如三维空间中的曲面可嵌入二维），即“低维嵌入”，因此可通过数学变换提取有效低维特征。

三、多维缩放（MDS）

MDS通过保持样本间的距离，将高维数据映射到低维空间，核心是“距离不变性”。

（一）核心目标

给定高维空间的距离矩阵$D$（$dis{t}_{ij}$为样本$x_i$与$x_j$的距离），找到低维空间表示$z_i$，使$\Vert z_i-z_j\Vert =dis{t}_{ij}$。

（二）算法步骤

1. 计算内积矩阵$B$：通过距离公式推导$b_{ij}=-\frac{1}{2}(dis{t}_{ij}^2-dis{t}_{i.}^2-dis{t}_{.j}^2+dis{t}_{..}^2)$，其中$dis{t}_{i.}^2$为第i行距离的均值；
2. 特征值分解：对$B$做特征值分解，取前$d^{\prime }$个最大特征值及对应特征向量；
3. 低维映射：低维坐标为$Z={\tilde{\Lambda }}^{1/2}{\tilde{V}}^T$（$\tilde{\Lambda }$为前$d^{\prime }$个特征值构成的对角矩阵，$\tilde{V}$为对应特征向量）。

（三）扩展

实际应用中可放宽“严格距离不变”，仅需低维距离尽可能接近原始距离，以实现有效降维。

四、主成分分析（PCA）

PCA是最常用的线性降维方法，通过寻找数据的主成分（最大方差方向），保留主要信息。

（一）核心思想

• 最近重构性：样本到低维超平面的距离最小（重构误差最小）；
• 最大可分性：样本在低维超平面上的投影方差最大，信息保留最多。

（二）算法步骤

1. 中心化：对所有样本去均值（$x_i\leftarrow x_i-\bar{x}$，$\bar{x}$为样本均值）；
2. 计算协方差矩阵：$X{X}^T$（$X$为中心化后的样本矩阵）；
3. 特征值分解：对协方差矩阵分解，取前$d^{\prime }$个最大特征值对应的特征向量构成投影矩阵$W$；
4. 映射：低维坐标为$z_i=W^T{x}_i$。

（三）低维维数$d^{\prime }$的选择

• 交叉验证：在不同$d^{\prime }$下训练模型（如kNN），选择性能最优值；
• 重构阈值：选取最小$d^{\prime }$使$\frac{{\sum }_{i=1}^{d^{\prime }}{\lambda }_i}{{\sum }_{i=1}^d{\lambda }_i}\ge t$（$t$为阈值，如0.95）。

（四）优势

• 计算简单，可去噪（最小特征值常对应噪声，舍弃后提升鲁棒性）；
• 新样本可直接通过投影矩阵映射到低维空间。

五、流形学习

流形学习假设高维数据分布在低维流形上（局部与欧氏空间同胚），通过局部距离推广到全局，实现非线性降维。

（一）核心概念

• 流形：局部与欧氏空间同胚的空间（如球面局部像平面）；
• 测地线距离：流形上两点的真实距离（高维空间直线距离可能不反映真实邻近关系）。

（二）Isomap算法（典型流形学习方法）

1. 构建近邻图：对每个样本，用欧氏距离找k近邻，近邻间距离为欧氏距离，非近邻为无穷大；
2. 计算测地线距离：通过Dijkstra或Floyd算法计算近邻图上的最短路径，作为样本间真实距离；
3. MDS降维：将测地线距离作为MDS的输入，得到低维坐标。

（三）应用

适合可视化（降维至2D/3D），但计算复杂度高， scalability较差。

六、度量学习

度量学习直接学习合适的距离度量，替代欧氏距离，提升近邻学习等任务的性能。

（一）距离度量的扩展

• 加权欧氏距离：为不同属性分配权重$w_i$，$dis{t}^2=(x_i-x_j{)}^{T}W(x_i-x_j)$（$W$为对角矩阵，$W_{ii}=w_i$）；
• 马氏距离：用半正定矩阵$M$建模属性相关性，$dis{t}^2=(x_i-x_j{)}^{T}M(x_i-x_j)$，$M$为度量矩阵。

（二）学习目标

通过优化任务性能（如kNN分类准确率）学习$M$，若$M$为低秩矩阵，可提取投影矩阵$P$实现降维（$z=P^{T}x$）。

总结

降维与度量学习通过提取低维有效特征或优化距离度量，缓解维数灾难。kNN是简单的近邻学习方法，MDS和PCA是经典线性降维方法，流形学习适用于非线性数据，度量学习则直接优化距离以提升任务性能。实际应用中需根据数据特性选择方法（线性/非线性、可解释性要求等）。

上一章：机器学习09——聚类
下一章：机器学习11——特征选择与稀疏学习
机器学习实战项目：【从 0 到 1 落地】机器学习实操项目目录：覆盖入门到进阶，大学生就业 / 竞赛必备