Regression Tree

Definition

Decision tree algorithm consists of growing and pruning step. Suppose $R_1(j,s)=\{\mathbf{x}|x_j\le s\},R_2(j,s)=\{\mathbf{x}|x_j>s\}$

1. growing: seek the splitting variable $j$ and split point $s$ that solves ${\min }_{j,s}\left[{\min }_{c_1}\sum _{i:{\mathbf{x}}_i\in R_1(j,s)}(y_i-c_1{)}^2+{\min }_{c_1}\sum _{i:{\mathbf{x}}_i\in R_2(j,s)}(y_i-c_2{)}^2\right]$
2. pruning: 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 _{j=1}^{|T|}\sum _{i:{\mathbf{x}}_i\in R_2}(Y_i-{\bar{Y}}_j{)}^2+\alpha |T|$ where $\alpha$ is a tuning parameter regularizing complexity.

Regression function is estimated by $\hat{f}(x)=\sum _{m=1}^M{\hat{C}}_{m}I(x\in R_m)$ A non-parametric regression that partitions explanatory variables into a set of rectangles and takes the average of the response variables in each rectangle as an estimate of the regression function in that region.