AI 工程基础体系 · 第 47/100 篇。内容覆盖机器学习、深度学习与生成式 AI；模型、数据、评测、权限和成本会作为同一生产系统处理。

KNN 与近邻方法：距离、索引、维度灾难、分类和回归

KNN（k-Nearest Neighbors，k 近邻）是一类通过“查找与查询样本最接近的训练样本，并利用这些邻居的标签或数值进行预测”的方法。它不先拟合一个显式的参数模型，而是在预测阶段使用训练数据，因此通常被称为惰性学习或基于实例的学习。

KNN 看似简单，但它把机器学习中的几个基础问题直接暴露出来：

什么叫两个样本“相似”；
如何高效找到最近样本；
特征尺度是否改变了距离；
高维空间中“最近”是否仍然有意义；
分类和回归如何从邻居推导预测；
数据更新、延迟、内存、隐私和权限如何影响生产系统。

因此，KNN 不只是一个分类器。它还是理解距离度量、特征表示、向量索引和检索增强生成（RAG）中向量搜索的基础模型。

一、先定义问题：什么是近邻

设训练集为：

D=\{(x_i,y_i)\}_{i=1}^{n}

其中：

$x_i\in\mathbb{R}^d$ 是第 $i$ 个样本的特征向量；
$y_i$ 是标签或目标值；
$n$ 是训练样本数量；
$d$ 是特征维度。

给定一个待预测样本 $x$ ，距离函数记为：

d(x,x_i)

将所有训练样本按距离从小到大排序，距离最小的前 $k$ 个样本组成：

N_k(x)

其中 $N_k(x)$ 表示样本 $x$ 的 $k$ 个近邻，而不是整个数据集。

KNN 的核心过程只有三步：

计算查询样本与候选训练样本之间的距离；
选择距离最小的 $k$ 个样本；
使用这些邻居的标签或目标值产生预测。

“训练”阶段通常只是保存训练数据；真正的主要计算发生在预测阶段。因此 KNN 的训练成本通常较低，但预测成本和存储成本可能较高。

二、距离：近邻方法的真正模型假设

KNN 没有显式学习出一组线性权重，但它并非没有模型假设。它隐含假设：

在当前特征表示和距离函数下，距离较近的样本，其目标值更可能相似。

因此，距离函数实际上决定了模型认为“什么样的样本相似”。

2.1 欧氏距离

最常见的欧氏距离为：

d_2(x,z)=\sqrt{\sum_{j=1}^{d}(x_j-z_j)^2}

其中 $x_j,z_j$ 是两个样本在第 $j$ 个特征上的取值。

平方根不影响距离排序，因此实际实现常常比较平方欧氏距离：

d_2^2(x,z)=\sum_{j=1}^{d}(x_j-z_j)^2

例如：

x=(1,2),\quad z=(4,6)

则：

d_2(x,z)=\sqrt{(1-4)^2+(2-6)^2} =\sqrt{9+16}=5

欧氏距离适合数值型特征，并且通常要求各维度具有可比较的尺度。

2.2 曼哈顿距离和闵可夫斯基距离

曼哈顿距离为：

d_1(x,z)=\sum_{j=1}^{d}|x_j-z_j|

对上面的两个点：

d_1(x,z)=|1-4|+|2-6|=3+4=7

更一般的闵可夫斯基距离为：

d_p(x,z)= \left(\sum_{j=1}^{d}|x_j-z_j|^p\right)^{1/p}

$p=1$ ：曼哈顿距离；
$p=2$ ：欧氏距离；
$p$ 越大，较大的单维差异影响越强。

距离不是越复杂越好。应根据数据生成机制、特征类型和验证集表现选择，而不能只凭习惯使用欧氏距离。

2.3 余弦距离

对向量方向更重要、长度不重要的场景，常用余弦相似度：

\operatorname{cos\_sim}(x,z)= \frac{x^\top z}{\|x\|_2\|z\|_2}

余弦距离常定义为：

d_{\cos}(x,z)=1-\operatorname{cos\_sim}(x,z)

例如文本 TF-IDF 向量或神经网络生成的 embedding 中，向量长度可能受文本长度或表示范数影响，此时方向相似度有时比欧氏距离更符合语义。

但余弦距离并不天然适合所有 embedding。某些模型的向量范数包含有用信息，强制归一化可能损失信号。因此应通过验证集比较归一化与不归一化的效果。

2.4 二值、集合和混合特征的距离

对于布尔特征、标签集合或离散属性，直接使用欧氏距离可能没有合理含义。例如：

