In the panoply of pattern classification techniques, few enjoy the intuitive
appeal and simplicity of the nearest neighbor rule: given a set of samples in
some metric domain space whose value under some function is known, we estimate
the function anywhere in the domain by giving the value of the nearest sample
per the metric. More generally, one may use the modal value of the m nearest
samples, where m is a fixed positive integer (although m=1 is known to be
admissible in the sense that no larger value is asymptotically superior in
terms of prediction error). The nearest neighbor rule is nonparametric and
extremely general, requiring in principle only that the domain be a metric
space. The classic paper on the technique, proving convergence under
independent, identically-distributed (iid) sampling, is due to Cover and Hart
(1967). Because taking samples is costly, there has been much research in
recent years on selective sampling, in which each sample is selected from a
pool of candidates ranked by a heuristic; the heuristic tries to guess which
candidate would be the most "informative" sample. Lindenbaum et al. (2004)
apply selective sampling to the nearest neighbor rule, but their approach
sacrifices the austere generality of Cover and Hart; furthermore, their
heuristic algorithm is complex and computationally expensive. Here we report
recent results that enable selective sampling in the original Cover-Hart
setting. Our results pose three selection heuristics and prove that their
nearest neighbor rule predictions converge to the true pattern. Two of the
algorithms are computationally cheap, with complexity growing linearly in the
number of samples. We believe that these results constitute an important
advance in the art.

本文提出并证明了三种新的启发式算法可以用于遥感应用中的样本选择，以最小化模板来估计其位置估计与真实模板之间的误差。

最近邻模式分类与选择性采样的收敛性

Convergence of Nearest Neighbor Pattern Classification with Selective  Sampling

The $k$th-nearest neighbor rule is arguably the simplest and most intuitively
appealing nonparametric classification procedure. However, application of this
method is inhibited by lack of knowledge about its properties, in particular,
about the manner in which it is influenced by the value of $k$; and by the
absence of techniques for empirical choice of $k$. In the present paper we
detail the way in which the value of $k$ determines the misclassification
error. We consider two models, Poisson and Binomial, for the training samples.
Under the first model, data are recorded in a Poisson stream and are "assigned"
to one or other of the two populations in accordance with the prior
probabilities. In particular, the total number of data in both training samples
is a Poisson-distributed random variable. Under the Binomial model, however,
the total number of data in the training samples is fixed, although again each
data value is assigned in a random way. Although the values of risk and regret
associated with the Poisson and Binomial models are different, they are
asymptotically equivalent to first order, and also to the risks associated with
kernel-based classifiers that are tailored to the case of two derivatives.
These properties motivate new methods for choosing the value of $k$.

本文详细介绍了在训练样本为 Poisson 分布和二项式分布下 $k$ 值对于误判率影响的方式，并就此提出了选择 $k$ 值的新方法。