什么是 KNN？
KNN（K-Nearest Neighbors，K近邻算法） 是一种简单但强大的监督学习算法。它的核心思想非常直观：近朱者赤，近墨者黑。
当需要预测一个新数据点的类别时，KNN 会找到训练数据中与它最近的 K 个邻居，然后根据这 K 个邻居的类别来投票决定新点的类别。
关键参数：
- K 值：选择多少个近邻。K 越小，模型越复杂（容易过拟合）；K 越大，决策边界越平滑（可能欠拟合）
- 距离度量：通常使用欧氏距离，也可以用曼哈顿距离等
🎯 适用场景
- 小规模数据集：几千到几万样本，KNN 效果很好
- 低维数据：特征维度不太高（避免维度诅咒）
- 复杂决策边界：KNN 能自然地拟合任意形状的边界
- 多分类问题：KNN 天然支持多分类，无需额外扩展
- 推荐系统：基于用户/物品相似度的推荐（协同过滤）
💡 经典应用：手写数字识别、电影推荐、植物分类、医疗诊断辅助
📜 历史渊源
问题背景：1950年代，统计学家面临一个基本问题：给定一个新样本，如何判断它属于哪一类？当时的方法（如线性判别）都需要假设数据的分布形式，但真实数据往往不符合这些假设。
关键突破：1951年，Fix 和 Hodges 提出了一个极其简单的想法：不做任何假设，直接看新样本周围的邻居属于哪一类，少数服从多数。这就是 KNN——可能是最直觉的分类方法。1967年，Cover 和 Hart 证明了一个惊人的理论结果：当数据量趋于无穷时，1-NN 的错误率不超过最优分类器错误率的两倍。
深远影响：KNN 开创了"非参数方法"的先河——不假设数据分布，让数据自己说话。这个思想影响了后来的核方法、局部回归等一系列算法。
趣闻：KNN 被称为"懒惰学习"（Lazy Learning）——训练阶段什么都不做，只是把数据存起来，预测时才开始计算。这种"懒惰"反而是优点：新数据随时可以加入，不需要重新训练。
🔗 发展脉络
⚠️ 局限性
- 维度诅咒：高维空间中，"最近"变得没有意义（所有点距离都差不多）
- 预测速度慢：需要计算到所有训练点的距离
- 存储开销大：需要保存所有训练数据
- 特征尺度敏感：需要对特征进行标准化
- 不平衡数据：多数类会主导投票结果
💡 解决方案：降维（PCA）、KD-Tree/Ball-Tree 加速、特征选择、加权投票
🏢 工业界地位
KNN 在工业界的地位比较特殊：
- 推荐系统：Netflix、Amazon 早期使用基于 KNN 的协同过滤
- 图像检索：以图搜图的核心技术之一
- 异常检测：通过近邻距离判断是否异常
- 基线模型：快速建立基线，评估复杂模型的价值
🎯 现状：在大规模生产环境中，KNN 通常被更高效的近似最近邻（ANN）算法取代，如 FAISS、Annoy、HNSW 等。但 KNN 仍然是理解这些高级算法的基础。
交互式可视化
- 设置 K=1，观察决策边界非常曲折（过拟合）；增大 K 到 15，边界变得平滑（可能欠拟合）
- 点击画布添加「测试点」，观察它如何根据 K 个最近邻居的投票被分类
- 切换「距离度量」为曼哈顿距离，观察决策边界的形状变化
数学原理
距离计算：
对于两个点 $x$ 和 $x'$，常用的距离度量包括：
- 欧氏距离（L2）：$d(x, x') = \sqrt{\sum_i (x_i - x'_i)^2}$
- 曼哈顿距离（L1）：$d(x, x') = \sum_i |x_i - x'_i|$
分类决策：
给定测试点 $x$，找到其 $K$ 个最近邻 $N_K(x)$，然后：
即选择 $K$ 个近邻中出现次数最多的类别。
K 值的影响：
- $K = 1$：最复杂，决策边界不规则，容易受噪声影响
- $K = N$（训练集大小）：最简单，始终预测多数类
- 通常选择奇数 $K$ 避免投票平局
算法复杂度
时间复杂度：O(n·d) 预测，其中 n 是训练样本数，d 是特征维度
空间复杂度：O(n·d) 需要存储所有训练数据
优点：简单直观，无需训练过程，对异常值不敏感（当 K > 1）
缺点：预测需要遍历所有训练数据，对高维数据效果差（维度诅咒）