32
$\begingroup$

From what I understand, we can only build a regression function that lies within the interval of the training data.

For example (only one of the panels is necessary): enter image description here

How would I predict into the future using a KNN regressor? Again, it appears to only approximate a function that lies within the interval of the training data.

My question: What are the advantages of using a KNN regressor? I understand that it is a very powerful tool for classification, but it seems that it would perform poorly in a regression scenario.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Can you clarify what you mean by "predict into the future"? Do you have time-series & you want to do forecasting, or are you trying to fit a relationship between 2 variables & want to use that in the future to guess a Y value from a known X value? $\endgroup$
    – gung - Reinstate Monica
    Commented Jun 21, 2014 at 20:51
  • 1
    $\begingroup$ For example, if I wanted to predict the value Y such that X=15 from the image above. A KNN-regressor wouldn't cut it right? $\endgroup$
    – user46925
    Commented Jun 22, 2014 at 1:38
  • 1
    $\begingroup$ I would agree with you that if you trained on a set with $x \in [0,5]$ but expected that you may see values of $x$ far beyond what is in your data then non-parametric local methods might not be ideal. Instead you might want to use that domain knowledge and define a parametric model that includes your knowledge of how 'unobserved' $x$ is expected to behave. $\endgroup$
    – Meadowlark Bradsher
    Commented Jun 22, 2014 at 2:45
  • 1
    $\begingroup$ An example of KNN being used successfully for regression is Nate Silver's PECOTA baseball prediction thing. You can read about the pros and cons from the Wikipedia article on PECOTA or newspaper articles like this one: macleans.ca/authors/colby-cosh/… $\endgroup$
    – Flounderer
    Commented Jun 22, 2014 at 2:48
  • 6
    $\begingroup$ Also to make a more general point, as you become knowledgeable in statistics (or data mining/machine learning etc) you'll find that answers to very general questions such as yours will often be a paraphrased version of 'it depends'. Knowing what 'it depends' on and why is the knowledge. $\endgroup$
    – Meadowlark Bradsher
    Commented Jun 22, 2014 at 2:51

5 Answers 5

Reset to default
22
$\begingroup$

Local methods like K-NN make sense in some situations.

One example that I did in school work had to do with predicting the compressive strength of various mixtures of cement ingredients. All of these ingredients were relatively non-volatile with respect to the response or each other and KNN made reliable predictions on it. In other words none of the independent variables had disproportionately large variance to confer to the model either individually or possibly by mutual interaction.

Take this with a grain of salt because I don't know of a data investigation technique that conclusively shows this but intuitively it seems reasonable that if your features have some proportionate degree of variances, I don't know what proportion, you might have a KNN candidate. I'd certainly like to know if there were some studies and resulting techniques developed to this effect.

If you think about it from a generalized domain perspective there is a broad class of applications where similar 'recipes' yield similar outcomes. This certainly seemed to describe the situation of predicting outcomes of mixing cement. I would say if you had data that behaved according to this description and in addition your distance measure was also natural to the domain at hand and lastly that you had sufficient data, I would imagine that you should get useful results from KNN or another local method.

You are also getting the benefit of extremely low bias when you use local methods. Sometimes generalized additive models (GAM) balance bias and variance by fitting each individual variable using KNN such that:

$$\hat{y}=f_1(x_1) + f_2(x_2) + \dots + f_n(x_n) + \epsilon$$

The additive portion (the plus symbols) protect against high variance while the use of KNN in place of $f_n(x_n)$ protects against high bias.

I wouldn't write off KNN so quickly. It has its place.

Improve this answer
$\endgroup$
1
8
$\begingroup$

I don't like to say it but actually the short answer is, that "predicting into the future" is not really possible not with a knn nor with any other currently existing classifier or regressor.

Sure you can extrapolate the line of a linear regression or the hyper plane of an SVM but in the end you don't know what the future will be, for all we know, the line might just be a small part of a curvy reality. This becomes apparent when you look at Bayesian methods like Gaussian processes for instance, you will notice a big uncertainty in the predictive distribution, as soon as you leave the "known input domain".

Of course you can try to generalize from what happened today to what likely happens tomorrow, which can easily be done with a knn regressor (e.g. last year's customer numbers during Christmas time can give you a good hint about this year's numbers). Sure other methods may incorporate trends and so on but in the end you can see how well that works when it comes to the stock market or long-term weather predictions.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ +1 for caution against extrapolation and for discussing the (relatively conservative) behavior of KNN when extrapolating. $\endgroup$
    – eric_kernfeld
    Commented Mar 25, 2019 at 20:40
  • 1
    $\begingroup$ KNN is more conservative than linear regression when extrapolating exactly because of the behavior noted by OP: it can only produce predictions within the range of Y values already observed. This could be an advantage in a lot of situations. $\endgroup$
    – eric_kernfeld
    Commented Mar 25, 2019 at 20:42
