Decision Tree

Decision Tree

Rule Based classifier
: 일련의 질문에 대한 답에 근거하여 데이터를 분류하는 모델
-classification, regression 모두 가능한 지도학습 모델

• attribute (질문, 속성) : 하나의 질문 (분기)마다 변수 영역을 두 개로 구분

구성

• node : 질문 or 정답
  • intermediate node
  • leaf node (terminal node) : 더 이상으 자손이 없는 노드
  • depth : 몇 개의 분기가 존재?

Decision Tree는 overfitting의 문제점을 가지고 있음.
$\rightarrow$ Pruning을 통해 해결
1) 사전 가지치기 : 나무가 완성되기 전에,특정 조건을 만족하면 알고리즘 중단
2) 사후 가지치기 : 나무가 완성된 후,하단 노드부터 유의하지 않은 바로 위 나무의 node로 변환

사후 가지치기

$<$비용-복잡도 가지치기$>$
CC(T)=Err(T)+$\alpha$$*$L(T)
위의 함수를 최소화하는 방향으로 가지치기를 수행

좋은 Decision Tree란?

하나의 데이터를 통해 만들 수 있는 Decision Tree의 종류는 무한하다. 이 중, 각각의 attribute에 의해 분할된 영역에 class가 같은 데이터가 최대한 많이 존재할 수록 좋은 Tree라고 할 수 있다.

• Impurity (불순도) : 각 범주에 서로 다른 데이터가 얼마나 섞여 있는가? (=최대한 동일한 class끼리 구성되어 있어야 함)
  $\rightarrow$ impurity를 최소화 하는 방향으로 학습이 진행된다.

알고리즘 진행 과정

1) emtpy decision tree에서 시작
2) 다음 순서의 best attribute를 기준으로 split (이 순서에서 impurity지표 사용)
3) recurse
 2)와 3)의 과정을 반복한다