Implementando un clasificador KNN en C++

Los artículos escritos en este blog fueron creados con el objetivo de enseñar. Además, la información del artículo puede ser incorrecta, así que tenga cuidado.

Creemos un clasificador KNN nosotros mismos en C++. El ejemplo utiliza una clase de muestra y de número entero con dos características.

#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;
}

Sólo se compararon distancias cuadradas sin calcular raíces cuadradas. Como sólo se necesita el orden de las distancias, el resultado es el mismo.

Limitaciones de la implementación simple

El código actual ordena todos los vecinos, por lo que la complejidad del tiempo es aproximadamenteO(N log N)soy. Si solo necesitas K cercastd::nth_elementPuede utilizar , o si los datos son muy grandes, puede considerar una estructura de datos espaciales como KD-Tree.

El manejo de los amarres también debe determinarse de acuerdo con las reglas del proyecto. Cuando el número de votos es el mismo, puedes comparar la distancia total de las clases que están más cerca o priorizar las clases.

Y en la práctica, se deben probar múltiples valores de K dividiendo los datos de entrenamiento y los datos de verificación. Hacer que el código se ejecute y hacer buenas predicciones son dos cosas diferentes.