K-최근접 이웃과 거리 척도(K-Nearest Neighbors and Distance Metrics)

전부 저장합니다. 예측할 때 이웃을 봅니다. 실제로 동작하는 가장 단순한 알고리즘입니다.

유형: Build 언어: Python 선수 지식: Phase 1 (14 Norm과 거리) 예상 시간: 약 90분

학습 목표

• 설정 가능한 K와 거리 가중 투표(Distance-weighted voting)를 포함해 KNN 분류와 회귀를 처음부터 구현합니다.
• L1, L2, 코사인(Cosine), 민코프스키(Minkowski) 거리 척도를 비교하고 데이터 유형에 맞는 거리 척도를 선택합니다.
• 차원의 저주(Curse of dimensionality)를 설명하고, 고차원 공간에서 KNN 성능이 왜 떨어지는지 시연합니다.
• 효율적인 최근접 이웃 탐색(Nearest neighbor search)을 위한 KD-tree를 만들고, 언제 brute-force보다 빠른지 분석합니다.

문제

데이터셋이 있습니다. 새 데이터 포인트가 들어왔고, 이를 분류하거나 값을 예측해야 합니다. 선형 회귀나 SVM처럼 데이터에서 파라미터를 학습하는 대신, 새 포인트와 가장 가까운 K개의 학습 포인트를 찾고 그 이웃들이 투표하게 할 수 있습니다.

이것이 K-최근접 이웃(K-nearest neighbors, KNN)입니다. 학습 단계가 없습니다. 학습할 파라미터도 없고, 최소화할 손실 함수도 없습니다. 전체 학습 세트를 저장해두고 예측 시점에 거리를 계산합니다.

너무 단순해서 동작하지 않을 것처럼 보입니다. 하지만 KNN은 작은 데이터셋과 중간 규모 데이터셋에서 의외로 경쟁력 있습니다. 또한 KNN을 깊이 이해하면 거리 척도 선택, 차원의 저주, 게으른 학습(Lazy learning)과 즉시 학습(Eager learning)의 차이를 알 수 있습니다.

KNN은 현대 AI에도 다른 이름으로 계속 등장합니다. 벡터 데이터베이스(Vector database)는 임베딩(Embedding) 위에서 KNN 탐색을 합니다. 검색 증강 생성(Retrieval-augmented generation, RAG)은 가장 가까운 K개의 문서 청크(chunk)를 찾습니다. 추천 시스템은 비슷한 사용자나 아이템을 찾습니다. 알고리즘은 같습니다. 규모와 자료구조가 달라질 뿐입니다.

개념

KNN이 동작하는 방식

라벨이 있는 데이터셋과 새 질의 포인트(query point)가 주어졌을 때 KNN은 다음 순서로 동작합니다.

1. 질의(query)와 데이터셋의 모든 포인트 사이의 거리를 계산합니다.
2. 거리를 기준으로 정렬합니다.
3. 가장 가까운 K개를 선택합니다.
4. 분류(Classification)에서는 K개 이웃의 다수결 투표(Majority vote)를 사용합니다.
5. 회귀(Regression)에서는 K개 이웃 값의 평균 또는 가중 평균을 사용합니다.

graph TD
    Q["질의 포인트 ?"] --> D["모든 학습 포인트까지<br>거리 계산"]
    D --> S["거리 기준 정렬"]
    S --> K["K개 최근접 이웃 선택"]
    K --> C{"분류<br>또는 회귀?"}
    C -->|분류| V["다수결 투표"]
    C -->|회귀| A["값 평균"]
    V --> P["예측"]
    A --> P

알고리즘은 여기까지입니다. 적합(fitting)도, 경사하강법도, 에포크(epoch)도 없습니다.

K 선택하기

K는 KNN의 유일한 하이퍼파라미터입니다. K는 편향-분산 절충(Bias-variance trade-off)을 제어합니다.

일반적인 시작점은 데이터셋 크기가 N일 때 K = sqrt(N)입니다. 이진 분류에서는 동률을 피하기 위해 홀수 K를 사용하는 것이 좋습니다.

graph LR
    subgraph "K=1 (과적합)"
        A["울퉁불퉁한 경계<br>모든 점을 따라감"]
    end
    subgraph "K=15 (적절)"
        B["부드러운 경계<br>진짜 패턴 포착"]
    end
    subgraph "K=N (과소적합)"
        C["평평한 경계<br>다수 클래스 예측"]
    end
    A -->|"K 증가"| B -->|"K 증가"| C

거리 척도

