가까운 것끼리
이웃 몇 명에게 물어볼 것인가

텃밭에서 씨앗 한 알을 주웠습니다. 봉투가 없어 품종을 모릅니다. 곁에는 품종을 아는 씨앗이 열 알 있어요. 우리가 가진 것은 두 가지 측정값뿐입니다 — 길이(mm)와 무게(g). 새로 주운 씨앗은 [6.1, 3.0]이었습니다.

가장 단순한 생각부터 해 봅시다. 가장 닮은 씨앗과 같은 품종일 것이다. '닮았다'를 숫자로 바꾸는 방법은 이미 배웠습니다. 5차시에서 만든 거리 함수를 쓰면 되지요. 실제로 재 보면 가장 가까운 씨앗은 [6.15, 2.95]이고 거리는 0.071, 품종은 A입니다. 답이 나왔습니다. 이 씨앗은 A입니다.

그런데 이웃을 하나 더 물어보면 어떨까요. 2위는 [6.0, 3.2], 거리 0.224, 품종 B. 3위도 B, 4위도 B, 5위도 B, 6위도 B입니다. 가까운 순서로 셋만 세면 A 1표 대 B 2표, 다섯을 세면 A 1표 대 B 4표예요. 이웃 하나에게 물으면 A, 셋에게 물으면 B입니다.

이 물음은 '몇 명'이라는 사소한 설정처럼 보이지만 그렇지 않습니다. 오늘 실제로 재 보면 이웃 수 하나를 바꾸는 것만으로 테스트 정확도가 60.0%에서 93.3%까지 오르내리고, 더 키우면 33.3%까지 무너집니다. 알고리즘은 한 글자도 바뀌지 않는데 말이지요.

씨앗 열 알의 값은 이렇습니다. 앞 넷이 A, 다음 넷이 B, 그리고 마지막 둘은 새 씨앗 바로 곁에 붙어 있는 두 알입니다.

9번 씨앗을 눈여겨보세요. 길이 6.15에 무게 2.95인데 품종이 A로 적혀 있습니다. 그런데 그 둘레는 온통 B예요. 5·6·7·8·10번이 모두 B입니다. 이 한 알은 기록이 잘못됐을 수도 있습니다. 그런데 이웃을 하나만 묻는 방식은 바로 이 한 알에게 판단을 통째로 맡기는 셈입니다. 오늘 이야기의 씨앗이 여기 있습니다.

k-최근접 이웃(k-nearest neighbors, 줄여서 k-NN)이 하는 일은 전부입니다. 세 줄이면 다 적힙니다.

1. 거리를 잰다. 새 데이터와 가지고 있는 모든 데이터 사이의 거리를 하나씩 계산해 가까운 순으로 줄을 세운다. — 5차시의 dist()가 여기서 쓰인다.
2. 앞에서 k개를 뽑는다. 줄의 맨 앞 k개만 남기고 나머지는 잊는다.
3. 다수결로 답한다. 뽑힌 k개의 이름표를 세어 표를 가장 많이 받은 이름표를 답으로 낸다.

학습이라고 부를 만한 단계가 없다

여기서 이상한 점이 하나 보입니다. 7차시에서 지도학습은 "정답이 붙은 데이터로 무언가를 배우는 것"이라 했는데, k-NN 에는 배우는 단계가 없습니다. 데이터를 그냥 들고 있을 뿐이에요. 가중치를 조정하지도, 규칙을 만들지도 않습니다.

그래서 k-NN 을 게으른 학습(lazy learning)이라 부릅니다. 공부는 하나도 안 해 두고 시험지를 받은 다음에야 교과서를 펼치는 셈이지요. 대신 대가를 치릅니다. 예측할 때마다 전체 데이터를 처음부터 끝까지 훑어야 합니다.

