I'd like to develop some intuitions about linear regression and KNN in a regression setting.

Let's say I have 6 different datasets below. They all have 1 independent variable X and corresponding real value Y, and let's assume that X values do not overlap in each dataset. Imagine that I separate them into a training set and test set, apply KNN(K with 3 or 5) and linear regression(without nonlinear kernels) and validate with the test sets using MSE. Red lines are regression lines that I will get from linear regression. Here what I like to think about is the performances of KNN and linear regression with different shapes and variabilities of datasets.

enter image description here

Here are my conjectures.

With the dataset 1-1, KNN will result better performance because, although there is some linearity, the dataset disperses a lot making it more non-linear. With the dataset 1-2, I think KNN and linear regression will perform somewhat the same because the linearity and variability of the dataset compensates each other.

With 2-1, KNN will outperform a linear regression because the datasets look very non-linear. KNN also will outperforms with 2-2 because the dataset is also very non-linear.

The dataset 3-1 seems to have a strong linearity with gaussian noise. Thus, linear regression will bring about the better performance, because when KNN tests the points close to the linear line, it will predict values far from the linear line. The dataset 3-2 seems to have the same linearity, but with noise uniformly distributed. In this case, I think KNN will perform better because the points are not centered around the linear line, making linear regression hard to predict.

I think my reasoning is very weak and somewhat non-systematic. Can you please let me know I should interpret these datasets in relation to KNN and linear regression?


2 Answers 2


Well, at first you need to define order of your KNN model and order of your Linear regression

2-2 has some curvature, so obviously plain linear first regression would perform bad (MSE perspective).

With K=[6-9] and good training set I would say that KNN will beat Liner regression. Because in nature it tries to approximate based on some local vicinity. So if in this area you have 6-9 points your approximation will be good enough.

MSE KNN in most of the cases is smaller than Linear Regression, on rest of the cases it's slightly worse (so it seems that KNN is almost always better). But KNN has bad performance in high dimension spaces, MSE degrades much faster than LinearRegression solution (Intuition - if in this space you don't have any example, so point will be estimated based on long distant examples).

ISLR has good explanation of both cases in Chapter 3. http://www-bcf.usc.edu/~gareth/ISL/

  • $\begingroup$ I don't see the connecting between linear regression and KNN clustering, The pictures are confusing too. $\endgroup$ Jul 25, 2017 at 3:06
  • $\begingroup$ Don't want to type chapter 3 from the book, but look picture $\endgroup$ Jul 25, 2017 at 3:43

Overall: Why did I put this paragraph before the one where I try to address your question? Because the assumptions and the basic idea behind the models dictate how you interpret the output and thus what you use the model for.

Linear regression is 'simply' a projection of a random variable $Y$ unto a subspace spanned by your independent variables. You can do this no matter how Y is actually distributed (https://en.wikipedia.org/wiki/Linear_least_squares_(mathematics)#Properties_of_the_least-squares_estimators).

Intuitively: Adding more dimensions to the problem (provided you can't describe the newly added dimension with those you've already included in the model) will always minimize the error between your model and your data. How much you minimize the error should be related to the actual descriptive power of the added variable. Adding someone's astrological sign to a regression against life-time earnings might not explain a lot of the variation is people's life-time accumulation of money, whereas the level of education might be a better variable. This to say that linear regression relies on a bit of expert knowledge or assumptions about the data, and that knowledge then leads to a model with a lot of nice properties like the existence of Confidence Intervals (disputed as they may be) and p-values etc...

K-nearest neighbor regression is a local method, where the size of the local neighborhood is inversely proportional to $K$, that uses the (potentially weighted) average of the supplied data points to describe the behavior in that local neighborhood. In KNN no assumptions are made about anything. We're free to describe anything as a collection of local behaviors. The flipside is that we're missing out on CI, p-values, possibility of extrapolating from our model[1], physical interpretation of our model and so on.

Have you seen: Why would anyone use KNN for regression?

How to interpret these datasets in relation to KNN and linear regression:

Be mindful of the assumptions underlying the two different approaches. If you have a meaningful description of independent components, ie if you have 'expert knowledge' about how the input and the outputs are related then linear regression makes sense and has a physical interpretation. You can then talk about how much a certain amount of input changes the output.

If you cannot make any justifiable, and/or simplifying, assumptions about your data then KNN is a reasonable choice. Just remember that KNN tells you something about how a small, local ensemble of data behaves, not why the data behaves the way it does.

Your outset seems to be which is more accurate in terms of MSE, but that then relates back to which assumptions can be made about the data and also why you'd only care about the MSE and not about the physical interpretation of your model. If the first thing you did was to plot your data and found, say plot 1-1, would you honestly sit down and try to choose between KNN regression and a straight line slope?

That is why you always plot your data and do residual analysis: data does not exist in a vacuum where math comes to the rescue and provides a summary statistic that says: That one is best!

The data and how the data was collected determines the best approach, not the model that provides the smallest MSE.

To relate to your own analysis: In plot 2-1 I believe that a weighted regression would be much more appropriate than a KNN. If you have reason to believe that there is a straight line behaviour through that cloud of data, then taking heteroscedacity into consideration is sensible. From an 'armchair' point of view KNN's tendency to low bias would cause the KNN regression to wiggle around the middle of the graph and stabilize out at the ends. Is that a meaningful representation of the data? Honest question, not having a stab at you.

Plot 1-1 and plot 1-2 are obvious cluster analysis data sets, given no other information than the data I'm looking at.

Plot 2-2 is an tempting linear regression with a spline/polynomial/trig function depending on what kind of system the data were measured on.

3-1 and 3-2 both fit right into the linear model framework.

2-2, 3-1, and 3-2 are the only data sets where KNN would capture the qualitative behavior in any meaningful sense.[2]

TOO LONG; DIDN'T READ Either I think you're asking the wrong kind of question by insisting on comparing two different and possibly ill-fitting models to your toy data or I completely misunderstood what you wanted to know.

[1] Before you downvote: sometimes, just sometimes we need to extrapolate a bit beyond the domain where our model was initially trained...

[2] I am now sorely tempted to patch together some data that looks like yours and actually try it out.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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