[파이썬머신러닝] 결정 트리 Decision Tree

 

 

SVM처럼 결정 트리는 분류외 회귀 작업, 다중출력 작업도 가능한 머신러닝 알고리즘이다.

또한, 최근 자주 사용되는 머신러닝 알고리즘인 랜덤 포레스트의 기본 구성 요소가 되기도 한다.

 

 

1. 결정 트리 학습과 시각화

다음은 붓꽃 데이터셋에 DecisionTreeClassifier을 훈련시키는 코드이다.

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier

iris = load_iris()
X = iris.data[:, 2:] # 꽃잎 길이와 너비
y = iris.target

tree_clf = DecisionTreeClassifier(max_depth=2, random_state=42)
tree_clf.fit(X, y)

 

여기서 export_graphviz() 함수로 그래프 정의를 iris_tree.dot 파일로 출력하여 훈련된 결정트리를 시각화 할 수 있다.

from graphviz import Source
from sklearn.tree import export_graphviz

export_graphviz(
        tree_clf,
        out_file=os.path.join(IMAGES_PATH, "iris_tree.dot"),
        feature_names=iris.feature_names[2:],
        class_names=iris.target_names,
        rounded=True,
        filled=True
    )

Source.from_file(os.path.join(IMAGES_PATH, "iris_tree.dot"))

 

.dot 파일을 Graphviz 패키지에 있는 dot 명령줄 도구로 pdf나 png같은 포맷으로 변경할 수 있다.

$ dot -Tpng iris_tree.dot -o iris_tree.png

 

 

2. 예측하기

위에서 학습시킨 트리가 어떻게 예측을 만들어낼까?

새로 발견한 붓꽃의 품종을 분류한다고 가정해보자. 

 

 

루트 노드(root node)에서 꽃잎의 길이가 2.45cm보다 짧은지 검사

1. 맞다면 깊이가 1인 왼쪽의 자식 노드(child node)로 이동
2. 왼쪽의 자식 노드의 경우 자식 노드를 가지지 않는 리프 노드(leaf node)이므로 추가로 검사하지 않고, 해당 노드의 예측 클래스를 보고 결정 트리가 새로 발견한 꽃의 품종을 Iris-Setosa(class=setosa)라고 예측

 

1. 아니라면 깊이가 2인 오른쪽의 자식 노드로 이동
2. 이 노드는 리프 노드가 아니기 때문에, 추가로 꽃잎의 너비가 1.75cm보다 작은지 검사
3. 맞다면 이 꽃은 아마도 Iris-Versicolor(깊이 2, 왼쪽)이고, 아니라면 Iris-Virginica(깊이 2, 오른쪽)으로 예측

 

* 결정 트리의 장점 중 하나는 특성의 스케일을 맞추거나 평균을 원점에 맞추는 등의 데이터 전처리가 거의 필요하지 않다는 것이다.

* 사이킷런은 이진 트리만 만드는 CART 알고리즘을 사용한다. 따라서 리프 노드 외 모든 노드는 자식 노드를 두 개씩 갖는다. 하지만, ID3같은 알고리즘은 둘 이상의 자식 노드를 가진 결정 트리를 만들 수 있다.

 

• sample : 얼마나 많은 훈련 샘플이 적용되었는지에 대한 것 (ex) 100개의 훈련 샘플의 꽃잎 길이가 2.45보다 길다.
• value : 각 클래스에 얼마나 많은 훈련 샘플이 있는지 (ex) 보라색 노드에서는 Iris-Setosa 0개, Iris-Versicolor가 1개, Iris-Virginica 45개임을 알 수 있다.
• gini : 노드의 불순도 (impurity) 측정

 

불순도 측정

[ 지니 불순도 ]

$$ G_i = 1 - \sum_{k=1}^{n}p_{i, k}^2 $$

* \( p_{i, k} \)는 i번째 노드에 있는 훈련 샘플 중 클래스 k에 속한 샘플의 비율이다.

 

