결정 트리

결정 트리 학습과 시각화

루트 노드^{root node} : 깊이가 0인 맨 꼭대기의 노드
리프 노드^{leaf node} : 자식 노드를 가지지 않는 노드

---

CART^{classification and regression tree} 훈련 알고리즘

먼저 크기에 따른 가중치가 적용된 가장 순수한 서브셋으로 나눌 수 있는 ($k$,$t_ {k}$) 짝을 찾는다.
훈련 세트를 하나의 특성 $k$의 임곗값 $t_ {k}$를 사용해 두 개의 서브셋으로 나눈다.
CART 알고리즘이 훈련 세트를 성공적으로 둘로 나누었다면 같은 방식으로 서브셋을 또 나누고 그다음엔 서브셋의 서브셋을 나누고 이런 식으로 계속 반복
이 과정은 최대 깊이가 되면 중지하거나 불순도를 줄이는 분할을 찾을 수 없을 때 멈추게 된다.

분류에 대한 CART 비용 함수

$
\begin{split}
&J(k, t_k) = \dfrac{m_{\text{left}}}{m}G_\text{left} + \dfrac{m_{\text{right}}}{m}G_{\text{right}}\\
&\text{여기서 }\begin{cases}
G_\text{left/right} \text{는 왼쪽/오른쪽 서브셋의 불순도}\\
m_\text{left/right} \text{는 왼쪽/오른쪽 서브셋의 샘플 수}
\end{cases}
\end{split}
$

---

지니 불순도^impurity 또는 엔트로피?

지니 불순도가 조금 더 계산이 빠르기 때문에 기본값으로 좋다.
다른 트리가 만들어지는 경우 지니 불순도가 가장 빈도 높은 클래스를 한쪽 가지^branch로 고립시키는 경향이 있는 반면 엔트로피는 조금 더 균형 잡힌 트리를 만든다.

지니 불순도

$G_ i = 1 - \sum\limits_ {k=1}^{n}{{p_ {i,k}}^2}$
$p_ {i,k}$는 $i$번째 노드에 있는 훈련 샘플 중 클래스 $k$에 속한 샘플의 비율

엔트로피

$H_ i = -\sum\limits_ {k=1 \atop p_ {i,k} \ne 0}^{n}{{p_ {i,k}}\log_2(p_ {i,k})}$

---

규제

비파라미터 모델^{nonparametric model} : 훈련되기 전에 파라미터 수가 결정되지 않는다. (과대적합 > 과소적합) (e.g. 결정 트리)
파라미터 모델^{parametric model} : 미리 정의된 모델 파라미터 수를 가진다. (과대적합 < 과소적합) (e.g. 선형 모델)
결정 트리 규제

• 결정 트리의 최대 깊이
• 분할되기 위해 노드가 가져야 하는 최소 샘플 수
• 리프 노드가 가지고 있어야 할 최소 샘플 수
• 위와 같지만 가중치가 부여된 전체 샘플 수에서의 비율
• 리프 노드의 최대 수
• 각 노드에서 분할에 사용할 특성의 최대 수

---

회귀

분류 트리와 주요한 차이는 각 노드에서 클래스를 예측하는 대신 어떤 값을 예측

회귀를 위한 CART 비용 함수

$
\begin{split}
&J(k, t_k) = \dfrac{m_{\text{left}}}{m}\text{MSE}_ \text{left} + \dfrac{m_{\text{right}}}{m}\text{MSE}_ {\text{right}}\\
&\text{여기서 }\begin{cases}
\text{MSE}_ \text{node} = \sum_{i\in \text{node}}(\hat{y}_ {\text{node}}-y^{(i)})^{2}\\
\hat{y}_ {\text{node}}=\frac{1}{m_ {\text{node}}}\sum_{i\in \text{node}}y^{(i)}
\end{cases}
\end{split}
$

---

불안정성

훈련 세트의 회전에 민감 (해결 방법 : 훈련 데이터를 더 좋은 방향으로 회전시키는 PCA 기법을 사용)
훈련 데이터에 있는 작은 변화에도 매우 민감

---

실습코드링크 : decision tree