KNN（K 近邻）

KNN 属于「惰性学习」（Lazy Learning），训练阶段几乎不做计算，只存储全部数据。

• 非参数方法：没有显式参数学习过程，模型即全部训练数据本身
• 分类任务：取 K 个近邻中出现次数最多的类别标签（多数投票）
• 回归任务：取 K 个近邻目标值的均值或加权均值
• 超参数 K：K 越小越易过拟合，K 越大偏差越大，通常用交叉验证选取最优值
• 可解释性强：预测结果可直接追溯到具体的近邻样本，无黑盒之忧

KNN 的核心步骤是距离计算与邻居聚合，距离度量的选择直接决定模型效果。

• 欧氏距离：最常用，适合连续特征且各维度尺度相近的场景
• 曼哈顿距离（L1）：对离群点更鲁棒，适合高维稀疏特征
• 余弦相似度：衡量方向而非大小，常用于文本向量或 Embedding 场景
• 特征标准化：使用前必须对特征做归一化或标准化，否则量纲大的特征会主导距离计算
• 加权 KNN：对距离近的邻居赋予更高权重（如距离倒数），通常比均等投票效果更好

精确 KNN 在大数据下代价极高，工程实践中常用近似最近邻（ANN）方法替代。

• KD 树（KD-Tree）：在低维（维度 ≤ 20）空间高效，平均查询复杂度降至 O(log n)
• Ball Tree：比 KD 树更适合中等维度或非欧距离场景
• HNSW：分层可导航小世界图，是当前工业界 ANN 的主流算法，支持亿级向量毫秒级检索
• FAISS：Meta 开源的相似性搜索库，支持 GPU 加速，内置多种 ANN 索引，是向量数据库的常用底层引擎
• 近似最近邻整体趋势：以少量精度损失换取数量级的检索速度提升，是 RAG 等场景的工程基础

KNN 原始形态在中小规模数据上仍是可靠基线，其近似变体支撑着现代 AI 系统的检索层。

• 推荐系统：协同过滤早期实现即基于用户或物品的近邻相似度
• 异常检测：距离所有邻居都很远的样本被视为离群点
• 医学图像分类：皮肤病变、细胞形态等低维特征场景的快速基线
• 向量数据库与 RAG：语义检索的核心操作本质是 ANN 搜索，FAISS、Milvus、Weaviate 等均基于此
• Embedding 空间探索：在词向量或图像 Embedding 空间中，KNN 可直接可视化语义相似关系

KNN 有几个在实践中必须正视的固有缺陷。

• 维度灾难：高维空间中所有样本点间距离趋于均等，「近邻」概念失效，效果显著退化
• 推理成本高：暴力搜索复杂度 O(Nd)，N 为训练集大小，d 为维度，百万级以上不可用
• 对噪声敏感：K 较小时，单个离群点可直接改变预测结果
• 存储代价大：整个训练集必须常驻内存，无法像参数模型那样压缩表示
• 误区——「不训练就没风险」：KNN 仍会过拟合（K=1 时），特征工程和标准化质量对结果影响极大

KNN 与几个形似概念之间存在容易混淆的关键差异。

• KNN vs K-means：K-means 中 K 是聚类中心数，属无监督学习；KNN 中 K 是近邻数，属有监督学习，共享字母但逻辑完全不同
• KNN vs SVM：SVM 训练后形成紧凑的支持向量表示，推理无需访问原始训练集；KNN 推理必须查询全部训练数据
• KNN vs 决策树：决策树训练后生成可存储的树结构，推理复杂度仅 O(depth)；KNN 推理复杂度 O(Nd)
• 精确 KNN vs ANN：精确 KNN 保证找到最近邻但速度慢；ANN 以极小精度损失换取数量级提速，是工程首选
• KNN vs 语义搜索：语义搜索在 Embedding 空间做 ANN，是 KNN 思想的现代工程化延伸

KNN 是机器学习历史上最早的算法之一，其核心思想持续延伸至今。

• 1951：Evelyn Fix 与 Joseph Hodges 在美国空军技术报告中首提近邻分类思想，奠定非参数分类基础；该报告因保密未公开发表
• 1967：Cover 与 Hart 发表论文「Nearest Neighbor Pattern Classification」（IEEE Trans. Information Theory），证明 1-NN 错误率不超过贝叶斯最优错误率两倍，完成理论奠基
• 1970s–1980s：KD-Tree、Ball Tree 等空间索引结构相继提出，部分缓解低维检索效率问题
• 1990s：scikit-learn 等工具链使 KNN 成为机器学习入门标配算法
• 2019 至今：向量数据库（Milvus、Weaviate、Pinecone 等）兴起，KNN 的近邻检索思想成为 RAG、语义搜索、推荐系统的核心基础设施