13강 / 20강

이웃과 경계 — 가장 가까운 것 · 가장 넓은 틈

k-이웃과 SVM, 그리고 차원의 저주

두 가지 발상이 더 있습니다. 둘 다 거리를 씁니다.

k-이웃

"가장 가까운 k 명이 뭐라고 하는지 본다"
훈련이 없다 — 자료를 그냥 들고 있는다

서포트 벡터 머신

"두 무리 사이 가장 넓은 틈의 한가운데로 선을 긋는다"
경계에 붙은 몇 점만 결정에 참여한다

고등학생가장 가까운 것 · 가장 넓은 틈

발상이 정반대인 두 모형입니다.

모형	발상
k-이웃	비슷한 것끼리 답도 비슷할 것
SVM	두 무리를 가르는 가장 넓은 틈

하나는 이웃을 본다, 하나는 경계를 긋는다

k-이웃 — 학습이 없다

놀랍게도 훈련 단계가 없습니다. 자료를 그냥 저장해 두죠.

단계	k-이웃
훈련	저장만 — 0초
예측	전부와 거리 계산 — 느리다 ⚠

비용을 예측 시점으로 미룬 것 — 게으른 학습

k 를 몇으로 할까

k	성격
1	가장 가까운 하나 — 잡음에 약하다
중간	적당 ✔
매우 큼	전체 다수결 — 세부를 놓친다

또 그 U 자 곡선 — 5강의 과적합 축이 k 로 나타났다

SVM — 왜 '넓은 틈' 인가

두 무리를 가르는 선은 무한히 많습니다. 그중 양쪽에서 가장 멀리 떨어진 선을 고릅니다.

여유가 넓을수록 새 점이 와도 잘 갈린다

비유하자면 — 길을 낼 때 벽에 붙여 내지 않고 가운데로 내는 것과 같아요.

k=1 은 훈련 정확도 <b>1.000</b> 입니다. 자기 자신이 가장 가까운 이웃이니까요.

Python 브라우저에서 실행

# k-이웃 - k 를 바꾸면 무엇이 달라지나
import numpy as np
rng = np.random.default_rng(151)

def make(n, r):
    X = r.normal(0, 1, (n, 2))
    y = (X[:,0] + X[:,1] > 0).astype(int)
    flip = r.random(n) < 0.10
    return X, np.where(flip, 1-y, y)

Xtr, ytr = make(200, rng)
Xte, yte = make(2000, np.random.default_rng(7))

def knn(Xtr, ytr, Xte, k):
    out = np.empty(len(Xte), int)
    for i, x in enumerate(Xte):
        d = ((Xtr - x)**2).sum(1)
        nb = np.argpartition(d, k)[:k]
        out[i] = int(ytr[nb].mean() > 0.5)
    return out

print("  k     훈련 정확도   시험 정확도")
for k in [1, 3, 9, 25, 75, 150]:
    tr = knn(Xtr, ytr, Xtr, k)
    te = knn(Xtr, ytr, Xte, k)
    print(f"  {k:3d}    {(tr==ytr).mean():9.3f}   {(te==yte).mean():9.3f}")
print()
print("k=1 은 훈련 정확도가 1.000 이다 - 자기 자신이 가장 가까우니까.")
print("그런데 시험에서는 잡음까지 따라가 손해다. 전형적인 과적합이다(5강).")
print("k 가 너무 크면 이번엔 뭉개진다.")
print()
print("k 도 초매개변수다 - 교차검증으로 고른다(6강).")

고등학생거리를 잰다는 것

k-이웃의 전부는 거리입니다. 그런데 거리를 재는 데 전제가 숨어 있어요.

"가깝다" 는 것은 비슷하다는 뜻이어야 한다

그게 깨지는 경우

문제	결과
눈금이 다르다 (3강)	큰 숫자 특징이 거리를 지배
무의미한 특징이 많다	잡음이 거리에 더해진다
범주형 특징	거리가 정의되지 않는다

k-이웃은 표준화가 필수다 — 안 하면 거의 무의미하다

무의미한 특징이 왜 해로운가

거리는 모든 축을 더합니다. 쓸모없는 축이 100개면 그 잡음이 100개분 더해지죠.

축	거리 기여
의미 있는 축 5개	신호
무의미한 축 1000개	잡음이 압도 ⚠

특징을 많이 넣을수록 좋은 게 아니다 — 오히려 반대다

비유 — 사람 닮음 판단

두 사람이 얼마나 닮았나 를 잽니다.

비교 항목	결과
얼굴 특징 5가지	의미 있는 판단 ✔
+ 신발 크기 · 좋아하는 색 · 1000가지	닮음이 희석된다 ⚠

관계없는 항목을 더할수록 진짜 닮음이 묻힌다

이게 다음에 나올 차원의 저주입니다.

고등학생차원의 저주 — '가까움' 이 뜻을 잃는다

note 의 이 경고가 고차원 자료의 근본 문제입니다.

차원이 높아지면 모든 점이 서로 멀어진다 — 그리고 비슷하게 멀다

숫자로 보면

무작위 점들 사이 거리의 최대/최소 비를 봅시다.

차원	가장 먼 것 / 가장 가까운 것
2	크다 — 구별된다
10	줄어든다
1000	거의 1 — 다 비슷하다 ⚠

"가장 가까운 이웃" 이 가장 먼 것과 비슷하게 멀다

왜 그런가 — 직관

차원이 늘 때마다 거리에 항이 하나씩 더해집니다. 차이가 쌓여서 다들 멀어져요.

그리고 평균 주위로 몰립니다. 1000개 항의 합은 큰 수의 법칙으로 안정되니까요.

거리의 분산이 줄어든다 — 그래서 구별력이 사라진다

비유 — 넓은 사막에 흩어진 사람들

공간	"가까운 사람"
작은 방	의미가 있다
거대한 사막	전부 아득히 멀다 — 순위가 무의미

공간이 넓어지면 "이웃" 이라는 말이 뜻을 잃는다

그래서 대책

대책	강
특징을 줄인다	11강 L1 · 선택
차원 축소	14강 ⭐
거리를 안 쓰는 모형	12강 나무

3강의 "환자 100명 · 유전자 2만 개" 자료에서 k-이웃은 대개 나쁜 선택이다

차원이 오르면 <b>가장 가까운 점과 가장 먼 점이 비슷해집니다</b>.

Python 브라우저에서 실행

# 차원이 높아지면 '가장 가까움' 이 뜻을 잃는다
import numpy as np
rng = np.random.default_rng(161)

print("점 1,000개를 무작위로 뿌리고, 한 점에서 나머지까지의 거리를 본다")
print()
print("  차원     가장 가까움   가장 멂    (멂-가까움)/가까움")
for p in [2, 5, 20, 100, 500, 2000]:
    X = rng.normal(0, 1, (1000, p))
    d = np.sqrt(((X[1:] - X[0])**2).sum(1))
    lo, hi = d.min(), d.max()
    print(f"  {p:5d}    {lo:10.2f}  {hi:8.2f}    {(hi-lo)/lo:14.3f}")
print()
print("오른쪽 칸이 0 으로 간다 - 가장 가까운 점과 가장 먼 점이 비슷해진다.")
print("'가장 가까운 이웃' 이라는 말 자체가 뜻을 잃는 것이다.")

🤔 확인 문제

유전자 2만 개를 특징으로 k-이웃 분류기를 만들었더니 성능이 찍기 수준입니다. 가장 그럴듯한 원인은?