질문을 반복해 데이터를 쪼개는 결정 트리

선형 모델은 $w \cdot x + b = 0$ 이라는 직선 하나로 공간을 가른다. 다항 특성을 붙이면 곡선이 되기는 하지만, 경계의 모양을 수식이 미리 정해둔다는 점은 그대로다.

결정 트리는 수식 대신 질문을 쓴다. “꽃잎 길이가 2.45cm 이하인가?”로 데이터를 두 덩어리로 가르고, 각 덩어리에 또 질문을 던진다. 질문이 쌓이면서 범위가 좁아지고 더 나눌 것이 없어진 지점에서 답을 내놓는다. 사람이 판단을 좁혀가는 방식과 거의 같아서, 학습이 끝난 모델을 그림 한 장으로 펼쳐놓고 왜 그렇게 예측했는지 따라갈 수 있다.

트리를 이루는 노드

Iris 데이터를 깊이 2까지만 키우면 트리는 이런 모양이 된다.

루트의 150개가 50개와 100개로 갈리고, 오른쪽 100개가 다시 54개와 46개로 갈린다. 노드는 세 종류다.

각 노드가 담는 조건은 언제나 특성 하나 + 임계값 하나다. 데이터 포인트는 예/아니오로 답하며 리프까지 내려가고, 도착한 리프의 다수 클래스가 예측값이 된다.

좋은 분할이란 무엇인가

트리가 풀어야 할 문제는 하나다. 어떤 특성의 어떤 임계값으로 쪼갤 것인가. 가능한 조합을 전부 시도해보고 가장 좋은 것을 고른다.

좋은 분할은 나뉜 두 그룹이 더 순수해지는 분할이다. 한 그룹 안에 같은 클래스끼리 모일수록 좋다. 이 순수도를 재는 자가 지니 불순도와 엔트로피다.

지니 불순도

노드 $t$에서 임의로 샘플 하나를 뽑고, 그 노드의 클래스 비율대로 무작위 레이블을 붙였을 때 틀릴 확률이 지니 불순도다.

$G(t) = 1 - \sum_{i} p_i^2$

$p_i$ 는 노드 $t$ 안에서 클래스 $i$ 가 차지하는 비율이다. 어떤 샘플이 실제로 클래스 $i$ 일 확률이 $p_i$ 이고 그 샘플에 클래스 $i$ 를 붙일 확률도 $p_i$ 이므로, 맞힐 확률은 $\sum_i p_i^2$ 이고 1에서 빼면 틀릴 확률이 된다.

def gini(counts):
    total = sum(counts)
    return 1 - sum((c / total) ** 2 for c in counts)

gini([50, 50, 50])   # 루트  0.6667
gini([50, 0, 0])     # 왼쪽  0.0
gini([0, 50, 50])    # 오른쪽 0.5

분할의 좋고 나쁨은 자식 노드들의 가중 평균 불순도가 부모보다 얼마나 낮아졌는지로 잰다.

$\Delta G = G(\text{parent}) - \sum_j \frac{n_j}{n} \, G(\text{child}_j)$

Iris의 첫 분할에 넣어보면 $\frac{50}{150} \times 0 + \frac{100}{150} \times 0.5 = 0.3333$ 이고, 루트의 0.6667에서 정확히 절반이 줄었다. 이 조합이 모든 후보 중 감소량이 가장 크므로 트리는 이것을 첫 질문으로 택한다.

엔트로피와 정보 이득

순수도를 재는 자는 하나 더 있다. 정보 이론에서 가져온 엔트로피는 노드의 불확실성을 잰다.

$H(t) = -\sum_i p_i \log_2 p_i$

확률이 낮은 사건일수록 놀라움이 크고, 그 놀라움의 크기를 $-\log_2 p$ 로 정의한다. 엔트로피는 이 놀라움의 기대값이다. 클래스가 고르게 섞여 있으면 다음에 무엇이 나올지 모르니 엔트로피가 최대가 된다.

분할 전후 엔트로피의 감소량이 정보 이득이다.

$IG = H(\text{parent}) - \sum_j \frac{n_j}{n} \, H(\text{child}_j)$

같은 첫 분할을 넣으면 루트가 $\log_2 3 = 1.585$ 비트, 왼쪽이 0비트, 오른쪽이 1비트다. 가중 평균은 $\frac{100}{150} \times 1 = 0.667$ 비트이고, 정보 이득은 0.918비트다.

