최근접 이웃

최근접 이웃은 새 데이터의 답을 가장 닮은 기존 데이터에서 빌려 옵니다. 답이 달린 데이터를 모아 둡니다. 물음이 오면 가장 가까운 몇 개의 답을 따릅니다. 가장 닮은 데이터를 찾는 검색 문제도 같은 이름으로 부릅니다. 이 항목은 앞의 예측 방법을 다룹니다.

상세

이 절은 과일을 가르는 작은 예로 최근접 이웃이 답을 내는 과정을 봅니다. 먼저 데이터를 점으로 놓습니다. 닮음은 두 점 사이의 거리로 잽니다.

답을 빌려 오는 예측

머신러닝에서 분류는 데이터가 어느 무리에 드는지 맞히는 일입니다. 메일이 스팸인지 아닌지 가르는 일이 그 예입니다. 분류를 하려면 먼저 답이 달린 예를 모아야 합니다. 예마다 달린 이 답을 레이블이라고 부릅니다.

레이블이 달린 예를 모은 묶음은 훈련 데이터라고 부릅니다. 최근접 이웃은 훈련 데이터에서 새 데이터와 가장 닮은 예를 찾습니다. 그리고 그 예의 레이블을 새 데이터의 답으로 씁니다.

가장 닮은 하나만 보면 1-최근접 이웃입니다. 닮은 예 k 개를 보고 그 레이블 가운데 많은 쪽을 고르면 k-최근접 이웃(k-NN, k-Nearest Neighbors)입니다. 실무에서 최근접 이웃이라고 하면 대개 이 k-NN 을 말합니다.

데이터를 점으로 놓기

닮음을 재려면 데이터를 숫자로 적어야 합니다. 과일이라면 무게와 지름을 잴 수 있습니다. 데이터를 설명하려고 잰 이런 값 하나하나를 특성이라고 부릅니다.

특성을 정해진 순서로 늘어놓으면 벡터 하나가 됩니다. 무게가 5, 지름이 5 인 과일은 벡터 (5, 5) 입니다.

특성이 둘이면 이 벡터를 평면 위의 점 하나로 볼 수 있습니다. 무게를 가로축, 지름을 세로축에 놓으면 과일마다 점이 하나씩 찍힙니다. 닮은 과일끼리는 평면에서도 가까이 모입니다.

특성의 개수는 차원이라고 부릅니다. 무게와 지름만 잰 과일은 2차원입니다. 색과 당도까지 재면 4차원이 됩니다. 평면에 그릴 수는 없어도 거리는 같은 방법으로 잽니다.

두 점이 닮은 정도는 두 점 사이의 거리로 잽니다. 거리가 짧을수록 닮았다고 봅니다. 가장 흔한 것은 두 점을 곧게 이은 길이인 유클리드 거리입니다. 축을 따라 가로세로로만 간 길이인 맨해튼 거리도 씁니다.

예측 한 번의 절차

답이 무리가 아니라 수일 때도 있습니다. 집값처럼 수를 맞히는 일은 회귀라고 부릅니다. 최근접 이웃은 분류와 회귀를 둘 다 합니다.

예측은 세 단계로 끝납니다. 새 데이터와 훈련 데이터 전부 사이의 거리를 잽니다. 거리가 짧은 순서로 k 개를 골라 이웃으로 삼습니다. 마지막으로 이웃의 답을 모읍니다.

flowchart TD
    A["새 데이터가 온다"] --> B["훈련 데이터 전부와 거리를 잰다"]
    B --> C["가장 가까운 k 개를 이웃으로 고른다"]
    C --> D{"맞히는 답이 무리인가 수인가"}
    D -->|"무리 · 분류"| E["이웃 레이블의 다수결"]
    D -->|"수 · 회귀"| F["이웃 값의 평균"]

분류에서는 이웃의 레이블 가운데 가장 많은 것을 고릅니다. 이것을 다수결 투표라고 부릅니다. 회귀에서는 이웃의 값을 평균합니다. 가장 닮은 집 셋이 3억, 4억, 5억 원에 팔렸으면 새 집의 값은 4억 원으로 맞힙니다.

이웃 수에 따라 바뀌는 답