거리 함수는 "가깝다"는 말의 의미를 정의합니다. 거리 척도가 달라지면 이웃도 달라지고 예측도 달라집니다.

L2, 즉 유클리드 거리(Euclidean distance) 는 기본 선택지입니다. 직선 거리입니다.

d(a, b) = sqrt(sum((a_i - b_i)^2))

특성 스케일에 민감합니다. L2를 KNN에 사용할 때는 항상 특성을 표준화해야 합니다.

L1, 즉 맨해튼 거리(Manhattan distance) 는 절댓값 차이를 합산합니다. 차이를 제곱하지 않기 때문에 L2보다 이상치(Outlier)에 더 강합니다.

d(a, b) = sum(|a_i - b_i|)

코사인 거리(Cosine distance) 는 벡터의 크기는 무시하고 각도를 측정합니다. 텍스트와 임베딩 데이터에서 중요합니다.

d(a, b) = 1 - (a . b) / (||a|| * ||b||)

민코프스키 거리(Minkowski distance) 는 파라미터 p로 L1과 L2를 일반화합니다.

d(a, b) = (sum(|a_i - b_i|^p))^(1/p)

p=1: Manhattan
p=2: Euclidean
p->inf: Chebyshev (최대 절댓값 차이)

어떤 척도를 쓸지는 데이터에 따라 달라집니다.

가중 KNN

표준 KNN은 K개 이웃에 같은 가중치를 줍니다. 하지만 거리 0.1의 이웃은 거리 5.0의 이웃보다 더 중요해야 합니다.

거리 가중 KNN(Distance-weighted KNN) 은 각 이웃의 거리에 반비례해 가중치를 줍니다.

weight_i = 1 / (distance_i + epsilon)

분류: 가중 투표
회귀: 가중 평균 = sum(w_i * y_i) / sum(w_i)

epsilon은 질의 포인트가 학습 포인트와 정확히 같을 때 0으로 나누는 일을 막습니다.

가중 KNN은 먼 이웃의 영향이 작기 때문에 K 선택에 덜 민감합니다.

차원의 저주

고차원에서는 KNN 성능이 떨어집니다. 이는 막연한 우려가 아니라 수학적 사실입니다.

문제 1: 거리들이 수렴합니다. 차원이 커질수록 최대 거리와 최소 거리의 비율이 1에 가까워집니다. 모든 점이 질의에서 거의 똑같이 "멀어집니다".

무작위 균등 포인트의 d차원 공간:

d=2:    max_dist / min_dist = 폭넓게 변함
d=100:  max_dist / min_dist ~ 1.01
d=1000: max_dist / min_dist ~ 1.001

모든 거리가 거의 같아지면 "가장 가까운"이라는 말이 의미를 잃습니다.

문제 2: 부피가 폭발합니다. 데이터의 일정 비율을 포함하는 K개 이웃을 잡으려면 탐색 반경이 특성 공간의 훨씬 큰 부분을 덮어야 합니다. 고차원에서 "이웃"이라는 영역이 공간 대부분을 포함하게 됩니다.

문제 3: 모서리가 지배합니다. d차원 단위 초입방체(Unit hypercube)에서는 대부분의 부피가 중심이 아니라 모서리 근처에 집중됩니다. 초입방체 안에 내접한 구(Sphere)는 d가 커질수록 전체 부피에서 차지하는 비중이 사라집니다.

실무적으로 KNN은 대략 20-50개 특성까지 잘 동작합니다. 그 이상에서는 PCA, UMAP, t-SNE 같은 차원 축소(Dimensionality reduction)를 먼저 적용하거나, 데이터의 낮은 내재 차원(Intrinsic dimensionality)을 활용하는 탐색 자료구조가 필요합니다.

KD 트리(KD-tree): 빠른 최근접 이웃 탐색

전수 탐색(Brute-force) KNN은 질의와 모든 학습 포인트 사이의 거리를 계산합니다. 질의 하나당 O(n * d)입니다. 데이터셋이 커지면 너무 느립니다.

KD-tree는 특성 축을 따라 공간을 재귀적으로 나눕니다. 각 레벨에서 한 차원을 골라 중앙값에서 분할합니다.

graph TD
    R["x1=5.0에서 분할"] -->|"x1 <= 5.0"| L["x2=3.0에서 분할"]
    R -->|"x1 > 5.0"| RR["x2=7.0에서 분할"]
    L -->|"x2 <= 3.0"| LL["잎: 포인트 3개"]
    L -->|"x2 > 3.0"| LR["잎: 포인트 4개"]
    RR -->|"x2 <= 7.0"| RL["잎: 포인트 2개"]
    RR -->|"x2 > 7.0"| RRR["잎: 포인트 5개"]

