[ML] Decision Tree (의사결정 나무)

𝖣𝖾𝖼𝗂𝗌𝗂𝗈𝗇 𝖳𝗋𝖾𝖾

= 나무가 뒤집힌 모양

- 제일 꼭대기에 하나의 Root Node

- 각 가지들은 Branch(or Edge)

- 자식이 있는 Node는 Internal Node(or Decision Node)

- 가장 끝에 자식이 없는 Node는 Leaf Node(or Terminal Node, External Node)

​​

𝖦𝖾𝗇𝖾𝗋𝖺𝗍𝗂𝗇𝗀 𝖠𝗅𝗀𝗈𝗋𝗂𝗍𝗁𝗆

좋은 트리의 기준은 무엇일까 ?

- 모델의 정확도나 트리의 높이가 기준이 된다

- 트리의 높이는 최대한 짧은 것 (빠른 수행 속도)

- Leaf Node에서 통일된 Label의 데이터만 남는 것 (높은 분류 정확도, 의사결정 정확도)

​

처음에 어떤 Feature를 고려하는가에 따라 트리 깊이가 달라지는데, 어떤 방법으로 트리를 생성할까 ?

- Base : 트리의 생성 방법은 Root Node ~ Leaf Node로 이어짐

- Node에서 고려할 데이터가 이미 하나의 class에만 속하거나, 더 이상 고려할 Feature가 없으면 Leaf Node

- 데이터들을 가장 잘 나눠주는 Feature를 우선 선택

- 선택된 Feature에 대한 조건별로 자식 Node 생성

- 각 자식 Node에서 해당 조건을 만족하는 데이터만 고려하여 처음부터 반복

​

• Purity

- 한 쪽 데이터만 존재할 수록 더 pure 하다

ex) { o, o, x, x, x, x } 보다 { x, x, x, x, x, x }가 더 pure

​

• Entropy (Impurity)

- Purity의 반대

- 0 ~ 1 사이의 값 범위를 가진다

- Entropy가 크다 = 더 Chaotic 하다 = 분석할 정보가 더 많다

 

• 엔트로피 수식

Entropy를 tree 생성에 어떻게 적용할까 ?

- Information Gain 활용 = 부모노드 Entropy — 자식노드 Entropy

- 부모노드에서 정보의 함량이 더 크다

- 자식노드가 여러개인 경우가 많기 때문에, Weighted Average Entropy of Children을 구하여 IG 구함

- 자식 Entropy 값에 Instance 개수만큼 곱해주는 것

- IG가 가장 큰 Feature 선택, Feature별로 IG를 계산하고 트리의 결정노드로 먼저 선택

 

 

Feature가 Real-value Feature에 대해서는 어떻게 해야할까 ?

- Value ‘bin’을 사용

- 특정 Root Node로부터 모종의 분기 ( *열린구간 : [], 닫힌구간 : () )

​

 

* Tree 모양에 따른 용어

- edge에 화살표 존재유무가 큰 의미를 가지므로 구분하여 사용

Balanced Tree / Deep Tree / Bushy Tree / Left,Right Skewed

 

Decision Tree는 Overfitting 되기 쉽나 ?

- 쉽다. 그래서 Model의 Complexity 중요

- 학습하는 순간, 이미 Overfitting 되는 지 정해짐

- Feature별로 IG를 고려하여 위에서 밑으로 내려온다 (학습데이터에 과하게 맞춰짐)

- 현재 노드에서 최적으로 보이는 Feature를 선택하고, 뒤쪽 노드는 신경쓰지 않는다

- 첫 단추부터 잘못끼워진 셈 (나비효과)

​

Decision Tree의 Feature 값들은 Normalization이 필요한가 ?

- 필요없다. 수치만 바뀔뿐 같은 노드 형태이다

​

𝖣𝖾𝖼𝗂𝗌𝗂𝗈𝗇 𝖳𝗋𝖾𝖾 𝖲𝗎𝗆𝗆𝖺𝗋𝗒

- Model 구현과 이해가 쉽다 (사람이 눈으로 보고 이해하고 설명 가능 [White Box])

- Powerful한 Model이 아니라, 복잡한 문제에서는 성능이 떨어짐