一、最懒的算法：什么都不学，只记住

别的算法训练时要反复迭代，KNN 训练时只做一件事： 把训练集存起来。 真正的工作全在预测时——来一个新点，算它到每个训练点的距离，排序，取前 k 个， 看这 k 个里哪类多。 所以「训练快、预测慢」是它的天生属性。 数据集小的时候无所谓，上百万条时每预测一个点都要扫全表，就受不了了。 工业界的对策是近似最近邻：先建索引（KD 树、HNSW），查的时候只扫一部分。 这也带来一个别的好处： 新数据来了直接加进去就行，不用重新训练。 推荐系统里那种「用户行为天天在变」的场景， 这一点很值钱。 还有一点常被忽略：KNN 是非参数方法。 它不假设数据长什么样，所以能拟合任意形状的边界。 代价是它必须把数据全留着——模型大小等于数据大小。

二、k 是唯一的旋钮，但它很难拧

k = 1 时，每个训练点最近的邻居就是它自己（距离为 0），所以训练准确率必然是 1.0000。 这个分数没有任何意义，它只说明算法能把自己找回来。 k 变大，相当于让更多邻居参与投票，边界变得更平滑。 k 太小，模型跟着噪声走（一个标错的点会影响它周围一片）； k 太大，边界被抹平，远处的点也开始影响判断。 Demo 里 k 从 1 加到 3，测试从 0.8667 升到 0.8833，再往上就不动了。 原因是这份数据只有 120 个训练点、10% 的标签还是错的——0.8833 已经顶到噪声决定的天花板。 选 k 的正规做法还是在验证集上试（第 4 章）。有个经验值可以先试：k 取训练样本数的平方根。 120 个样本对应 k 约 11——但这个值只是起点，不能当结论。 还有一个变体值得知道：加权 KNN。 距离近的邻居票数更重（按距离倒数加权），这样 k 大一点也不会把近处的信息稀释掉。 多数库都支持这个选项。

三、距离怎么定义，直接影响结果

KNN 全靠距离，所以「距离」怎么算就是模型设计的一部分。教材提了欧氏距离和曼哈顿距离两种。 欧氏距离是直线距离，各维差平方相加再开方；曼哈顿距离是各维差的绝对值相加，像走街区一样只能横竖走。 后者对离群维度更宽容，因为不像欧氏那样把大差平方放大。 还有一个更根本的问题：各维的量纲不一样怎么办？ 一个特征以万元计、一个以百分比计， 直接相加等于让前者独吞距离。 所以 KNN 之前必须标准化——这是 1.2 节量过的事，当时准确率从 0.3556 跳到 0.9333。 如果特征之间相关性很强（比如身高和体重），标准欧氏距离会重复计算同一份信息。 这时可以用马氏距离：先白化再算距离，等于先把相关维度去重。这本书没展开，知道有这条路就行。

四、维度灾难：高维里没有「邻居」

这是 KNN 最根本的限制，也是整本书最值得记住的一条。 在二维平面上撒点，「最近的点」和「最远的点」距离差得很远——邻居是有意义的。 但维度一高，所有点之间的距离会趋同：最近的那个和 farthest 那个差不了多少。 Demo 里量得很清楚：维度 2 时最远是最近的 19.6 倍；维度 20 时 2 倍；维度 100 时只有 1.34 倍。 当所有点都差不多远时，「找最近的 k 个」等于随机挑 k 个，KNN 就退化成瞎猜。 为什么会这样？ 因为在单位立方体里，随着维度增加， 「大部分体积都集中在角落附近」——点与点之间的距离分布变得越来越集中。 这不是数据的性质，是空间的几何性质。 这个限制不只针对 KNN。 k-means 靠距离、RBF 核靠距离、LLE 和 t-SNE 靠邻居关系，全都会被高维稀释。 所以第 3 章的降维不是选修课，是给这些算法做的前置处理。

五、动手 Demo：不训练，只把邻居的意见平均一下

三类点，每类 60 个，中心在 (0,0)、(2.4,0.3)、(1.2,2.2)。 再把 10% 的标签故意改错——没有这层噪声，k = 1 就够用，看不出 k 的作用。 训练 120 个、 测试 60 个。 第二部分换一个完全不同的实验：随机点、维度从 2 加到 100，量「最近邻」和「最远邻」的距离比。 这一段和分类无关，它要说明的是空间的几何性质。

import numpy as np

def knn(Xtr, ytr, x, k):
    d = ((Xtr - x) * (Xtr - x)).sum(axis=1)   # 和每个训练点算距离
    idx = np.argsort(d)[:k]                   # 取最近的 k 个
    return ytr[idx].mean()                    # 投票

for k in (1, 3, 5, 9, 15, 25):
    pred = np.array([knn(Xtr, ytr, x, k) for x in Xte])
    print("k=%2d  测试准确率 %.4f" % (k, (np.abs(pred - yte) < 0.5).mean()))

# 维度灾难：最近邻与最远邻的距离之比
for dim in (2, 5, 20, 50, 100):
    Q = rg.random((200, dim))
    diff = Q - rg.random(dim)
    d = np.sqrt((diff * diff).sum(axis=1))
    print("维度 %3d  最近/最远 = %.3f" % (dim, d.min() / d.max()))

