k近邻

k近邻（k-Nearest Neighbors, kNN）是”懒学习”（lazy learning，指训练阶段不构建模型、把所有计算推迟到预测时的范式）的代表作——它根本不训练模型，而是把训练数据原样存起来；预测时在特征空间里找到与待测样本最近的 k 个邻居，让他们投票决定类别（分类）或取平均（回归）。原理极简，却经常是出人意料的好 baseline。前置阅读：监督学习。

核心直觉

把 kNN 想象成**“物以类聚”的常识判断**：

你想知道一栋房子的价格，最朴素的办法不是建复杂模型，而是找最近、最像它的几栋房子，看它们卖多少钱，取个平均。
你要判断一个陌生人的职业倾向，看他身边最常来往的三五个朋友是什么职业，大概率错不了。
kNN 就是把这套”看邻居”的常识变成算法：在特征空间里，离你最近的邻居们，决定了你是什么。

这里隐含一个关键假设：特征空间中的”距离”要能反映样本的真实相似度。如果特征选得差、量纲混乱，“最近”可能毫无意义。所以 kNN 的效果几乎完全取决于特征工程——这正是它”原理简单但调起来麻烦”的根源。

kNN 与前面所有算法的根本区别：其他算法是急切学习（eager learning，训练阶段就把数据浓缩成模型参数的方法），训练阶段把数据浓缩成模型参数；kNN 是懒学习，训练阶段几乎不做事（只存数据），所有计算都推迟到预测时。代价是预测慢，好处是天然支持增量更新——新数据直接加进来即可。

原理详解

算法步骤

给定训练集 $\{(\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2), \dots, (\mathbf{x}_N, y_N)\}$ 和待预测样本 $\mathbf{x}$ ：

计算 $\mathbf{x}$ 与训练集中每个样本 $\mathbf{x}_i$ 的距离 $d(\mathbf{x}, \mathbf{x}_i)$ 。
选出距离最小的 k 个，记为 $\mathbf{x}$ 的 k 个近邻，其索引集合记为 $N_k(\mathbf{x})$ 。
分类：k 个邻居中多数类作为预测（多数投票）。回归：k 个邻居目标值的平均（或按距离加权平均）作为预测。

分类的数学表达（多数投票）：

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

其中 $\mathbb{1}(\cdot)$ 是指示函数（条件成立时取 1，否则取 0）。公式的直觉很简单：遍历 k 个邻居，统计每个类别 c 出现多少次，得票最多的类别就是预测结果。

回归的数学表达（简单平均）：

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

距离加权回归（近邻权重更大）：

\hat{y} = \frac{\sum_{i \in N_k(\mathbf{x})} w_i \cdot y_i}{\sum_{i \in N_k(\mathbf{x})} w_i}, \quad w_i = \frac{1}{d(\mathbf{x}, \mathbf{x}_i) + \epsilon}

其中 $\epsilon$ 是一个极小的正数（如 $10^{-8}$ ），防止距离为 0 时除以零。直觉是：离你越近的邻居，意见越重要；远处的邻居虽然也参与，但权重被距离压低了。

偏差-方差视角

理解 kNN 行为的关键是偏差-方差分解（bias-variance decomposition，一种把模型误差拆分为”系统性偏差”和”对数据波动的敏感性”的分析框架）：

k=1（1-NN）：每个训练点周围形成以它为中心的”势力范围”（Voronoi 单元，即空间中离该训练点最近的所有点构成的区域）。预测完全取决于最近的一个邻居——偏差极低（几乎完美拟合训练数据），方差极高（一个噪声点就扭曲一大片区域的预测）。这就是典型的过拟合。
k=N（全部样本）：无论输入什么，预测都一样——总是返回训练集中最多的类（分类）或全局均值（回归）。偏差极高，方差为零。这就是典型的欠拟合。
最优 k 在两个极端之间，通过交叉验证（cross-validation，将数据反复切分以评估模型泛化能力的方法，详见交叉验证）确定。

Cover 与 Hart（1967）的经典理论结果：当数据量 $N \to \infty$ 时，1-NN 的错误率上界为贝叶斯最优错误率（Bayes error rate，即任何分类器在当前数据分布下能实现的最低错误率）的两倍——这说明 kNN 在理论上有渐近保证。

