k 近邻
基础 k 近邻不拟合参数化的决策函数。它保存标注点，收到查询后计算距离、排序，取最近 k 个点投票，以多数决定类别。这里没有需要优化的权重，但预处理、选择距离和建立索引仍可能需要工作。
k 只决定截取排序表的位置。同一个查询、同一组距离，在 k=1 和 k=3 时就可能翻转。小 k 能保留细节，也容易跟随错标点；大 k 能平滑孤立噪声，也可能抹掉真实的小群体。
数据就是模型
线性分类器用少量参数概括训练数据，kNN 保留数据本身。暴力版本的设置主要是存储，预测才支付距离与排序的成本。N 个 d 维点需要计算 N 次距离。
本课用欧氏距离 d=√((p₁−q₁)²+(p₂−q₂)²)，它默认各轴可比较。同一特征从米改为毫米，数值扩大千倍，对平方距离的影响扩大百万倍。是否标准化或采用领域度量，应由特征意义决定，并在训练数据上拟合预处理，避免评价泄漏。
KD-tree、ball tree 等精确索引在合适数据上可减少扫描，同时保持精确近邻；最坏情形和高维时可能接近全扫描。HNSW、IVF 等近似索引以可能漏掉近邻为代价换取速度。数据规模、维度、指标质量和延迟共同决定是否适用。
k 改变了什么
k=1 时，一个最近点独自决定，包括错标点。k=N 时所有查询都得到全局多数类，位置不再起作用。增大 k 能压过孤立噪声，也能压过小于周围多数的真实结构；算法没有“噪声”与“小群体”的语义判断。
默认数据同时包含两种情况：A 区中一个误标为 B 的点，以及 B 簇旁两个真实 A 点组成的前哨。k=1 信任误标点，k=9 又吞掉前哨。应在独立验证数据上选择 k，不能用保存的数据给自身打分。
决策地图怎样出现
算法没有保存边界，只保存点与预测规则。动画对 55×55 个网格中心分别做距离、排序、截取、投票，用颜色近似地图。格子边缘不是精确边界。
k=1 对应样本点的 Voronoi 分区。每点在离自己最近的区域发言，包括误标样本。在本课没有冲突重合点的条件下，每个训练点都是自己唯一的零距离近邻，训练准确率为 100%；这并不说明新查询正确。k 增大时小区域可能消失，接近 N 时地图接近全局多数色。
“两座岛”预设承接线性分类器的凸性限制。kNN 的局部投票不要求同类区域连通或凸，三票能保留两岛；改为 13 票后，两岛被全局多数淹没。能表达某种形状，也不保证任何 k 都能保留它。
逐步演示
默认保存 14 点：8 个 A、6 个 B。六个 A 在上半区，五个 B 在右下；(−1,3) 是藏在 A 区的误标 B，画面没有预先标明它。真实 A 前哨在 (0,−3)、(1,−4)。查询 q=(−1,2)，初始 k=3。
- 设置，第 1 拍。 点按标签着色，查询空心；没有权重或已拟合边界。
- 距离，第 2 拍。 14 根虚线连接查询与样本。最近的误标点距离
1.00，真实 A 点(−2,3)、(−2,1)距离√2≈1.41，最远 B 点超过 7。列表先按存储顺序展示。 - 排序，第 3 拍。 按 Python
(d,y)元组排序：距离优先，同距时 A 在 B 前，同距同类保持原顺序。 - 截取与投票，第 4–5 拍。 截止线放在第 3 行下，选出 B、A、A。画圆穿过第三近点，票数为 A 2、B 1。
- 判定，第 6 拍。 查询归 A，依据是距离和投票，不是学习到的打分函数。
- k=3 地图，第 7 拍。 A 在左上、B 在右下，真实 A 前哨保有自己的小区域。
- 改为 k=1，第 8–10 拍。 只把截止线移到第 1 行；距离与排序都不变。误标 B 独占一票，查询翻为 B，A 区中出现 B 岛。保存点上的准确率仍是 100%。
- 改为 k=9，第 11–13 拍。 截取九项，票数 A 6、B 3，查询回到 A。误标岛消失，真实前哨也消失。在
(0,−3)的九近邻中 A 4、B 5，因此真实 A 点被判 B。 - 区分显示规则。 错误圈只统计与真实标签点的冲突，不圈那个误标点。算法并不知道谁是噪声；作者知道标签来源，才可这样区分“修正噪声”和“损失结构”。
- 整个旋钮，第 14 拍。 并排比较 k=1、3、9、13。k=1 留下噪声岛，k=3 兼顾此例的去噪与前哨，k=9 丢掉前哨，k=13 全为 A。14 点中选 13 个，A 至少 7、B 至多 6，所以任何位置都判 A；五个真实 B 点被圈出。
- 结束，第 15 拍。 回到配置的 k=3 和判定 A。存储、距离、排序、截取、投票构成完整过程。
时间与空间复杂度
单次查询距离成本 O(Nd)，完整排序 O(N log N)。只维护最好的 k 项可用 O(N log k) 堆；本课为展示多次截取而保留全排序。模型存储 O(Nd)，复制数据也是 O(Nd)；距离表另占 O(N)。建索引和特征预处理不包含在“只存储”的基础版本内。
精确索引的收益取决于数据，近似索引还可能改变近邻集合乃至类别。预测成本不能仅用一个“训练时间很短”概括。
边界情况
- 查询与样本重合：距离为零，k=1 通常取该标签；若重合样本标签冲突，须按规则破平。距离加权版本还要处理除以零。
- 距离平手：本课按距离、标签、稳定原顺序处理。两类且 k 为奇数，票数不会平手；多类或偶数 k 要另定票数规则，不能无意依赖
most_common(1)的顺序。 - k=N：忽略查询位置，返回全局多数。本例 k=13 已达到同样的单色结果，“仅多数”预设可重跑。
- 查询远离数据：仍会有最近点和类别，没有自动拒绝。外部区域可能由边缘样本主导，不能把答案当作见过相似样本。
- 高维：许多独立特征下，距离可能集中，近点与远点距离比例接近 1。不是所有高维数据必然失败，但必须检查度量、降维或学习到的表示是否保留任务信息。
常见错误
- 期待权重训练步骤。基础版本不优化权重，性能应计入查询、预处理和索引成本。
- 以为同一查询改 k 就重算距离。本演示只改
dists[:k]；查询或数据改变才需重新计算。 - 因 k=1 训练满分就信任模型。独特坐标保证它能查到自己，验证数据才检验泛化。
- 忽略单位与量纲。欧氏平方和可能被数值范围较大的特征主导。
- 把 55×55 色块边缘当精确边界。它只是采样显示，真实投票可能在格子内部变化。