When, if ever, is nearest neighbor classification the best choice?

Question

I've been researching the history and use of k-nearest neighbor classification and regression, and various tweaks including k-d trees and LAESA.

I understand that it is useful because it is simple and flexible, but can be computationally expensive and requires a lot of data storage.

But here's what I don't know:

Is there any class of problems for which nearest neighbor classification is the best or one of the best algorithms to use?

By 'class of problems' I mean either a class based on data structure (for instance, maybe KNN is great for low-dimensional data with a mix of nominal and numerical data), or a class of real-life problems (maybe KNN is useful in predicting diseases for insurance holders).

Answer 1

One situation where NN would be ideal is if the data are sample points of a piecewise constant function. In this case, the true function is composed of a tesselation of its domain, with a constant value for all points within each division.

Answer 2

If I remember it correctly, classical theory says it is ideal, when the data are gaussians with an identity-covariance matrix. Then it behaves as the Bayesian( Gaussian ) Classifier which is optimal with respect to the 0 - 1 Loss-function.

Which still doesn't say anything about the behaviour with a real dataset without infinite data like suggested before.

The practical answer could be, to try it as a first guess. When it doesn't work apply PCA to your data ( to decorrelate your features ) and try it again. If it still doesn't work, try other stuff.