[ML] 04. Decision Tree

목차

• 1. Decision Tree 동작원리
• 2. 트리 분할 측정 척도
  • 1) 지니불순도
  • 2) 정보이득
• 3. 트리분할 알고리즘 : CART
•  

1. Decision Tree 동작원리

의사결정 트리 분류기: 의사결정트리 생성하는 학습단계, 데이터 분류하는 분류단계

 

CART

각 노드에서 분할을 위한 특성과 해당특성의 값의 조합을 탐욕적으로 탐색
(=> Global Optima가 아닌 Local Optima 우선고려)

---

2. 트리 분할 측정 척도

1) 지니불순도

데이터가 클래스 별로 고르게 분포되어 있는지!

편중될 수록 값이 작고, 고를수록 값이 크다 (Impurity)

$$Gini=1-\sum_{k=1}^{K}p_{k}^{2}$$

 

ex) 두개 클래스가 존재할때,

한클래스에만 속한다면 지니불순도 $1-(1^{2}+0^{2})=0$

&

두클래스에 반반 속하면 지니불순도 $1-(0.5^{2}+0.5^{2}=0.5)$

 

$$G(X_{p},f)=\sum_{c}^{C_{f}}\frac{n_{c}}{n_{p}}Gini_{c}$$

$$\begin{align}&C_{f}: 특성 f를 기준으로 분할한 자식 노드 집합\\&Gini_{c}: 자식 노드 c에 있는 데이터의 지니불순도\\&n_{p}: 부모노드 p에 속하는 데이터 수\\&n_{c}: 자식 노드 c에 속하는 데이터 수\end{align}$$

2) 정보이득

트리 분할 후 얼마나 순도가 더 좋아졌는지 평가

= 트리 분할을 통해 불확실성(복잡도)이 얼마나 줄어드는지 평가

=> 트리 분할 전후의 엔트로피 값차이로 계산

 

정보량: 사건 발생을 알릴만한 가치, 가끔 발생할수록 가치가 큼

$$I(X=k)=log(\frac{1}{p(X=k)})$$

Entropy: 정보량의 기댓값, 모두가 동일한 확률을 가지는 것이 가장 최대 정보량을 가짐, 불확실성, 복잡도

$$H(X)=-\sum_{k=1}^{K}p(X=k)log(p(X=k))$$

(기대값=sum(확률*값))

 

불확실성이 트리 분할 후 얼마나 떨어졌는 지 평가

정보이득은 트리분할전(부모노드) 엔트로피와 트리 분할 후(자식노드) 엔트로피 값차이로 정의

$$I(X_{p},f)=H(X_{p})-\sum_{c}^{C_{f}}\frac{n_{c}}{n_{p}}H(X_{c})$$

 

정보 이득이 높을수록 좋은 분할

---

3. 트리분할 알고리즘 : CART

분할

정지-> 노드 샘플 수가 일정 수준 이하일때, 트리 깊이가 일정 수준 이상일때