최근접 이웃을 찾을 때는 질의가 들어갈 잎까지 내려간 뒤, 더 가까운 점이 있을 가능성이 있는 인접 분할 영역(partition)만 되돌아가며 확인합니다.

낮은 차원에서 평균 질의 시간은 O(log n)입니다. 하지만 고차원, 특히 d > 20에서는 역추적(backtracking)으로 제거되는 가지(branch)가 줄어 KD-tree도 O(n)에 가까워집니다.

볼 트리(Ball tree): 중간 차원에서 더 나은 선택

Ball tree는 축 정렬 박스 대신 중첩된 초구(Hypersphere)로 데이터를 나눕니다. 각 노드는 해당 하위 트리(subtree)의 모든 점을 포함하는 공(ball), 즉 중심과 반경을 정의합니다.

KD-tree보다 나은 점은 다음과 같습니다.

• 중간 차원, 대략 50차원까지 더 잘 동작합니다.
• 축에 정렬되지 않은 구조를 더 잘 다룹니다.
• 더 단단한 경계 부피(bounding volume) 덕분에 탐색 중 더 많은 가지를 잘라낼 수 있습니다.

KD-tree와 ball tree는 모두 정확한 알고리즘입니다. 수백만 포인트와 수백 차원 같은 대규모 검색에서는 HNSW, IVF, 곱 양자화(product quantization) 같은 근사 최근접 이웃(Approximate nearest neighbor) 방법을 사용합니다. 이 내용은 Phase 1 Lesson 14와 이후 검색/RAG 관련 lesson에서 다시 연결됩니다.

게으른 학습과 즉시 학습

KNN은 게으른 학습기(Lazy learner)입니다. 학습 시점에는 아무 일도 하지 않고, 모든 일을 예측 시점에 합니다. 선형 회귀, SVM, 신경망 같은 대부분의 알고리즘은 즉시 학습기(Eager learner)입니다. 학습 시점에 무거운 계산을 해서 간결한 모델(compact model)을 만들고, 예측은 빠르게 수행합니다.

게으른 학습은 다음 상황에 적합합니다.

• 데이터셋이 자주 바뀌어 포인트를 추가하거나 제거해야 하는 경우
• 아주 적은 수의 질의에만 예측이 필요한 경우
• 학습 시간을 0에 가깝게 만들고 싶은 경우
• 전수 탐색이 빠를 만큼 데이터셋이 작은 경우

회귀용 KNN

회귀에서는 다수결 투표 대신 K개 이웃의 타깃 값을 평균냅니다.

prediction = (1/K) * sum(y_i for i in K nearest neighbors)

거리 가중치를 쓰면:
prediction = sum(w_i * y_i) / sum(w_i)
where w_i = 1 / distance_i

KNN 회귀는 구간별 상수(Piecewise-constant), 또는 가중치를 사용하면 구간별로 부드러운 예측을 만듭니다. 학습 데이터 범위를 넘어 외삽(Extrapolation)할 수는 없습니다. 학습 타깃이 모두 0과 100 사이였다면 KNN은 200을 예측하지 못합니다.

만들어 보기

Step 1: 거리 함수

L1, L2, 코사인, 민코프스키 거리를 구현합니다. 이는 Phase 1 Lesson 14와 직접 연결됩니다.

import math

def l2_distance(a, b):
    return math.sqrt(sum((ai - bi) ** 2 for ai, bi in zip(a, b)))

def l1_distance(a, b):
    return sum(abs(ai - bi) for ai, bi in zip(a, b))

def cosine_distance(a, b):
    dot_val = sum(ai * bi for ai, bi in zip(a, b))
    norm_a = math.sqrt(sum(ai ** 2 for ai in a))
    norm_b = math.sqrt(sum(bi ** 2 for bi in b))
    if norm_a == 0 or norm_b == 0:
        return 1.0
    return 1.0 - dot_val / (norm_a * norm_b)

def minkowski_distance(a, b, p=2):
    if p == float('inf'):
        return max(abs(ai - bi) for ai, bi in zip(a, b))
    return sum(abs(ai - bi) ** p for ai, bi in zip(a, b)) ** (1 / p)

Step 2: KNN 분류기와 회귀기

K, 거리 척도, 선택적 거리 가중치를 설정할 수 있는 전체 KNN을 만듭니다.

class KNN:
    def __init__(self, k=5, distance_fn=l2_distance, weighted=False,
                 task="classification"):
        self.k = k
        self.distance_fn = distance_fn
        self.weighted = weighted
        self.task = task
        self.X_train = None
        self.y_train = None

    def fit(self, X, y):
        self.X_train = X
        self.y_train = y

    def predict(self, X):
        return [self._predict_one(x) for x in X]

