K-최근접 이웃(KNN): 가장 직관적인 분류 알고리즘

지난 글에서 같은 선형 결합에 무엇을 씌우느냐가 회귀와 분류를 가른다는 것을 봤다. 이번에는 전혀 다른 접근인 K-최근접 이웃을 다룬다. KNN은 "비슷한 것끼리는 비슷한 레이블을 가진다"는 가정 하나로 돌아간다. 최적화도 없고 학습할 파라미터도 없다. 새 점이 들어오면 훈련 데이터 중 가장 가까운 K개를 찾아 다수결로 답한다. 그 단순함이 KNN을 입문용으로 만들지만, 실제로 쓰려면 거리·스케일·차원·자료구조라는 네 가지를 다 손봐야 한다. 이 글은 그 넷을 차례로 본다.

게으른 학습기

저장뿐인 학습

대부분의 모델에서 fit은 무거운 일이고 predict는 가벼운 일이다. 선형 회귀는 학습에서 계수를 구해 두고 예측에서는 곱셈 몇 번만 한다. KNN은 이 비대칭이 뒤집혀 있다. fit은 훈련 데이터를 그대로 들고 있을 뿐이고, 거리를 재고 이웃을 고르고 다수결을 내는 일은 전부 predict에서 일어난다.

그래서 KNN을 게으른 학습기라고 부른다. 일반화를 미리 해 두지 않고 질문이 들어온 뒤에야 그 질문 주변만 본다. 반대쪽에 있는 것이 부지런한 학습기다 — 학습 때 데이터를 요약해 규칙으로 바꿔 두고 원본은 버린다. 둘의 차이는 계산을 언제 치르느냐이고, KNN은 그 청구서를 예측 시점으로 미뤄 둔 것이다.

이 성질이 늘 손해인 것만은 아니다. 데이터가 계속 들어오는 상황을 생각해 보자. 부지런한 학습기는 새 데이터를 반영하려면 학습을 다시 돌려야 하지만, KNN은 새 행을 저장소에 더하는 것으로 끝난다. 재학습이라는 개념 자체가 없다. 데이터가 자주 바뀌고 양이 작은 자리에서 KNN이 여전히 쓰이는 이유가 이것이다.

O(1)과 O(n·d)

숫자로 보면 미뤄 둔 비용의 크기가 잡힌다. 붓꽃 데이터는 훈련 120행에 특성 4개다. 한 번 예측할 때 거리 계산은 120 × 4, 곧 480번의 곱셈이다. 노트북에서 눈 깜짝할 새다.

같은 계산을 100만 행에 특성 100개짜리 데이터에 대 보자. 한 번 예측에 1억 번이다. 초당 1,000건을 받는 서비스라면 초당 1,000억 번의 거리 계산이 필요하고, 이건 최적화로 줄일 수 있는 규모가 아니다. 학습 비용이 사실상 0이라는 장점과 예측 비용이 데이터 크기에 비례한다는 단점은 같은 성질의 앞뒤다.

모델이 곧 데이터

한 가지가 더 따라온다. KNN에는 학습된 파라미터가 없으므로 배포할 것이 훈련 데이터 자체다. 선형 회귀라면 특성 100개짜리 모델의 무게가 계수 100개, 400바이트다. 같은 문제의 KNN은 100만 행 × 100 특성 × 4바이트로 400MB를 통째로 서버에 올려야 한다.

개인정보가 섞인 데이터라면 문제가 더 커진다. 다른 모델은 학습이 끝나면 원본을 지울 수 있지만 KNN은 못 지운다. 모델을 배포하는 것이 곧 데이터를 배포하는 것이라, 규제를 받는 도메인에서 KNN이 프로토타입 이상으로 안 가는 이유 하나가 여기에 있다.

가까움의 정의

민코프스키 한 식

"가깝다"를 정하는 것이 거리 지표이고, 흔히 쓰는 셋은 사실 한 식의 세 경우다.

$$d_p(x, y) = \left( \sum_i |x_i - y_i|^p \right)^{1/p}$$

p=2면 유클리드 거리로 우리가 자로 재는 직선거리다. p=1이면 맨해튼 거리로 축을 따라서만 움직여 간 길이이고, 격자 도시에서 블록을 도는 거리라 그 이름이 붙었다. p를 무한히 키우면 가장 큰 좌표 차이 하나만 남아 체비쇼프 거리가 된다.

