决策树

机器学习

---

Decision Tree

Decision Tree is a basic classification and regression method. Contains 3 algorithms:

• ID3
• C4.5
• CART

---

Select Features

Define Entropy as

$$H(p) = H(X) = -\sum_{i=1}^n p_i \log{p_i},$$
where $X$ is a random variable with probability $p_i = P(X = x_i)$, with range $0 \le H(p) \le \log{n}$.The larger the uncertainly is, the larger entropy $H(X)$ will be.

Define Conditional Entropy as

$$H(Y \mid X) = \sum_{i=1}^n p_i H(Y \mid X = x_i),$$
where $X$ and $p$ are defined as above.

Define Information Gain is defined as:

$$G(D, A) = H(D) - H(D \mid A),$$
which measures how much uncertainty reduced by introducing $A$ for classification. We should keep those features reduce most uncertainty.

---

Generating Decision Tree

ID3

Input: Training data set $D$, feature set $A$, threshold $\epsilon$;
Output: Decision Tree $T$.

1. If all instances belong to same class $C_k$, return $T$ with label $C_k$;
2. If $A = \oslash$, return $T$ with label $C_k$ with most instances in $D$;
3. Calculates information gains for each $A_i$, and select $A_g$ with largest information gain;
   
   • If information gain of $A_g \lt \epsilon$, return $T$ with label $C_k$ with most instances in $D$;
   • Else, partition $D$ into $D_i$s with different $A_g = a_i$, construct sub-trees with $D_i$ and $A - {A_g}$.

This approach tends to over-fit.

C4.5

C4.5 is similar to ID3 but select features with information gain ratio

$$g_R(D, A) = \frac{g(D, A)}{H(D)}$$
instead of information gain.

---

Pruning Decision Tree

Cost function

Let $T$ denote a decision tree with $t$ leaves. Each leaf has $N_t$ samples, and $N_{tk}$ samples for class $k$. Define loss function as:

$$C_\alpha(T) = -\sum_{t=1}^{|T|} \sum_{k=1}^{K} N_{tk} \log{\frac{N_{tk}}{N_t}} + \alpha |T|.$$

Pruning algorithm

1. Calculate emperical entropy for every nodes;
2. If the cost become smaller, then prune it.

---

CART Algorithm

Classification And Regression Tree is a widely used approach for learning decision tree. It can be used for both classification and regression.

Generate regression tree

Input: Training set $D$
Output: Regression tree $f(x)$

1. Scan for the most appropriate splitting variable $j$ and splitting point $s$, solving
   

   $$\min_{j,s} \left[ \min_{c_1} \sum_{x_i \in R_1} (y_i - c_1)^2 + \min_{c_2} \sum_{x_i \in R_2} (y_i - c_2)^2 \right]$$
   where $R_1$ and $R_2$ are regions splitted by $j$ and $s$, $c_m = E(y_i \mid x_i \in R_m)$.

2. Back to step 1 for $R_1$ and $R_2$, until terminating condition satisfied.

3. Split input space into $M$ regions $R_1, R_2, \dots, R_M$, generate decision treeL
   

   $$f(x) = \sum_{m=1}^{M} \hat{c}_m I(x \in R_m)$$

Geni Index

Geni Index of probability distribution is defined as

$$\mathrm{Gini}(p) = \sum_{k=1}^{K} p_k(1 - p_k) = 1 - \sum_{k=1}^{K} p_k^2$$

For binomial distribution, the equivalent form of Gini index is $\mathrm{Gini}(p) = 2p(1-p)$.

The Gini index of sample set $D$ is

$$\mathrm{Gini}(D) = 1 - \sum_{k=1}^{K} \left( \frac{|C_k|}{|D|} \right)^2$$

Split $D$ into $D_1$ and $D_2$ by letting $D_m = \left\{ (x,y) \in D \mid A(x) = a \right\}$. Then under the constraint of feature $A$, Gini index is defined as

$$\mathrm{Gini}(D, A) = \frac{|D_1|}{|D|} \mathrm{Gini}(D_1) + \frac{|D_2|}{|D|} \mathrm{Gini}(D_2)$$

The higher Gini index is, the more unpredicatable of samples are.

Generate classification tree

Input: Training set $D$
Output: CART classification decision tree

1. Split $D$ with $A = a$ for every feature $A$ and every possible value $a$, calculates Gini index $\mathrm{Gini}(D, A)$.
2. Split $D$ with $A = a$ which produces smallest Gini index.
3. Call step 1 and step 2 for subset $D_1$ and $D_2$.

CART Pruning

TODO: Don't know how this algorithm come.

Input: Decision Tree generated by CART
Output: Optimized decision tree $T_a$

1. Set $k = 0$, $T = T_0$.
2. Set $\alpha = +\infty$.
3. Calculate $C(T_t)$, $|T_t|$,
   $$\begin{equation} g(t) = \frac{C(t) - C(T_t)}{|T_t| - 1} \end{equation}$$
   and
   $$\begin{equation} \alpha = \min(\alpha, g(t)) \end{equation}$$
   from top down, where $T_t$ is sub-tree with root $t$, $C(T_i)$ is error, $|T_t|$ is the number of leaves.
4. Visit $t$ from top down, if $g(t) = \alpha$, prune $T_t$.
5. Set $k = k+1$, $\alpha_k = \alpha$, and $T_k = T$.
6. If $T$ is not a single node tree, back to step 4.