[D&A 운영진 ML 스터디] 3주차 2차시

결정 트리(Decision Tree)의 학습과 시각화

# 학습
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)
tree_clf.fit(X, y)

# 시각화
from sklearn.tree import export_graphviz
export_graphvis(tree_clf, out_file=image_path("iris_tree.dot"),
    feature_names = iris.feature_names[2:], class_names = iris.target_names,
    rounded = True, filled=True)

!dot -Tpng iris_tree.dot -o iris_tree.png

• export_graphviz 함수를 통해 그래프를 iris_tree.dot 파일로 출력해 시각화
  • sample: 얼마나 많은 훈련 데이터가 해당 노드의 조건을 만족하는 수
  • value: 각 클래스별 해당 노드의 조건을 만족하는 수
  • gini: 불순도(impurity) 측정
    • 한 노드의 샘플이 모두 같은 클래스에 속해 있는 경우 해당 노드를 순수하다고 함
    • $gini = 0$
    • $G_i = 1-\Sigma^n_{k=1} p_{i,k}^2$
      • $i$: 노드, $k$: 클래스
      • 해당 노드에 속한 클래스의 비율

예측

• 루트노드부터 시작해 해당 조건을 만족하는지 검사
  • 만족할 경우 왼쪽 자식 노드로 이동, 만족하지 못할 경우에는 오른쪽 자식 노드로 이동
  • 해당 과정을 리프 노드를 만날 때까지 반복
    • 리프 노드: 자식 노드가 없는 노드
• 해당 예측 방법의 특성으로 인해 데이터 전처리가 거의 필요하지 않다는 장점
  • 스케일링, 정규화 필요하지 않음

해석

• 결정 트리는 직관적이고 결정 방식 이해가 쉬움
  • 화이트 박스이다.
  • 반대로 블랙박스는 예측 결과를 쉽게 설명하기 어려움
    • ex) 랜덤 포레스트, 신경망 등

클래스 확률 추정

• 한 샘플이 특정 클래스 $k$에 속할 확률 추정 가능
  • 해당 샘플에 대해 리프 노드를 찾기 위한 탐색
  • 해당 노드에 있는 클래스 $k$의 비율 반환
• 예측 시, 해당 노드에서 가장 확률이 높은 클래스 출력

CART 훈련 알고리즘

• scikit-learn에서는 결정 트리 훈련을 위해 CART(Classification and Regression Tree) 알고리즘 사용
• 훈련 세트를 하나의 특성 $k$의 임계값 $t_k$를 사용해 두 개의 서브셋으로 나눔
  • 그렇다면 $k$와 $t_k$는 어떻게 계산?
    • 크기에 따른 가중치가 적용된 가장 순수한 서브셋으로 나눌 수 있는 $(k,t_k)$ 짝을 찾음
• CART 비용함수를 최소화
  • $J(k,t_k) = \cfrac{m_{left}}{m} G_{left} + \cfrac{m_{right}}{m} G_{right}$
    • $G_{left/right}$: 서브셋의 불순도
    • $m_{left/right}$: 서브셋의 샘플 수
  • 해당 알고리즘은 Greedy 알고리즘
    • 하지만 최적의 트리를 찾는 알고리즘은 NP-완전 문제이다.
      • $O(e^m)$이 필요하고 매우 작은 훈련 세트에서 적용 어려워 사용 불가
• 위 과정을 반복
  • max_depth에 도달하거나 불순도를 줄이는 분할을 찾을 수 없을 때 중지
  • 그 외 매개변수도 중지 조건에 관여
    • min_samples_split
    • min_samples_leaf
    • min_weight_fraction_leaf
    • max_leaf_nodes

계산 복잡도

• 예측을 위해서는 결정 트리를 루트 노드에서부터 리프 노드까지 탐색
  • 일반적으로 결정 트리는 균형을 이루므로 약 $O(\log_2(m))$개의 노드 거쳐야 함
  • 각 노드는 하나의 특성값만 확인하기 때문에 전체 계산 복잡도는 특성 수와 무관
    • 큰 훈련 세트를 다룰 때도 예측 속도가 빠름
• 훈련 알고리즘은 각 노드에서 모든 훈련 샘플의 모든 특성을 비교
  • 각 노드에서 모든 샘플의 모든 특성을 비교하면 훈련 복잠도 $O(mn\log_2(m))$
  • 훈련 세트가 작을 경우 presort = True를 통해 미리 데이터를 정렬하여 훈련 속도 향상

