왜 “거리”로 분류하는가 — K-NN의 아이디어

K-최근접 이웃(K-Nearest Neighbors, K-NN)은 새로운 데이터가 어떤 클래스인지 알고 싶을 때, “이 점과 가장 가까운 이웃 $k$개는 어떤 클래스인가”를 보고 다수결로 정하는 알고리즘입니다. 결정트리(11편)처럼 규칙을 학습하는 것도 아니고, 로지스틱 회귀(10편)처럼 수식의 계수를 학습하는 것도 아닙니다. K-NN은 훈련 데이터를 통째로 기억해 두었다가, 새 데이터가 들어올 때마다 그때그때 거리를 재서 판단하는 게으른 학습(Lazy Learning, 미리 모델을 만들어두지 않고 예측 시점에 계산하는 방식)입니다.

쉽게 말하면: K-NN은 “네 주변에 누가 사는지 보면 네가 어떤 사람인지 알 수 있다”는 생각을 그대로 계산으로 옮긴 것입니다.

1. 거리 계산 — 실제 좌표로 유클리드와 맨해튼

2차원 평면에 A반(클래스 A) 학생 3명과 B반(클래스 B) 학생 3명의 좌표(예: 수학 점수, 영어 점수를 정규화한 값)가 있고, 새로 전학 온 학생 $q$의 반을 예측하려 합니다.

유클리드 거리(Euclidean Distance, 두 점을 잇는 직선 거리)는 다음과 같이 계산합니다.

각 점에 대해 $q=(3,3)$까지의 거리를 계산합니다.

맨해튼 거리(Manhattan Distance, 바둑판 모양 도로를 격자 방향으로만 이동한 거리, 택시 거리라고도 함)는 각 축의 차이를 절댓값으로 더합니다.

결과를 정리하면:

결과 해석 — 거리 기준에 따라 순위가 달라진다: 유클리드 거리로는 A2(1.414)가 가장 가깝고 A3와 B3가 2.000으로 동률입니다. 그런데 맨해튼 거리로는 A2, A3, B3 세 점이 모두 2로 동률이 됩니다. 즉 같은 좌표라도 어떤 거리 척도를 쓰느냐에 따라 순위와 동률 여부가 달라질 수 있다는 것이 K-NN의 중요한 함정입니다. 좌표 축의 스케일이 서로 다른 특징(예: 나이는 0100, 연봉은 0100000000)을 그대로 쓰면 거리가 큰 스케일의 특징에 지배되므로, K-NN을 쓰기 전에는 반드시 06편의 스케일링(정규화·표준화)을 거쳐야 합니다.

2. k값에 따른 분류 — 편향-분산 트레이드오프

유클리드 거리 기준으로 가까운 순서는 A2(1.414) → A3=B3(2.000, 동률) → B1(2.236) → A1(2.828) → B2(4.243)입니다.

• $k=1$: 가장 가까운 1개는 A2 하나뿐이므로 동률 문제 없이 바로 클래스 A로 예측합니다.
• $k=3$: 가까운 3개를 뽑으면 A2, 그리고 공동 2등인 A3와 B3가 함께 포함되어 (A2, A3, B3) = A 2표, B 1표로 클래스 A가 다수결 승리합니다.
• $k=5$: 다섯 번째까지 포함하면 (A2, A3, B3, B1, A1) = A 3표, B 2표로 여전히 클래스 A가 다수결 승리합니다.

이 예제는 우연히 $k$를 바꿔도 결과가 같지만, $k$가 커질수록 더 먼 점들까지 투표에 참여시키므로 결과가 흔들릴 여지가 커집니다. 이것이 편향-분산 트레이드오프(Bias-Variance Trade-off, 19편에서 이론적으로 더 깊이 다룸)로 이어집니다.

쉽게 말하면: $k=1$은 “바로 옆집 한 곳만 보고 판단”해서 예민하고(분산이 큼), $k$가 아주 크면 “동네 전체 여론을 따라가서” 둔감해집니다(편향이 큼).

자주 틀리는 함정 — 짝수 k의 동률 문제: 이진분류에서 $k$를 짝수로 두면(예: $k=6$, 전체 데이터 수와 같음) 투표가 3:3처럼 정확히 반으로 갈려 다수결을 결정할 수 없는 상황이 생길 수 있습니다. 그래서 이진분류에서는 관례적으로 $k$를 홀수로 설정해 동률을 피합니다.

3. SVM — 마진을 최대로 벌리는 경계선

서포트 벡터 머신(Support Vector Machine, SVM)은 두 클래스를 나누는 경계선을 그리되, 단순히 나누기만 하는 것이 아니라 경계선에서 양쪽 클래스까지의 여백(마진)을 가장 넓게 만드는 경계선을 찾습니다.

쉽게 말하면: SVM은 두 클래스 사이에 “가장 넓은 도로”를 놓고, 그 도로의 정중앙 선을 결정경계로 삼습니다.

