Weighted K Nearest Neighbors

Weights always make life a bit better.

So following up on our post on KNN, we are adding another layer to it which is more realistic i.e. Weighted Least Square.

Now in KNN, our predictions for new observation was based on K nearest observations, and we either too mean/median(for regression) or mode(for classification).

One thing to be noted here is that we placed equal weight to each K nearest observation. That is class label of Kth nearest point matters as much as say 2nd nearest point. While more realistically speaking we should have listened more to nearest family members than distant relatives.

So mending our ways a lit bit to incorporate this ideation. The weight of a observation w.r.t. a certain fixed observation is inversely proportional to the distance between those observation.
So we move from

to

where largest probability will decide the net outcome for given x0.

So that means we have different weights associated with each observation. We use Kernel functions for the same. For example

If x is within r radius, then take (1-distance of x from x’)..also called Parzen Windows

or may be fast decaying functions like

Gaussian Kernel

or

Exponential Kernel

Please Note that here instead of K, we have r and sigma deciding our Bias Variance Trade-off.

Properties

• Runs slower than KNN
• We can assign global weights rather than just K, as very far away ones will automatically get very smaller weight. Or we can just use Local weights and assign weight to just KNN
• Weighted KNN or KNN for the matter can false prey to Curse of Dimensionality as larger the number of features considered for prediction, larger the space we would have to find nearest neighbors, and stretching the Neighborhood to multiple dimensions would become more difficult. Technique that can be used for correcting this is ‘Stretching the axis’. But make sure that we do not fall into Overfitting problem in that case.

Hey!! If you are still following, Thanks a lot.

This was about Weighted KNN for Classification. To read about Locally Weighted Linear Regression check out here.

Resources:

http://lcsl.mit.edu/courses/mlcc/mlcc2014/classes/Lecture2_MemoryBasedLearning.pdf