"ML 기초 학습 (2/9) — 이웃 알고리즘: k-NN의 단순함과 함정"

머신러닝에서 가장 단순한 아이디어 하나만 들고 가자: 새 입력의 답은, 가장 가까운 친구들의 답을 평균낸 값이다. 이 한 문장이 $k$-최근접 이웃(k-NN) 알고리즘 전체다. 단순한 만큼 ML의 핵심 개념(편향-분산, 차원의 저주, 비모수 모델, 결정경계)이 가장 적나라하게 드러난다.

0. 학습 목표

$k$-NN의 분류와 회귀 규칙을 식과 한 문장으로 각각 쓸 수 있다.
유클리드·맨해튼·코사인 거리의 정의와 어떤 상황에서 무엇이 적합한지 설명한다.
$k$ 값이 작을 때와 클 때 편향-분산 측면에서 무엇이 어떻게 변하는지 그림과 식으로 설명한다.
차원의 저주(curse of dimensionality) 가 거리 기반 방법에 어떻게 영향을 주는지 식 한 줄로 설명한다.
sklearn으로 k-NN을 학습하고, k와 거리 메트릭을 grid search로 고를 수 있다.
KD-tree·Ball-tree·brute-force 세 가지 백엔드의 시간 복잡도 차이를 안다.

1. 핵심 요약

$k$-NN은 학습이 없다. 데이터 자체를 저장하고, 예측 시점에 가장 가까운 $k$개 이웃의 정답을 모아 결정한다.
분류에서는 다수결, 회귀에서는 평균이 기본이다.
매우 단순하지만, ML의 거의 모든 핵심 함정을 보여준다: 거리 정의 문제, 스케일 민감성, 차원의 저주, 편향-분산 트레이드오프.
백엔드는 KD-tree(저차원), Ball-tree(중간 차원), brute-force(고차원, 작은 $n$) 중 자동 선택.
베이즈 분류기 (이론적 최적) 의 오차의 2배 이하라는 Cover & Hart 1967의 고전적 결과를 갖고 있다.

2. 직관 — 거리만 잘 재면 답이 보인다

2.1 한 줄 알고리즘

새로운 입력 $x$가 들어왔다. "가장 비슷한 과거 사례들을 찾아서 그들이 했던 답을 모은다." 이게 전부다.

분류라면 $k$명 이웃에게 투표시킨다 — 다수가 고른 클래스가 답.

회귀라면 $k$명 이웃의 출력을 평균낸다.

훈련 단계: 데이터를 저장만 한다. 학습이라 부를 게 없다.
예측 단계: 거리를 모두 계산해 가장 가까운 k개를 찾고, 그들의 답을 모은다.

이 "학습 없이 데이터 자체를 모델로 쓰는" 성격을 비모수(non-parametric) 라고 부른다. 모델 파라미터가 데이터 크기에 비례해 증가한다.

2.2 왜 이 단순한 알고리즘으로 시작하는가

세 가지 이유다.

베이스라인. 어떤 ML 문제를 만나도, k-NN은 첫 번째 비교군이다. k-NN보다 못한 정교한 모델은 의심해야 한다.
개념 압축. 거리·스케일·차원·바이어스·분산 같은 핵심 개념이 한 모델 안에 다 들어 있다.
시각적이다. 결정경계를 2D 그림으로 그려 보면 $k$의 효과가 즉시 보인다.

2.3 역사

Fix, E. & Hodges, J. L. Discriminatory Analysis – Nonparametric Discrimination: Consistency Properties (1951). 미국 USAF 보고서. k-NN의 통계학적 토대.
Cover, T. M. & Hart, P. E. Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), 21–27 (1967). 가장 자주 인용되는 정리: 1-NN 오차율은 베이즈 최적 오차율의 두 배를 넘지 않는다.

이 1967년 결과가 보여주는 것은 놀랍게도 단순한 알고리즘이 이론적 하한과 거의 닿아 있다는 사실이다.

3. 정의와 표기

3.1 거리 (distance)

두 벡터 $x, x' \in \mathbb{R}^{d}$ 사이 거리 $d(x, x')$는 다음 중 하나를 쓴다.

$$ d_{\text{Euclidean}}(x, x') = \sqrt{\sum_{j=1}^{d} (x_j - x'_j)^2} $$

