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.