KNN 近邻分类
不需要训练，不需要公式，看看周围邻居是谁，少数服从多数——这就是 KNN
01 核心原理（大白话版）
你刚搬到一个新城市，不知道附近哪家餐厅好。怎么判断？——问问周围邻居平时去哪吃，多数人去哪你就去哪。
KNN 做的就是这件事：不认识这个新来的点？就看它身边最近的 K 个邻居都是什么类别，谁多就投谁。
算法只有三步
算出新来的点到每一个训练点的距离（用直线距离，即欧氏距离）。
把距离从小到大排好，选出最近的 K 个点作为"邻居"。
K 个邻居里哪个类别最多，新来的点就被归为哪类。
KNN 没有"训练"过程——它把所有训练数据直接存起来，每次预测时才开始计算。所以训练快，但预测慢（每次都要量一遍所有距离）。
K 值怎么选？
K 太小（比如 K=1）
只看最近一个邻居，一个噪声点就能左右结果，容易过拟合，决策边界锯齿状。
K 太大
邻居太多，远处的点也参与投票，边界过于平滑，可能欠拟合，计算量也大。
实践中常用奇数（K=3、5、7）避免平票，用交叉验证找最优 K。
一步步构建 KNN
生成两个空间上分离的簇，打乱顺序让两类交替出现，模拟真实数据的混乱感。
KNN 的核心操作只有一个：算距离。两点之间的直线距离，就是欧氏距离。
对所有训练点按距离排序，取前 K 个，统计各类票数，多的那类就是预测结果。
KNN 没有训练过程——每加入一批点，直接调用 predict 重绘决策边界，观察它如何随数据增多而稳定。
四段拼在一起，加上可视化，就是完整演示代码——看下面。
02 代码
03 学术性讲解
形式化定义
给定训练集 D = {(x₁,y₁), ..., (xₙ,yₙ)}，对于新样本 x，KNN 的预测为：
其中 N_K(x) 是 x 的 K 个最近邻的集合，𝟙 为指示函数。
距离度量
标准 KNN 使用欧氏距离（L₂ 范数）：
也可使用曼哈顿距离（L₁）、闵可夫斯基距离（Lₚ）等。若各维度量纲不同，需先做标准化，否则数值大的维度会主导距离。
复杂度
- 训练：O(1)——只存数据，无需计算
- 预测：O(n·d)——每次预测需遍历全部训练点，n 为样本数，d 为维度
- 空间：O(n·d)——需存储全部训练集
大规模数据下可用 KD 树或 Ball 树加速近邻搜索，将平均查询降至 O(log n)。
决策边界
KNN 的决策边界是 Voronoi 图的组合形式：K=1 时边界即 Voronoi 边界，K 增大时边界趋于平滑。理论上，当 n→∞ 时，1-NN 的错误率不超过贝叶斯最优错误率的两倍。
局限性
- 维度诅咒：高维空间中距离趋于相等，近邻概念失效
- 预测慢：每次预测都需全量计算，不适合实时场景
- 对噪声敏感：K 小时单个离群点可改变预测结果
- 类别不均衡：多数类会占据近邻，可用加权投票（按距离倒数加权）缓解