降维与度量分析
k近邻学习（KNN）
- 思想：一个样本的类别或值，可以由其周围“最像的”（即最近邻的）几个样本的类别或值来决定
- 核心参数：K值、距离度量和决策规则
-
错误率估计：泛化错误率不超过贝叶斯最优分类器错误率的两倍
-
优点：
- 直观易懂：原理简单，易于理解和解释。
- 无需训练：是一种“惰性学习”算法。训练阶段只是把数据存储起来，开销为零。真正的计算发生在预测（查询）阶段。
- 对数据分布没有假设：不像其他算法（如朴素贝叶斯）需要假设数据服从某种分布。
- 可用于非线性问题：由于是基于实例的学习，可以拟合非常复杂的决策边界
-
缺点：
- 计算复杂度高：预测时需要计算待测样本与所有训练样本的距离。当数据集很大、特征很多时，预测速度非常慢。
- 对不相关特征和尺度敏感：尺度敏感：如果某个特征的数值范围非常大（如工资），它会主导距离计算，而数值范围小的特征（如年龄）则几乎不起作用。因此，数据标准化/归一化是使用KNN前的必要步骤。
低维嵌入
- 多维缩放方法（MDS, Multiple Dimensional Scaling）旨在寻找一个低维子空间，使得距离和样本原有距离近似不变
- 寻找低维子空间尽量保持样本内积不变，思路：特征值分解（常用技巧）
主成分分析（PCA）
输入：
- 样本集D={x_1,x_2,...,x_m}
- 低维空间维度d'
过程：
- 对所有样本进行中心化：\(x_i \leftarrow x_i -\frac{1}{m}\Sigma_{i=1}^mx_i\)
- 计算样本的协方差矩阵 \(XX^T\)
- 对协方差矩阵 \(XX^T\) 做特征值分解
- 取最大的d'的特征值对应的特征向量 \(w_1,\dots, w_{d'}\)
输出：投影矩阵 \(W=(w_1,\dots,w_{d'})\)
- 降维后低维空间的维数 d' 通常是由用户事先指定，或通过在 d' 值不同的低维空间中对近邻分类器(或其他开销较小的学习器)进行交叉验证来选取较好的 d' 值.
- 对 PCA，还可从重构的角度设置一个重构阈值，例如 t= 95后选取使下式成立的最小 d' 值:
\[
\frac{\Sigma_{i=1}^{d'}\lambda_i}{\Sigma_{i=1}^d\lambda_i}\geq t
\]
- PCA 仅需保留W与样本的均值向量即可通过简单的向量减法和矩阵-向量乘法将新样本投影至低维空间中
PCA 与LDA对比
- PCA：会选择数据“拉得最开”的方向（方差最大方向），可能混合两类。
- LDA：会选择将两类中心尽量分开、同时每类内部尽量紧凑的方向。
PCA与LDA的区别与联系
一、核心区别
| 维度 | PCA（主成分分析） | LDA（线性判别分析） |
|---|---|---|
| 目标 | 最大化数据方差，保留最多的变异信息 | 最大化类间距离，最小化类内距离，提升分类能力 |
| 监督性 | 无监督，不利用标签信息 | 有监督，依赖样本类别标签 |
| 优化准则 | 数据协方差矩阵的最大特征向量 | 类间散度矩阵与类内散度矩阵的广义特征向量 |
| 降维上限 | 最多降到特征数 \(d\)（或样本数-1） | 最多降到 类别数 \(C - 1\) |
| 适用场景 | 数据可视化、去噪、预处理 | 分类任务的特征降维 |
| 数学本质 | 正交变换，寻找数据变化最大方向 | 寻找能最佳区分类别的投影方向 |
二、重要联系
- 均为线性降维方法：通过线性变换将数据投影到低维空间。
- 均基于特征值分解：核心步骤都涉及求解矩阵的特征值与特征向量。
- 可结合使用：实践中可先用PCA降维去噪（如降至 \(C\) 维以上），再用LDA进一步降至 \(C-1\) 维，以避免小样本问题。
- 均为全局嵌入：都考虑全局数据分布（而非局部结构）。
核化线性降维
流形学习
- 关键假设：很多高维数据并非“散乱”分布，而是近似分布在一个更低维的弯曲流形上（想象三维空间中的一张二维曲面）。
等度量映射（ISOMAP）
- 核心思路：将高维流形数据降到低维，保持数据点间的“真实距离”（即流形上的测地距离，而非直线欧氏距离）。
流程：
- 构建邻接图：为每个点找K近邻或ε邻域，连接邻域点。
- 计算测地距离：用图中最短路径距离（如Dijkstra算法）近似两点在流形上的真实弯曲距离。
- 多维尺度分析：将测地距离矩阵输入MDS算法，得到在低维空间中保持这些距离的坐标。
局部线性嵌入（LLE）
- 目标：降维后保持每个样本点与其邻域点之间的线性重构关系。
- 核心：局部线性，全局拼接——每个点的局部邻域是线性的，通过保持这些局部线性关系来获得全局非线性低维嵌入。
度量学习
- 核心目标：学习一个“量身定制”的距离度量函数，使得在这个新的度量空间下，相似样本距离更近，不相似样本距离更远，从而提升后续任务（如分类、检索、聚类）的性能。