Classification Tree

Definition

Suppose $Y\in \{1,2,\dots ,K\}$, and $R_1(j,s)=\{\mathbf{x}|x_j\le s\},R_2(j,s)=\{\mathbf{x}|x_j>s\}$ Define a variable ${\hat{p}}_{mk}$ representing the proportion of class $k$ observations in a node $m$ ${\hat{p}}_{mk}=\frac{1}{n_m}\sum _{i:{\mathbf{x}}_i\in R_m}I(Y_i=k),k=1,2,\dots ,K$ We classify the observations in a node $m$ to class $k(m)=\underset{1\le k\le K}{\mathrm{argmax}}{\hat{p}}_{mk}$ Suppose the number of terminal nodes in a tree $T$ is $|T|$ and $R_{ii=1,\dots ,|T|}$ is the split regions corresponding to the terminal node. For a tree $T$, define the cost complexity function. $C_{\alpha }(T)=\sum _{m=1}^{|T|}{n}_m{Q}_m(T)+\alpha |T|$ where $Q_m(T)$ is an impunity function, $\alpha$ is a tuning parameter regularizing complexity.

The tree minimizes $C_{\alpha }$ is the selected as optimal.

Impunity Functions

• Misclassification error: $\frac{1}{n_m}\sum _{i:{\mathbf{x}}_i\in R_m}I(Y_i\ne k(m))=1-{\hat{p}}_{mk}$
• Gini index: $\sum _{k=1}^K{\hat{p}}_{mk}(1-{\hat{p}}_{mk})$
• Cross entropy on deviance: $-\sum _{k=1}^K{\hat{p}}_{m}k\ln ({\hat{p}}_{m}k)$