decision tree의 가지치기(pruning)

위와 같이 decision tree는 recursive partitioning을 통해 각 node에서 information gain이 순간 순간 최대가 되는 방향으로 feature를 선택하고 최종 node의 entropy가 0이 될 때까지 구분을 진행합니다.

 

그런데 딥러닝을 많이 하신 혹시나 이 글을 읽고 계신 분은 짐작하셨겠지만 주어진 training data에 너무나 fitting된다는 단점이 있습니다.

 

그러니까 새로운 data가 들어올 때 사실 정확한 분류를 해줄지는 미지수라는 점입니다.

 

그래서 pruning이라는 방법을 수행하여 일반화 능력(generalization performance)을 올려줍니다.

 

일반화 능력은 딥러닝에서 모델이 train중 한 번도 보지 못한 test data에 대해서도 잘 예측할 수 있는 능력으로 정의합니다.

 

pruning하는 방법은 여러 가지가 있는데 기본 원리는 추상적으로 말하자면

 

전체 tree를 구성하고 나서 검증용 데이터를 넣어보면서 오분류율이 증가하는 지점을 찾아 가지를 쳐서 없애는 방식입니다.

 

없앤다고 하지만 아래의 가지들을 모두 합쳐서 상위 노드로 만들어준다고 생각해야한다고 합니다.

 

방법들을 예를 들어 나열하자면

 

1) 각 분기점에서 entropy 변화가 통계적으로 정말 유의한지 chi square test를 이용한 방법

 

2) 특별한 cost function을 정의하는 방법

 

3) error reduced pruning으로 잘라보고 나서 오분류율과 자르기 전 오분류율을 비교하여 자르고 나서 좋으면 자르는 방법

 

4) 그 외에 rule post pruning 등등 여러 가지가 있다고 합니다.

 

그림1. pruning에 대한 직관적인 그림 예시

 

참고

 

[머신러닝] 의사결정트리 (Decision Trees) (tistory.com)

[머신러닝] 의사결정트리 (Decision Trees)