의사결정나무(2) (Decision Tree)

의사결정나무(2) (Decision Tree)

의사결정나무의 분류 모델을 설명하고 Information Gain 에 대해서 설명한다.

1. 의사결정나무 분류 모델 concept

파란색 점이 들어 왔을 때 파란색점은 빨강색으로 예측

초록색 점이 들어오면 주위의 검정색 점이 5개로 검정색으로 예측

2. 의사결정나무 분류나무 모델

각 관측치 마다 반응 변수 값 $y_{i} = 1,2,….,k$ 즉 k 개의 클래스 존재

$R_{m}$ : 끝노드 m에 해당하며 $N_{m}$관측치 개수를 가지고 있음

$\hat{p}_{mk}$ : 끝노드 m에서 k 클래스에 속해 있는 관측치의 비율

$\hat{p}_{mk} = \dfrac{1}{N_{m}}\sum_{x_{i} \in R_{m}}I(y_{i} = k)$

예)

끝노드에 데이터가 1이 3개 0이 2개(2개의 클래스) 로 분포

1은 $\dfrac{3}{5}$

0은 $\dfrac{2}{5}$

끝노드 m으로 분류된 관측치는 k(m) 클래스로 분류

$k(m) = argmax_{k}\hat{p}_{mk}$

1 class 의 값($\dfrac{3}{5}$) 이 더 크다

$\hat{p}_{10} = 0.4, \hat{p}_{11} = 0.6$

$argmax_{k}(0.4, 0.6) = 1$ 이다. 1번 클래스 이다.

$\hat{f}(x) = \sum_{m=1}^{5}k_{m}I{(x_{1},x_{2}) \in R_{m}}$

$= k_{1}I{(x_{1},x_{2}) \in R_{1}} + k_{2}I{(x_{1},x_{2}) \in R_{2}}$

$+ k_{3}I{(x_{1},x_{2}) \in R_{3}} + .. + k_{5}I{(x_{1},x_{2}) \in R_{5}}$

$k(m) = argmax_{k}\hat{p}_{mk}$

$\hat{p}_{mk} = \dfrac{1}{N_{m}}\sum_{x_{i} \in R_{m}}I(y_{i} = k)$

3. 분류나무모델의 비용함수(불순도 측정)

Misclassification rate : $\dfrac{1}{N_{m}}\sum_{i \in R_{m}}I(y_{i} \ne k(m)) = 1 – \hat{p}_{(mk)m}$

Gini Index : $\sum_{k \ne \acute{k}}\hat{p}_{mk}\hat{p}_{m\acute{k}} = \sum_{k=1}^{K}\hat{p}_{mk}(1-\hat{p}_{mk})$

Cross-entropy : $-\sum_{k=1}^{K}\hat{p}_{mk}log\hat{p}_{mk}$

4. 분류나무모델 분할변수 분할점 결정방법

모든 경우의 수를 대입하여 불순도가 가장 낮아지는지 계산한다. 비용함수가 가장 낮은값을 찾는다.

5. Misclassification rate(오분류율) – 비용함수

분할법칙

  • 분할변수와 분할기준은 목표변수의 분포를 가장 잘 구별해주는 쪽으로 정함
  • 목표변수의 분포를 잘 구별해주는 측도로 순수도(purity) 또는 불순도(impurity)를 정의
  • 예를 들어 클래스 0과 클래스 1의 비율이 45%와 55%인 노드는 각 클래스의 비율이 90%와 10%인 마디에 비하여 순수도가 낮다(또는 불순도가 높다)라고 해석
  • 각 노드에서 분할변수와 분할점의 설정은 불순도의 감소가 최대가 되도록 선택

L 노드의 오분류율 = 21/(63+21) = 21 / 84 = 0.25

R 노드의 오분류율 = 37/(37+79) = 37/116 = 0.32

총 오분류율 = (37/116)*(116/200) + (21/84)*(84/200) = 0.29

6. Gini 지수 – 비용함수

위 그림을 보면 얼룩말 6마리, 코뿔소 1마리

7. Entropy 지수 – 비용함수

Entropy 값은 1에 가까울 수록 불순도가 높다.

8. Information Gain(IG)

the expect reduction in entropy caused by partitioning the data according to this variable(특정 변수를 사용했을 때 entropy 감소량)

IG(S,A) – Entropy(S) – $\sum\dfrac{|S_{v}|}{|S|}Entropy(S_{v})$

전체 entropy에서 특정변수 A 를 사용했을 때 entropy의 감소량

wind에 대한 IG 계산

$Entropy(S_{false}) = -\dfrac{6}{8}log_{2}(\dfrac{6}{8}) – \dfrac{2}{8}log_{2}(\dfrac{2}{8})$ 으로 계산된다.

IG(S,Humidity) = 0.151 의 값이 나온다.

Humidity의 IG의 값이 크다 즉 Humidity 변수가 Winde 변수보다 영향이 크다.

9. 개별트리 모델의 단점

  • 계층적 구조로 인해 중간에 에러가 발생하면 다음 단계로 에러가 계속 전파
  • 학습 데이터의 미세한 변동에도 최종 결과에 크게 영향
  • 적은 개수의 노이즈에도 크게 영향
  • 나무의 최종노드 개수를 늘리면 과접합 위험(Low Bias, Large Variance)

해결방안 -> 랜덤 포래스트(Random forest)

랜덤포레스트 (Random Forests)

답글 남기기