Decision Tree

참고 블로그 및 자료 

- https://ratsgo.github.io/machine%20learning/2017/03/26/tree/

의사결정나무(Decision Tree) · ratsgo's blog

순천향대학교 정영섭 교수님 강의.

 

Decision Tree

Decision Tree 란?

> 말 그대로 의사를 결정해주는 나무처럼 생긴 모델을 말한다.

 

 

출처 - https://ratsgo.github.io/machine%20learning/2017/03/26/tree/

 

decision tree는

데이터를 분석하여

데이터 간 존재하는 패턴을 예측 가능한

규칙의 조합으로 나타낸다.

 

 

초기 지점 root node를 시작으로

분기를 거듭할 수록 데이터의 개수는 줄어들고 

terminal node의 데이터 개수를 모두 합하면

root node의 데이터 개수와 같다.

 

그리고 terminal node의 개수는 분리된 

집합의 개수이며

위 그림처럼 terminal node가 3개라면

전체 데이터가 3개의 부분집합으로 나눠진 셈이다.

 

 

 

 

의사결정나무는 분류(classification)와 회귀(regression) 모두 가능하다.

범주나 연속형 수치 모두 예측할 수 있다.

 

의사결정나무의 범주예측, 즉 분류 과정은 

새로운 데이터가 특정 terminal node에 속한다는 정보를 확인한 뒤

해당 terminal node에서 가장 빈도가 높은 범주에

새로운 데이터를 분류하게 된다.

 

회귀의 경우는

해당 teminal node의 종속 변수 y 의 평균 예측값으로

반환하게 되는데 

 

이 때 예측값의 종류는 terminal node 개수와 일치한다.

 

terminal node 수가 3개뿐이라면

새로운 데이터의 수와 상관없이

의사결정나무는 딱 3종류의 답만을 출력한다.

 

 

좋은 트리의 조건

 

1) terminal node(leaf node) 에서 통일된label (class)의 데이터만 남는 것
>높은분류정확도, 의사결정정확도
2) 트리의 높이(혹은깊이)가 짧은 것
>빠른 수행 속도

 

 

 

트리 생성 방법.

 

순서: Root node -> Leaf nodes

 

* Root 노드는 모든 데이터를 고려 한다고 가정 한다.
* 하위노드(자식노드)로 내려 가면서 feature에 따라 데이터들이 분류 됨

 

(1) 노드에서 고려할 데이터가 이미 하나의 class 에만 속하였거나, 

더 이상 고려할 feature가 없으면 Leaf node로 여기고 자식노드 생성 안함
> 고려할 feature 가 더 이상 없어서 leaf node가 된 경우, 

가장 많은 수의 class 를 결과 값 으로 채택한다.

 

(2) 데이터들을 ‘가장 잘 나눠 주는‘ feature 선택
* 주의: Leaf node 에서 완벽하게 나눠 진다는 보장은 없음

*위에 있는 좋은트리에 조건에 맞춰 깊이와

label을 고려하여 feature을 선택한다.

 

(3) 선택된 feature 에 대한 조건 별로(값 마다) ‘자식 노드‘ 생성

 

(4) 각 ‘자식 노드‘에서는 해당 조건을 만족하는 데이터만 고려하여 (1)부터 반복

 

 

 

 

불순도 / 불확실성 

 

분류나무는 구분 뒤 각 영역의 순도(homogeneity)가 증가, 

불순도(impurity) 혹은 불확실성(uncertainty)이

최대한 감소하도록 하는 방향으로 학습을 진행한다.

순도가 증가/불확실성이 감소하는 걸 두고

정보이론에서는 정보획득(information gain)이라고 한다. 

 

 

 

Purity

>한쪽 데이터만 존재 할수록 more pure 하다!

 

 

출처 - https://www.python-course.eu/Decision_Trees.php

 

Entropy (Impurity)

 

>Purity 의 반대 개념
>“Entropy 가크다”== “더Chaotic 하다”

 

*Information theory 에 따르면,
“Entropy 가 크다“ == “더 정보가 많다“

 

엔트로피 수식.

 

p : class k의 확률을 의미
 (#data of class k) / (#total_data) 로써 계산

 

 

트리 생성 시, 각 노드 마다 어떤 feature 를 고려 할때
자식 노드들이 가지는 데이터가 pure 할수록 좋은 feature이다.

이것이 의미하는 것은

부모 노드의 purity 와 자식 노드들의 purity 를 비교 해서,

그 차이가 “클수록“ 더좋은feature이다!

 

Information Gain

Information theory 에서는

Entropy (impurity) ==‘정보의함량‘ 이라고 보고 있다.

 

부모노드 -> 자식노드 방향으로 데이터가 흐르므로,

부모 노드에서 정보의 함량이 더 큼
IG = 부모노드의entropy (impurity) –자식노드들의entropy (impurity)
값의범위: 0~1

 

IG가 클수록 더 좋은 feature 이다.

출처 - https://www.google.com/url?sa=i&source=images&cd=&ved=2ahUKEwiNvcrYwMXhAhXxwosBHYErAQMQjhx6BAgBEAM&url=http%3A%2F%2Fwww.grroups.com%2Fblog%2Fan-information-gain-based-feature-ranking-function-for-xgboost&psig=AOvVaw2DtTCM2dHwhTB3-hquHItf&ust=1554985003336259