Week 5. 분류 알고리즘 — KNN, SVM, 결정트리

고전 머신러닝의 도구상자. 각 알고리즘이 "결정경계"를 그리는 방식이 어떻게 다른지 시각적으로 익힙니다.

이번 주에 배우는 것

KNN 다시 보기 — 거리·가중치·차원의 저주
SVM과 마진 최대화
커널 트릭
결정트리와 정보이득
랜덤포레스트 — 나무들의 합의

1. KNN 다시 보기 — 기억만으로 분류하기

W1에서 만난 KNN을 한 단계 더 깊이 봅니다. KNN의 매력은 "모델이 없다"는 점입니다 — 학습 단계가 사실상 "데이터를 그냥 저장"하는 것이고, 예측할 때 비로소 이웃을 찾아 투표합니다. 이런 방식을 lazy learning 또는 instance-based learning이라 부릅니다. 정반대로 로지스틱 회귀나 SVM은 학습 때 가중치를 뽑고 예측 때는 가볍게 내적만 하는 eager learning입니다.

KNN의 본질적 가정은 "비슷한 입력에는 비슷한 출력"입니다. 이것을 local smoothness assumption이라 부르며, 거의 모든 지도학습 알고리즘이 공유하는 암묵적 가정입니다. 다만 KNN은 이 가정을 극단적으로 믿어, 가까운 이웃 외엔 전혀 고려하지 않습니다.

KNN의 매력은 간단함이지만, 다음 한계도 명심해야 합니다.

차원의 저주(curse of dimensionality) — 특성 차원이 10, 100, 1000으로 늘면 "가까운 점"이라는 개념이 의미를 잃습니다. 고차원 공간에서는 모든 점이 거의 같은 거리로 서로 떨어져 있기 때문입니다. 구체적으로, $d$차원 단위 초구의 부피는 $d$가 커질수록 기하급수로 줄어들어, 표본 하나가 "이웃"의 의미를 갖기까지 필요한 데이터 수가 지수적으로 증가합니다. 이 때문에 KNN은 $d < 20$ 정도에서만 실용적이라 봅니다.
예측 비용 — 학습은 $O(1)$이지만 매 예측이 $O(Nd)$입니다. 수백만 샘플이 있으면 매 예측마다 수백만 개 거리를 재야 하므로 느립니다. kd-tree나 ball-tree 같은 공간 분할 자료구조로 $O(\log N)$까지 가속할 수 있지만, 차원이 높아지면 이마저도 효과가 줄어듭니다.
스케일 민감 — 키(cm 단위, 150~190)와 체중(kg 단위, 50~100)을 유클리드 거리로 그냥 재면 키 차이가 지배하게 됩니다. W2 §표준화에서 배운 $z$-score 표준화가 필수입니다.
이상치에 취약 — $K=1$일 때 잡음 한 점이 주변 전체를 오분류할 수 있습니다. $K$를 키우면 완화되지만 경계가 흐려집니다.

가중치 KNN(weighted KNN)을 쓰면 거리에 반비례한 가중치를 이웃에게 주어 가까운 표에 더 힘을 실어줍니다. 이로써 큰 $K$에서도 세밀함이 유지됩니다. $K$의 선택은 교차 검증(cross-validation)으로 정하는 것이 표준입니다.

실전 팁 — $K$는 보통 홀수로 잡습니다(동점 방지). 시작은 $K = \sqrt{N}$ 근처, 그 다음 교차 검증으로 ±2~3 범위를 탐색. 클래스 불균형이 심하면 가중치를 클래스 빈도의 역수로 조정하는 것도 효과적입니다.

2. SVM — 가장 넓은 도로 만들기

SVM(Support Vector Machine, Vapnik & Chervonenkis, 1963; 실용적 버전은 1995년)은 두 클래스를 가르는 수많은 직선 중에서 하나를 고르는 원칙을 명확하게 정합니다: "도로를 가장 넓게 내라". 즉 데이터가 양쪽 클래스로 가장 멀리 떨어진, 가장 두꺼운 경계 띠를 찾는 것입니다. 이 띠 위(또는 안)에 있는 점들이 서포트 벡터로, SVM은 이 몇 개의 점에만 의존해 경계를 결정합니다 — 그래서 이름이 "Support Vector" Machine.