距离度量

“近”如何定义取决于距离度量，常用：

欧氏距离（L2）：最常用， $d = \sqrt{\sum_{i=1}^{D}(x_i - y_i)^2}$ 。对尺度敏感，必须先标准化特征。直觉上就是初等几何中的”直线距离”。
曼哈顿距离（L1）： $d = \sum_{i=1}^{D} |x_i - y_i|$ ，对各维度差值取绝对值再求和，对异常值更稳健。名称来源于曼哈顿的网格状街道——只能沿坐标轴方向走。
余弦距离：衡量方向而非幅度， $d = 1 - \cos(\theta) = 1 - \frac{\mathbf{x} \cdot \mathbf{y}}{\|\mathbf{x}\| \|\mathbf{y}\|}$ ，文本 / 高维稀疏向量首选。直觉：两个向量”指向同一方向”就算相似，不在乎各自有多长。
闵可夫斯基距离（Minkowski）： $d = \left(\sum_{i=1}^{D} |x_i - y_i|^p\right)^{1/p}$ ，是上面三者的推广： $p=1$ 是曼哈顿距离， $p=2$ 是欧氏距离。
汉明距离（Hamming）：用于类别特征，统计不同维度的个数。

距离度量的选择本质上是定义什么算”相似”，要根据数据语义选择。在 NLP 和推荐场景中，用 embedding（密集向量表示）+ 余弦距离往往优于欧氏距离。

k 的选择

k 是 kNN 最关键的超参数：

k 太小（如 1）：对噪声极度敏感，一个异常点就让预测翻车——高方差、低偏差。
k 太大：邻居范围太广，远处不太像的样本也参与投票，决策边界变模糊——低方差、高偏差，最终退化为”总是预测多数类”。
经验法则：k 取样本数的平方根附近，且通常选奇数（二分类避免平票）。用交叉验证确定最优 k。

加权投票

简单投票的问题：远处和近处的邻居发言权一样。距离加权让近的邻居权重更大（如权重取 $1/d$ ），通常能提升效果，尤其在类别不平衡或数据分布不均时。

sklearn 中只需设置 weights='distance'，它使用 $w_i = 1/d(\mathbf{x}, \mathbf{x}_i)$ ；也可以传入自定义函数实现更灵活的加权方案（如高斯核 $w_i = \exp(-d^2 / 2\sigma^2)$ ）。

维度灾难

kNN 在高维空间会失效——这就是维度灾难（curse of dimensionality，维度升高时数据变得稀疏、距离失去区分力的现象）。维度越高，所有点彼此距离趋于接近，“最近”失去意义：最近邻和最远邻的距离差随维度升高而缩小。

形式化直觉：Beyer 等人（1999）证明，在满足一定条件的高维空间中，最大距离与最小距离之比趋于 1：

\lim_{D \to \infty} \frac{d_{\max} - d_{\min}}{d_{\min}} \to 0

这意味着所有邻居”一样近”，投票变成随机猜测。应对方法：先做降维（PCA、t-SNE、特征选择），或用余弦距离 + 稀疏表示（文本场景），或使用学习到的 embedding（如用预训练 Transformer 提取低维稠密表示）。

加速：KD 树与球树

暴力 kNN 每次预测都要与全部训练样本算距离，复杂度 $O(N \cdot D)$ ，大数据上不可行。加速结构：

KD 树：沿各维度递归切分空间，平均查询 $O(\log N)$ 。适合低维（小于 20 维）。原理：对第 1 维取中位数切两半，对第 2 维再切，轮流进行，构建一棵二叉树；查询时只访问可能包含近邻的子树。
球树：用超球体划分，适合稍高维或不均匀分布。每个节点用一个最小包围球覆盖其所有数据点，查询时利用三角不等式剪枝。
近似最近邻（Approximate Nearest Neighbor, ANN，牺牲少量精度换取大幅加速的近邻搜索方法）：超高维或海量数据用 FAISS、HNSW、Annoy 等近似算法，牺牲一点精度换数十倍加速。现代向量检索几乎都用 ANN。

原理图解

下图展示 k=5 时，一个待预测点（★）在特征空间中找到 5 个最近邻居（实心圆点）并投票的过程——3 个属于类别 A、2 个属于类别 B，因此预测为 A：

