Bounds on the Classification Error of the Nearest Neighbor Rule

Abstract

The average classification error P of the nearest neighbor rule has been shown to be bounded (from above) by about twice the Bayes classification error when the sample set size is infinite and the likelihood functions of the input x with respect to its classification satisfy some reasonable smoothness constraints. Here, two new bounds are derived that apply to the practically interesting case of finite and specific sample set S. Also the case where S is infinite but specific is discussed. In general, the classification error Ps of the nearest neighbor rule given a sample set S is shown to be bounded from below by the Bayes error and from above by a bound that is equal to that derived for P plus a term that depends on S and the continuity of the likelihood functions. A sufficient assumption is Holder continuity of the likelihood functions of x with respect to its classification.