순수 노드 (gini = 0) : 한 노드의 모든 샘플이 같은 클래스에 속해 있다

 

깊이 1의 왼쪽 노드는 Iris-Setosa 훈련 샘플만 가지고 있으므로 순수 노드이고 gini 점수가 0이다.

깊이 2의 왼쪽 노드의 gini 점수는 \(  1-(0/54)^2 - (49/54)^2 - (5/54)^2 \approx 0.168 \) 이다.

 

 

일반적으로 지니 불순도가 사용되지만 criterion 매개변수를 'entropy'로 지정해 엔트로피 불순도를 사용할 수 있다.

 

열역학에서 엔트로피는 분자의 무질서함을 측정하는 것으로, 분자가 안정되고 질서 정연하면 엔트로피는 0에 가깝다.

머신러닝에서는 불순도 측정 시 사용되며 어떤 세트가 한 클래스의 샘플만 담고 있다면 엔트로피가 0이다.

 

[ 엔트로피 ]

$$ H_i = -\sum_{k=1,\ p_{i, k}\neq 0}^{n} p_{i, k}\ log_2(p_{i,k})$$

 

예를 들어 깊이 2의 왼쪽 노드의 엔트로피는  \(-\frac{49}{54}log_2(\frac{49}{54})-\frac{5}{54}log_2(\frac{5}{54}) \approx 0.445\) 이다.

 

지니 불순도와 엔트로피 중 뭘 사용해야 할까?

=> 실제로는 큰 차이가 없다.

 

지니 불순도가 조금 더 계산이 빨라 기본값으로 좋지만, 엔트로피는 조금 더 균형 잡힌 트리를 만든다.

 

 

결정 트리의 결정 경계

다음은 결정 트리의 결정 경계이다.

• 굵은 수직선 : 루트 노드(깊이 0)의 결정 경계 (꽃잎 길이 = 2.45cm)를 나타낸다.
• 왼쪽 영역 : 순수 노드 (Iris-Setosa만 있음)이기 때문에 더 나눌 수 없다.
• 오른쪽 영역 : 순수 노드가 아니므로 깊이 1의 오른쪽 노드는 꽃잎 너비 =1.75cm에서 나누어 진다. (파선)
• max_depth를 2로 설정했기 때문에 결정 트리는 더 분할되지 않는다.
• max_depth=3 이면 깊이 2의 두 노드가 각각 결정 경계를 추가로 만든다. (점선)

 

모델 해석 : 화이트박스와 블랙박스

• 화이트 박스 (white box) 모델
  • 직관적이고 결정 방식을 이해하기 쉬움
  • (ex) 결정 트리
• 블랙 박스 (black box) 모델
  • 성능이 뛰어나고 예측을 만드는 연산 과정을 쉽게 확인할 수 있음
  • 왜 그런 예측을 했는지 쉽게 설명하기 어려움
  • (ex) 랜던 포레스트, 신경망

 

 

3. 클래스 확률 추정

결정 트리는 한 샘플이 특정 클래스 k에 속할 확률을 추정할 수도 있다.

 

1. 샘플에 대해 리프 노드를 찾기 위해 트리 탐색
2. 그 노드에 있는 클래스 k의 훈련 샘플의 비율 반환

예를 들어 길이=5cm, 너비=1.5cm인 꽃잎을 발견했다고 가정해보자.

이에 해당하는 리프 노드는 깊이 2에서 왼쪽 노드이므로 결정 트리는 그에 해당하는 확률을 출력한다.

=> Iris-Setosa는 0% (0/54), Iris-Versicolor는 90.7% (49/54), Iris-Virginica는 9.3% (5/54)

만약 클래스를 하나 예측한다면 가장 높은 확률을 가진 Iris-Versicolor (class 1)을 출력할 것이다.

 

# 확률 반환
tree_clf.predict_proba([[5, 1.5]])
>>> array([[0.        , 0.90740741, 0.09259259]])