动手实践

sklearn kNN 分类与 k 的影响

from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_wine
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler

X, y = load_wine(return_X_y=True)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=42)

# 关键：kNN 对量纲敏感，必须标准化
scaler = StandardScaler().fit(X_tr)
X_tr_s, X_te_s = scaler.transform(X_tr), scaler.transform(X_te)

for k in [1, 5, 11, 21]:
    clf = KNeighborsClassifier(n_neighbors=k, weights='distance')
    clf.fit(X_tr_s, y_tr)
    print(f"k={k}: 测试准确率={clf.score(X_te_s, y_te):.3f}")

用 GridSearchCV 自动选 k

from sklearn.model_selection import GridSearchCV
from sklearn.neighbors import KNeighborsClassifier

# 奇数 k，避免二分类平票
param_grid = {'n_neighbors': range(1, 30, 2),
              'weights': ['uniform', 'distance'],
              'metric': ['euclidean', 'manhattan']}

grid = GridSearchCV(KNeighborsClassifier(), param_grid, cv=5, scoring='accuracy')
grid.fit(X_tr_s, y_tr)
print(f"最优参数: {grid.best_params_}")
print(f"最优交叉验证准确率: {grid.best_score_:.3f}")
print(f"测试集准确率: {grid.score(X_te_s, y_te):.3f}")

numpy 手写 kNN 分类

import numpy as np
from collections import Counter

def knn_predict(X_tr, y_tr, x, k=3):
    # 计算待测点与所有训练点的欧氏距离
    d = np.sqrt(((X_tr - x) ** 2).sum(axis=1))
    # 取距离最小的 k 个邻居的标签
    idx = np.argsort(d)[:k]
    top = y_tr[idx]
    # 多数投票
    return Counter(top).most_common(1)[0][0]

# toy 数据：两类二维点
X_tr = np.array([[1,1],[1,2],[2,1],[5,5],[5,6],[6,5]])
y_tr = np.array([0,0,0,1,1,1])
print("点 [3,3] 预测类别:", knn_predict(X_tr, y_tr, np.array([3,3]), k=3))

距离加权回归（手写）

import numpy as np

def knn_regress_weighted(X_tr, y_tr, x, k=3):
    """距离加权 kNN 回归：权重 = 1/distance"""
    d = np.sqrt(((X_tr - x) ** 2).sum(axis=1))
    idx = np.argsort(d)[:k]
    distances = d[idx]
    targets = y_tr[idx]
    # 加权平均，加 epsilon 防止除零
    weights = 1.0 / (distances + 1e-8)
    return np.sum(weights * targets) / np.sum(weights)

# toy 数据：y = 2x + 噪声
X_tr = np.array([[1],[2],[3],[4],[5]])
y_tr = np.array([2.1, 4.0, 6.2, 7.8, 10.1])
print(f"kNN 回归 (x=3.5): {knn_regress_weighted(X_tr, y_tr, np.array([3.5]), k=3):.2f}")
# 输出约 6.0，接近真实值 7.0

FAISS 做高效向量检索（RAG 场景）

import numpy as np
import faiss

# 模拟 10 万条 768 维文档 embedding（如 BERT 输出）
d = 768
nb = 100_000
embeddings = np.random.randn(nb, d).astype('float32')
faiss.normalize_L2(embeddings)  # 归一化后用内积等价于余弦相似度

# 构建 HNSW 索引（图结构近似最近邻，高精度高速度）
index = faiss.IndexHNSWFlat(d, 32)
index.add(embeddings)

# 查询：找 query 的 5 个最近邻
query = np.random.randn(1, d).astype('float32')
faiss.normalize_L2(query)
distances, indices = index.search(query, 5)
print(f"最近邻索引: {indices[0]}")
print(f"相似度分数: {distances[0]}")
# 在真实 RAG 系统中，这里返回的索引即为最相关的文档片段

实践要点