2.1 마진 폭 유도 — 왜 $2/\|\mathbf w\|$인가

결정 경계가 $\mathbf w^\top \mathbf x + b = 0$인 초평면이라 합시다. 여기서 "도로의 폭(margin)"이란 어떤 것일까요? 경계로부터 한쪽 클래스의 가장 가까운 점까지 거리의 두 배가 도로 폭입니다.

일반성을 잃지 않고 서포트 벡터가 $\mathbf w^\top \mathbf x + b = \pm 1$을 만족하도록 $\mathbf w, b$를 스케일링할 수 있습니다. 그럼 두 초평면 $\mathbf w^\top \mathbf x + b = 1$과 $\mathbf w^\top \mathbf x + b = -1$ 사이의 거리는 점-초평면 거리 공식으로:

$$ \text{margin} = \frac{|1 - (-1)|}{\|\mathbf w\|} = \frac{2}{\|\mathbf w\|} $$

따라서 "마진을 최대화"하려면 $\|\mathbf w\|$를 최소화하면 됩니다. 수학적 편의상 $\|\mathbf w\|^2$로 바꿔도 최적해는 같으므로 표준 형태가 나옵니다:

$$ \min_{\mathbf{w}, b} \frac{1}{2}\|\mathbf{w}\|^2 \quad \text{s.t.} \quad y_i(\mathbf{w}^\top \mathbf{x}_i + b) \ge 1,\; i = 1, \dots, N $$

여기서 $y_i \in \{-1, +1\}$로 두는 관례가 로지스틱 회귀의 $\{0, 1\}$과 다르다는 점을 주의하세요. 부등식 $y_i (\mathbf w^\top \mathbf x_i + b) \ge 1$은 "모든 점이 자신의 클래스 쪽 도로 밖에 있어야 한다"는 제약입니다.

이 문제는 볼록 이차계획법(QP)이라 전역 최솟값이 유일하고, SMO 같은 효율적 알고리즘이 있습니다. 무엇보다 매력적인 점: 해는 오직 서포트 벡터들에만 의존합니다. 도로에서 멀리 떨어진 점들은 경계 결정에 전혀 영향을 주지 않습니다.

2.2 소프트 마진 — 현실의 잡음을 허용

현실 데이터는 깨끗하게 분리되지 않습니다. 몇몇 점이 도로 안으로 침범하거나 심지어 잘못된 쪽에 있을 수 있습니다. Cortes & Vapnik(1995)는 슬랙 변수(slack variable) $\xi_i \ge 0$를 도입해 위반을 허용했습니다:

$$ \min_{\mathbf{w}, b, \boldsymbol\xi} \frac{1}{2}\|\mathbf{w}\|^2 + C \sum_i \xi_i \quad \text{s.t.} \quad y_i(\mathbf{w}^\top \mathbf{x}_i + b) \ge 1 - \xi_i, \;\; \xi_i \ge 0 $$

파라미터 $C$가 "위반을 얼마나 벌줄지"를 정합니다. 두 극단:

$C \to \infty$: 하드 마진과 같음. 모든 점을 엄격히 분리 (잡음 데이터에 취약).
$C \to 0$: 위반이 공짜. 마진은 넓어지지만 많은 오분류 허용 (과소적합).

$C$는 전형적인 하이퍼파라미터로, 교차 검증으로 $10^{-3}, 10^{-2}, \dots, 10^{3}$ 같은 로그 스케일에서 탐색합니다. 편향-분산 트레이드오프의 전형적 예시입니다.

2.3 커널 트릭 — 비선형으로 확장하는 마법

SVM이 진짜로 강력해진 이유는 커널 트릭(kernel trick)입니다. 아이디어는 이렇습니다: 원래 공간에서 선형으로 분리되지 않는 데이터라도, 더 높은 차원 공간으로 "들어 올리면" 선형 분리가 가능할 수 있다. 예를 들어 원형으로 섞인 두 클래스는 2D에서 선으로 못 가르지만, $(x_1, x_2) \to (x_1, x_2, x_1^2 + x_2^2)$로 3D에 올리면 수평면 하나로 분리됩니다.

