Decision Tree

2021-1학기, 대학에서 ‘통계적 데이터마이닝’ 수업을 듣고 공부한 바를 정리한 글입니다. 지적은 언제나 환영입니다 :)

💥 이번 포스트는 <Decision Tree>를 수학적으로 정의하는 내용을 다룹니다. DT에 대한 정의와 개념은 다른 포스트를 참고해주세요 😉

DT Estimation

DT를 이루는 각 terminal node 또는 leaf node는 DT가 분할하는 region $R_i$에 대응된다.

DT는 regression과 classification 두 문제에서도 모두 적용해볼 수 있는데, 각 경우에 대한 DT estimation function $f$는 아래와 같이 정의된다.

1. DT estimation in regression problem

\[\hat{f}(x) = \sum^M_{m=1} \hat{c}_m \cdot I(x\in R_m)\]

where

\[\hat{c}_m = \frac{1}{n_m} \sum_{x_i \in R_m} y_i\]

$n_m$ is the # of training data in $R_m$.

그냥 terminal node에 속하는 training data의 평균으로 estimation 한다고 생각하면 된다.

2. DT estimation in classification problem

\[\hat{P}(Y=k \mid X=x) = \hat{p}_{mk} = \frac{1}{n_m} \sum_{x_i \in R_m} I(y_i = k) \quad \text{for} \quad x \in R_m\]

Then, for given $X = x$, estiation $\hat{Y}$ is

\[\hat{Y} = \underset{k}{\text{argmax}} \; \hat{P}(Y=k \mid X=x)\]

그냥 다수결에 의해 estimation 한다고 생각하면 된다.

---

DT의 장점은 좋은 interpretation power를 제공한다는 것이다! 때로는 결정에 대한 이유를 설명해야 하는 경우가 있는데, DT는 이런 상황에서 좋은 interpretation insight를 제공한다.

ex: a bank must explain reasons for rejection to a loan applicant.

---

DT Construction

DT는 아래 4가지 과정을 통해 만들어진다.

1. Growing

• Find an optimal splitting rule for each node and grow the tree.
• Stop growing if stopping rule is satisfied.

2. Prunning

• Remove nodes which increase prediction error or which have inappropriate inference rules.
  (Complexity 감소! 😆)

※ # of terminal nodes는 DT model의 complexity에 영향을 준다.

3. Validation

• Validate to decide how much we prune the tree. (Overfitting과 관련)

4. Interpretation & Prediction

• Interpret the constructed tree & Predict!

---

Splitting Rule

DT를 만드는 각 과정에서, 아래 두 가지를 결정해줘야 한다.

1. splitting variable $X_j$
2. splitting criterion

이때, $X_j$가 continuous인지 categorical인지에 따라 criterion을 만드는 상황이 달라진다.

Splitting Rule: Regression

Assume that all input variables are continuous and

\[R_1 (j, s) = \left\{ X : X_j \le s \right\} \quad \text{and} \quad R_2(j, s) = \left\{ X : X_j > s \right\}\]

splitting crieterion을 얻기 위해 splitting variable $X_j$와 split point $s$를 결정하는 문제는 아래의 식을 푸는 것과 동치다.

\[\min_{j, s} \left[ \min_{c_1} \left( \sum_{x_i \in R_1(j, s)} (y_i - c_1)^2\right) + \min_{c_2} \left( \sum_{x_i \in R_2 (j, s)} (y_i - c_2)^2 \right) \right]\]

이때, $c_1$과 $c_2$는 $R_1(j, s)$와 $R_2(j, 2)$에 속하는 data에 대한 평균값이다.

위의 식을 잘 살펴보면, 결국 “training error”를 최소화하는 $X_j$와 $s$를 찾는 문제임을 볼 수 있다!

Splitting Rule: Classification

Classification도 마찬가지로 “training error”를 최소화하는 아래의 식을 풀어 splitting criterion을 구할 수 있다.

\[\min_{j, s} \left[ \min_{k_1} \left( \sum_{x_i \in R_1(j, s)} I(y_i \ne k_1) \right) + \min_{k_2} \left( \sum_{x_i \in R_2(j, s)} I(y_i \ne k_2) \right) \right]\]

마찬가지로 이때, $k_1$과 $k_2$는 $R_1(j, s)$, $R_2(j, s)$에 속하는 data에서 다수결에 의해 구한 label이다.

Classification DT에서는 Splitting이 좋은지 안 좋은지 <Impurity>를 통해 측정해볼 수 있다. 그래서 위의 경우는 zero-one loss를 통해 criterion을 결정했는데, 이 방식은 곧 <misclassification error>라는 impurtiy measure를 사용한 것과 같다. 다른 impurity measure를 주어 동일한 training data라도 다른 DT를 얻을 수 있다!

