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).

  • $\begingroup$ Fundamentally, it's best when cross validation indicates it's best amongst the other classifiers you might have opted to choose for the problem. You might regard SVMs as a special class of nearest neighbour classifiers, where the neighbours are restricted to the support vectors. $\endgroup$ – image_doctor Sep 10 '15 at 23:40
  • $\begingroup$ There is no best algorithm, even per class. You can craft a dataset which the best for a particular algorithm, e.g. nearest neighbor. $\endgroup$ – Vladislavs Dovgalecs Sep 11 '15 at 4:58

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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.