[ML] Decision Tree - classification / regression

Decision Tree

• 분류 / 회귀 작업 / 다중출력 작업이 가능한 머신러닝 알고리즘
• 랜덤 포레스트의 기본 구성 요소

 

 

1. 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)

2. 예측하기

새로 발견한 붓꽃의 품종을 분류해보자

 

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

 

• impurity(불순도)
  • 한 노드의 모든 샘플이 같은 클래스에 속해 있다면 이 노드를 순수(gini=0)하다고 한다.
  • impurity 측정 (지니(gini) 불순도)
    • $G_{i} = 1 - \sum_{k=1}^{n}p_{i,k}^{2}$
    • $p_{i,k}$는 i번째 노드에 있는 훈련 샘플 중 클래스 k에 속한 샘플의 비율
    • 즉, 한 개의 집합에서 대체 샘플링(sampling with replacement)을 두 번 할 경우 두 개의 요소가 서로 다른 클래스를 지닐 확률이다
    • 결정 트리가 클래스 예측을 할 때, 지니 불순도 측정값을 최소화 하도록 split한다.

• 화이트박스와 블랙박스
  • 결정 트리는 매우 직관적이고 결정 방식을 이해하기 쉽다 -> 화이트 박스
  • 랜덤 포레스트 / 신경망 -> 블랙박스
  • 블랙박스 모델의 알고리즘은 성능이 뛰어나고 예측을 만드는 연산 과정을 쉽게 확인할 수 있다. 하지만 왜 그런 예측을 만드는지는 쉽게 설명하기 어렵다.
  • 반면에 결정트리는 수동으로 직접 따라 해볼 수도 있는 간단하고 명확한 분류 방법을 사용한다.

 

3. 클래스 확률 추정

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

먼저 이 샘플에 대해 리프 노드를 찾기 위해 트리를 탐색하고 그 노드에 있는 클래스 k의 훈련 샘플의 비율을 반환한다.

 

 

4. CART 훈련 알고리즘

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

• 아이디어
  • 훈련 세트를 하나의 특성 k의 임곗값 $t_{k}$를 사용해 두 개의 서브셋으로 나눈다 (e.g. 꽃잎의 길이 < 2.45cm)
  • 크기에 따른 가중치가 적용된 가장 순수한 서브셋으로 나눌 수 있는 (k, $t_{k}$) 짝을 찾는다.
  • 이 알고리즘의 최소화해야 하는 비용 함수 -> [식 6.2]
  • 훈련 세트를 성공적으로 둘로 나누었다면 같은 방식으로 서브셋을 또 나누고 (반복)
  • 이 과정은 최대 깊이가 되면 중지하거나 불순도를 줄이는 분할을 찾을 수 없을 때 멈추게 된다.
  • 이 방법은 O(exp(m)) 시간이 필요해 매우 작은 훈련 세트에도 적용하기 어렵다 ㅠㅠ
  • 최적의 트리를 찾는 것은 NP-Complete problem으로 알려져 있다.

 

[식 6.2]

 

Information gain

• 정보 획득(IG): feature이 class에 대해 제공하는 “정보”의 양을 측정

• CART(Classification And Regression Tree) 알고리즘의 목적 함수는 각 분할에서 IG를 최대화 하는 것이다.

 f: 분할에 사용되는 특성  Dp,Dj: 부모/자식 노드의 데이터 셋

 N: 샘플의 전체 개수       Nj: j번째 자식 노드의 샘플 개수

 I: 불순도 지표

 

• IG가 가장 높은 속성이 먼저 tested/split 된다.

 

 

5. 지니 불순도 or 엔트로피

기본적으로 지니 불순도(gini impurity)가 사용되지만 criterion 매개변수를 "entropy"로 지정하여 엔트로피 불순도를 사용할 수 있다.

• 엔트로피: 분자의 무질서함을 측정하는 것으로 원래 열역학의 개념
• 어떤 세트가 한 클래스의 샘플만 담고 있다면 엔트로피가 0이다.
• i번째 노드의 엔트로피 정의: $H_{i} = - \sum_{k=1 , P_{i,k}≠0}^{n}P_{i,k}\log_{2}(P_{i,k})$
• 보통 지니 불순도랑 엔트로피는 별 차이 없지만, 새로운 다른 트리가 만들어지는 경우 지니 불순도가 가장 빈도 높은 클래스를 한쪽 가지(branch)로 고립시키는 경향이 있는 반면 엔트로피는 조금 더 균형 잡힌 트리를 만든다.

Entropy

• m개의 레코드가 속하는 A영역에 대한 entropy

• A영역을 두 개의 부분 집합 (R1, R2)로 분할 

    Ri: 분할 전 레코드 중 분할 후 i 영역에 속하는 레코드의 비율

