KNN Introduction

Lesson 6 of 19 in Coddy's Introduction to Machine Learning course.

K-Nearest Neighbors (KNN) is a supervised learning algorithm that’s used for both classification and regression problems. It’s simple yet powerful and is often used as a baseline for more complex models.

The KNN algorithm finds feature similarity using distance metrics to identify the closest neighbors to a point. For example, it can sort wines by comparing them to the closest ones, like grouping together wines with similar flavors. It’s like having a guide who helps you find which wines are alike based on their most common traits. 🍷
The idea behind KNN is quite straightforward:

Distance Calculation: For a given test point, the algorithm calculates the distance between that point and every other point in the training dataset. The distance can be calculated in various ways, such as Euclidean or Manhattan distance.
Find Nearest Neighbors: The algorithm then selects the k points in the training data that are closest to the test point. k is a user-defined constant, and can be any integer.
Make Prediction: For classification, the algorithm assigns the most common class label among the k nearest neighbors to the test point. For regression, it assigns the average of the ‘k’ nearest neighbors.

KNN is a lazy learning algorithm, meaning it doesn’t actually learn a model. Instead, it memorizes the training instances and uses them for prediction (the next lesson will cover the training phase). This makes KNN computationally expensive during the testing phase.

Despite its simplicity, KNN can achieve surprisingly good performance. However, it’s sensitive to the choice of k and the type of distance metric, and it doesn’t perform well with high-dimensional data due to the curse of dimensionality.

Test yourself

This lesson includes a short quiz. Start the lesson to answer it and track your progress.

Test yourself

This lesson includes a short quiz. Start the lesson to answer it and track your progress.

Test yourself

This lesson includes a short quiz. Start the lesson to answer it and track your progress.

Challenge

Easy

In this challenge, we will learn different distance calculations.

Create a function named distances_option_calculator that receives three variables: X, y, and distance_type. The functions will return the distance between X and y according to the distance_type.

Here is a list of common distance calculations:

Euclidian distance (Most common) The straight-line distance between two points. The square root of the sum of the squares of the differences between each corresponding coordinate of the points:

Manhattan distance is also known as Taxicab or City Block distance. The sum of the absolute differences between points across all dimensions. For two points ( P ) and ( Q ), with coordinates ( (p_1, p_2, …, p_n) ) and ( (q_1, q_2, …, q_n) ) respectively:

Hamming distance: The number of positions at which the corresponding symbols are different. It’s often used for categorical data.
For example, let’s take two binary strings:

String 1: 1101
String 2: 1001

Comparing them position by position, we see that the second position has different bits (1 in String 1 and 0 in String 2). All other positions are the same. So, the Hamming distance between these two strings is 1.

The distance_type can have the following items: hamming, manhattan, euclidian.

Try it yourself

def distances_option_calculator(X, y, distance_type):
    # Write code here
    if distance_type == "euclidian":
        pass
    elif distance_type == "manhattan":
        pass
    elif distance_type == "hamming":
        pass