KNN简介

小象实战讲义 · 机器学习算法精讲

从本节起进入一片新天地：经典的机器学习模型（classical machine learning models）——机器学习出现后的几十年里最早诞生、又被大家不断使用至今的一批算法。开篇第一个登场的思路叫 case based reasoning（基于样例的推理）：case 可以理解为一个个具体的样例，对新情况做决策时不是先套公式，而是直接去看”以前发生过的类似案例”。顺着这条路，我们迎来第一个非参数模型：K 最近邻（K-Nearest Neighbors，KNN）。它简单到什么程度？讲师原话：给从来没学过机器学习的人讲机器学习，如果不讲数学和其他东西，往往第一个讲的就是它。本节同时补上它的地基——什么是有参数模型、什么是非参数模型。

💡 核心导读

• 先给 model 正名：百度搜”model”出来的全是模特——我们关心的 mathematical model 长什么样；假设空间里，初级选手只会线性、sin、cos，高级选手才掏得出对数、指数。
• 有参数 vs 无参数：$h_\theta(x)=\theta_0+\theta_1 x$ 里的 $\theta$、正态分布的 $\mu$ 与 $\sigma$，都是有参数模型；KNN 不预设任何函数形式，是第一个非参数模型。
• KNN 怎么干活：物以类聚——找最近的 K 个邻居，分类靠投票、回归靠平均；偶数 K 的平局可以用”距离倒数加权”破解。
• K 的大小是门学问：K=1 把噪声围成小岛（过拟合），K 无穷大退化成”全民公投”；要找既保留 generalization、又有 specification 的中间值。
• 几何与回归两把刀：垂直中线切出的 Voronoi 领地；从”猜英语成绩”到时间序列预测，KNN 的回归用法。

先聊聊 model：从模特到数学模型

讲师先用一个小段子活跃气氛：去百度搜”model”，搜出来的图基本都是模特——生活中绝大多数人理解的 model，是这种”赏心悦目”的 model。但这门课 interested in 的，是数学模型（mathematical model）。这也呼应课程一直在说的：机器学习更像是 Model Learning——我们要 learn 的是 the models，不是 learn 一台真正有质感、看得见摸得着的”机器”。

那数学模型长什么样？回到我们已经熟悉的一件事：整个机器学习的过程，更像是在假设空间（hypothesis space）里搜索一个特别合适的假设。假设空间是什么？它代表人脑对看到的数据的一种解释——你会拿什么样的数学函数去描述它。讲师给了一个很妙的分级：如果你是很初级的选手，可能只会用线性函数、sin、cos；高级一些的，会掏出 log 函数、指数函数，或者其他特别复杂的分布。

有参数的世界：Parametric Model

回看这些函数，会发现一个共同点：都有参数。

• 线性函数（上一章的假设函数）：$h_\theta(x) = \theta_0 + \theta_1 x$，其中 $\theta_0$、$\theta_1$ 就是参数 $\theta$；
• 正态分布：有均值 $\mu$ 和标准差 $\sigma$——这也是参数。

所以以前学的很多模型都叫 Parametric model（有参数模型）。学它的过程可以概括成：给定模型的数学形式，形式里有一组参数 $\theta$；给定参数，数据的分布就定下来了；而 $\theta$ 取多少，由训练数据决定。两个熟悉的场景：

• 分类：class one 是红色的点、class two 是蓝色的点，用一条直线 $h_\theta(x)$ 去拟合——这是一个 parametric model；
• 密度估计：看到一批数据呈某种分布，猜想它是个正态分布，那就用数据 $D$ 去估计均值 $\mu$ 和标准差 $\sigma$——这也是在求一个 parametric model。

（顺带记一个讲师的拼写字眼：parameter 是名词”参数”，parametric 是它的形容词”有参数的”，一字之差。）

但是，机器学习不见得必须做这种假设——不见得非要用一个有参数的模型或函数，来解释数据生成的道理。这就引出了另一种学习模式。

KNN 登场：物以类聚的第一个非参数模型

第一个 nonparametric model（非参数模型）就是 KNN——K-nearest neighbors，最近的 K 个邻居。它主要用来做 classification and regression：分类和预测（拟合）。

场景还是熟悉的两类数据：一类空心圆、一类实心圆，监督学习（supervised learning）已经把训练数据全加好了标签。现在来了一个新数据点，想知道它属于实心还是空心——一个非常直接的分类问题。KNN 的做法按字面意思理解就行：

1. 给定一个 K，比如 K=3：找到离新点最近的三个点（三个邻居）；
2. 这三个点里有两个实心、一个空心——投票，少数服从多数，新点判为实心。分类结束。

非常简单直接的算法。K 还可以继续取：讲师板书里 K=7 的例子，大外圈七个邻居中五个实心、两个空心，仍判实心；K=9、K=11 也都可以；K=1 是极端情况，只找最近的那一个点，一看是实心，判实心——这种就叫最近邻（nearest neighbor）。