아래 코드는 과일 여섯 개를 훈련 데이터로 두고 새 과일 하나를 가릅니다. 특성은 둘이고 레이블은 귤과 사과입니다. 훈련 데이터 가운데 (5, 4) 의 귤 하나는 사과 무리 가까이에 홀로 떨어져 있습니다.

import math
from collections import Counter

train = [((1, 1), "귤"), ((2, 2), "귤"),
         ((5, 4), "귤"), ((7, 5), "사과"),
         ((6, 7), "사과"), ((7, 7), "사과")]
q = (5, 5)

near = sorted(train,
              key=lambda t: math.dist(t[0], q))

def vote(k):
    ys = [y for _, y in near[:k]]
    return Counter(ys).most_common(1)[0][0]

vote(1)   # '귤'
vote(3)   # '사과'

near 는 훈련 데이터를 새 과일 q 와 가까운 순서로 줄 세운 목록입니다. 맨 앞은 거리가 1 인 (5, 4) 의 귤입니다. 그다음 세 개는 모두 사과입니다.

k 가 1 이면 이 귤 하나만 보고 귤이라고 답합니다. k 가 3 이면 귤 하나와 사과 둘을 보고 사과라고 답합니다. (5, 4) 의 귤은 레이블을 잘못 적은 예일 수 있습니다. 드물게 생긴 귤일 수도 있습니다. k 를 키우면 이런 점 하나에 답이 흔들리지 않습니다.

k 를 고르는 법

k 가 너무 작으면 이웃 한둘에 답이 휘둘립니다. 앞 예에서 k 가 1 일 때 (5, 4) 의 귤 하나가 답을 정한 것이 그렇습니다. 그 귤이 레이블을 잘못 적은 예라면 데이터에 섞인 엉뚱한 값입니다. 이런 값을 잡음이라고 부릅니다.

k 가 작으면 이 잡음까지 따라서 답합니다. 훈련 데이터에만 지나치게 맞춘 이 상태를 과적합이라고 부릅니다. 과적합되면 처음 보는 데이터에서 자주 틀립니다.

k 가 너무 크면 먼 데이터까지 투표에 끼어듭니다. k 를 훈련 데이터의 개수로 잡으면 어떤 물음에도 가장 흔한 레이블만 답합니다. 데이터의 무늬를 못 잡는 이 상태를 과소적합이라고 부릅니다.

k 는 사람이 미리 정해 두는 값입니다. 데이터를 모아 둔다고 저절로 정해지지 않습니다. 이렇게 사람이 골라 주는 값을 하이퍼파라미터라고 부릅니다.

보통 k 를 여럿 시험해 봅니다. 이때 시험 문제로 훈련 데이터를 다시 쓰면 안 됩니다. k 가 1 이면 어느 점이든 가장 가까운 이웃이 자기 자신입니다. 그러면 한 번도 안 틀린 것처럼 나옵니다.

그래서 답을 아는 데이터 일부는 모아 두는 훈련 데이터에 넣지 않습니다. 따로 떼어 둔 이 데이터를 검증 세트라고 부릅니다. k 마다 검증 세트의 답을 맞혀 봅니다. 그중 가장 덜 틀리는 k 를 고릅니다.

데이터가 적으면 어느 몫을 떼어 두느냐에 따라 고른 k 가 달라질 수 있습니다. 이때는 데이터를 여러 몫으로 나눕니다. 몫마다 한 번씩 검증 세트로 쓰고 결과를 모읍니다. 이 방법을 교차 검증이라고 부릅니다.

레이블이 둘뿐인 분류에서는 k 를 홀수로 잡는 일이 많습니다. 짝수면 투표가 반반으로 갈릴 수 있기 때문입니다.

가까운 이웃의 표에 더 큰 무게를 주는 변형도 있습니다. 거리가 짧을수록 표가 무거워집니다. 그러면 먼 이웃이 답을 덜 흔듭니다.

숫자 단위 맞추기

거리는 특성 값의 차이로 잽니다. 그래서 값의 폭이 큰 특성 하나가 거리를 거의 혼자 정합니다. 아래 표는 고객 셋을 나이와 연봉으로 적은 것입니다.

A 와 B 는 나이가 서른 살, 연봉이 10만 원 차이 납니다. A 와 C 는 나이가 한 살, 연봉이 100만 원 차이 납니다. 연봉을 원 단위로 두고 거리를 재면 A 와 B 사이는 약 100,000, A 와 C 사이는 약 1,000,000 입니다.

