Implementierung eines KNN-Klassifikators in C++

Die in diesem Blog verfassten Artikel wurden mit dem Ziel erstellt, zu unterrichten. Außerdem können die Informationen im Artikel falsch sein, also seien Sie bitte vorsichtig.

Lassen Sie uns selbst einen KNN-Klassifikator in C++ erstellen. Das Beispiel verwendet eine Sample- und Integer-Klasse mit zwei Funktionen.

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

Es wurden nur quadratische Abstände verglichen, ohne dass Quadratwurzeln berechnet wurden. Da nur die Reihenfolge der Abstände benötigt wird, ist das Ergebnis dasselbe.

Einschränkungen der einfachen Implementierung

Der aktuelle Code sortiert alle Nachbarn, sodass die zeitliche Komplexität ungefähr beträgtO(N log N)Bin. Wenn Sie nur K in der Nähe brauchenstd::nth_elementSie können verwenden oder, wenn die Daten sehr groß sind, eine räumliche Datenstruktur wie KD-Tree in Betracht ziehen.

Der Umgang mit Krawatten muss ebenfalls gemäß den Projektregeln festgelegt werden. Wenn die Anzahl der Stimmen gleich ist, können Sie die Gesamtdistanz der Klassen vergleichen, die näher beieinander liegen, oder Klassen priorisieren.

Und in der Praxis müssen mehrere K-Werte getestet werden, indem die Trainingsdaten und die Verifizierungsdaten geteilt werden. Code zum Laufen zu bringen und gute Vorhersagen zu treffen, sind zwei verschiedene Dinge.