Step 3: 효율적인 탐색을 위한 KD 트리(KD-tree)

각 차원의 중앙값을 기준으로 재귀적으로 분할하는 KD-tree를 직접 만듭니다.

class KDTree:
    def __init__(self, X, indices=None, depth=0):
        # 데이터를 재귀적으로 분할(partition)합니다.
        self.axis = depth % len(X[0])
        # 현재 축의 중앙값을 기준으로 분할합니다.
        ...

    def query(self, point, k=1):
        # 잎까지 내려간 뒤 되돌아가며 탐색(backtrack)합니다.
        ...

전체 보조 메서드(helper method)와 데모(demo)는 code/knn.py에서 확인합니다.

Step 4: 특성 스케일링

KNN은 거리 기반 방법이므로 특성 크기에 민감합니다. 0에서 1000까지 움직이는 특성은 0에서 1까지 움직이는 특성보다 거리를 지배합니다.

def standardize(X):
    n = len(X)
    d = len(X[0])
    means = [sum(X[i][j] for i in range(n)) / n for j in range(d)]
    stds = [
        max(1e-10, (sum((X[i][j] - means[j]) ** 2 for i in range(n)) / n) ** 0.5)
        for j in range(d)
    ]
    return [[((X[i][j] - means[j]) / stds[j]) for j in range(d)] for i in range(n)], means, stds

사용하기

scikit-learn에서는 다음처럼 사용할 수 있습니다.

from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline

clf = Pipeline([
    ("scaler", StandardScaler()),
    ("knn", KNeighborsClassifier(n_neighbors=5, metric="euclidean")),
])
clf.fit(X_train, y_train)
print(f"정확도: {clf.score(X_test, y_test):.4f}")

scikit-learn은 데이터셋이 충분히 크고 차원이 충분히 낮으면 KD-tree나 ball tree를 자동으로 사용합니다. 고차원 데이터에서는 전수 탐색으로 대체(fallback)합니다. 이 동작은 algorithm 파라미터로 제어할 수 있습니다.

대규모 최근접 이웃 검색, 예를 들어 수백만 개 벡터에는 FAISS, Annoy, 또는 벡터 데이터베이스를 사용합니다.

import faiss

index = faiss.IndexFlatL2(dimension)
index.add(embeddings)
distances, indices = index.search(query_vectors, k=5)

연습문제

1. 3개 클래스를 가진 2D 데이터셋에서 KNN 분류를 구현합니다. K=1, K=5, K=15, K=N에 대해 결정 경계를 그립니다. 과적합에서 과소적합으로 이동하는 과정을 관찰합니다.

2. 2, 5, 10, 50, 100, 500차원에서 무작위 포인트 1000개를 생성합니다. 각 차원에서 최대 쌍별 거리(pairwise distance)와 최소 쌍별 거리의 비율을 계산합니다. 차원에 따른 비율을 그려 차원의 저주를 시각화합니다.

3. TF-IDF 벡터를 사용하는 텍스트 분류 문제에서 L1, L2, 코사인 거리를 비교합니다. 어떤 척도가 가장 좋은 정확도를 내나요? 텍스트에서 코사인이 좋은 이유를 설명합니다.

4. KD-tree를 구현하고 2D, 10D, 50D에서 1k, 10k, 100k 포인트에 대한 질의 시간을 전수 탐색과 비교합니다. KD-tree가 전수 탐색보다 느려지는 차원은 어디인가요?

5. y = sin(x) + noise에 대해 가중 KNN 회귀기를 만듭니다. K=3, 10, 30에서 비가중 KNN과 비교합니다. 특히 큰 K에서 가중치가 더 부드러운 예측을 만드는지 확인합니다.

핵심 용어

더 읽을거리

• Cover & Hart: Nearest Neighbor Pattern Classification (1967) — KNN의 기반 논문입니다.
• Friedman, Bentley, Finkel: An Algorithm for Finding Best Matches in Logarithmic Expected Time (1977) — KD-tree 원 논문입니다.
• Beyer et al.: When Is "Nearest Neighbor" Meaningful? (1999) — 최근접 이웃과 차원의 저주를 형식적으로 분석합니다.
• scikit-learn Nearest Neighbors documentation — 알고리즘 선택과 실무 사용법을 볼 수 있습니다.
• FAISS: A Library for Efficient Similarity Search — 대규모 근사 최근접 이웃 검색 라이브러리입니다.