k-최근접 이웃(kNN): 가까운 이웃 k 개에게 묻기

답을 모르는 새 점이 오면, 답을 아는 점들 가운데 가장 가까운 k 개를 찾아 그 점들에게 묻습니다. 거리 재기, 줄 세우기, k 개 남기기, 투표를 한 걸음씩 눌러 보세요.

한 줄 답. k-최근접 이웃(kNN)은 학습하지 않고 훈련 자료를 그대로 들고 있다가, 새 점이 오면 가장 가까운 k 개를 찾아 그 점들의 답으로 다수결(분류)이나 평균(회귀)을 냅니다. k 는 사람이 정하고, k 가 작으면 경계가 들쭉날쭉하고 크면 매끈해집니다.

초록 A 와 파랑 B 는 답을 아는 훈련 점이고, 「?」가 든 주황 동그라미가 답을 모르는 새 점입니다(끌어서 옮길 수 있습니다). 가는 회색 선은 거리, 작은 번호는 가까운 순서, 굵은 선은 남긴 이웃, 주황 점선 원은 k 번 이웃까지의 거리, 화살표는 이웃이 내는 표입니다. 옆 표는 줄의 앞 k + 2 개를 보여 줍니다. 점 36 개(A 18, B 18)는 고정 시드(seed) 난수기로 지어낸 것이라 쪽을 열 때마다 같습니다.

해 볼 것. ① 처음 그대로(새 점 (0.4, 0.4), k = 5) 「다음」을 네 번 누르면: 가장 가까운 점은 A 이고 거리 0.32, 가장 먼 점은 4.53, 5 번 이웃까지는 0.81, 투표는 A 2표, B 3표 → B 입니다. ② 가중치 단추를 눌러 「1 ÷ 거리」로 바꾸면 A 5.16, B 4.76 → A 로 답이 뒤집힙니다. 가장 가까운 셋 가운데 둘(0.32, 0.5)이 A 라서입니다. ③ 균등으로 돌려 k 를 1, 3, 5, 7 로 바꾸면 답이 A, A, B, B 입니다. 같은 자료, 같은 새 점이어도 k 에 따라 답이 다릅니다.

1. k-최근접 이웃이란: 배우지 않고 기억하기

자료마다 정답(클래스 A 인가 B 인가)이 붙어 있고, 새 자료의 정답을 맞히는 일을 지도 학습이라고 합니다. 보통의 모델은 훈련 자료에서 규칙(가중치)을 뽑아 두고 훈련 자료는 버립니다. k-최근접 이웃은 다릅니다. scikit-learn 문서의 말로는 「일반적인 내부 모델을 만들려 하지 않고, 훈련 자료의 사례를 그저 저장한다」. 그래서 사례 기반 학습이라고 부릅니다.

일은 새 점이 왔을 때 합니다. 새 점에서 훈련 점들까지의 거리를 재고, 가장 가까운 k 개를 골라, 그 점들의 정답으로 새 점의 답을 정합니다. 답이 클래스(class)면 분류(다수결), 답이 숫자면 회귀(평균)입니다.

이름이 닮은 k-평균은 다른 것입니다. k-평균은 정답 없이 점들을 클러스터(cluster) k 개로 묶고, 여기의 k 는 이웃의 수입니다. 그리고 많은 점 가운데 가까운 것을 빨리 찾는 법은 벡터 검색 쪽에서 다룹니다. 이 쪽은 찾은 이웃으로 답을 정하는 법을 다룹니다.

2. 절차와 식

들고 있기  훈련 점과 그 답을 모두 저장한다(배우는 계산은 없다)
새 점 q 가 오면
  ① 거리:    훈련 점마다 q 까지의 거리를 잰다
  ② 줄:      가까운 순으로 줄 세운다
  ③ 남기기:  앞의 k 개만 남긴다
  ④ 답:      분류면 k 개의 클래스로 투표, 회귀면 k 개의 답을 평균

식으로 적으면 이렇습니다.

거리        d(x, q) = √((x₁ − q₁)² + (x₂ − q₂)² + …)
다수결      ŷ = 이웃 k 개 가운데 가장 많이 나온 클래스
거리 가중   클래스 c 의 점수 = (클래스가 c 인 이웃마다 1 ÷ dᵢ 를 모두 더한 값),  ŷ = 점수가 가장 큰 클래스
회귀        ŷ = (y₁ + y₂ + … + y_k) ÷ k

균등과 거리 가중. 다수결은 이웃마다 한 표입니다(scikit-learn 의 weights="uniform"). 거리 가중은 이웃마다 1 ÷ 거리 만큼의 표를 줘서 가까운 이웃의 말을 더 듣습니다(weights="distance"). 실험의 해 볼 것 ② 처럼 둘의 답이 갈릴 수 있습니다. 거리가 0 이면 1 ÷ 0 을 셀 수 없어서, 이 쪽의 실험은 그때 거리 0 인 점들만 표를 내게 했습니다.

