不训练参数也能分类吗？K 近邻的距离投票与维度灾难

上一篇的逻辑回归用一组全局权重画出线性决策边界。它快速、清晰，却无法在原始特征中直接分开同心圆或弯月形类别。

如果问题满足另一种规律——相似样本往往有相似标签——可以不先假设一条全局公式。收到新样本时，直接寻找训练集中最相似的若干样本，再让它们投票。这就是 K 近邻（K-Nearest Neighbors，KNN）。

KNN 的 fit 几乎不学习参数，却把大量工作留到推理阶段。本文只讲透四个紧密环节：距离定义、邻居选择、局部投票，以及它为什么在高维空间逐渐失效。

01 从一条全局边界转向局部证据#

考虑二维分类：横轴是用户最近 7 天活跃次数，纵轴是平均会话时长。正负样本形成两个弯曲区域，一条直线无法分开，但新用户附近的训练用户大多属于同一类。

会话时长 x₂
▲
│  ○ ○ ○             + + +
│ ○     ○           +     +
│ ○     ○    ?      +     +
│  ○ ○ ○      + + +
└────────────────────────────► 活跃次数 x₁

? 的类别不由一条全局直线决定，
而由它周围最近的 K 个已标记样本决定。

text

这叫基于实例的学习（Instance-Based Learning）：训练阶段保留实例，预测阶段才针对查询点进行局部计算。也常称惰性学习（Lazy Learning），因为昂贵的决策被推迟到查询时。

KNN 分类的数据流是：

训练：X_train [N,D] + y_train [N] ──► 保存 / 建索引

查询：X_query [Q,D]
          │ 与训练样本计算距离
          ▼
      distances [Q,N]
          │ 每行选最小 K 个
          ▼
      neighbor_indices [Q,K]
          │ 取标签、投票
          ▼
      class_votes [Q,C] ──► prediction [Q]

text

$N$ ：训练样本数；
$Q$ ：一次查询的样本数；
$D$ ：特征维数；
$C$ ：类别数；
$K$ ：每个查询点使用的邻居数量。

02 “最近”必须先定义距离#

最常见的是欧氏距离（Euclidean Distance）：

d_2(x,q)=\sqrt{\sum_{j=1}^{D}(x_j-q_j)^2}

$x$ 是训练样本， $q$ 是查询样本。若只比较远近，平方根不改变排序，也可比较平方距离。

更一般的闵可夫斯基距离（Minkowski Distance）为：

d_p(x,q)=\left(\sum_{j=1}^{D}|x_j-q_j|^p\right)^{1/p}

$p=1$ ：曼哈顿距离（Manhattan Distance），各维绝对差之和；
$p=2$ ：欧氏距离，直线距离；
$p$ 越大：越强调单个维度上的最大差异。

一个可手算的三邻居查询#

训练数据如下，A/B 是类别：

点	坐标 $(x_1,x_2)$	标签	到查询点 $q=(2,2)$ 的欧氏距离
$x_1$	$(1,1)$	A	$\sqrt2\approx1.414$
$x_2$	$(2,3)$	A	$1$
$x_3$	$(3,2)$	B	$1$
$x_4$	$(5,5)$	B	$\sqrt{18}\approx4.243$
$x_5$	$(0,4)$	B	$\sqrt8\approx2.828$

若 $K=3$ ，最近邻依次是 $x_2(A)$ 、 $x_3(B)$ 、 $x_1(A)$ ，A 得 2 票，B 得 1 票，所以预测 A。

均匀投票的类别分数可写为：

s_c(q)=\sum_{i\in\mathcal{N}_K(q)}\mathbb{1}[y_i=c]

\hat y(q)=\arg\max_c s_c(q)

$\mathcal{N}_K(q)$ 是查询点的 K 个最近邻索引集合。

03 距离加权怎样改变投票？#

均匀投票让第 1 近和第 K 近拥有相同影响。距离加权（Distance Weighting）则让近邻权重更高，常用：

w_i(q)=\frac{1}{d(x_i,q)+\varepsilon}

s_c(q)=\sum_{i\in\mathcal{N}_K(q)}w_i(q)\mathbb{1}[y_i=c]

$\varepsilon$ 是防止手写实现除以 0 的小正数。

假设三个最近邻变为：A 距离 1.4、A 距离 1.6、B 距离 0.1。均匀投票仍判 A；倒数距离权重为：

s_A=\frac{1}{1.4}+\frac{1}{1.6}\approx1.339

s_B=\frac{1}{0.1}=10

加权结果改判 B，因为一个极近的 B 比两个较远的 A 更有证据。