숫자로 따져 볼까요. 오늘 쓰는 데이터는 마흔 줄이라, 씨앗 하나를 판정하려면 거리를 마흔 번 계산합니다. 데이터가 백만 줄이면 백만 번이고, 씨앗 천 개를 판정하려면 십억 번입니다. 학습에 드는 시간은 0인데 예측에 드는 시간이 데이터 크기에 정비례해 늘어납니다. 13·14차시에서 만들 퍼셉트론과 층 쌓은 신경망은 정반대예요 — 학습에 오래 걸리지만, 다 배우고 나면 예측은 순식간입니다.

파이썬으로 옮기면 이렇게 짧습니다. 오늘 여러분이 채울 곳은 ????? 두 곳이에요.

def nearest(train, point, k):
    """① 거리를 재서 가까운 순으로 줄 세우고 ② 앞에서 k개를 뽑는다."""
    ranked = sorted(train, key=lambda item: ?????)
    return ranked[:k]


def knn(train, point, k):
    """③ 뽑힌 k개의 표를 세어 다수결로 답한다."""
    votes = {}
    for feat, label in nearest(train, point, k):
        votes[label] = votes.get(label, 0) + 1
    return ?????

여덟 줄입니다. 이 여덟 줄이 오늘 만들 분류기의 전부이고, 11차시에서 과적합을 재는 도구로 그대로 다시 쓰입니다.

새 씨앗 [6.1, 3.0]에 k를 바꿔 가며 물어본 결과입니다.

K = 1이 갈리는 이유는 표의 두 줄에 전부 들어 있습니다. 1위 [6.15, 2.95]가 거리 0.071로 바짝 붙어 있고, 2위 [6.0, 3.2]가 0.224입니다. 세 배 넘게 차이 나지요. 그런데 3위부터 6위까지가 전부 B라서, 이웃을 셋만 늘려도 표가 뒤집힙니다.

여기서 k가 무엇을 정하는 수인지가 드러납니다. k는 기계가 한 알의 기록을 얼마나 믿을 것인가를 정하는 수입니다.

양 끝이 다 나쁘다면 가운데 어딘가가 좋을 겁니다. 그 '어딘가'를 실제로 재서 찾는 것이 오늘 손으로 할 일이에요. 그러려면 데이터를 두 몫으로 갈라 두어야 합니다.

이 두 몫으로 k를 1부터 39까지 갈아 끼워 본 결과가 아래 표입니다. 미리 결과만 보면 이렇습니다.

표의 아래쪽 두 줄을 확인해 보세요. k = 31일 때 훈련 정확도가 57.5%인데, 훈련 씨앗 40개 중 A가 23개입니다. 23 ÷ 40 = 0.575지요. 테스트 정확도 33.3%도 마찬가지입니다. 테스트 씨앗 15개 중 A가 5개, 5 ÷ 15 = 0.333. 두 숫자가 품종 개수와 정확히 맞아떨어집니다. 이것이 "어디를 물어도 A라고만 답한다"의 증거입니다.

k = 1의 훈련 정확도가 100%인 까닭

표 맨 위가 이상하지 않나요. k = 1일 때 훈련 정확도가 정확히 100.0%입니다. 완벽해 보이지만, 잠깐 생각하면 당연합니다. 훈련 데이터 안의 어떤 씨앗을 골라 "이건 무슨 품종이니?"라고 물으면, 그 씨앗과 가장 가까운 씨앗은 자기 자신(거리 0)이에요. 자기가 자기에게 표를 던집니다.

그러니 k = 1의 100%는 외운 것이지 이해한 것이 아닙니다. 실제로 처음 보는 씨앗 15개로 채점하면 60.0%로 주저앉아요. 더 나쁜 소식이 있습니다. 테스트 씨앗 15개 중 B가 10개라서, 아무 생각 없이 "전부 B"라고만 우기는 기계의 정확도가 66.7%입니다. k = 1은 그것보다도 못합니다.

k를 홀수로 잡는 까닭

품종이 둘인데 k를 짝수로 두면 표가 갈릴 수 있습니다. k = 2에서 A 1표 B 1표가 되면 기계는 무엇을 골라야 할까요? 앞의 코드는 max(votes, key=votes.get)라고만 적혀 있어 동점일 때 무엇이 나올지 코드 어디에도 적혀 있지 않습니다.