결정경계는 $w \cdot x + b = 0$ 형태이며, 마진의 폭은 다음과 같이 계산됩니다.

• $\lVert w \rVert$ (노름): 계수 벡터 $w$의 길이(크기), $w=(w_1,w_2,\dots)$이면 $\lVert w \rVert=\sqrt{w_1^2+w_2^2+\cdots}$

서포트 벡터(Support Vector)는 이 도로의 양쪽 가장자리에 정확히 걸쳐 있는, 경계선에 가장 가까운 데이터 점들입니다. 마진을 결정짓는 것은 오직 이 서포트 벡터들뿐이며, 도로에서 멀리 떨어진 다른 점들은 경계선의 위치에 전혀 영향을 주지 않습니다.

실제 숫자로 확인해 보겠습니다. $w=(1,1)$, $b=0$인 결정경계가 있고, 점 $(1,0)$은 양성 클래스의 서포트 벡터, 점 $(-1,0)$은 음성 클래스의 서포트 벡터라고 합시다.

서포트 벡터는 $y_i(w\cdot x_i+b)=1$을 만족해야 하는데, 양성 점은 $1\times1=1$, 음성 점은 $(-1)\times(-1)=1$로 두 점 모두 조건을 정확히 만족합니다. 이때 마진의 폭은 다음과 같습니다.

결과 해석: $w$의 크기가 작을수록(계수가 작을수록) 마진 $2/\lVert w\rVert$은 커집니다. 즉 SVM이 “마진을 최대화”한다는 것은 수식으로 보면 “$\lVert w\rVert$를 최소화”하는 것과 같은 문제입니다.

4. 하드 마진과 소프트 마진

데이터가 실제로는 완벽하게 두 그룹으로 깔끔히 갈리지 않는 경우가 대부분입니다. 이때 SVM이 오차를 허용하는 정도에 따라 두 가지로 나뉩니다.

자주 틀리는 점: “$C$가 클수록 항상 좋은 모델이다”라는 설명은 틀렸습니다. $C$는 09편의 정규화 강도 $\lambda$와 반대 방향으로 작동하는 하이퍼파라미터로, $C$가 지나치게 크면 훈련 데이터의 이상치까지 정확히 맞추려다 과적합이 발생합니다.

5. 커널 트릭 — 선형으로 못 나누는 데이터 다루기

두 클래스가 직선(또는 평면)으로 절대 나뉘지 않는 경우가 있습니다. 대표적인 예가 XOR 문제입니다.

이 4개의 점은 2차원 평면 위에서 어떤 직선을 그어도 클래스 0과 1을 완전히 나눌 수 없습니다. 그런데 여기에 새로운 특징 $x_3=x_1 \times x_2$를 추가하면, $(0,0)\to x_3=0$, $(1,1)\to x_3=1$, $(0,1)\to x_3=0$, $(1,0)\to x_3=0$이 되어 새로운 차원에서는 선형으로 분리할 실마리가 생깁니다.

커널 트릭(Kernel Trick)은 이처럼 데이터를 더 높은 차원으로 옮기면 선형 분리가 가능해질 수 있다는 아이디어를, 실제로 높은 차원의 좌표를 일일이 계산하지 않고도 커널 함수(Kernel Function)라는 지름길 계산으로 그 효과만 얻어내는 방법입니다.

쉽게 말하면: 커널 트릭은 “2차원에서는 안 갈리는 두 무리를, 3차원(또는 그 이상)으로 튕겨 올려서 갈라놓고, 그 계산을 지름길로 빠르게 해내는 것”입니다.

6. K-NN과 SVM 비교 및 판단 흐름

핵심 정리

• K-NN은 새 데이터와 훈련 데이터 사이의 거리(유클리드·맨해튼 등)를 계산해 가장 가까운 $k$개의 다수결로 클래스를 정하는 게으른 학습이며, 스케일링이 필수다.
• $k$가 작을수록 분산이 크고(노이즈에 민감), $k$가 클수록 편향이 커진다(지역 패턴을 놓침). 이진분류에서는 동률을 피하기 위해 $k$를 홀수로 둔다.
• SVM은 마진 $2/\lVert w\rVert$을 최대화하는 결정경계를 찾으며, 마진 경계에 걸친 점만이 서포트 벡터로서 경계 위치를 결정한다.
• 하드 마진은 오차를 전혀 허용하지 않고, 소프트 마진은 하이퍼파라미터 $C$로 오차 허용 정도를 조절한다.
• 커널 트릭은 데이터를 더 높은 차원으로 옮겨 선형 분리가 가능해지는 효과를, 실제 고차원 좌표 계산 없이 커널 함수로 얻어낸다.

마무리 복습

참고 자료

• scikit-learn User Guide — Nearest Neighbors, Support Vector Machines 
• In-depth Comparison of Supervised Classification Models