Networks/Hands-On 머신러닝 정리

Hands-On Machine Learning 정리 - 머신러닝(Chapter 6: 결정 트리)

코딩하는 Español되기 2024. 10. 21. 03:00

SVM 같이 결정 트리(Decision Tree)는 분류, 회귀, 다중출력 작업도 가능한 다재다능한 머신러닝 알고리즘입니다.

또한 매우 복잡한 데이터셋도 훈련이 가능한 강력한 알고리즘입니다.

이전에 과대적합이 나오긴 하지만 2장에서 사용했던 주택 가격 데이터셋을 완벽하게 맞추는 DecisionTreeRegressor 모델을 사용했습니다.

 

해당 장에서는 결정 트리의 훈련, 시각화, 예측 방법에 대해 알아봅니다. 그다음 CART 훈련 알고리즘과 트리에 규제를 가하는 방법 및 회귀 문제에 적용하는 방법에 대해 알아보겠습니다.


Chap6 목차

1. 결정 트리 학습, 시각화, 예측

    - 결정 트리 학습과 시각화

    - 예측

2. 클래스 확률 추정, CART 훈련 알고리즘

    - 클래스 확률 추정

    - CART 훈련 알고리즘

3. 계산복잡도, 지니 불순도/엔트로피, 규제 매개변수

    - 계산 복잡도

    - 지니 불순도 또는 엔트로피

    - 규제 매개변수

4. 회귀와 불안정성

    - 회귀

    - 불안정성


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

아래는 붓꽃 데이터셋(4장)에 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 파일로 출력하여 시각화

    ● .dot 파일을 .png 이미지로 변경

    ● .dot 파일을 Graphviz 패키지에 있는 dot 명령줄 도구로 PDF나 PNG 같은 포맷으로 변경

    ※ 사이키럿 0.21 버전에서 dot 파일을 만들지 않고 바로 트리를 그리는 plot_tree() 함수가 추가됨

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"))

1-2 예측하기

○ 가정 : 새로 발견한 붓꽃의 품종을 분류

○ 순서

    ● 루트 노드(깊이가 0인 꼭대기 노드)에서 시작

    ● 꽃잎의 길이가 2.45cm보다 짧은지 검사

        IF True : 왼쪽의 자식 노드(깊이 1)로 이동 & 리프 노드(자식이 없는 노드)이므로 추가 검사 X

                       → 새로 발견한 꽃의 품종 = Iris-Setosa(class=setosa)로 예측

        Elif False : 오른쪽 자식 노드로 이동

             IF 꽃잎 너비 < 1.75cm : Iris-Versicolor(깊이 2, 왼쪽 노드)

             Else: Iris-Virginica(깊이2, 오른쪽 노드)

※ 결정 트리의 장점 中 1 = 데이터 전처리가 거의 필요 없음(특성 스케일 맞추기, 평균을 원점으로 맞추는 작업 등)

노드의 sample 속성 : 얼마나 많은 훈련 샘플이 적용되었는지 count한 것

노드의 gini 속성 : 불순도(impurity)측정

    ● When 한 노드의 모든 샘플이 같은 클래스에 속함 then gini=0

       e.g. 깊이 1의 왼쪽 노드

gini 불순도 공식

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

위 식에서 p_{i, k} :  i 번째 노드에 있는 훈련 샘플 중 클래스 k에 속한 샘플의 비율



※ 사이킷런은 이진트리만 만드는 CART 알고리즘을 사용

    So, 리프 노드 외의 모든 노드는 자식 노드를 두 개씩 가지게 됨(True | False)

    But, ID3 같은 알고리즘의 경우 둘 이상의 자식 노드를 가진 결정 트리를 만들 수 있음

 

아래 그림은 결정 트리의 결정 경계를 보여줌

○ 굵은 수직선 : 루트 노드(깊이 0)의 결정 경계(꽃잎 길이 = 2.45cm)

○ 왼쪽 영역 : 순수 노드(Only Iris-Setosa)

○ 오른쪽 영역 : !순수노드 So, 깊이 1의 오른쪽 노드는 꽃잎 너비 = 1.75cm에서 나눠짐(파선)

                         max_depth = 2 이기에 결정 트리는 더 분할되지 않음

                         If max_depth =3 then 두 노드가 각각 결정 경계를 추가로 생성(점선)