“是否付费用户”：0 和 1 的差异可以解释；
“颜色编码为红=1、蓝=2、绿=3”：数值差异并不表示颜色相似程度；
文本类别、设备型号、城市编码：整数编码可能制造虚假的顺序。

常见选择包括：

二值向量：Jaccard、Dice、汉明距离；
类别特征：匹配距离或经过合理编码后使用混合距离；
文本：TF-IDF 加余弦距离；
图像、语音、文本 embedding：根据表示模型和训练目标选择余弦或欧氏距离；
混合数据：分别计算各类特征距离，再加权组合。

混合距离可以写为：

d(x,z)= \sum_{g=1}^{G}\alpha_g d_g(x^{(g)},z^{(g)})

其中：

$g$ 表示特征组；
$x^{(g)}$ 表示第 $g$ 组特征；
$d_g$ 是该组特征的距离；
$\alpha_g$ 是该组距离的权重。

权重必须在验证数据上评估。否则，某一组维度多、数值大，就可能无意中支配全部距离。

三、为什么必须进行特征缩放

考虑两个样本：

x=(年龄=20,\ 收入=50000)

z=(年龄=30,\ 收入=51000)

使用原始欧氏距离：

d(x,z)= \sqrt{(20-30)^2+(50000-51000)^2} \approx1000.05

收入差异几乎完全掩盖了年龄差异。此时模型实际使用的不是“年龄和收入共同决定的相似性”，而是“收入的原始单位决定相似性”。

3.1 标准化

常见标准化为：

x'_j=\frac{x_j-\mu_j}{\sigma_j}

其中：

$\mu_j$ 是训练集第 $j$ 个特征的均值；
$\sigma_j$ 是训练集第 $j$ 个特征的标准差。

重要约束是： $\mu_j$ 和 $\sigma_j$ 只能由训练集计算，不能使用验证集或测试集，否则会造成数据泄漏。

3.2 Min-Max 缩放

另一种常见形式是：

x'_j=\frac{x_j-\min_j}{\max_j-\min_j}

它把特征映射到通常的 $[0,1]$ 区间，但容易受到异常值影响。

3.3 鲁棒缩放

若特征含有明显异常值，可以使用中位数和四分位距：

x'_j=\frac{x_j-\operatorname{median}_j} {\operatorname{IQR}_j}

这并不能自动解决异常值问题，但通常比均值和标准差对极端值更不敏感。

3.4 缩放的边界

缩放不是无条件正确的：

如果业务距离本来就由实际单位定义，盲目标准化可能破坏语义；
对 one-hot 特征和连续特征混合缩放，需要明确每组特征的权重；
如果某一特征在业务上确实重要，应该通过距离权重或特征工程表达，而不是让原始量纲偶然决定权重。

四、KNN 分类：从邻居标签到类别概率

给定分类标签 $y_i\in\{1,\dots,C\}$ ，最基本的 KNN 分类器使用多数投票：

\hat y(x)= \arg\max_{c} \sum_{i\in N_k(x)} \mathbf{1}(y_i=c)

其中：

$c$ 是一个候选类别；
$\mathbf{1}(\cdot)$ 是指示函数，条件成立时为 1，否则为 0；
$\hat y(x)$ 是预测类别。

4.1 分类完整算例

假设一维特征上的训练数据如下：

样本	$x_i$	标签
A	1	红
B	2	红
C	4	蓝
D	7	蓝
E	8	蓝

对 $x=3$ 预测，距离为：

| 样本 | 距离 $|x-x_i|$ | 标签 |
|---|---:|---|
| B | 1 | 红 |
| C | 1 | 蓝 |
| A | 2 | 红 |
| D | 4 | 蓝 |
| E | 5 | 蓝 |

如果 $k=3$ ，邻居是 B、C、A：

红：2 个；
蓝：1 个。

因此预测为红。

如果 $k=2$ ，最近的两个样本 B 和 C 一红一蓝，投票出现平局。实现需要规定平局处理方式，可能受到样本排序、类别编码或距离权重影响。为了降低二分类中平局概率，常见经验是使用奇数 $k$ ，但这不是理论保证，也不适用于所有类别数和任务。

4.2 距离加权投票

普通投票把所有邻居视为同等重要。距离加权则令更近的邻居贡献更大：

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

预测为：

\hat y(x)= \arg\max_c \sum_{i\in N_k(x)} w_i\mathbf{1}(y_i=c)

其中 $\varepsilon>0$ 用来避免距离为 0 时除零。

例如，两个邻居的标签分别为红、蓝，距离分别为 0.1 和 0.9，则权重近似为 10 和 1.11。此时即使只有一个红色邻居，红色也可能明显胜出。

实际实现中也可能使用：

w_i=\frac{1}{d(x,x_i)^p}

