1951: Evelyn Fix and Joseph Hodges introduced nearest neighbor classification in a US Air Force report. The often-quoted 1967 is Thomas Cover and Peter Hart's paper proving that 1-NN's error is at most twice the Bayes error.
Card 1 of 259. Answer: 1951: Evelyn Fix and Joseph Hodges introduced nearest neighbor classification in a US Air Force report. The often-quoted 1967 is Thomas Cover and Peter Hart's paper proving that 1-NN's error is at most twice the Bayes error.
About · Quizzes · History of AI · To suggest new questions or report an error send me a dm.
The nearest neighbor rule dates to 1951, not 1967. Evelyn Fix and Joseph Hodges, statisticians at the University of California, Berkeley, introduced it in a February 1951 technical report for the US Air Force School of Aviation Medicine, "Discriminatory Analysis. Nonparametric Discrimination: Consistency Properties". The rule classifies a new point by the labels of the training points closest to it.
Fix and Hodges proposed the k-nearest neighbor rule and proved it consistent: as the sample grows, with k growing too but more slowly, its error approaches the best achievable. The report went unpublished until International Statistical Review reprinted it in 1989. The 1967 date comes from Thomas Cover and Peter Hart's paper "Nearest neighbor pattern classification" in IEEE Transactions on Information Theory.
Their result is a classic interview question: with unlimited data, the 1-nearest neighbor error R satisfies R* ≤ R ≤ 2R*(1 − R*) for two classes, where R* is the Bayes error. If the best possible classifier errs 5% of the time, 1-NN errs at most 9.5%.
