Information Theory, IEEE Transactions on, Vol. 13, No. 1. (1967), pp. 21-27.
Abstract
The nearest neighbor decision rule assigns to an unclassified sample point the classification of the nearest of a set of previously classified points. This rule is independent of the underlying joint distribution on the sample points and their classifications, and hence the probability of error<tex>R</tex>of such a rule must be at least as great as the Bayes probability of error<tex>R^ast</tex>--the minimum probability of error over all decision rules taking underlying probability structure into account. However, in a large sample analysis, we ...