결정 트리, 랜덤 포레스트, 부스팅

「x₂ 가 7.25 보다 큰가?」 같은 질문 하나로 자료를 둘로 가르고, 갈린 칸을 또 질문으로 가릅니다. 이것이 결정 트리(decision tree)입니다. 깊이 막대를 올리며 트리가 평면을 네모로 갈라 가는 모습과, 너무 깊으면 무엇이 망가지는지 보세요.

한 줄 답. 결정 트리는 「이 값이 기준보다 큰가」를 이어 물어 자료를 칸으로 가르고, 칸마다 많은 쪽 답을 내는 모델입니다. 가를 곳은 칸이 가장 덜 섞이게 되는 곳으로 고르고, 섞인 정도는 지니 불순도 1 − Σ pₖ² 나 엔트로피로 잽니다. 트리 하나는 깊으면 과적합하기 쉬워서, 트리 여럿을 따로 키워 투표하거나(랜덤 포레스트) 앞 트리의 실수를 다음 트리가 고치게(그래디언트 부스팅) 모아 씁니다.

막대나 숫자 칸으로 깊이를 1 ~ 6 으로 바꿉니다. 아래 트리 그림은 같은 트리를 노드(node)와 가지로 그린 것입니다. 한 줄이 노드 하나이고, 노드마다 질문(리프면 답), A·B 개수, 지니 값을 적었습니다. 위에 오는 실선 가지가 예(≤), 아래에 오는 점선 가지가 아니오(>) 입니다. 노드를 가리키거나 누르면 평면에서 그 노드의 칸이 주황 테두리로 보이고, 평면의 칸을 누르면 그 칸의 리프가 트리 그림에서 주황으로 보입니다. 깊이를 1 올리면 새 가지가 자랍니다. 트리는 이 쪽의 스크립트가 지니 기준으로 직접 키웁니다(2절의 방법). 그림에는 학습 점 60개(A 초록 동그라미 30, B 파랑 네모 30)만 그립니다. 시험 점 200개는 같은 규칙으로 따로 지어낸 것이고 정확도만 잽니다. 대체로 대각선 x₂ = x₁ 위쪽이 B 이고, 경계 근처는 일부러 섞어 두었습니다. 고정 시드(seed)로 지어내 쪽을 열 때마다 같습니다. 진짜 라이브러리와 같은 방식이지만 점 수십 개로 작게 줄인 본보기입니다.

1. 결정 트리란: 질문을 이어 붙인 스무고개

결정 트리는 질문을 차례로 던져 답을 찾습니다. 질문은 늘 한 모양입니다: 「특징 하나의 값이 임계값(threshold)보다 작거나 같은가」. 예라면 왼쪽 가지로, 아니라면 오른쪽 가지로 내려가고, 더 내려갈 곳이 없는 끝(리프, leaf)에 닿으면 그 리프의 답을 냅니다. 위 실험의 깊이 1 트리는 질문이 하나뿐입니다: x₂ ≤ 7.25 이면 A, 아니면 B.

트리를 키우는 절차는 이렇습니다. 맨 처음에는 학습 자료 전부가 한 칸에 있습니다.

트리 키우기(칸):
  한 클래스만 남았거나 깊이가 다 찼으면 → 리프. 칸에 많은 쪽 클래스를 답한다
  아니면 가를 수 있는 곳을 모두 해 본다:
    특징마다, 이웃한 두 값의 가운데를 임계값으로 「≤ 기준」과 「> 기준」으로 나눈다
    가른 뒤의 섞인 정도(2절의 지니)를 잰다
  가장 덜 섞이는 곳에서 가르고, 두 칸에서 각각 다시 트리 키우기

질문 하나는 특징 하나만 봅니다. 그래서 칸의 벽은 늘 가로선이나 세로선이고, 평면이 네모로 나뉩니다. 답이 클래스가 아니라 숫자(집값 같은 것)이면 회귀 트리라 부르고, 리프는 그 칸 점들의 평균을 답하며, 섞인 정도 대신 제곱 오차가 줄어드는 곳을 고릅니다.

2. 식이 만들어지는 과정: 지니 불순도

