Weighted KNN Algorithm

Weighted k-NN is a modified version of k nearest neighbors. One of the many issues that affect the performance of the k-NN algorithm is the choice of the hyperparameter k. If k is too small, the algorithm would be more sensitive to outliers. If k is too large, then the neighborhood may include too many points from other classes.

lets consider any example of training data

the red ball indicate the class 0 and blue ball indicate class1.then now consider a white ball of query( the point whose class label has to be predicted)

If we give the above dataset to a k-NN based classifier, then the classifier would declare the query point to belong to the class 0. But in the plot, it is clear that the point is more closer to the class 1 points compared to the class 0 points. To overcome this disadvantage, weighted k-NN is used. In weighted k-NN, the nearest k points are given a weight using a function called as the kernel function. The intuition behind weighted kNN, is to give more weight to the points which are nearby and less weight to the points which are farther away. Any function can be used as a kernel function for the weighted knn classifier whose value decreases as the distance increases. The simple function which is used is the inverse distance function.

Algorithm:

Let L = { ( xi , yi ) , i = 1, . . . ,n } be a training set of observations xi with given class yi and let x be a new observation(query point), whose class label y has to be predicted.
Compute d(xi, x) for i = 1, . . . ,n , the distance between the query point and every other point in the training set.
Select D’ ⊆ D, the set of k nearest training data points to the query points
Predict the class of the query point, using distance-weighted voting. The v represents the class labels. Use the following formula

To overcome this disadvantage, weighted k-NN is used.

In weighted k-NN, the nearest k points are assigned a weight. The intuition behind weighted KNN is to give more weight to the points which are nearby and less weight to the points which are farther away…

The simple function which is used is the inverse distance function which implies that as the distance increases weight decreases and as the distance decreases, weight increases.