# Is kNN best for classification?

I wanted to know if kNN might produce the best result for classification? Since, it is not model based, it does not loose any detail and compares every training sample to give the prediction. Hence testing performance should be good.

I understand that testing is very slow and it is susceptible to noise. But, other than this are there any reasons why kNN should not give the best performance for classification?

There is no such thing as the best classifier, it always depends on the context, what kind of data/problem is at hand. As you mention, kNN is slow when you have a lot of observations, since it does not generalize over data in advance, it scans historical database each time a prediction is needed.

With kNN you need to think carefully about the distance measure. For instance, if one feature is measured in 1000s of kilometers, another feature in 0.001 grams, the first feature will dominate the distance measure. You can normalize the features, or give certain importance weights, based on the domain knowledge.

Also, in a very high dimensional space the distance to all neighbors becomes more or less the same, and the notion of nearest and far neighbors becomes blurred.

Do you know $k$? If $k$ is unknown all bets are off.

How do you define 'best'? In a statistical sense, best implies minimizing the risk with a squared error loss function. If this isn't the case, and even if this is the case how are you going to compare methods?

As addressed by inzl there is no best classifier. If you know that your data takes a spherical form, you might want to try a k-means based approach, and under that condition alone the k-means based approach would be more statistically efficient (not to mention k-means is more computationally efficient).

It should also be noted that for large data sets kNN falls apart even for moderate dimensions, that is why we use approximate nearest neighbors (an active area of research).

What you're referring to is called Bias.

Since kNN is not model based, it has low Bias, but that also means it can have high Variance. This is called the Bias-Variance tradeoff.

Basically, there's no guarantee that just because it has low Bias it will have a good "testing performance". Quite the contrary, it could easily overfit the data and have very low testing performance.

There's a really great book by Hastie, Tibrishiani and Friedman called The Elements of Statistical Learning that briefly discusses the topic. It's (legally) available for free online here. On page 37 they discuss the Bias-Variance tradeoff in the context of kNN, so it should be particularly useful for you.

Given infinite data, k-NN is guaranteed to approach the Bayes error rate under ideal conditions. You probably don't have infinite data, and your k is probably not large enough (it has to approach infinity).

In practice, there's no reason k-NN should be the best classifier given finite data!

I would atleast consider NaiveBayes along with knn.

You can do cross validation with both knn and Naive Bayes on your training data and select the best one.

• The OP asked if kNN is best. Just mentioning Naive Bayes doesn't answer the question. – Michael Chernick Apr 15 '17 at 3:55

kNN is one of the fastest classifiers on the planet! I have observed many times when kNN outperformed other classifiers when there was a class of objects "within" another class of objects. In spite of what a lot of users are saying, my experience is that kNN is a superior alternative -- and in fact, if I was "stuck on an island and could only choose one" classifier, it would be kNN. The best classifier is random forest, since it does not overfit.