셋의 성격이 갈리는 지점은 큰 차이 하나를 어떻게 대하느냐다. p가 클수록 큰 차이가 합을 지배한다. 그래서 특성 하나가 유독 크게 어긋난 점을 유클리드는 멀다고 보고 맨해튼은 덜 멀다고 본다. 특성마다 오차가 조금씩 있는 데이터에서 맨해튼이 더 안정적이라고 하는 근거가 이것이다.

코사인과 해밍

거리가 언제나 좌표 차이일 필요는 없다. 문서 임베딩처럼 방향이 뜻을 담고 크기는 안 담는 데이터에서는 코사인 유사도를 쓴다. 긴 문서와 짧은 문서가 같은 주제를 다루면 벡터의 길이는 달라도 방향이 비슷한데, 유클리드는 길이 차이에 끌려 둘을 멀다고 본다.

범주형만 있는 데이터에는 해밍 거리가 맞다. 두 행에서 값이 다른 칸의 개수를 세는 것이고, 「빨강/중형/서울」과 「빨강/대형/서울」의 거리는 1이다. 범주를 숫자로 바꿔 유클리드를 쓰면 「서울=1, 부산=2, 대구=3」에서 서울과 대구가 서울과 부산보다 두 배 멀어지는데, 이건 데이터에 없던 순서를 만들어 낸 것이다.

지표를 고르는 순서는 데이터의 종류를 먼저 보는 것이다. 연속형 수치면 유클리드에서 출발하고, 특성마다 단위가 다르고 이상치가 섞여 있으면 맨해튼을 함께 재 보고, 방향이 중요한 벡터면 코사인, 범주형이면 해밍이다. 여러 지표를 교차 검증에 함께 넣어 비교하는 것도 흔한데, 이때 지표를 바꾸면 최적 K도 같이 바뀐다는 점을 잊지 말아야 한다 — 둘은 따로 고를 값이 아니라 같이 고를 값이다.

스케일링

KNN에서 전처리 하나를 고르라면 스케일링이다. 거리 계산에는 단위 개념이 없어서 숫자가 큰 특성이 거리를 통째로 가져간다.

나이와 연봉으로 이웃을 찾는다고 하자. 나이가 30살 차이 나면 제곱이 900이다. 연봉이 1만 원 차이 나면 제곱이 1억이다. 1만 원 차이가 30살 차이보다 11만 배 크게 계산된다. 이 상태의 KNN은 사실상 연봉 하나만 보고 이웃을 고르며, 나이 특성은 넣으나 마나다.

# KNN은 거리 기반 → 스케일링이 선택이 아니라 필수
scaler  = StandardScaler()
X_train = scaler.fit_transform(X_train)
X_test  = scaler.transform(X_test)   # 훈련 통계로 변환

fit_transform은 훈련에만 쓰고 테스트에는 transform만 쓴다는 점도 중요하다. 테스트 데이터로 평균과 표준편차를 다시 재면 평가에 쓸 정보가 변환기로 새어 들어간다.

K 선택

K=1과 K=n

K는 KNN에서 사실상 유일한 손잡이이고, 양 끝을 보면 그 손잡이가 무엇을 움직이는지 알 수 있다.

K=1이면 각 점의 가장 가까운 이웃은 자기 자신이므로 훈련 정확도가 100%다. 그러나 결정 경계가 점 하나하나를 따라 울퉁불퉁해지고, 잘못 라벨링된 점 하나가 자기 주변을 통째로 자기 편으로 만든다. 전형적인 과적합이다. 반대로 K를 훈련 데이터 수만큼 키우면 어떤 점을 물어도 전체 다수결이 나와 언제나 같은 답을 낸다. 극단적인 과소적합이다.

그래서 K는 경계의 거칠기를 정하는 값이다. 작으면 잡음까지 따라 그리고 크면 실제 구조까지 뭉갠다. K = √n을 출발점으로 삼는 어림이 널리 쓰이지만 그건 탐색의 시작점이지 답이 아니다.

교차 검증

K를 고르는 정석은 교차 검증이다. 훈련 데이터를 다섯 조각으로 나눠 네 조각으로 학습하고 한 조각으로 재는 일을 다섯 번 돌려 평균을 내고, K를 1부터 30까지 훑으며 그 평균이 가장 좋은 값을 고른다.