scikit-learn 으로는 몇 줄입니다. fit 은 자료를 담아 두는 일이고, 계산은 predict 때 일어납니다.

from sklearn.neighbors import KNeighborsClassifier

model = KNeighborsClassifier(n_neighbors=5)        # weights="distance" 를 더하면 거리 가중
model.fit(X_train, y_train)                        # 훈련 자료를 담아 둔다
print(model.predict([[0.4, 0.4]]))                 # 가까운 5 개의 다수결
print(model.score(X_test, y_test))                 # 시험 자료의 정확도

3. 손으로 풀어 보기: 수직선 위의 점 여섯

훈련 점이 수직선 위에 있습니다. 1(A), 2(A), 4(B), 5(A), 7(B), 8(B). 새 점은 4.4 입니다.

훈련 점클래스4.4 까지 거리순위
1A3.45
2A2.43
4B0.41
5A0.62
7B2.64
8B3.66
  1. k = 1. 가장 가까운 것은 4(B, 거리 0.4)라 답은 B. 이웃 하나가 혼자 정합니다.
  2. k = 3, 균등. 이웃은 4(B), 5(A), 2(A). A 2표, B 1표라 답은 A. k 를 늘리자 답이 바뀌었습니다.
  3. k = 3, 거리 가중. A 는 1 ÷ 0.6 + 1 ÷ 2.4 ≈ 1.67 + 0.42 = 2.08, B 는 1 ÷ 0.4 = 2.5. 답은 B. 2 는 멀어서(2.4) 표가 가볍기 때문입니다.
  4. 회귀라면. 이웃 셋의 답이 숫자 10, 12, 20 이라면 답은 (10 + 12 + 20) ÷ 3 = 14 입니다.

4. k 가 경계를 바꾼다

평면의 모든 자리에 새 점을 놓아 보고, 답이 A 인 곳은 초록, B 인 곳은 파랑으로 칠하면 두 색이 만나는 선이 생깁니다. 이것이 결정 경계입니다. 아래 막대로 k 를 바꿔 보세요. 그 아래 그래프는 k 마다 훈련 점 36 개를 맞힌 비율(훈련 정확도)과, 같은 규칙으로 따로 지어낸 시험 점 100 개를 맞힌 비율(시험 정확도)입니다. 시험 점은 그리지 않았습니다.

훈련 정확도
시험 정확도

해 볼 것. ① k = 1 이면 훈련 정확도가 100% 입니다. 훈련 점마다 가장 가까운 이웃이 자기 자신(거리 0)이라서입니다. 그런데 시험 정확도는 78% 이고, 경계는 섞여 든 점 하나하나를 감싸며 들쭉날쭉합니다. ② k 를 3, 5, 7 로 올리면 시험 정확도가 82%, 85%, 87% 로 오르고 경계가 매끈해집니다. 이 자료에서는 k = 7 이 가장 높습니다(그때 훈련 정확도는 83%). ③ k 를 9, 11 로 더 올리면 시험 정확도가 84%, 82% 로 내려갑니다. k = 15 는 85% 입니다.

scikit-learn 문서는 「알맞은 k 는 자료에 따라 크게 다르다. 대체로 k 가 크면 노이즈(noise)의 영향을 누르지만, 분류의 경계가 덜 뚜렷해진다」고 적습니다. 실험에서 k = 1 의 훈련 100%, 시험 78% 는 훈련 자료의 노이즈까지 외운 모양이고, 이것이 과적합입니다. 훈련 정확도로 k 를 고르면 늘 k = 1 이 뽑히니, 훈련에 쓰지 않은 자료로 재서 고릅니다. 여기서는 시험 자료로 쟀지만, 실제로 k 를 고를 때는 검증 자료를 따로 떼어 쓰고 시험 자료는 마지막에 한 번만 씁니다(자료 나누기).

5. 거리를 재기 전에: 특징 스케일링(feature scaling)

거리 식 d = √((가로 차이)² + (세로 차이)²) 를 보면, 특징 하나의 숫자가 100 배가 되면 그 차이의 제곱은 10000 배가 됩니다. 그래서 눈금이 큰 특징이 거리를 거의 혼자 정합니다. 이것은 다른 근거 없이 거리 식에서 바로 나오는 말입니다. 같은 점 셋으로 봅니다.

전: 가로 값 그대로(m) 0123 123 P (A) R (B) q q→P 1.50 · q→R 1.02: R 이 가깝다 가로 × 100 후: 가로 값 × 100(cm) 100150200 P (A) R (B) q q→P 10.11 · q→R 100: P 가 가깝다
같은 세 점 q, P, R. 오른쪽은 가로 특징만 m 에서 cm 로 적어 숫자가 100 배가 된 것을 같은 비율로 그렸습니다. 세로 차이(1.5 이하)는 거의 보이지 않고, 가장 가까운 점이 R(B) 에서 P(A) 로 바뀝니다. k = 1 이면 답도 B 에서 A 로 바뀝니다. 굵은 주황 선이 가장 가까운 점까지의 선입니다.