[그림 4-2로 되돌아가기]

[결정 경계 그림 코드]

더보기
from matplotlib.colors import ListedColormap

def plot_decision_boundary(clf, X, y, axes=[0, 7.5, 0, 3], iris=True, legend=False, plot_training=True):
    x1s = np.linspace(axes[0], axes[1], 100)
    x2s = np.linspace(axes[2], axes[3], 100)
    x1, x2 = np.meshgrid(x1s, x2s)
    X_new = np.c_[x1.ravel(), x2.ravel()]
    y_pred = clf.predict(X_new).reshape(x1.shape)
    custom_cmap = ListedColormap(['#fafab0','#9898ff','#a0faa0'])
    plt.contourf(x1, x2, y_pred, alpha=0.3, cmap=custom_cmap)
    if not iris:
        custom_cmap2 = ListedColormap(['#7d7d58','#4c4c7f','#507d50'])
        plt.contour(x1, x2, y_pred, cmap=custom_cmap2, alpha=0.8)
    if plot_training:
        plt.plot(X[:, 0][y==0], X[:, 1][y==0], "yo", label="Iris setosa")
        plt.plot(X[:, 0][y==1], X[:, 1][y==1], "bs", label="Iris versicolor")
        plt.plot(X[:, 0][y==2], X[:, 1][y==2], "g^", label="Iris virginica")
        plt.axis(axes)
    if iris:
        plt.xlabel("Petal length", fontsize=14)
        plt.ylabel("Petal width", fontsize=14)
    else:
        plt.xlabel(r"$x_1$", fontsize=18)
        plt.ylabel(r"$x_2$", fontsize=18, rotation=0)
    if legend:
        plt.legend(loc="lower right", fontsize=14)

plt.figure(figsize=(8, 4))
plot_decision_boundary(tree_clf, X, y)
plt.plot([2.45, 2.45], [0, 3], "k-", linewidth=2)
plt.plot([2.45, 7.5], [1.75, 1.75], "k--", linewidth=2)
plt.plot([4.95, 4.95], [0, 1.75], "k:", linewidth=2)
plt.plot([4.85, 4.85], [1.75, 3], "k:", linewidth=2)
plt.text(1.40, 1.0, "Depth=0", fontsize=15)
plt.text(3.2, 1.80, "Depth=1", fontsize=13)
plt.text(4.05, 0.5, "(Depth=2)", fontsize=11)
plt.show()
모델 해석 : 화이트 박스와 블랙박스
- 결정 트리는 직관적이고 결정 방식을 이해하기 쉬움. 이러한 모델을 화이트 박스 모델이라고 함.
- 랜덤 포레스트, 신경망 등은 블랙박스 모델
- 블랙박스 모델의 경우 이러한 알고리즘들은 성능이 뛰어나고 예측을 만드는 연산과정을 쉽게 확인이 가능하지만 왜 그런 예측을 했는지 쉽게 설명할 수 없음
- e.g. 신경망이 어떤 사람이 사진에 있다고 판단했을 때 무엇이 이런 예측을 초래했는지 파악이 어려움

 

2. 클래스 확률 추정과 CART 훈련 알고리즘

2-1 클래스 확률 추정

○ 결정 트리는 한 샘플이 특정 클래스 k에 속할 확률을 추정 가능

    ● 샘플에 대해 리프 노드를 찾기 위해 트리를 탐색

    ● 그 노드에 있는 클래스 k의 훈련 샘플의 비율 반환(예를 들어 길이 = 5cm, 너비 = 1.5cm인 꽃잎 발견)

    ● 이에 해당하는 리프노드는 깊이 2에서 왼쪽 노드 

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

tree_clf.predict_proba([[5, 1.5]]) # array([[0. , 0.90740741, 0.09259259]])

    ● 출력 : 가장 높은 확률을 가지는 Versicolor(클래스 1)을 출력

tree_clf.predict([[5, 1.5]]) # array([1])

 

2-2 CART 훈련 알고리즘

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