或其他核函数。权重函数中的 $p$ 、零距离处理和数值稳定性都属于实现细节，应通过验证而不是默认认为某种形式最好。

4.3 分类概率不是天然校准概率

邻居中某类的比例可以作为局部概率估计：

\hat P(y=c\mid x)= \frac{1}{k} \sum_{i\in N_k(x)} \mathbf{1}(y_i=c)

例如 5 个邻居中有 4 个属于正类，可以得到 0.8。

但这个 0.8 不一定是可靠的概率。它依赖：

$k$ 的大小；
距离定义；
类别是否平衡；
局部样本密度；
训练数据是否具有代表性。

如果下游系统根据概率做风控、拒绝或资源分配，应使用可靠性曲线、Brier score 或校准方法验证概率含义，而不能把邻居比例自动当作经过校准的概率。

五、KNN 回归：从邻居目标值到连续预测

回归目标 $y_i$ 是连续数值时，最常见的 KNN 回归预测是邻居目标值的平均：

\hat y(x)= \frac{1}{k} \sum_{i\in N_k(x)}y_i

距离加权回归为：

\hat y(x)= \frac{\sum_{i\in N_k(x)}w_i y_i} {\sum_{i\in N_k(x)}w_i}

5.1 回归完整算例

假设某查询样本的 3 个近邻如下：

邻居	距离	目标值
A	1	10
B	2	14
C	4	22

普通 KNN 回归：

\hat y=\frac{10+14+22}{3}=15.33

若使用 $w_i=1/d_i$ ，则：

w_A=1,\quad w_B=0.5,\quad w_C=0.25

因此：

\hat y= \frac{1\cdot10+0.5\cdot14+0.25\cdot22} {1+0.5+0.25} = \frac{22.5}{1.75} \approx12.86

距离更近的目标值对预测影响更大。

5.2 KNN 回归的边界行为

KNN 回归的预测通常是邻居目标值的加权平均，因此：

普通平均预测通常落在邻居目标值的最小值和最大值之间；
它不擅长外推到训练目标范围之外；
在稀疏区域，最近邻可能也很远，预测不确定性会升高；
$k=1$ 对噪声非常敏感；
$k$ 太大则会跨越真实局部结构，产生过度平滑。

这说明 KNN 回归是局部插值方法，而不是擅长趋势外推的参数模型。

六、 $k$ 的作用：偏差、方差和局部性

$k$ 决定一次预测使用多少邻居。

$k$ 较小

例如 $k=1$ ：

预测高度局部化；
对噪声、异常点和标签错误敏感；
分类决策边界更复杂；
方差较高、偏差较低。

$k$ 较大

预测更平滑；
对单个异常点不敏感；
可能混入远处、不相关区域的样本；
偏差升高、方差降低。

这一关系可以用验证集选择 $k$ ，而不是仅凭训练集表现。对 KNN，训练集上的 $k=1$ 分类准确率甚至可能接近 100%，因为每个训练样本最接近自己；这并不代表泛化能力好。

在交叉验证中， $k$ 、距离度量、权重方式和预处理应作为一个整体选择。例如，只调 $k$ 而固定错误的距离函数，可能得到一个“补偿错误”的最优值。

七、维度灾难：为什么高维中的“最近”会失效

维度灾难不是单一错误，而是一组随维度增加而出现的问题。对 KNN 最重要的表现是：

数据在空间中变得稀疏；
最近邻和最远邻的距离差异相对缩小；
所有点看起来都差不多远；
局部邻域不再局部，预测质量下降；
索引结构的剪枝效果变差。

7.1 体积增长的直觉

假设每个特征都被缩放到 $[0,1]$ ，希望查询点周围每个维度都落在长度为 $2r$ 的局部区间内，则该邻域体积约为：

(2r)^d

当 $d$ 增加时，即使 $r$ 很小，体积也会迅速变得极小。为了在这个局部区域中找到足够多的样本，训练集规模必须指数级增加。

例如，若每个维度只取中心附近长度为 0.1 的区间：

0.1^5=10^{-5}

在 5 维时，该局部区域约占整体空间的十万分之一；在 20 维时则是：

0.1^{20}=10^{-20}

这意味着有限数据几乎不可能均匀覆盖所有局部区域。

7.2 距离集中现象

对高维随机向量，欧氏距离的平方为：

D^2=\sum_{j=1}^{d}(X_j-Z_j)^2

如果各维独立且同分布，那么 $D^2$ 是多个随机变量的和。根据大数效应，随着 $d$ 增大，距离相对均值的波动可能变小。直观上：

最近点的距离变大；
最远点的距离也变大；
但两者的相对差异变小。

