AI 工程地基 28｜K 近邻：最笨的办法为什么还能用

K 近邻大概是机器学习里最笨的算法。别的算法都要训练：算梯度、迭代、收敛。它不。训练的时候它只干一件事——把数据原封不动存起来。等新数据来了，算一遍它和每个老数据的距离，挑出最近的 K 个，让它们投票。票多的答案就是答案。

就这么简单。1967 年的论文就证明了，这么笨的办法，错误率最多是理论最优的两倍。它还活得很好——今天所有的向量数据库、所有的 RAG 检索，找"最相关的文档片段"，底层就是这个算法。名字换了，规模大了，内核没变。

一个不需要训练的算法

"没有训练"是什么意思？看时间就明白。5000 个点，KNN 的训练耗时 41 微秒。这 41 微秒里它做的事是把数据复制一份存起来。预测呢？每次查询要跟 5000 个点都算一遍距离，耗时 0.43 秒。

所以 KNN 是个懒算法：训练零成本，预测全成本。别的模型反过来——神经网络训练几个小时，预测毫秒级。这决定了它的适用场景：数据经常变（加个点就行，不用重训）、查询不频繁、数据量不大。

它只有一个旋钮：K 取多少。

K=1 的时候，每个训练点自己就是自己的最近邻，训练准确率必然是 100%。这叫记忆，不叫学习。K 拉大，边界变平滑，抗噪声，但太大了就走向另一个极端——K 等于样本总数时，每个查询的邻居都是所有人，答案永远是多数类，等于什么都没学。

一个常见的起点是 K 取样本数的平方根。课上建议用交叉验证选：300 个样本、5 折、K 从 1 扫到 31，选出来的最优值是 7。注意，7 和平方根建议值 17 差了挺远。启发式只是起点，自己的数据自己说了算。

距离是什么，邻居就是什么

KNN 里"近"的定义完全由距离函数决定。换一个度量，邻居就换一批人。

欧氏距离是默认选项，直线距离，符合直觉。曼哈顿距离把差取绝对值求和，不平方，所以大的差距不会被放大，有离群值时更稳。文本数据要用余弦距离——两个词向量，长度是噪音（文档长短造成的），方向才是意思（话题是什么）。

Minkowski 把这些统一进一个公式，参数 p 从 1 走到无穷：p 等于 1 是曼哈顿，p 等于 2 是欧氏，p 趋于无穷就变成"只看差最大的那一维"。拿 [1,2,3] 和 [4,0,6] 算一遍：p=1 时是 8，p=2 时是 4.69，p 无穷大时是 3。p 越大，最差的那一维说话越算数。

还有一个增强：距离加权。默认 K 个邻居一人一票，但距离 0.1 的邻居凭什么和距离 5.0 的邻居同权？让权重等于 1 除以距离，近的说话大声。加一个小常数防止除以零——万一查询点恰好和某个训练点重合，距离是 0。

高维的坑：数字对不上

KNN 最著名的软肋是维度灾难。课上说：随机点撒在 100 维空间里，最远距离和最近距离之比只剩 1.01；1000 维只剩 1.001。所有点都一样远，"最近"失去意义。

趋势是对的。我在 2 维撒 200 个点，最远最近比是 44；10 维剩 3.0；100 维剩 1.37。收缩肉眼可见。

但那个 1.01，跑不出来。我跑了课上的示例代码，它自己打印的就是 1.3748。距离比要真缩到 1.01，按这个收敛速度，维度还得再加两个数量级。书上的数字是把"维度趋于无穷时的极限"抄成了"100 维时的现状"——方向没错，日程表提前了。顺带一提，第一季讲降维时那张距离表里 100 维印的是 1.02，同一门课两次讲这个现象，两次给的数字不一样，也都和自己的演示代码对不上。