실제로 돌려 보면 테스트 씨앗 15개 중 10개에서 동점이 납니다. 그런데 오류는 나지 않아요. 파이썬의 딕셔너리는 넣은 순서를 기억하고, max()는 값이 같으면 먼저 들어온 것을 돌려주기 때문입니다. 이웃을 가까운 순서로 넣었으니, 결과적으로 1위 이웃의 품종이 이깁니다.

증거는 이렇습니다. k = 2의 예측이 k = 1과 15개 모두 같습니다. 이웃을 하나 더 물었는데 바뀐 답이 하나도 없어요. 물어본 값이 없는 겁니다.

가장 간단한 해결은 k를 홀수로 잡는 것입니다. 품종이 둘일 때 홀수 k에서는 동점이 구조적으로 불가능해요. 실제로 k가 1·3·5·7·9·11일 때 동점은 단 한 번도 나지 않습니다. 다만 품종이 셋 이상이면 홀수로도 동점이 납니다(3표·3표·1표). 그때는 규칙을 직접 정해 적어야 해요.

지금까지는 씨앗 하나를 판정했습니다. 이제 시야를 넓혀 봅시다. 길이 4.4mm~8.6mm, 무게 1.4g~4.2g 사이의 모든 자리에 대해 "여기 씨앗이 있다면 무슨 품종일까"를 물으면 어떻게 될까요.

답은 그림이 됩니다. 평면이 A라고 답하는 구역과 B라고 답하는 구역으로 갈라지고, 그 사이에 선이 생깁니다. 이 선을 결정 경계(decision boundary)라 부릅니다.

분류기가 만들어 내는 것은 이 선입니다. 예측 하나하나가 아니라 평면 전체를 나누는 선이에요. 그리고 k를 바꾸면 이 선의 모양이 바뀝니다. 아래는 씨앗 열 알로 그린 두 장의 지도입니다. 계산은 실제로 21 × 13 = 273자리에서 돌렸습니다.

'매끄러워진다'를 눈이 아니라 자로 잰다

지도 두 장을 나란히 놓으면 차이가 보이긴 합니다. 그런데 "매끄러워졌다"는 말은 느낌이지 측정이 아니에요. 숫자로 재 봅시다.

방법은 간단합니다. 무게를 하나로 고정하고, 길이를 4.4mm부터 0.01mm씩 늘려 가며 답이 A에서 B로(또는 그 반대로) 바뀌는 지점을 찾습니다. 무게를 여섯 가지로 바꿔 가며 같은 일을 하면, 경계가 어디를 지나는지 여섯 점이 나옵니다.

K = 1의 경계는 무게가 달라짐에 따라 1.58mm나 좌우로 휘청입니다. K = 9에서는 0.60mm, 곧 거의 곧은 선이에요. 2.6배 차이입니다. 이제 "K를 키우면 경계가 매끄러워진다"가 느낌이 아니라 잰 값이 되었습니다.

실제 데이터에서도 결정 경계는 이렇게 그려집니다. 아래 산점도를 보세요. 붓꽃의 특성 네 개(꽃받침 길이·너비, 꽃잎 길이·너비)를 둘씩 짝지어 그린 작은 그림 열두 장입니다. 어느 두 특성을 골라도 빨간 점(세토사)은 따로 떨어진 무리를 이룹니다. 하지만 초록(버시컬러)과 파랑(버지니카)은 맞닿아 겹치는 자리가 있고, 그 자리에서는 어떤 분류기든 틀립니다.

k-NN 은 처음부터 끝까지 거리로만 움직입니다. 그러니 거리 계산이 흔들리면 알고리즘 전체가 흔들려요. 그런데 거리는 우리가 생각하는 것보다 훨씬 쉽게 흔들립니다. 저울의 단위를 바꾸기만 해도 흔들립니다.

실험해 봅시다. 무게를 g 대신 mg으로 적어 보는 겁니다. 2.1g은 2100mg이 되지요. 데이터는 하나도 안 바뀌었습니다. 같은 씨앗, 같은 무게예요. 적는 방식만 바꿨습니다.

