의사결정나무(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)