KNN.md

K nearest Neighbours

Introduction

KNN is a baseline algorithm in ML. It follows brute force approach and any other algorithm that is devised should have accuracy greater than that of KNN to be accepted as correct.

The output in KNN is predicted as the majority of the K nearest points to our query point.

Here the query point is shown as a star and there are 2 different classes, A(Blue) and B(Orange).
The chosen value of k=3, which means we consider the 3 closest neighbours to our query point
Here, the distribution of the neighbours is A->1 and B->2
Since B neighbours are present in majority, the query point will be predicted to be of class B

Algorithm

1. Finding the K Nearest Neighbours

We compute the distance of each point from our query point.
The distance used is the Euclidean distance

2. After computing the distances, they are arranged in ascending order and the first K points are chosen

3. Then we compute the majority vote out of these K neighbours.

Key Points

• Simplest Algorithm in Machine Learning
• Used for classification and regression both
• Comes under supervised learning
• Non parametric
• Value of k is kept odd- because if it is even there are greater chances of both classes being present in equal numbers when taking majority vote
• No training is required as all work is done in query time