# For what type of problems nearest neighbor performs better

I'm trying to predict house prices. I use features like the area of the house, age of the house, etc.

I turns out that knn (k-nearest neighbor) algorithm beats all the other powerful algorithms like Neural networks, SVMs, linear regression.

What might be the reason of this? And in general for what characteristics of data knn works better than other algorithms?

One answer I think of is that if the underlying relation is too complex then it might be difficult to find a model, this explains the poor performance of the model based algorithms.

Any other ideas or better explanations?

Thanks

• It turns out? link? :) – rogerdpack Feb 16 '18 at 17:10

It probably has to do with the characteristics of your problem! What sorts of features are you using for your classification (i.e., are they binary, continuous-valued, etc.), and what's the dimensionality of your problem? I don't have a reference for this off the top of my head, but it's a well-accepted observation that SVMs tend to perform well in high-dimensioned classification problems, which is why they are so ubiquitous in text classification, where problems frequently have over hundreds of thousands of dimensions.

As an algorithm, $k$NN has always interested me, because it's a very general approach to classification that can be adapted to the characteristics of a particular problem. For example, the value of $k$ can (and should) be optimized using a hold-out training data set, and can differ drastically from problem to problem. What's more, there are any number of distance metrics that can be used to determine how data points relate to one another. In my own work, I've used mutual information as a distance metric for protein-protein interaction text classification, which out-performed other distance metrics and an SVM-based approach. This specific flavor of $k$NN, however, hasn't been as successful on other problems, though!

• I'm using only 4 features. All of them are continuous. Actually even if I use a single feature (size of the house) knn still outperforms others significantly. – Ahmet Yılmaz Nov 27 '12 at 15:57

The advantage (and disadvantage) of k-NN is that it keeps all training data. If your classes are strongly overlapping and "smeared" out, parametric models (SVM, Bayes etc) can have trouble remembering local groupings, as by their nature they summarize information in some way. With SVMs, sometimes the right choices of kernel and margin can circumvent this problem.

The price you pay when using k-NN in general is two things:

• If you have a lot of data, prediction becomes costly. Basically, all training data might be involved in decision making (which gives the advantage above). If you have only a very moderate number of dimensions (<< 100), a spatial index (R-Tree and derivatives) will probably do the trick for you. Most of the time you will need to hit the disc (can be a problem in high load settings).

• However, if the dimensionality is much higher, any index usually becomes useless (because the union of per-dimension matches becomes too large, resulting in long scans). For categorical attributes, inverted lists can still help you here. Also, as Kyle pointed out, the distance measure becomes crucial, and sometimes no useful distance measure will be available (cf. the curse of dimensionality). Most parametric classifiers do not have this problem.

Because your dimensionality is very low, k-NN might just be the right choice for you.