「가장 덜 섞이는 곳」을 고르려면 섞인 정도를 숫자 하나로 재야 합니다. 실험의 학습 점 60개로 그 숫자를 한 단계씩 만들어 봅니다.

「다음」을 누르면 식에 조각이 하나씩 붙고(주황 바탕이 이번에 붙은 조각), 오른쪽 그림이 바뀌고, 아래에 까닭이 나옵니다. 숫자는 손으로 따라 할 수 있게 아래에도 적었습니다.

  1. 칸 안의 비율: pₖ = nₖ ÷ n. 칸에 점이 n 개 있고 클래스 k 가 nₖ 개입니다. A 30개, B 30개라 p_A = 30 ÷ 60 = 0.5, p_B = 0.5.
  2. 둘을 뽑아 같을 확률: Σ pₖ². 칸에서 점 하나를 뽑아 보고 되돌려 놓은 뒤 또 뽑습니다. 둘 다 A 일 확률은 p_A × p_A, 둘 다 B 일 확률은 p_B × p_B 이고, 같을 확률은 이 둘의 합 0.5² + 0.5² = 0.25 + 0.25 = 0.5 입니다. Σ 는 클래스마다 더한다는 뜻입니다.
  3. 1 에서 빼기: G = 1 − Σ pₖ². 둘이 다를 확률입니다. 1 − 0.5 = 0.5. 한 클래스만 있으면 늘 같은 것이 뽑혀 0 이고, 섞일수록 커집니다. 클래스가 둘이면 1 − p_A² − p_B² = 2 × p_A × p_B(A 다음 B, 또는 B 다음 A)라 반반일 때 가장 큰 0.5 입니다. 이 G 가 지니 불순도입니다.
  4. 가른 뒤: (n₁ ÷ n)·G₁ + (n₂ ÷ n)·G₂. 트리가 고른 첫 분할(split)은 x₂ ≤ 7.25 입니다. 칸 1 은 41개(A 29, B 12)라 G₁ = 1 − (29/41)² − (12/41)² = 1 − 0.5003 − 0.0857 = 0.414. 칸 2 는 19개(A 1, B 18)라 G₂ = 1 − (1/19)² − (18/19)² = 0.0997. 크기로 무게를 줘 평균하면 41/60 × 0.414 + 19/60 × 0.0997 = 0.283 + 0.032 = 0.315. 분할 전 0.5 보다 0.185 줄었습니다. 까닭: 무게 없이 그냥 평균 내면, 점 하나만 떼어 낸 분할도 떼어 낸 칸의 지니 0 덕분에 좋아 보입니다. 나머지 59개는 거의 그대로 섞여 있는데도 말입니다. 점이 많은 칸이 결과에 그만큼 더 쳐야 합니다.

트리는 두 특징의 이웃한 값 사이를 모두 임계값으로 해 보고, 4 의 값이 가장 작은 곳을 고릅니다. 이 자료에서는 x₂ ≤ 7.25 였습니다. 그다음 두 칸에서 같은 일을 되풀이합니다. scikit-learn 문서는 같은 식을 Σ pₖ(1 − pₖ) 로 적는데, 풀면 Σ pₖ − Σ pₖ² = 1 − Σ pₖ² 라 같습니다.

3. 다른 기준: 엔트로피

섞인 정도를 재는 또 하나의 방법이 엔트로피입니다: H = −Σ pₖ × log₂ pₖ. 교차 엔트로피 쪽의 그 엔트로피입니다. 지니처럼 한 클래스만 있으면 0 이고(0 × log 0 은 0 으로 둡니다), 반반일 때 가장 큽니다. 반반이면 H = −(0.5 × (−1) + 0.5 × (−1)) = 1 입니다. 위의 칸 1(A 29, B 12)은 지니 0.414, 엔트로피 0.872 입니다.

가른 뒤의 값도 같은 방식으로 두 칸의 엔트로피를 크기로 무게 줘 평균합니다. 분할 전 엔트로피에서 이 값을 뺀 것을 정보 이득이라고 부릅니다. 로그의 밑을 2 대신 e 로 해도 모든 값이 같은 비율로 바뀔 뿐이라 고르는 분할은 같습니다. scikit-learn 의 결정 트리는 criterion 으로 둘 가운데 하나를 고르고, 기본값은 지니입니다.

