k 近邻与距离:最简单的可用算法

k 近邻与距离:最简单的可用算法

本节摘要:k 近邻(K-Nearest Neighbors, KNN)是「懒」到家的算法——训练时什么都不做,把整个训练集存下来,预测时找到离新点最近的 k 个邻居,让它们投票。没有参数要学,没有损失函数要最小化,没有训练阶段。听起来简单得不像能工作,但 KNN 在中小数据集上出奇地有竞争力。本节将吃透它的核心:K 的选择如何控制偏差方差权衡、L1/L2/余弦/闵可夫斯基等距离度量的本质与适用场景、距离加权 KNN、维数灾难(Curse of Dimensionality)为何让 KNN 在高维空间失效,以及 KD 树和球树如何把暴力搜索的 O(n) 降到 O(log n)。KNN 在现代 AI 里无处不在,只是换了名字:向量数据库对嵌入做 KNN 搜索,检索增强生成(RAG)找最近文档块,推荐系统找相似用户——算法一样,规模和数据结构不同。

学习目标

阅读完本节,你应当能够:

1. 从零实现 KNN 分类与回归,支持可配置的 K 和距离加权投票。
2. 对比 L1、L2、余弦、闵可夫斯基距离,为给定数据类型选对度量。
3. 解释维数灾难,演示 KNN 为何在高维空间退化。
4. 构建 KD 树做高效最近邻搜索,分析它何时优于暴力法。

一、问题与直觉

你有一个数据集,新来一个数据点,你要给它分类或预测它的值。与线性回归、SVM 那样从数据学参数不同,你直接找离新点最近的 k 个训练点,让它们投票。

这就是 k 近邻。没有训练阶段,没有参数要学,没有损失函数要最小化。你存下整个训练集,预测时算距离。

听起来简单得不像能用。但 KNN 对很多问题都有竞争力,尤其在中型数据集上;深入理解它会暴露一些根本概念:距离度量的选择(呼应第 1 章第 14 节)、维数灾难、懒学习与急学习之别。

KNN 在现代 AI 里无处不在,只是换了名字。向量数据库对嵌入做 KNN 搜索,检索增强生成(RAG)找最近的文档块,推荐系统找相似用户或物品。算法一样,规模和数据结构不同。

KNN 如何工作

给定带标签的数据点和一个新的查询点:

1. 算查询点到每个点的距离
2. 按距离排序
3. 取最近的 k 个点
4. 分类:k 个邻居多数投票
5. 回归:k 个邻居值的平均(或加权平均)

这就是整个算法。没有拟合,没有梯度下降,没有 epoch。

选 K

K 是唯一的超参数,控制偏差方差权衡:

常见起点是 K = sqrt(N)(N 是数据点数)。二分类用奇数 K 避免平票。

距离度量

距离函数定义什么是「近」。不同度量产生不同邻居、不同预测。

L2(欧氏距离) 是默认值,直线距离。

d(a, b) = sqrt(sum((a_i - b_i)^2))
​

对特征尺度敏感。用 L2 配 KNN 前务必标准化特征。

L1(曼哈顿距离) 取绝对差之和。因不平方,比 L2 更抗离群点。

d(a, b) = sum(|a_i - b_i|)
​

余弦距离 度量向量夹角,忽略大小。对文本和嵌入数据至关重要。

d(a, b) = 1 - (a . b) / (||a|| * ||b||)
​

闵可夫斯基距离(Minkowski) 用参数 p 推广 L1 和 L2。

d(a, b) = (sum(|a_i - b_i|^p))^(1/p)

p=1: 曼哈顿
p=2: 欧氏
p->inf: 切比雪夫(最大绝对差)
​

用哪种度量取决于数据:

加权 KNN

标准 KNN 给所有 k 个邻居等权重。但距离 0.1 的邻居应比距离 5.0 的更重要。

距离加权 KNN 把每个邻居按距离倒数加权:

weight_i = 1 / (distance_i + epsilon)

分类:加权投票
回归:加权平均 = sum(w_i * y_i) / sum(w_i)
​

epsilon 防止查询点恰好命中训练点时除零。

加权 KNN 对 K 的选择不那么敏感,因为远邻居无论如何都贡献很少。

维数灾难

KNN 在高维下退化。这不是模糊担忧,是数学事实。

问题 1:距离趋同。 维度增加时,最大距离与最小距离之比趋近 1。所有点离查询都一样「远」。