“k 不就是参数吗”：一个必须回答的质疑

有同学马上会问：老师，你说 KNN 是 nonparametric model、没有任何参数，那这个 k 不就是参数吗？

讲师的回答：并不完全是这样理解。关键在于——KNN 从头到尾没有假设任何数学模型：我们没有假设数据服从什么分布，也没有假设分类的边界是 sin 函数、直线或任何其他函数。既然没有假设的数学模型，也就没有”模型的参数”。而 k 本身，只是取不同值时性能表现不同的情况（K=3、K=5……）——它控制的是算法”看几个邻居”这个行为，不是嵌在某个数学形式里、要靠数据学出来的量。（术语上，这类由使用者设定、控制算法行为的量，通常叫超参数 hyperparameter。）

偶数 K 行不行：距离加权破平局

紧接着的好问题（课件上原文写着：Q: k has to be an odd number? k 必须是奇数吗？）：投票要分出”多少实心、多少空心”，那一三五七九总能投出来；偶数行不行？ 比如 K=4 找到四个最近点，恰好两实两空——投不出来了，怎么办？

别忘了：还有距离。四个邻居的第一、第二、第三、第四，距离是不一样的。直觉上，距离越小，权重越大：把每个邻居的权重 $w_i$ 设成正比于距离的倒数 $1/d_i$，更近的邻居话语权就更大——这样即使偶数，这个点也仍然会被判为实心，因为实心的那两个点更近。讲师的结论：大家学过的 KNN 例子里 K 几乎都是奇数，但实际上偶数也并没有问题。用代码把这一幕演出来：

# 演示一：KNN 分类——"实心圈 vs 空心圈"，顺带破解偶数 K 的平局
SOLID  = [(1.6, 1.4), (1.4, 1.62), (1.2, 1.3), (1.15, 1.2)]   # 实心圈训练点
HOLLOW = [(1.75, 1.7), (1.62, 1.78), (1.9, 1.85)]             # 空心圈训练点

