数据由种子 42 的 LCG 确定性生成（每类 15 点，共 45 点）。距离采用欧氏距离。
红=类 0 / 蓝=类 1 / 绿=类 2 / 黑×=查询点 / 虚线圆=到第 k 个最近邻的距离
k-NN 是一种「懒惰学习」的监督算法：先把训练数据原样记下，到查询时从中选出距离查询点 $\mathbf{x}$ 最近的 k 个点，用它们的多数票预测类别。
二维欧氏距离。训练点 $\mathbf{x}_i = (x_{i1}, x_{i2})$，查询点 $\mathbf{x} = (x_1, x_2)$：
$$d(\mathbf{x},\mathbf{x}_i) = \sqrt{(x_1 - x_{i1})^2 + (x_2 - x_{i2})^2}$$
预测类别。$\mathcal{N}_k(\mathbf{x})$ 是查询点的 k 近邻集合，$y_i$ 是训练点 $\mathbf{x}_i$ 的类别：
$$\hat{y}(\mathbf{x}) = \arg\max_{c}\;\sum_{\mathbf{x}_i \in \mathcal{N}_k(\mathbf{x})}\mathbb{1}[y_i = c]$$
留一法交叉验证精度。$\hat{y}^{(-i)}$ 是去掉 $\mathbf{x}_i$ 后训练的分类器对其的预测：
$$\text{Acc}_\text{LOO} = \frac{1}{N}\sum_{i=1}^{N}\mathbb{1}[\hat{y}^{(-i)}(\mathbf{x}_i) = y_i]$$
多数票打平时，对各候选类比较到 k 近邻的平均距离，取距离更小的一方作为预测类。
什么是 k 近邻（k-NN）2D 分类模拟器
🙋
我刚开始学机器学习，听说 k 近邻是最简单的算法，但是真的好用，是这样吗？
🎓
是真的。简单说，k-NN 是一种「不学模型」的算法，把训练数据原样记下来就行。来了一个新点，就找「最近的 k 个」，按它们的多数票决定类别——就这么简单。看上面模拟器里的红、蓝、绿点，黑色的 × 是查询点，k=5 时就看最近的 5 个点投票。
🙋
我动一下 k 这个滑块，背景的颜色填充方式完全变了，这是什么？
🎓
那就是「决策边界」。对平面上每个点，计算「如果这是查询点会被预测为哪一类」，再用对应类别的浅色给背景上色。k=1 时边界应该是锯齿状的——因为一个异常点就能把它拽歪。把 k 调到 11 或 21，边界变平滑，但这时又开始看不到细微的结构了。
🎓
都不对，正解是「根据数据来选」。看 LOO 交叉验证精度那张卡——每次拿出训练数据中的一个点，用剩下的预测它，对所有点都做一遍，把正确率统计出来。种子 42 的数据上，k=5 大概在 90% 左右。实务上把 k 取 1、3、5……扫一遍，挑出精度最高的 k。设为奇数以保证多数票不打平，这是惯例。
🙋
我把「训练数据离散度 σ」拉到 3.0，几类点混在了一起，精度一下子掉下来了。
🎓
对，这正是 k-NN 的弱点也是它的强项。数据分得开时精度很高，类别一旦重叠，怎么调 k 都救不回来。实务上先「设计能把类分开的特征」，再去调分类器才有意义。简单的 k-NN 作为基线之所以强，是因为它能诚实地反映你的特征设计是不是真的有效。
常见问题
距离度量必须用欧氏距离吗？
不一定，按用途选。本模拟器用的是二维下最直观的欧氏距离（L2 范数），实务中也常用曼哈顿距离（L1）、余弦相似度、马氏距离等。文本分类等高维稀疏向量场合常用余弦相似度，特征量尺度差异较大时则常用马氏距离。
k-NN 最大的缺点是什么？
预测时的计算成本大。每分类一个新点都要计算与全部训练点的距离，N 个数据点要 O(N)。数据量一大，预测就变慢，难以用于实时场景。实务上用 kd-tree、ball-tree 等空间数据结构，或者 FAISS、Annoy 等近似最近邻库来加速。
需要做特征缩放吗？
是必需的。k-NN 基于距离，尺度大的特征（如年收入）会压制尺度小的特征（如年龄）。请务必进行标准化（均值 0、方差 1）或 Min-Max 归一化。本模拟器使用的是各特征同尺度的二维数据，因此无需缩放即可运行。
把 k 调得太大会怎样？
当 k 接近训练数据数量时，任何查询都会返回「全部数据的多数票」即最频繁类。决策边界几乎消失，少数类永远不会被预测出来。另一方面 k=1 会完美拟合训练数据，容易过拟合。看着 LOO 精度卡片来选合适的 k，是现实可行的做法。
实际应用
推荐系统： 在电影或商品推荐中，把用户或商品表示为多维向量，用 k-NN 找「相似用户」或「相似商品」。Amazon 的「买了这个商品的人还买了……」、Netflix 的协同过滤等都基于这个思想。生产级系统中，要从上亿向量中瞬间取出 k 近邻，背后通常运行着近似最近邻搜索库。
异常检测（Anomaly Detection）： 在生产线传感器数据或网络流量上，可以把「到 k 近邻的平均距离」作为异常分数。正常数据密集分布的空间里，如果一个点的 k 近邻全都很远，就可以判定为「孤立点 = 异常」。模拟器中「查询点到 k 近邻的平均距离」卡片正是这个指标。
图像分类、OCR 的基础： 在手写数字识别（MNIST）等经典基准上，k-NN 在深度学习之前一直是一个强基线。直接把像素值当成 784 维向量，仅用 k-NN 就能达到 3% 左右的错分率。现在仍被用作验证模型合理性的「最低水线」。
地理信息与空间检索： 地图应用里「从当前位置最近的 5 家咖啡馆」这类查询，本质上就是 k 近邻搜索。把经纬度看作二维坐标、距离用球面距离，再用 R-tree 等空间索引加速 k-NN，就是许多地理服务的底层基础。
常见误解与注意事项
最常见的误解是认为「k-NN 不需要训练，所以很简单」 。训练阶段确实只是「把数据存起来」，但代价是预测阶段很重，而特征设计的好坏决定了一切。在模拟器里把「训练数据离散度 σ」拉到 3.0 看看，各类点重叠在一起，无论选哪个 k，LOO 精度都会大幅下降。这说明「特征空间中各类没有被分开」，只靠 k-NN 是解决不了的。即便看起来不需要训练，特征构造阶段仍然需要人脑认真投入。
其次常见的是误以为「k 越大精度越高」 。k=1 确实容易过拟合，但持续增大 k 后，会出现相反的问题——「少数类被多数类吞没」。把模拟器里的 k 从 1 调到 25，观察 LOO 精度。最优 k 在中间某处，且会随数据分布而变化。k 是要根据数据来选的超参数，应通过系统的交叉验证来确定。「一味调大」和「一味取 1」都是错的。
最后，「LOO 精度高，实际部署也会同样精度」这种过度信任很危险 。LOO 交叉验证暗中假设训练数据分布与运行时数据分布一致。实际上，数据采集时间或传感器不同导致的「域偏移」很常见，LOO 上 90% 的模型在生产环境下掉到 70% 是司空见惯的事。模拟器显示的 LOO 精度只是理想条件下的值，部署前请别忘了用 hold-out 验证或时序交叉验证再确认一次。