C++로 KNN 분류기 구현하기

본 블로그 작성 글들은, 강의를 목표로 하고 제작되었습니다. 또한 작성된 글의 정보도 틀렸을 수 있으니, 주의해주세요.

KNN 분류기를 C++로 직접 만들어보자. 예제에서는 두 개의 특징을 가진 샘플과 정수형 클래스를 사용한다.

#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 값을 시험해야 한다. 코드가 실행된다는 것과 좋은 예측을 한다는 것은 서로 다른 문제다.