[핸즈온 머신러닝] 6장

AI/Hands-on ML

[핸즈온 머신러닝] 6장 - 결정 트리

KIM DEON 2021. 1. 3. 23:20

6. 결정 트리(decision tree)

- SVM처럼 분류와 회귀 작업, 그리고 다중출력 작업도 가능한 머신러닝 알고리즘

- 매우 복잡한 데이터셋도 학습할 수 있는 강력한 알고리즘

(2장에서 캘리포니아 주택 가격 데이터셋을 완벽하게 맞추는 DecisionTreeRegressor 모델 훈련)

- 가장 강력한 ML 알고리즘 중 하나인 랜덤 포레스트의 기본 구성 요소

6.1 결정 트리 학습과 시각화

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)

=> DecisionTreeClassifier(max_depth=2, random_state=42)

from graphviz import Source
from sklearn.tree import export_graphviz #conda install python-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"))

※ export_graphviz 수행시 ExecutableNotFound 에러

=>conda install python-graphviz 로 해결

6.2 예측하기

- 위 붓꽃의 품종을 분류하는 결정 트리가 예측하는 방법

루트 노드에서 꽃잎의 길이가 2.45cm보다 짧다면, 왼쪽 자식 노드로 이동(깊이1, 왼쪽 노드)
- 이 노드가 리프 노드(자식 노드를 가지지 않는 노드)이므로 Iris-Setosa 클래스로 예측
루트노드에서 꽃잎의 길이가 2.45cm보다 길다면, 오른쪽 자식 노드로 이동
- 이 노드는 리프 노드가 아니므로 추가로 검사
- 꽃잎의 너비가 1.75cm보다 작다면 Iris-Versicolor(깊이2, 왼쪽 노드)
sample 속성 - 얼마나 많은 훈련 샘플이 적용되었는가
- (깊이1, 오른쪽) 100개의 훈련 샘플의 꽃잎 길이가 2.45cm보다 김
  - (깊이2, 왼쪽) 그 중 54개 샘플의 꽃잎 너비가 1.75보다 짧음
value 속성 - 노드에서 각 클래스에 얼마나 많은 훈련 샘플이 있는가
- (맨 오른쪽 아래 노드) Iris-Setosa 0개, Iris-Versicolor 1개, Iris-Virginica 45개
gini 속성 - 불순도 측정
- 한 노드의 모든 샘플이 같은 클래스에 속해 있다면 이 노드를 순수(gini=0)하다고 함
- (깊이1, 왼쪽 노드)는 Setosa 훈련 샘플만 가지므로 순수 노드이며 gini 점수가 0
- (깊이2, 왼쪽 노드)의 gini 점수는 1-(0/54)^2-(49/54)^2-(5/54)^2 ≈ 0.168
  - 아래 식에서 P_i,k는 i번째 노드에 있는 훈련 샘플 중 클래스 k에 속한 샘플의 비율

- 결정 트리의 장점 중 하나는 데이터 전처리가 거의 필요하지 않다는 것

(특성의 스케일을 맞추거나 평균을 원점에 맞추는 작업이 필요하지 않음)

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

리프 노드 외의 모든 노드는 자식 노드를 두개 씩 가짐(yes or no)
ID3 같은 알고리즘은 둘 이상의 자식 노드를 가진 결정 트리를 만들 수 있음

- 결정 트리의 결정 경계

굵은 수직선이 루트 노드(깊이 0)의 결정 경계를 나타냄 => 꽃잎 길이=2.45cm
왼쪽 영역은 순수 노드(Setosa만 존재)이므로 더 이상 나눌 수 없음
오른쪽 영역은 순수 노드가 아니므로 깊이 1의 오른쪽 노드는 꽃잎 너비=1.75cm에서 나누어짐 (파선)
- max_depth가 2이므로 결정 트리는 더 분할되지 않음
- max_depth가 3이면 깊이 2의 두 노드가 각각 (점선처럼) 결정 경계를 추가로 만듦

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

- 화이트박스 모델

결정 트리와 같이 직관적이고 결정 방식을 이해하기 쉬운 모델

- 블랙 박스 모델