4. 깊은 트리의 과적합

트리는 끝까지 키우면 칸마다 한 클래스만 남을 때까지 가릅니다. 그러면 학습 정확도는 1 이 됩니다. 하지만 경계 근처의 섞인 점은 규칙이 아니라 우연이라, 그 점 하나를 위해 만든 작은 칸은 새 자료에서 틀립니다. 학습 자료를 외운 것입니다. 이것이 과적합입니다.

해 볼 것. 맨 위 실험에서 깊이를 1 부터 6 까지 올려 보세요. ① 깊이 1 은 리프 2개, 학습 0.78(60개 중 47), 시험 0.68(200개 중 136). 가로선 하나로는 대각선 경계를 잘 따라가지 못합니다. ② 깊이 2 는 학습 0.92, 시험 0.81. 깊이 3 은 리프 6개, 학습 0.95, 시험 0.84 로 가장 높습니다. 칸들이 대각선을 계단으로 흉내 냅니다. ③ 깊이 4 부터는 학습 정확도가 계속 올라 깊이 6 에서 1(60개 모두)이 되지만, 시험 정확도는 0.8(200개 중 160)로 깊이 3 보다 낮습니다. 섞인 점 하나를 따로 감싸는 작은 칸이 생기는 것을 보세요.

막는 법은 트리가 너무 잘게 가르지 못하게 하는 것입니다. 깊이에 상한을 두거나(max_depth), 리프에 점이 몇 개 이상 있어야 한다고 하거나(min_samples_leaf), 다 키운 뒤 쓸모가 적은 가지를 잘라 냅니다(가지치기). 그 값은 학습에 쓰지 않은 자료로 재서 고릅니다(자료 나누기). 또 하나의 길이 다음 절의 「트리 여럿 모으기」입니다.

5. 꼭 알아야 할 성질

성질쉬운 말실험에서
경계가 축에 나란한 네모질문 하나가 특징 하나만 보므로 칸의 벽은 가로선이나 세로선이다. 비스듬한 경계는 계단으로 흉내 낸다깊이 3 의 계단
깊을수록 학습 자료를 외운다끝까지 키우면 학습 정확도는 1 이 되지만 섞인 점까지 외워 새 자료에서 틀린다깊이 6: 학습 1, 시험 0.8
규칙을 읽을 수 있다리프까지 가는 길이 「x₂ ≤ 7.25 이고 x₁ ≤ …」 같은 조건의 줄이라 사람이 따라갈 수 있다깊이 1 의 규칙 하나
자료가 조금 바뀌면 트리가 크게 바뀐다위쪽 분할 하나가 바뀌면 그 아래가 모두 바뀐다. 트리 여럿을 모으면 이 흔들림이 줄어든다6절
지금 가장 좋은 분할만 고른다한 번 가른 것을 되돌리지 않는다. 그래서 전체로 가장 좋은 트리라는 보장은 없다2절 4 단계

6. 트리 여럿 모으기: 랜덤 포레스트와 그래디언트 부스팅

트리 하나는 흔들리고 쉽게 외웁니다. 그래서 실제로는 트리 여럿을 모아 씁니다(앙상블). 모으는 길은 둘입니다.

따로 키워 투표: 랜덤 포레스트

학습 자료에서 같은 수만큼 뽑고 되돌려 넣기를 되풀이해 조금씩 다른 자료 묶음을 여럿 만들고(부트스트랩), 묶음마다 트리를 하나씩 키웁니다. 가를 곳을 찾을 때도 특징 전부가 아니라 무작위로 고른 몇 개만 봅니다. 그러면 트리들이 서로 다른 실수를 하고, 모아서 투표하면 실수가 서로 지워집니다. 트리끼리 기다릴 일이 없어 동시에 키울 수 있습니다. 원 논문은 트리들이 클래스를 투표하고, scikit-learn 은 트리들이 낸 클래스별 확률을 평균합니다.