표를 위아래로 읽어 보세요. 두 가지가 한꺼번에 드러납니다.

첫째, mg으로 적은 줄과 '무게만' 쓴 줄이 여섯 칸 모두 같습니다. 우연이 아니에요. 예측 15개도 15개 모두 같습니다. 무게를 mg으로 적으면 두 씨앗의 무게 차이가 수백~수천이 되고, 길이 차이는 기껏해야 4입니다. 제곱해서 더하면 길이 쪽 값은 있으나 마나가 되지요. 길이라는 특성이 계산에서 사라진 것이고, 위 표가 그것을 증명합니다. kg으로 적은 줄이 '길이만' 쓴 줄과 닮은 것도 같은 이유입니다 — 이번엔 무게가 사라졌어요.

둘째, 정규화를 켠 세 줄은 완전히 같습니다. 소수점 한 자리도 다르지 않아요. 5차시에서 만든 minmax_fit()·minmax_apply()가 두 특성을 모두 0~1 사이로 눌러 놓으면, 원래 g으로 적었든 mg으로 적었든 같은 좌표가 됩니다. 정규화가 하는 일은 단위를 지우는 것입니다.

거리 재는 방식도 하나가 아니다

5차시에서 쓴 거리는 유클리드 거리였습니다. 가로 차와 세로 차를 제곱해 더하고 뿌리를 씌우는, 자로 잰 직선 거리예요. 그런데 거리를 재는 방식은 여럿입니다. 맨해튼 거리는 제곱하지 않고 차의 절댓값을 그냥 더합니다.

가장 좋은 k가 5에서 7로 옮겨 갔습니다. k-NN 을 쓴다는 것은 이웃 수 k만 고르는 일이 아니라, 거리를 어떻게 잴지도 함께 고르는 일입니다. 정규화 방식(0~1 / z-점수), 거리 방식(유클리드 / 맨해튼), 이웃 수(k) — 정할 것이 최소 셋이에요. 알고리즘이 여덟 줄이라고 해서 결정할 것까지 적은 것은 아닙니다.

아래 판을 누르면 그 자리에 새 씨앗이 놓입니다. 누른 채 끌면 씨앗이 따라오고, 판정은 그때그때 다시 계산됩니다. 가까운 k개 이웃까지 노란 선이 이어지고, 배경의 옅은 색이 결정 경계예요. k 슬라이더를 움직이면 그 경계가 눈앞에서 다시 그려집니다.

공책을 펴 두세요. 아래 세 과제의 답을 확인 문제에서 다시 묻습니다.

과제 ① 표를 채운다 — 경계가 흔들리는 폭을 잰다

설정을 씨앗 열 알 · 정규화 안 함 · g · 유클리드로 두고(초기 상태입니다), k와 무게를 바꿔 가며 📏 경계 찾기를 열여덟 번 누릅니다. 무게는 숫자 칸에 직접 적는 편이 빠릅니다.

맨 아랫줄이 경계가 흔들리는 폭입니다. 세 값을 견주어 "K를 키우면 경계는 ○○해진다"를 한 문장으로 적어 보세요. (여러분이 채운 값은 개념 3의 표와 같아야 합니다. 다르면 설정을 다시 확인하세요.)

과제 ② 반례를 만든다 — 판정이 뒤집히는 자리

씨앗을 마흔 알로, 정규화를 0~1로 바꿉니다. 이제 씨앗을 이리저리 끌면서 k = 1과 k = 5의 판정이 서로 다른 자리를 찾으세요. k를 1로 두고 판정을 본 뒤 슬라이더를 5로 옮겨 보면 됩니다.

• 그런 자리를 세 곳 찾아 좌표를 적으세요.
• 세 자리에는 공통점이 하나 있습니다. 무엇인가요? (힌트: 1위 이웃의 품종과, k = 5일 때 뽑힌 다섯 알의 표(A·B)를 나란히 적어 보세요)
• 거꾸로, k를 1에서 11까지 아무리 바꿔도 판정이 안 바뀌는 자리도 한 곳 찾아 적으세요.