랜덤 포레스트나 신경망
성능이 뛰어나고 예측을 만드는 연산 과정을 쉽게 확인할 수 있지만
왜 그런 예측을 만드는지 쉽게 설명하기 여러움
ex) 신경망이 어떤 사람이 사진에 있다고 판단했을 때 무엇이 이런 예측을 낳게 했는지 파악하기 어려움

6.3 클래스 확률 추정

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

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

- 그 노드에 있는 클래스 k의 훈련 샘플의 비율을 반환

길이가 5cm이고 너비가 1.5cm인 꽃잎을 발견했다고 가정했을 때,
이에 해당하는 리프 노드는 (깊이 2, 왼쪽 노드)이므로 결정 트리는 그에 해당하는 확률을 출력
즉, Setosa 0% (0/54), Versicolor 90.7% (49/54), Virginica 9.3% (5/54)
클래스를 하나 예측한다면 가장 높은 확률을 가진 Iris-Versicolor(클래스1)를 출력할 것

tree_clf.predict_proba([[5, 1.5]])

=> array([[0. , 0.90740741, 0.09259259]])

tree_clf.predict([[5, 1.5]])

=> array([1])

- 추정된 확률은 [결정 트리의 결정 경계] 그래프의 오른쪽 아래 사각형 안에서는 어느 위치든 동일

길이가 6cm, 너비가 1.5cm인 꽃잎도 위 예시와 확률이 같음 (Virginica에 더 가까워 보이지만)

tree_clf.predict_proba([[6, 1.5]])

=> array([[0. , 0.90740741, 0.09259259]])

6.4 CART 훈련 알고리즘

사이킷런은 결정 트리를 훈련시키기 위해 (트리를 성장시키기 위해) CART(classification and regression tree) 알고리즘을 사용

- 훈련 세트를 하나의 특성 k의 임계값 t_k를 사용해 두 개의 서브셋으로 나눔 (ex. 꽃잎의 길이 <= 2.45cm)

- k와 t_k를 고르는 방법

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

- CART 알고리즘이 훈련 세트를 성공적으로 둘로 나누었다면, 같은 방식으로 서브셋을 또 나누고, 그 후 서브셋의 서브셋을 나누는 방식으로 반복

이 과정은 최대 깊이(max_depth)가 되면 중지하거나
불순도를 줄이는 분할을 찾을 수 없을 때 멈추게 됨
다른 몇 개의 매개변수도 중지 조건에 관여
- min_samples_split, min_sam ples_leaf, min_weight_fraction_leaf, and max_leaf_nodes

※ CART 알고리즘은 탐욕적 알고리즘

- 맨 위 루트 노드에서 최적의 분할을 찾으며 이어지는 각 단계에서 이 과정을 반복

- 현재 단계의 분할이 몇 단계를 거쳐 가장 낮은 불순도로 이어질 수 있을지 없을지 고려하지 않음

- 즉, 최적의 솔루션을 보장하지 않음

- 최적의 트리를 찾는 것은 NP-완전 문제로 알려져 있음

이 문제는 O(exp(m)) 시간이 필요
매우 작은 훈련 세트에도 적용하기 어려움
그러므로 탐욕적 알고리즘으로 만족하는 것이 좋음

6.5 계산 복잡도

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

- 일반적으로 결정 트리를 탐색하기 위해서 약 O(log2(m))개의 노드를 거쳐야 함(m: 훈련데이터 수)

- 각 노드는 하나의 특성값만 확인하기 때문에 예측에 필요한 전체 복잡도는 O(log2(m))

=> 큰 훈련 세트를 다룰 때도 예측 속도가 매우 빠름

훈련 알고리즘은 각 노드에서 모든 훈련 샘플의 모든 특성을 비교함(max_features 지정시 그 보다는 적은)

- 각 노드에서 모든 샘플의 모든 특성을 비교하면 훈련 복잡도는 O(n x mlog2(m))

- 훈련 세트가 작을 경우(수천 개 이하) 사이킷런은 미리 데이터를 정렬하여 훈련 속도를 높일 수 있음(presort=True)