나이 차이는 거리에 거의 보태지지 않습니다. 그 결과 서른 살 많은 B 가 A 와 더 닮은 고객으로 나옵니다.

이 일을 막으려고 거리를 재기 전에 특성마다 값의 폭을 맞춥니다. 이 손질을 특성 스케일링이라고 부릅니다. 흔한 방법은 둘입니다.

하나는 최소-최대 스케일링입니다. 특성마다 값에서 최솟값을 뺀 뒤 폭으로 나눕니다. 그러면 어느 특성이든 값이 0 과 1 사이에 들어옵니다.

고객 전체의 나이가 20~80세, 연봉이 2,000만~1억 원에 걸쳐 있다고 해 봅시다. 차이를 이 폭으로 나눠 다시 재면 A 와 B 사이는 약 0.5, A 와 C 사이는 약 0.02 입니다. 이제 C 가 A 와 더 닮은 고객으로 나옵니다.

다른 하나는 표준화입니다. 특성마다 평균을 뺀 뒤 값들이 평균에서 퍼진 정도로 나눕니다. 이 퍼진 정도를 재는 수가 표준편차입니다.

훈련 단계가 비어 있는 방식

많은 학습 방법은 훈련 단계에서 데이터를 보고 모델을 만듭니다. 모델은 데이터에서 뽑아낸 규칙을 담은 결과물입니다. 예측할 때는 그 모델만 씁니다. 훈련 데이터는 다시 보지 않습니다.

결정 트리는 「지름이 4 보다 큰가」 같은 질문의 순서를 모델로 남깁니다. 신경망은 입력에 곱할 숫자 묶음을 남깁니다.

최근접 이웃은 훈련 단계에서 아무것도 계산하지 않습니다. 훈련 데이터를 저장해 둘 뿐입니다. 계산은 예측할 때까지 미룹니다. 이런 방식을 게으른 학습이라고 부릅니다.

미루는 덕에 얻는 것이 있습니다. 새 데이터가 들어오면 저장해 둔 데이터에 더하기만 해도 다음 예측부터 반영됩니다. 답의 근거도 이웃으로 보여 줄 수 있습니다. 「가장 닮은 고객 다섯 명 가운데 넷이 떠났다」는 설명은 누구나 알아듣습니다.

모양을 미리 정하지 않는 경계

무리와 무리를 가르는 선을 결정 경계라고 부릅니다. 과일 예라면 평면에서 귤로 답하던 곳이 사과로 답하는 곳으로 바뀌는 선입니다. 최근접 이웃은 모델을 미리 만들지 않으니 이 선의 모양도 미리 정해 두지 않습니다. 선은 저장해 둔 점들이 어디 있느냐로만 정해집니다.

앞의 과일 예에서 k 가 1 이면 (5, 4) 의 귤 둘레가 귤 구역이 됩니다. 그 귤이 가장 가까운 이웃인 물음은 사과 무리 곁이어도 귤로 답합니다. 경계선이 그 귤 하나를 감싸며 사과 쪽으로 불룩 휘어 들어갑니다.

가까운 이웃이 바뀌는 곳마다 선이 이렇게 꺾입니다. 무리가 구불구불하게 섞여 있어도 경계가 그 모양을 따라갑니다.

로지스틱 회귀는 이와 다릅니다. 특성에 숫자를 곱해 더한 값 하나로 무리를 가릅니다. 그 결과 경계는 곧은 선입니다. 무리가 구불구불하게 섞여 있으면 곧은 선 하나로는 다 가르지 못합니다.

계산 비용

비용은 훈련 데이터의 개수 n 과 특성의 개수 d 가 정합니다. 결정 트리나 신경망과 달리 비용이 예측 쪽에 몰립니다. 아래 표의 O(n·d) 는 비용이 n 과 d 의 곱에 비례한다는 뜻입니다. 이 표기는 빅오 표기법이라고 부릅니다.

이웃 고르기는 전부 정렬하지 않아도 됩니다. 가장 먼 것을 빨리 꺼내는 힙에 k 개만 담아 둡니다. 더 가까운 것이 오면 가장 먼 것과 바꿔 넣습니다. 그러면 정렬의 O(n log n) 대신 O(n log k) 가 듭니다.

