The Nearest Neighbor Classification Rule with a Reject Option

An observation comes from one of two possible classes. If all the statistics of the problem are known, Bayes' classification scheme yields the minimum probability of error. If, instead, the statistics are not known and one is given only a labeled training set, it is known that the nearest neighbor rule has an asymptotic error no greater than twice that of Bayes' rule. Here the (k,k') nearest neighbor rule with a reject option is examined. This rule looks at the k nearest neighbors and rejects if less than k' of these are from the same class; if k' or more are from one class, a decision is made in favor of that class. The error rate of such a rule is bounded in terms of the Bayes' error rate.