用 C++ 實作 KNN 分類器

該部落格上撰寫的文章是出於教學目的而創建的。 另外，文章中的資訊可能不正確，請謹慎。

讓我們用 C++ 自己建立一個 KNN 分類器。 此範例使用具有兩個特徵的樣本和整數類別。

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

僅比較平方距離，而不計算平方根。 由於只需要距離的順序，因此結果是相同的。

簡單實現的局限​​性

當前代碼對所有鄰居進行排序，因此時間複雜度約為O(N log N)是。 如果你只需要附近的Kstd::nth_element可以使用 ，或者如果資料很大的話可以考慮KD-Tree之類的空間資料結構。

平局處理也必須根據項目規則來決定。 當得票數相同時，您可以比較較近的班級的總距離，或優先考慮班級。

而在實際中，必須透過訓練資料和驗證資料的劃分來測試多個K值。 讓程式碼運行和做出好的預測是兩件不同的事情。