예측 한 번이 훈련 데이터 전부를 훑습니다. 훈련 데이터가 백만 개면 물음 하나에 거리를 백만 번 잽니다. 그 계산 시간은 서비스의 응답 시간에 더해집니다.

가장 가까운 k 개를 찾는 일만 떼어 보면 최근접 이웃 검색이라는 검색 문제입니다. 이 검색을 빠르게 하면 예측도 빨라집니다.

차원이 낮으면 k-d 트리를 씁니다. k-d 트리는 공간을 미리 구역으로 나눠 둡니다. 물음이 오면 먼 구역은 통째로 건너뜁니다.

가장 가까운 것을 가끔 놓쳐도 되는 경우도 있습니다. 그때는 근사 최근접 이웃 검색으로 후보만 먼저 추립니다. 거리는 그 후보와만 잽니다.

특성이 많을 때

고객을 특성 수백 개로 적었다고 해 봅시다. 나이와 연봉 말고도 상품마다 산 횟수가 하나씩 특성이 됩니다. 이렇게 특성이 늘면 거리가 잘 듣지 않습니다.

거리는 축마다 생긴 차이를 모두 모아 얻습니다. 축이 수백 개면 작은 차이가 수백 번 쌓입니다. 그 결과 어느 두 고객 사이도 비슷하게 멀어집니다.

가장 가까운 고객과 가장 먼 고객의 거리 차이가 작아집니다. 그러면 「가깝다」가 뜻을 잃습니다. 이 현상을 차원의 저주라고 부릅니다.

답과 상관없는 특성도 같은 문제를 키웁니다. 쓸모없는 특성 하나하나가 거리에 잡음을 더하기 때문입니다. 흔히 답에 쓸모 있는 특성만 추립니다. 또는 차원 축소로 특성 수를 줄인 뒤에 최근접 이웃을 씁니다.

쓰는 때와 안 쓰는 때

맞는 경우와 맞지 않는 경우를 나란히 놓으면 아래와 같습니다. 대부분 앞 소절들에서 본 성질에서 나옵니다.

다른 모델의 성적을 재는 첫 기준으로도 자주 씁니다. 훈련이 없어 데이터만 있으면 바로 결과가 나오기 때문입니다. 더 복잡한 모델이 이 결과보다 덜 틀려야 그 복잡함을 쓸 까닭이 생깁니다.

같은 생각은 분류 밖에서도 쓰입니다. 추천 시스템은 나와 닮은 사용자들이 좋아한 상품을 골라 보여 주기도 합니다. 이웃들과 멀리 떨어진 점을 찾으면 이상치를 골라낼 수 있습니다.

관련 항목

최근접 이웃이 속하는 상위 분류

머신러닝 · 지도 학습 · 분류 · 회귀 · 게으른 학습 · 인스턴스 기반 학습 · 비모수 모델

최근접 이웃과 맞세워지는 다른 학습 방법

결정 트리 · 신경망 · 로지스틱 회귀 · 선형 회귀 · 나이브 베이즈 · 서포트 벡터 머신 · 랜덤 포레스트

이웃의 가까움을 재는 거리 척도

유클리드 거리 · 맨해튼 거리 · 민코프스키 거리 · 코사인 유사도 · 해밍 거리 · 거리 함수

거리를 재기 전에 거치는 특성 손질

특성 스케일링 · 표준화 · 최소-최대 스케일링 · 특성 선택 · 차원 축소 · 주성분 분석 · 원-핫 인코딩

k 를 고를 때 맞서는 문제와 검증 방법

과적합 · 과소적합 · 편향과 분산 · 하이퍼파라미터 · 검증 세트 · 교차 검증 · 잡음

이웃 찾기를 빠르게 하는 검색 방법

최근접 이웃 검색 · 완전 탐색 · k-d 트리 · 볼 트리 · 근사 최근접 이웃 · HNSW · 지역 민감 해싱 · 차원의 저주

최근접 이웃이 다루는 데이터 표현

벡터 · 차원 · 특성 벡터 · 레이블 · 훈련 데이터 · 임베딩 · 결정 경계

최근접 이웃을 바탕으로 한 응용

추천 시스템 · 협업 필터링 · 이상치 · 이상 탐지 · LOF

이름이 비슷해 헷갈리는 알고리즘

k-평균 군집화 · 최근접 이웃 보간 · 근사 최근접 이웃 검색