C++でKNN分類器を実装する

本ブログ作成文は、講義を目指して製作されました。 また、作成された文章の情報も間違っている可能性がありますので、ご注意ください。

KNN分類器をC ++で直接作成しましょう。 この例では、2つの特徴を持つサンプルと整数型クラスを使用しています。

#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)である。 近いK個だけが必要な場合std::nth_elementを使用したり、データが非常に大きい場合は、KD-Treeなどの空間データ構造を検討することができます。

同率処理もプロジェクトルールに合わせて定めなければならない。 投票数が等しい場合は、より近いクラスの合計距離を比較したり、クラス優先順位を付けたりすることができます。

そして実戦では、学習データと検証データを分けて複数のK値を試験しなければならない。 コードが実行されると良い予測をすることは異なる問題です。