머신러닝 6장 결정트리

6. 결정트리

1. 결정트리 훈련과 활용

• 결정트리 방식의 최대 장점: 데이터 전처리 거의 불필요. 필요한 경우도 존재함
• 사이킷런의 DecisionTreeClassifier모델 활용
• 붓꽃 데이터 활용. 꽃잎의 길이와 너비 기준으로 분류

• max_depth=2: 결정트리의 최대 깊이 지정. 여기서는 최대 2번의 데이터셋 분할 허용. 기본값은 None이며 무제한 데이터셋 분할 허용.

    iris = load_iris(as_frame=True)
    X_iris = iris.data[["petal length (cm)", "petal width (cm)"]].values
    y_iris = iris.target
      
    tree_clf = DecisionTreeClassifier(max_depth=2, random_state=42)
    tree_clf.fit(X_iris, y_iris)
  

결정트리 시각화

• 위 코드를 시각화한것이다.
• 사이킷런의 export_graphiv()함수 활용
• pdf.png 등 많은 종류의 파일로 변환 가능
• 시간은 계산량이 적기 때문에 오래 안걸림

• 가지를 쪼개는 기준은 불순도로 잡음 그림에서는 gini가 불순도임
• 가지를 쪼갤수록 불순도가 낮아짐

petal length (cm) <= 2.45

위 코드는 꽃잎의 길이가 2.45보다 큰지 물어보는것이다.

True라면 왼쪽으로 False라면 오른쪽으로 간다.

쪼갠 결과는 samples을 보면 된다. (좌측은 50, 우측은 100임)

value를 보면 좌측은 50, 0, 0으로 분류가 끝남

but, 우측은 0, 50, 50으로 분류가 안끝나서 이어서 분류를 진행

petal width (cm) <= 1.75

위 코드는 꽃잎의 너비가 1.75보다 큰지 물어보는것이다.

조건에 맞춰 분류를 진행하면 된다

이 이상 분류는 가능하지만 코드에 max_depth=2이 있다.

때문에 깊이가 2 이후로는 더 진행이 불가능하다.

트리 구성 요소

• 노드 (node): 가지 분할이 시작되는 지점
• 루트 노드(root): 맨 상단에 위치한 노드이며
• 리프 노드(leaf): 더 이상의 가지분할이 발생하지 않는 노드이며, 따라서 자식 노드를 갖지 않는다.

지니 불순도

i번째는 아래와 같은 순서를 지닌다.

• $G_i$: $i$번째 노드의 지니 불순도

  \[G_i = 1 - \sum_{k=1}^{K} (p_{i,k})^2\]
• $p_{i,k}$는 $i$번째 노드에 있는 훈련 샘플 중 클래스 $k$에 속한 샘플의 비율. $K$는 클래스의 총 개수.

• 예제: 깊이 2의 왼편 노드 $G_4$ 의 지니 불순도

  \[G_4 = 1 - (0/54)^2 - (49/54)^2 - (5/54)^2 = 0.168\]
• CART 알고리즘으로 만들어진 tree를 지니 불순도를 사용해 노드를 분할함 낮을수록 좋음

• CART 알고리즘에서 지니 불순도를 기반으로 하는 비용 함수

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

결정경계

아래 그림은 max_depth=3으로 지정해서 학습한 결정트리의 결정경계를 보여준다.

• 1차 분할 기준: 꽃잎 길이 2.45cm
• 2차 분할 기준: 꽃잎 너비 1.75cm

• 3차 분할 기준: 꽃잎 길이 4.85cm와 4,95cm

  

• 3차 분할을 why 길이로 했는가?
  • 지니 불순도가 가장 낮은 값이 길이이기 때문

분류 결과 vensicolor가 우세한곳은 1군데임

예측값

• predict_proba() 메서드: 지정된 샘플의 클래스별 추정 확률을 계산

    >>> tree_clf.predict_proba([[5, 1.5]]).round(3)
    array([[0.   , 0.907, 0.093]])
  

• predict() 메서드: 품종 클래스를 예측하며, 가장 높은 추정 확률을 갖는 품종으로 지정

    >>> tree_clf.predict_proba([[5, 1.5]]).round(3)
    array([1])
  

2. CART 훈련 알고리즘

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

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

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

탐욕적 알고리즘 사용. 해당 노드를 기준으로 지니 불순도가 가장 낮은, 가장 순수한 두 개의 부분집합으로 분할. 최적의 분할이란 보장은 X

• 분할 과정 반복: max_depth등 규제의 한계에 다다르거나 더 이상 불순도를 줄이는 분할이 불가능할 때까지 진행

CART 알고리즘의 시간 복잡도

• 훈련 샘플이 크기순으로 정렬된 경우($n, m$은 각각 특성 개수와 샘플 개수를 나타냄)
  • 각 노드에서 분류하는 데 걸리는 시간: $O(n\cdot m\cdot \log_2(m))$
  • 결정트리를 완성하는 데 걸리는 시간: $O(n\cdot m^2\cdot \log_2(m))$
  • 규제가 있는 경우 좀 더 빨라짐
• 훈련 셋 크기가 몇 천보다 크면 정렬이 더 오래 걸림
• 가장 빠른 정렬 알고리즘의 복잡도 = $O(m \log m)$

지니 불순도 vs 엔트로피