predict_proba 给出的也不是经似然训练的参数概率，而是邻域中各类别的加权票数比例。邻域很小、类别密度变化或数据漂移时，它可能不校准。

04 特征尺度为什么可以直接改写答案？#

假设两个特征是年龄（年）和年收入（元）：

查询用户 q = (年龄 30, 收入 100000)
用户 A     = (年龄 31, 收入 100000)
用户 B     = (年龄 30, 收入 101000)

text

原始欧氏距离：

d(q,A)=1,qquad d(q,B)=1000

模型会认为 A 远比 B 相似，几乎完全忽略年龄之外的语义权衡。若收入改用“万元”，B 的距离又变成 0.1；只换单位就可能交换邻居次序。

常见处理是用训练集统计量做标准化：

z_j=\frac{x_j-\mu_j}{\sigma_j}

使每个连续特征的数值尺度更接近。但标准化只解决量纲，不保证距离符合任务语义：邮政编码、用户 ID 等类别编号即使标准化，也不应按数值远近比较。

原始 X_train ── fit μ,σ ──► 标准化训练数据 ──► KNN 保存
X_query       ── 用同一 μ,σ ─► 标准化查询点   ──► 距离查询

text

均值和标准差只能从当前训练折学习，因此缩放器必须放入 Pipeline。否则交叉验证的验证折会泄漏进距离定义。

05 K 值控制的是怎样的偏差—方差权衡？#

$K$ 太小时，决策高度依赖单个样本：

$K=1$ 的训练误差常常极低；
一个错标样本或异常点就能制造小片错误区域；
边界曲折，方差高。

$K$ 很大时，局部信息被大范围多数类淹没：

边界过度平滑；
小类别区域可能消失；
偏差高，最终甚至接近“永远预测全局多数类”。

K=1：边界追随每个点          K 较大：边界更平滑

 +++○++  局部小岛               +++++++
 ++○○++                           +++++
 ○○++○+                         ─────────
 ○○○○○+                           ○○○○○

text

验证集或交叉验证负责选 $K$ 。候选值无需只取奇数：奇数只能减少二分类均匀投票中的一部分平票，无法解决相同距离、重复样本、多分类或加权票数相等。

06 不依赖 `fit`，写出一个可检查的 KNN#

下面实现欧氏距离和均匀投票。它刻意保留中间数组，便于看清数据流；大数据时不应一次构造完整 [Q,N,D] 张量。

import numpy as np

X_train = np.array([
    [1.0, 1.0],
    [2.0, 3.0],
    [3.0, 2.0],
    [5.0, 5.0],
    [0.0, 4.0],
])                                         # [N=5, D=2]
y_train = np.array([0, 0, 1, 1, 1])       # [5]
X_query = np.array([[2.0, 2.0]])           # [Q=1, D=2]
k = 3

# [Q,1,D] - [1,N,D] -> [Q,N,D]
differences = X_query[:, None, :] - X_train[None, :, :]
squared_distances = np.sum(differences ** 2, axis=2)  # [Q,N]

# argpartition 只保证前 k 个是最小集合，不保证它们内部有序
neighbor_indices = np.argpartition(
    squared_distances,
    kth=k - 1,
    axis=1,
)[:, :k]                                  # [Q,K]
neighbor_labels = y_train[neighbor_indices]            # [Q,K]

classes = np.unique(y_train)               # [C]
votes = np.stack([
    np.sum(neighbor_labels == class_label, axis=1)
    for class_label in classes
], axis=1)                                 # [Q,C]
predictions = classes[np.argmax(votes, axis=1)]        # [Q]

python

最小调试检查：

assert X_train.ndim == X_query.ndim == 2
assert X_train.shape[1] == X_query.shape[1]
assert y_train.shape == (X_train.shape[0],)
assert 1 <= k <= X_train.shape[0]
assert neighbor_indices.shape == (X_query.shape[0], k)
assert np.isfinite(squared_distances).all()

python

若需要解释一个预测，应打印邻居的原始样本 ID、距离、标签和票权，而不只返回类别。KNN 的局部可解释性来自“哪些实例参与了决策”，不是来自全局特征系数。

07 用当前 scikit-learn API 建立无泄漏流程#

截至本文写作时，scikit-learn 1.9 的 KNeighborsClassifier 默认参数包括 n_neighbors=5、weights='uniform'、metric='minkowski'、p=2 和 algorithm='auto'。下面把缩放和 KNN 放入同一 Pipeline，并只在开发数据内选超参数。

from sklearn.model_selection import GridSearchCV, StratifiedKFold
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

