5 결정트리

결정트리는 분류와 회귀 모두에 활용 가능한 다목적 머신러닝 모델이다. 예측 과정이 사람이 이해하기 쉬운 규칙의 연속으로 이루어지기 때문에, 모델의 동작 방식을 직관적으로 파악할 수 있다는 것이 큰 장점이다. 또한 데이터 전처리가 거의 필요 없으며, 강력한 앙상블 모델인 랜덤 포레스트의 핵심 구성 요소이기도 하다.

이 장에서는 결정트리의 훈련 방식과 내부 구조, 예측 과정, 그리고 분류·회귀에서의 활용을 살펴본다. 아울러 CART 알고리즘, 지니 불순도와 엔트로피, 규제 하이퍼파라미터, 결정트리의 한계도 함께 다룬다.

5.1결정트리 훈련과 시각화¶

5.1.1결정트리 훈련¶

결정트리는 훈련 데이터에서 분할 규칙을 반복적으로 학습하여 구성된다. 각 단계에서 하나의 특성을 기준으로 데이터를 두 부분으로 나누며, 나뉜 각 부분에 대해 같은 과정을 반복한다.

예를 들어, 붓꽃 데이터셋에서 꽃잎의 길이와 너비 두 가지 특성만을 이용해 세 품종(세토사, 버시컬러, 버지니카)을 분류하는 결정트리를 훈련시킬 수 있다.

싸이킷런의 DecisionTreeClassifier 분류 모델을 max_depth=2 하이퍼파라미터로 지정하여 훈련시키면 루트 노드에서 시작해서 최대 2번의 분할만 허용하는 결정트리가 학습된다.

5.1.2결정트리 시각화¶

학습된 결정트리는 아래 그림처럼 트리 구조로 시각화할 수 있다. 각 노드에는 해당 분할이 어떤 기준으로 이루어졌는지, 그리고 그 노드에 속한 샘플들의 정보가 함께 표시된다.

결정트리의 각 노드에 포함된 속성은 다음과 같다.

5.1.3트리 구조: 노드와 잎¶

트리와 노드

트리rooted tree는 아래 성질을 만족하는 노드node와 이음선edge들로 이루어진다.

• 루트root로 사용되는 하나의 노드가 있다.

• 루트를 제외한 모든 노드는 부모 노드로부터 오는 진입 이음선으로 연결된다.

• 루트로부터 임의의 노드로 연결되는 경로가 유일하게 존재한다.

트리의 노드는 가지 분할이 시작되는 지점이며 부모 노드와 자식 노드를 가질 수 있다.

• 루트 노드: 맨 상단에 위치한 노드. 부모 노드를 갖지 않음.

• 내부 노드: 루트와 잎이 아닌 노드. 부모와 자식 노드를 모두 가짐.

• 잎 노드: 더 이상의 가지분할이 발생하지 않는 노드. 자식 노드를 갖지 않음.

노드의 깊이는 루트 노드에서 해당 노드까지의 거리(이음선 수)를 의미한다.

5.1.4지니 불순도¶

결정트리의 각 노드는 지니 불순도Gini impurity를 이용해 자신에 속한 샘플들이 얼마나 다양한 범주에 분포되어 있는지를 측정한다.

노드의 지니 불순도 $G$는 다음과 같이 계산된다.

• $p_k$: 해당 노드의 훈련 샘플 중 범주 $k$에 속한 샘플의 비율

• $K$: 범주(클래스)의 개수

모든 샘플이 하나의 범주에만 속하면 $G = 0$으로 불순도가 가장 낮다. 반대로 샘플들이 여러 범주에 골고루 분포될수록 $G$는 1에 가까워진다.

예를 들어, 깊이 2의 왼편 잎 노드에는 세토사 0개, 버시컬러 49개, 버지니카 5개(총 54개)가 포함되어 있어서 노드의 지니 불순도는 다음과 같이 계산된다.

반면에 깊이 1의 왼편 노드에는 세토사 품종 55개만 포함되어 있어서 노드의 지니 불순도가 0이다.

5.2결정트리 모델의 예측값¶

5.2.1범주 예측¶

결정트리는 새로운 샘플을 받으면 루트 노드에서 시작하여 분할 조건을 하나씩 확인하면서 잎 노드까지 내려간다. 도달한 잎 노드에서 가장 높은 비율을 차지하는 범주를 예측값으로 반환한다.