实跑输出：

--------------------------------------------------------------------
KNN：不训练，只把邻居的意见平均一下
--------------------------------------------------------------------

  三类点，每类 60 个，中心分别在 (0,0)、(2.4,0.3)、(1.2,2.2)。
  再把 10%% 的标签故意改错——这一步是为了让 k 的差别显出来。训练 120 个、测试 60 个。
  KNN 没有「训练」这一步，它把训练集原样存下来，来一个测试点就找最近的 k 个邻居投票。

  【一】k 从 1 扫到 25
  k       训练准确率    测试准确率
  ----------------------------------
  1       1.0000        0.8667
  3       0.8500        0.8833
  5       0.8750        0.8833
  9       0.8667        0.8833
  15      0.8583        0.8833
  25      0.8417        0.8833
  k = 1 时训练准确率是 **1.0000**
  ——每个点最近的邻居就是它自己，这分数毫无意义。k 从 1 加到 3，测试从 0.8667 升到 0.8833，
  再往上加就不动了。**这份数据只有 120 个训练点、10% 的标签还是错的，0.8833 已经顶到天花板**
  ——再调 k 也翻不过噪声这道墙。挑 k 的办法只有一个：在验证集上试（第 4 章讲正规做法）。

  【二】维度灾难：维度一高，「最近」这个词就失效了
  维度    最近邻距离    最远邻距离    最近／最远
  ----------------------------------------------
  2       0.0616        1.2120        0.051
  5       0.1508        1.5130        0.100
  20      1.1335        2.2471        0.504
  50      2.2892        3.5390        0.647
  100     3.4180        4.5845        0.746
  在单位立方体里随机撒 200 个点，问「最近的邻居有多近」。维度 2 时最远是最近的 19.6 倍，
  所以「邻居」这个词有意义；到 100 维只剩 1.34 倍——**所有点离你差不多一样远。**
  这时候「找最近的 k 个」等于随机挑 k 个，KNN 就废了。
  这不是 KNN 一家的病。**任何靠距离干活的算法都会被高维稀释**
  ——k-means、RBF 核、甚至 LLE 和 t-SNE 都躲不掉。所以第 3 章的降维不是选修课，
  是给这些算法做的前置处理。

  【三】KNN 的代价：快在训练，慢在预测
  环节        KNN                       线性回归
  --------------------------------------------------------
  训练        什么都不做，只存数据      解一次方程
  预测一个点  要和每个训练点算一次距离  算一次内积
  新数据进来  直接加进去就行            得重新训练
  **「不训练」不是优点也不是缺点，是把成本挪了个位置。**训练集上百万条时，
  KNN 每预测一个点都要扫一遍全表——工业界这时会换成「先建索引再查」的近似最近邻，
  思路还是 KNN 的。

k 那张表第一行就说明问题：k = 1 训练 1.0000、测试 0.8667。 训练满分是因为每个点自己就是最近的邻居——这个分数是自欺欺人。 k 从 1 到 3 涨了一点（0.8667 到 0.8833），之后一直不动。不是 k 再大没用， 是噪声决定了天花板：10% 的标签是错的，任何 k 都无法把这部分错误抵消掉。 维度灾难那段是硬数据。维度 2 时最远是最近的 19.6 倍，到 100 维只剩 1.34 倍。 「邻居」这个概念被稀释掉了。注意这个实验里数据完全是随机的， 没有任何结构——但它说明的不是「数据没结构」，而是「高维空间本身没有远近」。 最后那张三行表是这一节的落点。KNN 快在训练、慢在预测；线性回归正好相反。 「不训练」不是优点也不是缺点，是把成本挪了个位置。

30 秒实验

1. 把 k 加到 51（超过每类样本数的一半），预测会变成什么？为什么？
2. 把 10% 的标签噪声去掉，k 的最优值会变大还是变小？
3. 如果只有 50 个训练样本、却有 100 个特征，KNN 还能用吗？ 比一下「最近邻距离」和「训练集里的平均距离」。

常见误区

1. 用 k = 1 的训练准确率报成绩。1.0000 毫无意义，每个点自己就是自己的邻居。 KNN 必须报测试集，而且必须和别的 k 比。
2. 不标准化就用 KNN。距离会被量纲大的特征独吞，准确率可能从 0.93 掉到 0.35。 这是 1.2 节量过的数。
3. 在高维数据上直接用 KNN。维度一高，距离失去区分度，KNN 会静默劣化——不报错， 只是变得和随机差不多。特征超过几十个时，先降维或先做特征选择。

第 2 章的九个有监督算法讲完了。 第 3 章换一个前提：没有标签。 从 3.1 的 PCA 开始，八个无监督算法一个一个来。

• ☐ （本章完，下一节 3.1 算法 10：PCA）

相关笔记

• 算法 8：神经网络
• 机器学习的步骤
• 40 课 · 图解机器学习 · 索引
• 🧮 图解机器学习算法 · 索引