「다음」을 누를 때마다 트리가 한 그루 늘어납니다(9 그루까지). 자료는 맨 위 실험의 학습 점 60개이고, 정확도는 같은 시험 점 200개로 잽니다. 트리는 깊이 3 으로 얕게 두고, 노드마다 x₁ 과 x₂ 가운데 하나를 무작위로 골라 그 축에서만 가를 곳을 찾습니다(위 글의 「무작위로 고른 몇 개」. 특징이 둘뿐이라 하나). 투표는 그루마다 한 표이고, 표가 같으면 A 로 둡니다(이 실험의 규칙. 트리 수가 짝수일 때만 생깁니다). 고정 시드라 늘 같은 트리들이 나옵니다.

해 볼 것. ① 트리 1 그루의 시험 정확도는 0.73(200개 중 146)입니다. ② 3 그루 0.845, 5 그루 0.88. 4 그루에서는 0.81 로 3 그루보다 낮아, 그루가 늘 때마다 늘 오르지는 않습니다. ③ 9 그루의 투표는 0.88(176)입니다. 9 그루 가운데 혼자 가장 좋은 트리도 0.84(168)인데, 투표가 그보다 높습니다. 오른쪽 그림에서 회색 선이 쌓일수록 굵은 투표 경계가 대각선을 따라가는 것을 보세요.

앞 트리의 실수를 다음 트리가 고침: 그래디언트 부스팅

트리를 차례로 키웁니다. 첫 예측은 단순하게(예: 평균) 시작하고, 다음 트리는 지금까지의 예측이 자료마다 얼마나 틀렸는지를 배웁니다. 그 트리의 답에 작은 비율(학습률)을 곱해 예측에 더하고, 또 남은 실수를 다음 트리가 배웁니다. 제곱 오차로 숫자를 맞힐 때는 「얼마나 틀렸나」가 바로 정답 − 지금 예측(잔차)입니다. 일반적으로는 손실의 기울기(그래디언트)의 반대 방향을 배우고, 이름이 여기서 왔습니다. 손실을 줄이는 쪽으로 한 걸음씩 가는 것이 경사 하강법과 같은 생각입니다. 분류에서도 손실로 로지스틱 회귀의 로그 손실을 쓰고, 트리는 숫자를 내는 회귀 트리를 씁니다. 트리 하나하나는 보통 얕게 둡니다.

Fₘ(x) = Fₘ₋₁(x) + η × hₘ(x)

점 11개는 지어낸 것입니다(x 가 클수록 y 도 대체로 큽니다). 「다음」을 누를 때마다 트리 한 그루를 잔차에 맞추고 그 절반을 예측에 더합니다(6 그루까지).

해 볼 것. ① 처음 예측은 평균 4.55 이고, 잔차 제곱합은 56.79 입니다. ② 트리 1 은 x ≤ 5.2 에서 갈라 왼쪽 −1.871, 오른쪽 2.245 를 냅니다. 그 절반(−0.936, 1.123)을 더하면 잔차 제곱합이 56.79 → 22.12 로 줄어듭니다. ③ 트리 2 ~ 6 에서 22.12 → 8.19 → 4.03 → 2.15 → 1.46 → 1.05. 계단은 남은 잔차에 맞추므로, 잔차가 작아질수록 계단도 작아지고 줄어드는 양도 작아집니다.

# scikit-learn 으로 셋을 비교하기
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import RandomForestClassifier, HistGradientBoostingClassifier
models = [
    DecisionTreeClassifier(max_depth=3),          # 트리 하나. 기본 기준은 지니
    RandomForestClassifier(n_estimators=200),     # 따로 키운 트리 200 그루
    HistGradientBoostingClassifier(),             # 차례로 실수를 고치는 트리들
]
for model in models:
    model.fit(x_train, y_train)
    print(type(model).__name__, model.score(x_valid, y_valid))   # 검증 자료로 비교한다

표 모양 자료에서는. 표 모양 자료 45 개로 비교한 연구(출처)에서, 자료가 1만 개 안팎인 중간 크기에서는 XGBoost 와 랜덤 포레스트 같은 트리 기반 모델이 신경망보다 좋은 결과를 냈습니다. 모든 자료에서 그렇다는 뜻은 아닙니다.

7. 언제 무엇을 쓰나