for k in range(1, 31):
    scores = cross_val_score(KNeighborsClassifier(n_neighbors=k),
                             X_train, y_train, cv=5, scoring='accuracy')
    print(k, round(scores.mean(), 4))

곡선을 읽을 때는 꼭짓점 하나에 매달리지 않는 편이 낫다. K=7이 0.953이고 K=9가 0.951이라면 둘의 차이는 검증 조각을 어떻게 나눴느냐로 뒤집힐 수 있는 크기다. 평평한 구간이 보이면 그 구간의 가운데쯤을 고르는 것이 다음 데이터에서도 버틸 확률이 높다.

짝수 K의 동점

이진 분류에서 K를 짝수로 두면 2 대 2 같은 동점이 생긴다. 이때 어떤 답이 나오는지는 알고리즘이 아니라 구현이 정한다 — sklearn은 클래스 배열에서 앞에 오는 쪽을 고르므로, 레이블 이름이 무엇이냐에 따라 예측이 달라진다.

피하는 방법은 둘이다. 이진 분류에서는 K를 홀수로 두거나, 거리 가중을 켜서 동점 자체가 잘 안 생기게 한다. 클래스가 셋 이상이면 홀수도 동점을 막지 못하므로 뒤의 가중 방식이 더 일반적인 해법이다.

동점이 드물다고 넘길 문제도 아니다. 이진 분류에서 K를 6으로 두면 3 대 3이 꽤 자주 나오고, 그 자리가 대개 두 무리의 경계라 예측이 가장 어려운 구간과 정확히 겹친다. 조용히 한쪽으로 기우는 규칙이 하필 가장 민감한 자리에서 작동하는 셈이다.

거리 가중과 결정 경계

uniform과 distance

weights='uniform'은 이웃 K개에 같은 한 표씩 준다. weights='distance'는 거리의 역수를 표의 무게로 삼아 가까운 이웃에 더 큰 발언권을 준다.

한 점에서 갈리는 모습을 보자. K=3이고 이웃이 A 클래스 하나에 거리 0.1, B 클래스 둘에 거리 1.0과 1.2라고 하자. uniform이면 1 대 2로 B가 이긴다. distance면 A가 10이고 B가 1 + 0.83 = 1.83이라 A가 크게 이긴다. 바로 옆에 붙은 점 하나와 멀리 있는 점 둘 중 어느 쪽을 믿을 것이냐의 문제이고, 두 설정은 그 답을 다르게 준다.

경계의 매끄러움

K를 키우면 결정 경계가 매끄러워진다. 이웃을 많이 볼수록 개별 점의 영향이 평균에 묻히기 때문이다. 다만 매끄러워지는 것과 좋아지는 것은 구간이 다르다. 처음에는 잡음이 깎이며 경계가 데이터의 실제 모양에 가까워지다가, 어느 지점을 넘으면 서로 다른 무리 사이의 진짜 경계까지 밀려 뭉개진다.

distance 가중은 이 뭉개짐을 늦춘다. K를 크게 잡아도 멀리 있는 이웃의 표가 작아 경계 근처에서는 여전히 가까운 점들이 결정을 쥐기 때문이다. K를 키우고 싶은데 경계가 흐려지는 것이 걱정이면 먼저 켜 볼 스위치다.

클래스 불균형

KNN이 조용히 실패하는 대표적인 자리가 클래스 불균형이다. 전체의 99%가 정상이고 1%가 이상인 데이터에서 K=20으로 다수결을 하면, 이상 구역 한가운데에 있는 점조차 이웃 20개 중 상당수가 정상으로 채워질 수 있다. 다수 클래스가 공간 전체에 깔려 있으니 어느 자리에서 물어도 표가 그쪽으로 기운다.

대책은 세 갈래다. K를 줄여 아주 가까운 이웃만 보거나, distance 가중으로 멀리 있는 다수 클래스의 표를 깎거나, 표본을 다시 뽑아 비율 자체를 손본다. 어느 쪽이든 정확도 대신 재현율과 정밀도로 평가해야 문제가 보인다 — 전부 정상이라고 답해도 정확도는 99%다.

차원의 저주

거리 비의 수렴

KNN의 근본적인 약점은 차원이다. 특성이 늘어날수록 점들 사이의 거리가 서로 비슷해져, 가장 가까운 점과 가장 먼 점의 차이가 사라진다.

