K-Nearest Neighbors Algorithm
Hello readers , this blog explains about the most widely used classification algorithm in Machine Learning called K-nearest Neighbors . We will try to understand about what is the main concept of this algorithm along with its mathematical working .
Introduction
K-Nearest Neighbors ( KNN ) algorithm is one of the simplest Supervised Machine Learning algorithm that can be used in both Classification and Regression problems but most widely preferred for Classification problems .
This algorithm is used in cases where the Linear and Logistic Regression cannot be implemented i.e when the data is non-linear separable . Non-linear data is a type of data in which the dependency of dependent variable (y) on the independent variable (x) is not linear . In other words , we cannot draw a best fit straight linear regression line for non-linear separable data .
In addition to this , KNN is a type of algorithm that uses the Lazy Learning approach in order to train the model . This means that there are no weight and bias ( w and b in y=b + wx) calculated in this algorithm . The model get trained by analyzing a pattern in the data .
Lazy Learning Approach
Lazy Learning is a type of approach in which none of the functions or equation is used to derive the relationships in the data (For example : y = b+ wx in regression algorithms ) . In this approach , the whole data is memorized in order to do predictions .
So , KNN uses Lazy Learning by memorizing whole data and learn from it by finding patterns in order to predict the future data . Now let us understand the working of KNN by explaining the meaning of “K-Nearest Neighbors” term with the help of an example —
Working of KNN
Let us consider this graph showing the data plot of the evaluation of students who passed or failed in an exam based on their time dedicated to Studies and Playing ( time pass activities ) . The “green” points show that the student passed and “red” point show that the student failed .
We can see that the students who give more time to studies have more chance of passing the exams and those who spare their time and didn’t study much get failed . But , there are some cases where a student didn’t study much and passed . Also , in some cases , the student studied well but failed . So , this is a non-linear problem because we cannot derive a smart relationship between the factors of result and output of result .
Now , let a new observation comes (blue point) which we have to predict that the student will pass or will fail . So , how the KNN will predict the output for this new observation ??
The answer is , by analyzing the output of “K” number of the previous points who are close to the new point . Let us see how —
The KNN algorithm first finds out the nearest “K” number of neighbors (here K = 5) . Then it gets the outputs of these neighbors . Whichever output has the highest frequency is allotted as the output for the new point . In the figure , out of 5 nearest neighbors , 4 have an output of Pass , hence the new point will be predicted as “Pass” or we can say that the model predicts that the new student will pass the examination .
The example above shows the working of the KNN model or KNN algorithm in the Classification problems . Let us see how the KNN works for the continuous data —
KNN working on Continuous Data
Whenever a new prediction is to be done on the continuous data , the KNN algorithm finds out the average output of the K-nearest neighbor points and assign that average as the output for the new point or the output as the prediction .
Now , the question come that how the KNN algorithm finds out the nearest neighbors to perform predictions ?? Let us see —
Mathematical Implementation of KNN
The KNN algorithm works on certain steps to do the predictions . These are —
- Find out the distance of all the points from the new point .
- Sort the neighbors in ascending order based on their distance from the new point .
- Determine the output of first “K” points who are nearest to the new point .
- Continuous Data : Find the average of the outputs and give this average as output prediction . / Categorical Data : Find the category with highest frequency and give that category as output prediction for the new point .
In order to find out the distance between the new point and each previous point , there can be two ways —
- Euclidean Distance
- Manhattan Distance
So , the KNN uses any of these 2 ways in order to get the distance between the two points .
Getting right value of K ( Elbow Method )
Now , you might be thinking that how the model decides that what will be the number of neighbors to be analyzed to correctly predict the output o a point . So , here is the answer that the value of K is provided by us ( programmer ) to the model to get trained .
In order to understand the best K value to have the best accuracy of model , we run the model over different values of K and find out the error for each model train on the previous data . Then this error is plotted on the graph ( K value Vs Error ) and the K value after which the error almost becomes constant is selected for the model . This graph is known as Elbow Graph and the method of selecting the optimal value of K from this graph is called Elbow Method .
That is all about the KNN algorithm . Hope it was an informative one for you . Thank you for reading…!!!
