CART 훈련 알고리즘

CART 훈련 알고리즘

참고: 핸즈온 머신러닝 (오렐리앙 제롱 저, 박해선 역)

scikit-learn은 decision tree를 훈련시키기 위해 CART (Classification And Regression Tree) 알고리즘을 사용한다. 이 알고리즘의 아이디어는 간단하다. 먼저 train set을 하나의 특성 $k$ 의 임곗값 $t_k$ 를 사용해 두 개의 서브셋으로 나눈다. 이 때 $k$ 와 $t_k$ 는 가장 순수한 서브셋으로 나눌 수 있는 ($k$, $t_k$) 로 찾는다. 이 알고리즘의 최소화해야 하는 비용 함수는 다음과 같다.

\[J(k, t_k) = \dfrac{m_{\text{left}}}{m}G_{\text{left}} + \dfrac{m_{\text{right}}}{m}G_{\text{right}}\]

• $G_{\text{left/right}}$: 왼쪽/오른쪽 서브셋의 불순도
• $m_{\text{left/right}}$: 왼쪽/오른쪽 서브셋의 샘플 수

train set이 성공적으로 나눠지면 같은 방식으로 서브셋을 나누는 과정을 반복한다. 이 과정은 최대 깊이가 되거나 불순도를 줄이는 분할을 찾을 수 없을 때 중지된다.

CART 알고리즘은 탐욕 알고리즘이다. 납득할만한 솔루션을 만들어내지만 최적의 솔루션을 보장하지는 않는다.