一个常用的集中度指标是：

\frac{D_{\max}-D_{\min}}{D_{\min}}

当这个比值趋近于 0 时，最近邻和最远邻的区分度下降，距离排序难以表达有用的局部结构。

这不是说高维 KNN 必然失败，而是说原始坐标空间中的距离可能不再是有效的相似性依据。若高维数据具有低维流形结构，降维、特征选择或学习表示后仍可能使用近邻方法。

7.3 非信息特征会直接污染距离

设真正有用的特征只有 $x_1$ ，其余 $d-1$ 个特征是独立噪声。欧氏距离平方为：

d^2(x,z)= (x_1-z_1)^2+ \sum_{j=2}^{d}(x_j-z_j)^2

即使第一维存在清晰的预测信号，随着噪声维度增加，后面的累加项也会主导总距离。

因此，添加“可能有用”的特征并不一定改善 KNN。对于近邻模型，特征选择和表示学习尤其重要。

7.4 Hubness：某些点异常频繁成为邻居

在高维空间中，可能出现某些训练点被大量查询样本选为近邻的现象，称为 hubness。它可能来自：

数据分布不均；
向量范数差异；
高维距离集中；
表示空间中的局部密度结构。

结果是少数“枢纽点”对大量预测产生影响，尤其会伤害少数类检索和公平性。诊断时可以统计每个训练点出现在查询近邻列表中的次数，并检查这些点是否是异常点、重复样本或某类样本的代表。

7.5 应对方法

常见方法包括：

删除无信息或高噪声特征；
使用特征选择；
使用 PCA 等降维方法；
使用监督度量学习；
使用适合任务的 embedding；
重新检查归一化和距离函数；
评估不同 $k$ 与局部密度；
对少数类和数据覆盖不足区域单独验证。

降维不是自动修复。PCA 优化的是总体方差，不一定保留分类边界；低维可视化也不等价于低维可预测表示。

八、精确近邻搜索：从线性扫描到索引

最直接的精确 KNN 搜索是对每个查询样本计算它与所有 $n$ 个训练样本的距离。

若特征维度为 $d$ ，单个查询的距离计算量约为：

O(nd)

查询 $m$ 个样本时约为：

O(mnd)

这通常被称为 brute-force 或线性扫描。它的优点是：

结果精确；
实现简单；
适合中小规模数据；
可以高效利用向量化和批量矩阵运算。

缺点是数据规模增长后，在线延迟、CPU/GPU 成本和带宽成本都会上升。

8.1 KD-tree

KD-tree 递归地按某个坐标轴切分空间，把样本组织成树结构。查询时先进入与查询点相近的区域，再根据当前最佳距离判断是否需要访问另一侧分支。

它依赖一个关键剪枝条件：

如果某个空间区域到查询点的下界距离已经大于当前第 $k$ 近邻中最远者的距离，则该区域不可能包含更近的点，可以跳过。

KD-tree 在低维、数值型、使用适当距离时可能有效，但高维时大量区域无法剪枝，性能会接近线性扫描。它也更适合静态或低频更新的数据。

8.2 Ball-tree

Ball-tree 使用包围一组样本的球形区域，而不是按单个坐标轴切分。查询时同样通过区域到查询点的距离下界进行剪枝。

相较 KD-tree，它对某些维度和距离度量更灵活，但仍然受高维稀疏性影响，并不存在“维度再高也能保持快速”的保证。

8.3 scikit-learn 中的搜索算法

sklearn.neighbors 中常见的搜索方式包括：

algorithm="brute"：线性扫描；
algorithm="kd_tree"：KD-tree；
algorithm="ball_tree"：Ball-tree；
algorithm="auto"：由实现根据输入选择。

具体选择和支持的度量依赖 scikit-learn 版本、数据类型和参数。auto 是常见实现行为，不应被理解为对所有数据都能自动得到最优性能。工程上应使用目标数据规模和查询分布进行基准测试。

九、近似近邻：用可控误差换取延迟和规模

当向量数量达到百万、千万甚至更大时，常用近似近邻搜索（Approximate Nearest Neighbor，ANN）。

ANN 不保证总能返回真实的前 $k$ 个最近邻，而是通过索引结构快速返回高概率接近真实结果的候选。常见结构包括：

HNSW 图；
IVF 倒排文件；
Product Quantization；
LSH；
基于树或聚类的分区结构。

ANN 的核心权衡是：

\text{召回率} \leftrightarrow \text{延迟、内存、索引构建成本}

其中近邻召回率可以定义为：

\operatorname{Recall@k} = \frac{ |\text{近似搜索返回结果}\cap\text{精确前}k\text{结果}| }{k}

