Tree-Based Model

Tree-Based Model은 Linear/Logistic Regression과 더불어 실제 실무에서 가장 많이 활용되고 있는 알고리즘 중에 하나입니다. Tree-Based Model의 장점은 Linear/Logistic Regression처럼 해석이 용이하며, Bagging/Boosting 방법을 통해서 성능 또한 좋기 때문입니다.

Tree-Based Model은 Feature space를 나누어 구분합니다. 예를 들어 키 170cm 이상, 170cm 미만으로 나누는 것과 유사합니다. 

정말 간단한 Tree-Base Model을 수식으로 표현하면 아래와 같습니다.

$X_1$, $X_2$ 두개의 feature가 있다고 가정하면, $X_1$, $X_2$의 조건에 따라 Identiy function $I$가 0인지 1인지가 결정되고 각 조건에 따라 값(상수 $c_m$)을 결정하는 것입니다.

[Regression Tree]

먼저 Regression Tree에 대해서 정리해보도록 하겠습니다. 간단한 사상을 정리하면, 위에서 정리한 기본적인 Tree-based model과 같이 구역을 잘 나누고 해당 구역에서의 평균값을 예측값으로 활용하는 것입니다.

이 때, $R$은 나뉜 구역이며, 이 구역을 나누는 기준은 아래와 같습니다.

즉 각 구역에서의 예측값이 실제값과의 오차가 제일 적은 기준으로 구역을 나눈다는 것이고, Analytic한 방법으로 Solution을 찾기 보다는 Greedy Search와 비슷한 방법으로 Best pair(j,s)를 찾게 됩니다.

이를 일반화한 Criterion으로 나타내면 아래와 같습니다.

[Classification Tree]

Classification문제에 Tree-based model이 적용될 때 또한 Regression Tree와 거의 유사합니다. 다만, 구역을 나누는 기준이 상이합니다. Regression Tree와 다르게 한 구역에 여러가지 Class가 섞이는 것이 최소화되도록 구역을 구분하게 됩니다.  이러한 개념을 일반적으로 불순도(impurity)라고 정의하며 불순도를 최소화하도록 Tree를 구성하게 됩니다.

먼저 node m에서 class k가 발견되는 비율을 아래와 같이 정의하겠습니다.

다음으로 각 node m에서 가장 많이 발견되는 Class를 정의하겠습니다.

대표적인 불순도 지표 3가지는 아래와 같습니다.

The Elements of Statistical Learning

Misclassification error같은 경우는, Regression Tree와 같이 Greed Search 알고리즘을 많이 적용됩니다. 다만 Gini index나 Cross-entropy 같은 경우는 미분이 가능하기 때문에 다른 수치적 최적화 알고리즘을 적용할 수 있게 됩니다.

기본적인 Tree-based model의 개념에 대해서 정리해보았는데, Tree-based model은 만약 Node수가 많아 지게 되면 Overfitting 문제를 피하기 어렵고 결측값이 있을 경우 성능이 떨어지는 이슈가 있습니다.