pipeline = make_pipeline(
    StandardScaler(),
    KNeighborsClassifier(
        algorithm='auto',
        metric='minkowski',
        n_jobs=None,  # 让外层 GridSearchCV 负责并行，避免双层抢占 CPU
    ),
)

search = GridSearchCV(
    estimator=pipeline,
    param_grid={
        'kneighborsclassifier__n_neighbors': [1, 3, 5, 9, 15, 31],
        'kneighborsclassifier__weights': ['uniform', 'distance'],
        'kneighborsclassifier__p': [1, 2],
    },
    scoring='balanced_accuracy',
    cv=StratifiedKFold(n_splits=5, shuffle=True, random_state=42),
    n_jobs=-1,
    refit=True,
)
search.fit(X_train, y_train)

predictions = search.predict(X_val)          # [num_val]
probabilities = search.predict_proba(X_val)  # [num_val, num_classes]

best_knn = search.best_estimator_.named_steps['kneighborsclassifier']
scaled_query = search.best_estimator_.named_steps['standardscaler'].transform(
    X_val[:2]
)                                           # [2, D]
distances, indices = best_knn.kneighbors(scaled_query)
# distances: [2, K]；indices: [2, K]，索引指向训练样本

python

关键 API 的输入输出：

fit(X,y) 接收 [N,D] 与 [N]；对 KNN 而言主要是保存训练数据并准备查询结构；
kneighbors(X) 返回 (distances, indices)，形状都是 [Q,K]；
predict_proba(X) 返回 [Q,C]，列顺序按 classes_；
weights='uniform' 等票投票，weights='distance' 使用距离倒数加权；
p=1 与 p=2 分别对应曼哈顿和欧氏距离；
algorithm='auto' 让实现根据输入选择查询策略，但稀疏输入会使用暴力搜索；
n_jobs 控制邻居搜索并行度；外层交叉验证已经并行时，要防止双层并行导致 CPU 过度抢占；
leaf_size 影响 KD 树或球树的构建、查询与内存折中，不改变数学预测规则。

08 “几乎不训练”不等于计算便宜#

暴力搜索对每个查询点计算到全部训练样本的距离，时间复杂度近似：

O(ND)

一次查询还要维护最近的 K 个候选。训练数据本身通常也要保存在内存中，空间至少为 $O(ND)$ 。

KD 树（KD-Tree）沿坐标维递归切分空间，球树（Ball Tree）用嵌套超球组织样本；在低维、距离结构合适时，它们能跳过大量不可能成为近邻的区域。但维数升高后，剪枝效率下降，查询会逐渐接近暴力扫描。

阶段	逻辑回归	KNN 暴力查询
训练	迭代优化参数	主要保存数据
模型大小	$O(D)$	$O(ND)$
单样本推理	$O(D)$	约 $O(ND)$
新增少量样本	通常要重训	可加入索引，但要管理重建
删除隐私数据	删除模型未必足够	必须从样本库与索引清除

工程上要同时测量构建索引时间、P50/P99 查询延迟、内存、吞吐和召回一致性。若使用近似最近邻（Approximate Nearest Neighbor，ANN）换取速度，还要额外评估“没有找回真正近邻”对分类的影响。

09 维度灾难为什么让所有点都显得差不多远？#

维度灾难（Curse of Dimensionality）不是“维度多所以计算慢”这么简单。在高维空间中，数据变得极度稀疏；要覆盖与低维相同的局部密度，样本数会随维度指数增长。

看单位超立方体 $[0,1]^D$ 。若希望一个轴对齐邻域在每个维度只覆盖长度 0.1，它的体积为：

V=0.1^D

维数 $D$	邻域体积 $0.1^D$	平均放入 1 个样本约需总样本数
1	$10^{-1}$	$10$
2	$10^{-2}$	$100$
10	$10^{-10}$	$10^{10}$

高维中，查询点的最近邻也可能很远，最近距离与最远距离的相对差距往往缩小。此时“最近”不再代表真正相似，局部投票失去基础。

缓解方向包括：

删除噪声、重复和无语义的特征；
用领域知识设计真正代表相似性的度量；
先做特征选择、主成分分析或学习低维表示；
增加覆盖真实分布的样本，而不是盲目生成更多维度；
在验证集上比较 KNN 与不依赖局部欧氏距离的模型。

降维步骤同样必须只在训练折拟合，并放进 Pipeline。

10 常见错误与最短调试路径#