评估 ANN 时，不能只看查询延迟。还需要在一批固定查询上用精确搜索生成基准结果，再测量 Recall@k、P95/P99 延迟、内存占用、构建时间和更新成本。

9.1 ANN 的数据流

一个典型的向量检索路径如下：

flowchart LR
    A[原始对象] --> B[特征工程或 embedding]
    B --> C[向量归一化与版本标记]
    C --> D[近邻索引]
    Q[查询] --> E[查询向量]
    E --> D
    D --> F[候选近邻]
    F --> G[权限过滤与业务重排]
    G --> H[分类、回归或下游生成]

关键路径不是“索引返回结果”就结束：

原始对象生成向量；
向量与模型版本、数据版本、对象 ID 绑定；
索引返回候选；
应用权限过滤；
必要时使用更准确的距离或业务规则重排；
再交给分类、回归、推荐或生成模型。

如果先检索、后做权限过滤，可能出现两个问题：

用户看到本不应访问的对象；
过滤后结果不足，导致召回率下降。

更安全的设计是支持索引内过滤，或者在受控服务端完成过滤；不能把访问控制交给客户端。

9.2 索引不是事实源

向量索引通常是派生数据，而不是原始数据的唯一来源。生产系统需要处理：

原始对象删除后，索引是否同步删除；
embedding 模型升级后，旧向量是否重建；
元数据更新后，过滤字段是否更新；
索引构建中断后，是否能继续或回滚；
查询使用的模型版本是否与索引兼容。

一个安全的发布方式是构建新索引，完成校验后切换别名或版本指针，而不是直接覆盖正在服务的索引。切换前至少检查：

向量数量；
ID 唯一性；
模型和维度版本；
随机查询的 Recall@k；
权限过滤结果；
P95/P99 延迟。

十、一个可运行的 scikit-learn 端到端例子

下面的例子使用乳腺癌二分类数据，展示：

训练集和测试集划分；
仅使用训练集拟合标准化器；
使用 KNN 分类；
评估准确率和分类报告；
访问一个样本的近邻距离和索引。

from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score, classification_report

# 1. 加载数据
X, y = load_breast_cancer(return_X_y=True)

# 2. 分层划分，保证训练集和测试集的类别比例大致一致
X_train, X_test, y_train, y_test = train_test_split(
    X,
    y,
    test_size=0.2,
    random_state=42,
    stratify=y,
)

# 3. 标准化 + KNN
model = Pipeline([
    ("scaler", StandardScaler()),
    ("knn", KNeighborsClassifier(
        n_neighbors=7,
        weights="distance",
        metric="minkowski",
        p=2,
        algorithm="auto",
    )),
])

# 4. 拟合模型
model.fit(X_train, y_train)

# 5. 预测与评估
y_pred = model.predict(X_test)

print("accuracy =", accuracy_score(y_test, y_pred))
print(classification_report(y_test, y_pred))

# 6. 查询测试集第一个样本的 7 个近邻
distances, indices = model.named_steps["knn"].kneighbors(
    model.named_steps["scaler"].transform(X_test[:1]),
    n_neighbors=7,
)

print("neighbor distances =", distances[0])
print("neighbor train indices =", indices[0])

10.1 每一步为什么成立

train_test_split(..., stratify=y) 将数据划分为训练集和测试集，并尽量保持类别比例。测试集不能参与缩放器拟合，否则测试集的均值和方差会泄漏进训练流程。

Pipeline 把标准化与 KNN 绑定在一起。调用 fit 时，StandardScaler 只在 X_train 上学习均值和标准差；调用 predict 时，训练集和测试集使用同一套变换。

weights="distance" 表示距离越近，邻居对投票贡献越大。p=2 表示闵可夫斯基距离退化为欧氏距离。

kneighbors 返回：

distances：每个查询样本到近邻的距离；
indices：这些近邻在传入 KNN 的训练数据中的行号。

这里传入 kneighbors 的查询数据必须先经过与训练阶段相同的标准化。直接把原始 X_test[:1] 传给已经在标准化空间中建立的 KNN，会导致距离空间不一致。

输出中的准确率会因 scikit-learn 版本或环境保持一致时通常稳定，但不应在没有实际执行代码的情况下声称某个固定数值。生产评估还应结合类别不平衡、误报成本和漏报成本选择指标。

十一、KNN 回归的可运行例子

下面使用人工生成的连续目标，演示缩放、KNN 回归和均方误差。

import numpy as np
from sklearn.model_selection import train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsRegressor
from sklearn.metrics import mean_squared_error

rng = np.random.default_rng(42)

