Validation of nearest neighbor classifiers

Abstract

This article presents a method to bound the out-of-sample error rate of a nearest neighbor classifier. The bound is based only on the examples that comprise the classifier. Thus all available examples can be used in the classifier; no examples need to be withheld to compute error bounds. The estimate used in the bound is an extension of the holdout estimate. The difference in error rates between the holdout classifier and the classifier consisting of all available examples is estimated using truncated inclusion and exclusion.