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
q: 답을 모르는 새 점.q₁, q₂는 그 점의 첫째·둘째 특징 값입니다.x: 훈련 점 하나.x₁, x₂도 그 점의 특징 값입니다.d,dᵢ: 곧은 거리(유클리드 거리).dᵢ는 i 번 이웃에서 q 까지의 거리입니다.k: 남기는 이웃의 수. 사람이 정합니다.c: 클래스 하나(분류의 답 하나).ŷ: 새 점에 대해 내놓는 답.yᵢ: 회귀일 때 i 번 이웃의 답(숫자).
균등과 거리 가중. 다수결은 이웃마다 한 표입니다(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 까지 거리 | 순위 |
|---|---|---|---|
| 1 | A | 3.4 | 5 |
| 2 | A | 2.4 | 3 |
| 4 | B | 0.4 | 1 |
| 5 | A | 0.6 | 2 |
| 7 | B | 2.6 | 4 |
| 8 | B | 3.6 | 6 |
- k = 1. 가장 가까운 것은 4(B, 거리 0.4)라 답은 B. 이웃 하나가 혼자 정합니다.
- k = 3, 균등. 이웃은 4(B), 5(A), 2(A). A 2표, B 1표라 답은 A. k 를 늘리자 답이 바뀌었습니다.
- 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) 표가 가볍기 때문입니다.
- 회귀라면. 이웃 셋의 답이 숫자 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 배가 됩니다. 그래서 눈금이 큰 특징이 거리를 거의 혼자 정합니다. 이것은 다른 근거 없이 거리 식에서 바로 나오는 말입니다. 같은 점 셋으로 봅니다.
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 개의 답(숫자)을 평균합니다(3절의 14).
- 임베딩 위에서. 점이 2차원이 아니어도 거리만 잴 수 있으면 같습니다. 문서나 그림의 임베딩 벡터에서 가까운 k 개를 찾아 그 답을 따를 수 있고, 그때 가까운 것을 빨리 찾는 일이 벡터 검색입니다.
자주 묻는 것
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) |
출처
- scikit-learn 사용자 안내: Nearest Neighbors(가까운 이웃 방법의 원리, 사례 기반 학습, 다수결, k 고르기와 노이즈·경계,
uniform·distance가중치, 찾는 법brute·kd_tree·ball_tree, 이웃 답의 평균으로 하는 회귀).