模型不认识图，也不认识字。它只做一件事：拿到一串数，跟手里存着的一堆数比远近， 然后跟着最近的那个走。 这一节把这件事拆成三个零件——样本、距离、决策规则——再逐个量它们在什么情况下失灵。 结论会有点意外：分类规则怎么改都只差一两个点，真正拖后腿的是维数。
这一节是第 7 章 kNN 的展开版。7.2 里它只露了个脸，这里把它拆开、量清楚。 它也是第 10 章的开头。后面三节讲的全是同一件事的另一半：那串数到底怎么来。 这一节先让你看清「数从哪儿来」比「怎么比」重要得多。
一、三个零件：样本、距离、判断
先把问题摆成最小可量的样子。 平面上造三类点，每类 30 个训练、25 个测试，三个类中心分别在 (2.0, 2.2)、(5.8, 2.6)、 (3.9, 6.2)，噪声标准差 1.4。 三团点互相压着一部分，这是故意的——分得太开就什么都量不出来了。 然后换四种判断规则，其余全不动：
| 规则 | 怎么判 | 测试准确率 |
|---|---|---|
| 最近邻（k=1） | 跟最近的那一个样本同类 | 0.9200 |
| 3 个近邻投票 | 最近三个里占多数的那类 | 0.9333 |
| 5 个近邻投票 | 最近五个里占多数的那类 | 0.9333 |
| 离类中心最近 | 谁的平均位置离得近算谁 | 0.9200 |
| 四种规则全在 0.92 到 0.93 之间，差了 1.3 个点。 | ||
| 这就是模式识别的第一个反直觉之处：规则怎么选，几乎不影响结果。 | ||
| 再看 k=1 的错都错在哪儿： |
| 真实类别 | 判成 1 类 | 判成 2 类 | 判成 3 类 |
|---|---|---|---|
| 1 类（25 个） | 23 | 0 | 2 |
| 2 类（25 个） | 3 | 21 | 1 |
| 3 类（25 个） | 0 | 0 | 25 |
| 错全发生在 1 类和 2 类的交界处，3 类一个都没错。 | |||
| 这不是算法偏心，是那两团的中心本来就只隔 3.9——噪声标准差 1.4，两团必然重叠。 |
二、把决策区域画出来
光看准确率没有画面感。Demo 第 2 段把整个平面铺成 18 行 24 列的格子，每格按 k=1 判一个类别， 再把训练样本的落点标成 o，画了一张决策区域图。 那张图上三类各占一片，边界弯弯曲曲，1／2／3 三个字符就是三类的领地。 盯着它看半分钟，能看出两件事：边界没有一条是直的；样本落点 o 越密的地方，边界越规整。 这张图说明的是「模型」这两个字最朴素的含义：它不是一个公式，是一张查表。 边界之所以弯弯曲曲，因为它是「哪一格的最近样本是谁」逐格问出来的。 样本密的地方边界就规整，样本稀的地方边界就乱拐——o 挨得越近，边界越像样。 这条性质在后面所有模型里都成立，只是表现形式不一样。
三、k 取多大：拿平滑换边界
k 是唯一的旋钮，扫一遍看看：
| k | 1 | 3 | 5 | 9 | 15 | 25 | 45 |
|---|---|---|---|---|---|---|---|
| 测试准确率 | 0.9200 | 0.9333 | 0.9333 | 0.9067 | 0.9067 | 0.9200 | 0.9200 |
| 最好的落在 k=3（0.9333），可 k=45 也有 0.9200，只差 1.3 个点。 | |||||||
| 老实说这批数据量不出 k 的威力。原因还是那一条： | |||||||
| 三团分得太干净，k 变大变小只是在边界上抹掉或加进一两个点。 | |||||||
| k 真正起作用要在边界模糊、样本又少的时候看： | |||||||
| k 小，一个噪声样本就能在自己周围划出一小块飞地； | |||||||
| k 大，飞地被投票投平，可两个本来贴着的类也会被投成一类。 | |||||||
| 这个取舍方向是确定的，只是这批数据里幅度太小。 |
四、维度灾难：最近邻到底有多「近」
现在换个问题。 前面所有讨论都默认「最近的样本确实很近」，可这件事在几十维、上百维的空间里还成不成立？ 量法很土但有效： 在 d 维单位超立方体里随机撒 400 个点，算每个点的最近邻距离和最远距离，再取这两个数的比值。
| 维数 d | 最近邻距离 | 最远距离 | 比值 |
|---|---|---|---|
| 1 | 0.0008 | 0.7277 | 0.0010 |
| 2 | 0.0220 | 1.0238 | 0.0215 |
| 4 | 0.1433 | 1.3199 | 0.1085 |
| 8 | 0.4396 | 1.7333 | 0.2536 |
| 16 | 0.9063 | 2.2319 | 0.4061 |
| 32 | 1.5984 | 2.9192 | 0.5476 |
| 64 | 2.5707 | 3.8981 | 0.6595 |
| 128 | 3.9371 | 5.2691 | 0.7472 |
| 一维的时候这个比值是 0.001——最近的点几乎贴着你。 | |||
| 128 维的时候它涨到 0.7472，也就是「最近」和「最远」只差两成半。 | |||
| 这意味着什么呢？在 128 维空间里，你随便挑一个点， | |||
| 离它最近的那个点跟最远的那个点，距离差不多是同一个量级。 | |||
| 「近邻」这个词就不再有意义了——没有谁真的近。 | |||
| 顺带一个反直觉的数：最近邻距离本身在变长。 | |||
| 一维 0.0008，128 维 3.9371——涨了四千多倍。 | |||
| 高维空间里，所有的点都彼此远离。 |
五、同样的样本数，摊到高维还剩多少
上面那个实验只看距离，还没看能不能分类。 换成前面那个三类任务，训练样本还是 90 个，只把维数加高——多出来的维度全是纯噪声， 一点类别信息都没有：
| 维数 | 1 个近邻 | 3 个近邻 | 类中心 |
|---|---|---|---|
| 2 | 0.7867 | 0.8400 | 0.8533 |
| 4 | 0.7333 | 0.7600 | 0.8400 |
| 8 | 0.6667 | 0.8000 | 0.8000 |
| 16 | 0.7333 | 0.7600 | 0.8133 |
| 64 | 0.5600 | 0.6267 | 0.7867 |
| 256 | 0.4933 | 0.5200 | 0.6133 |
| 512 | 0.4000 | 0.4133 | 0.5333 |
| 二维的时候 1 个近邻还有 0.7867，三个类中心也有 0.8533。 | |||
| 512 维只剩 0.4000 和 0.5333，而瞎猜的线是 0.3333。 | |||
| 注意最要紧的一点：信息一点没少。前两维原封不动在那儿，类别信息完整保留。 | |||
| 坏就坏在噪声维度把距离撑大了——两个点的距离里，百分之九十九来自那些跟类别无关的维度。 | |||
| 这不是「算法不好」，是「距离这个度量失效了」。 | |||
| 换什么分类器都救不回来，因为它们用的都是同一个距离。 | |||
| 再算一笔账，看能不能靠撒样本填满。 | |||
| 要让 d 维空间里每维切 10 格都至少有一个样本，需要的样本数是 10 的 d 次方： |
| 维数 d | 需要的样本数 |
|---|---|
| 1 | 10 个 |
| 2 | 100 个 |
| 3 | 1000 个 |
| 6 | 100 万个 |
| 10 | 100 亿个 |
| 20 | 1e+20 个 |
| 50 | 1e+50 个 |
| 一张 8 乘 8 的小图就是 64 维。 | |
| 按这张表，靠撒样本把它填满这件事，在宇宙尺度上就不成立。 |
六、所以真正的功夫在特征上
把这一节收一下。模式识别的流程是三步：拿到样本、算距离、按规则判。 Demo 量的结果是：三步里最不该花力气的是第三步。 四种规则差 1.3 个点，k 从 1 调到 45 也只差 1.3 个点。 第一、二步才是命门。样本不够密，边界就乱；维数一高，距离就失灵。 而这两件事指向同一个出路：别把原始数据直接当特征。 把 25 个像素换成 2 个「有意义的数」，距离就重新有意义了—— 这就是下一节要讲的降维。
七、动手 Demo：给样本、给距离、给规则，机器就开始认模式了
五段：四种决策规则、决策区域图、k 的扫描、维度灾难、高维下摊薄。 第 1 段到第 3 段说「规则不关键」，第 4 段和第 5 段说「什么才关键」。 全部用 numpy 手写，没有 sklearn。距离、投票、混淆矩阵都自己算， 这样每一个数在哪儿来的都能指出来。
def knn(TR, TY, X, k=1): # 训练集、标签、要判的样本
d = ((X[:, None, :] - TR[None, :, :]) ** 2).sum(-1) # 两两距离
idx = np.argsort(d, axis=1)[:, :k] # 取最近的 k 个
out = np.zeros(len(X), int)
for i, row in enumerate(TY[idx]):
out[i] = int(np.bincount(row, minlength=NC).argmax()) # 投票
return out
def center_rule(TR, TY, X): # 另一种规则：比到类中心的距离
M = np.array([TR[TY == c].mean(0) for c in range(NC)])
d = ((X[:, None, :] - M[None, :, :]) ** 2).sum(-1)
return d.argmin(1)
# 维度灾难：最近邻距离除以最远距离，看这个比值往哪儿走
q = (P * P).sum(1)
D = np.sqrt(np.maximum(0.0, q[:, None] + q[None, :] - 2.0 * (P @ P.T)))
np.fill_diagonal(D, np.nan) # 自己到自己是 0，得挖掉
print(np.nanmedian(np.nanmin(D, 1)) / np.nanmedian(np.nanmax(D, 1)))
实跑输出：
--------------------------------------------------------------------
给样本、给距离、给规则，机器就开始认模式了
--------------------------------------------------------------------
==============================================================
[1] 模式识别的三个零件：样本、距离、决策规则
造三类二维点，每类训练 30 个、测试 25 个，
三个类中心分别落在 (2.0, 2.2)、(5.8, 2.6)、(3.9, 6.2)，噪声标准差 1.4。
训练集长这样（每类抽 12 个，其余用点代替）：
类 1：(2.5,3.4) (2.5,0.4) (3.3,2.8) (1.2,3.0) (2.5,2.6) (2.0,3.0)
(1.0,2.0) (1.3,3.0) (2.1,1.8) (0.9,1.8) (2.0,1.8) (3.8,3.6)
类 2：(5.9,3.0) (4.4,1.0) (6.1,1.9) (6.1,3.7) (3.5,3.0) (7.5,2.2)
(4.7,3.7) (6.2,3.9) (5.3,0.5) (5.6,2.0) (6.9,2.9) (3.5,0.9)
类 3：(6.0,4.1) (0.4,7.1) (7.5,4.8) (2.1,7.0) (2.7,5.5) (3.4,6.9)
(3.3,6.6) (3.7,5.0) (3.5,4.9) (3.9,4.6) (2.4,8.2) (3.8,6.1)
三种决策规则，同一个训练集、同一个测试集：
最近邻（k=1） 测试准确率 0.9200
3 个近邻投票 测试准确率 0.9333
5 个近邻投票 测试准确率 0.9333
离哪个类中心最近 测试准确率 0.9200
k=1 的混淆矩阵（行是真实类，列是判出来的类）：
判 1 判 2 判 3
真实 1 23 0 2
真实 2 3 21 1
真实 3 0 0 25
[2] 把决策区域画出来
在整个平面上铺 18 乘 24 的格子，每格按 k=1 判一个类别：
字符 1／2／3 是三个类的领地，o 是训练样本落点。
333333333333333333333333
333333333333333333333333
333333o3o333333333333333
33333333333o333333333333
3o33o3333333o33333333333
33333o3ooo33333333333333
33o33o3o3o333333o3333333
3331133o333oo33333333333
3111o3o3oo33333333333333
1111133o3oo3323333o33333
111111111122oooo22222222
111111oo2ooo2o2o2oo22222
111o1oo1oo22ooo2oo222222
1111ooo1o12222o222o2o222
1oo1oo1o112222oo22222222
1o111oo1o22o122222222222
111111o1o22ooo2222222222
o11o1111112222222o222222
**边界不是算出来的，是「每个格子去问最近的样本是谁」问出来的。**
**所以样本密的地方边界准，样本稀的地方边界就弯得莫名其妙。**
[3] k 取多大合适：从 1 一路扫到 45
同一批数据，只改投票人数：
k = 1 测试准确率 0.9200
k = 3 测试准确率 0.9333
k = 5 测试准确率 0.9333
k = 9 测试准确率 0.9067
k = 15 测试准确率 0.9067
k = 25 测试准确率 0.9200
k = 45 测试准确率 0.9200
**最好的落在 k = 3（0.9333）。**
**k 太小，一个噪声点就能在它周围划出一小块飞地；**
**k 太大，边界被抹平，本来分得开的两个类被投票投成一类。**
[4] 维度灾难：最近邻到底有多「近」
在 d 维单位超立方体里随机撒 400 个点，
量「最近邻距离」除以「最远距离」。如果这个数接近 1，
就说明「最近」和「最远」差不多远——近邻这个词就没意义了。
d 最近邻 最远 比值
1 0.0008 0.7277 0.0010
2 0.0220 1.0238 0.0215
4 0.1433 1.3199 0.1085
8 0.4396 1.7333 0.2536
16 0.9063 2.2319 0.4061
32 1.5984 2.9192 0.5476
64 2.5707 3.8981 0.6595
128 3.9371 5.2691 0.7472
**比值从 0.001 一路涨到 0.75。**
**意思是：一百多维的时候，「最近」和「最远」只差三成，近邻这个词基本失效了。**
[5] 同样的样本数，摊到高维还剩多少
还是那个三类任务，训练样本还是 90 个，只把特征维度加高——
多出来的维度全是纯噪声，一点类别信息都没有：
d 1 个近邻 3 个近邻 类中心
2 0.7867 0.8400 0.8533
4 0.7333 0.7600 0.8400
8 0.6667 0.8000 0.8000
16 0.7333 0.7600 0.8133
64 0.5600 0.6267 0.7867
256 0.4933 0.5200 0.6133
512 0.4000 0.4133 0.5333
**二维的时候 1 个近邻还有 0.79，三个类中心也有 0.85；**
**加到 512 维只剩 0.40 和 0.53，而瞎猜的线是 0.33——1 个近邻已经贴着它走了。**
**注意：信息一点没少，前两维原封不动在那儿，是噪声把它冲淡了。**
再算一笔账。要让 d 维空间里每维切 10 格都至少有一个样本，
需要的样本数是 10 的 d 次方：
d = 1 需要 10 个
d = 2 需要 100 个
d = 3 需要 1000 个
d = 6 需要 100 万个
d = 10 需要 100 亿个
d = 20 需要 1e+20 个
d = 50 需要 1e+50 个
**这就是为什么「直接把像素堆成向量丢给最近邻」不行：**
**一张 8 乘 8 的小图是 64 维，靠撒样本是撒不满的。**
**出路只有一条——别用原始像素当特征，去提一种维度低、又抓住要害的特征。**
下一节讲的，就是这条出路。
五段连起来：**模式识别＝样本加距离加规则**；
**k 是拿平滑换边界**；**维度一高近邻就失灵**；
**同样的样本数摊到高维，连三分之一都保不住**；**所以吃功夫的地方不在分类器，在特征。**
第 1 段那张表要横着读：四种规则，从最近邻到类中心，准确率 0.9200 到 0.9333。 这说明「用哪个分类器」在这批数据上几乎不重要。 第 2 段的图是本节的骨架。边界不是算出来的， 是逐格问「最近的样本是谁」问出来的—— 记住这一点，后面看到神经网络画出花里胡哨的边界，你就知道它本质上也在干这件事。 第 4 段那个 0.0010 到 0.7472 的爬升，是整本书里最值得记住的一组数之一。 它解释的不是某个模型不行，是「高维空间」这个几何事实跟直觉差多远。 第 5 段最后那句 0.4000 对 0.3333 要说清楚：不是分类器坏了， 是「最近邻」这个概念在 512 维里已经没意义了。
30 秒实验
- 把第 1 段的噪声标准差从 1.4 改成 2.2，重跑。 四种规则的差距会拉开到 5 个点以上——规则什么时候才重要？两团粘在一起的时候。
- 把第 1 段的训练样本从每类 30 个减到 5 个，重跑。 最近邻会明显掉，类中心反而稳一些——因为类中心只用 25 个数就估出来了，最近邻要用满 5 个。
- 把第 4 段撒的点数从 400 改成 4000，重跑。 比值会更贴近 1——点越多，「最近」和「最远」越接近，这正是高维的诅咒加速的地方。
常见误区
- 以为「换个更好的分类器就能提分」。Demo 第 1 段：四种规则差 1.3 个点。 瓶颈在数据和特征上，不在分类器上。
- 以为「维度越高信息越多，应该更好分」。Demo 第 5 段：512 维只剩 0.4000， 而二维有 0.7867。多出来的维度全是噪声，把距离稀释掉了。
- 以为「维度灾难只是计算慢」。它首先坏的是距离的含义， 然后才是内存和算力。这两件事差着好几个量级的重要性。
- 以为「k 越大越稳」。k 大到把两个类都包进去，投票就投成一类了。 k 是拿平滑换边界，方向是确定的，最优值跟数据有关。
自测三问（点开对答案）
1. 为什么这一节里「换分类器」几乎不影响结果？ —— 因为**这批数据的分开程度已经定死了上限**。 Demo 第 1 段：四种规则 0.9200 到 0.9333， **差 1.3 个点。**错的地方全在 1 类和 2 类的交界处—— **那两团中心只隔 3.9，噪声标准差 1.4，重叠是数据本身的性质，任何规则都绕不开。** 2. 「维度灾难」到底灾在哪儿？ —— **灾在距离这个度量上。**Demo 第 4 段：一维时最近邻距离除以最远距离是 0.0010， **128 维是 0.7472——「最近」和「最远」差不多了。** **这时候「近邻」没有意义，所有基于距离的算法一起失效，换分类器也没用。** 3. 为什么说「撒更多样本」解决不了高维问题？ —— 因为**需要的样本数是指数增长的**。 Demo 最后那张表：每维切 10 格，**10 维要 100 亿个样本，20 维要 1e+20 个。** **而一张 8 乘 8 的小图就是 64 维。** **出路不是撒更多样本，是把维度降下来。**下一节讲怎么降维。思路只有一句话： 既然没用的维度会把距离稀释掉，那就先把没用的维度找出来扔掉。 怎么判断哪个维度没用？ 看数据自己在哪个方向上散得最开——散得最开的方向，往往就是携带信息最多的方向。
- ☐ （本节完，下一节 10.2 特征提取方法）