必须标准化特征：kNN 基于距离，量纲不一致会让数值大的特征主导距离。StandardScaler（Z-score 标准化，化为均值 0 标准差 1）或 MinMaxScaler（缩放到 [0,1]）是标配。
先做特征选择 / 降维：维度越高，距离越没区分力。在百维以上数据上裸跑 kNN 几乎必败，先 PCA 或特征选择。详见降维。
用交叉验证选 k：k 没有万能默认值，对每个数据集单独调。常用范围 1 到 50，奇数优先。
优先用距离加权：weights='distance' 通常优于均匀投票，尤其类别不平衡时。详见类别不平衡。
不平衡数据要小心：多数类天然邻居多，简单投票会偏向多数类。可用加权或调整距离度量。
大数据用近似最近邻：训练集上百万时，sklearn 的 KD 树也吃不消。换 FAISS、HNSW、Annoy 等近似最近邻库。
分类边界是非线性的：kNN 天然能拟合复杂边界，不需要像逻辑回归那样手工构造多项式特征。
embedding 质量决定一切：在现代应用中，kNN 的输入往往是预训练模型的 embedding 向量。模型越好，embedding 空间中”语义相近 = 距离相近”越成立，kNN 效果就越好。
注意数据的尺度与分布：对于计数型或重尾分布的特征，先做对数变换再标准化，比直接标准化更有效。

典型应用

推荐系统的协同过滤：基于用户或物品的 kNN 是推荐系统最经典的协同过滤方法——“喜欢相似物品的用户”就是邻居。详见推荐系统。
手写数字识别：MNIST 用 kNN 配合合适的距离 / 特征可达 97% 以上准确率，是经典的入门任务。
图像检索与以图搜图：用 CNN 提取特征向量后，kNN 在向量库中找最相似的图片——这是 FAISS 等向量检索库的核心使用场景。
文本分类（小数据集）：TF-IDF + 余弦距离 kNN，在数据量不大时效果与朴素贝叶斯相当。
缺失值填补：用 kNN 找最相似的样本，用它们的值填补缺失——sklearn 的 KNNImputer 即此用途。
异常检测的基线：一个点如果最近的 k 个邻居都很远，它可能是异常点。详见异常检测。
大模型 RAG 的向量检索：本质就是 kNN——在 embedding 空间里检索与 query 最相似的文档片段。这也是 2023 年后 kNN 重新成为热点的最大推手。
地理空间查询：找最近的加油站、最近的配送站，底层都是空间 kNN（通常用 R 树加速）。
医疗诊断辅助：根据患者症状特征向量找到历史上最相似的 k 个病例，辅助医生参考已有诊疗方案。

典型类库与工具

类库	语言	说明
sklearn.neighbors.KNeighborsClassifier / Regressor	Python	标准 kNN 实现，支持 KD 树 / 球树 / 暴力三种搜索
sklearn.neighbors.NearestNeighbors	Python	底层近邻搜索接口，可用于推荐、异常检测等
FAISS	Python / C++	Meta 开源的高效向量检索库，GPU 加速，亿级向量秒查
HNSWLib	Python / C++	基于分层可导航小世界图的近似最近邻库，内存效率高
ScaNN	Python / C++	Google 开源的 ANN 库，各向异性量化，精度领先
Annoy	Python / C++	Spotify 开源的基于树的近似最近邻库，适合静态数据
Milvus / Qdrant / Weaviate	多语言	专用向量数据库，内置 kNN / ANN 检索，支持过滤与持久化
NVIDIA cuVS (RAPIDS)	Python / C++	GPU 加速的向量检索库，支持 HNSW、IVF-PQ 等，配合 GPU 训练 pipeline

术语表

术语	英文	解释
k近邻	k-Nearest Neighbors, kNN	基于最近 k 个邻居投票或平均的非参数方法
懒学习	Lazy Learning	训练阶段不构建模型，预测时才计算的范式
急切学习	Eager Learning	训练阶段就把数据浓缩为模型的方法，与懒学习相对
欧氏距离	Euclidean Distance	最常用的直线距离度量，对尺度敏感
余弦距离	Cosine Distance	衡量向量方向相似度的度量，文本与高维稀疏数据首选
维度灾难	Curse of Dimensionality	维度升高时数据变稀疏、距离失去区分力的现象
Voronoi 图	Voronoi Diagram	空间中每个区域归属于离它最近的训练点，1-NN 的决策边界即 Voronoi 图
KD 树	KD-Tree	沿维度递归划分空间的数据结构，加速低维近邻搜索
近似最近邻	Approximate Nearest Neighbor, ANN	牺牲少量精度换取大幅加速的近邻搜索方法
距离加权	Distance Weighting	让更近的邻居有更大投票权重的策略
向量量化	Vector Quantization	将高维向量压缩为更紧凑表示的技术，常用于加速 ANN
向量数据库	Vector Database	专门存储和检索 embedding 向量的数据库，RAG 时代的基础设施