# 两个数值特征
X = rng.normal(size=(500, 2))

# 非线性目标，并加入少量噪声
y = (
    2.0 * np.sin(X[:, 0])
    + 0.5 * X[:, 1] ** 2
    + rng.normal(scale=0.1, size=500)
)

X_train, X_test, y_train, y_test = train_test_split(
    X,
    y,
    test_size=0.2,
    random_state=42,
)

model = Pipeline([
    ("scaler", StandardScaler()),
    ("knn", KNeighborsRegressor(
        n_neighbors=10,
        weights="distance",
        p=2,
    )),
])

model.fit(X_train, y_train)
y_pred = model.predict(X_test)

print("MSE =", mean_squared_error(y_test, y_pred))
print("first five predictions =", y_pred[:5])

这里的目标函数是非线性的，KNN 可以通过局部邻居平均近似它。它不需要预先指定正弦函数或二次函数的形式。

但是，若测试点落在训练数据覆盖范围之外，KNN 只能找到相对较远的邻居，通常不会可靠地推断出新的外推趋势。这是 KNN 与线性回归、树模型或带趋势项的时间序列模型的重要区别。

十二、从零实现一个简单的 KNN 分类器

为了看清算法本身，可以实现一个只支持二维欧氏距离的版本：

import numpy as np
from collections import Counter

class SimpleKNNClassifier:
    def __init__(self, k=3):
        if k <= 0:
            raise ValueError("k must be positive")
        self.k = k
        self.X_train = None
        self.y_train = None

    def fit(self, X, y):
        X = np.asarray(X, dtype=float)
        y = np.asarray(y)

        if X.ndim != 2:
            raise ValueError("X must be a 2D array")
        if len(X) != len(y):
            raise ValueError("X and y must have the same number of samples")
        if self.k > len(X):
            raise ValueError("k cannot exceed the number of training samples")

        self.X_train = X
        self.y_train = y
        return self

    def predict(self, X):
        if self.X_train is None:
            raise RuntimeError("fit must be called before predict")

        X = np.asarray(X, dtype=float)
        if X.ndim == 1:
            X = X.reshape(1, -1)

        if X.shape[1] != self.X_train.shape[1]:
            raise ValueError("feature dimension mismatch")

        predictions = []

        for query in X:
            # 对所有训练样本计算平方欧氏距离
            squared_distances = np.sum(
                (self.X_train - query) ** 2,
                axis=1,
            )

            # 取距离最小的 k 个位置
            neighbor_indices = np.argsort(squared_distances)[:self.k]
            neighbor_labels = self.y_train[neighbor_indices]

            # 多数投票
            label = Counter(neighbor_labels).most_common(1)[0][0]
            predictions.append(label)

        return np.asarray(predictions)


X_train = np.array([
    [1.0, 1.0],
    [1.2, 0.9],
    [4.0, 4.0],
    [4.2, 3.8],
])

y_train = np.array(["A", "A", "B", "B"])

model = SimpleKNNClassifier(k=3).fit(X_train, y_train)

X_query = np.array([
    [1.1, 1.0],
    [4.1, 4.0],
])

print(model.predict(X_query))
# 预期输出：['A' 'B']

算法中的中间状态是：

squared_distances 保存查询点到所有训练点的距离；
argsort(... )[:k] 选择距离最小的 $k$ 个索引；
neighbor_labels 取得这些索引对应的标签；
Counter 统计标签频次；
频次最高的标签成为预测结果。

这个实现为了清晰使用了完整排序，单个查询的排序成本约为 $O(n\log n)$ 。实际实现可以使用部分选择算法、批量矩阵运算或专门的索引结构降低常数和排序成本。

它还没有处理：

距离加权；
距离为零；
平局的确定性规则；
缺失值；
类别编码；
大规模索引；
并发访问和内存管理。

因此它适合解释原理，不适合作为生产实现直接部署。

十三、数据泄漏和预处理边界

KNN 对数据预处理很敏感，因为任何预处理都会改变距离。

13.1 错误示例：先对全部数据标准化

# 不推荐：测试集信息参与了 scaler 的拟合
X_all_scaled = StandardScaler().fit_transform(X)
X_train, X_test, y_train, y_test = train_test_split(
    X_all_scaled, y, test_size=0.2, random_state=42
)

这里的均值和标准差使用了测试集数据。即使没有直接使用测试标签，测试集的分布信息也已经进入训练流程。

13.2 正确做法：使用 Pipeline

pipeline = Pipeline([
    ("scaler", StandardScaler()),
    ("knn", KNeighborsClassifier(n_neighbors=5)),
])

pipeline.fit(X_train, y_train)
score = pipeline.score(X_test, y_test)