---

Impurity Measures

1. Misclassification Error

\[\frac{1}{n_m} \sum_{i \in R_m} I(y_i \ne k_m) = 1 - \hat{p}_{mk_m}\]

2. Gini Index

\[\sum^K_{k = 1} \hat{p}_{mk} (1 - \hat{p}_{mk})\]

3. Cross-Entropy or Deviance

\[- \sum^K_{k=1} \hat{p}_{mk} \log \hat{p}_{mk}\]

---

Pruning

DT는 splitting의 계속한다면, tratining error는 0으로 수렴한다. 그러나 이것은 overfitting을 야기하고, model의 generalization을 떨어뜨린다. 그래서 node이 갯수를 줄이는 pruning 과정이 필요하다.

Let $T_0$ be a large tree obtatined by splitting.

A subtree $T \subset T_0$ is any tree that can be obtained by pruning.

let $n_m = \left| \{ i : x_i \in R_m \} \right|$ and \(\displaystyle\hat{c}_m = \frac{1}{n_m} \sum_{x_i \in R_m} y_i\).

1. In a regression,

\[Q_m (T) = \frac{1}{n_m} \sum_{x_i \in R_m} (y_i - \hat{c}_m)^2\]

2. In a classication (ver. Gini Index)

\[Q_m(T) = \sum^K_{k=1} \hat{p}_{mk} (1-\hat{p}_{mk})\]

Then, cost complexity pruning is defined by

\[C_{\alpha}(T) = \left(\sum^{|T|}_{m=1} n_m Q_m(T)\right) + \alpha |T|\]

where $\alpha > 0$ is a tuning parameter.

$C_\alpha(T)$에 대한 식을 잘 살펴보면, “training err”와 “complexity panelty”에 대한 텀이 있음을 확인할 수 있다.

이제, 위의 $C_\alpha(T)$를 기준으로 Best Pruning Subtree $T_\alpha$를 결정할 수 있다.

\[T_\alpha = \underset{T}{\text{argmin}} \; C_{\alpha} (T) \quad \text{where} \quad T \subset T_0\]

위와 같은 접근법을 <weakest link pruning>라고도 한다.

tuning parameter $\alpha$는 generalization error를 최소화하는 것을 골라서 사용하면 된다고 한다. (Cross Validation을 활용하는 것 같다.)

---

Sensitivity & Specificity

Medical Classification Problem을 다루는 상황에서 $Y=1$이 disease state라고 가정하자. 이때, <sensitivity>와 <specificity>는 아래와 같이 정의된다.

Definition. Sensitivity

“Probability of predicting disease given true disease.”

True Positive Rate를 의미한다. 또는 <Recall>이라고 한다.

\[P(\hat{Y} = 1 \mid Y = 1)\]

Definition. Specificity

“Probability of predicting non-disease given true non-disease.”

True Negative Rate를 의미한다.

\[P(\hat{Y} = 0 \mid Y = 0)\]

ROC curve

앞에서 살펴본 DT는 다수결(majority vote)에 의해 prediction을 결정했다. 그러나 다수결 방식 외에도 어떤 threshold 값을 정해, spam/normal을 분류해볼 수도 있다.

\[\hat{Y} = I\left( \hat{P}(Y=1 \mid X=x) > c \right)\]

for some $c > 0.5$.

이때, 우리는 classiciation rule $c$의 값을 바꿔가며, “sensitivity-specificity”를 측정할 수 있는데, 이것을 pair로 삼아 plot으로 그린 것이 바로 <ROC curve; Receiver Operating Characteristic curve>다.

ps) ROC curve는 classification problem에서만 유도할 수 있다!

이때, ROC curve의 <AUC; Area Under the Curve>를 통해 모델의 성능을 비교 평가할 수도 있다.

---

DT: 장점 & 단점

Advantages.

• Robust to input outliers
• Non-parameteric model

Disadvantages.

• Poor prediction accuracy with continuous output compared to linear regression model.
• When depth is too large, not only accuracy but interpretation are bad 😥
• Heavy computation cost
• Unstable
• Absence of linearity
• Absence of Main effects: all nodes are high order interactions.
• Discontinuity

---

이어지는 챕터에서는 통계적 모델의 꽃🌹이라고 할 수 있는 <Boosting>에 대해 다룬다. 내용이 쉽진 않지만, 현대 통계의 핵심이기 때문에 잘 익혀둬야 하는 테크닉이다.