The Nearest Neighbor Classification Rule with a Reject Option
- 1 July 1970
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Systems Science and Cybernetics
- Vol. 6 (3) , 179-185
- https://doi.org/10.1109/tssc.1970.300339
Abstract
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.Keywords
This publication has 6 references indexed in Scilit:
- A generalized k-nearest neighbor ruleInformation and Control, 1970
- On optimum recognition error and reject tradeoffIEEE Transactions on Information Theory, 1970
- Some convergence properties of a nearest neighbor decision ruleIEEE Transactions on Information Theory, 1970
- Nearest neighbor pattern classificationIEEE Transactions on Information Theory, 1967
- A Nonparametric Estimate of a Multivariate Density FunctionThe Annals of Mathematical Statistics, 1965
- An optimum character recognition system using decision functionsIRE Transactions on Electronic Computers, 1957