用 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值。 让代码运行和做出好的预测是两件不同的事情。