k-최근접 이웃(kNN) 분류기 계산기

새 점을 분류할 때, 훈련 데이터 중 가장 가까운 k개의 점을 찾아 그 점들의 라벨 중 다수를 따르는 방법입니다. "유유상종" — 비슷한 위치에 있는 것들은 같은 부류일 것이라는 직관을 그대로 계산으로 옮긴 것입니다.

퍼셉트론·로지스틱 회귀·나이브 베이즈는 훈련 데이터로 경계선(가중치)을 먼저 구해 두고, 그다음부터는 새 점이 와도 그 경계선만 보고 즉시 분류합니다. kNN은 그런 학습 단계가 아예 없습니다 — 새 점이 올 때마다 훈련 데이터 전체와 거리를 다시 재서 그때그때 다수결을 냅니다("게으른 학습").

k=1이면 가장 가까운 점 하나만 보므로 훈련 데이터의 잡음에도 경계가 쉽게 흔들립니다(과적합). k를 늘리면 여러 점의 다수 의견을 따르게 되어 경계가 매끄러워지지만, 너무 크면 지역적인 패턴을 놓치고 전체 다수 라벨 쪽으로 쏠립니다(과소적합). 보통 홀수를 쓰고 데이터로 여러 값을 시험해 고릅니다.

표를 가장 많이 받은 라벨이 둘 이상이면 그 라벨을 가진 이웃들의 평균 거리가 더 가까운 쪽을 고릅니다. 그마저 같으면 라벨 이름의 사전순으로 정합니다 — 결과가 입력 순서에 좌우되지 않도록 완전히 결정적으로 정합니다.

voronoi-cell은 라벨 없이 "어느 사이트가 가장 가까운가"만 판정하는 순수 기하 문제입니다. 이 도구는 각 점에 라벨이 있고 그 라벨을 다수결로 예측하는 분류(머신러닝) 문제라는 점이 다릅니다.