• Abhishek Singh

Implementation of K- Nearest Neighbors from scratch in python


The K-Nearest Neighbors is a straightforward algorithm, we can implement this algorithm very easily.


It is used to solve both classifications as well as regression problems. KNN algorithm is used in a variety of applications such as medical, banking, agriculture, and genomics.


There is one cool application which is customer churning, in this we predict whether the customer is going to cancel our subscription plan or stick with it.


In the medical sector, we can use KNN to classify between healthy patients and diabetic patients.


In agriculture, we use it to classify damaged crops and healthy crops. KNN works based on similarity features.




In this blog, we are going to cover the following topics:




What are K-Nearest Neighbors

KNN is a non-parametric and instance-based learning algorithm. 


Non-parametric means there is no assumption that we have to follow to implement KNN. It means, the model structure decided from the dataset. This will be useful practically very useful where the vast majority of the datasets don't follow scientific hypothetical presumptions.


KNN is a type of instance-based learning, or lazy learning, which means classifier immediately adapts as we collect new training data. It allows the algorithm to quickly respond when the changes in the input are made in real-time.


Along with these benefits, there are some disadvantages also like KNN doesn't perform well on imbalanced data. Imbalance data means we have an uneven distribution of classes.


For example: let us consider a dataset called anomaly detection on some server. Primarily we have 2 classes like anomaly and not anomaly. In this case, we have a dissimilar distribution like a 50:1 ratio between anomaly and non-anomaly classes.

How does the KNN algorithm work?

Let us take an example and understand the algorithm.


In the below figure you can see that we have two classes. The first class is denoted by blue squares and the second class is denoted by the red triangle. Now we have to find the green circle belongs to which class?


To solve this problem we use KNN, where k represents the total number of neighbors.

Now we use KNN to find the k nearest neighbors for the green circles and take the majority vote of each data point and then we assign it to the green circles.



KNN


Now let us understand this thing with the help of an example, let us take the k value is 3 and we can see that we have 2 red triangles and 1 blue square as the closest neighbors to the green circle and we take the majority and assign green circle as a red triangle.


When we take k value as 5 you can see that it belongs to the blue square.


So the question arises is how to find the nearest neighbors?


To find the nearest neighbors we use distance function i.e it gives us the distance between the elements of a set.


Some of the common distance functions are Euclidean, Minkowski, Manhattan, etc.


The formula for all 3's are




Formula to calculate distance


Now we have understood how the KNN algorithm works. Let us write all the steps in pseudo-code format.

  • The first step is to choose the value of K.

  • calculate the distance between the unknown point and all the available points.

  • Sort the calculated distance in ascending order based on distance values.

  • get the top k rows from the sorted array.

  • count the most frequent class of these rows

  • and then return the predicted class for unknown point.



How do we choose the value of K

There is no predefined value of K for datasets. It depends upon the requirements of the problem. Generally, larger k values decrease the effect of noise on classification and boundaries between classes less visible.


Or we can also use cross-validation to find the optimal value of k, we try with different k values and check how the validation error rate is varying, we choose the elbow point as best k value.



How to choose value of K

Difference between eager learners and lazy learners

Some of the major differences between eager learners and lazy learners are


1- Learning is fast in lazy and it can be slow in eager.


2- Prediction requires work so it can be slow in lazy, whereas predictions are fast in eager.


3- Lazy learners wait for querying before generalizing whereas eager learners generalize before seeing query.



Curse of Dimensionality

Curse of Dimensionality states that " if the number of features" increases then it is very hard to predict new data. So in this way, the problems become computationally expensive and hard to solve.


To solve this problem we use dimensionality reduction techniques like principal component analysis, t-SNE, Sammon mapping, and laplacian Eigenmaps.





Coding KNN on a real-life example



Pros and Cons of KNN

Pros of KNN

  • KNN can be used to solve both classifications as well as regression types of problems.

  • KNN algorithm can easily respond to changes in input in real-time.

  • It is also used to solve the multi-class classification problem.

  • There are no special criteria that we have to meet before applying KNN.

Cons of KNN

  • KNN works well in small no of input variables but as the no of variables grows it is very hard to predict the output of new data. This is also called a curse of dimensionality.

  • KNN algorithm needs normalized data.

  • It cannot deal with missing value problems.

  • The major issue with the KNN is to choose the optimal no of neighbors.

Wrap up the Session

In this tutorial we have learned about, what is knn algorithm and how does it works after that we learn about how to choose the optimal value of K. After that we learn about the difference between the lazy learners and eager learners. And then we implement the KNN algorithm on real-life examples using python and at last, we learn about the advantages and disadvantages of using KNN.

If you want to learn about machine learning, deep learning, natural language processing, computer vision. You can subscribe to my blog for getting notified when I release a new blog. If you liked this tutorial please like it, share it, and if you have any problem regarding the implementation or any topic feel free to leave a comment. 



722 views