[ML] CART 알고리즘

이전 포스팅에서는 의사결정 나무에서 엔트로피를 불순도로 사용하는 ID3와 C4.5 알고리즘을 정리해보았습니다.
이번 포스팅에서는 엔트로피 외에 다른 불순도 지표를 사용하는 CART 알고리즘에 대해 정리해보도록 하겠습니다.

CART (Classification And Regression Tree)

CART는 ID3 알고리즘과 비슷한 시기에, 별도로 개발된 알고리즘으로 Classification And Regression Tree의 약자입니다. 이름 그대로 Classification뿐 아니라 Regression도 가능하다는 것을 포함해서, ID3나 C4.5 알고리즘과 비교했을 때 몇 가지 차이점이 존재합니다.

1. 불순도: Gini index
2. Binary tree
3. Regression tree

위 세가지 항목에 대해 하나씩 살펴보도록 하겠습니다.

---

CART 알고리즘 특징 1: Gini index

Gini index는 엔트로피와 같은 불순도 (Impurity) 지표입니다. \(C\)개 사건의 집합 \(S\)에 대한 Gini index \(G(S)\)는 아래 수식으로 표현됩니다.

\begin{aligned}
G(S) &= \sum{i=1}^C p_i(1-p_i) \\\
&= \sum{i=1}^C pi - \sum{i=1}^C pi^2 \\\
&= 1 - \sum{i=1}^Cp_i^2 \\\
\end{aligned}

Binary 문제에서 Probability에 따른 Gini index와 Entropy 변화

Gini index는 Entropy처럼 분류가 잘 될 때 낮은 값을 갖습니다. 따라서 CART 알고리즘에서도 ID3, C4.5와 마찬가지로 모든 분기 경우의 수에 대해 분기 후의 Gini index를 계산해, 그 값이 가장 큰 경우를 기준으로 선택합니다.

ID3에서 Information Gain을 이용하는 것과 동일하기 때문에, 본 포스팅에서는 이 부분에 대한 예시는 생략합니다.

[ML] ID3 알고리즘

 

---

CART 알고리즘 특징 2: Binary tree

CART 알고리즘의 또 하나의 특징으로는 가지 분기 시, 여러 개의 자식 노드가 아닌 단 두 개의 노드로 분기한다는 것입니다. 이를 이진트리 (Binary tree) 구조라고 합니다.

ID3와 CART 분기의 비교

좌측은 ID3 알고리즘, 우측은 CART 알고리즘의 분기를 나타냅니다. ID3의 경우 모든 클래스 (e.g., Sunny, Overcast, Rain)로 가지가 뻗어져 나갑니다. 즉, ID3 알고리즘의 경우 Information Gain을 변수별로 한 번씩만 계산하면 됩니다.

반면, CART는 '하나의 클래스와 나머지'와 같이 가지가 생성됩니다. 따라서 아래 예시와 같이 모든 지표 X 모든 레벨 개수만큼 비교가 필요합니다.

---

CART 알고리즘 특징 3:Regression tree

Classification And Regression Tree라는 이름답게, CART 알고리즘은 Regression(회귀)를 지원합니다. 회귀라는 것은 결괏값을 성별, 등급과 같은 몇 개 구간이 아니라, 온도, 가격 등 다양한 연속형 값으로 추정하는 문제를 말합니다.

회귀 나무 (Regression Tree)의 방법은 간단합니다. 분기 지표를 선택할 때 불순도(e.g., Entropy, Gini index)를 사용하는 대신 실제값과 예측값의 오차를 사용합니다.

수식을 보기 전, 간단한 예시를 먼저 살펴봅시다. tomaszgolan's blog의 설명을 참고했습니다.

Regression Tree 예시 1

위의 그림은 x값을 통해 y값을 예측하기 위한 학습 데이터를 나타냅니다.

Regression Tree 예시 2

예를 들어 \(x <0.3\) 과 \(x<0.6\)을 노드로 갖는 의사결정 나무는 위와 같이 0.3, 0.6을 기준으로 입력받는 x값을 나누도록 학습합니다 (초록 점선)

Regression Tree 학습

이렇게 학습된 Regression tree는 각 구간에 해당하는 값이 입력값으로 들어올 경우, 해당 구간 학습 데이터의 결괏값 (y축)의 평균값 (빨간 실선)을 예측값 \( f(x_i) \)으로 내놓습니다. 예를 들면 \( x=0.5 \)을 입력으로 받으면 [0.3, 0.6] 구간의 평균인 약 0.25를 결과로 반환하는 식입니다.

의사결정나무의 학습과정에서는, 다양한 분기조건으로 반환값을 얻어낸 뒤, 실제값과의 잔차제곱합 (Residual Sum of Square, RSS) 또는 평균제곱오차 (Mean Squared Error, MSE)를 계산합니다.

\[ RSS = \sum_{i=1}^N(y_i - f(x_i)})^2 \]

\[ MSE = \frac{1}{N}\sum_{i=1}^N(y_i-f(x_i)}^2 \]

지금은 3개 구간으로 나누어서 Regression으로 보기는 어렵지만, 데이터를 나누는 초록 점선이 촘촘하게 생길 수록 (의사결정 나무의 깊이가 깊어질 수록) 예측값과 실제값의 오차는 줄어들 것입니다.

\[
J(k, t_k)=\frac{m_{left}}{m}MSE_{left}+\frac{m_{right}}{m}MSE_{right}
\]

따라서 위 수식과 같이 Binary tree의 좌우 노드에 각각에 대한 오차값 \( MSE{left}, MSE{right} \)을 계산하고, 좌우 노드에 해당하는 샘플 수의 비율 \( \frac{m{left}}{m}, \frac{m{right}}{m}( \)을 가중치로 곱해 전체 오차값 \( J(k, t_k) \)을 계산하여 지표간 비교를 통해 가장 적은 오차를 갖는 최적의 분기 조건을 결정합니다.

---

간단하면서도 효과적인 아이디어의 의사결정나무지만, 이 모형은 치명적인 단점이 있습니다.
다음 포스팅에서는 이러한 단점을 정리하고, 의사결정나무의 문제점을 보완한 배깅 (Bagging), 부스팅 (Boosting), 스태킹 (Stacking) 등 다양한 앙상블 모형을 정리해고자 합니다.