2
$\begingroup$

First an example for "How would I predict into the future using a KNN regressor ?".

Problem: predict hours of sunlight tomorrow $sun_{t+1}$ from $sun_t .. sun_{t-6}$ over the last week.
Training data: $sun_t$ (in one city) over the last 10 years, 3650 numbers.

Denote $week_t \equiv sun_t .. sun_{t-6}$ and $tomorrow( week_t )) \equiv sun_{t+1} $ .

Method: put the 3650-odd $week_t$ curves in a k-d tree with k=7.
Given a new $week$, look up its say 10 nearest-neighbor weeks
with their $tomorrow_0 .. tomorrow_9$ and calculate
$\qquad predict( week ) \equiv $ weighted average of $tomorrow_0 .. tomorrow_9$

Tune the weights, see e.g. inverse-distance-weighted-idw-interpolation-with-python,
and the distance metric for "Nearest neighbor" in 7d.

"What are the advantages of using a KNN regressor ?"
To others' good comments I'd add easy to code and understand, and scales up to big data.
Disadvantages: sensitive to data and tuning, not much understanding.

(Longish footnote on terminology:
"regression" is used as a fancy word for "fitting a model to data".
Most common is fitting data $X$ to a target $Y$ with a linear model:
$\qquad Y_t = b_0 X_t + b_1 X_{t-1} + ... $
Also common is predicting tomorrow's say stock price $Y_{t+1}$ from prices over the last week or year:
$\qquad Y_{t+1} = a_0 Y_t + a_1 Y_{t-1} + ... $
Forecasters call this an ARMA, Autoregressive moving-average_model or Autoregressive model . See also Regression analysis .

So your first line "we can only build a regression function that lies within the interval of the training data" seems to be about the confusing word "regression".)

Improve this answer
$\endgroup$
2
$\begingroup$

From An Introduction to Statistical Learning, section 3.5:

In a real-life situation in which the true relationship is unknown, one might draw the conclusion that KNN should be favored over linear regression because it will at worst be slightly inferior than linear regression if the true relationship is linear, and may give substantially better results if the true relationship is non-linear.

But there are constraints (not from the textbook, just what I concluded):

  1. a sufficient number of observations per predictor.
  2. the number of predictors should not be too big.
Improve this answer
$\endgroup$
2
$\begingroup$

Hangyu Tian makes a great point that k-NN regression will not do well when there isn't enough data and method like linear regression that make stronger assumptions may outperform k-NN. However, the amazing thing about k-NN is that you can encode all sorts of interesting assumptions by using different weights. For example, if you normalize the data and then use $k(x, x')=x \cdot x'$ as the weight between $x$ and $x'$ for all $x, x'$ in your data, that will actually approximate good old fashioned linear regression! Of course, it would be unnecessarily slow compared to other methods for linear regression but the point is that you actually have a lot of flexibility. For reference this is called the linear kernel.

I played around with the notebook that generated the photos you attached. I don't see much reason to do k-NN regression with uniform or distance weights as that example shows. So I changed it to use RBF weights. This means that it will be like scipy.interpolate.Rbf except that we are only looking at the nearest neighbors. Obviously looking at k nearest neighbors doesn't improve accuracy but it can be essential for performance when you have a large dataset. I also upped the number of neighbors to 10. Also, I think you should be comparing to the true function rather than the noisy data. Our goal here is to approximate the true function and ignore all that noise. Also, to have a baseline I compared to CubicSpline. I also am using 80 examples rather than just 40. I played around with different axis bound on the time axis because that affects the density which is an important factor for the performance of any k-NN method. The k-NN interpolation works pretty well even as I change the bounds on the axis. It usually gets close to the original function than the original data was. So I that this particular example just needed a bit of work done on it. Anyways, the reason in general for using k-NN anything is that it's faster than looking at the entire dataset. So k-NN based regression will be more scalable than a Gaussian process. It is also just very simple, intuitive and predictable. You can see in the attached picture that cubic spline is showing some strange behavior in certain areas. Neural networks are also relatively unpredictable. Another huge difference between k-NN interpolation and methods like cubic spline is that k-NN interpolation doesn't try to fit the data perfectly because we know the data is noisy. enter image description here enter image description here

We can also see that k-NN gets better with more data. Meanwhile cubic spline gets starts acting crazy and gaussian processes start getting too slow.

Here we use twice the amount of data. enter image description here

I think the moral of the story is that k-NN can do very different things depending on how you define your distances and weights. Actually, you could even use k-NN with polynomial kernel to interpolate polynomials as we did with cubic spline. Or since the underlying function here is sin it would make the most sense to use the periodic kernel. For more info see the kernel cookbook https://www.cs.toronto.edu/~duvenaud/cookbook/

Improve this answer
$\endgroup$

Your Answer

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