예를 들어, 꽃잎 길이 5cm, 꽃잎 너비 1.5cm인 붓꽃을 max_depth=2로 훈련된 결정트리로 분류한다면:

1. 루트 노드: 꽃잎 길이가 2.45cm보다 크므로 → 오른쪽 자식 노드로 이동

2. 깊이 1 오른편 노드: 꽃잎 너비가 1.75cm 이하이므로 → 왼쪽 자식 노드(잎 노드)로 이동

3. 잎 노드 도달: 해당 잎 노드에서 버시컬러 비율이 가장 높으므로 → 버시컬러로 예측

이처럼 결정트리는 예측값이 도출되는 과정을 명확하게 추적할 수 있다. 이런 의미에서 결정트리 모델은 화이트박스white-box 모델이라 부른다.

범주에 속할 확률 예측

결정트리는 단순히 범주를 예측하는 것에 그치지 않고, 주어진 샘플이 각 범주에 속할 확률도 함께 계산한다.

확률 계산 방법은 다음과 같다.

1. 해당 샘플이 포함되는 잎 노드를 확인한다.

2. 잎 노드에서 계산된 각 범주의 비율을 해당 범주에 속할 확률로 사용한다.

예를 들어, 꽃잎 길이 5cm, 꽃잎 너비 1.5cm인 붓꽃이 도달하는 잎 노드에는 54개의 샘플이 포함되어 있으며, 그 중 세토사 0개, 버시컬러 49개, 버지니카 5개가 포함되어 있다. 따라서 각 범주에 속할 확률은 다음과 같다.

버시컬러에 속할 확률이 약 90.7%로 가장 높으므로, 해당 샘플은 버시컬러로 예측된다.

한편, max_depth=3으로 훈련된 더 깊은 결정트리는 동일한 샘플에 대해 버지니카(66.7%)로 예측할 수 있다. 이는 같은 데이터라도 결정트리의 깊이에 따라 다른 잎 노드에 할당되어 예측이 달라질 수 있음을 보여준다.

5.2.2결정경계¶

결정경계decision boundary란 결정트리가 학습된 분할 규칙에 따라 특성 공간을 여러 영역으로 구분하는 경계선이다. 각 분할은 특정 특성의 임곗값을 기준으로 축에 수직인 직선으로 이루어지기 때문에, 결정경계는 항상 직각으로 구성된 계단 형태를 갖는다.

max_depth=3으로 결정트리를 다시 훈련시킨 후 결정경계를 확인한다.

tree_clf3 = DecisionTreeClassifier(max_depth=3, random_state=42)
tree_clf3.fit(X_iris, y_iris)

훈련된 결정트리를 시각화하면 다음과 같다.

max_depth=3으로 훈련된 결정트리의 결정경계를 다음과 같이 시각화된다.

각 분할에서 사용된 기준값은 다음과 같다.

5.3결정트리 학습 알고리즘¶

사이킷런의 결정트리는 CART(Classification and Regression Tree) 알고리즘을 사용하여 훈련된다. CART는 각 노드를 두 개의 자식 노드로 분할하는 이진 분할만을 수행하는 알고리즘이다.

5.3.1분류용 CART 알고리즘¶

CART 분류 알고리즘은 각 노드에서 아래 비용함수를 최소화하는 특성 $k$와 해당 특성의 임곗값 $t_k$를 탐색한다. 그런 다음, 찾아낸 $(k, t_k)$ 쌍을 기준으로 노드를 두 개의 자식 노드로 분할한다. 이 과정을 지정된 최대 깊이에 도달하거나 더 이상 불순도를 줄이는 분할이 불가능해질 때까지 반복한다.

• $m$, $m_\text{left}$, $m_\text{right}$: 각각 부모와 왼쪽·오른쪽 자식 노드에 속한 샘플 수

• $G_\text{left}$, $G_\text{right}$: 각각 왼쪽·오른쪽 자식 노드의 지니 불순도

특성 $k$는 기본적으로 모든 특성을 대상으로 탐색되며(max_features 하이퍼파라미터를 설정하여 일부 특만 고려하도록 할 수 있음), 임곗값 $t_k$는 해당 특성의 모든 훈련 샘플 값을 대상으로 탐색된다.

$J(k, t_k)$를 가장 작게 하는 $k$와 $t_k$를 찾는 CART 알고리즘은 탐욕 알고리즘greedy algorithm이다. 각 노드에서 현재 가장 좋은 분할만을 선택하고, 이후의 분할에 대한 영향은 고려하지 않기 때문이다. 이로 인해 전역적으로 최적인 결정트리를 보장하지는 않지만, 실제로는 충분히 좋은 성능을 보인다.

