Implementing a KNN classifier in C++

The articles written on this blog were created with the goal of teaching. Also, the information in the article may be incorrect, so please be careful.

Let’s create a KNN classifier ourselves in C++. The example uses a sample and integer class with two features.

#include <algorithm>
#include <cmath>
#include <stdexcept>
#include <unordered_map>
#include <vector>

struct Sample
{
    float X = 0.0f;
    float Y = 0.0f;
    int Label = 0;
};

struct Neighbor
{
    float DistanceSquared = 0.0f;
    int Label = 0;
};

int PredictKNN(const std::vector<Sample>& Samples, float X, float Y, int K)
{
    if (Samples.empty())
    {
        throw std::invalid_argument("Samples must not be empty");
    }

    std::vector<Neighbor> Neighbors;
    Neighbors.reserve(Samples.size());

    for (const Sample& Item : Samples)
    {
        const float DX = Item.X - X;
        const float DY = Item.Y - Y;
        Neighbors.push_back({ DX * DX + DY * DY, Item.Label });
    }

    std::sort(Neighbors.begin(), Neighbors.end(),
        [](const Neighbor& A, const Neighbor& B)
        {
            return A.DistanceSquared < B.DistanceSquared;
        });

    K = std::clamp(K, 1, static_cast<int>(Neighbors.size()));

    std::unordered_map<int, int> Votes;
    for (int Index = 0; Index < K; ++Index)
    {
        ++Votes[Neighbors[Index].Label];
    }

    int BestLabel = Neighbors[0].Label;
    int BestVotes = 0;

    for (const auto& [Label, VoteCount] : Votes)
    {
        if (VoteCount > BestVotes)
        {
            BestLabel = Label;
            BestVotes = VoteCount;
        }
    }

    return BestLabel;
}

Only square distances were compared without calculating square roots. Since only the order of distances is needed, the result is the same.

Limitations of simple implementation

The current code sorts all neighbors, so the time complexity is approximatelyO(N log N)am. If you only need K nearbystd::nth_elementYou can use , or if the data is very large, you can consider a spatial data structure such as KD-Tree.

Tie handling must also be determined in accordance with project rules. When the number of votes is the same, you can compare the total distance of classes that are closer, or prioritize classes.

And in practice, multiple K values ​​must be tested by dividing the training data and validation data. Getting code to run and making good predictions are two different things.