결정 나무 (Decision Tree)

의사 결정 나무(Decision Tree)는 분류, 회귀 문제에 널리 사용하는 모델입니다.
의사 결정 나무를 이용한 분류법은 다음과 같습니다.
1. 여러가지 독립변수 중 하나의 독립변수를 선택합니다.
2. 그 독립변수에 대한 기준값(threshold) - 분류 규칙 - 을 정합니다.
3. 전체 학습 데이터 집합을 분류 규칙에 따라, 기준값보다 큰 데이터 그룹(노드 1)과 기준값보다 작은 데이터 그룹(노드 2)로 나눕니다.
4. 각 노드에 대해서 1~3 단계를 반복하여 한 가지 클래스만 존재할 때까지 혹은 사전에 지정한 일정 기준까지 하위 노드를 만듭니다.

의사 결정 나무 모형에 데이터를 입력하면, 데이터는 분류 규칙(기준값)에 따라 특정 노드를 선택해서 내려가게 됩니다.
이때 노드에 속한 데이터의 클래스의 비율을 구하여, 노드의 조건부 확률 분포 $P(Y = k \mid X)_{\text{node}}$ 라고 정의합니다.

$$P(Y=k \mid X){\text{node}} \approx \dfrac{N{\text{node}, k}}{N_{\text{node}}}$$

분류 규칙은 부모 노드, 자식 노드 간 엔트로피를 가장 낮게 만드는 독립변수와 기준값을 찾는 식으로 이루어집니다.
다시 말해 정보 획득량(information gain)이 가장 높은 독립변수와 기준값은 찾는 셈인데요. 정보 획득량은 변수 X가 확률변수 Y의 엔트로피를 얼마나 줄였는지 나타내는 값입니다.

$$IG[Y, X] = H[Y] - H[Y \mid X]$$

엔트로피
- 엔트로피는 확률분포가 가질 수 있는 확신의 정도를 수치로 표현한 것입니다.
- 예를 들어, 확률변수에 여러가지 값이 나올 확률이 비슷하면 엔트로피가 높아지고, 특정값이 나올 확률이 높아지고 나머지값이 나올 확률이 낮아진다면 엔트로피는 낮아집니다.
- 수학적으로는 이산확률변수이면,
  $$H[Y] = -\sum_{k=1}^K P(y_k) \log_2 P(y_k)$$
- 연속확률변수이면,
  $$H[Y] = -\int_{-\infty}^{\infty} p(y) \log_2 p(y) \; dy$$
엔트로피와 정보량
- 엔트로피는 확률변수가 담을 수 있는 정보량을 의미하기도 합니다.
- 엔트로피가 0이라면, 확률변수는 결정론적(항상 예측할 수 있는 값이 나온다) 이기 때문에, 추가 정보량은 없습니다.
- 반면 엔트로피가 크다면, 확률변수는 다양한 결과값을 내놓을 수 있기 때문에 추가로 획득할 수 있는 정보량이 상대적으로 많습니다.
크로스엔트로피
- 크로스엔트로피는 확률분포의 차이를 정량화한 값이지만 기준 분포가 $p$로 고정되어 있습니다. $$H[p, q] \neg H[q, p]$$
- 크로스엔트로피는 분류 모형의 성능을 측정할 때도 사용합니다.

$$G[Y] = \Sigma_{k=1}^K P(y_k)(1 - P(y_k))$$