수업 들은 기념 결정 트리(Decision Tree) 다시 정리하기 호호

https://bkshin.tistory.com/entry/%EB%A8%B8%EC%8B%A0%EB%9F%AC%EB%8B%9D-4-%EA%B2%B0%EC%A0%95-%ED%8A%B8%EB%A6%ACDecision-Tree

머신러닝 - 4. 결정 트리(Decision Tree)

위 블로그를 필사하며 공부

 

* 모든 텍스트와 이미지의 출처는 위 블로그입니다.

 

---

 

* 결정 트리 (Decision Tree)

 

: 특정 기준(질문)에 따라 데이터를 구분하는 모델

- 한 번의 분기 때마다 변수 영역을 두 개로 구분

 

출처: ratsgo's blog

 

출처: 텐서 플로우 블로그

- 데이터를 가장 잘 구분할 수 있는 질문들로 기준을 나눔

- 지나치게 많이 하면 위처럼 오버피팅이 됨.

   - 결정 트리에 아무 파라미터를 주지 않고 모델링하면 오버피팅이 됨

 

 

 

 

가지치기(Pruning)

: 오버피팅을 막기 위한 전략

 

- 트리의 최대 깊이나 터미널 노드의 최대 개수, or 한 노드가 분할하기 위한 최소 데이터 수 제한

- min_sample_split 파라미터를 조정하여 한 노드에 들어있는 최소 데이터 수를 정해줄 수 있음

ex. min_sample_split=10이라면, 한 노드에 10개의 데이터가 있을 경우 그 노드는 더 이상 분기 x

- max_depth를 통해 최대 깊이 지정 가능

ex. max_depth=4라면, 깊이가 4보다 크게 가지를 치지 않음

 

 

 

 

 

 

엔트로피(Entropy), 불순도(Impurity)

 

- 불순도(Impurity): 해당 범주 안에 서로 다른 데이터가 얼마나 섞여 있는지를 뜻함

출처: ratsgo's blog

- 위 그림에서 위쪽 범주는 불순도가 낮고, 아래쪽 범주는 불순도가 높다.

 

- 한 범주에 하나의 데이터만 있다면 불순도가 최소이고, 한 범주 안에 서로 다른 두 데이터가 정확히 반반이라면 불순도가 최대

- 결정트리는 불순도를 최소화하는 방향으로 학습을 진행함

 

- 엔트로피(Entropy): 불순도를 수치적으로 나타낸 척도

- 엔트로피가 높다=불순도가 높다 / 엔트로피가 낮다=불순도가 낮다

- 엔트로피가 1 = 불순도 최대 (한 범주 안에 서로 다른 데이터가 정확히 반반 있다.)

- 엔트로피가 0 = 불순도 최소 (한 범주 안에 하나의 데이터만 존재)

 

출처: 위 블로그

(Pi = 한 영역 안에 존재하는 데이터 가운데 범주 i에 속하는 데이터의 비율)

 

 

 

(예제)

출처: 위 블로그

- P_slow = 2/4 = 0.5

- P_fast = 0.5

->> 엔트로피: 1 (정확히 반반 있다.)

 

 

 

 

 

정보 획득 (Information gain)

: 분기 이전의 엔트로피에서 분기 이후의 엔트로피를 뺀 수치

- 엔트로피가 1인 상태에서 0.7로 바뀌었다면 정보 획득은 0.3

 

Information gain = entropy(parent) - [weighted average]entropy(children)

 

- entropy(parent): 분기 이전의 엔트로피

- entropy(children): 분기 이후의 엔트로피

- [weighted average]entropy(children): entropy(children)의 가중 평균

 

- 분기 이후 엔트로피에 대해 가중 평균을 하는 이유: 분기를 하면 범주가 2개 이상으로 쪼개지기 때문

- 범주가 1개라면 위 엔트로피 공식으로 바로 엔트로피 구할 수 있지만

- 범주가 2개 이상이라면 가중 평균을 활용해 분기 이후 엔트로피를 구함

 

 

- 결정 트리 알고리즘은 정보 획득을 최대화하는 방향으로 학습이 진행된다.

- 어느 feature의 어느 분기점에서 정보 획득이 최대화되는지 판단을 해 분기가 진행됨

 

 

 

 

 

---

 

 

 

(경사 기준 분기)

출처: 위 블로그

- steep은 총 3개이며 이 때 속도는 각각 slow, slow, fast

- flat은 총 2개이며 이 때 속도는 fast

   --->>> entropy(flat) = 0

 

* steep으로 분기했을 때,

- slow는 2개 --> P_slow=2/3

- fast는 1개 --> P_fast=1/3

   --->>> entropy(steep) = 0.9184 (공식 이용)

 

 

* 분기 이후 노드에 대한 가중평균은?

[weighted average] entropy(children) = weighted average of steep * entropy(steep) + weighted average of flat * entropy(flat)

= 3/4 * 0/9184 + 1/4 * 0

= 0.6888

 

Information gain = entropy(parent) - [weighted average] entropy(children)

= 1 - 0.688

= 0.3112

 

- 경사 feature를 기준으로 분기를 햇을 때 0.3112만큼의 정보 획득(information gain)이 있다는 뜻

 

 

 

 

(표면 기준 분기)

출처: 위 블로그

- bumpy는 총 2개이며 이 때 속도는 slow, fast

- smooth는 총 2개이며 이 때 속도는 slow, fast

-->> 하나의 범주에 서로 다른 데이터가 정확히 반반 있으므로 entropy(bumpy) = entropy(smooth) = 1

 

information gain = entropy(parent) - [weighted average] entropy(children)

= 1 - (2/4) * 1 - (2/4) * 1

= 0

 

- 즉, 표면을 기준으로 분기했을 때는 정보 획득이 전혀 x

 

 

 

 

 

(속도 제한 기준 분기)

출처: 위 블로그

- yes의 경우 slow, slow

- no의 경우 fast, fast

--->> entropy(yes) = entropy(no) = 0

 

즉, information gain = 1

 

 

---

 

 

- 경사, 표면, 속도제한 기준으로 분기를 했을 때 정보 획득은 각각 0.3112, 0, 1이다.

- 결정트리는 정보 획득이 가장 많은 방향으로 학습이 진행되므로 첫 분기점을 속도제한 기준으로 잡는다.

- 이런식으로 max_depth나 min_sample_split으로 설정한 범위까지 분기를 하게 된다.

 

이게 바로 결정트리의 전체적인 알고리즘 !!

 

 

 

 

 

 

---

처음 위 블로그로 결정 트리를 공부했을 때, 정보 획득 부분이 솔직히 전혀 이해가 가지 않았었다. 그러다 최근 학교 수업에서 배우고 다시 복습을 해보니 이해가 쏙쏙 .. 넘 재밌다 이런 공부 허허