KNN algorithm in Machine Learning

Machine Learning is one of the most used modern technologies in our world. Machine Learning helps human a lot to do their jobs at ease. Today almost every big tech companies use Machine Learning technologies to give their customers best service. KNN algorithm is one of the simplest algorithms in Machine Learning. The full form of KNN is K Nearest Neighbour. By this algorithm we can classify one item by its similar item which is stored in data set. In this article we are going to discuss about KNN algorithm in details. Let’s start to understand about this algorithm.

What is KNN algorithm?

It is one of the simplest algorithms in Machine Learning. This algorithm is a supervised algorithm. The main function of this algorithm is to identify new items or cases by checking older items or cases in data set. Mainly it checks whether the new case has some similarity with older cases which is available in data set, or not. This algorithm can be used in both regression and classification techniques of Machine Learning. But it is mainly used in classification cases. This algorithm is a non parametric algorithm because it does not build any assumptions by underlying data. We know for every model there is training stage where the model learns about the method of prediction but for KNN algorithm the training phase is quite different. In training phase it only takes the data set and when new cases arrive then it stores them by checking older data set. This algorithm is called as lazy learner algorithm because it does not learn fast from training data set. It only does action when there are new cases. For this reason it is named so.

Example: 

Let’s understand the concept of this algorithm by a simple example. Suppose we have build one Machine Learning model using this algorithm such as it can identify the pictures of animals. Now we have two pictures of lion and tiger. We want to know the animal. So we pass the new cases in the model of KNN algorithm. It will search the similarity of these images in its older data sets. After processing it will classify the images as tiger and lion. This is the basic concept of KNN algorithm. It finds similarity to find out the nearest neighbour of the case.

Why we need KNN algorithm?

This algorithm is mainly used for classification purposes. Let’s think we have two groups of data points. Now there is a new data point. So we have to choose in which group we will add new point. It is not possible to analyse minute details deeply for a human. For this reason we need this algorithm. It analyse the similarities between the new point and two existing group and then classifies it as one of the groups.

What should be the value of K in this algorithm?

We have learnt the meaning of two n in this algorithm. But what is K? K is a particular value which, we have to take for different cases. K mainly represents the number of nearest neighbours. The value of K is an important point because we will only analyse k neighbours of the new data point. So, it is obvious that if the value of k increases then it will be good to detect the particular group. But the higher value of k can make the analysis difficult. For this reason we can make the value of k as 5. But it can change depending upon the situation. If we take lower value for k then it may give some error because if k is equal to 2 or 3 then it is very low cases we are analysing. For this reason, it is better to take k as near about 5.

The basic working principle of KNN algorithm

Following is the steps of this algorithm:

1. Step-1: First, we have to choose K number of the neighbor from new data point.
2. Step-2: After that, we will calculate the distance of new point and neighbors.
3. Step-3: We have to take K nearest neighbours depending the distance.
4. Step-4: After that, we will detect the category of the neighbours.
5. Step-5: We have to put the new point in the category which has maximum neighbours.
6. Step-6: Our model is ready to work.

Python implementation of KNN algorithm

Let’s understand the implementation of the above concept of the algorithm. We will implement the algorithm in Python. First look at the problem statement.

Problem statement:

Suppose one car company has built a revised model of one of their old models. Now the company wants to give ad to the customers for this new model. But it is sure that those who has old model will not buy this car so, the identification of users is necessary here. For this reason we will use KNN algorithm in this problem. We have to use a data set extracted from the social media. There will be many variables. For this problem we have to consider salary and age as independent variable and purchased car or not variable as dependent variable.

The main steps for implementing the KNN algorithm in this data set are as follows:

1. Step-1: First we have do pre processing or feature selection from the data set.
2. Step-2: After that we will adjust the KNN algorithm to the training set
3. Step-3: The model will predict the result of the test.
4. Step-4: After that we will check how much accuracy present in the result.
5. Step-5: We have to visualize the result of test set.
6. Step-6: Our model is ready to work.

Data pre-processing step