5.3.2CART 알고리즘의 시간 복잡도¶

최적의 결정트리를 찾는 문제는 $O(\exp(m))$ 복잡도를 갖는 NP-완전NP-complete 문제이다. 따라서 매우 작은 훈련셋에 대해서도 전역 최적해를 정확하게 구하기 어렵다.

반면에 탐욕 기법을 사용하는 CART 알고리즘의 시간 복잡도는 다음과 같다. $n$과 $m$은 각각 특성 수와 샘플 수를 나타낸다.

예측 시간이 $O(\log_2 m)$으로 매우 빠른 이유는 결정트리가 균형 이진 탐색 트리에 가깝기 때문이다. 각 노드에서 하나의 특성값만 확인하면 되므로 특성 수와 무관하게 트리의 경로를 빠르게 따라갈 수 있다.

5.4규제 하이퍼파라미터¶

5.4.1파라미터 모델 vs. 비파라미터 모델¶

결정트리 모델이 훈련을 통해 학습하는 파라미터는 노드 분할에 사용되는 특성과 임곗값이다. 그런데 결정트리 모델의 파라미터 수는 미리 정해지지 않는데 이유는 다음과 같다.

• 노드를 분할할 때마다 새로운 분할 기준이 추가된다.

• 분할 횟수를 제한하지 않으면 분할이 몇 번 이뤄질지 모델 훈련 전에 미리 알 수 없다.

이처럼 파라미터 수가 훈련 과정에서 결정되는 모델을 비파라미터 모델nonparametric model이라 한다. 반면에 선형 회귀 모델처럼 훈련 시작 전에 파라미터 수가 고정된 모델을 파라미터 모델parametric model이라 하며, 과대적합 가능성이 상대적으로 낮다.

5.4.2주요 규제 하이퍼파라미터¶

비파라미터 모델은 규제를 가하지 않으면 모델 복잡도에 제한이 없어 훈련셋에 과대적합될 가능성이 매우 높다. 예를 들어 max_depth 제한을 두지 않는다면 CART 알고리즘은 하나의 범주에 속하는 샘플들만 포함되도록 노드를 최대한 많이 분할할 것이다. 그런데 그렇게 하면 애초에 꽃잎의 길이와 너비 많으로는 완벽하게 구분할 수 없는 버시컬러 품종과 버지니카 품종을 매우 세밀하게 구분하는 과대적합 모델이 학습될 것이다.

결정트리의 과대적합을 방지하기 위해 다양한 하이퍼파라미터를 이용해 규제를 가할 수 있다. min_으로 시작하는 하이퍼파라미터는 값을 키울수록 규제가 강해지고, max_로 시작하는 하이퍼파라미터는 값을 줄일수록 규제가 강해진다.

아래 그래프는 초승달 모양의 데이터셋을 대상으로 규제 없이 훈련된 결정트리(왼쪽)와 min_samples_leaf=5 규제를 적용한 결정트리(오른쪽)의 결정경계를 보여준다.

• 왼쪽: 규제 없이 훈련된 결정트리. 훈련셋에 과대적합되어 복잡한 결정경계를 형성한다.

• 오른쪽: min_samples_leaf=5 규제 적용. 잎 노드에 최소 5개의 샘플이 포함되어야 하므로 지나치게 세밀한 분할이 억제되고, 일반화 성능이 더 좋은 결정트리가 생성된다.

5.5회귀 결정트리¶

결정트리는 분류뿐만 아니라 회귀 문제에도 활용할 수 있다. 아래 그림은 잡음이 포함된 2차 함수 형태의 데이터셋을 보여준다. 이 데이터셋을 이용하여 회귀 결정트리를 훈련시킨다.

rng = np.random.default_rng(seed=42)
X_quad = rng.random((200, 1)) - 0.5              # 단변량 입력 데이터셋
y_quad = X_quad ** 2 + 0.025 * rng.standard_normal((200, 1)) # 타깃셋

5.5.1회귀 결정트리의 구조¶

max_depth=2로 훈련된 회귀 결정트리의 구조는 아래와 같다. 분류 결정트리와 유사하게 생겼지만, 각 노드에 포함된 속성이 다르다.

회귀 결정트리 각 노드에 포함된 속성은 다음과 같다.