# 가장 높은 확률을 가진 class 출력
tree_clf.predict([[5, 1.5]])
>>> array([1])

* predict_proba 함수는 각 샘플에 대해 어느 클래스에 속할 확률을 0에서 1 사이의 값으로 돌려준다.

 

 

4. CART 훈련 알고리즘

사이킷런은 결정 트리를 훈련시키기 위해 CART (Classification And Regression Tree) 알고리즘을 사용한다.

 

훈련 세트를 하나의 특성 k의 임계값 \(t_k\)를 사용해 두 개의 서브셋으로 나눌 때, 어떻게 k와 \(t_k\)를 나눌까?

=> 크기에 따른 가중치가 적용된 가장 순수한 서브셋으로 나눌 수 있는 \( (k, t_k) \) 짝을 찾는다.

 

즉, 아래 비용 함수를 최소화하는 쌍을 찾는다.

 

[분류에 대한 CART 비용 함수]

$$ J(k, t_k) = \frac{m_{left}}{m}G_{left} + \frac{m_{right}}{m}G_{right} $$

여기서 \(G\)는 서브셋의 불순도, \(m\)은 서브셋의 샘플 수이다.

 

CART 알고리즘이 훈련 세트를 나누는 과정을 반복한다.

이 과정은 max_depth 매개변수로 정의된 최대 깊이가 되면 중지하거나 불순도를 줄이는 분할을 찾을 수 없을 때 멈춘다.

 

CART 알고리즘은 탐욕적 알고리즘 (greedy algorithm)이다. 맨 위 루트 노드에서 최적의 분할을 찾으며 이어지는 각 단계에서 이 과정을 반복한다. 현재 단계의 분할이 몇 단계를 거쳐 가장 낮은 불순도로 이어질 수 있을지는 고려하지 않는다. 참욕적 알고리즘은 종종 납득할만한 솔루션을 만들지만 최적의 솔루션을 보장하지는 않는다.

* 또한, overfitting 되기 쉬운 문제가 있다.

 

최적의 트리를 찾는 것은 NP-완전 (NP-Compete) 문제로 알려져 있다. 하지만 이 문제는 O(exp(m)) 시간이 필요하고 매우 작은 훈련 세트에도 적용하기 힘들어 '납득할 만한 좋은 솔루션'으로 만족해야 하는 문제가 있다.

 

** 불순도 : Gini index

** Binary tree : CART 알고리즘의 또 하나의 특징으로 가지 분기 시, 여러 개의 자식 노드가 아닌 단 두개의 자식 노드로 분기한다는 것.

 

 

5. 계산 복잡도

예측을 위해서는 결정 트리를 루트 노드에서 리프 노드까지 탐색한다.

일반적으로 결정 트리 탐색을 위해서 약 \( O(log_2(m)) \)개의 노드를 거쳐야 하므로 예측에 필요한 전체 복잡도는 특성 수와 무관하게 \( O(log_2(m)) \)이다. (m은 훈련 데이터 수)

따라서, 큰 훈련 세트를 다룰 때도 예측 속도가 매우 빠르다.

 

훈련 알고리즘은 각 노드에서 모든 훈련 샘플의 모든 특성을 비교한다.

각 노드에서 모든 샘플의 모든 특성을 비교하면 훈련 복잡도는 \( O(n \times mlog(m)) \)이 된다.

훈련 세트가 수천 개 이하의 샘플 정도로 작다면 사이킷런은 presort=True로 지정하면 미리 데이터를 정렬해 훈련 속도를 높일 수 있다. 하지만, 훈련 세트가 큰 경우 속도가 많이 느려진다.

 

 

6. 규제 매개변수

훈련 데이터에 대한 제약 사항이 거의 없는 결정 트리의 경우, 트리가 훈련 데이터에 아주 가깝게 맞추려고 하기 때문에 과대적합이 되기 쉽다.

 