In this step, we will process the data and find out the main features. It is an important step. Below is the code to do so.

import numpy as nm  
import matplotlib.pyplot as mtp  
import pandas as pd  
 
data_set= pd.read_csv('user_data.csv')  
  
x= data_set.iloc[:, [2,3]].values  
y= data_set.iloc[:, 4].values  
  
from sklearn.model_selection import train_test_split  
x_train, x_test, y_train, y_test= train_test_split(x, y, test_size= 0.25, random_state=0)  
  
from sklearn.preprocessing import StandardScaler    
st_x= StandardScaler()    
x_train= st_x.fit_transform(x_train)    
x_test= st_x.transform(x_test)  

Fitting KNN classifier to the training data set

Below is the code to fit the KNN classifier to the training data set.

from sklearn.neighbors import KNeighborsClassifier  
classifier= KNeighborsClassifier(n_neighbors=5, metric='minkowski', p=2 )  
classifier.fit(x_train, y_train) 

Predicting the Test Result

Below is the python code for the predicting the result.

y_pred= classifier.predict(x_test)  

Creating the Confusion Matrix

Now we have to create the confusion matrix to check the accuracy of the algorithm in this problem. Below is the python code for the same.

    from sklearn.metrics import confusion_matrix  
    cm= confusion_matrix(y_test, y_pred)  

Visualizing the Training set result

Now we will check the model by training data set. Below is the python code for the same.

from matplotlib.colors import ListedColormap  
x_set, y_set = x_train, y_train  
x1, x2 = nm.meshgrid(nm.arange(start = x_set[:, 0].min() - 1, stop = x_set[:, 0].max() + 1, step  =0.01),  
nm.arange(start = x_set[:, 1].min() - 1, stop = x_set[:, 1].max() + 1, step = 0.01))  
mtp.contourf(x1, x2, classifier.predict(nm.array([x1.ravel(), x2.ravel()]).T).reshape(x1.shape),  
alpha = 0.75, cmap = ListedColormap(('red','green' )))  
mtp.xlim(x1.min(), x1.max())  
mtp.ylim(x2.min(), x2.max())  
for i, j in enumerate(nm.unique(y_set)):  
    mtp.scatter(x_set[y_set == j, 0], x_set[y_set == j, 1],  
        c = ListedColormap(('red', 'green'))(i), label = j)  
mtp.title('K-NN Algorithm (Training set)')  
mtp.xlabel('Age')  
mtp.ylabel('Estimated Salary')  
mtp.legend()  
mtp.show()  

Visualizing the Test set result

After the completion of the training of the model by training set we will pass new data set or test set to see the result. The code will be almost same as previous one.

from matplotlib.colors import ListedColormap  
x_set, y_set = x_test, y_test  
x1, x2 = nm.meshgrid(nm.arange(start = x_set[:, 0].min() -1,  stop = x_set[:, 0].max() + 1, step  =0.01),  
nm.arange(start = x_set[:, 1].min() - 1, stop = x_set[:, 1].max() + 1, step = 0.01))  
mtp.contourf(x1, x2, classifier.predict(nm.array([x1.ravel(), x2.ravel()]).T).reshape(x1.shape),  
alpha = 0.75, cmap = ListedColormap(('red','green' )))  
mtp.xlim(x1.min(), x1.max())  
mtp.ylim(x2.min(), x2.max())  
for i, j in enumerate(nm.unique(y_set)):  
    mtp.scatter(x_set[y_set == j, 0], x_set[y_set == j, 1],  
        c = ListedColormap(('red', 'green'))(i), label = j)  
mtp.title('K-NN algorithm(Test set)')  
mtp.xlabel('Age')  
mtp.ylabel('Estimated Salary')  
mtp.legend()  
mtp.show()  

Advantages

1. As we have previously discussed that the algorithm is very simple to implement.
2. The algorithm can be very effective if the data set is large.

Disadvantages

1. We have to determine many destinations so, the calculations may be complex.
2. We have to take the value of k. It may not be easy for all problems.