• 분기 전보다 분기 후에서 엔트로피가 감소하면 데이터를 두 개의 부분 집합으로 나눈다

 

* Entropy와 Information Gain

- Entropy: 각 노드들의 impurity를 측정

- IG: 선택한 attribute가 training data를 얼마나 잘 나눴는지를 측정. 나누기 전 각 노드들의 entropy 합과, 나눈 후의 노드들의 entropy를 구해서 계산

 

 

6. 규제 매개변수

결정 트리는 훈련 데이터에 대한 제약사항이 거의 없다. 하지만 제한을 안두면 overfitting되기 쉽다

• 비파라미터 모델(nonparametric model): 훈련되기 전에 파라미터 수가 결정되지 않는 모델. 모델 구조가 데이터에 맞춰져서 고정되지 않고 자유롭다.
• 파라미터 모델(parametric model): 미리 정의된 모델 파라미터 수를 가지므로 자유도가 제한되고 overfitting될 위험이 줄어든다. (but upderfitting될 위험이 커짐)

 

7. 회귀(Regression)

회귀 트리 만들기

from sklearn.tree import DecisionTreeRegressor

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

• 분류 트리처럼 클래스를 예측하는 것이 아니라 어떤 값을 예측한다.
• 예를 들어 $x_{1}$=0.6인 샘플의 클래스를 예측한다고 가정해보면 이는 결국 value=0.1106인 리프 노드에 도달하게 된다. 
• 각 영역의 예측 값 = 그 영역에 있는 타깃값의 평균
• 알고리즘은 예측값과 가능한 한 많은 샘플이 가까이 있도록 영역을 분할한다.
• CART 알고리즘은 훈련 세트를 불순도를 최소화하는 방향으로 분할하는 대신 평균제곱오차(MSE)를 최소화하도록 분할한다.

 

8. 불안정성

결정 트리의

• 장점: 편하고 여러 용도로 사용할 수 있으며, 성능도 뛰어나다
• 단점: 계단 모양의 decision boundary를 만들어서 훈련 세트의 회전에 민감하다. 훈련 데이터에 있는 작은 변화에도 매우 민감.
• 문제 해결: PCA 기법, 랜덤 포레스트(많은 트리에서 만든 예측을 평균하여 이런 불안정성을 극복)

 

 

Model training

• 재귀적 분기(recursive partitioning)

• 입력 변수 영역을 두 개로 구분

• 가지치기(pruning)

• 너무 자세하게 구분된 영역을 통합

 

• Recursive partitioning
  1. 한 변수 기준으로 정렬

  2. 가능한 모든 분기점에 대해 엔트로피/지니계수를 구해 분기 전과 비교해 정보 획득을 조사.                       분기지점을 첫 레코드와 나머지 레코드로 두고, 1번 레코드와 나머지 레코드 간의 엔트로피를 구한 뒤 분기 전후 엔트로피와 비교해 정보획득을 조사합니다. 이후 분기 지점을 두번째 레코드로 두고 처음 두 개 레코드와 나머지 레코드 간의 엔트로피를 계산한 뒤 정보획득을 알아봅니다. 이렇게 순차적으로 계산한 뒤

  3. 다른 변수를 기준으로 정렬 후 같은 작업 반복
  4. 모든 경우의 수 중에서 정보획득이 가장 큰 변수를 가진 점을 택해 분기를 한다
• Pruning
  
  
  • 가지치기라고 데이터를 버리는게 아니라 분기를 합치는 개념
  • Full tree: 모든 terminal node의 순도가 100%인 상태 
  • Full tree를 생성한 뒤 적절한 수준에서 terminal node를 결합해주어야 한다.
  • 이유: 분기가 너무 많아 학습데이터에 과적합(overfitting)할 염려가 생겨서
  • 의사결정트리에서 분기 수가 증가할 때 처음에는 새로운 데이터에 대한 오분류율이 감소하나 일정 수준 이상이 되면 증가하는 현상이 발생
    •  검증 데이터에 대한 오분류율이 증가하는 시점에서 가지치기 해야함
  • terminal node가 너무 많으면 새로운 데이터에 대한 예측 성능인 일반화(generalization) 능력이 매우 떨어질 위험이 있다.
  • 가지치기의 비용함수 -> 이 비용함수를 최소로 하는 분기를 찾아내도록 학습됨

CC(T): 의사 결정 트리의 비용 복잡도 

ERR(t): 검증데이터에 대한 오분류율

L(t): terminal node의 수 (구조의 복잡도)

 

 

 

 

 

 

 

출처:

책 - Hands-On Machine Learning with Scikit-Learn & TensorFlow

블로그 - https://ratsgo.github.io/machine%20learning/2017/03/26/tree/