5.5.2회귀 결정트리 예측¶

회귀 결정트리의 예측 방식은 분류 결정트리와 동일하게 루트 노드에서 시작하여 잎 노드까지 내려가는 방식이다. 단, 잎 노드에 도달하면 해당 노드의 value(평균 타깃값)를 예측값으로 반환한다.

예를 들어, $x_1 = 0.2$인 경우의 예측 과정은 다음과 같다.

1. 루트 노드: $x_1 < 0.343$이므로 → 왼쪽 자식 노드로 이동

2. 깊이 1 왼쪽 노드: $x_1 > -0.302$이므로 → 오른쪽 자식 노드로 이동

3. 잎 노드 도달: value = 0.038이므로 → 0.038을 예측값으로 반환

아래 그래프는 max_depth=2(왼쪽)와 max_depth=3(오른쪽)으로 훈련된 회귀 결정트리의 예측 함수이다.

• 실선(Depth=0): 1차 분할 기준

• 파선(Depth=1): 2차 분할 기준

• 점선(Depth=2, 오른쪽 그래프만): 3차 분할 기준

결정트리 회귀 모델은 각 영역 내 샘플들의 평균값을 예측하므로, 예측 곡선이 계단 형태를 띤다.

5.5.3회귀용 CART 비용함수¶

회귀 결정트리의 CART 알고리즘은 분류의 경우와 동일하게 탐욕적으로 비용함수를 최소화하는 분할을 반복한다. 단, 지니 불순도 대신 평균 제곱 오차(MSE)를 사용한다.

• $m$과 $m_\text{child}$: 각각 부모와 자식 노드에 속하는 샘플 수

• $\hat{y}_\text{child}$: 자식 노드에 속한 샘플들의 타깃값 평균

• $y^{(i)}$: 샘플 $i$의 실제 타깃값

5.5.4회귀 결정트리 규제¶

회귀 결정트리도 분류의 경우와 마찬가지로 규제가 없으면 과대적합이 발생한다.

아래 그래프의 왼쪽은 규제 없이 훈련된 회귀 결정트리로, 훈련셋에 과대적합되어 있다. 오른쪽은 min_samples_leaf=10 규제를 적용한 결과로, 일반화 성능이 보다 좋은 모델이 생성된다.

5.6결정트리의 과대적합¶

결정트리는 직관적이고 강력한 모델이지만 무엇보다도 훈련셋에 매우 민감하게 반응하는 과대적합 현상을 쉽게 발생시킨다. 결정트리 모델이 훈련셋에 과대적합되는 이유 두 가지를 소개한다.

• 훈련셋 회전 민감도

• 높은 분산값

훈련셋 회전 민감도

결정트리는 항상 축에 수직인 분할만을 사용한다. 따라서 훈련셋에 회전을 조금만 가해도 결정경계가 크게 달라진다.

아래 그래프에서 왼쪽은 원래 데이터셋으로 훈련된 결정트리이고, 오른쪽은 같은 데이터를 45도 회전시킨 훈련셋으로 학습된 결정트리이다. 오른쪽 결정트리는 불필요하게 복잡한 계단 형태의 결정경계를 갖는다.

높은 분산값

결정트리는 꽤 높은 분산을 갖는다. 즉, 훈련셋이나 하이퍼파라미터가 조금만 달라져도 완전히 다른 결정트리가 훈련될 수 있다. 심지어 동일한 데이터로 동일한 모델을 훈련시켜도 다른 결정트리가 생성되기도 한다. 이는 사이킷런의 훈련 알고리즘이 각 노드에서 기준 특성을 지정할 때 순서를 무작위로 섞어서 특성과 기준값이 매번 달라질 수 있기 때문이다. 예를 들어, random_state를 이용하여 난수 발생기의 시드를 고정하지 않으면 동일한 훈련셋에 대해 아래 그래프와 같이 매우 다른 결정트리가 생성되기도 한다.

5.7연습문제¶

문제 1

(코드 워크아웃) 결정트리 내용을 학습하라.

문제 2

초승달 데이터셋을 이용한 결정트리 모델을 미세 조정한다.

힌트: (코드 워크아웃) 결정트리 미세조정

문제 3

랜덤 포레스트(random forest) 모델을 훈련하는 방법을 살펴본다. 랜덤 포레스트는 여러 개의 결정트리로 구성된다.

힌트: (코드 워크아웃) 랜덤 포레스트 모델 훈련