결정 트리

Decision Tree

• $x$ : data(observation)
• $y$ : label(class)

1. 데이터 집합을 가장 잘 나눌 수 있는 특징을 선택
   좋은 특징을 고르는 방법? - 데이터가 나눠진 후 불순도가 가장 낮은 특징을 선택(같은 클래스로 이루어진 데이터가 많이 모이는 특징)
2. 선택된 특징의 값을 기준으로 데이터 집합을 나눈다
   좋은 값을 판단하는 방법?

확률 변수의 불확실성을 측정하는 방법

1. 최대값
   : $p$ 가 균등 분포일 때 (완전 불확실)
   ex. $p(Y = y_1) = 0.5$, $p(Y = y_2) = 0.5$
   $H(Y) = -0.5 \log 0.5 - 0.5 \log 0.5 = 1$
2. 최소값
   : 0 (완전 확실)
   ex. $p(Y = y_1) = 1$, $p(Y = y_2) = 0$
   $H(Y) = -1 \log 1 - 0 \log 0 = 0$

• $Y$가 균등한 분포에서 나온 경우
• 히스토그램이 평평함
• 이로부터 샘플링된 값들은 예측하기 어려움

• $Y$가 다양한 분포 (피크와 계곡이 있는 분포)에서 나온 경우
• 히스토그램에 많은 낮음과 높음이 있음
• 이로부터 샘플링된 값들은 예측하기 쉬움

• 엔트로피를 줄이는
  특징
  을 선택하여 데이터를 분할

• $p(Y = T) = \frac{5}{6}$
• $p(Y = F) = \frac{1}{6}$
• $H(Y) = - \frac{5}{6} \log \frac{5}{6} - \frac{1}{6} \log \frac{1}{6} = 0.19$

• $X_1$이 T일 때, $p(Y = T) = \frac{4}{4}$, $p(Y = F) = \frac{0}{4}$
  • $p(Y = T|X_1 = T) = 1$, $p(Y = F|X_1 = T) = 0$
• $X_1$이 F일 때, $p(Y = T) = \frac{1}{2}$, $p(Y = F) = \frac{1}{2}$
  • $p(Y = T|X_1 = F) = 0.5$, $p(Y = F|X_1 = F) = 0.5$

• $X_2$이 T일 때, $p(Y = T) = \frac{3}{3}$, $p(Y = F) = \frac{0}{3}$
  • $p(Y = T|X_2 = T) = 1$, $p(Y = F|X_2 = T) = 0$
• $X_2$이 F일 때, $p(Y = T) = \frac{2}{3}$, $p(Y = F) = \frac{1}{3}$
  • $p(Y = T|X_2 = F) = \frac{2}{3}$, $p(Y = F|X_2 = F) = \frac{1}{3}$

$X_2$를 사용하여 데이터를 나누는 것이 더 좋은 결과를 가져옴(엔트로피를 줄임)

분할 후 엔트로피(불확실성)의 감소

• $IG(X_1) > 0 \rightarrow$ $X_1$은 분할에
  유용한
  특징

• $IG(X_2) > 0 \rightarrow$ $X_2$는 분할에
  더 유용한
  특징

1. 빈 결정 트리에서 시작
2. 노드를 만들고 정보 이득(IG)에 기반하여 좋은 특징을 선택
   • $\arg \max IG(X_i) = \arg \max (H(Y) - H(Y|X_i))$
3. 선택된 특징을 사용하여 데이터 집합을 분할
4. 분할된 데이터 집합에 대해 재귀적으로 반복
5. 모든 데이터가 같은 클래스에 속하거나 더 이상 특징이 없을 때까지 반복
   • only a single label

부트스트랩 집계(Bootstrap Aggregating)를 사용하여 많은 결정 트리를 학습시킴