[ML] 의사결정나무 Decision Tree

의사결정나무 Decision Tree

https://pasongsong.tistory.com/136?category=1026284 

[자료구조] 트리 Tree

---

 의미

• 변수들로 기준을 만들고 이것을 통하여 샘플을 분류하고 분류된 집단의 성질을 이용하여 추정하는 모형

장점

• 위의 표를 보면 샘플의 play tennis의 결과에 영향을 미치는 요인들을 Tree 구조를 통해 직관적으로 볼 수 있음
• 해석력이 높음 
• 직관적이고 범용적임(독립변수, 종속변수가 범용적이든 연속적이든 사용 가능)

단점

• 높은 변동성 (샘플이 조금만 바뀌어도 tree가 바뀔 수 있음)
• 샘플에 민감할 수 있음

---

용어

트리 구조에 보편적으로 사용되는 용어

• node : 분류의 기준이 되는 변수가 위치
• Parent node : 상위 노드 (상대적)
• Child node : 하위 노드 (상대적)
• Root node : 상위 노드가 없는 가장 위의 노드
• Leaf node (tip) : 하위 노드가 없는 가장 아래의 노드
• Internal node : Leaf node가 아닌 노드
• Edge : 샘플을 분류하는 조건이 위치하는 곳
• Depth : root node에서 특정 노드까지 도달하기 위해 거쳐야 하는 Edge의 수

---

• 분류 트리 : 종속 변수가 범주형 변수일 때 사용함
• 회귀 트리 : 종속 변수가 연속형 변수일 때 사용함

---

분순도/ 불확실성

• 순도 homogeneity -> 증가
• 불순도 impurity -> 감소
• 불확실성 uncertainty -> 감소

하는 방향으로 학습을 진행함. 이는 information gain을 통해 얼마나 학습이 진행됐는지 확인할 수 있음

엔트로피 Entropy

• 섞여있는 정도를 의미함 
• 엔트로피가 높다면 섞임이 강하고 엔트로피가 낮다면 섞임이 약한 상태이다.
• 아래와 같이 분류점을 이용하여 Decision Tree를 구성하기 위해서 사용함

$$ -plog_{2}p-(1-p)log_{2}(1-p) $$

0 또는 1일 확률이 최소, 0.5일 확률이 최대가 되게 하는 함수

Depth가 깊어질수록 Entroy가 낮아짐

outlook으로 분류한 것에 대한 Entropy

 

---

Entropy 와 흰돌이 나올 확률 사이의 그래프

Entropy가 0.5일 때 속성을 가지고 0으로 변화를 시킨다.

---

Information Gain

• 엔트로피의 차이를 알려주는 것 -> 이를 통해 어떠한 변수를 통해 얼마의 이득을 취했는지 알 수 있음
• Parent node를 정할 때 사용함
• \( Entropy_{before} - Entropy_{after} \)

outlook으로 분류한 것에 대한 Entropy

\( Entropy_{after} \) \( = \frac{5Entrpy_{a1}+4Entrpy_{a2}+5Entrpy_{a3} }{5+4+5} \)\( =  \frac{n_{1}Entrpy_{a1}+n_{2}Entrpy_{a2}+n_{3}Entrpy_{a3} }{n_{1}+n_{2}+n_{3}} 
\)

\( n_{1},n_{2},n_{2} \)는 데이터의 개수이고 이것을 가중치 값으로 씀

---

각각의 속성에 대해서 IG을 구하고 IG가 높은 속성을 tree위에 설정한다.