• $i$ 노드의 엔트로피($H$)

  \[\begin{split}H_i = -\sum_{\substack{k=1\\p_{i,k}\neq 0}}^{K} p_{i,k} \log_2(p_{i,k})\end{split}\]

• 지니 불순도를 사용할 때와 비교해서 큰 차이가 나지는 않는다. 만약 차이가 난다면 엔트로피 방식이 결정 트리를 보다 좌우 균형이 잡히도록 자식 노드로 분할한다. 하지만 기본적으로 별 차이가 없고 지니 불순도 방식이 보다 빠르게 훈련되기에 기본값으로 지정되었다.

비파라미터 모델

• 결정트리 모델은 데이터에 대해 어떤 가정도 안 함
• 규제를 가하지 않으면 과대적합 위험이 높아짐

사이킷런 DecisionTreeClassifier 규제 하이퍼파라미터

• 규제 강화 방법 보통 이름이 아래 접두사를 따름
  • min접두사 사용 규제: 값을 키울 것
  • max_접두사 사용 규제: 값을 감소시킬 것

하이퍼 파라미터	기능
max_depth	결정트리의 높이 제한
min_samples_split	노드 분할에 필요한 최소 샘플 개수
min_samples_leaf	리프에 포함된 최소 샘플 개수
min_weight_fraction_leaf	샘플 가중치 합의 최솟값, 여기서는 사용 X
max_leaf_nodes	최대 리프 개수
max_features	분할에 사용되는 특성 개수, 랜덤 포레스트에서 사용

예제: 규제 적용

• 예제: 초승달 데이터셋에 대한 결정트리 모델 학습

  

  • 왼편: 규제 X, 보다 정교하며 과대적합
  • 오른편: min_samples_elaf=4, 일반화 성능이 보다 좋음

3. 회귀 결정트리

사이킷런의 DecisionTreeRegressor 예측기 활용

• 결정트리 알고리즘 아이디어를 거의 그대로 이용해 회귀 문제에 적용 가능

    tree_reg = DecisionTreeRegressor(max_depth=2, random_state=42)
    tree_reg.fit(X_quad, y_quad)
  

예제: 잡음이 포함된 2차 함수 형태의 데이터셋

• 왼쪽 그림이 위 시각화한 회귀 결정트리를 나타낸것이다.

• 붉은색 선은 평균값을 의미한다.
• 우측 그림은 한단계 더 쪼갠것이다. (샘플이 총 8개임)

회귀용 CART 알고리즘과 비용함수

• $\text{MSE}_\text{node}$: 해당 노드의 평균제곱오차 (MSE)
• $m_\text{node}$: 해당 노드에 속하는 샘플 수

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

  \[\begin{split}\begin{align*}J(k, t_k) &= \frac{m_\text{left}}{m}\, \text{MSE}_\text{left} + \frac{m_\text{right}}{m}\, \text{MSE}_\text{right} \\[2ex]\text{MSE}_\text{node} &= \frac{1}{m_\text{node}} \sum_{i\in \text{node}} (\hat y_{node} - y^{(i)})^2\\[1ex]\hat y_\text{node} &= \frac{1}{m_\text{node}} \sum_{i\in\text{node}} y^{(i)}\end{align*}\end{split}\]

규제

• 분류의 경우처럼 규제가 없으면 과대적합 발생
• 왼쪽: 규제 X, 과대적합 발생
• 우측: min_samples_leaf=10
  • 리프 노드가 갖는 최소 샘플수를 10개로 제한함

4. 결정트리 단점

단점 1: 훈련 셋 회전 민감도

• 결정트리 알고리즘은 성능이 매우 우수하나 기본적으로 주어진 훈련 셋에 민감히 반응
• 결정트리는 항상 축에 수직인 분할을 사용. 따라서 조금만 회전을 가해도 결정 경계가 많이 달라짐
• 예제: 우측 그래프: 왼쪽 그래프를 45도 회전시킨 훈련 셋 학습

예제: PCA() 모델 기법 적용 데이터 변환

• PCA 기법: 데이터셋을 회전시켜 특성들 사이 연관성을 약화시킴

• 예제: PCA 기법으로 회전시킨 붓꽃 데이터셋에 분류 결정트리를 훈련시킨 결과

    pca_pipeline = make_pipeline(StandardScaler(), PCA())
    X_iris_rotated = pca_pipeline.fit_transform(X_iris)
    tree_clf_pca = DecisionTreeClassifier(max_depth=2, random_state=42)
    tree_clf_pca.fit(X_iris_rotated, y_iris)
  

  

붓꽃 데이터 셋은 회전시키지 않으면 대각선으로 분류가 됨

단점2 : 훈련 셋 변화 민감도

• 훈련 데이터의 작은 변화에도 매우 민감함
• 동일한 모델을 훈련 시켜도 다른 결과 가능(아래 그래프 참고)
  • 특성을 무작위로 선택하기 때문

• 많은 트리에서 만든 예측값의 평균을 활용 추천(7장 랜덤포레스트 모델 참고)

  

그림 그리는 코드는 안봐도 됨 대신 그림은 이해해야 함

보통 코드에서 tree가 tree의 모든 정보를 담고 있다고 함

tree = tree_clf.tree_

위 코드가 있으면 tree에 tree_clf.tree_를 사용하면 트리의 노드, 구조, 특성 중요도 등이 tree에 들어간다는 소리임