[ML] Decision Tree (상시 업데이트)

Decision Tree

의사결정나무를 잘 설명한 글 : 의사결정나무(Decision Tree) by ratsgo's blog

지도학습 알고리즘 중 하나다. 일반적으로 분류 문제에 사용되지만 회귀 문제에도 사용될 수 있다. 분류 문제에 사용될 때 classification tree라고 하고 회귀 문제에 사용될 때 regression tree라고 한다.

트리 형태로 모델이 진행되는 과정을 시각화할 수 있기 때문에 결과를 해석하기 쉽다는 장점이 있다. 단점은 Decision tree를 하나면 사용했을 때 성능이 그렇게 높지 않다는 것이다. 이를 보완하기 위해 보통 여러 개의 트리를 함께 사용한다. 이를 앙상블이라고 한다. 

How It Works 

어떤 기준을 만족하는 독립변수와 해당 독립변수 값에 따라 데이터 포인트들을 서로 다른 그룹으로 나누어 그룹별로 종속변수의 값을 예측한다. 즉, 같은 그룹에 속하는 데이터 포인트들의 종속변수(y)들은 모두 동일하다고 예측한다. 종속변수가 연속형 변수라면 평균값을 대푯값으로 삼고, 범주형 변수라면 최빈값(mode)을 대푯값으로 삼는다. 이때 몇 개 그룹으로 나눌지(depth)는 연구자가 정해야 할 하이퍼 파라미터다. 

독립변수 X1, X2가 있고 네 개 그룹으로 나눈 예

그렇다면, 어떤 기준으로 데이터를 두 그룹으로 나눌 지는 어떻게 정할까? 즉, 각 decision node에서 어떤 변수의 어떤 값(cutoff value)으로 데이터를 split할까? 이는 split 됐을 때 발생하는 에러를 최소화 하는 방식을 따른다. 결국 에러를 계산해야 하는데 그 계산 방법은 회귀 문제와 분류 문제에서 다르다.

회귀 문제에서는 RSS(Residual Sum of Squares) 값을 에러로 본다. 만약 데이터를 두 개 그룹으로 나눴다면, 각 그룹의 RSS를 구해서 이를 더한 값이 에러가 된다. 이 값을 최소화하는 변수와 해당 변수의 값 (cutoff value)를 선택해야 한다. 

분류 문제에서는 극 그룹의 에러 정도를 측정하기 위해 Gini index, Entorypy 등 두 가지 값을 사용할 수 있다.

Ensemble

여러 개의 weak한 learner(모델)를 합쳐서 하나의 강력한 learner(모델)을 만드는 방법이다. 앙상블에 많이 사용되는 weak learner가 decision tree다. 데이터의 양이 충분하지 않을 때 Ensemble 기반 방법이 딥러닝 기반 방법보다 성능이 좋기 때문에 앙상블을 잘 알고 있어야 한다. 

앙상블을 하는 방법에는 두 가지가 있다. Bagging과 Boosting이다.

(1) Bagging

- 학습 데이터에서 랜덤한 서브 샘플링을 여러번해서, 각 서브 샘플에 대해 의사결정나무를 적용해 예측값을 계산한 후, 그 결과를 종합한다. 회귀 문제일 때는 여러 예측값의 평균값을 최종 예측값으로 선택하고, 범주형인 경우 최빈값을 최종 예측값을 선택한다.  

그렇다면 서브 샘플을 어떻게 뽑을까? 이때 사용하는 방법을 Bootstrapping이라고 한다. Bootstrapping은 replacement를 허용하면서 서브 샘플링한다.

Bagging에는 과적합 문제가 발생하는 한계가 있다. 여러 개의 트리를 사용할 지라도 매번 decision node가 사용하는 feature들이 비슷하기 때문이다.

이 문제를 개선하기 위해 각 decision node에서 데이터를 split하는데 모든 feature를 사용하는 게 아니라 일부만 임의로 선택해 사용한다. 보통 학습 데이터에 사용되는 feature가 p개라고 할 때 √p(루트 p)개의 feature를 사용한다. 이를 Random forest 방법이라고 한다. 

(2) Boosting

• 이전 learner가 부족한 부분을 이후 learner가 추가적으로 설명해 전체적인 예측력을 높이는 방법이다. 
• Gradient Boosting
• 원리: 
• XGBoosting (Extreme gradient boosting) : 2014년 Tianqi Chen이 새롭게 제안한 방법이다. 속도와 성능을 개선했다. 

위와 같은 총 6가지를 개선했는데, 이들 중 비용함수에 패널티를 주는 방법(Regularization for avoiding overfitting)이 가장 중요하다. 

• Light GBM ( 더 최근에 나온 방법 ) : 크게 두 가지를 개선했다. 
• Leaf-wise split
• Gradient-based One-Side Smpling(GOSS) 
• Adaptive boosting (AdaBoosting) 

예전에는 random forest가 주목받았는데, 최근에는 XGBoosting과 LightGBM이 각광받고 있다.