Layman’s Introduction to KNN
Layman’s Introduction to KNN

k-nearest neighbour algorithm is where most people begin when starting with machine learning.

Photo by timJ on Unsplash

kNN stands for k-Nearest Neighbours. It is a supervised learning algorithm. This means that we train it under supervision. We train it using the labelled data already available to us. Given a labelled dataset consisting of observations (x,y), we would like to capture the relationship between x — the data and y — the label. More formally, we want to learn a function g : X→Y so that given an unseen observation X, g(x) can confidently predict the corresponding output Y.

Other examples of supervised learning algorithms include random forests, linear regression and logistic regression.

kNN is very simple to implement and is most widely used as a first step in any machine learning setup. It is often used as a benchmark for more complex classifiers such as Artificial Neural Networks (ANN) and Support Vector Machines (SVM). Despite its simplicity, k-NN can outperform more powerful classifiers and is used in a variety of applications such as economic forecasting, data compression and genetics.

Genetics

Agriculture

Aviation — Air traffic flow prediction

As with most technological progress in the early 1900s, KNN algorithm was also born out of research done for the armed forces. Two offices of USAF School of Aviation Medicine — Fix and Hodges (1951) wrote a technical report introducing a non-parametric method for pattern classification that has since become popular as the k-nearest neighbor (kNN) algorithm.

Source: DTIC — The Declassified Paper in full.

How does it work?

Let’s say we have a dataset with two kinds of points — Label 1 and Label 2. Now given a new point in this dataset we want to figure out its label. The way it is done in kNN is by taking a majority vote of its k nearest neighbours. k can take any value between 1 and infinity but in most practical cases k is less than 30.

Blue Circles v/s Orange Triangles

Let’s say we have two groups of points — blue-circles and orange-triangles. We want to classify the Test Point = black circle with a question mark, as either a blue circle or an orange triangle.

Goal: To label the black circle.

For K = 1 we will look at the first nearest neighbour. Since we take majority vote and there is only 1 voter we assign its label to our black test point. We can see that the test point will be classified as a blue circle for k=1.
['Rishi Sidhu']
['Algorithms', 'Technology', 'Artificial Intelligence', 'Data Science', 'Machine Learning']