你说的算法是：k-最近邻算法，k=使用的训练点数。我将其定义为jms-k-nearest-neighbor。

由于 VC 维度是训练误差为 0的算法所能粉碎的最大训练点数，因此jms-k-nearest-neighbor的 VC 维度只能为 k 或 0。

1 个训练实例 => k=1：在训练期间 jms-1-nearest-neighbor 正好存储这个实例。在完全相同的训练集上应用时，一个实例最接近存储的训练实例（因为它们是相同的），因此训练误差为0。

所以我同意，VC 维度至少为 1。

2 个训练实例 => k=2：只有标签不同时才会出现问题。在这种情况下，问题是如何做出类标签的决定。多数票不会导致结果（VC = 0？），如果我们使用按距离反向加权的多数票，则 VC 维度为 2（假设不允许相同的训练实例使用不同的标签两次，因为如果所有算法的 VC 维度都是 0（我猜））。

没有标准的 k 近邻算法，它更像是一个基本思想相同但在实现细节上风格不同的家族。

使用的资源：Andrew Moore 的 VC 维度幻灯片