$$ d_{\text{Manhattan}}(x, x') = \sum_{j=1}^{d} |x_j - x'_j| $$

$$ d_{\text{Minkowski}, p}(x, x') = \Big(\sum_{j=1}^{d} |x_j - x'_j|^{p}\Big)^{1/p} $$

$p=1$이면 맨해튼, $p=2$이면 유클리드, $p \to \infty$이면 체비셰프($\max_j |x_j - x'_j|$).

방향 정보가 중요한 경우 코사인 유사도의 음을 거리로 쓴다.

$$ d_{\cos}(x, x') = 1 - \frac{x \cdot x'}{\|x\| \, \|x'\|} $$

텍스트 임베딩이나 LLM 표현 공간에서는 코사인이 표준이다.

3.2 k-NN 분류 규칙

이웃 집합 $\mathcal{N}_k(x) = \{x_{(1)}, \dots, x_{(k)}\}$는 훈련 데이터 중 $x$에서 가장 가까운 $k$개다. 분류 예측은

$$ \hat{y}(x) = \arg\max_{c \in \{1,\dots,C\}} \sum_{i \in \mathcal{N}_k(x)} \mathbb{1}[y_i = c] $$

가중 k-NN은 거리 역수를 가중치로 쓴다.

$$ \hat{y}(x) = \arg\max_{c} \sum_{i \in \mathcal{N}_k(x)} \frac{1}{d(x, x_i)} \, \mathbb{1}[y_i = c] $$

3.3 k-NN 회귀 규칙

$$ \hat{y}(x) = \frac{1}{k} \sum_{i \in \mathcal{N}_k(x)} y_i $$

또는 거리 가중 평균

$$ \hat{y}(x) = \frac{\sum_{i \in \mathcal{N}_k(x)} w_i \, y_i}{\sum_{i \in \mathcal{N}_k(x)} w_i}, \quad w_i = \frac{1}{d(x, x_i) + \epsilon} $$

4. 수식과 메커니즘 — 편향, 분산, 차원

4.1 $k$와 편향-분산 트레이드오프

$k=1$: 모델이 훈련 데이터에 완벽하게 적합된다. 훈련 오차 = 0. 하지만 새 데이터가 조금만 흔들려도 예측이 따라 흔들린다 → 분산 높음, 편향 낮음.

$k=N$ (전체 데이터): 어떤 입력에 대해서도 같은 다수 클래스를 답한다. 편향 높음, 분산 낮음.

$k$는 두 극단 사이를 보간한다. 회귀에서 평균을 취하면 분산은 $1/k$에 비례해 감소한다(독립 가정 시).

$$ \mathrm{Var}\Big(\frac{1}{k}\sum_{i=1}^{k} y_i\Big) = \frac{\sigma^2}{k} $$

$k$를 늘릴수록 분산은 $1/k$에 비례해 떨어지지만, 멀리 있는 이웃까지 끌어들이므로 편향은 올라간다. 최적 $k$는 데이터의 잡음 크기와 결정경계 곡률에 의존한다.

4.2 결정경계의 모양

k-NN은 Voronoi 분할 위에서 동작한다. 훈련점 하나가 자기 영역을 갖고, 그 영역 안 점은 그 훈련점의 라벨을 (1-NN이면) 그대로 받는다.

    .   .   .
  + |   | + |     ← 각 cell은 한 훈련점의 영역
    .   .   .
  - | + | + |
    .   .   .

$k$가 커지면 경계가 매끄러워진다. $k=1$이면 경계가 들쭉날쭉, $k=N$이면 경계가 사라진다(전체가 다수 클래스).

4.3 차원의 저주

$d$차원 공간에서 모든 점이 비슷한 거리에 있게 되는 현상이다.

가장 가까운 점과 가장 먼 점 사이 거리의 비율이 어떻게 변하는지 보자. $d$차원 단위 큐브 $[0,1]^d$ 위에 $n$개 점을 무작위로 뿌리고 원점에서 거리를 잰다. $d$가 커지면

$$ \frac{\text{max distance} - \text{min distance}}{\text{min distance}} \;\xrightarrow{d \to \infty}\; 0 $$

즉 모든 이웃이 똑같이 멀다. "가장 가까운"이라는 개념이 무너진다.

직관적 예: $d$차원 큐브 부피를 90%까지 채우려면 한 변의 길이가 $0.9^{1/d}$이다. $d=10$이면 0.99, $d=100$이면 0.999. 고차원에서 부피의 거의 전부가 표면 근처에 있다는 사실이 거리 기반 방법을 무너뜨린다.

대처법:

차원 축소: PCA, 오토인코더로 $d$를 줄인다.
피처 선택: 의미 있는 피처만 골라 쓴다.
거리 학습: Mahalanobis 거리, large-margin nearest neighbor.
임베딩 공간 사용: 텍스트는 $d=768$이 흔하지만, 임베딩이 잘 학습돼 있으면 코사인 거리는 여전히 의미가 있다.

4.4 스케일 민감성

피처별 단위가 다르면 (예: 키 cm, 몸무게 kg) 큰 값의 피처가 거리에 지배적이 된다. 키 1cm 차이가 몸무게 1kg 차이보다 거리에 큰 기여를 한다.

해결: StandardScaler로 정규화 (평균 0, 분산 1). 1편의 Pipeline 패턴 그대로 적용한다.

5. 다이어그램 — k가 바꾸는 것

추가 시각:

k=1:    +  -  +  -  +     경계: 들쭉날쭉
            ↕
k=5:    +     -     +     경계: 매끄럽다
            ↕
k=N:    모두 +(다수클래스)  경계 없음

6. 원리 워크스루 — k-NN 한 줄을 해부하다

알고리즘 자체는 사실 두 줄이다 — "거리를 재고, 가장 가까운 $k$개의 다수결을 답으로 한다". 그 두 줄이 학습하지 않는 모델이라는 깊은 의미를 가진다는 점이 학습 가치다.

6.1 표준 호출 한 줄

from sklearn.neighbors import KNeighborsClassifier
clf = KNeighborsClassifier(n_neighbors=5, weights="distance").fit(X_tr, y_tr)

이 한 줄에 학습 단계가 사실상 없다. fit은 단지 훈련 데이터를 인덱스에 저장할 뿐 — 모델 파라미터를 찾는 게 아니라 예측 시점에 쿼리당 $O(nd)$ 거리 계산을 한다. 이것이 비모수 (non-parametric) 모델의 정의이고, k-NN이 모든 ML 강의 첫 자리에 오는 이유다.

6.2 거리 메트릭은 도메인 결정이다

무엇을 비교하는가 Minkowski 거리 $d_p(x, x') = \big(\sum_j |x_j - x'_j|^p\big)^{1/p}$에서 $p=2$는 유클리드, $p=1$은 맨해튼, $p \to \infty$는 체비셰프. 매개변수 $p$가 공간의 형태를 정의한다.

왜 둘 다 살아남았는가 - 유클리드 ($p=2$): 등방적(isotropic), 회전 불변, 미분 가능. 신경망 임베딩의 기본. - 맨해튼 ($p=1$): 격자 구조에 적합, 이상치에 더 강건. 도시 거리·체스보드 거리. - 코사인: 방향만 비교 (크기 무시). 텍스트 임베딩에서 사실상 표준 — 단어 빈도의 절대값이 아니라 분포가 중요하기 때문.

거리 선택은 "두 점이 비슷하다는 게 무엇이냐"는 도메인 질문에 답하는 일이다. 7.3에서 거리를 학습으로 정한다는 발상으로 이어진다.

6.3 차원의 저주 — 거리가 의미를 잃는 자리

관찰되는 패턴 $d$차원 유닛 큐브에서 무작위로 1000개 점을 뽑으면, 임의 쿼리에서 최근접 거리와 최원 거리의 비율 $(\max - \min)/\min$이 다음과 같이 변한다.

$d$	2	5	10	50	100	500	1000
비율	14.2	4.7	2.6	0.99	0.68	0.29	0.21

의미 $d = 1000$이면 가장 가까운 점과 가장 먼 점의 거리 차이가 최소 거리의 20% 수준 — 즉 "가까운 점"이라는 개념이 사실상 사라진다. k-NN의 다수결이 무작위 추첨에 수렴한다 (Beyer et al. 1999, When Is "Nearest Neighbor" Meaningful?).

다음 단계 6편 신경망의 표현 학습 (representation learning) 이 이 한계의 정면 답이다. 원본 공간이 1000차원이어도, 학습된 임베딩이 의미 있는 64~512차원으로 압축되면 거리가 다시 살아난다. 8편 어텐션·임베딩이 정확히 이 작업이다.

6.4 결정경계 시각화 (개념)

무엇을 보는 것인가 2차원 평면에 학습 데이터를 점으로 흩뿌리고, 평면 전체를 촘촘한 그리드(격자)로 채운 뒤, 각 격자 점에 k-NN을 적용해 예측 클래스를 색으로 칠한다. 색이 바뀌는 선이 곧 결정경계 (decision boundary) 다. 모델이 두 클래스를 어떻게 가르는지 한 장의 그림으로 드러난다.

$k$가 바꾸는 것 - $k=1$: 경계가 들쭉날쭉(jagged)하다. 훈련점 하나가 자신의 보로노이 셀(Voronoi cell)을 그대로 결정경계로 만들기 때문이다. 이상점 한 개가 주변 셀 전체를 뒤집을 수 있다. 분산(variance)이 크다. - $k=10$: 경계가 매끄러워(smooth)진다. 다수결이 이상점의 영향을 약화시킨다. 편향(bias)이 커지고 분산은 줄어든다. - $k=n$ (전체): 모든 점에서 가장 많은 클래스가 답. 결정경계가 사라지고 모델은 "데이터"를 잊고 평균에 수렴한다.

왜 이 시각화가 학습 도구로 강력한가 편향-분산 트레이드오프는 식만 보면 추상적이다. $k$를 1·5·20·100으로 바꿀 때 경계가 어떻게 변하는지 한 번 보면, 같은 언어가 이후 모든 분류 모델 — 로지스틱 회귀의 직선 경계, 결정트리의 계단형 경계, SVM의 마진 경계, 신경망의 곡선 경계 — 에 그대로 적용된다. sklearn 공식 예제 plot_classification.html이 이 시각화의 표준 패턴(meshgrid + contourf)을 보여준다.

한계와 다음 단계 3차원 이상에서는 결정경계를 직접 볼 수 없다. 우회로는 두 가지다. (1) PCA·t-SNE·UMAP으로 2차원에 투영한 뒤 그 위에 경계를 근사한다. (2) 일부 변수를 고정하고 나머지 두 변수만 슬라이스한다. 다음 편 선형회귀에서는 결정경계 대신 회귀선(regression line) 으로 같은 직관을 옮겨 본다. 이산적인 클래스가 연속적인 $y$로 바뀔 뿐, 모델이 그리는 "예측 표면(prediction surface)"이라는 본질은 같다.

7. 변형과 사례 — k-NN이 임베딩 검색의 뿌리가 되는 자리

단순한 알고리즘이 왜 2026년에도 살아 있는지의 답은, 이웃 검색 그 자체가 추천·검색·RAG의 핵심 연산이기 때문이다.

7.1 거리 가중 (Distance-Weighted k-NN)

무엇이 바뀌나 모든 이웃을 동등하게 다루는 대신, 거리의 역수로 가중한다 (weights="distance"). 가중치 $w_i = 1/(d_i + \epsilon)$로 멀리 있는 이웃의 발언권을 줄인다.

왜 등장했나 $k$ 고정 시 $k$번째 이웃이 사실상 상관없는 거리에 있을 수 있다. 다수결이 그 점에 동등한 한 표를 주면 결정경계가 거칠어진다. Dudani 1976 The Distance-Weighted k-NN Rule 이후 표준이 되었다.

무엇이 가능해졌나 결정경계가 부드러워지고, 동률(tie) 처리가 자연스러워진다. 회귀 버전에서는 더 의미 있다 — 회귀값이 가까운 점들에 비례해 weighted average로 계산되므로 연속성이 보장된다.

한계와 다음 단계 가중 함수 자체는 여전히 고정된 식이다. 학습으로 가중치를 정하면 7.3 metric learning, 더 일반화하면 신경망의 attention이다.

7.2 반지름 기반 (Radius Neighbors)

무엇이 바뀌나 $k$를 고정하지 않고 반경 $r$ 안의 모든 이웃을 쓴다 (RadiusNeighborsClassifier). 이웃 수가 가변.

왜 등장했나 밀도가 불균일한 데이터에서는 $k$ 고정이 문제다. 데이터가 밀집한 곳에서는 $k=5$면 충분하지만, 희소한 곳에서는 $k=5$도 너무 멀리까지 잡아 의미가 사라진다.

무엇이 가능해졌나 - 지리정보 (GIS) — "반경 1km 안의 모든 매장" 같은 자연스러운 쿼리. - 이상치 탐지의 LOF (Local Outlier Factor) — 한 점의 지역 밀도를 반경 기반으로 측정. - 클러스터링의 DBSCAN — 핵심 점의 정의가 반경 $\epsilon$ 안에 최소 $\text{minPts}$.

한계와 다음 단계 $r$ 선택이 $k$ 선택만큼 어렵다. 그리고 극희소 영역에서는 이웃 수가 0이 되어 예측 불가.

7.3 학습된 거리 (Metric Learning)

무엇이 바뀌나 Mahalanobis 거리 $d(x, x') = \sqrt{(x - x')^{\top} M (x - x')}$의 $M$을 학습으로 찾는다. 같은 클래스는 가깝게, 다른 클래스는 멀게 만드는 $M$을 데이터에서 추출.

왜 등장했나 유클리드는 모든 축에 같은 가중을 준다. 그러나 실제로는 어떤 축이 더 클래스를 구분하는지 데이터가 알려준다. Weinberger & Saul 2009 Distance Metric Learning for Large Margin Nearest Neighbor Classification (LMNN)이 이 발상의 대표.

무엇이 가능해졌나 - 얼굴 인식의 임베딩: FaceNet (Schroff et al. 2015)이 같은 사람 가까이, 다른 사람 멀리를 학습. - 검색의 의미 매칭: Sentence-BERT (Reimers & Gurevych 2019)가 문장 유사도를 학습된 거리로. - 추천의 user/item 임베딩: 같은 취향끼리 가깝게.

한계와 다음 단계 $M$ 한 행렬로 표현되는 거리는 선형 변환 뿐이다. 비선형 변환은 신경망 임베딩(6편) 으로 자연스럽게 일반화 — 그리고 그 결과를 다시 k-NN으로 검색하는 패턴이 RAG의 본체다.

7.4 어디서 살아남았는가 — 현대 ML의 이웃 검색

분야	활용	핵심 도구
추천 시스템	user-user / item-item 이웃	협업 필터링
이상치 탐지	LOF — 지역 밀도 기반	sklearn `LocalOutlierFactor`
이미지 검색	임베딩 후 ANN	FAISS, ScaNN
의료 진단	비슷한 케이스 매칭	EMR + clinical embeddings
RAG	임베딩 공간 의미 검색	OpenAI text-embedding-3, Cohere reranker
표절 탐지	문장 임베딩 후 cos-sim	Semantic Scholar API

핵심 시각: 지난 10년의 ML 진보는 "k-NN을 어디서 하느냐"의 진보로 요약할 수 있다. 원본 픽셀에서 → 학습된 임베딩 위에서. 알고리즘은 거의 그대로다.

7.5 대규모 데이터 — Brute Force에서 ANN으로

100만 개 벡터에서 매 쿼리 $O(nd)$ 거리 계산은 비현실적이다. 근사 최근접 이웃 (Approximate Nearest Neighbor, ANN) 가 답. - KD-tree (저차원, $d < 20$): 공간을 재귀 분할. - Ball-tree: 거리 계산 횟수 줄임. - LSH (Locality-Sensitive Hashing): 비슷한 점을 같은 버킷에. - HNSW (Hierarchical Navigable Small World, Malkov 2018): 그래프 기반, 현재 표준. - IVF + PQ (FAISS): 클러스터링 + 양자화로 메모리·속도 둘 다 최적.

ANN은 정확한 k-NN의 99.5% 정확도를 수십~수백 배 빠르게 달성. RAG 시스템이 ms 단위 응답을 내는 비결.

8. 한계와 실패 양상 — k-NN의 한계가 ML의 다음 100년을 정했다

8.1 예측 시간이 $O(nd)$ — 학습은 무료, 추론은 비싸다

왜 본질적 한계인가 k-NN은 학습 시점에 아무것도 하지 않는 모델이다. 모든 계산이 예측 시점으로 미뤄진다. 데이터가 100만 개면 매 쿼리가 100만 번의 거리 계산.

어떻게 진단하는가 실시간 응답이 필요한 서비스에서 latency 측정 — 쿼리당 100ms 이상이면 brute-force는 부적합.

다음 단계 ANN (HNSW, FAISS, ScaNN) — 정확도 99.5%로 100배 빠르게. 또는 모델 파라미터화 (선형회귀·신경망) — 학습 시간에 계산을 몰아넣고 추론은 $O(d)$로.

8.2 메모리 — 모든 훈련 데이터를 들고 있어야 함

왜 본질적 한계인가 파라미터 모델은 학습 후 데이터를 버려도 된다 — 가중치만 들고 있으면 된다. k-NN은 그게 불가능 — 훈련 데이터 자체가 모델이다. 100만 샘플 × 1000 피처 × 4 byte = 4GB 메모리.

어떻게 진단하는가 배포 환경의 RAM 한계 + 모델 크기 ≈ 4GB를 비교.

다음 단계 프로토타입 선택 (NCA, condensed k-NN), 양자화 (FAISS의 Product Quantization), 또는 임베딩 차원 축소 후 k-NN.

8.3 스케일 민감성 — 미터와 mm가 같은 가중을 받는다

왜 본질적 한계인가 거리 계산에서 한 피처의 단위가 1000배 크면, 그 피처가 결과를 결정한다. 신장(cm)과 체중(kg)을 함께 쓰면 cm 값이 작아 무시되고 kg만 본 결과를 낸다.

어떻게 진단하는가 원본 데이터의 피처별 std를 확인. 차이가 10배 이상이면 즉시 정규화 필수.

다음 단계 StandardScaler (z-score) 또는 RobustScaler (median + IQR) 를 Pipeline에 넣어 항상 사용. 7.3의 metric learning이 이 문제의 더 일반적 답.

8.4 결측치 — 거리 정의가 깨진다

왜 본질적 한계인가 np.nan이 한 차원에라도 있으면 $(x_j - x'_j)^2$가 NaN이 되어 거리 전체가 무너진다. 거리 기반 알고리즘의 구조적 약점.

어떻게 진단하는가 X.isna().any() — 단 하나의 NaN도 허용 안 됨.

다음 단계 사전 imputation (평균·중앙값·k-NN imputer). 또는 부분 거리 — 결측 아닌 차원만으로 계산 후 보정.

8.5 클래스 불균형 — 다수 클래스가 이웃을 점령한다

왜 본질적 한계인가 양성 비율 1%에서 $k=5$면 이웃 5개 중 약 0.05개만 양성. 다수결로 항상 음성 답. 모델이 양성을 못 본다.

어떻게 진단하는가 classification report의 양성 클래스 recall이 0에 가까움.

다음 단계 가중 k-NN, 오버샘플링 (SMOTE), 또는 다수 클래스 언더샘플링. 1편 7.1의 클래스 불균형 지표 논의와 동일한 패턴이 여기서도.

8.6 차원의 저주 — 거리가 의미를 잃는다

왜 본질적 한계인가 6.3의 표대로 $d \to \infty$에서 모든 점이 거의 같은 거리에 있게 된다. 다수결이 무작위 추첨에 수렴.

어떻게 진단하는가 $d > 50$ 이상 + 데이터가 균일하게 흩어진 경우.

다음 단계 표현 학습 (representation learning) — PCA, autoencoder, 신경망 임베딩. 1000차원 픽셀 → 의미 있는 128차원 임베딩. 6·8편의 전체 동기.

한계가 알려주는 흐름

k-NN의 6가지 한계는 ML의 다음 100년을 정확히 압축한다: - $O(nd)$ 추론 → 파라미터 모델 (3편 선형회귀, 6편 신경망) - 메모리 → 가중치 압축·양자화 (9편 로컬 LLM) - 스케일 민감 → 정규화·BatchNorm (5편 정규화, 7편 학습 기법) - 결측치 → imputation 모델 - 클래스 불균형 → 비용 민감 학습 (1편 7.1) - 차원의 저주 → 표현 학습 (6편 표현, 8편 임베딩)

k-NN을 이해한다는 것은 이후 모든 ML 발전의 동기를 한 모델로 압축해 본다는 의미다.

9. 정리된 결론 — 보지 않고 답해 보라

이 글이 답한 핵심 질문 5개. 먼저 답을 가린 채로 한 줄로 답해 본 뒤 정답과 비교.

Q1. k-NN의 `fit`은 무엇을 하는가? 왜 비모수 모델로 분류되는가?

정답 fit은 훈련 데이터를 인덱스에 저장할 뿐, 파라미터를 찾지 않는다. 예측 시점에 매번 거리 계산. 왜 학습된 파라미터(가중치) 없이 데이터 자체가 모델이라는 점이 비모수의 정의다. 추론 비용 $O(nd)$, 메모리 비용 데이터 전체. (본문 6.1, 8.1, 8.2)

Q2. $k$를 1에서 $n$까지 키우면 편향-분산은 어떻게 변하는가?

정답 $k$ 작음 → 분산 큼·편향 작음. $k$ 큼 → 편향 큼·분산 작음. $k = n$ → 항상 최빈 클래스 (편향 극대). 왜 더 많은 이웃을 평균하면 노이즈가 평활되어 분산이 줄지만, 결정경계가 단순해져 편향이 늘어난다. 1편 1.3 편향-분산 분해의 가시화. (본문 6.4)

Q3. 1000차원 데이터에서 k-NN이 실패하는 이유는?

정답 차원의 저주 — 가장 가까운 점과 가장 먼 점의 거리가 거의 같아져 "가까움"이 의미를 잃는다. 왜 $(\max - \min)/\min$ 비율이 $d=2$에서 14, $d=1000$에서 0.2로 떨어진다 (Beyer et al. 1999). 답은 표현 학습 — 신경망 임베딩으로 의미 있는 64~512차원으로 압축. (본문 6.3, 8.6)

Q4. RAG (Retrieval-Augmented Generation)가 본질적으로 k-NN의 변형이라고 말할 수 있는 이유는?

정답 RAG의 검색 단계는 "쿼리 임베딩에 가장 가까운 $k$개의 문서 임베딩을 가져온다" — 임베딩 공간 위의 k-NN. 왜 ML 진보의 본체는 알고리즘이 아니라 어디서 k-NN을 하느냐다. 원본 단어 빈도에서 → 학습된 임베딩 공간으로. 대규모는 ANN (FAISS, HNSW) 으로 100배 빠르게. (본문 7.4, 7.5)

Q5. `StandardScaler`를 생략하고 키(cm)와 체중(kg)으로 k-NN을 돌리면 무슨 일이 벌어지나?

정답 cm 값(예: 170)이 kg 값(예: 65)보다 크니까 거리가 거의 키만으로 결정된다. 모델이 체중을 무시한다. 왜 거리 계산이 등방적이라 단위 차가 그대로 가중 차로 반영된다. 정규화는 옵션이 아니라 필수. metric learning이 한 단계 더 일반화된 답. (본문 6.2, 8.3)

4~5개를 한 줄로 답할 수 있었다면 k-NN의 핵심이 자리잡은 것이다. 막힌 질문은 본문 해당 챕터로 돌아가 재독.

10. 추가 학습

1차 자료

Cover, T. M., Hart, P. E. Nearest Neighbor Pattern Classification. IEEE TIT 13(1), 21–27 (1967). — 1-NN 오차 한계 정리.
Fix, E., Hodges, J. L. Discriminatory Analysis – Nonparametric Discrimination: Consistency Properties (1951). USAF School of Aviation Medicine, Report Number 4. — k-NN의 통계적 토대.
Weinberger, K. Q., Saul, L. K. Distance Metric Learning for Large Margin Nearest Neighbor Classification. JMLR 10 (2009): 207–244. — 학습된 거리.

공식 docs

sklearn Nearest Neighbors: https://scikit-learn.org/stable/modules/neighbors.html
KD-tree / Ball-tree 알고리즘 설명: https://scikit-learn.org/stable/modules/neighbors.html#brute-force

보조 자료

Hastie, Tibshirani, Friedman. The Elements of Statistical Learning. 2.3장, 13장.
Aggarwal, C. C. Outlier Analysis. 2nd ed., Springer 2017. LOF 등 k-NN 기반 이상치 탐지.

다음 편(3/9)에서는 선형 회귀를 다룬다. 데이터에 직선(또는 초평면)을 긋는 가장 오래된 방법인데, 최소제곱·정규방정식·경사하강이 한 자리에서 만난다. ML 모든 학습 알고리즘이 결국은 "어떤 식으로든 손실을 최소화한다"는 사실이 식 하나에서 손에 잡힌다.

시리즈 전체 안내: 시리즈 목차