第7章 基于距离与相似度的方法
在机器学习的世界里，有一类算法不依赖复杂的参数学习过程，而是通过“比较样本间的相似性”来进行预测。 这种思想源于人类的直觉学习方式——我们看到一个新事物时，会下意识地问：
“它像不像我见过的某个东西？”
这类方法的代表是 k-近邻算法（K-Nearest Neighbors, KNN）。 它是“基于实例”的学习（Instance-based Learning）， 也是“惰性学习”（Lazy Learning）的典型代表。
7.1 k-近邻算法（KNN）
✅ 一、算法思想
KNN 的核心思想非常简单：
如果一个样本在特征空间中与某类样本“很接近”， 那它也很可能属于这一类。
KNN 不需要显式训练模型，而是在预测时直接利用整个训练数据。
✅ 二、算法流程
1️⃣ 计算距离： 对测试样本 (x)，计算它与训练集中所有样本 (x_i) 的距离。
2️⃣ 选择邻居： 选取距离最近的 (k) 个样本。
3️⃣ 投票或加权平均：
- 分类任务：多数投票法决定类别。
- 回归任务：取邻居标签的平均值（或加权平均）。
[
\hat{y} =
\begin{cases}
\text{mode}({y_i}{i=1}^k), & \text{分类}
\frac{1}{k} \sum{i=1}^k y_i, & \text{回归}
\end{cases}
]
✅ 三、常见距离度量
| 距离度量 | 数学形式 | 适用场景 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 欧式距离 | ( d(x,y) = \sqrt{\sum_i (x_i - y_i)^2} ) | 连续特征常用 | ||||||||
| 曼哈顿距离 | ( d(x,y) = \sum_i | x_i - y_i | ) | 稀疏数据或L1空间 | ||||||
| 明可夫斯基距离 | ( d(x,y) = (\sum_i | x_i - y_i | ^p)^{1/p} ) | 通用形式 | ||||||
| 余弦相似度 | ( \cos(\theta) = \frac{x \cdot y}{ | x | , | y | } ) | 文本或高维方向性特征 | ||||
| 汉明距离 | 不同位数目 | 离散/二进制特征 |
✅ 四、k 的选择与模型表现
- k 太小 → 对噪声敏感，容易过拟合。
- k 太大 → 模型过于平滑，可能欠拟合。
通常通过交叉验证（Cross-Validation）选取最优的 (k)。
✅ 五、加权 KNN
不是所有邻居都一样重要——越近的样本越可信。 因此可以按距离加权：
[ \hat{y} = \frac{\sum_{i=1}^k \frac{1}{d(x,x_i)} y_i}{\sum_{i=1}^k \frac{1}{d(x,x_i)}} ]
这种方法称为 加权KNN（Weighted KNN），在噪声数据上表现更稳健。
✅ 六、优缺点总结
| 优点 | 缺点 |
|---|---|
| 原理简单，无需训练 | 推理开销大（O(N)） |
| 可用于分类与回归 | 对特征缩放敏感 |
| 可适应复杂边界 | 对噪声敏感 |
| 仅需样本间距离定义 | 难以处理高维数据（维度灾难） |
7.2 相似度度量与特征归一化
KNN 的性能极度依赖于“距离度量”的定义。 换句话说：如何衡量“像不像” 是算法的灵魂。
✅ 一、特征尺度问题
若特征量纲不同，例如：
- 年龄范围是 0–100，
- 收入范围是 0–100000，
则收入特征会主导距离计算，导致不公平。
✅ 二、常见的归一化方法
| 方法 | 公式 | 说明 | ||||
|---|---|---|---|---|---|---|
| Min-Max 归一化 | ( x’ = \frac{x - x_{min}}{x_{max} - x_{min}} ) | 将特征缩放至 [0,1] | ||||
| Z-score 标准化 | ( x’ = \frac{x - \mu}{\sigma} ) | 均值为0，方差为1 | ||||
| L2 归一化 | ( x’ = \frac{x}{ | x | _2} ) | 保留方向信息 |
✅ 三、特征加权
在某些场景中，特征的重要性不同，可以赋予不同权重：
[ d(x, y) = \sqrt{\sum_i w_i (x_i - y_i)^2} ]
特征权重 (w_i) 可通过经验、统计分析或自动学习获得。
✅ 四、高维数据与相似度退化
当维度过高时：
- 所有样本的距离趋于相同（“维度灾难”）；
- 相似度概念逐渐失效。
常用解决方案：
- 特征选择（去冗余）；
- 降维方法（如 PCA、t-SNE）；
- 局部敏感哈希（LSH）：近似搜索加速。
7.3 实例学习与惰性学习思想
✅ 一、与参数学习的对比
传统机器学习（如线性回归、SVM）属于 “参数学习”（Parametric Learning）： 通过训练学习参数 (w)，再用 (w) 进行预测。
而 KNN 属于 “实例学习”（Instance-based Learning）： 它不学习显式参数，直接在样本间比较。
| 对比项 | 参数学习 | 实例学习 |
|---|---|---|
| 学习目标 | 参数 | 样本之间的关系 |
| 训练阶段 | 显式建模 | 无需训练 |
| 推理阶段 | 快速 | 需大量计算 |
| 优化目标 | 最小化损失函数 | 基于距离度量 |
| 举例 | 逻辑回归、SVM | KNN、基于记忆的推理 |
✅ 二、惰性学习（Lazy Learning）
KNN 在训练阶段什么也不做，只在预测时才开始“工作”。 这种模式称为 惰性学习（Lazy Learning），对应的是：
“急切学习（Eager Learning）”——如神经网络。
惰性学习的特点：
- 学习延迟到预测阶段；
- 适合样本分布动态变化的环境；
- 但预测计算量大，难以在线扩展。
✅ 三、从 KNN 到记忆增强学习
KNN 是早期的“记忆型学习”，后来这一思想被深度学习继承并扩展，如：
- Memory Networks（记忆网络）
- Retrieval-Augmented Generation（检索增强生成，RAG）
- Nearest-Neighbor Language Models
这些现代模型的核心仍是相似度匹配，只是通过神经网络学会“如何计算距离”。
总结
| 小节 | 核心思想 | 关键点 |
|---|---|---|
| 7.1 KNN 算法 | 用邻居投票或加权平均做预测 | k 值选择、距离度量 |
| 7.2 相似度与归一化 | 距离定义决定算法灵魂 | 归一化、特征权重、高维问题 |
| 7.3 实例与惰性学习 | 不学习参数，而是存储样本 | 延迟学习思想与现代衍生 |
🌱 思考题 / 延伸阅读
- 为什么 KNN 不需要训练阶段却仍然能“学习”？
- 如何在百万样本上高效实现 KNN？（提示：KD-Tree、Ball-Tree、近似搜索）
- 如果样本分布动态变化（如推荐系统），KNN 是否更有优势？
- 现代大型语言模型（LLM）的“向量检索”与 KNN 有何本质联系？