○ 방법

    ● 훈련 세트를 하나의 특성 k의 임곗값 t_k를 사용해 두 개의 서브넷으로 나눔(꽃잎의 길이 ≤ 2.45cm)

    ● (크기에 따른 가중치가 적용된) 가장 순순한 서브넷으로 나눌 수 있는 (k, t_k) 짝을 찾음

    ● 알고리즘이 최소화해야 하는 비용 함수(분류에 따른 CART 비용 함수)는 아래와 같음

    ● 훈련 세트를 나눈 후 같은 방식으로 서브셋을 나누는 행위를 반복

    ● max_depth가 되면 중지하거나 불순도를 줄이는 분할을 찾을 수 없을 때 중지

※ 중지 조건에 관여하는 매개변수(아래에서 자세히 설명)

    : min_samples_split, min_samples_leaf, min_weight_fraction_leaf, max_leaf_nodes

 

[분류에 따른 CART 비용 함수]

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

- G: 왼쪽/오른쪽 서브셋의 불순도

- m: 왼쪽/오른쪽 서브셋의 샘플 수

CART 알고리즘
○ Greedy Argorithm으로 맨 위 루트 노드에서 최적의 분할을 찾으며 이어지는 각 단계에서 이 과정을 반복
○ 현재 단계의 분할이 몇 단계를 거쳐 가장 낮은 불순도로 이어질 수 있을지 없을지는 고려하지 않음
○ 훌륭한 솔루션을 제공하지만, 최적의 솔루션을 보장하지는 않음
○ 최적의 트리를 찾는 것 : NP-완전(NP-Complete) 문제
    ● But O(exp(m))의 시간이 필요하고 매우 작은 훈련 세트에 적용하기 어려움

 

3. 계산 복잡도, 지니 불순도/엔트로피, 규제 매개변수

3-1 계산 복잡도

○ 예측을 하기 위해서는 결정 트리를 루트 노드에서부터 리프 노드까지 탐색해야 함

○ 일반적으로 결정 트리는 거의 균형을 이루고 있으므로 결정 트리 탐색을 위해서는 약 O(log_2(m))개의 노드를 거쳐야 함

○ 각 노드는 하나의 특성값만 확인하기 때문에 예측에 필요한 전체 복잡도 = 특성 수와 무관하게 O(log_2(m))

   So, 큰 훈련 세트를 다룰 때도 예측 속도가 빠름

 

3-2 지니 불순도 또는 엔트로피

○ 기본적으로 지니 불순도가 사용되지만 criterion 매개변수를 "entropy"로 지정하여 엔트로피 불순도를 사용 가능

※ 엔트로피는 분자의 무질서함을 측정하는 것으로 원래 열역학의 개념. 분자가 안정되고 질서 정연하면 엔트로피는 0에 가까움

※ 메시지 평균 정보 양을 측정하는 섀넌의 정보 이론도 여기에 포함(모든 메시지가 동일할 때 엔트로피가 0이 됨)

 

○ 머신러닝에서 어떤 세트가 한 클래스의 샘플만 담고 있다면 엔트로피 = 0

○ 지니 불순도와 엔트로피 둘 다 비슷한 트리를 만들어 내지만 지니 불순도가 조금 더 계산이 빠른 편

○ But 다른 트리가 만들어지는 경우 지니 불순도가 가장 빈도 높은 클래스를 한쪽 branch로 고립시키는 경향이 있는 반면 

   엔트로피는 조금 더 균형 잡힌 트리를 만들어줌

○ 아래 식에서 i 번째 노드의 엔트로피 정의를 보여줌

[엔트로피]

