# On what kind of data (simple example) will KNN outperform linear regression

Linear regression outperforms KNN in simple dataset like a line or a polynomial (say quadratic) I am looking for a simple example where KNN would outperform linear regression. I tried sin and cosine function but they linear regression performs better as compared to KNN.

For comparison I am using the metrics RMSE and cross correlation.

• It shouldn't be the case that linear regression outperforms KNN regression on sin/cos unless you're sampling your input space fairly sparsely, or you're only considering a small range of inputs. If you cover at least one period, then linear regression shouldn't be able to do better than predicting the mean, whereas KNN will (with sufficient data) perform perfectly. – Dougal Apr 4 '16 at 10:12
• KNN does very very well for the insample ( training data) but not for out of sample (test data) – Bunny Rabbit Apr 4 '16 at 11:31
• It sounds like you're doing something strange with parameters of how many points you're giving / etc. you should plot it and take a look at what's going on. – Dougal Apr 4 '16 at 17:31

One situation where $k$-NN can easily outperform regression is when you are trying to approximate a function with some structure, but you don't know what that structure is. For example, suppose your data looks like this function $f(x)$:
Now consider trying to fit this with an explicit regression model. If you knew that that $f(x)$ had six transitions and they were all steps, you could write down a model and fit it. However, suppose we didn't know that a priori, and the data might really have 7--or 70 steps! It's still potentially possible to fit this (e.g, by doing some model selection), but it may not be easy and may require a lot of data to distinguish between similar possibilities.
A second advantage of $k$-NN is that its performance scales with the number of data points. Suppose we have a second function $f'(x)$ (not shown), which is like $f(x)$, but has some fine structure: perhaps the values also oscillate slightly, so that $f'(x)=1.001 \textrm{ or } f'(x)=0.001$ for odd $x$ values. You could explicitly incorporate this into your regression model--if you noticed it--but you would need to observe it and realize that it requires yet another degree of freedom in your model. In contrast, you'll get this "for free" with a $k-$NN model.
The major disadvantage of $k$-NN is that there is not much of a model to interpret. A regression model would tell you that there are transition points here and there (with this much uncertainty about their positions), which might be of interest. The $k$-NN model just tells you that the $k$-nearest points are (or are not) similar.