그런데 고차원에서 내적 $\phi(\mathbf x)^\top \phi(\mathbf x')$을 실제로 계산하는 것은 비쌉니다. 놀라운 발견: SVM의 해 공식에는 내적만 등장합니다 (라그랑지안 dual에서). 그래서 $\phi$를 명시적으로 계산할 필요 없이, 내적 함수(커널) $K(\mathbf x, \mathbf x') = \phi(\mathbf x)^\top \phi(\mathbf x')$만 알면 됩니다. 이걸 "커널 트릭"이라 부릅니다.

대표 커널:

선형 커널 $K(\mathbf x, \mathbf x') = \mathbf x^\top \mathbf x'$ — 기본 SVM
다항 커널 $K = (\mathbf x^\top \mathbf x' + c)^d$ — 차수 $d$만큼 비선형
RBF 커널 (가우시안) $K = \exp(-\gamma\|\mathbf x - \mathbf x'\|^2)$ — 가장 널리 쓰임, 무한차원 공간에 대응
시그모이드 커널 $K = \tanh(\alpha \mathbf x^\top \mathbf x' + c)$ — 신경망 흉내

RBF 커널의 파라미터 $\gamma$는 "국소성"을 조절합니다 — 크면 각 샘플 주변만 영향을 미쳐 복잡한 경계가 가능하지만 과적합 위험이, 작으면 경계가 부드러워집니다.

역사적 한 토막 — 1990년대 후반부터 2010년대 초반까지 SVM은 머신러닝의 "황제"였습니다. 작은 데이터셋, 고차원 입력(텍스트, 생물정보), 수학적 엄밀함에서 타의 추종을 불허했습니다. 딥러닝이 2012년 이후 시각·음성·자연어를 차례로 장악하면서 주류 자리를 내줬지만, 여전히 작은 데이터·고해석성이 필요한 분야에서 첫 선택지입니다.

🎮 인터랙티브: SVM 마진 (소프트 vs 하드)

두 가우시안 클러스터를 분리하는 SVM의 마진을 그립니다. C 슬라이더로 마진의 폭이 어떻게 달라지는지 봅니다(시각화 단순화 버전).

C (위반 비용) 1

커널 트릭. 데이터가 직선으로 안 갈리면 RBF 같은 커널 함수로 고차원 공간에 매핑한 뒤 그 공간에서 직선을 긋습니다. 실제로 고차원으로 가지 않고 내적만 계산하기 때문에 "트릭"입니다.

3. 결정트리

"먼저 길이가 20cm 이상인가? 그렇다면 무게가 300g 이상인가? ..." 이런 식으로 질문을 가지치며 분류하는 모델입니다. 인간이 이해하기 쉽다는 큰 장점이 있습니다.

각 노드에서 어떤 질문이 가장 좋은지는 지니 불순도나 엔트로피로 측정합니다.

$$ G = 1 - \sum_k p_k^2, \quad H = -\sum_k p_k \log p_k $$

분할 후 불순도가 가장 많이 줄어드는 질문을 고릅니다(정보이득).

🎮 인터랙티브: 결정트리 영역 분할

2D 데이터를 단계별로 수직/수평선으로 나눕니다. 깊이가 깊어질수록 영역이 잘게 쪼개집니다.

최대 깊이 3

3.1 어떤 질문이 좋은 질문인가 — 분할 기준

결정트리의 핵심 질문: "어느 특징의 어느 값을 기준으로 나눠야 가장 효율적인가?" 이를 정량화하는 두 가지 기준이 표준입니다.

지니 불순도(Gini impurity)는 "노드에서 무작위로 뽑은 두 샘플이 서로 다른 클래스일 확률"을 측정합니다:

$$ \text{Gini}(t) = 1 - \sum_{k=1}^K p_k^2 $$

$p_k$는 노드 $t$에서 클래스 $k$의 비율. 완벽히 순수한 노드(한 클래스만)는 $\text{Gini} = 0$, 두 클래스가 50:50이면 $\text{Gini} = 0.5$(최대).

정보 엔트로피(entropy)는 정보 이론에서 온 기준입니다:

$$ H(t) = -\sum_{k=1}^K p_k \log_2 p_k $$

순수하면 0, 균등하면 $\log_2 K$. 한 번의 분할이 제공하는 정보 이득(information gain)은 부모 엔트로피 빼기 자식 엔트로피의 가중 평균입니다. 트리는 매 분할에서 정보 이득이 가장 큰 질문을 탐욕적으로 고릅니다.

실전에서 지니와 엔트로피는 거의 같은 결과를 냅니다(지니가 약간 빠름). CART 알고리즘은 지니, ID3/C4.5는 엔트로피를 씁니다.

3.2 과적합과 가지치기

트리를 깊게 키우면 훈련 데이터를 완벽히 외웁니다 (순수 리프 = 0 오차). 하지만 새 데이터에 대한 성능은 급격히 떨어집니다. 과적합의 전형입니다. 해법:

사전 가지치기(pre-pruning) — 최대 깊이 제한, 리프당 최소 샘플 수 제한, 최소 정보 이득 한계 설정.
사후 가지치기(post-pruning) — 전체를 키운 뒤 검증 셋으로 "덜 유용한 가지"를 되돌리며 제거.

트리의 또 다른 한계는 불안정성입니다. 데이터를 약간만 바꿔도 전혀 다른 트리가 나올 수 있습니다. 이 단점이 오히려 다음 섹션 "랜덤포레스트"의 강점이 됩니다 — 다양성이 앙상블에 필요한 원료가 되니까요.

4. 랜덤포레스트 — 나무들의 민주주의

나무 하나는 약하고 흔들리기 쉽지만 백 그루가 모이면 안정된 숲이 됩니다. 랜덤포레스트(Random Forest, Breiman 2001)는 여러 결정트리를 독립적으로 만들고 다수결(분류) 또는 평균(회귀)으로 결과를 냅니다. 각 트리의 편향은 그대로지만 분산이 평균화로 줄어들기 때문에 전체 성능은 크게 향상됩니다.

그런데 단순히 같은 알고리즘을 여러 번 돌리면 모든 트리가 똑같아져 앙상블 효과가 없습니다. 따라서 다양성을 강제로 주입하는 두 장치가 핵심:

배깅(Bagging, Bootstrap Aggregating) — 각 트리를 학습할 때 전체 $N$개 데이터에서 복원추출로 $N$개를 뽑아 씁니다. 약 63.2%의 데이터만 각 트리에 들어가고, 나머지는 자연스럽게 out-of-bag 검증 셋이 됩니다.
특성 무작위화 — 각 분할에서 전체 특성 중 $\sqrt d$ 또는 $\log d$ 개만 후보로 고려. 이로써 지배적인 한두 특성이 모든 트리에 반복 등장하지 못하게 막아 트리들의 다양성을 확보합니다.

랜덤포레스트는 과적합에 강하고, 특성 스케일에 민감하지 않으며, 결측치와 범주형 변수를 자연스럽게 다루고, "기본 하이퍼파라미터"가 거의 동작합니다. 그래서 "뭘 쓸지 모를 때 먼저 돌려보는" 베이스라인으로 오랫동안 사랑받았습니다. 최근에는 XGBoost, LightGBM 같은 그래디언트 부스팅 트리가 캐글 경진에서 더 자주 승리하지만, 랜덤포레스트는 여전히 해석과 빠른 프로토타입에서 최고 선택입니다.

특성 중요도 — 랜덤포레스트의 또 다른 매력은 각 특성이 평균적으로 얼마나 불순도를 줄였는지를 계산해 특성 중요도(feature importance)를 제공한다는 점입니다. 이 덕분에 "어떤 변수가 예측에 큰 역할을 했나"를 쉽게 볼 수 있어 의료, 금융처럼 해석이 중요한 분야에서 많이 쓰입니다.

5. 코드 예제

from sklearn.svm import SVC
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import RandomForestClassifier

svm = SVC(C=1.0, kernel='rbf').fit(X_tr, y_tr)
dt  = DecisionTreeClassifier(max_depth=4).fit(X_tr, y_tr)
rf  = RandomForestClassifier(n_estimators=100).fit(X_tr, y_tr)

for m in [svm, dt, rf]:
    print(type(m).__name__, m.score(X_te, y_te))

📖 더 깊이 공부하기

The Elements of Statistical Learning — Hastie 외, 9·15장. 트리와 SVM의 결정판.
scikit-learn SVM 가이드 — 공식 문서. 커널 종류와 C·γ의 의미.
Random Forests — Leo Breiman 원논문(2001).
Visual Intro to Decision Trees — r2d3.us. 결정트리 시각화의 명작.