TensorTonic의 KNN Classifier 문제를 풀면서 정리했다. 지금까지 다뤘던 선형 회귀 로지스틱 회귀 소프트맥스 회귀는 모두 "데이터에 맞는 파라미터를 찾는다"는 같은 틀 위에 있었다. KNN은 그 틀을 비껴간다. 학습 과정도, 파라미터도 없다. 그 차이가 알고리즘 모양을 어떻게 바꾸는지가 이 글의 중심이다.

학습이 없는 모델

KNN(K-Nearest Neighbors)은 instance-based learning 또는 lazy learning으로 분류된다. 이름 그대로 학습 단계에서 사실상 아무것도 안 한다. fit 함수가 하는 일이라곤 데이터를 그대로 저장하는 게 전부다.

	선형/로지스틱/소프트맥스 회귀	KNN
학습	경사하강법으로 $w, b$ 업데이트	데이터 저장만
예측	$\hat{y} = f(\mathbf{x}; w, b)$ 한 번	모든 학습 데이터와 거리 + 다수결
파라미터	$O(d)$ 또는 $O(dK)$	없음 (단 학습 데이터 전부 보관)
비용 무게중심	학습	예측

이전 모델들이 학습에서 비용을 치르고 예측은 거의 공짜였다면 KNN은 반대다. 학습은 공짜고 예측 때마다 모든 학습 데이터를 훑는다. 그래서 데이터가 늘어날수록 예측이 느려진다.

장점은 단순함이다. 모델의 가설(hypothesis) 이 따로 없다. 선형 회귀가 "정답이 입력의 선형 결합으로 표현된다"는 가설을 깔고 들어간다면 KNN은 "비슷한 입력은 비슷한 출력을 갖는다"라는 거의 보편적인 가정 하나로 충분하다. 결정 경계 모양에 제약이 없다. 데이터 분포가 곡선이든 도넛이든 그대로 따라간다.

알고리즘

문제 정의를 그대로 옮기면 두 줄이다.

d(\mathbf{x}, \mathbf{x}') = \sqrt{\sum_{j=1}^{d} (x_j - x'_j)^2}

\hat{y} = \arg\max_{c} \sum_{i \in N_k(\mathbf{x})} \mathbf{1}[y_i = c]

순서대로 읽으면 "테스트 점 $\mathbf{x}$ 에 가장 가까운 학습 점 $k$ 개를 모아( $N_k(\mathbf{x})$ ) 그 안에서 가장 많이 등장한 클래스 $c$ 를 답으로 한다"이다. 위 식에서 $d$ 가 두 번 등장하는데 의미가 다르다. 왼쪽의 $d(\cdot, \cdot)$ 는 distance 함수 이름이고 시그마의 위 첨자 $d$ 는 입력의 차원 수다. 헷갈리기 쉬워 짚어둔다.

거리 함수 선택

거리만 정의되면 어떤 데이터에도 KNN을 쓸 수 있다. 그 거리를 어떻게 정의하느냐가 결과를 가른다.