지니 불순도 또는 엔트로피

• criterion = "entropy"를 사용 시, 지니 불순도 대신 엔트로피 불순도 사용
  • $H_i = -\Sigma^n_{k=1, p_{i,k}\ne0} p_{i,k} \log_2(p_{i,k})$
• 지니 불순도가 계산이 조금 더 빠름
• 지니 불순도는 가장 빈도 높은 클래스를 한쪽으로 고립시키는 경향 존재
  • 엔트로피는 조금 더 균현 잡힌 트리 제작
  • 하지만 사실상 둘이 비슷

규제 매개변수

• 결정 트리는 훈련 데이터에 대한 제약 사항 거의 없음
  • 선형 모델은 데이터가 선형일 것이라고 가정
• 제한을 두지 않으면 트리가 훈련 데이터에 아주 가깝게 맞추려고 하여 과대적합되기 쉬움
  • 모델 파라미터가 훈련되기 전에 파라미터 수가 결정되는 것이 아님: 비파라미터 모델
    • 모델이 자유로워 데이터에 맞춰짐
  • 반대로 파라미터 수가 미리 정해지는 파라미터 모델은 자유도가 제한되고 과대적합될 위험 높음
    • ex) 선형 모델
• 과대적합을 피하기 위해 결정 트리의 자유도 제한
  • 깊이 제한: max_depth (제한 없애고 싶을 경우 = None)
  • min_samples_split: 분할 되기 위해 노트가 가져야 하는 최소 샘플 수
  • min_samples_leaf: 리프 노드가 가지고 있어야 할 최소 샘플 수
  • min_weight_fraction_leaf: 가중치가 부여된 점체 샘플 수에서의 비율(min_samples_leaf와 유사)
  • max_leaf_nodes: 리프 노드의 최대 수
  • max_features: 각 노드에서 분할에 사용할 특성의 최대 수
  • min_으로 시작하는 매개변수를 증가, max_로 시작하는 매개변수를 감소시키면 모델 규제 증가
• 제한 없이 결정 트리를 훈련시킨 후, 불필요한 노드를 가지치기하는 알고리즘도 존재
  • 순도를 높이는 것이 통계적으로 큰 효과가 없다면 리프 노드 바로 위의 노드는 불필요
  • $\chi^2$ 검정과 같은 통계적검정을 사용해 우연히 순도가 향상된 것인지 추정
    • 해당 확률을 $p-$값이라고 부름
    • 특정 임계값보다 높으면 해당 노드는 불필요한 것으로 간주
      • 통상적으로 5% 사용
  • 가지치기는 불필요한 노드가 모두 없어질 때까지 계속

회귀

from sklearn.tree import DecisionTreeRegressor
tree_reg = DecisionTreeRegressor()
tree_reg.fit(X, y)

• 결정트리를 회귀 문제에서도 사용 가능
• 분류와 차이점은 각 노드에서 클래스 대신 어떤 값을 예측
  • value: samples개 훈련 샘플의 평균 타겟값
    • 즉 예측값임
  • MSE: 위 예측값을 사용해 samples개 훈련 샘플에 관한 MSE
• 예측값과 가능한 한 많은 샘플이 가까이 있도록 영역 분할
• 비용함수
  • $J(k, t_k) = \cfrac{m_{left}}{m}MSE_{left} + \cfrac{m_{right}}{m}MSE_{right}$
    • $MSE_{node} = \cfrac{1}{m_{node}} \Sigma_{i \in node} (\hat y - y^{(i)})^2$
    • $\hat y_{node} = \cfrac{1}{m_{node}} \Sigma_{i \in node} y^{(i)}$

불안정성

• 결정 트리는 계단 모양의 결정 경계를 만듦
  • 훈련 세트와 회전에 민감
  • 훈련 데이터를 더 좋은 방향으로 회전시키는 PCA 기법을 사용하면 해당 문제 해결
• random_state 매개변수를 지정하지 않으면 같은 훈련 데이터에서도 다른 모델 생성
  • 훈련 알고리즘은 확률적이기 때문

참고
Hands-on Machine Learning with Scikit-Learn, Keras & Tensorflow 2 - 오렐리앙 제롱