• 비파라미터모델 (nonparametric model)
  • 모델 파라미터가 전혀 없는 것이 아니라 훈련 전 파라미터 수가 결정되지 않는 것
  • 모델 구조가 데이터에 맞춰져서 고정되지 않고 자유롭다
  • 결정 트리가 여기에 해당
• 파마리터 모델 (parametric model)
  • 미리 정의된 모델 파라미터 수를 가짐
  • 자유가 제한되고 과대적합이 될 위험이 줄어든다.
  • 반대로 과소적합될 위험은 커진다.

 

따라서, '규제'를 통해 과대적합을 피하기 위해 학습할 때 결정 트리의 자유도를 제한할 필요가 있다.

 

DecisionTreeClassifier에서 결정 트리의 형태를 제한하는 규제 매개변수들

• max_depth : 결정 트리의 최대 깊이 제어 (기본값은 None)
• min_samples_split : 분할되기 위해 노드가 가져야 하는 최소 샘플 수
• min_samples_leaf : 리프 노드가 가지고 있어야 할 최소 샘플 수
• min_weight_fraction_leaf : 리프 노드의 최대 수
• max_features : 각 노드에서 분할에 사용할 특성의 최대 수

여기서 min으로 시작하는 매개변수를 증가시키거나, max로 시작하는 매개변수를 감소시키면 모델에 규제가 커지고 과대적합의 위험이 감소한다.

 

moons 데이터셋에 훈련시킨 두 개의 결정 트리이다.

• 왼쪽 결정 트리 : 기본 매개변수를 사용하여 훈련 (즉, 규제없음)
• 오른쪽 결정 트리 : min_samples_leaf=4로 지정하여 훈련

결과적으로 왼쪽 모델이 과대적합되었고, 오른쪽 모델은 일반화 성능이 더 좋아보인다.

 

 

** 제한없이 결정 트리를 훈련시키고 불필요한 노드를 가지치기(pruning)하는 알고리즘도 있다.

순도를 높이는 것이 통계적으로 큰 효과가 없다면, 리프 노드 바로 위의 노드는 불필요할 수 있다.

 

대표적으로 카이제곱 검정(chi-squared test)같은 통계적 검정을 사용해 우연히 향상된 것인지 추정한다.

이 확률을 p-값이라고 부르며 어떤 임곗값보다 높으면 그 노드는 불필요한 것으로 간주되고 그 자식 노드는 삭제된다.

가지치기는 불필요한 노드가 모두 없어질 때까지 계속된다.

 

 

 

7. 회귀

결정 트리는 회귀 문제에도 사용할 수 있다.

사이킷런의 DecisionTreeRegressor을 사용해 잡음이 섞인 2차 함수 형태의 데이터셋에서 회귀 트리를 만들어보겠다.

# 2차식으로 만든 데이터셋 + 잡음
np.random.seed(42)
m = 200
X = np.random.rand(m, 1)
y = 4 * (X - 0.5) ** 2
y = y + np.random.randn(m, 1) / 10

 

훈련된 결정트리를 시각화 해보겠다.

from graphviz import Source
from sklearn.tree import export_graphviz

export_graphviz(
        tree_reg1,
        out_file=os.path.join(IMAGES_PATH, "regression_tree.dot"),
        feature_names=["x1"],
        rounded=True,
        filled=True
    )
    
Source.from_file(os.path.join(IMAGES_PATH, "regression_tree.dot"))

회귀 결정 트리

앞서 만든 분류 트리와의 차이는 각 노드에서 클래스를 예측하는 대신 어떤 값을 예측한다는 점이다.

 

예를 들어, \( x_1 = 0.6 \)인 샘플의 클래스를 예측한다고 가정해보자.

1. 루트 노드부터 트리를 순회하여 value=0.111 인 리프 노드에 도달
2. 이 리프 노드에 있는 110개 훈련 샘플의 평균 타깃값이 예측값이 됨
3. 이 예측값을 사용해 110개 샘플에 대한 평균제곱오차 (MSE)를 계산 => MSE = 0.015

 

