A computer-based system computes a probabilistic bound on the error
probability of a nearest neighbor classifier as follows. A subset of the
examples in the classifier is used to form a reduced classifier. The error
frequency of the reduced classifier on the remaining examples is computed
as a baseline estimate of the error probability for the original
classifier. Additionally, subsets of the examples outside the reduced
classifier are combined with the reduced classifier and applied to the
remaining examples in order to estimate the difference in error
probability for the reduced classifier and error probability for the
original classifier.