2025-2026 前沿进展

向量数据库成为 AI 基础设施

大模型 RAG（Retrieval-Augmented Generation，检索增强生成）的爆发让 kNN 从”经典教科书算法”变成”现代 AI 栈的核心组件”。2024-2025 年，向量数据库赛道进入白热化竞争与整合期：

Milvus（Zilliz）、Qdrant、Weaviate、Pinecone 等持续迭代，支持十亿级向量的实时插入与亚秒级查询。
主流数据库纷纷引入混合检索（hybrid search），将 kNN 向量检索与 BM25 关键词检索融合（参见 BM25），兼顾语义匹配与精确匹配。
PostgreSQL 生态的 pgvector 扩展日益流行，让传统关系型数据库也能做向量检索，降低了中小项目的接入门槛。

GPU 加速与 cuVS

NVIDIA 在 RAPIDS 生态中推出 cuVS（CUDA Vector Search）库，将 FAISS 风格的 ANN 搜索移植到 GPU 上并深度优化，支持 HNSW、IVF-PQ（一种结合倒排文件与乘积量化的索引方法）等算法。2025 年的 cuVS 版本在十亿级向量上实现了毫秒级查询，同时支持 GPU 上的实时插入与更新，大幅降低了大规模推荐和搜索系统的延迟。

量化与压缩技术成熟

向量量化（vector quantization，将高维浮点向量压缩为更紧凑表示的技术）在 2024-2025 年取得显著进展，成为大规模 kNN 的标配：

乘积量化（PQ） 和 加性量化（AQ） 可以将 768 维 float32 向量压缩到几十字节，内存占用降低 50 倍以上。
二值量化（binary quantization） 将 embedding 压缩为 0/1 比特，配合汉明距离实现极速检索，在可接受精度损失下实现 100 倍加速。
FAISS 和 ScaNN 均内置了多种量化方案，支持量化-精度可调的配置。

Matryoshka Representation Learning（套娃表示学习）

OpenAI 等机构推广的 Matryoshka embedding（2024-2025 年成为主流）是一种自适应维度的 embedding 方案：一个向量从高维到低维”嵌套”——截断前 64 维与截断前 256 维、768 维都是有效的语义表示。这使得 kNN 检索可以灵活地在”快速粗排（低维）“和”精确精排（高维）“之间切换，降低了存储和计算成本。

学习型索引与神经 ANN

传统 ANN 索引（KD 树、HNSW）是手工设计的数据结构。2024-2025 年，学习型索引（learned index）方向持续发展：用小神经网络学习数据分布，自动构建更高效的检索结构。虽然尚未大规模取代 HNSW，但在特定分布的数据（如地理坐标、时间序列）上已展现出优势。

差分隐私近邻搜索

在医疗、金融等敏感场景中，kNN 检索可能泄露训练数据信息。2024-2025 年的研究方向之一是差分隐私 kNN（differentially private kNN），在保证检索结果可用的前提下，对查询结果添加精心设计的噪声，使得攻击者无法从结果反推单个训练样本。这一方向正从理论走向工程实践。

kNN 在基础模型研究中的新角色

2025 年，kNN-LM 和 kNN 分类头 思路重新受到关注：不做 fine-tuning，直接在大模型输出的隐层表示上跑 kNN，从一个外部知识库中检索最相关的表示来辅助预测。这种”无参数修改的知识注入”方式与 RAG 互补，在领域适应和低资源场景中展现了独特价值。

基准与评测

ANN-benchmarks（ann-benchmarks.com）持续更新，覆盖 HNSW、ScaNN、FAISS IVF、NGT 等主流算法的召回率-延迟权衡曲线。2025 年的共识是：HNSW 在大多数中等规模（百万级）场景仍是综合最优；GPU 方案在十亿级以上有不可替代的优势；量化技术则在内存受限时是关键工具。

k近邻