Why do nearest-neighbour algorithms do so well?

Brian Ripley
Oxford University


Abstract Nearest-neighbour algorithms in pattern recognition are almost always amongst the best in comparative studies; they are known by many names in other fields but all work by examining the few most similar examples from the training set. There are now ways to use data to help decide the metric for `nearest' and many relationships to visualization algorithms. There are some circumstances in which they fail bbadly, but often can be improved by `editing' algorithms.