$$ H_i = -\underset{p_{i,k\neq 0}}{\sum_{k=1}^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 $$

3-3 규제 매개변수

○ 결정 트리는 훈련 데이터에 대한 제약 사항이 거의 없음

○ 그래서 제한을 두지 않는다면 대부분 과대적합되기 쉬움

○ 모델 파라미터가 전혀 없는 것이 아니라 훈련되기 전에 파라미터 수가 결정되지 않음(비파라미터 모델)

   So, 모델 구조가 데이터에 맞춰져서 고정되지 않고 자유로움

○ 반대로 선형 모델 같은 파라미터 모델은 미리 정의된 모델 파라미터 수를 가짐

   So, 자유도 제한, 과대적합 위험 감소(But 과소적합될 위험은 증가)

○ DecisionTreeClassifier에서 결정 트리 형태를 제한하는 다른 매개변수

    ● min_samples_split : 분할되기 위해 노드가 가져야 하는 최소 샘플 수

    ● min_samples_leaf : 리프 노드가 가지고 있어야 할 최소 샘플 수

    ● min_weight_fraction_leaf : min_samples_leaf와 같지만 가중치가 부여된 전체 샘플 수에서의 비율

    ● max_leaf_nodes : 리프 노드의 최대 수

    ● max_features : 각 노드에서 분할에 사용할 특성의 최대 수

○ 기본 모델과, min_samples_leaf = 4로 규제를 준 모델 비교 

    ● 왼쪽 모델은 과대적합된 반면 오른쪽 모델은 일반화 성능이 더 좋아 보임

[min_samples_leaf 매개변수를 사용한 규제]

더보기
from sklearn.datasets import make_moons
Xm, ym = make_moons(n_samples=100, noise=0.25, random_state=53)

deep_tree_clf1 = DecisionTreeClassifier(random_state=42)
deep_tree_clf2 = DecisionTreeClassifier(min_samples_leaf=4, random_state=42)
deep_tree_clf1.fit(Xm, ym)
deep_tree_clf2.fit(Xm, ym)

fig, axes = plt.subplots(ncols=2, figsize=(10, 4), sharey=True)
plt.sca(axes[0])
plot_decision_boundary(deep_tree_clf1, Xm, ym, axes=[-1.5, 2.4, -1, 1.5], iris=False)
plt.title("No restrictions", fontsize=16)
plt.sca(axes[1])
plot_decision_boundary(deep_tree_clf2, Xm, ym, axes=[-1.5, 2.4, -1, 1.5], iris=False)
plt.title("min_samples_leaf = {}".format(deep_tree_clf2.min_samples_leaf), fontsize=14)
plt.ylabel("")

plt.show()
제한 없이 결정 트리를 훈련시키고 불필요한 노드를 가지치기(Pruning; 제거)하는 알고리즘(사후 가지치기)도 있음
※ 사이킷런 0.22 버전에서 비용 복잡도 기반의 사후 가지치기를 위한 ccp_alpha 매개변수가 결정 트리와 트리 기반의 앙상블 모델에 추가됨
○ 순도를 높이는 것이 통계적으로 큰 효과가 없다면 리프 노드 바로 위 노드는 불필요할 수 있음
○ 대표적으로 카이제곱 검정(chi-squared test) 같은 통계적을 사용하여 우연히 향상된 것인지를 추정(귀무가설)
○ 이 확률을 p-값이라고 부르며 어떤 임곗값보다 높으면 그 노드는 삭제됨
※ p-값이 임곗값보다 높으면 순도 향상이 우연에 의한 것일 수 있다고 봄
카이제곱 값이 커지면 p-값은 감소
○ 가지치기는 불필요한 노드가 모두 없어질 때까지 계속됨

 

4. 회귀와 불안정성

4-1 회귀

DecisionTreeRegressor를 사용하여 회귀 트리 생성

    ● 잡음이 섞인 2차 함수 형태의 데이터셋에서 max_depth=2로 설정

    ● 훈련 데이터는 y = 4(x-0.5)^2를 사용해 만들었으며 y 값에 랜덤 한 잡음이 섞여있음

○ 분류 트리와 매우 비슷해 보이지만 각 노드에서 클래스를 예측하는 대신 어떤 값을 예측한다는 점이 차이

    ● e.g. x_1 = 0.6 인 샘플의 타깃값을 예측 → value=0.111인 리프 노드에 도달

               → 110개 샘플에 대한 MSE(평균제곱오차)를 계산하여 0.015가 됨

               → 모델의 예측은 오른쪽 그림의 왼쪽 그래프에 나오고 max_depth=3으로 설정하면 오른쪽과 같이 됨

 

[Python 코드]

더보기

- 훈련 데이터

# 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 sklearn.tree import DecisionTreeRegressor

tree_reg = DecisionTreeRegressor(max_depth=2, random_state=42)
tree_reg.fit(X, y)

 

 

- 시각화(왼쪽 그림)

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"))

 

- 시각화(오른쪽 그림)

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)

def plot_regression_predictions(tree_reg, X, y, axes=[0, 1, -0.2, 1], ylabel="$y$"):
    x1 = np.linspace(axes[0], axes[1], 500).reshape(-1, 1)
    y_pred = tree_reg.predict(x1)
    plt.axis(axes)
    plt.xlabel("$x_1$", fontsize=18)
    if ylabel:
        plt.ylabel(ylabel, fontsize=18, rotation=0)
    plt.plot(X, y, "b.")
    plt.plot(x1, y_pred, "r.-", linewidth=2, label=r"$\hat{y}$")