在 d 维里,对均匀随机点:

d=2:    max_dist / min_dist = 变化很大
d=100:  max_dist / min_dist ~ 1.01
d=1000: max_dist / min_dist ~ 1.001

当所有距离几乎相等,"最近"就失去意义。
​

问题 2:体积爆炸。 要在固定比例的数据里抓到 K 个邻居,你得把搜索半径扩到覆盖特征空间更大比例。「邻域」在高维下几乎覆盖整个空间。

问题 3:角落主导。 在 d 维单位超立方体里,大部分体积集中在角落附近而非中心。内切球随 d 增大,占的体积份额趋于零。

实践后果:KNN 在 20~50 个特征内表现良好。再多就得先用降维(PCA、UMAP、t-SNE),或用能利用数据内禀低维的树搜索结构。

KD 树:快速最近邻搜索

暴力 KNN 算查询点到每个训练点的距离,每次查询 O(n * d)。大数据集上太慢。

KD 树沿特征轴递归切分空间。每一层在一个维度上按中位数切分。

找最近邻时,先走到包含查询点的叶子,再回溯,只在可能含更近点的相邻分区里检查。

平均查询时间:低维下 O(log n)。但 KD 树在高维(d > 20)退化成 O(n),因为回溯能剪掉的分支越来越少。

球树:中维更好

球树把数据切成嵌套超球而非轴对齐盒子。每个节点定义一个球(球心 + 半径),包含该子树所有点。

相比 KD 树的优势:

• 中维(到约 50)下表现更好
• 处理非轴对齐结构
• 更紧的包围体意味着搜索时能剪掉更多分支

KD 树和球树都是精确算法。对真正大规模搜索(百万点、数百维),改用近似最近邻方法(HNSW、IVF、乘积量化),详见第 1 章第 14 节。

懒学习 vs 急学习

KNN 是懒学习器:训练时不做事,预测时全做事。大多数其他算法(线性回归、SVM、神经网络)是急学习器:训练时做重活建紧凑模型,预测时很快。

懒学习适合:

• 数据集频繁变化(增删点无需重训)
• 只需对很少查询做预测
• 想要零训练时间
• 数据集小到暴力搜索就够快

KNN 用于回归

KNN 回归不再多数投票,而是取 k 个邻居目标值的平均。

prediction = (1/K) * sum(y_i for i in K 个最近邻)

或带距离加权:
prediction = sum(w_i * y_i) / sum(w_i)
其中 w_i = 1 / distance_i
​

KNN 回归产生分段常数(或加权时分段光滑)预测,无法外推到训练数据范围之外。若训练目标都在 0~100 之间,KNN 永远不会预测 200。

二、从零实现

第 1 步:距离函数

实现 L1、L2、余弦、闵可夫斯基距离。直接呼应第 1 章第 14 节。

import math

def l2_distance(a, b):
    return math.sqrt(sum((ai - bi) ** 2 for ai, bi in zip(a, b)))

def l1_distance(a, b):
    return sum(abs(ai - bi) for ai, bi in zip(a, b))

def cosine_distance(a, b):
    dot_val = sum(ai * bi for ai, bi in zip(a, b))
    norm_a = math.sqrt(sum(ai ** 2 for ai in a))
    norm_b = math.sqrt(sum(bi ** 2 for bi in b))
    if norm_a == 0 or norm_b == 0:
        return 1.0
    return 1.0 - dot_val / (norm_a * norm_b)

def minkowski_distance(a, b, p=2):
    if p == float('inf'):
        return max(abs(ai - bi) for ai, bi in zip(a, b))
    return sum(abs(ai - bi) ** p for ai, bi in zip(a, b)) ** (1 / p)
​

第 2 步:KNN 分类器与回归器

构建完整 KNN,支持可配置 K、距离度量、可选距离加权。

class KNN:
    def __init__(self, k=5, distance_fn=l2_distance, weighted=False,
                 task="classification"):
        self.k = k
        self.distance_fn = distance_fn
        self.weighted = weighted
        self.task = task
        self.X_train = None
        self.y_train = None

    def fit(self, X, y):
        self.X_train = X
        self.y_train = y

    def predict(self, X):
        return [self._predict_one(x) for x in X]
​

_predict_one 按 K、度量、是否加权给出预测,完整实现见 code/knn.py。