交叉验证时也必须把预处理放进 Pipeline，这样每个交叉验证折只使用对应训练折拟合变换。

13.3 缺失值

许多 KNN 实现不接受 NaN，或者对 NaN 的距离定义不明确。应在距离计算前处理缺失值，例如：

使用训练集统计量填补；
对缺失情况增加指示变量；
使用能处理缺失值的专门距离；
删除不适合该任务的样本或特征。

填补操作同样只能在训练数据上拟合。若用全量数据计算中位数，也存在泄漏风险。

十四、索引、数据更新和并发

KNN 模型和传统参数模型在生命周期上不同。

14.1 训练阶段

通常包含：

读取训练样本；
清洗和编码；
拟合特征变换；
将变换后的样本写入内存或索引；
保存标签、ID、元数据和版本信息；
用离线数据验证预测指标和近邻质量。

14.2 查询阶段

一次查询通常经历：

校验输入维度、类型和必填字段；
使用固定版本的预处理器转换查询；
调用精确或近似索引；
获取邻居 ID、距离和元数据；
做权限过滤和业务约束；
聚合标签或目标值；
返回预测及必要的诊断字段。

14.3 更新阶段

若直接在正在服务的索引上批量修改，可能出现：

查询看到部分新数据、部分旧数据；
索引构建期间延迟升高；
删除和新增操作顺序导致短暂重复；
进程崩溃后索引状态不一致。

常见的可靠方案是：

从权威数据源构建新索引；
对新索引执行一致性和质量检查；
进行离线查询回放；
原子切换服务指针；
保留旧索引用于回滚；
确认稳定后再清理旧版本。

这属于系统设计习惯，而不是所有库都提供的规范保证。具体索引库的并发读写、删除语义、快照和持久化能力必须查阅对应版本文档并实测。

14.4 并发和资源隔离

KNN 查询的主要资源可能是：

CPU：距离计算；
内存：训练向量、树或图索引；
GPU：大批量距离矩阵；
网络：远程向量索引和元数据服务；
存储：索引持久化和版本保留。

批量查询通常能提高硬件利用率，但会增加单次请求的内存峰值和尾延迟。在线服务应限制：

单请求最大查询数量；
最大 $k$ ；
最大返回元数据大小；
超时和取消行为；
并发队列长度。

当索引服务不可用时，系统应明确选择：

返回可解释的降级结果；
使用较小的本地缓存索引；
转为线性扫描的小数据集；
或直接失败而不生成误导性结果。

对于高风险分类和生成式 AI，静默返回空结果或未经权限过滤的候选通常比显式失败更危险。

十五、距离索引中的权限和数据治理

向量相似不等于用户有权访问。

例如，知识库中同时存在：

公共文档；
某部门内部文档；
单个客户的合同；
含个人信息的工单。

如果把所有向量放进一个共享索引，只依据距离返回结果，可能发生越权检索。尤其在 RAG 中，检索到的文档会进入提示词，随后可能被生成模型复述。

安全边界至少应包含：

文档或向量的租户 ID；
访问控制标签；
数据保留期限；
删除状态；
embedding 模型和版本；
原始对象的审计 ID。

过滤必须发生在受信任的服务端。若只能在索引返回后过滤，应扩大候选集并验证过滤后的有效召回率，但这仍不能把未经授权的内容交给不可信客户端。

向量本身也可能包含敏感信息。删除原文并不代表历史 embedding 自动消失，因此需要定义向量删除、索引重建和备份清理策略。

十六、评测：不要只看分类准确率

KNN 的评测应同时覆盖预测效果、近邻质量和系统代价。

16.1 分类指标

根据任务选择：

Accuracy：类别均衡且错误代价接近时使用；
Precision：误报代价高时关注；
Recall：漏报代价高时关注；
F1：需要平衡 Precision 和 Recall 时使用；
ROC-AUC 或 PR-AUC：评估排序和阈值变化；
混淆矩阵：查看哪些类别容易互相混淆。

少数类问题尤其不能只看 Accuracy。例如 99% 的负类任务，全部预测为负类也可能得到 99% Accuracy，但正类 Recall 为 0。

16.2 回归指标

常见指标包括：

\operatorname{MSE} = \frac{1}{m}\sum_{i=1}^{m}(y_i-\hat y_i)^2

\operatorname{MAE} = \frac{1}{m}\sum_{i=1}^{m}|y_i-\hat y_i|

MSE 对大误差更敏感，MAE 更容易解释。还应按数据密度、时间段、地区、租户或业务类别分组评估，因为 KNN 往往在稀疏区域表现明显变差。

16.3 近邻和系统指标

