We introduce a variant of the $k$-nearest neighbor classifier in which $k$ is
chosen adaptively for each query, rather than supplied as a parameter. The
choice of $k$ depends on properties of each neighborhood, and therefore may
significantly vary between different points. (For example, the algorithm will
use larger $k$ for predicting the labels of points in noisy regions.)
We provide theory and experiments that demonstrate that the algorithm
performs comparably to, and sometimes better than, $k$-NN with an optimal
choice of $k$. In particular, we derive bounds on the convergence rates of our
classifier that depend on a local quantity we call the `advantage' which is
significantly weaker than the Lipschitz conditions used in previous convergence
rate proofs. These generalization bounds hinge on a variant of the seminal
Uniform Convergence Theorem due to Vapnik and Chervonenkis; this variant
concerns conditional probabilities and may be of independent interest.

该论文提出了一种改进的 K 近邻分类器，它可以自适应地为每个查询选择 K，该选择取决于每个邻域的属性，因此可能在不同点之间显着变化，并且可以利用条件概率推导推导出一些收敛界限。