둘 다 $p = 0$ 이나 $p = 1$ 에서 0이고 $p = 0.5$ 에서 최대다. 최댓값은 엔트로피가 1, 지니가 0.5로 두 배 차이가 나지만, 어느 분할이 더 나은지를 두고는 거의 항상 같은 답을 낸다.

성능 차이는 실무에서 거의 없다. 기본값인 지니를 그대로 쓰면 된다.

분할을 직접 찾아보기

트리가 최적 분할을 찾는 과정은 특별한 기교 없이 전수 탐색이다. 특성 하나를 골라, 그 특성이 가진 값들을 임계값 후보로 놓고, 전부 계산해서 가장 많이 줄어드는 조합을 남긴다.

import numpy as np
from sklearn.datasets import load_iris

def gini(y):
    if len(y) == 0:
        return 0
    _, counts = np.unique(y, return_counts=True)
    return 1 - np.sum((counts / len(y)) ** 2)

def best_split(X, y):
    best = (-1, None, None)
    g_parent = gini(y)
    for f in range(X.shape[1]):
        for t in np.unique(X[:, f]):
            left = X[:, f] <= t
            if left.sum() == 0 or (~left).sum() == 0:
                continue
            n_l, n_r = left.sum(), (~left).sum()
            g = (n_l * gini(y[left]) + n_r * gini(y[~left])) / len(y)
            if g_parent - g > best[0]:
                best = (g_parent - g, f, t)
    return best

iris = load_iris()
gain, feat, thresh = best_split(iris.data, iris.target)
print(f"{iris.feature_names[feat]} <= {thresh:.2f}, 감소량 {gain:.4f}")

petal length (cm) <= 1.90, 감소량 0.3333

꽃잎 길이 1.90cm가 답으로 나온다. sklearn은 후보 값과 그 다음 값의 중간점을 쓰기 때문에 2.45로 표시하지만, setosa의 최대 꽃잎 길이가 1.9이고 versicolor의 최소가 3.0이라 두 값은 정확히 같은 분할을 만든다.

특성이 $m$ 개, 각 특성의 고유값이 평균 $n$ 개면 노드 하나당 $O(mn)$ 번의 불순도 계산이 든다. sklearn은 특성을 한 번 정렬해두고 임계값을 옮겨가며 클래스 카운트를 증분 갱신해서 이 비용을 줄인다.

결정 경계가 계단 모양인 이유

분할 조건이 늘 “특성 하나 $\le$ 임계값” 이라는 것은 곧 결정 경계가 축에 평행한 직선뿐이라는 뜻이다. 깊이 2 트리가 꽃잎 길이와 꽃잎 너비 평면을 나누는 모습을 그려보면 이렇다.

리프 하나가 영역 하나에 대응한다. 깊이를 늘리면 영역이 더 잘게 쪼개지면서 경계가 계단처럼 촘촘해진다. 같은 두 특성으로 깊이 제한 없이 키우면 리프가 셋에서 여덟으로 늘어난다.

새로 생긴 다섯 영역 중 셋은 꽃잎 너비 1.75 바로 아래에 깔린 좁은 띠를 세 조각으로 자른 것이고, 조각마다 훈련 샘플이 한두 개씩만 들어 있다. 이런 영역은 그 안에 들어온 몇 개 점의 위치가 그대로 규칙이 된 것이라, 데이터가 조금만 달라져도 사라지거나 자리를 옮긴다. 과적합이 결정 경계에 드러나는 모습이 이것이다.

45도로 기운 경계가 필요한 문제라면 트리는 그것을 계단으로 근사해야 하고, 그만큼 분할이 많이 필요해진다. 반대로 특성 축이 곧 의미 있는 기준인 데이터(임계값이 실제로 존재하는 센서 값, 나이 구간 등)에서는 이 제약이 오히려 잘 맞는다.

과적합과 규제

깊이 제한이 없으면 트리는 모든 리프가 순수해질 때까지 쪼갠다. 클래스가 섞인 구석마다 분할을 하나씩 더 붙이는 셈이라 훈련 데이터의 잡음까지 규칙으로 새긴다. 깊이를 3으로 묶으면 훈련 점수를 조금 내주는 대신 그 암기를 막는다.

from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split

X_train, X_test, y_train, y_test = train_test_split(
    iris.data, iris.target, test_size=0.3, random_state=42
)