fig, axes = plt.subplots(ncols=2, figsize=(10, 4), sharey=True)
plt.sca(axes[0])
plot_regression_predictions(tree_reg1, X, y)
for split, style in ((0.1973, "k-"), (0.0917, "k--"), (0.7718, "k--")):
    plt.plot([split, split], [-0.2, 1], style, linewidth=2)
plt.text(0.21, 0.65, "Depth=0", fontsize=15)
plt.text(0.01, 0.2, "Depth=1", fontsize=13)
plt.text(0.65, 0.8, "Depth=1", fontsize=13)
plt.legend(loc="upper center", fontsize=18)
plt.title("max_depth=2", fontsize=14)

plt.sca(axes[1])
plot_regression_predictions(tree_reg2, X, y, ylabel=None)
for split, style in ((0.1973, "k-"), (0.0917, "k--"), (0.7718, "k--")):
    plt.plot([split, split], [-0.2, 1], style, linewidth=2)
for split in (0.0458, 0.1298, 0.2873, 0.9040):
    plt.plot([split, split], [-0.2, 1], "k:", linewidth=1)
plt.text(0.3, 0.5, "Depth=2", fontsize=13)
plt.title("max_depth=3", fontsize=14)

plt.show()

○ CART 알고리즘은 훈련 세트를 불순도를 최소화하는 방향으로 분할하는 대신

    MSE를 최소화하도록 분할하는 것을 제외하고는 앞의 설명과 거의 비슷하게 작동

[알고리즘이 최소화하기 위한 비용 함수]

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

$$ 여기서 \begin{cases}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{cases} $$

 

○ 회귀작업에서도 결정 트리가 과대적합되기 쉬움

    ● 규제가 없다면 왼쪽 그림과 같이 예측(과대 적합)

    ● min_samples_leaf = 10으로 지정하여 예측(그럴싸한 모양의 그래프가 생성)

[결정 트리 회귀 모델의 규제 시각화 코드]

더보기
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)

fig, axes = plt.subplots(ncols=2, figsize=(10, 4), sharey=True)

plt.sca(axes[0])
plt.plot(X, y, "b.")
plt.plot(x1, y_pred1, "r.-", linewidth=2, label=r"$\hat{y}$")
plt.axis([0, 1, -0.2, 1.1])
plt.xlabel("$x_1$", fontsize=18)
plt.ylabel("$y$", fontsize=18, rotation=0)
plt.legend(loc="upper center", fontsize=18)
plt.title("No restrictions", fontsize=14)

plt.sca(axes[1])
plt.plot(X, y, "b.")
plt.plot(x1, y_pred2, "r.-", linewidth=2, label=r"$\hat{y}$")
plt.axis([0, 1, -0.2, 1.1])
plt.xlabel("$x_1$", fontsize=18)
plt.title("min_samples_leaf={}".format(tree_reg2.min_samples_leaf), fontsize=14)

plt.show()

4-2 불안정성

○ 결정 트리가 많은 장점이 있지만 몇 가지 제한 사항이 있음

    [제한 사항 1] 계단 모양의 결정 경계를 생성(모든 분할은 축에 수직) So, 훈련 세트의 회전에 민감

    e.g. 왼쪽 결정 트리는 쉽게 데이터셋을 구분하지만,

           오른쪽 결정트리(데이터셋을 45º 회전한)는 불필요하게 구불구불해짐 → 잘 일반화될 것 같지 않음

   문제를 해결하는 방법 : 훈련 데이터를 더 좋은 방향으로 회전시키는 PCA기법을 사용하는 것(8장)

    [제한 사항 2] 훈련 데이터에 있는 작은 변화에도 매우 민감하다.

    e.g. 훈련 세트에서 가장 넓은 Iris-Versicolor(꽃잎 길이= 4.8cm, 꽃잎 너비 = 1.8cm인 것)을 제거하고 훈련하면?

           이전 그림과 매우 다른 모습

   문제를 해결하는 방법 : 랜덤 포레스트(7장)에서 많은 트리에서 만든 예측을 평균해 불안정성을 극복