* 사이킷런 0.21버전에서 히스토그램 기반 그레이디언트 부스팅이 추가되었고 presort 매개변수로 얻을 수 있는 성능 향상이 크지 않기 때문에 사이킷런 0.24버전에서 결정 트리와 그레이디언트 부스팅 클래스의 presort 매개변수가 삭제되었음

6.6 지니 불순도 또는 엔트로피?

지니 불순도

- 기본적으로 사용

- DecisionTreeClassifier의 criterion 매개변수 기본 값은 "gini"

엔트로피 불순도

- criterion 매개변수를 "entropy" 로 지정

- 열역학 개념에서, 분자가 안정되고 질서 정연하면 엔트로피가 0에 가까움

- 메시지의 평균 정보 양을 측정하는 섀넌의 정보이론에서, 모든 메시지가 동일하면 엔트로피가 0

- 머신러닝에서는 불순도의 측정 방법으로 자주 사용

어떤 세트가 한 클래스의 샘플만 담고 있다면 엔트로피가 0
깊이 2의 왼쪽 노드의 엔트로피는 − (49/54) x log2(49/54) − (5/54) x log2(5/54) ≈ 0.445

※ 지니 불순도와 엔트로피 중 어떤 것을 사용해야하는가

- 실제로 큰 차이가 없으며, 비슷한 트리를 만들어냄

- 지니 불순도가 조금 더 계산이 빠르므로 기본값으로 좋음

- 다른 트리가 만들어지는 경우

지니 불순도가 가장 빈도 높은 클래스를 한쪽 가지로 고립시키는 경향이 있는 반면
엔트로피는 조금 더 균형 잡힌 트리

6.7 규제 매개변수

결정 트리는 훈련 데이터에 대한 제약 사항이 거의 없음 (선형 모델은 데이터가 선형일 거라 가정하는 반면)

제한을 두지 않으면 트리가 훈련 데이터에 아주 가깝게 맞추려 해 과대적합되기 쉬움

- 결정 트리는 모델 파라미터가 없는 것이 아니라(보통 많음)

- 훈련되기 전에 파라미터 수가 결정되지 않음 => 비파라미터 모델

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

- 파라미터 모델(ex. 선형 모델)은 미리 정의된 모델 파라미터 수를 가짐

자유도가 제한되며, 과대적합될 위험이 줄어듬
과소적합될 위험은 커짐

훈련 데이터에 대한 과대적합을 피하기 위해 학습할 때 결정 트리의 자유도를 제한할 필요가 있음 => 규제

- 규제 매개변수는 사용하는 알고리즘에 따라 다르지만

- 적어도 결정 트리의 최대 깊이는 제어 가능

사이킷런의 max_depth 매개변수(기본값=None, 제한 없음)
max_depth를 줄이면 과대적합의 위험 감소

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

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

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

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

- max_leaf_nodes : 리프 노드의 최대 수

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

=> min으로 시작하는 매개변수를 증가시키거나 max로 시작하는 매개변수를 감소시키면 모델에 규제가 커짐

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

- 왼쪽 결정 트리 : 기본 매개변수 사용해 훈련, 규제 없음

과대적합되었음

- 오른쪽 결정 트리 : min_samples_leaf=4로 지정하여 훈련

일반화 성능이 더 좋을 것으로 보임

※ 가지치기 pruning (제거)

제한 없이 결정 트리를 훈련시키고 불필요한 노드를 가지치기 (= 사후 가지치기)

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

- 대표적으로 카이제곱 검정 같은 통계적 검정을 사용하여 순도 향상이 우연히 향상된 것인지 추정(귀무가설)

- 이 확률을 p-값이라고 부름

- p-값이 어떤 임계값보다 높으면 그 노드는 불필요한 것으로 간주, 그 자식노드 삭제

임계값은 하이퍼파라미터로 조정되지만, 통상적으로 5%
가지치기는 불필요한 노드가 모두 없어질 때까지 계속됨

6.8 회귀

- 결정 트리를 회귀 문제에 사용할 수 있음

- 사이킷런의 DecisionTreeRegressor를 사용해, 잡음 섞인 2차 함수 형태의 데이터셋에서 max_depth=2 설정으로 회귀 트리 훈련

# Quadratic training set + noise
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)
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"))