이름	식	특징
유클리드 (L2)	$\sqrt{\sum_j (x_j - x'_j)^2}$	직선거리. 회전 불변
맨해튼 (L1)	$\sum_j \lvert x_j - x'_j \rvert$	격자 따라 가는 거리. 축 의존적
코사인	$1 - \dfrac{\mathbf{x} \cdot \mathbf{x}'}{\lVert \mathbf{x} \rVert \lVert \mathbf{x}' \rVert}$	방향만 비교. 크기 차이 무시

이 문제는 유클리드 거리를 명시한다. 식만 보면 "그냥 차이의 절댓값 합을 쓰면 안 되나" 싶다. 절댓값 합도 그 자체로 유효한 거리 함수다(맨해튼 거리). 다만 KNN의 표준 기본값으로 유클리드가 자리잡은 이유가 있다.

직선거리 직관과 맞는다. "가깝다"는 인간의 직관이 보통 직선거리에 가깝다.
회전 불변이다. 좌표축을 어떻게 회전시켜도 거리가 같다. 맨해튼은 축에 따라 값이 달라져 좌표계 선택을 탄다.
미분 가능하다. KNN 자체에는 필요 없지만 거리 함수를 학습 대상으로 삼는 metric learning 같은 후속 작업에서 중요해진다.

유클리드를 곧바로 가져다 쓰기 전에 한 가지 먼저 확인할 게 있다. feature의 스케일이 맞춰져 있는가다. 한 feature가 0~~1 범위이고 다른 feature가 0~~10000 범위라면 거리 계산이 큰 feature 하나에 사실상 지배된다. 표준화(StandardScaler)나 정규화(MinMaxScaler)가 KNN의 사실상 전제다. 선형 회귀에서는 스케일 차이가 학습률 튜닝 정도의 문제였지만 KNN에서는 모델 동작 자체가 망가진다.

Tie-breaking 규칙

다수결에 함정이 하나 있다. 표가 동률로 갈리는 경우다. $k = 4$ 에 두 클래스가 2:2로 갈리면 "가장 많이 등장한 클래스"가 둘이다. 어느 쪽을 고를지 명시적으로 정해 두지 않으면 구현마다 답이 달라진다.

이 문제는 "동률이면 더 작은 클래스 라벨을 선택"이라는 규칙을 명시한다. 결정론적이고 검증하기 쉬워 코딩 테스트에서 흔히 등장한다. 그런데 파이썬의 Counter.most_common은 동률일 때 먼저 등장한 라벨을 우선한다. 입력 순서에 따라 답이 달라지므로 그대로 두면 채점이 어긋난다.

Counter([2, 1, 2, 1]).most_common(1)  # [(2, 2)]
Counter([1, 2, 1, 2]).most_common(1)  # [(1, 2)]

요구사항을 맞추려면 횟수가 같을 때 라벨 값으로 한 번 더 비교해야 한다. 방법은 여럿이지만 가장 깔끔한 건 튜플 비교다. 파이썬에서 튜플은 사전식으로 비교되므로 "1차 키는 횟수 내림차순 2차 키는 라벨 오름차순"을 한 줄로 표현할 수 있다.

min(counts.items(), key=lambda it: (-it[1], it[0]))

min은 기본이 오름차순이라 횟수가 큰 쪽을 고르려면 부호를 뒤집어 -it[1]로 둔다. 같은 횟수일 때는 it[0](라벨)이 작은 쪽이 사전식 비교에서 더 작으므로 자동으로 선택된다. 전체를 정렬할 필요가 없으니 sorted(...)[0]보다 한 단계 가볍다.

라벨이 작은 음 아닌 정수라면 np.bincount로 풀어도 좋다. bincount의 인덱스가 곧 라벨이고 argmax는 최댓값이 동률일 때 가장 작은 인덱스를 돌려준다. 이 성질이 우리 tie-break 규칙과 정확히 맞아떨어진다.

NumPy 구현

import numpy as np
from collections import Counter

def knn_classify(X_train, y_train, X_test, k=3):
    """
    Returns: A list of predicted integer labels for each test point
    """
    X_train = np.asarray(X_train, dtype=float)
    y_train = np.asarray(y_train, dtype=int)
    X_test = np.asarray(X_test, dtype=float)

    prediction = []
    for x in X_test:
        distances = np.sqrt(np.sum((X_train - x) ** 2, axis=1))
        nearest_idx = np.argsort(distances)[:k]
        nearest_labels = y_train[nearest_idx]
        counts = Counter(nearest_labels.tolist())
        predicted_label = min(counts.items(), key=lambda it: (-it[1], it[0]))[0]
        prediction.append(predicted_label)

    return prediction

학습 코드가 따로 없다는 게 첫인상이다. 회귀 모델 구현은 for _ in range(epochs) 루프 안에서 w와 b를 업데이트하는 게 본체였는데 KNN에는 그 루프가 통째로 빠져 있다. 대신 테스트 점 하나당 거리 계산 → 정렬 → 다수결 세 단계가 자리를 차지한다.

거리 계산이 한 줄로 끝나는 이유

distances = np.sqrt(np.sum((X_train - x) ** 2, axis=1))

X_train은 $(n, d)$ 모양 행렬이고 $\mathbf{x}$ 는 $(d,)$ 벡터다. 두 모양이 다른데도 X_train - x가 그대로 동작하는 건 브로드캐스팅 덕분이다. numpy가 $\mathbf{x}$ 를 $(n, d)$ 로 복제한 셈치고 다뤄서 모든 행에서 한 번씩 뺀 결과를 만든다. shape이 어떻게 변해 가는지 따라가 보면 다음과 같다.

X_train - x → $(n, d)$ . 각 행이 한 학습 점과 테스트 점의 좌표별 차이.
** 2 → $(n, d)$ . 원소별 제곱.
np.sum(..., axis=1) → $(n,)$ . 행마다 모든 feature 차이를 합쳐 거리의 제곱 하나로 줄임.
np.sqrt → $(n,)$ . 원소별 제곱근.

핵심은 axis=1이 가리키는 바다. 합치는 축이 결과에서 사라진다. $d$ 차원 feature 축을 따라 합치므로 결과는 feature 축이 빠진 길이 $n$ 벡터다. 만약 axis를 빼면 전체가 한 스칼라로 줄어 "모든 학습 점까지 거리의 제곱을 다 더한 값" 하나가 되어 버린다.

수치적 여담 하나. 사실 np.sqrt는 생략해도 KNN의 결과가 같다. 제곱근은 단조 함수라서 거리 제곱으로 정렬한 순서와 거리로 정렬한 순서가 동일하기 때문이다. argsort가 보는 건 순서뿐이라 sqrt 한 단계를 아껴도 답이 바뀌지 않는다. 거리를 다른 곳에 출력하거나 임계값과 비교할 일이 있다면 의미가 달라지므로 수식 그대로 두는 편이 안전하다.

argsort로 인덱스 뽑기

nearest_idx = np.argsort(distances)[:k]
nearest_labels = y_train[nearest_idx]

np.argsort는 정렬된 값이 아니라 정렬된 순서의 인덱스를 반환한다. 우리가 알아야 하는 건 "어느 학습 점이 가까운가"이지 "그 거리가 얼마인가"가 아니다. 거리를 그냥 정렬해 버리면 원본 인덱스가 사라져 그 점의 라벨을 다시 찾을 길이 없다. argsort가 돌려준 인덱스를 y_train에 fancy indexing으로 넘기면 가까운 점들의 라벨이 한 번에 뽑힌다.

성능을 더 짜내야 한다면 np.argpartition(distances, k)[:k]로 바꿀 수 있다. 상위 $k$ 개만 모으면 충분하므로 전체 정렬보다 빠르다. 다만 그 안에서의 순서는 보장되지 않는데 다수결만 할 거라면 그 순서는 어차피 필요 없다.

다수결과 tie-break

counts = Counter(nearest_labels.tolist())
predicted_label = min(counts.items(), key=lambda it: (-it[1], it[0]))[0]

앞서 본 튜플 비교 트릭이 이 한 줄로 압축된다. Counter는 {라벨: 등장횟수} 형태의 dict이고 .items()로 꺼낸 (라벨, 횟수) 쌍에 key 함수를 걸어 min이 사전식으로 비교한다. 람다의 인자 이름을 it으로 둔 건 바깥 루프 변수 x와 이름이 겹치지 않게 하기 위해서다. 같은 x를 써도 동작은 같지만 가독성이 떨어진다.

.tolist()는 np.int64를 일반 파이썬 int로 바꿔 Counter의 키 타입을 단순화한다. 안 붙여도 보통 동작하지만 다른 코드와 라벨을 비교할 때 타입 차이로 미묘한 버그가 생기곤 한다.

$k$ 를 어떻게 고를까

$k$ 는 KNN의 사실상 유일한 하이퍼파라미터다. 너무 작거나 크면 곤란한데 두 방향의 트레이드오프가 정반대다.

$k$ 가 작으면 (예: $k = 1$ ) 결정 경계가 학습 점 하나하나를 그대로 따라간다. 노이즈가 섞인 한 점이 그 주변 예측을 통째로 흔든다. variance가 크고 bias가 작은 모델이다.
$k$ 가 크면 가까운 점뿐 아니라 멀리 있는 점까지 투표에 참여한다. 결정 경계가 매끄러워지는 대신 클래스 경계 근처에서 다수파에 휩쓸려 잘못 분류할 가능성이 커진다. bias가 크고 variance가 작은 모델이다.

극단을 잡아 보면 더 명확해진다. $k = 1$ 이면 학습 점을 모두 정확히 맞히지만 노이즈에 취약하다. $k = n$ 이면 어떤 입력이 와도 학습 데이터에서 가장 흔한 클래스만 답으로 내놓는다. 그 사이 어딘가에 좋은 값이 있다.

실무에서는 보통 교차 검증으로 후보를 훑어 $k$ 를 고른다. 이진 분류에서는 동률을 피하려고 홀수를 쓰는 관습이 있다. 다중 분류에서는 홀수만으로 동률을 막을 수 없으므로 앞서 본 tie-break 규칙이 더 중요해진다.

고차원의 함정: 차원의 저주

KNN이 "비슷한 입력은 비슷한 출력"을 가정한다고 했는데 이 가정이 흔들리는 상황이 있다. 고차원 공간이다.

차원이 커질수록 임의의 두 점 사이 거리가 거의 같아진다는 현상이 일어난다. 가장 가까운 점과 가장 먼 점 사이 거리 비율이 1에 수렴한다는 결과가 알려져 있다. "가깝다"는 개념 자체가 의미를 잃기 시작한다. feature가 수십 개만 돼도 이 효과가 체감된다.

대처는 두 갈래다. 하나는 차원 축소다. PCA나 오토인코더로 의미 있는 저차원 표현을 먼저 뽑고 그 위에서 KNN을 돌린다. 다른 하나는 거리 함수를 데이터에 맞춰 학습하는 metric learning이다. 모든 feature를 동등하게 다루는 유클리드 대신 데이터의 분포 구조를 반영한 거리로 바꿔 가까움의 의미를 회복한다.

예측 비용과 가속 자료구조

순진하게 구현한 KNN의 예측 비용은 테스트 점 하나당 $O(nd)$ 다. 학습 데이터 전체와 거리를 재고 정렬해야 한다. 점이 수십만 개를 넘기면 한 예측에 초 단위가 걸리기 시작한다.

이를 줄이는 표준적인 방법이 트리 기반 자료구조다. KD-tree는 축에 평행한 초평면으로 공간을 재귀 분할해 검색 범위를 가지치기로 잘라낸다. 평균 $O(\log n)$ 수준의 검색이 가능하지만 차원이 커지면 효율이 급격히 떨어진다. Ball-tree는 초구로 공간을 묶어 분할하므로 비교적 고차원에서도 견딘다. 더 큰 데이터에서는 정확한 최근접 대신 근사 알고리즘을 쓰는 게 일반적이다. 벡터 검색 엔진에서 사실상 표준이 된 HNSW 같은 그래프 기반 인덱스가 대표적이다.

sklearn의 KNeighborsClassifier는 algorithm 파라미터로 brute, kd_tree, ball_tree, auto를 선택할 수 있고 데이터 크기와 차원에 따라 적절한 쪽으로 자동 분기한다.

마무리

KNN을 처음 만나면 "이게 학습이 맞나" 싶을 정도로 단순하다. 단순함의 대가는 예측 비용과 거리 정의에 대한 민감도다. 그럼에도 이 모델이 ML 입문에 자주 등장하는 이유는 분류라는 문제의 본질을 가장 빠르게 보여주기 때문이다. 분류는 결국 결정 경계를 어떻게 그릴 것인가의 문제다. 선형 모델은 그 경계의 형태를 함수로 가정하고 가정에 맞는 파라미터를 찾는다. KNN은 가정을 거의 두지 않고 데이터가 직접 경계를 그리게 둔다. 어떤 모델을 쓰든 "가정을 얼마나 두는가"와 "데이터에 얼마나 따라가는가" 사이의 트레이드오프를 피할 수 없다.

이번 구현에서 남는 포인트는 세 가지다.

학습이 없는 모델도 있다. 파라미터를 찾는 대신 데이터를 그대로 들고 다닌다. 비용의 무게중심이 학습에서 예측으로 옮겨간다는 점이 이 트레이드오프의 핵심이다.
거리 함수가 모델의 가정 역할을 한다. 어떤 거리를 쓰느냐 그리고 feature가 어떻게 스케일되어 있느냐가 결과를 결정한다. KNN에서는 전처리가 모델 선택만큼 중요하다.
다수결도 규칙이 필요하다. 동률 처리는 사소해 보여도 명시하지 않으면 결정론적이지 않은 출력이 나온다. (-count, label) 같은 튜플 키로 한 번에 표현할 수 있다.