clf = DecisionTreeClassifier(max_depth=3, random_state=42).fit(X_train, y_train)
print(f"훈련 {clf.score(X_train, y_train):.4f} / 테스트 {clf.score(X_test, y_test):.4f}")

훈련 0.9524 / 테스트 1.0000

깊이를 바꿔가며 재보면 훈련 정확도는 단조롭게 오른다. 훈련·테스트 열은 위와 같은 7:3 분할에서, 교차검증 열은 나누지 않은 150건 전체에 cross_val_score(..., cv=5)를 돌려 얻은 값이고, 트리는 모두 random_state=42다.

Iris는 클래스가 잘 갈라져 있어서 테스트 정확도가 떨어지지 않지만, 교차검증 평균을 보면 깊이 3 이후로 오히려 낮아진다. 노이즈가 섞인 실제 데이터에서는 이 하락이 훨씬 뚜렷하게 나타난다. 훈련 점수 하나만 보고 깊이를 정하면 반드시 과적합 쪽으로 넘어간다.

주로 쓰는 규제 파라미터는 다음과 같다.

학습된 트리 읽기

plot_tree로 그린 그림에서 내부 노드 하나는 다섯 줄로 표시된다. 리프는 분할 조건이 없어 네 줄이다.

from sklearn.tree import plot_tree

plot_tree(clf, feature_names=iris.feature_names,
          class_names=iris.target_names, filled=True, rounded=True)

위에서 학습한 깊이 3 트리의 루트는 이렇게 찍힌다.

이 루트는 versicolor와 virginica가 37개로 동점인데, sklearn은 이럴 때 클래스 순서가 앞선 쪽을 택한다. filled=True를 주면 다수 클래스에 따라 노드 색이 달라지고, 색이 진할수록 순수한 노드다. 예측이 이상할 때 이 그림을 따라 내려가면 어느 분할에서 갈라졌는지 바로 보인다.

자주 하는 실수

스케일링을 붙인다. 트리는 “특성 값 $\le$ 임계값” 비교만 하므로 값의 순서가 유지되는 변환에는 완전히 불변이다. StandardScaler를 파이프라인에 넣어도 결과가 한 자리도 바뀌지 않는다. 로지스틱 회귀나 SVM에서 몸에 밴 습관이 그대로 넘어오는 자리다.

클래스 불균형을 그냥 둔다. 사기 탐지처럼 양성이 1%인 데이터에서는 소수 클래스를 통째로 무시해도 불순도가 거의 줄어들지 않아, 트리가 다수 클래스만 맞히는 쪽으로 자란다. class_weight='balanced'를 주면 각 클래스에 $n / (K \cdot n_k)$ 만큼 가중치가 붙어 불순도 계산에서 소수 클래스의 몫이 커진다.

clf_balanced = DecisionTreeClassifier(class_weight='balanced', random_state=42)

마치며

결정 트리의 학습은 결국 한 문장으로 줄어든다. 불순도를 가장 많이 줄이는 분할을 탐욕적으로 반복한다. 지니와 엔트로피는 그 불순도를 재는 두 가지 자일 뿐이고, 어느 쪽을 쓰든 트리의 모양은 거의 같다.

이 단순함이 강점과 약점을 한꺼번에 만든다. 값의 순서만 보므로 스케일링에 손댈 일이 없고, 학습된 규칙을 그대로 읽을 수 있다. 대신 매 단계 눈앞의 이득만 보고 고르기 때문에 위쪽 분할 하나가 바뀌면 그 아래가 전부 다시 그려진다.

그래서 실무에서 단일 트리를 그대로 쓰는 일은 드물다. 다음 글에서는 트리 여러 그루를 학습해 예측을 합치는 방법으로 이 분산을 줄인다.

함께 보면 좋은 글

• 편향-분산 트레이드오프 : 트리가 왜 고분산 모델로 분류되는지
• 앙상블 학습과 배깅 : 트리 여러 그루를 합쳐 분산을 줄이는 원리
• 랜덤 포레스트 : 트리마다 후보 특성을 달리해 상관관계를 낮추는 방법

참고자료

• Scikit-learn Decision Trees User Guide
• Scikit-learn DecisionTreeClassifier
• Aurélien Géron, Hands-On Machine Learning, Ch.6 Decision Trees
• Stanford CS229 Lecture Notes