from sklearn.tree import DecisionTreeRegressor

tree_reg1 = DecisionTreeRegressor(random_state=42, max_depth=2)
tree_reg2 = DecisionTreeRegressor(random_state=42, max_depth=3)
tree_reg1.fit(X, y)
tree_reg2.fit(X, y)

두 개의 결정 트리 회귀 모델의 예측

위 그래프를 보면 모델의 예측이 나타나있다.

각 영역의 예측값은 항상 그 영역에 있는 타깃값의 평균이 된다.

알고리즘은 예측값과 가능한 많은 샘플이 가까이 있도록 영역을 분할한다.

 

CART 알고리즘은 훈련 세트를 불순도를 최소화하는 방향으로 분할하는 대신 평균제곱오차(MSE)를 최소화하도록 분할한다.

 

[ 회귀를 위한 CART 비용 함수 ]

$$ J(k, t_k) = \frac{m_{left}}{m}MSE_{left} + \frac{m_{right}}{m}MSE_{right} $$

$$ \left\{\begin{matrix}
MSE_{node} = \sum_{i\in node}^{}(\hat{y}_{node}-y^{(i)})^2 \\
\hat{y}_{node} = \frac{1}{m_{node}}\sum_{i\in node}^{}y^{(i)}
\end{matrix}\right. $$

분류에서와 같이 회귀 작업도 결정 트리가 과대 적합되기가 쉽다.

 

tree_reg1 = DecisionTreeRegressor(random_state=42)
tree_reg2 = DecisionTreeRegressor(random_state=42, min_samples_leaf=10)
tree_reg1.fit(X, y)
tree_reg2.fit(X, y)

x1 = np.linspace(0, 1, 500).reshape(-1, 1)
y_pred1 = tree_reg1.predict(x1)
y_pred2 = tree_reg2.predict(x1)

결정 트리 회귀 모델의 규제

위와 같이 규제가 없을 때보다 min_samples_leaf=10 (리프 노드가 가지고 있어야 할 최소 샘플 수) 으로 지정하여 규제를 주었을 때 조금 더 일반화하기 쉬운 모델이 생성된다.

 

 

8. 불안정성

결정트리의 장점

• 이해하고 해석하기 쉬움
• 사용하기 편함
• 여러 용도로 사용할 수 있음
• 성능이 뛰어남

 

결정 트리의 단점

• 계단 모양의 결정 경계를 만들어 회전에 민감 (모든 분할이 축에 수직)
  • 아래 오른쪽 그래프의 경우 간단한 선형으로 구분될 수 있는 데이터셋임에도 불구하고 불필요하게 구불구불하게 분류됨. 훈련 세트는 완벽하게 학습하지만, 일반화되기 쉽지않음
  • 해결 방법 ) 훈련 데이터를 더 좋은 방향으로 회전시키는 PCA 기법 사용

훈련 세트의 회전에 민감한 결정 트리

• 훈련 데이터에 있는 작은 변화에도 매우 민감
  • 예를 들어 훈련 세트에서 가장 넓은 Iris-Versicolor을 제거하고 결정 트리를 훈련시키면 다음과 같은 모델이 만들어짐
  • 사이킷런에서 사용하는 훈련 알고리즘은 확률적이기 때문에 random_state 매개변수를 지정하지 않으면 같은 훈련 데이터에서도 다른 모델을 얻게 될 수 있음

훈련 세트의 세부사항에 민감한 결정 트리

이러한 결정 트리의 불안정성을 랜덤 포레스트를 통해 극복할 수 있다

랜덤 포레스트는 많은 트리에서 만든 예측을 평균하게 된다.

 

 

 

---

* 해당 포스팅은 머신러닝 학습 중 핸즈온 머신러닝 2판을 참고하여 작성하였습니다. *