def dist(p, q):
    return ((p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2) ** 0.5

def neighbors(query, k):
    pts = [("实心", p) for p in SOLID] + [("空心", p) for p in HOLLOW]
    return sorted(pts, key=lambda t: dist(t[1], query))[:k]

query = (1.5, 1.5)   # 待分类的新数据点

for k in (3, 4):
    ranked = neighbors(query, k)
    votes = {}
    for label, _ in ranked:
        votes[label] = votes.get(label, 0) + 1
    print(f"K={k} 邻居(近→远): {[lbl for lbl, _ in ranked]}  票数: {votes}")

# K=4 出现 2:2 平局——用"权重正比于 1/距离"破解
ranked = neighbors(query, 4)
w = {}
for label, p in ranked:
    w[label] = w.get(label, 0.0) + 1.0 / dist(p, query)
print(f"K=4 平局！距离加权票: 实心 {w['实心']:.2f} vs 空心 {w['空心']:.2f}"
      f" -> 判为 {max(w, key=w.get)}")

K=3 邻居(近→远): ['实心', '实心', '空心']  票数: {'实心': 2, '空心': 1}
K=4 邻居(近→远): ['实心', '实心', '空心', '空心']  票数: {'实心': 2, '空心': 2}
K=4 平局！距离加权票: 实心 13.47 vs 空心 6.41 -> 判为 实心

K=3 时两实一空，判实心——正是讲师板书的例子；K=4 时两实两空打成平手，但距离加权的票数 13.47 对 6.41 压倒性倾斜——实心的两个邻居确实更近，平局破解。

K 的大小：从过拟合的小岛到全民公投

K 取不同的值，会产生不同的边界、不同的复杂情况。讲师这里搬出一份”真正的 practical 数据”，并顺手荐书：例子取自 《Introduction to Statistical Learning》——一本黄皮书，斯坦福三位教授写的，有兴趣的同学值得一看。

书里的例子：黄色和蓝色两类点。K=5 时，KNN 画出一条边界——边界右边都属于蓝色，左边都属于黄色。有个细节值得记住：如果新数据恰好落在边界上，代表它分到左边、右边都可以——随机取。（这正好接上偶数之问的极端情形：假如四个邻居两实两空、连平均距离都拉成完全一样，那就随机选一边——总会有办法。）

K=1 呢？边界会出问题：不再是连续的一条——落在黄色区域里的那些蓝色数据，会被割裂成一个小岛一个小岛，各自为政。大家已经学过这是什么：overfitting，过拟合（第 3 章）。它意味着：对训练数据分类分得特别好，连混在黄色区域里的零星蓝色点都被单独划出了”领地”；但也许这些点跑到这边来，只是因为噪声的污染——强行把它们分出来，就是在过度地拟合已知的训练数据。所以 K 比较小时，分类方式反而比较不好。

K 不断增大（3、5、……），边界会越来越平滑。那顺理成章的下一个问题（课件原文：Q: What if K becomes very large? K 非常大会怎样？）：K 取无穷大呢？无穷大个邻居，等于把训练数据的所有点都算上——那还投什么票？哪一类的点数多，任何新数据都直接判给哪一类。这相当于退化成”全民公投”，显然也不是好结果。

结论浮出水面：K=1 不是好结果，K 无穷大也不是好结果——要根据具体的数据，找一个比较均匀的中间 K 值，讲师的原话是：既保留 generalization（泛化），又有很好的 specification（刻画）。怎么找？第 3 章学过的交叉验证正是干这个的工具。

几何视角：垂直中线切出的领地

再往深看一层：如果真把整个平面交给 KNN，它会把这个平面切成什么样？讲师展示了一张蜂窝状的图：红色一类、黑色一类，最近邻（K=1）把整个空间割裂成了一块一块的部分。怎么切出来的？道理出奇地简单：

任何两个点之间，作它们连线的垂直平分线。 比如点一和点二之间画一条黑线：线这边的一切位置都离点一更近，属于点一；线那边的一切位置都离点二更近，属于点二。这条黑线就是两点的分界线。任何两个点都这么切，整个区域就被画成很多小块——每一小块都是某个训练点的”领地”：数据落到这，一定属于红色；落到那，属于黑色。红黑两类通过这种分割方式，把整个平面全部覆盖（cover）——任何一个新数据落进来，总有一块领地接住它、给出判断。

刚才的例子是二维的（特征 $X_1$、$X_2$）。如果给定三个特征 $X_1$、$X_2$、$X_3$，同样的性质在三维空间依然成立——只是两点之间切割出来的不再是中线，而是一张面（垂直于两点的连线）。课件还补了一个漂亮的形容：三维里决策边界的形状，像水晶的表面。这套”每点一领地”的分割，数学上有个名字：Voronoi cells（沃罗诺伊胞元）——课件里给的就是这个词，记住形状即可。

KNN 做 regression：从猜成绩到时间序列

到目前为止所有例子都在做 classification。那 KNN 能不能做 regression（预测）？能。讲师搬出中国一句古话：物以类聚，人以群分——好朋友之间总在一起玩。用 KNN 的思想做预测，就水到渠成了。

猜一个新同学的英语成绩

一个极其简单的例子：班上新来一个同学，想知道他（她）的英语成绩。

• 办法一（什么都不知道）：英语成绩 0 到 100 分，那就当均匀分布随机采样，一猜猜出个 70 分；
• 办法二（知道全班的分布）：大部分同学的成绩都在 60 分以上，80 多分的有一些，70 多、60 多的也有，小于 50 分的人就很少了，40 分不及格的更少——按这个分布的概率取一个值，也许取到 69 分；
• 办法三（KNN 的思想）：我对你并不熟悉，那我找你最近的三个好朋友，把这三个好朋友的英语成绩取个均值——那就有可能是你的成绩。

三个办法一个比一个用到的信息多，而第三个就是 KNN。形式化地说：prediction 是把一个 $x$ 映射到一个连续的 $y$（离散才是 classification）。想知道 $x$ 对应的 $y$，就找 $x$ 的 $K$ 个好朋友 $x_1, \ldots, x_k$（讲师板书把邻居集合记作 $N(x)$——一个有限集合，每个 $x_i$ 都对应一个 $y_i$），然后取算术均值：

$$\hat{y} = \frac{y_1 + y_2 + \cdots + y_k}{k}$$

时间序列：预测 x’=4 处的值

讲师还指了一个具体的用武之地：时间序列预测——KNN 在这方面用得非常好。给定一组采样出来的”小圈圈”数据，它们好像呈某种分布，但我们并不知道；横轴是 $X$、纵轴是 $Y$，两者之间也许有函数关系，也不知道是什么。现在想知道 $x' = 4$ 时，$y'$ 等于多少？

KNN 的做法非常 straightforward：找最近邻。把跟 $x'=4$ 距离上最近的 10 个邻居点圈进一个区域——数一数，一、二、三、四、五、六、七、八、九、十，正好 10 个点；每个点都有对应的 $y$ 值（$y_1$ 到 $y_{10}$），求一个均值，这个均值就是预测的 $y'$（讲师图里那个绿色的点）。

# 演示二：KNN 回归——"小圈圈"时间序列式数据，预测 x'=4 处的值
data = [
    (0.5, 1.3), (1.0, 1.6), (1.4, 2.0), (1.8, 2.3), (2.7, 2.9),
    (3.4, 3.3), (3.65, 3.5), (4.2, 3.9), (4.45, 3.7), (4.75, 4.1),
    (4.95, 3.8), (5.1, 4.2), (5.5, 4.4), (5.8, 4.1),
]

query, k = 4.0, 10
ranked = sorted(data, key=lambda p: abs(p[0] - query))[:k]
avg = sum(y for _, y in ranked) / k
print(f"x'={query} 的 {k} 个最近邻 x 坐标:", [x for x, _ in ranked])
print(f"算术均值预测 y' = {avg:.3f}")

# 算术均值假设 10 个邻居贡献相同——但邻居有远有近，还可以按距离加权
w_avg = sum(y / abs(x - query) for x, y in ranked) / sum(1 / abs(x - query) for x, _ in ranked)
print(f"距离加权预测 y' = {w_avg:.3f}")

x'=4.0 的 10 个最近邻 x 坐标: [4.2, 3.65, 4.45, 3.4, 4.75, 4.95, 5.1, 2.7, 5.5, 5.8]
算术均值预测 y' = 3.790
距离加权预测 y' = 3.755

10 个最近邻落在 2.7 到 5.8 之间（数据里更远的点自动出局），算术均值给出 3.790；考虑距离后加权给出 3.755——更近的邻居（比如 4.2、3.65）话语权更大，估计随之变得更”贴身”。

为什么还需要加权：算术均值的隐藏假设

直接求算术均值，其实悄悄做了一个假设：这 10 个邻居对 $x$ 的贡献是一样一样的。但回头想，我们找的是”最近的”邻居——邻居的距离本来就参差不齐：$x_1$、$x_2$ 离得近，$x_3$、$x_4$ 离得远，那 1 和 2 的贡献就应该超过 3 和 4。所以还可以再进一步，给每个邻居配一个权重 $w_i$——正比于距离的倒数是最常用的一种，当然还可以有其他方式。通过不断调整权重做平滑，有时能把点估计得更精确：讲师展示了两条估计曲线，一条只用算术均值，一条把距离做成权重——两条曲线不一样，哪种更好要按具体问题判断。

加权这步在时间序列里尤其有道理，讲师的直觉描述非常传神：今天发生的情况，跟你昨天直接相关；跟前天也相关，但关系已经弱了很多。所以预测时要看最近这几天——哪一天影响最大，就给那一天赋予更大的权重；而权重到底给多少，需要根据实际情况，或者通过其他知识学得。这也正好呼应课件上那句问话：Q: do we need to adjust the weights?（需要调整权重吗？）——答案取决于你的问题。

📝 动手练一练

1. 替讲师回答质疑：“你说 KNN 是 nonparametric model、没有任何参数，那 k 不就是参数吗？“请给出完整回答，并说明 k 与线性回归中 $\theta_0$、$\theta_1$ 的本质区别。

2. 手算破平局：查询点 q 的 4 个最近邻为——实心点距离 0.2 和 0.3，空心点距离 0.5 和 0.6。① 按”权重正比于 1/距离”加权投票，两类各得多少权重？判给谁？② 若距离反过来（实心 0.5/0.6、空心 0.2/0.3）呢？③ 什么情况下连加权也分不出胜负？

本章小结

本节开了经典模型的新篇：从 case based reasoning 的思想出发，先给 model 正名（我们要的是 mathematical model，不是模特），重温了有参数模型（$\theta$、$\mu$、$\sigma$）与假设空间（初级线性 sin cos、高级 log 指数），随后迎来第一个非参数模型 KNN——不预设任何分布与函数形式，看最近 K 个邻居：分类投票、回归平均。两个精彩问答值得记住：“k 不就是参数吗？“（没有假设的数学模型，就没有模型参数）与”K 必须是奇数吗？“（偶数平局可用距离倒数加权破解）。K 的大小是门学问：K=1 把噪声围成过拟合的小岛，K 无穷大退化成全民公投，要找既保留 generalization 又有 specification 的中间值。几何上，最近邻用垂直中线把平面切成 Voronoi 领地（三维是面，像水晶表面）。回归用法上，从”三个好朋友的成绩均值”到时间序列的 10 邻居预测，再到距离加权（今天跟昨天直接相关、跟前天弱很多），一条”物以类聚，人以群分”的线贯穿到底。

📋 行动清单

学完本节，你可以立即：

• 给外行讲一遍 KNN：不用任何数学，30 秒讲清”看最近 K 个邻居投票/平均”——它本来就是讲给初学者的第一个算法。
• 跑一遍两个演示：把演示一的查询点挪到 $(1.7, 1.8)$（空心圈腹地），观察 K=3/K=4 的投票变化；把演示二的预测点换成 $x'=5.5$，再看均值与加权。
• 荐书到手：找来《Introduction to Statistical Learning》翻一翻 KNN 那章的边界图，亲眼看看 K=1 的小岛与 K 增大后的平滑。

—— 小象教研组