A regression tree models the response as a piecewise-constant function over a partition of the input space into M regions, so that the parameters to be estimated are the regions R_m themselves and the constant response c_m assigned to each; given a region, the squared-error-minimizing constant is simply the mean of the training responses falling in it, and because the regions do not interact the minimization decomposes region by region. Finding the optimal set of regions is NP-complete, so recursive binary partitioning proceeds greedily: for each splitting variable j the candidate split points s are exhaustively searched — and only the values actually occurring in the training data need be considered, giving O(np) work per level — the (j*, s*) pair minimizing the summed squared error of the two child regions is chosen, and the procedure recurses independently within each child. The number of regions M is not fixed in advance but discovered from the data, which makes the model non-parametric; without a stopping rule or regularizer the recursion continues to one point per region, and fitting a local linear or other model per region instead of a constant yields the variant known as model trees.
A regression tree models the response as a piecewise-constant function over a partition of the input space into M regions, so that the parameters to be estimated are the regions R_m themselves and th…