단위 정육면체 안에 점을 균등하게 뿌리고 원점에서의 거리를 재 보면 경향이 보인다. 차원이 2일 때는 가장 먼 점이 가장 가까운 점보다 몇십 배 멀다. 차원이 100이 되면 그 비가 두 배 남짓으로 줄고, 1,000이 되면 거의 1에 붙는다. 차원이 늘면 각 좌표의 차이가 조금씩 더해지는데, 그 합이 대수의 법칙을 타고 모든 점에서 비슷한 값으로 수렴하기 때문이다.

같은 이야기를 부피로 해도 된다. 한 변이 1인 정육면체 안에서 전체 부피의 1%를 차지하는 작은 정육면체의 한 변은 2차원에서 0.1, 10차원에서 0.63, 100차원에서 0.95다. 고작 1%를 담는 상자가 각 축에서 거의 전 구간을 차지한다. 「가까운 이웃 몇 개」를 담을 만한 작은 구역이 더 이상 작지 않다는 뜻이고, 이것이 거리 비가 무너지는 현상의 다른 얼굴이다.

이웃이라는 말의 소멸

거리 비가 1에 가까워지면 "가장 가까운 이웃"이라는 표현이 뜻을 잃는다. 1등 이웃이 100등 이웃보다 5% 더 가까울 뿐이라면, 1등을 고르는 일은 구조를 반영한 선택이 아니라 잡음을 고르는 일에 가깝다.

증상이 잘 안 보인다는 점이 고약하다. 코드는 정상으로 돌고 정확도도 무작위보다는 높게 나온다. 특성을 늘렸는데 성능이 오히려 조금씩 나빠지는 패턴이 보이면 이 자리를 의심해야 한다. 특성을 더 넣는 것이 언제나 이득이라는 직관이 KNN에서는 성립하지 않는다.

차원 줄이기

대책은 차원을 줄이는 것이고 방법은 둘이다. 도메인 지식이나 특성 중요도로 쓸 것만 남기거나, PCA처럼 정보를 압축해 낮은 차원으로 옮기거나다. 앞쪽은 원래 특성의 뜻이 그대로 남아 해석이 쉽고, 뒤쪽은 특성끼리 겹치는 정보를 걷어 내는 데 강하다.

순서를 지키는 것이 중요하다. 차원을 줄인 다음 같은 교차 검증을 다시 돌려 K도 다시 고른다. 공간이 바뀌었으니 예전의 최적 K가 그대로일 이유가 없다. 줄이기 전후의 점수를 나란히 놓고 실제로 나아졌는지 확인하는 것까지가 한 묶음이다.

탐색 자료구조

완전 탐색 · KD 트리 · Ball 트리

기본 동작은 모든 훈련 점과의 거리를 다 재는 완전 탐색이다. 이걸 줄이려고 공간을 미리 쪼개 두는 자료구조가 둘 있다.

KD 트리는 축에 수직인 평면으로 공간을 반씩 갈라 나무를 만든다. 질의가 들어오면 해당 칸만 내려가 보고, 경계 너머에 더 가까운 점이 있을 가능성이 있을 때만 옆 가지를 확인한다. 저차원에서는 대부분의 가지를 건너뛰어 크게 빨라진다. 다만 차원이 20을 넘으면 건너뛸 가지가 거의 없어져 완전 탐색과 비슷해진다.

Ball 트리는 평면 대신 구로 공간을 감싼다. 축에 묶이지 않아 특성끼리 상관이 있는 데이터나 중간 차원에서 KD 트리보다 잘 버틴다. algorithm='auto'는 데이터 크기와 차원을 보고 셋 중 하나를 알아서 고르는 설정이고, 특별한 이유가 없으면 이대로 두는 편이 낫다.

leaf_size

트리를 끝까지 쪼개지 않고 잎에 점 몇 개가 남으면 거기서 멈춘 뒤 그 안은 완전 탐색으로 처리한다. 그 경계가 leaf_size이고 기본값은 30이다.

값을 낮추면 트리가 깊어져 탐색 단계는 줄지만 가지를 오르내리는 비용과 트리가 차지하는 메모리가 는다. 올리면 반대다. 30이 널리 쓰이는 것은 그 언저리에서 두 비용이 균형을 이루기 때문이고, 데이터가 아주 크거나 차원이 높으면 재 보고 조정할 값이다.