未缩放连续特征。 打印每列范围和标准差；检查邻居是否只由某一大数值特征决定。
把类别编号当连续坐标。 性别编码、邮编、设备 ID 的数字差不代表语义距离；应用合适编码或度量。
在全数据上标准化后交叉验证。 预处理必须在每个训练折内 fit。
只调 K，不调距离。 同时验证 p、权重和特征表示；它们共同定义“邻域”。
类别失衡仍用普通准确率。 大 K 容易吞没少数类；结合平衡准确率、每类召回率和邻域标签比例。
请求批次过大导致内存峰值。 暴力距离矩阵可非常大；分块查询，并监测实际内存。
重复点标签冲突。 距离相同但标签不同会产生不稳定平票；先检查去重、标注一致性和稳定样本顺序。
误把邻域票数当可信概率。 用可靠验证集检查校准，不要直接把 3/5 解释成真实风险 60%。

诊断单个预测：

print('classes:', best_knn.classes_)
for rank, (distance, row_index) in enumerate(
    zip(distances[0], indices[0]), start=1
):
    print(rank, distance, row_index, y_train[row_index])

python

若最近邻肉眼看起来毫不相似，优先怀疑特征表示和距离，而不是继续调 K；若近邻合理但标签混乱，问题可能来自标签噪声或该区域本身不可分。

11 失败场景与相近方法边界#

KNN 依赖局部平滑假设：彼此接近的点应该有相近标签。若标签在微小尺度上快速交替，或者所选特征无法表达真实相似性，增加样本也未必修复。

方法	预测依据	边界形状	训练 / 推理重心	适合场景
KNN	查询点附近实例投票	局部、可高度非线性	训练轻，推理重	中小型低维数据、距离有意义
逻辑回归	全局线性 logit	线性	训练优化，推理轻	可分性近似线性、要全局系数
最近质心	到每类中心的距离	分段线性	压缩为每类一个中心	类内近似紧凑、需要更快推理
半径邻居	固定半径内投票	局部	邻居数随密度变化	不同区域密度可解释
核方法	样本间核相似度	非线性	训练通常更重	需要光滑非线性边界

KNN 还不适合训练集巨大且延迟苛刻、每个特征都含大量噪声、数据隐私要求不能长期保存原始实例、流量分布快速漂移而索引更新滞后的系统。

12 今天真正需要记住什么？#

KNN 不学习显式全局参数，而是在预测时寻找 K 个最近训练实例并局部投票。
特征表示、缩放和距离度量共同定义“相似”，它们比 K 值本身更基础。
小 K 方差高、易追随噪声；大 K 偏差高、易被全局多数类支配，应在开发数据内选择。
fit 便宜不代表系统便宜：KNN 保存训练数据，暴力单查询约需 $O(ND)$ 计算。
高维中局部空间极度稀疏、距离对比变弱，KNN 会遭遇维度灾难。

13 思考题与小练习#

练习 1：比较两种距离

查询点 $q=(0,0)$ ，训练点 A 为 $(3,0)$ ，B 为 $(2,2)$ 。欧氏距离下 A 为 3、B 为 $\sqrt8\approx2.828$ ，所以 B 更近；曼哈顿距离下 A 为 3、B 为 4，所以 A 更近。距离定义可以直接改变预测。

练习 2：手算距离加权票数

三个邻居为 A@0.5、B@1、B@2。均匀投票判 B；倒数距离权重下 A 得 2，B 得 $1+0.5=1.5$ ，因此改判 A。

练习 3：观察维度灾难

分别在 2、20、200 维单位超立方体中随机生成点，计算每个查询的最近和最远距离，再记录 (d_max-d_min)/d_min。随着维度上升，观察距离对比如何变化，并解释这会怎样影响局部投票。

14 下一篇预告#

KNN 用许多局部实例拼出弯曲边界，却要在推理时保存并搜索训练数据。下一篇将学习决策树：怎样在训练阶段反复选择“哪个特征、哪个阈值最能降低不纯度”，把非线性边界压缩成一组可执行的 if-then 规则。

01 从一条全局边界转向局部证据#

02 “最近”必须先定义距离#

一个可手算的三邻居查询#

03 距离加权怎样改变投票？#

04 特征尺度为什么可以直接改写答案？#

05 K 值控制的是怎样的偏差—方差权衡？#

06 不依赖 fit，写出一个可检查的 KNN#

07 用当前 scikit-learn API 建立无泄漏流程#

08 “几乎不训练”不等于计算便宜#

09 维度灾难为什么让所有点都显得差不多远？#

10 常见错误与最短调试路径#

11 失败场景与相近方法边界#

12 今天真正需要记住什么？#

13 思考题与小练习#

相关工作#

14 下一篇预告#

06 不依赖 `fit`，写出一个可检查的 KNN#