Implementing k-Nearest Neighbors Algorithm in C++

Welcome to our exploration of the k-Nearest Neighbors (k-NN) algorithm! This essential machine learning classifier is widely appreciated for its simplicity and effectiveness. This lesson will equip you with a clear understanding of the k-NN algorithm and its elements, including the concept and selection of 'k' as well as distance calculation using the Euclidean metric. We'll proceed to implement a k-NN classifier in C++. Intriguing, isn't it? Let's delve into k-NN!

The k-NN algorithm classifies data based on a data point's 'k' nearest neighbors from the training dataset. Consider a fruit classification scenario: if a new data point, or fruit, emerges and 'k' is set to 3, the new fruit is classified based on the majority within its three nearest neighbors. Essentially, k-NN takes advantage of the simplicity of voting to make decisions—the class that receives the most votes wins!

Let's see this in action. Consider this dataset, where we have three fruits of Class 0 and three fruits of Class 1. We also have a query point, which is a fruit we aim to assign a class label to.

The kNN algorithm works on a basic principle: a data point is likely to be in the same category as the data points it is closest to. So, the model will identify the 'k' points nearest to our query point, and these 'k' points will vote on what Class the query should belong to. The class label with the most votes will be assigned to the query point. In this case, the query point will be assigned the Class 0 label.

Note that choosing 'k' significantly impacts our model. A low 'k' might capture more noise in the data, whereas a high 'k' is computationally expensive. Therefore, running tests to identify the optimal 'k' is crucial.

In k-NN, classification is determined by weighing the distance between data points. Euclidean distance is a frequently used metric that calculates the shortest straight-line distance $\sqrt{{(x_1 - x_2)}^2 + {(y_1 - y_2)}^2}$ between two points $(x_1, y_1)$ and $(x_2, y_2)$ in a Euclidean space. This formula, rooted in the Pythagorean theorem, will be implemented next in C++:

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// The 'euclidean_distance' function computes the Euclidean distance between two points
double euclidean_distance(const vector<double>& point1, const vector<double>& point2) {
    double sum_squares = 0.0;
    for (size_t i = 0; i < point1.size(); ++i) {
        sum_squares += pow(point1[i] - point2[i], 2); // Calculate squared distance for each dimension
    }
    return sqrt(sum_squares); // Return the square root of the sum of squares
}

int main() {
    vector<double> point1 = {1, 2}; // The coordinates of the first point
    vector<double> point2 = {4, 6}; // The coordinates of the second point
    cout << euclidean_distance(point1, point2) << endl; // 5.0

    return 0;
}

This code calculates and outputs the Euclidean distance between point1 and point2.