第 3 步:KD 树做高效搜索

从零构建 KD 树,沿每个维度的中位数递归切分。

class KDTree:
    def __init__(self, X, indices=None, depth=0):
        # 递归切分数据
        self.axis = depth % len(X[0])
        # 沿当前轴的中位数切分
        ...

    def query(self, point, k=1):
        # 走到叶子,再回溯
        ...
​

完整实现(含全部辅助方法与演示)见 code/knn.py。

第 4 步:特征缩放

KNN 必须特征缩放,因为距离对特征量级敏感。范围 01000 的特征会压倒范围 01 的特征。

def standardize(X):
    n = len(X)
    d = len(X[0])
    means = [sum(X[i][j] for i in range(n)) / n for j in range(d)]
    stds = [
        max(1e-10, (sum((X[i][j] - means[j]) ** 2 for i in range(n)) / n) ** 0.5)
        for j in range(d)
    ]
    return [[((X[i][j] - means[j]) / stds[j]) for j in range(d)] for i in range(n)], means, stds
​

三、框架对比

用 scikit-learn:

from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline

clf = Pipeline([
    ("scaler", StandardScaler()),
    ("knn", KNeighborsClassifier(n_neighbors=5, metric="euclidean")),
])
clf.fit(X_train, y_train)
print(f"Accuracy: {clf.score(X_test, y_test):.4f}")
​

scikit-learn 在数据集够大、维度够低时自动用 KD 树或球树,高维数据回退到暴力,可用 algorithm 参数控制。

对大规模最近邻搜索(百万向量),用 FAISS、Annoy 或向量数据库:

import faiss

index = faiss.IndexFlatL2(dimension)
index.add(embeddings)
distances, indices = index.search(query_vectors, k=5)
​

四、可复用产物

本节的从零实现位于 code/knn.py,含四种距离度量、可配置 KNN、KD 树和标准化辅助。把它当作「最近邻」工具箱:中小数据分类回归直接用 KNN;做 RAG、推荐、相似搜索时,把距离度量和加权逻辑搬到向量库的 SDK 上即可。

五、练习

1. 在三类二维数据集上实现 KNN 分类,画出 K=1、K=5、K=15、K=N 的决策边界,观察从过拟合到欠拟合的过渡。
2. 在 2、5、10、50、100、500 维各生成 1000 个随机点,对每个维度算最大成对距离与最小成对距离之比,画比值随维度变化曲线,可视化维数灾难。
3. 在文本分类问题上(用 TF-IDF 向量)对比 L1、L2、余弦距离的 KNN 准确率。哪个最好?为什么文本场景余弦常胜?
4. 实现 KD 树,在 1k、10k、100k 点、2 维/10 维/50 维的数据集上测查询时间 vs 暴力法。到第几维 KD 树不再比暴力快?
5. 为 y = sin(x) + 噪声 构建加权 KNN 回归器,与无加权 KNN 对比 K=3、10、30。展示加权产生更光滑预测,尤其大 K 时。

本节要点回顾

1. KNN 是懒学习:训练时只存数据,预测时找最近 k 个邻居投票(分类)或取平均(回归),零训练时间。
2. K 控偏差方差:K=1 过拟合、K=N 欠拟合,起点用 sqrt(N),二分类用奇数避免平票。
3. 度量决定「近」:L2 默认但敏感尺度、L1 抗离群、余弦看方向适合文本嵌入、闵可夫斯基用 p 推广。
4. 必须特征缩放:距离对量级敏感,标准化是 KNN 前提。
5. 加权 KNN 更鲁棒:邻居按距离倒数加权,远邻居贡献小,对 K 选择不敏感。
6. 维数灾难是数学事实:高维下距离趋同、体积爆炸、角落主导,KNN 在 20~50 维内好用,更高需先降维。
7. KD 树低维快、高维退化:沿轴按中位数递归切分,低维 O(log n)、d>20 退化成 O(n)。
8. 球树中维更优:嵌套超球切分,到约 50 维仍好,包围更紧剪枝更多。
9. 懒 vs 急:KNN 训练快预测慢、适应新数据即加即用;急学习器训练慢预测快、边界训练后固定。
10. KNN 无处不在:向量库、RAG、推荐系统底层都是 KNN,只是规模和数据结构不同。

下一节,我们离开监督学习,进入无监督学习——没有标签时如何用聚类、降维从数据里挖出结构。