q 에서 R 까지는 전에 1.0² + 0.2² = 1.04 의 제곱근이었는데, 후에는 100² + 0.2² = 10000.04 의 제곱근입니다. 세로 차이 0.2 는 거의 아무 몫도 못 합니다. 단위는 사람이 고른 것일 뿐인데 답이 바뀌니, 거리를 재기 전에 특징마다 눈금을 맞춥니다(정규화와 표준화).

6. 언제 무엇을 쓰나

선택지좋은 점나쁜 점쓰는 경우
k-최근접 이웃 자체배우는 계산이 없다. 훈련 자료를 저장해 두기만 한다내부 모델을 만들지 않으니 답을 낼 때마다 이웃을 찾아야 한다. 거리를 쓰니 특징의 눈금에 민감하다(5절)「가까운 것은 답도 비슷하다」가 맞는 자료. 눈금을 맞춘 뒤
작은 k가까운 점을 하나하나 따라가 경계가 세밀하다노이즈 점 하나에 답이 흔들린다. k = 1 의 훈련 정확도는 늘 100% 라 믿을 수 없다알맞은 k 는 자료에 따라 크게 다르다. 훈련에 쓰지 않은 자료로 재서 고른다(4절)
큰 k노이즈의 영향을 누른다분류의 경계가 덜 뚜렷해진다위와 같다
균등(uniform)이웃마다 한 표라 단순하다k 번 이웃처럼 먼 이웃도 가장 가까운 이웃과 같은 가중치다둘 다 재 보고 고른다
거리 가중(distance)가까운 이웃의 말을 더 듣는다아주 가까운 이웃 하나가 거의 혼자 정할 수 있다(1 ÷ 거리라서)둘 다 재 보고 고른다

가까운 k 개를 찾는 법. scikit-learn 은 찾는 법으로 전부 재기(brute), KD 트리(kd_tree), 볼 트리(ball_tree)를 둡니다. 이 쪽은 이름만 적습니다. 많은 점에서 가까운 것을 빨리 찾는 법은 벡터 검색 쪽에 있습니다.

어디에 쓰나

자주 묻는 것

k-최근접 이웃과 k-평균은 같은 건가요?

아닙니다. 이름만 닮았습니다. k-최근접 이웃은 정답이 붙은 점들 가운데 새 점과 가장 가까운 k 개를 찾아, 그 점들의 정답으로 새 점의 답을 정합니다. k 는 이웃의 수입니다. k-평균은 정답 없이 점들을 클러스터 k 개로 묶고, k 는 클러스터의 수입니다.

k 는 어떻게 고르나요?

정해진 값은 없습니다. 알맞은 k 는 자료에 따라 크게 다릅니다. k 를 여러 개 해 보고, 훈련에 쓰지 않은 자료에서 정확도가 가장 높은 k 를 고릅니다. 이 쪽의 실험 ② 에서는 k = 7 이었습니다. 클래스가 둘이면 홀수 k 를 써야 다수결이 비기지 않습니다.

벡터 검색과는 무엇이 다른가요?

벡터 검색은 많은 벡터 가운데 가까운 것을 빨리 찾는 일입니다. k-최근접 이웃은 찾은 이웃의 답으로 새 점의 답을 정하는 일입니다. k-최근접 이웃의 첫 걸음인 「가까운 k 개 찾기」를 빠르게 하는 법이 벡터 검색 쪽에 있습니다.

낱말

여기서 쓴 말책에서 부르는 말
가까운 이웃 k 개로 답 정하기k-최근접 이웃(k-nearest neighbors, kNN)
배우지 않고 자료를 기억하기사례 기반 학습(instance-based learning), 일반화하지 않는 학습(non-generalizing learning)
답을 아는 점 · 새 점훈련 자료(training data) · 쿼리 점(query point)
점마다 붙은 정답 A · B클래스(class), 레이블(label)
한 이웃 한 표 · 1 ÷ 거리 만큼의 표다수결 투표(majority vote), 균등 가중치(uniform weights) · 거리 가중치(distance weights)
두 색이 만나는 선결정 경계(decision boundary)
곧은 거리유클리드 거리(Euclidean distance)
숫자 답 내기 · 클래스 답 내기회귀(regression) · 분류(classification)
훈련에 쓰지 않은 자료검증 세트(validation set), 테스트 세트(test set)
눈금 맞추기특징 스케일링(feature scaling), 정규화(normalization), 표준화(standardization)
전부 재기 · KD 트리 · 볼 트리무차별 탐색(brute force) · k-d 트리(k-d tree) · 볼 트리(ball tree)

출처

← 결정 트리, 랜덤 포레스트, 부스팅k-평균 군집 →