K-Nearest Neighbor Algorithm in Machine Learning

This article will take you through the fundamentals of the KNN algorithm along with a demonstration of how it works.

What is the K nearest neighbour algorithm?

The KNN algorithm is an instance-based algorithm. The basic assumption is that there are groups in the dataset. A new data point is assigned to a group depending upon the neighbours.  This is also called the Lazy algorithm.

For example, consider the dataset given below in the picture. A point labelled as a black star is assigned to the blue group because for K=7 there are four blue and 3 red. While if we consider K=5 the same is assigned to the brown group.

The nearest neighbours are calculated by using the distances between the target point and various points around it.

 

  

 

The algorithm:

1, Load the dataset into your python.

2, Choose the value of k (that is the nearest neighbour)

3, Calculate the distance between the test point and other data points

 

          1, There are four ways to compute the distance between the data points.

          a) Hamming Distance

           This distance compares the similarity between two strings and finds the difference between them. The distance is a measure of dissimilarity between them.

           b) Euclidean Distance

             

 

4, Once the distance is found between the test point and other points, the distances are sorted in ascending order.

5, Depending upon the choice of 'k' the k number of rows is chosen.

6, Based on the majority the test point is classified.

The algorithm is simple and easy to understand and interpret. It is beneficial for non-linear data because there is no underlying assumption of any kind. It has high accuracy and one can use it for both regression and classification.

However, higher memory is required for computing the distances. For N points we will have to compute N(N-1) values. It is very sensitive to outliers.

 

A simple demonstration of how the k nearest neighbor knn algorithm works

Here we are using the iris data from UCI machine learning repository.

 

After displaying the head of the data, we do the following. 

1) Split the input and output

2) Split the training and test data

3) Scale the features

Now let us import the k-NN model and fit the data to the model.

 

 

Here we have taken 10 neighbours and we predict y_pred using the X test. 

To find the optimal number of neigbours we plot error vs the neighbours.

 

 

 

Finally, we print the model accuracy, classification report, and accuracy score.

 

 

We can use the same algorithm for regression also.