维度灾难伤 KNN 的方式很具体：有用的信息就那么几维，剩下的全是噪音维。做一个实验：标签只由前两维决定（两维之和大于 1 为正类），然后不断往上加纯噪音维。2 维时准确率 97.5%，50 维时掉到 75%。信息没少，但距离被 48 维噪音稀释了，近邻不再"近"在有用的方向上。

所以课程给的经验值是：特征在 20 到 50 维以内，KNN 好用；再高，先降维再查。

不缩放，少数类直接失明

距离是把各维的差加起来的，量纲就是命。年龄的差是个位数，薪水的差是几万。不处理的话，距离几乎完全由薪水决定——算年龄和白没算一样。

课上的演示：一个"年龄大于 45 且薪水低于 4 万"才为正类的数据集，不缩放时准确率 87.5%，缩放后 95%。看起来还行？有个背景数字没印出来：这个数据集 85% 的样本是负类。也就是说，一个什么都不看、闭眼全猜负类的笨蛋也有 85% 的准确率。不缩放的 KNN 只比这个笨蛋高 2.5 个百分点。

真正的伤害藏在召回率里。不缩放时，40 个测试样本里的 6 个正类，只抓到 2 个——因为找邻居只看薪水，年龄那个条件整个失明了。缩放后，6 个抓到 4 个。准确率那个 7.5 个百分点的差距只是表象，少数类从 33% 到 67% 的召回才是缩放买的真正东西。

类别不平衡时看准确率，是统计里的老陷阱。这个演示碰巧撞上了它。

加权投票：分类上白忙，回归上救命

距离加权在分类上演示的效果很尴尬：K 取 3、7、15、25，加权版和普通版的差距是持平、输 2.5 个百分点、输 2.5 个百分点、持平。整场没赢过。演示代码印着"加权让大 K 更安全"的结论，它自己的表格不支持这句话。

回归才是加权的主场。对 sin 曲线加噪音做回归：K=50 不加权时，均方误差 0.0733；加权后 0.0269，好 2.7 倍。原因想通了一半就明白：K 拉到 50，等于让 50 个远近不一的邻居平权平均，远邻居把曲线拉平了；加权让远邻居闭嘴，50 个邻居里真正干活的还是近处那几个。

这里还有个知识点值得记：KNN 回归永远外推不出去。训练目标都在 0 到 100 之间，它就永远不会预测出 200——因为预测是邻居目标值的（加权）平均，平均数不会超出被平均的数。这既是老实，也是天花板。

KD 树：让查询不用遍历所有人

暴力 KNN 每次查询算 n 个距离，点一多就慢。KD 树把空间按特征轴切成小块：第一刀切 x 轴中位数，第二刀切 y 轴中位数，如此递归。查询时先落到查询点所在的叶子，再回头检查那些"可能藏着更近点"的分支，大部分分支直接跳过。

效果实打实：2 维数据、取 5 个最近邻，5000 个点时暴力法 0.62 秒，KD 树 0.006 秒，快 107 倍。正确性我对拍过——随机造 50 个查询，KD 树和暴力法给出的邻居逐个对比，一个不差。

代价是高维失效。维度一高，查询点落在哪个分支都说不清，砍不掉的分支越来越多，最后退化回遍历。所以三维往上 20 维以内 KD 树好用，再高用球树撑到 50 维左右，再往上就是近似方法的天下了——HNSW、IVF 这些向量数据库的看家算法，第一季第 14 课讲过。

KD 树和球树都是精确算法：找出来的就是真最近邻，一个不差。近似方法用"大概率是对的"换速度，这才撑得起十亿级向量。

练习

拿 1000 个随机点，在 2、5、10、50、100、500 维各跑一遍，算最远两两距离和最近两两距离之比，画出随维度收缩的曲线。注意要用全部两两距离——课上那个演示只采了 500 对，采样的最小距离会偏高。想看到比值真贴到 1.01 附近，你得走到多高的维度？跑完这个，维度灾难就不再是书上的四个字了。