조정하기 전에 확인할 것이 있다. leaf_size는 답을 바꾸지 않는다 — 탐색 경로만 달라질 뿐 최종적으로 고르는 이웃 K개는 같다. 그래서 이 값은 정확도 손잡이가 아니라 속도와 메모리 손잡이이고, 교차 검증의 탐색 격자에 넣을 값이 아니라 배포 직전에 프로파일링으로 정할 값이다.

근사 최근접

훈련 점이 수백만을 넘으면 트리로도 감당이 안 된다. 이때 넘어가는 곳이 근사 최근접 탐색이다. FAISS나 HNSW 같은 라이브러리는 정확히 가장 가까운 K개를 보장하지 않는 대신 수십 배에서 수백 배 빠르게 답한다.

포기하는 것이 무엇인지는 분명히 알아야 한다. 1등 이웃이 가끔 2등으로 바뀌는 정도의 오차이고, 추천이나 검색처럼 순위가 조금 흔들려도 되는 곳에서는 사실상 손해가 없다. 반대로 의료 판정처럼 한 건의 이웃 선택이 결과를 뒤집는 곳에서는 그 오차가 그냥 오답이다.

재현율이라는 말로 그 손해를 잰다. 정확한 K개 중 몇 개를 실제로 찾아냈는가이고, 색인 설정을 조이면 재현율이 오르고 속도가 준다. 색인을 도입하는 작업의 절반은 그 곡선에서 우리 서비스가 견딜 수 있는 지점을 고르는 일이다.

KNN 회귀

이웃 평균

KNN은 분류만의 알고리즘이 아니다. 다수결 대신 이웃 K개의 y 평균을 내면 그대로 회귀가 된다. 분류와 회귀를 가르는 것은 이웃을 찾는 부분이 아니라 찾은 뒤 무엇을 하느냐뿐이고, 앞에서 본 거리·스케일·차원 이야기는 한 글자도 안 바뀐다. distance 가중을 켜면 거리의 역수를 무게로 한 가중 평균이 되고, 이쪽이 예측을 한결 매끄럽게 만든다.

uniform으로 두면 예측 곡선이 계단 모양이 된다. 질의 점이 조금 움직여도 이웃 집합이 그대로면 예측이 똑같고, 이웃 하나가 바뀌는 순간 값이 뚝 뛰기 때문이다. 가중을 켜면 이웃이 멀어질수록 표가 서서히 작아져 그 계단이 완만한 기울기로 바뀐다.

외삽 불가

KNN 회귀에는 구조적인 천장과 바닥이 있다. 예측이 이웃들 y의 (가중) 평균이므로 훈련 데이터의 y 범위를 절대 벗어나지 못한다. 훈련에 실린 집값이 1억에서 5억 사이였다면 어떤 입력을 넣어도 예측은 그 안에서 나온다.

선형 회귀와 정확히 반대되는 성질이다. 선형 회귀는 직선을 무한히 연장하므로 훈련 범위 밖에서도 값을 내는데, 그 값이 맞는다는 보장이 없어 위험하다. KNN은 범위를 안 넘는 대신 넘어야 맞는 상황에서 틀린다. 추세가 계속 이어지는 데이터에는 안 맞고, 값이 어떤 구간 안에서만 움직이는 데이터에는 이 성질이 오히려 안전장치가 된다.

벡터 검색과의 연결

KNN을 배워 두면 다른 곳에서 다시 만난다. 벡터 데이터베이스에서 "질문과 가장 비슷한 문서 다섯 개"를 찾는 일은 임베딩 공간에서의 KNN이다. 거리 지표로 코사인을 쓰고, 차원이 수백에서 수천이라 트리 대신 HNSW 같은 근사 탐색을 쓰고, 데이터가 커서 색인을 따로 관리한다 — 이 글에서 본 네 가지 고민이 그대로 반복된다.

그래서 KNN은 오래된 알고리즘이면서 동시에 지금 가장 널리 돌아가는 계산이기도 하다. 모델로는 프로토타입 자리에 머물지만, 그 안의 "가까운 것을 찾는다"는 계산은 검색과 추천의 바닥에 깔려 있다.

---

읽어주셔서 감사합니다. 😊