04 最近邻分类器 (K-Nearest Neighbors)
90 分钟学习安排：距离 → 邻居 → 样本外选择
目标： 手算并解释距离；解释训练期标准化；在预设欧氏距离与等权投票下用时间验证选择 \(k\)；诊断高维距离集中。
学习顺序：
先修先答： \((0,0)\) 到 \((3,4)\) 的欧氏距离和曼哈顿距离分别是多少？
- 反馈： 欧氏距离为 \(5\)，曼哈顿距离为 \(7\)；应由业务相似性的含义选择距离，而非默认套用。
今天的议题：信用风险评估
假设你是一位信贷经理，一位新客户前来申请贷款。
你的核心任务是：
- 评估风险：这位客户未来违约的可能性有多大？
- 做出决策：是批准还是拒绝这笔贷款？
这是一个典型的商业分类问题。
客户特征 → 距离度量 → 近邻投票 → 风险决策
数据驱动的解决方案
你并非毫无根据地猜测。你的银行拥有宝贵的历史数据。
- 现有数据: 数千名历史客户的完整记录。
- 特征 (Features): 收入、负债、年龄、职业…
- 结果 (Outcome): 按时还款 ✅ 或 违约 ❌
- 我们的方法: 利用这些数据，为新客户的风险画像，这就是最近邻 (KNN) 算法的用武之地。
历史客户记录 → 标准化 → 找到近邻 → 预测新客户类别
KNN的核心思想：“物以类聚，人以群分”
KNN算法的哲学非常简单：要判断一个新样本的类别，只需看离它最近的几个“邻居”属于哪个类别。
就像你要判断一个陌生人的兴趣爱好，最简单的方法就是看看他交往最密切的朋友们都是些什么样的人。
KNN的商业类比
| 新样本 (未知类别) |
一位新的贷款申请人 |
| 邻居 (已知类别) |
数据库中与新申请人情况最相似的历史客户 |
| 类别 |
‘会违约’ 或 ‘不会违约’ |
| “近”的度量 |
客户特征的相似度 (如收入、年龄、负债) |
| K值 |
我们参考多少个相似的客户来做决定？ |
本章学习内容概览
- 核心内容｜先定义近邻规则：距离、\(k\) 与投票如何共同产生预测。
- 核心内容｜先缩放再找邻居：只在训练期拟合标准化器，解释尺度为何改变邻居。
- 核心内容｜按时间选择模型：事先确定欧氏距离与等权投票，只用训练期时间顺序折选择 \(k\)。
- 核心内容｜测试期检查：确定模型后一次报告类别比例、ROC-AUC、AP 与混淆矩阵，并说明边界。
- 拓展内容｜机制与规模：加权 KNN、回归、KD/Ball Tree 与高维概率推导；核心内容只保留一个归一化距离直觉和算法含义。
4.1 最近邻规则 (k-NN) 的正式定义
给定一个待分类样本 \(x_n\)，KNN的决策过程分为两步：
- 寻找邻居: 在整个数据集中，找出与 \(x_n\) 距离最近 的 \(k\) 个样本。
- 投票决策: 在这 \(k\) 个邻居中，采用多数表决的方式，将得票最多的那个类别作为 \(x_n\) 的预测类别。
\[
\large{y_n = \underset{c \in \mathcal{Y}}{\arg\max} \sum_{i=1}^k I(y_i = c)}
\tag{1}\]
其中，\(I(\cdot)\) 是指示函数，如果邻居 \(i\) 的类别 \(y_i\) 等于类别 \(c\)，则为1，否则为0。这个公式本质上就是在数票数。
理解KNN的三个关键要素
要成功应用KNN算法，我们必须明确定义三个核心要素。它们是构建任何KNN模型的基石。
- 距离度量 (Distance Metric)
- \(k\) 值的选择 (The Choice of \(k\))
- 决策规则 (Decision Rule)
关键要素 1: 距离度量
如何定义“近”？这取决于我们选择的距离度量。
关键要素 2: k值的选择
参考多少个邻居？这是模型复杂度的关键开关。
关键要素 3: 决策规则
如何汇总邻居的“意见”？最常见的是少数服从多数。
深入探讨：距离度量
样本间的相似性是通过距离函数来度量的。对于两个 \(d\) 维的样本 \(x_i\) 和 \(x_j\)，常见的距离度量有：
欧几里得距离 (Euclidean Distance): 我们最熟悉的直线距离，也是KNN中最常用的。
\[ \large{L_2(x_i, x_j) = \sqrt{\sum_{l=1}^d (x_{il} - x_{jl})^2}} \]
曼哈顿距离 (Manhattan Distance): 想象在城市街道上开车，只能沿着网格线走。
\[ \large{L_1(x_i, x_j) = \sum_{l=1}^d |x_{il} - x_{jl}|} \]
可视化距离度量
欧几里得距离是“抄近道”，曼哈顿距离是“走街区”。
关键前提：数据标准化
重要提示: 距离度量对特征的尺度 (scale) 非常敏感。
- 问题: 如果“年收入”（单位：万）和“年龄”（单位：岁）直接计算距离，收入的巨大数值会完全主导距离计算，年龄的作用将微乎其微。
- 解决方案: 数据标准化 (Standardization)。将所有特征转换到相似的尺度上（例如，均值为0，标准差为1）。
在应用KNN之前，数据标准化几乎是必不可少的一步。
为什么标准化至关重要？
深入探讨：k值的选择
\(k\) 值的选择直接影响模型的性能，它是一个偏差-方差权衡 (Bias-Variance Tradeoff) 的过程。
- 较小的 \(k\) 值:
- 模型更复杂，决策边界更不规则。
- 容易受到噪声数据的影响，导致过拟合 (Overfitting)。
- 低偏差 (Low Bias)，高方差 (High Variance)。
- 较大的 \(k\) 值:
- 模型更简单，决策边界更平滑。
- 会忽略数据中局部的、细微的结构，导致欠拟合 (Underfitting)。
- 高偏差 (High Bias)，低方差 (Low Variance)。
小 k值: 高度灵活，容易过拟合
当 k 很小时 (例如 k=1)，模型决策边界会变得非常曲折，试图去完美匹配每一个训练数据点，包括噪声。
大 k值: 高度平滑，容易欠拟合
当 k 很大时 (例如 k=N)，模型会忽略数据的局部结构，决策边界变得过于简单，无法捕捉类别间的差异。
寻找最优 k 值
那么，如何找到那个“刚刚好”的 \(k\) 值呢？
我们将在稍后的Python实践中演示这个过程。
让我们通过一个例子来可视化KNN
假设我们有一组关于肿瘤的数据，分为“良性”和“恶性”两类。现在来了一个新的病人（用 ? 表示），我们需要判断其肿瘤是良性还是恶性。
Code
# 导入依赖以支持本页的数据处理、建模或可视化。
import numpy as np
# 导入依赖以支持本页的数据处理、建模或可视化。
import matplotlib.pyplot as plt
# 导入依赖以支持本页的数据处理、建模或可视化。
import seaborn as sns
# 导入依赖以支持本页的数据处理、建模或可视化。
from sklearn.datasets import make_blobs
# 教学说明：--- Generate Data ---。
input_feature_matrix, target_values = make_blobs(n_samples=50, centers=2, random_state=4, cluster_std=1.5)
new_point = np.array([[-3, 8]])
# 展示新病人与已标记肿瘤样本的初始空间关系。
plt.figure(figsize=(10, 6)) # 展示当前步骤的结果。
# 执行 `sns.scatterplot`，生成当前步骤需要的结果或可视化。
sns.scatterplot(x=input_feature_matrix[target_values==0, 0], y=input_feature_matrix[target_values==0, 1], s=120, label='良性 (Benign)', marker='o', color='royalblue', ec='black') # 展示当前步骤的结果。
# 执行 `sns.scatterplot`，生成当前步骤需要的结果或可视化。
sns.scatterplot(x=input_feature_matrix[target_values==1, 0], y=input_feature_matrix[target_values==1, 1], s=120, label='恶性 (Malignant)', marker='X', color='darkorange', ec='black') # 展示当前步骤的结果。
# 执行 `plt.scatter`，生成当前步骤需要的结果或可视化。
plt.scatter(new_point[:, 0], new_point[:, 1], s=300, c='red', marker='P', label='新样本', ec='black', linewidth=1.5) # 展示当前步骤的结果。
# 执行 `plt.title`，生成当前步骤需要的结果或可视化。
plt.title('一个需要被分类的新样本', fontsize=20, pad=15) # 展示当前步骤的结果。
# 执行 `plt.xlabel`，生成当前步骤需要的结果或可视化。
plt.xlabel('特征1 (Texture)', fontsize=20) # 展示当前步骤的结果。
# 执行 `plt.ylabel`，生成当前步骤需要的结果或可视化。
plt.ylabel('特征2 (Radius)', fontsize=20) # 展示当前步骤的结果。
# 执行 `plt.legend`，生成当前步骤需要的结果或可视化。
plt.legend(loc='upper right', fontsize=20) # 展示当前步骤的结果。
# 执行 `plt.grid`，生成当前步骤需要的结果或可视化。
plt.grid(True, linestyle='--', alpha=0.6) # 展示当前步骤的结果。
# 执行 `plt.gca().set_aspect`，生成当前步骤需要的结果或可视化。
plt.gca().set_aspect('equal', adjustable='box') # 展示当前步骤的结果。
# 执行 `plt.tight_layout`，生成当前步骤需要的结果或可视化。
plt.tight_layout() # 展示当前步骤的结果。
# 执行 `plt.show`，生成当前步骤需要的结果或可视化。
plt.show() # 展示当前步骤的结果。
当 k=1 时: 最近的邻居决定一切
1-NN是最简单的KNN形式。我们只看距离最近的那一个邻居。
在这个例子中，离新病人最近的样本是“恶性”类，所以1-NN会将其分类为恶性。这可能是一个受噪声影响的错误判断。
Code
# 教学说明：--- Recalculate from previous cell ---。
input_feature_matrix, target_values = make_blobs(n_samples=50, centers=2, random_state=4, cluster_std=1.5)
new_point = np.array([[-3, 8]])
# 教学说明：--- Calculate Distances ---。
distances_k1 = np.sqrt(np.sum((input_feature_matrix - new_point)**2, axis=1))
nearest_neighbor_idx = np.argmin(distances_k1)
# 突出唯一最近邻，展示 1-NN 对局部噪声的敏感性。
plt.figure(figsize=(10, 6)) # 展示当前步骤的结果。
# 执行 `sns.scatterplot`，生成当前步骤需要的结果或可视化。
sns.scatterplot(x=input_feature_matrix[target_values==0, 0], y=input_feature_matrix[target_values==0, 1], s=100, label='良性 (Benign)', marker='o', color='royalblue', alpha=0.4) # 展示当前步骤的结果。
# 执行 `sns.scatterplot`，生成当前步骤需要的结果或可视化。
sns.scatterplot(x=input_feature_matrix[target_values==1, 0], y=input_feature_matrix[target_values==1, 1], s=100, label='恶性 (Malignant)', marker='X', color='darkorange', alpha=0.4) # 展示当前步骤的结果。
# 执行 `plt.scatter`，生成当前步骤需要的结果或可视化。
plt.scatter(new_point[:, 0], new_point[:, 1], s=300, c='red', marker='P', label='新病人 (New Patient)', ec='black', linewidth=1.5) # 展示当前步骤的结果。
# 教学说明：Highlight the nearest neighbor。
plt.scatter(input_feature_matrix[nearest_neighbor_idx, 0], input_feature_matrix[nearest_neighbor_idx, 1], s=350,
facecolors='none', edgecolors='green', linewidth=3, label='最近邻 (k=1)')
# 执行 `plt.title`，生成当前步骤需要的结果或可视化。
plt.title('k=1：最近邻为恶性', fontsize=34, pad=15) # 展示当前步骤的结果。
# 执行 `plt.xlabel`，生成当前步骤需要的结果或可视化。
plt.xlabel('特征1 (Texture)', fontsize=34) # 展示当前步骤的结果。
# 执行 `plt.ylabel`，生成当前步骤需要的结果或可视化。
plt.ylabel('特征2 (Radius)', fontsize=34) # 展示当前步骤的结果。
# 执行 `plt.legend`，生成当前步骤需要的结果或可视化。
plt.legend(loc='upper right', fontsize=30) # 展示当前步骤的结果。
plt.tick_params(axis='both', labelsize=30) # 放大刻度文字以满足投影阅读距离。
# 执行 `plt.grid`，生成当前步骤需要的结果或可视化。
plt.grid(True, linestyle='--', alpha=0.6) # 展示当前步骤的结果。
# 执行 `plt.gca().set_aspect`，生成当前步骤需要的结果或可视化。
plt.gca().set_aspect('equal', adjustable='box') # 展示当前步骤的结果。
# 执行 `plt.tight_layout`，生成当前步骤需要的结果或可视化。
plt.tight_layout() # 展示当前步骤的结果。
# 执行 `plt.show`，生成当前步骤需要的结果或可视化。
plt.show() # 展示当前步骤的结果。
当 k=5 时: 多数投票，结果反转
现在，我们将 \(k\) 增加到 5，考察最近的5个邻居。
- 在这5个邻居中，有4个是“良性”，1个是“恶性”。
- 根据多数投票原则 (4 > 1)，5-NN会将其分类为良性。
这个例子清晰地表明了 \(k\) 值的选择对最终结果有决定性影响。
Code
# 教学说明：--- Recalculate from previous cell ---。
input_feature_matrix, target_values = make_blobs(n_samples=50, centers=2, random_state=4, cluster_std=1.5)
new_point = np.array([[-3, 8]])
# 教学说明：--- Calculate Distances ---。
distances_k5 = np.sqrt(np.sum((input_feature_matrix - new_point)**2, axis=1))
neighbor_count = 5
nearest_k_indices = np.argsort(distances_k5)[:neighbor_count]
# 圈出五个最近邻，展示多数投票如何改变分类结果。
plt.figure(figsize=(10, 6)) # 展示当前步骤的结果。
# 执行 `sns.scatterplot`，生成当前步骤需要的结果或可视化。
sns.scatterplot(x=input_feature_matrix[target_values==0, 0], y=input_feature_matrix[target_values==0, 1], s=100, label='良性 (Benign)', marker='o', color='royalblue', alpha=0.3) # 展示当前步骤的结果。
# 执行 `sns.scatterplot`，生成当前步骤需要的结果或可视化。
sns.scatterplot(x=input_feature_matrix[target_values==1, 0], y=input_feature_matrix[target_values==1, 1], s=100, label='恶性 (Malignant)', marker='X', color='darkorange', alpha=0.3) # 展示当前步骤的结果。
# 执行 `plt.scatter`，生成当前步骤需要的结果或可视化。
plt.scatter(new_point[:, 0], new_point[:, 1], s=300, c='red', marker='P', label='新样本', ec='black', linewidth=1.5) # 展示当前步骤的结果。
# 教学说明：Highlight the 5 nearest neighbors。
plt.scatter(input_feature_matrix[nearest_k_indices, 0], input_feature_matrix[nearest_k_indices, 1], s=350,
facecolors='none', edgecolors='green', linewidth=3, label='5 个最近邻')
# 教学说明：Draw a circle enclosing the neighbors。
center = new_point.flatten()
radius = distances_k5[nearest_k_indices[-1]]
circle = plt.Circle(center, radius, color='green', fill=False, linestyle='--', linewidth=2)
# 执行 `plt.gca().add_patch`，生成当前步骤需要的结果或可视化。
plt.gca().add_patch(circle) # 展示当前步骤的结果。
# 执行 `plt.title`，生成当前步骤需要的结果或可视化。
plt.title('k=5：多数投票为良性', fontsize=34, pad=15) # 放大图题以满足投影阅读距离。
# 执行 `plt.xlabel`，生成当前步骤需要的结果或可视化。
plt.xlabel('特征1 (Texture)', fontsize=34) # 放大横轴标题以满足投影阅读距离。
# 执行 `plt.ylabel`，生成当前步骤需要的结果或可视化。
plt.ylabel('特征2 (Radius)', fontsize=34) # 放大纵轴标题以满足投影阅读距离。
# 执行 `plt.legend`，生成当前步骤需要的结果或可视化。
plt.legend(loc='upper right', fontsize=30) # 放大图例以满足投影阅读距离。
plt.tick_params(axis='both', labelsize=30) # 放大刻度文字以满足投影阅读距离。
# 执行 `plt.grid`，生成当前步骤需要的结果或可视化。
plt.grid(True, linestyle='--', alpha=0.6) # 展示当前步骤的结果。
# 执行 `plt.gca().set_aspect`，生成当前步骤需要的结果或可视化。
plt.gca().set_aspect('equal', adjustable='box') # 展示当前步骤的结果。
# 执行 `plt.tight_layout`，生成当前步骤需要的结果或可视化。
plt.tight_layout() # 展示当前步骤的结果。
# 执行 `plt.show`，生成当前步骤需要的结果或可视化。
plt.show() # 展示当前步骤的结果。
4.2 加权最近邻分类器 (Weighted k-NN)
拓展内容提示：核心内容从 \(k\) 的偏差—方差检查直接前往高维距离诊断，再进入主要案例；加权、回归与 KD 树完成核心内容后选讲。
标准的KNN模型中，每个邻居的“投票权重”是相等的。但这是否合理？
- 直觉: 距离更近的邻居应该比距离远的邻居更有发言权。
- 解决方案: 加权最近邻 (Weighted k-NN)。根据邻居的远近来分配投票权重。
一种常见的加权方式是使用距离的倒数作为权重。
\[
\large{y_n = \underset{c \in \mathcal{Y}}{\arg\max} \sum_{i=1}^k w_i \cdot I(y_i = c) \quad \text{, where } w_i = \frac{1}{\text{distance}(x_n, x_i)}}
\]
加权KNN的直观解释
近的邻居“嗓门大”，远的邻居“嗓门小”。
加权KNN在scikit-learn中的实现
Code
from sklearn.neighbors import KNeighborsClassifier # 导入加权最近邻分类器
weighted_knn_example = KNeighborsClassifier(n_neighbors=5, weights='distance') # 创建尚未拟合的候选模型设置
weighted_knn_example.get_params()["weights"] # 核对课后拓展内容 的距离加权配置
若课后比较距离加权，必须另设训练期验证并重新测试期；当前 核心内容不比较该规则。
4.3 KNN不仅能分类，还能用于回归预测
KNN的核心思想同样适用于回归问题，即预测一个连续值（如股票价格、房屋售价）。
分类 (Classification)
- 目标：预测离散的类别
- 方法：邻居投票
- 例子：判断邮件是“垃圾”还是“非垃圾”
回归 (Regression)
- 目标：预测连续的数值
- 方法：邻居取平均值
- 例子：预测房屋的售价
KNN回归的数学表达
对于一个新样本，KNN回归模型的预测值是其 \(k\) 个最近邻居的目标值的平均值（或加权平均值）。
\[
\large{\hat{y}_n = \frac{1}{k} \sum_{i=1}^k y_i}
\]
其中，\(y_i\) 是第 \(i\) 个邻居的真实数值。
4.4 现实世界的挑战与解决方案
到目前为止，我们处理的都是理想化的数值型数据。但在商业世界中，数据往往更复杂。
- 挑战1: 如何处理非数值特征 (如“城市”、“产品类别”)？
- 挑战2: 当数据量巨大 (百万、千万级) 时怎么办？KNN的预测会变得极慢。
挑战1：处理分类特征 (Categorical Features)
问题
如何计算包含“北京”和“上海”这类文本特征的样本之间的“距离”？
解决方案:
- 独热编码 (One-Hot Encoding): 将分类特征转换为多个0/1的二元特征。这是最常用的方法。
- 使用特定的距离度量: 例如，汉明距离 (Hamming Distance)，它计算两个等长字符串之间不同位置的字符数。
可视化独热编码 (One-Hot Encoding)
挑战2：数据规模与预测速度
KNN的一个主要缺点是其计算成本高。
- 训练阶段: 速度极快，几乎没有计算，只是存储数据。
- 预测阶段: 速度极慢。对于每一个新的待预测样本，都需要计算它与所有训练样本的距离。如果训练集有百万样本，这将是无法接受的。
问题
如何在不牺牲太多精度的前提下，加快寻找最近邻的速度？
核心思想: 避免“蛮力搜索”
直接计算新样本与所有训练点的距离被称为蛮力搜索 (Brute-force search)。
加速策略的核心思想是：通过构建智能的数据结构，来快速排除大量不可能成为最近邻的样本点。
加速策略1: KD树 (k-dimensional tree)
KD树是一种经典的空间划分数据结构，它将 \(k\) 维空间递归地划分为一系列超矩形区域。
- 构建过程:
- 选择一个坐标轴（例如，方差最大的轴）。
- 找到所有数据点在该轴上的中位数。
- 用一个垂直于该轴的超平面将空间一分为二。
- 对左右两个子空间递归地重复此过程，直到每个区域只包含少量数据点。
KD树如何划分二维空间？
Code
import numpy as np # 生成可复现的二维教学点集
import matplotlib.pyplot as plt # 绘制 KD 树空间划分
np.random.seed(42) # 固定教学示意随机种子
data_kd = np.random.rand(25, 2) * 10 # 生成二维点供划分演示
data_sorted_x = data_kd[data_kd[:, 0].argsort()] # 按横轴排序以确定第一次切分
median_idx_x = len(data_sorted_x) // 2 # 定位横轴中位点
median_val_x = data_sorted_x[median_idx_x, 0] # 提取第一次垂直切分位置
left_data = data_sorted_x[:median_idx_x] # 取得第一次切分左侧点
left_data_sorted_y = left_data[left_data[:, 1].argsort()] # 按纵轴排序左侧点
median_val_ly = left_data_sorted_y[len(left_data_sorted_y) // 2, 1] # 计算左侧水平切分位置
right_data = data_sorted_x[median_idx_x + 1:] # 取得第一次切分右侧点
right_data_sorted_y = right_data[right_data[:, 1].argsort()] # 按纵轴排序右侧点
median_val_ry = right_data_sorted_y[len(right_data_sorted_y) // 2, 1] # 计算右侧水平切分位置
Code
# 教学说明：--- Visualization ---。
fig, ax = plt.subplots(figsize=(8, 6.5))
# 执行 `ax.scatter`，生成当前步骤需要的结果或可视化。
ax.scatter(data_kd[:, 0], data_kd[:, 1], c='navy', s=50, ec='black', alpha=0.8)
# 教学说明：1st split (vertical)。
ax.plot([median_val_x, median_val_x], [-1, 11], color='red', linestyle='--', linewidth=2, label='第一次划分 (x轴)')
# 教学说明：2nd split (horizontal) on left side。
ax.plot([-1, median_val_x], [median_val_ly, median_val_ly], color='green', linestyle='--', linewidth=2, label='第二次划分 (y轴)')
# 教学说明：2nd split (horizontal) on right side。
ax.plot([median_val_x, 11], [median_val_ry, median_val_ry], color='green', linestyle='--')
# 执行 `ax.set_xlim`，生成当前步骤需要的结果或可视化。
ax.set_xlim(-1, 11)
# 执行 `ax.set_ylim`，生成当前步骤需要的结果或可视化。
ax.set_ylim(-1, 11)
# 执行 `ax.set_title`，生成当前步骤需要的结果或可视化。
ax.set_title('KD树的空间划分过程', fontsize=20, pad=15)
# 执行 `ax.set_xlabel`，生成当前步骤需要的结果或可视化。
ax.set_xlabel('特征 1', fontsize=20)
# 执行 `ax.set_ylabel`，生成当前步骤需要的结果或可视化。
ax.set_ylabel('特征 2', fontsize=20)
# 执行 `ax.legend`，生成当前步骤需要的结果或可视化。
ax.legend(fontsize=20)
# 执行 `ax.set_aspect`，生成当前步骤需要的结果或可视化。
ax.set_aspect('equal', adjustable='box')
# 执行 `plt.grid`，生成当前步骤需要的结果或可视化。
plt.grid(True, linestyle='--', alpha=0.6) # 展示当前步骤的结果。
# 执行 `plt.tight_layout`，生成当前步骤需要的结果或可视化。
plt.tight_layout() # 展示当前步骤的结果。
# 执行 `plt.show`，生成当前步骤需要的结果或可视化。
plt.show() # 展示当前步骤的结果。
核心内容高维诊断：近邻对比为何消失
拓展内容：高维空间的诅咒
拓展内容结束：本分支结束后进入主要案例，不重放已经完成的 核心内容诊断。
核心问题：高维空间中的’距离’是什么？
拓展内容提示：90 分钟核心内容在进入本分支前已完成“相对距离差缩小会削弱邻居排序”的最小诊断；以下边界层、四阶矩与次高斯定理用于课后推导。本分支结束后只向前返回尚未完成的主要案例，不要求 核心内容先修概率论。
在高维空间中，我们基于低维（2D或3D）生活经验建立的几何直觉往往会失效。
- 直觉：点与点之间有远有近，总能找到’最近的邻居’。
- 高维现实：随着维度越来越高，点与点之间的欧氏距离会变得越来越相近。
本讲座旨在通过直观的例子和数学推导，揭示这一反直觉的现象——距离度量的失效。
简化模型：角点邻域与边界层
我们从一个简单的思想实验开始：将单位超立方体 \([0, 1]^d\) 的每个维度都从中点 \(0.5\) 处切开。
这会将整个空间分割成 \(2^d\) 个相同大小的“小超立方体”。
低维直觉：d=1 和 d=2 的角点分区
在低维空间，可以直接看到原点角落的子区与其补集。注意：这里比较的是“一个角落”和“其余区域”，不是中心与边界。
高维现象：角点体积缩小；边界层体积增大
随着维度 \(d\) 增加，原点角落子立方体 \([0,1/2]^d\) 的体积 \(2^{-d}\) 迅速趋近于 0；其补集并不等同于边界层。
| 1 |
2 |
50% |
50% |
| 3 |
8 |
12.5% |
87.5% |
| 10 |
1,024 |
~0.1% |
99.9% |
| 100 |
~\(1.27 \times 10^{30}\) |
~\(7.9 \times 10^{-31}\) |
~100% |
若把宽度为 \(\varepsilon\) 的边界层定义为
\[
B_\varepsilon=\{x\in[0,1]^d:\min_j\min(x_j,1-x_j)\le\varepsilon\},
\]
则 \(P(X\in B_\varepsilon)=1-(1-2\varepsilon)^d\to1\)（固定 \(0<\varepsilon<1/2\)）。这才严格表达“均匀质量靠近某个边界面”。
从离散到连续：均匀分布下的距离集中
刚才的切分模型是一个简化。现在我们考虑更一般的情况：\(n\) 个数据点 \(X_1, \ldots, X_n\) 在单位超立方体 \([0, 1]^d\) 中独立同分布。
有条件的结论
若样本量 \(n\) 固定、坐标独立同分布为 \(U(0,1)\)，则有限个点对的欧氏距离具有相同的一阶尺度，最大与最小距离的相对差距依概率趋于 0。
\[ \frac{dist_{max}-dist_{min}}{dist_{min}}\xrightarrow{p}0
\qquad(n\text{ 固定}). \]
若 \(n\) 随 \(d\) 增长、坐标相关、分布重尾，或改变度量，上述极值结论需要额外条件，不能直接沿用。
数学推导 1：构建距离的随机变量
我们来分析任意两点 \(X_i\) 和 \(X_j\) 之间的距离。
- 点的表示：每个点 \(X_j\) 是一个 \(d\) 维向量 \((X_{j1}, \ldots, X_{jd})^T\)。
- 分量的分布：每个分量 \(X_{jk}\) 独立地服从 \(U(0, 1)\) 分布。
- 期望：\(E(X_{jk}) = \frac{1}{2}\)
- 方差：\(\operatorname{Var}(X_{jk}) = \frac{1}{12}\)
- 距离的平方：我们分析欧氏距离的平方 \(S_{ij} = \lVert X_i - X_j\rVert_2^2\)，因为它更易于处理。
\[ \large{ S_{ij} = \sum_{k=1}^{d} (X_{ik} - X_{jk})^2 } \]
数学推导 2：计算距离平方的期望
利用期望的线性性质，我们可以计算 \(S_{ij}\) 的期望值。
首先，考虑单个维度上差的平方的期望 \(E[(X_{ik} - X_{jk})^2]\)。
根据方差定义 \(\operatorname{Var}(Y) = E(Y^2) - [E(Y)]^2\)，我们有：
\[ \large{E[(X_{ik} - X_{jk})^2] = \operatorname{Var}(X_{ik} - X_{jk}) + [E(X_{ik} - X_{jk})]^2} \]
由于 \(X_{ik}\) 和 \(X_{jk}\) 独立同分布：
- \(E(X_{ik} - X_{jk}) = E(X_{ik}) - E(X_{jk}) = \frac{1}{2} - \frac{1}{2} = 0\)
- \(\operatorname{Var}(X_{ik} - X_{jk}) = \operatorname{Var}(X_{ik}) + \operatorname{Var}(X_{jk}) = \frac{1}{12} + \frac{1}{12} = \frac{1}{6}\)
所以，\(E[(X_{ik} - X_{jk})^2] = \frac{1}{6} + 0^2 = \frac{1}{6}\)。
数学推导 3：对所有维度求和
最终，对所有维度求和：
\[ \large{ E(S_{ij}) = E[\sum_{k=1}^{d} (X_{ik} - X_{jk})^2] = \sum_{k=1}^{d} E[(X_{ik} - X_{jk})^2] = \frac{d}{6} } \]
数学推导 4：大数定律的应用
我们已经知道距离平方 \(S_{ij}\) 是 \(d\) 个独立同分布随机变量 \((X_{ik} - X_{jk})^2\) 的和。
根据大数定律，当 d 趋于无穷时，样本均值会依概率收敛于期望值：
\[ \large{ \frac{S_{ij}}{d} = \frac{1}{d} \sum_{k=1}^{d} (X_{ik} - X_{jk})^2 \xrightarrow{p} E[(X_{ik} - X_{jk})^2] = \frac{1}{6} } \]
此外 \(E[(X_{ik}-X_{jk})^4]=1/15\)，所以
\[
\operatorname{Var}(S_{ij})=\frac{7d}{180},\qquad
\frac{\operatorname{sd}(S_{ij})}{E(S_{ij})}=\sqrt{\frac{7}{5d}}.
\]
概念可视化：距离分布的集中
这个现象可以用距离分布的变化来直观理解。
推广：范数的集中 (Concentration of the Norm)
类似集中结论可以推广，但必须陈述分布与相关性条件，不能把它当作任意高维数据的普遍定理。
范数集中定理 (直观版): 例如，对均值为零、各向同性且次高斯的随机向量 \(X\in\mathbb R^d\)，\(\lVert X\rVert_2\) 会在 \(\sqrt d\) 的尺度附近集中；
常数与尾界取决于明确的次高斯参数。
一个更强的结论（Vershynin, 2018）表明，对于次高斯向量，这种偏离 \(\sqrt{d}\) 的概率会随着维度 \(d\) 的增加而指数级衰减。
这意味着在高维空间中，随机向量的长度几乎是一个确定性而非随机性的值。
实践意义：为什么’最近邻’会失效？
距离度量的失效对许多依赖于距离计算的算法构成了严峻挑战，特别是 k-最近邻 (k-NN) 算法。
- k-NN的目标: 找到特征空间中与查询点’最相似’的
k 个邻居。
- 高维困境: 如果所有邻居到查询点的距离都几乎相等，那么’最近’和’最远’的邻居之间没有实际差别。
- 结果: 若无低维结构或有效信号，邻居排序的对比度会下降，预测可能变得不稳定；这不是 k-NN 在所有高维任务上必然“毫无意义”的定理。
总结
- 高维几何反直觉: 我们不能将低维空间的直觉直接推广到高维空间。
- 边界层需要定义: 对均匀超立方体，固定宽度边界层的体积占比趋近于 1；一个角点的补集不能冒充边界层。
- 相对距离集中: 在明确分布且固定样本量的设定下，归一化距离的相对波动收缩。
- 算法需要诊断: 距离集中可能削弱 k-NN 或聚类的邻近对比，但效果取决于尺度、结构、度量与样本增长。
拓展内容结束
继续进入主要案例；不要跳过训练期选参与测试期检查。
进入主要案例前的学习目标回顾
回顾开场目标：①手算欧氏/曼哈顿距离；②解释标准化为何改变邻居；③用时间验证选择 \(k\)；④诊断高维距离集中。
- 回顾题： 点 \((0,0)\) 到 \((3,4)\) 的欧氏距离与曼哈顿距离分别是多少？
- 答案： 欧氏距离 \(\sqrt{3^2+4^2}=5\)；曼哈顿距离 \(|3|+|4|=7\)。选择何者取决于任务中的相似性含义。
形成性检查 1：先缩放还是先切分？
标准化器应在全样本拟合，还是只在训练期拟合？为什么？
答案
只在训练期拟合，再原样变换验证/测试期；全样本均值与标准差包含未来信息，会造成预处理泄漏。
主要案例：福耀玻璃 KNN 下跌分类
本例数据： data/stock/stock_price_pre_adjusted.h5；key=data；福耀玻璃 600660.XSHG；2018–2024；用当日收益、5 日收益与 5 日波动率预测下一日是否下跌；按时间 80/20 切分。
邻近方法来源： Cover & Hart (1967), 最近邻分类；本例先用训练期标准化，再在同一距离尺度上预测。
Code
from pathlib import Path # 使用统一路径对象定位数据文件
import pandas as pd # 导入表格工具以读取本地行情
from sklearn.preprocessing import StandardScaler # 用训练期尺度定义可比距离
from sklearn.neighbors import KNeighborsClassifier # 使用最近邻多数投票完成分类
from sklearn.metrics import average_precision_score, balanced_accuracy_score, confusion_matrix, roc_auc_score # 为确定测试检查准备排序与分类阈值指标
# 公网下载：https://assets.qiufei.site/data/stock/stock_price_pre_adjusted.h5
# 下载后把下一行改为本机文件位置；按课程结构存放时可用 Path("data/stock/stock_price_pre_adjusted.h5")。
# Windows：Path(r"C:\qiufei\data\stock\stock_price_pre_adjusted.h5")
# macOS：Path("/Users/你的用户名/data/stock/stock_price_pre_adjusted.h5")
# Linux：Path("/home/你的用户名/data/stock/stock_price_pre_adjusted.h5")
price_path = Path("/home/ubuntu/r2_data_mount/data/stock/stock_price_pre_adjusted.h5")
price_rows = pd.read_hdf(price_path, key='data', where=['order_book_id=="600660.XSHG"', 'date>=Timestamp("2018-01-01")', 'date<=Timestamp("2024-12-31")'], columns=['close']) # 仅载入目标公司与收盘价
knn_frame = price_rows.reset_index().sort_values('date') # 按交易日建立预测顺序
knn_frame['return_t'] = knn_frame['close'].pct_change() # 构造单日收益率
knn_frame['return_5d_t'] = knn_frame['close'].pct_change(5) # 构造五日累计收益
knn_frame['volatility_5d_t'] = knn_frame['return_t'].rolling(5).std() # 构造五日历史波动率
knn_frame['future_return_t1'] = knn_frame['return_t'].shift(-1) # 先保留连续未来收益以识别末端未知标签
knn_frame['target_date_t1'] = knn_frame['date'].shift(-1) # 保存标签实现日以清除跨窗口样本
knn_frame = knn_frame.dropna() # 在整数化之前删除滚动窗口与未来收益缺失行
Code
knn_frame['down_t1'] = (knn_frame['future_return_t1'] < 0).astype(int) # 仅把真实可观测的未来收益转换为类别
assert knn_frame['future_return_t1'].notna().all() and knn_frame['date'].max() < price_rows.reset_index()['date'].max() # 确认最后特征日早于最后标签实现日
split_row = int(len(knn_frame) * 0.8) # 固定前百分之八十为训练期
test_start_date = knn_frame.iloc[split_row]['date'] # 从完整序列确定测试起点
train_rows = knn_frame[(knn_frame['date'] < test_start_date) & (knn_frame['target_date_t1'] < test_start_date)] # 清除到测试期才实现的训练标签
test_rows = knn_frame[knn_frame['date'] >= test_start_date] # 确定测试特征窗口
assert train_rows['target_date_t1'].max() < test_rows['date'].min() # 确认标签实现边界
feature_names = ['return_t', 'return_5d_t', 'volatility_5d_t'] # 声明距离空间的三个语义维度
pd.Series({'train_end': train_rows['date'].max(), 'test_start': test_rows['date'].min()}) # 选参前只确认时间边界，不读取任何测试标签摘要
train_end 2023-08-04
test_start 2023-08-08
dtype: datetime64[ns]
形成性检查 2：\(k\) 的偏差—方差
从 \(k=1\) 增至 \(k=51\)，边界通常如何变化？训练误差和方差通常如何变化？
答案
边界更平滑，训练误差通常上升，方差下降、偏差上升。最佳 \(k\) 必须在训练期内部验证，不能看最终测试结果挑选。
分步练习：选择 \(k\)
- 任务：
事先确定欧氏距离与等权投票，在训练期做 5 个扩展窗口切分，比较 \(k\in\{5,15,31\}\) 的平衡准确率；
确定 \(k\) 后，一次报告测试期类别比例、ROC-AUC、AP 与混淆矩阵。
Code
from sklearn.model_selection import TimeSeriesSplit # 用扩展窗口保持训练早于验证
validation_rows = [] # 收集每个窗口和候选 k 的平衡准确率
for fold_id, (fit_index, validation_index) in enumerate(TimeSeriesSplit(n_splits=5).split(train_rows), start=1): # 生成五个时间有序窗口
fold_train = train_rows.iloc[fit_index] # 取得当前窗口的历史训练段
fold_validation = train_rows.iloc[validation_index] # 取得紧随其后的验证段
fold_train = fold_train[fold_train['target_date_t1'] < fold_validation['date'].min()] # 清除到验证折才实现的训练标签
assert fold_train['target_date_t1'].max() < fold_validation['date'].min() # 确认逐折标签实现边界
fold_scaler = StandardScaler().fit(fold_train[feature_names]) # 只在当前训练段估计尺度
for neighbor_count in [5, 15, 31]: # 比较预先声明的三个候选值
fold_model = KNeighborsClassifier(n_neighbors=neighbor_count, weights='uniform', metric='euclidean').fit(fold_scaler.transform(fold_train[feature_names]), fold_train['down_t1']) # 在事先确定的等权欧氏规则下拟合候选 k
fold_prediction = fold_model.predict(fold_scaler.transform(fold_validation[feature_names])) # 在未来验证段生成预测
validation_rows.append({'fold': fold_id, 'k': neighbor_count, 'balanced_accuracy': balanced_accuracy_score(fold_validation['down_t1'], fold_prediction)}) # 保存可重复的逐折结果
validation_table = pd.DataFrame(validation_rows) # 整理逐折验证记录
validation_summary = validation_table.groupby('k', as_index=False)['balanced_accuracy'].mean().sort_values('balanced_accuracy', ascending=False) # 汇总平均验证证据
selected_k = int(validation_summary.iloc[0]['k']) # 仅依据训练期验证选择邻居数
final_scaler = StandardScaler().fit(train_rows[feature_names]) # 选参后用完整训练期重新估计尺度
final_knn = KNeighborsClassifier(n_neighbors=selected_k, weights='uniform', metric='euclidean').fit(final_scaler.transform(train_rows[feature_names]), train_rows['down_t1']) # 用完整训练期重拟合已确定规则
final_test_prediction = final_knn.predict(final_scaler.transform(test_rows[feature_names])) # 只对测试期评价一次
final_test_probability = final_knn.predict_proba(final_scaler.transform(test_rows[feature_names]))[:, 1] # 由同一确定模型生成排序分数
final_test_confusion = confusion_matrix(test_rows['down_t1'], final_test_prediction) # 记录默认多数投票分类阈值的四格计数
test_summary = pd.Series({'selected_k': selected_k, 'prevalence': test_rows['down_t1'].mean(), 'roc_auc': roc_auc_score(test_rows['down_t1'], final_test_probability), 'AP': average_precision_score(test_rows['down_t1'], final_test_probability), 'balanced_accuracy': balanced_accuracy_score(test_rows['down_t1'], final_test_prediction), 'TN': final_test_confusion[0, 0], 'FP': final_test_confusion[0, 1], 'FN': final_test_confusion[1, 0], 'TP': final_test_confusion[1, 1]}) # 汇总一次性测试期检查
display(validation_summary.round(6), test_summary.to_frame().T.round(6)) # 紧凑展示训练期选择与单行测试期检查
综合练习
对象与规则： 换为恒瑞医药 600276.XSHG，并预设距离加权。
验证选择： 只在训练期同一组时间折上比较欧氏/曼哈顿距离与 \(k\)，确定唯一组合。
一次测试： 报告类别比例、平衡准确率和查询耗时，不再回选模型。
案例验证选择与测试期检查
Code
display(validation_comparison.round(6), transfer_test_summary.to_frame().T.round(6)) # 分开展示验证选择与测试期证据
| 0 |
euclidean |
5 |
0.519945 |
| 4 |
manhattan |
15 |
0.517000 |
| 5 |
manhattan |
31 |
0.512933 |
| 1 |
euclidean |
15 |
0.511542 |
| 2 |
euclidean |
31 |
0.510255 |
| 3 |
manhattan |
5 |
0.508568 |
| 0 |
euclidean |
5 |
0.52588 |
0.541321 |
3.145574 |
训练期扩展窗口在六个候选中确定欧氏距离与 \(k=5\)；随后只打开测试期一次。
测试样本数为 483、下跌比例为 0.525880，确定组合的平衡准确率为 0.541321。
最后特征日为 2024-12-30，未知未来标签已在整数化前删除。
耗时随硬件变化；预测邻近不是因果相似。
形成性检查 3：维度灾难
维度上升时，最近点与最远点距离之比趋近 1，这对 KNN 意味着什么？
答案
邻居的相对区分度下降，距离加权和局部投票更不稳定；应做特征选择/降维、用领域距离或换用对高维更稳健的模型。
来源与延伸阅读
- Cover & Hart (1967), “Nearest Neighbor Pattern Classification”。
- Hastie, Tibshirani & Friedman, The Elements of Statistical Learning, Chapter 13。
- scikit-learn User Guide：nearest neighbors 与 preprocessing。
- 数据：本地 A 股前复权行情数据；文件、key、字段、时期和切分见 前面的案例。
4.5 总结: KNN算法的优缺点
课后选学
完成核心内容后，可以继续学习加权近邻、KNN 回归与 KD 树，随后进入最终思考。
| ✅ 原理简单，易于实现 |
❌ 计算成本高，预测速度慢 |
| ✅ 无需训练，模型适应性强 (非参数) |
❌ 对内存需求大，需存储所有训练数据 |
| ✅ 对数据分布没有假设 |
❌ 对不平衡数据敏感 (多数类会主导投票) |
| ✅ 可用于分类和回归 |
❌ 高维灾难问题严重 |
| ✅ 决策边界可以非常灵活 |
❌ 需要对特征进行标准化 |
KNN在商业决策中的应用场景
凭借其简单性和灵活性，KNN在多个商业领域都有广泛应用：
- 金融: 客户信用评级，欺诈交易检测。
- 市场营销: 客户细分，识别高价值客户群。
- 推荐系统: “购买了X产品的用户也购买了Y产品”，这是典型的“寻找近邻”问题。
- 医疗: 疾病诊断，基因模式识别。
- 零售: 预测顾客购买行为，优化库存。
本章概念回顾：核心内容与拓展内容
| KNN分类 |
少数服从多数 |
k, distance metric |
| KNN回归 |
邻居的平均值 |
k, distance metric |
| 加权KNN |
近朱者赤，近墨者黑 |
weights='distance' |
| KD树 |
空间换时间，预先划分 |
适用于低维数据 |
| 维度灾难 |
高维空间中距离失去意义 |
特征选择/降维是关键 |
| 标准化 |
使量纲可比，不等于赋予相同预测权重 |
仅在训练期拟合后再计算距离 |
最终思考: KNN成功的关键
要成功应用KNN，经济学家和数据科学家需要关注以下几点：
- 特征工程: 选择与问题最相关的特征至关重要。垃圾进，垃圾出。
- 距离度量: 为你的特定问题选择合适的距离度量。欧几里得距离并非总是最佳选择。
- 参数调优：
- 效率考量: 对于大规模数据集，必须考虑使用KD树、Ball Tree等加速算法，或采用近似最近邻搜索。
KNN是进入机器学习世界的一扇极好的大门，它简单、直观且功能强大。