向量检索还需要评估：

Recall@k；
Precision@k；
MRR 或 NDCG 等排序指标；
P50、P95、P99 延迟；
索引构建和加载时间；
内存占用；
更新延迟；
权限过滤后的有效召回率；
单次查询成本。

对 ANN，必须把近似结果与精确搜索基线比较，否则无法知道“变快了多少、损失了多少”。

十七、常见误解和失败表现

17.1 “KNN 没有训练，所以不需要调参”

KNN 仍然需要选择：

$k$ ；
距离函数；
特征缩放；
特征子集；
距离权重；
精确或近似索引；
类别不平衡处理。

它只是没有传统意义上的大量参数拟合，不代表没有模型选择。

17.2 “维度越多，信息越多，KNN 越好”

无关特征会污染距离，高维还会导致样本稀疏和距离集中。增加特征前应验证：

该特征是否与任务相关；
其尺度是否合理；
是否和已有特征重复；
是否在预测时稳定可得；
是否增加缺失和成本。

17.3 “使用余弦距离就能解决高维问题”

余弦距离消除了向量长度的影响，但没有解决：

表示本身不包含任务相关信息；
高维局部稀疏；
类别分布不平衡；
embedding 模型版本不一致；
权限过滤；
ANN 索引误差。

距离函数只能改变相似性的定义，不能替代有效表示。

17.4 “训练准确率高说明 KNN 有效”

$k=1$ 时，每个训练点通常能找到自己，训练误差很低是自然结果。应使用独立测试集或交叉验证评估，且预处理必须在每个训练折内拟合。

17.5 “索引一定比暴力搜索快”

索引有构建、加载、内存和维护成本。数据量较小、查询批量较大或维度较高时，向量化 brute-force 可能更快、更准确。是否使用 KD-tree、Ball-tree 或 ANN，必须基于真实数据基准测试。

17.6 “返回了最近邻，就等于返回了最相关对象”

距离相近只表示在指定表示空间中相近，不保证：

业务相关；
标签正确；
内容最新；
用户有权限访问；
没有重复或近重复；
满足时间、地域或库存约束。

实际系统经常需要在近邻结果之后进行去重、权限过滤、时间衰减、业务重排或规则校验。

十八、什么时候使用 KNN，什么时候不使用

KNN 适合以下情况：

数据量中小，查询量可控；
局部相似性确实对应目标相似性；
特征表示和距离函数有明确语义；
需要一个简单、可解释的基线；
预测区域主要位于训练数据覆盖范围内；
可以接受预测时访问训练样本或向量索引。

KNN 不适合以下情况：

数据维度高且没有有效表示；
需要极低且严格稳定的在线延迟；
训练数据规模巨大且无法维护索引；
任务要求可靠外推；
特征包含大量类别、缺失或非度量结构，却没有合理距离；
数据更新频繁但索引无法低成本增量维护；
需要强可解释的全局因果关系。

在深度学习和生成式 AI 系统中，KNN 的角色经常从最终预测器变成：

embedding 检索器；
相似案例召回器；
训练样本去重工具；
异常检测辅助工具；
RAG 的候选文档检索器；
监督模型前的局部特征或标签传播组件。

此时最重要的不是“使用了哪个索引库”，而是表示空间、距离定义、召回质量、权限边界和版本一致性是否成立。

十九、核心判断框架

分析一个 KNN 或近邻系统时，可以按以下因果链检查：

\text{数据} \rightarrow \text{特征表示} \rightarrow \text{距离函数} \rightarrow \text{近邻搜索} \rightarrow \text{邻居聚合} \rightarrow \text{评测与业务决策}

任何一环出错，后面的优化都可能失去意义：

特征尺度错误，索引只会更快地返回错误邻居；
表示不包含语义，余弦相似度也没有业务价值；
$k$ 不合适，聚合会过度追随噪声或过度平滑；
ANN 召回率不足，下游分类器无法弥补缺失候选；
权限过滤过晚，预测质量再高也可能构成数据泄漏；
测试集参与预处理，离线指标会高估线上效果；
数据覆盖不足，KNN 可能在远离训练分布的区域给出看似确定、实际不可靠的结果。

KNN 的基础机制可以概括为一句话：

近邻方法不是从数据中直接发现“相似”，而是在选定的特征空间和距离函数中定义“相似”，再用局部样本完成预测。

理解这一点，才能正确处理分类、回归、向量索引、维度灾难，以及机器学习和生成式 AI 生产系统中的检索与决策问题。

系列导航与关联阅读

官方资料

本文依据研究论文、标准组织与主流框架官方文档重新梳理；正文、示例与工程清单由 WR BLOG 编写。