T. Cover & P. Hart (1967)
IEEE Transactions on Information Theory, 13(1), 21-27.
DOI: https://doi.org/10.1109/tit.1967.1053964
Abstract. Proves that, as the sample size tends to infinity, the error rate of the 1-nearest-neighbour rule is bounded by twice the Bayes-optimal error rate, a celebrated theoretical guarantee of asymptotic competitiveness for so simple an algorithm.
Tags: classification nearest-neighbours theory