K-Nearest Neighbors (KNN) Algorithm for Supervised Machine Learning

What is a Classification in Machine Learning?

Classification is the process of categorizing a given data set into predefined categories based on their features. For example, you could build a classification model to predict whether a brain tumor is malignant (cancerous) or benign (non cancerous) based on MRI data.

The KNN algorithm can be used for such classification tasks. Let's see how the KNN algorithm works.

How KNN Works

To understand the KNN algorithm we will be working with a BMI dataset provided by Kaggle. Each person is categorized into a BMI category of Extremely Weak, Weak, Normal, Overweight, Obesity and Extreme Obesity based on their gender, height and weight. To make things easier to understand, this dataset has been modified to categorize 22 people into a BMI category based on their height and weight.

To classify a new data point into a BMI category, the KNN algorithm works as follows:

1. Assign a value to K. The K represents the number of neighbors considered in the classification problem. For example, if K is 3 then only 3 nearest neighbors of the new data point will be considered in the classification problem.
2. Calculate the distance between the new data point with all of the other existing data points. The distance between the new data point and the nearest neighbors can be calculated using different types of distance metrics such as Euclidean distance, Manhattan distance, Minkowski distance, etc. We will be using Euclidean distance.
3. Arrange the calculated distances from Step 2 in ascending order
4. Select K data points with the smallest distances. These are the K-Nearest Neighbors of the new data point.
5. From the K Neighbors, assign the new data point to the majority class (or a BMI category)

Before we go through a worked example, let's first understand how to calculate the distance between a new data point with all of the other existing data points using the Euclidean distance.

How to find the Euclidean distance

Euclidean distance is the distance between two points (i.e. the length of the line segment between two points). Euclidean distance can be found using Pythagoras theorem. The Euclidean distance formula in a 2D space is:

d = √[(x₂ – x₁)² + (y₂ – y₁)²]

where:

• d is the Euclidean distance
• (x₁, y₁) is the coordinate of the first point
• (x₂, y₂) is the coordinate of the second point

Let's go through an example.

1. Let's determine the Euclidean distance between two points A (x₁, y₁) and B (x₂, y₂)

2. Join point A with point B using a straight line

3. Create a right-angled triangle. The hypotenuse (the longest side of the right-angled triangle) is AB.

• Draw a horizontal line from point A to C
• Draw a vertical line from point B to C

4. We can now apply Pythagoras theorem to the triangle ABC to find the distance between A and B. The Pythagoras theorem formula is:

Hypotenuse² = Base² + Perpendicular²

If we substitute the values in the formula we get:

AB² = AC² + BC²

Let's now calculate the distance between A and C which is simply (x₂ – x₁)²

Next, let's calculate the distance between B and C which is simply (y₂ – y₁)²

Therefore, d² = (x₂ – x₁)² + (y₂ – y₁)²

Finally we take the square root on both sides of the equation and the formula for Euclidean distance is derived:

d =√[(x₂ – x₁)² + (y₂ – y₁)²]

A Worked Example of KNN

Let's go through an example of how a new data point is classified using the KNN algorithm. In our data set, we will be classifying person X (the black dot in the diagram below) into a BMI category.

We will be calculating the distance using Euclidean distance and the value of K is 3. To make things easier to work with let's represent the data set as a table. Each person in the table is categorized into a BMI category of Extremely Weak, Weak, Normal, Overweight, Obesity and Extreme Obesity.

The new data point to be classed into a BMI category is:

We can now apply the KNN algorithm to class the new data point.

Step 1 - Calculate the Euclidean distance

The new data point (i.e. person to classify into a BMI category) is:

The formula for Euclidean distance is:

d =√[(x₂ – x₁)² + (y₂ – y₁)²]

where:

• x₂ is the new person's height (in this example it is 190 cm)
• x₁ is the existing person's height
• y₂ is the new person's weight (in this example it is 75 kg)
• y₁ is the existing person's weight

Calculating the Euclidean distance between the new data point and all of the existing data points:

Step 2 - Arrange Distances in Ascending Order

Rearranging the distances in ascending order:

Step 3 - Select K-Nearest Neighbors

Since we defined the K value as 3, we will select the top 3 entries from the table:

Step 4 - Assign New Data Point to Majority Class

From the K Neighbors, the majority class is Normal. We can therefore classify the new data point or the new person into a BMI category of Normal. The updated table:

KNN Pros and Cons

The KNN algorithm is easy to understand, implement and works well with simple classification problems that have small data sets and features. However one of the biggest drawbacks with the algorithm is that it is computationally heavy with large data sets. This is because the algorithm finds the distance between the new data point and all of the existing data points before it can classify the data. Selecting the optimal K value is also important as this will increase the accuracy of the model.

References

• Kaggle BMI Dataset
• Euclidean Distance