과제 ③ 문턱을 찾는다 — 단위가 판을 뒤집는 지점

설정을 마흔 알 · 정규화 안 함 · g로 두고 k를 5로 맞춥니다. 테스트 15개 정확도 칸을 읽어 적으세요. 그다음 무게 단위만 mg으로 바꿉니다.

1. 정확도가 얼마에서 얼마로 떨어졌는지 적으세요.
2. 배경의 결정 경계 모양이 어떻게 변했는지 한 문장으로 적으세요. (세로선이던 것이 무엇이 되었나요?)
3. 정규화를 0~1로 켜 보세요. 정확도가 돌아옵니까? 경계 모양도 돌아옵니까?
4. 단위를 kg으로 바꾸면 경계는 어느 방향의 곧은 선이 됩니까? mg일 때와 정확히 반대인 까닭도 함께 적으세요.

이제 화면이 대신 해 주던 계산을 직접 짭니다. 채울 곳은 두 곳이에요.

돌린 뒤에 할 것

1. 【1】의 거리 목록에서 1위와 2위의 거리를 공책에 적으세요. 그리고 "K = 1만 A인 이유"를 그 두 줄만 근거로 두 문장으로 쓰세요.
2. 【2】의 마지막에 찍히는 경계 폭 세 개를 시뮬레이터에서 손으로 채운 표와 견주세요. 같습니까? 다르다면 어느 설정이 달랐을까요?
3. 씨앗 ([6.15, 2.95], "A") 줄을 지우고 다시 돌려 보세요. K = 1의 답이 무엇으로 바뀝니까? K = 3·5·9는요?
4. 새 씨앗 좌표 new를 바꿔 가며, K = 1과 K = 3의 답이 갈리는 자리를 두 곳 더 찾아 적으세요.

열 알로는 정확도를 잴 수 없습니다. 그래서 씨앗을 마흔 알로 늘리고, 학습에 한 번도 쓰지 않는 테스트용 열다섯 알을 따로 두었습니다. 앞 열 줄은 방금 손으로 따진 그 열 알이에요 — 같은 데이터가 이어집니다.

이 칸에서 채울 곳은 한 곳입니다. 5차시의 규칙을 다시 묻는 자리예요.

돌린 뒤에 할 것

1. 【3】의 표에서 테스트 정확도가 가장 높은 k와 그 값을 적으세요. 그리고 "무조건 B"의 점수 66.7%보다 낮은 k가 있는지 찾아 적으세요.
2. 【4】에서 홀수 k의 동점 개수를 확인하세요. 전부 몇 개입니까? 왜 그렇습니까?
3. 【5】에서 mg 줄과 무게만 줄이 같은지 여섯 칸을 하나씩 대조하세요. 같다면 그것이 무엇을 뜻합니까?
4. 【6】의 마지막 씨앗 [9.1, 2.0]이 0~1로 눌렸을 때 1.101이 나옵니다. 이것이 왜 버그가 아닌지 두 문장으로 쓰세요.
5. 부수어 보기. k = 0으로 두면 어떻게 됩니까? k = 41(훈련 40개보다 크게)로 두면요? 하나는 죽고 하나는 조용히 도는데, 어느 쪽이 더 위험한 오류일까요?

오늘 우리는 분류 알고리즘 하나를 통째로 짰습니다. 세 단계, 여덟 줄이었어요. 그런데 그 여덟 줄을 돌리는 동안 정할 것이 셋이나 나왔습니다.

그리고 오늘 처음 만난 눈이 하나 더 있습니다. 결정 경계예요. 분류기가 실제로 만들어 내는 것은 예측 하나하나가 아니라 평면을 나누는 선이고, 그 선이 얼마나 구불구불한지를 1.58mm 대 0.60mm처럼 잴 수 있었습니다. 이 '구불구불함'을 11차시에서 과적합이라는 이름으로 다시 만납니다.

✍️ 문제마다 답을 쓰고 제출하기를 누르세요. 제출하면 모범 답안이 열리고, 제출한 답은 선생님께 전달됩니다.