[데이터 분석] Decision Tree(의사결정 나무) 알고리즘

Decision Tree 알고리즘 

 

참고글 : [R] Decision Tree(의사결정 나무) 알고리즘 - rpart

           [R 분석] Decision Tree 매개변수 튜닝

1. Decision Tree

(출처 : 위키백과)

Decision tree(의사결정나무)는 분류 모델 중 tree기반 모델의 기본이 되는 모델입니다.

 - 모델 학습 시 각 설명변수마다 feature importance(중요도)를 계산

   => 불순도 측정

   => 단순한 트리를 생성하기 위해 불순도가 가장 낮은(feature importance가 가장 높은) 설명변수를 상위 노드에 고정 

       (만약 비슷한 불순도를 갖는 설명변수가 있다면 더 많은 level(자식 노드)을 갖는 변수가 우선순위를 갖는 특징)

                                                                            -> Why? 자식 노드가 많을 수록 불순도가 낮아지므로

장점) 

  - 의사결정 나무 알고리즘은 간단하 쉬운 시각화로, 가독성이 높음 

  - X, Y의 인과관계와 설명변수와 종속변수 간 영향력 파악 가능

  - 시각화를 통해 어떠한 변수들이 중요할 것 같다는 정보를 획득하기에 용이 (전문가의 의견이 부족할 경우) 

  - 변수의 정규화나 표준화가 필요 없음

단점)

  - 알고리즘이 심플한 만큼 예측력이 떨어짐

  - 단일결정 트리이므로 과대적합이 발생하여 일반화 성능이 저하 (새로운 데이터 적용 시 낮은 예측력)

    * 이 단점을 보완하여 나온 알고리즘이 Random forest 알고리즘 (다수결에 의한 정보로 분석 -> 통계적 지식 없이도 예측력이 높은 모델)

2. Decision Tree의 불순도

  - 각 집단이 얼마나 혼합되어 있는지(혼잡한지)를 나타내는 지표

  - 판별력이 좋은 질문일 수록 분순도가 낮다고 표현, 반대로 불순도가 높다는 것은 좋은 판별이 아님

    즉, 상위 노드일수록 불순도가 높고, 하위 노드일수록 불순도가 낮음

  - 판별력이 좋은 질문이 상위에 위치할 수록 트리의 높이는 짧아짐. 그러므로 판단의 기준이 중요

  - Decision Tree 알고리즘은 각 변수의 불순도를 모두 계산한 후 불순도가 가장 낮은 질문을 상위부터 배치하므로

    시간 단축, 예측력 상승, 과대적합 해소에 유리

 * 과대적합(오버핏 현상) 

   - 모델이 복잡해지면서 모델을 만드는 데이터에 대해서는 예측력을 높일 수 있으나, 전혀 다른 새로운 데이터에 대해서는 굉장히 낮은 예측력을 보이는 현상

   - 모델이 복잡하게 생성되는 경우 자주 발생

   - 그러므로, Decision Tree 알고리즘을 적용한 모델의 최종 평가에서 과대적합이 발생하지 않는지 검증하는것이 중요

3. Decision Tree의 지니불순도

불순도를 측정하는 대표적인 불순도 함수

 F(p) = p(1-p) 

(출처 : R을 이용한 데이터 처리 & 분석 실무)

  - 데이터 셋의 6개의 데이터 중, 5개의 특정 분류로 구성되어있을 경우 = 5/6 * 1/6

  - 특정 분류로만 구성되어있을 경우(p=1), 특정 분류가 전혀 없을 경우(p=0) 일 때, 지니 불순도는 가장 작은 0을 갖음

  - 여러 분류가 섞여 있을 경우 큰 값을 갖게 되고, p=1/2일 때 최대(1/4) (높은 불순도)

 

4. Decision Tree의 과대적합 해결방안

1. 가지키기(cp)

  - 트리의 불필요한 리프노드를 잘라내는 방법

 

2. 재사용 가능한 설명변수의 개수 제한(max_depth)

  - max_dapth = 1 이면 질문을 재사용하지 않겠다는 의미 말라는 것

  - max_dapth 값이 높아질 수록 트리가 복잡해짐

3. 관측값의 최소갯수 제한(minbucket)

  - 오분류 된 데이터 수가 minbucket 으로 설정해 놓은 값보다 클 경우, 트리가 더 세분화되어 하위 트리로 분리될 수 있음

  - minbucket 의 크기가 작을수록 트리는 복잡해짐

  - 과대적합(오버핏 현상)이 계속 발생한다면 minbucket 값을 높혀주어야 함

5. 매개변수 튜닝을 위한 방법

 

 매개변수의 튜닝이 많이 필요하진 않지만 일반화 과정에서 필요한 경우가 있습니다.

1. cp

  - 가지치기 변수로, 0~1의 값을 갖음

  - $cptable을 통해 더 작은 size의 트리를 구성하기 위한 값을 확인

       cp    nsplit   size of tree(depth)         # nsplit : 노드의 분리 횟수  

       0.5     3           4                           # cp 값을 조정하면서 트리의 가지치기 가능 

      0.15     4           5

      0.01     5           6

2. max_depth

  - 트리를 작게 줄일 용도로 사용 

  - 재사용 가능한 설명변수의 개수를 의미

  - max_depth 값이 클수록 재사용 가능한 변수가 많아짐

    => 복잡한 트리의 생성 확률 증가 => 과대적합(overfit) 확률 증가

3. minbucket 또는 minsplit

  - 각 leaf Node마다 오분류 데이터의 수를 확인하여 더 split할지 여부를 결정하는 최소 분기 지점을 의미

      ex) minbucket = 5 인 경우, 오분류 데이터가 5이상이면 추가 split 수행

  - minbucket의 값이 작을수록 트리는 복잡해짐

참고: KIC 캠퍼스 머신러닝기반의 빅데이터분석 양성과정