K-Nearest Neighbors (KNN)

K 近邻（KNN）是一种监督学习算法，它根据与新样本距离最近的 k 个已标记样本来预测其标签：分类时对这些邻居进行多数投票，或在回归时取它们的平均值。KNN 是非参数且“惰性”的：它不学习任何权重，而是简单地存储训练数据，并在收到预测请求时才执行全部计算。Evelyn Fix 和 Joseph Hodges 于 1951 年提出了这种方法；1967 年，Thomas Cover 和 Peter Hart 证明，在数据量无限的情况下，单最近邻规则的错误率至多是最佳分类器的两倍。如今，同样的近邻搜索也大规模应用于向量数据库和图像检索系统，这些系统会比较神经网络生成的嵌入。

KNN 如何进行预测#

对于每个查询点，KNN 会执行三个步骤：

1. 计算距离：它会计算查询点与每个已存储样本之间的距离。默认使用欧几里得距离，曼哈顿距离和闵可夫斯基距离也是常见替代方案；对于嵌入，通常使用余弦相似度，因为向量的方向承载其含义。
2. 选择邻居：保留距离最小的 k 个样本。
3. 合并邻居的标签：分类时选择邻居中最常见的类别，回归时则取其数值的平均值。使用距离加权时（在 scikit-learn 中为 weights="distance"），距离更近的邻居权重更高。

每个特征都会影响距离，因此取值范围大的特征会占主导地位：以美元计的收入会压过以年计的年龄。因此，KNN 流程会先标准化特征，或者比较特征提取模型生成的嵌入，使每个维度的取值范围大致相当。

选择 k#

k 值决定了过拟合与欠拟合之间的平衡。k = 1 时，每个训练点（包括含噪声或标签错误的点）都会占据自己的区域，决策边界也会变得曲折。k 值很大时，每次投票都会覆盖远离查询点的区域，从而模糊真实的类别边界。对于两个类别，选择奇数 k 可以避免投票平局，而交叉验证是选择 k 的标准方法。在scikit-learn 的含噪声双月数据集上，这种权衡体现在以下三个数值中：

from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier

# Two interleaving half-moons with overlapping, noisy points
X, y = make_moons(n_samples=1000, noise=0.35, random_state=0)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=0)

# Fitting only stores the points; each prediction is a vote among the k nearest ones
for k in (1, 15, 300):
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X_train, y_train)
    print(f"k={k}: train {knn.score(X_train, y_train):.2f}, test {knn.score(X_test, y_test):.2f}")

k = 1 时，分类器会记住训练点，在训练点上的得分为 1.00，在留出点上的得分为 0.83。k = 15 时，得分分别为 0.90 和 0.89，是三种设置中测试结果最好的；k = 300 时（接近 700 个训练点的一半），决策边界变得过于平滑，两个得分都下降至 0.84 和 0.81。

加速近邻搜索#

暴力搜索会将查询点与 d 维空间中存储的全部 n 个点进行比较，因此每次预测的成本约为 n × d 次运算，内存占用也会随数据集增大。低维场景下，k-d 树和球树等空间划分结构可以跳过大部分比较；scikit-learn 的 algorithm="auto" 会在暴力搜索、k-d 树和球树之间进行选择。高维场景下，维度灾难会使点与点之间的距离几乎相同，树剪枝不再有效，大型系统便会改用近似最近邻（ANN）索引，例如 HNSW 图和带有乘积量化的倒排文件（IVF）索引，这些索引由 FAISS 等库实现。这些索引只需将查询与少量已存储向量进行比较，就能返回大部分真正的最近邻：

KNN 与相关方法的比较#

• K-means 聚类：一种无监督算法，将未标记的点围绕学习得到的质心分成 k 个簇。两者名称中共用一个字母纯属巧合：在 k-means 中，k 表示簇的数量。
• 向量搜索：这是同一操作在检索中的形式：它通常通过近似索引，返回距离查询嵌入最近的已存储项目，应用程序会直接使用这些项目。
• 支持向量机与逻辑回归：这些参数化模型会在训练期间学习决策边界，因此随着训练集增大，预测成本保持不变。

实际应用#

• 推荐系统：基于物品的协同过滤会推荐评分向量或购买向量与用户已经喜欢的物品最接近的产品。
• 异常检测：点到其第 k 个最近邻的距离可作为异常分数，因此，与所有正常样本都相距甚远的交易或传感器读数会显现出来。
• 缺失值填补：scikit-learn 的 KNNImputer 会用最相似的 k 行中该特征的平均值填补每个缺失值。
• 图像检索与再识别：系统会将图像的嵌入与图库进行比较，以查找另一台摄像机拍到的同一产品、人脸或人物。Ultralytics 的相似度搜索解决方案使用 OpenAI 的 CLIP 为文件夹中的图像生成嵌入，通过精确的暴力搜索计算每张已索引图像与“红色汽车”等文本查询之间的余弦相似度，并返回最近的图像，默认最多返回 30 张。