선택지좋은 점나쁜 점쓰는 경우
트리 하나규칙을 사람이 읽을 수 있다. 눈금 맞추기가 필요 없다. 학습과 예측이 빠르다깊으면 과적합. 자료가 조금 바뀌면 트리가 크게 바뀐다. 비스듬한 경계는 계단이 된다왜 그렇게 판단했는지 보여 줘야 할 때(설명 필요). 자료를 처음 훑어볼 때. 규칙을 뽑아 코드로 옮길 때
랜덤 포레스트트리 하나보다 덜 흔들리고 덜 외운다. 트리를 동시에 키울 수 있다트리 수백 그루라 규칙을 읽을 수 없다. 모델이 크다표 모양 자료에서 먼저 세워 보는 기준 모델. 설정을 오래 만질 시간이 없을 때
그래디언트 부스팅표 모양 자료에서 높은 정확도를 내는 경우가 많다학습률, 트리 수, 깊이를 맞춰야 한다. 트리를 차례로 키운다. 트리를 너무 많이 쌓으면 과적합한다표 모양 자료에서 정확도가 가장 중요할 때(중간 크기 자료)
신경망그림, 글, 소리처럼 표가 아닌 자료를 잘 다룬다. 자료가 아주 많을 때 커질 수 있다표 모양 중간 크기 자료에서는 트리 기반 모델보다 못한 결과가 많다(출처). 입력 눈금을 맞춰야 한다. 설명이 어렵다그림·글·소리, 아주 큰 자료. 표 모양 자료라도 트리와 비교해 본 뒤에

어디에 쓰나

자주 묻는 것

트리에 넣기 전에 정규화를 해야 하나요?

보통 하지 않아도 됩니다. 트리는 「이 값이 기준보다 큰가」만 물어서 값의 순서만 씁니다. 평균을 빼고 나누는 표준화나 0 ~ 1 로 맞추는 최소-최대는 순서를 바꾸지 않으므로, 같은 점들이 같은 칸으로 갈립니다. 트리를 모은 랜덤 포레스트와 그래디언트 부스팅도 같습니다.

트리의 깊이는 얼마로 해야 하나요?

정해진 값은 없습니다. 깊이를 몇 가지로 바꿔 가며 학습에 쓰지 않은 검증 자료로 점수를 재고, 가장 좋은 깊이를 고릅니다. 이 쪽 실험에서는 깊이 3 이 시험 정확도 0.84 로 가장 좋았고, 깊이 6 은 학습 정확도가 1 인데 시험 정확도는 0.8 로 떨어졌습니다.

표 모양 자료에서는 신경망보다 트리가 더 낫나요?

그렇다는 연구가 있습니다. 표 모양 자료 45 개로 비교한 연구에서, 자료가 1만 개 안팎인 중간 크기에서는 XGBoost 와 랜덤 포레스트 같은 트리 기반 모델이 신경망보다 좋은 결과를 냈습니다. 모든 자료에서 그렇다는 뜻은 아니니, 둘 다 해 보고 검증 자료로 고릅니다.

낱말

여기서 쓴 말책에서 부르는 말
질문을 이어 붙인 모델결정 트리(decision tree). 흔한 방식의 이름은 CART
질문 하나, 기준이 되는 값노드(node), 분할(split), 임계값(threshold)
더 내려갈 곳이 없는 끝 칸리프, 리프 노드(leaf)
칸이 섞인 정도불순도(impurity). 지니 불순도(Gini impurity), 엔트로피(entropy)
가르기로 줄어든 섞임불순도 감소, 정보 이득(information gain)
답이 숫자인 트리회귀 트리(regression tree)
쓸모 적은 가지 잘라 내기가지치기(pruning)
모델 여럿 모으기앙상블(ensemble)
뽑고 되돌려 넣기로 묶음 만들기부트스트랩(bootstrap). 그렇게 키워 모으면 배깅(bagging)
따로 키워 투표랜덤 포레스트(random forest)
앞의 실수를 차례로 고치기부스팅(boosting), 그래디언트 부스팅(gradient boosting)
정답 − 지금 예측잔차(residual)
한 번에 더하는 비율학습률(learning rate), 축소(shrinkage)
표 모양 자료정형 데이터, 테이블 데이터(tabular data)

출처

← 매니폴드k-최근접 이웃(kNN) →