In more detail, creating the tree involves selecting some variable X and finding the point in which to split data based on which point causes the greatest reduction in residual sum squares. 

This process is repeated with each new region created until a criterion is reached (ex. no region has more than 10 observations)

Creating the tree: Recursive Binary Splitting

Roughly speaking, there are two steps.
1. We divide the predictor space—that is, the set of possible values for X1, X2, . . . , Xp—into J distinct and non-overlapping regions, R1,R2,...,RJ.
2. For every observation that falls into the region Rj , we make the same prediction, which is simply the mean of the response values for the training observations in Rj.

University of Michigan - Ann Arbor

Decision trees can be applied to both regression and classificatioin problems, and can thus be divided into

- Regression trees
- Classification trees

Decision trees applied to regression and classificatioin problems

James, G., Witten, D., Hastie, T., & Tibshirani, R. (2013). An introduction to statistical learning (Vol. 112, pp. 3-7). New York: springer.

An Introduction to Statistical Learning with Applications in R

Steps of creating a decision tree

1. Over fitting -  Can create over-complex trees that do not generalize the data well. This problem gets solved by setting constraints on model parameters and pruning.
2. Not fit for continuous variables - While working with continuous numerical variables, decision tree loses information, when it categorizes variables in different categories.
3. Generally low accuracy compared to other ML algorithms
4.  Potentially unstable - because small variations in the data might result in a completely different tree being generated. This is called variance, which needs to be lowered by methods like bagging and boosting.

Source: [medium.com/greyatom/decision-trees-a-simple-way-to-visualize-a-decision-dc506a403aeb ](https://medium.com/greyatom/decision-trees-a-simple-way-to-visualize-a-decision-dc506a403aeb )

Decision Tree Disadvantages

The predictor space ($X_1, X_2, …, X_p$) is divided into J non-overlapping regions. Then make the same prediction for each observation that falls into the region $R_j$, and the predicted value is the mean of the response values for the training observations in $R_j$. The goal is to find the matrix region that minimizes the RSS of the model $\sum_{j=1}^{J} \sum_{i \in R_j} (y_i - \hat{y}_{R_j})^2$. 

Recursion Binary Splitting: from the top of the tree (*top-down*), the prediction space is split to two new branches, and the determination of the optimal (*best*) split is limited to a particular step instead of some future step. 

Cost Complexity pruning, as known as Weakest Link Pruning, is able to avoid overfitting. 
$$ \sum_{m=1}^{|T|} \sum_{i:x_i \in {R_m}} (y_i - \hat{y}_{R_m})^2 + \alpha |T| $$


Regression Tree

Classification Tree is used to predict qualitative variables instead of quantitative variables. It is very similar to regression tree and use recursive binary splitting to generate the classification tree. But use *Gini index* 
$$ G = \sum_{k=1}^{K} \hat{p}_{mk} (1-\hat{p}_{mk}) $$
and *entropy* as the indicator. 
$$ D = -\sum_{k=1}^{K} \hat{p}_{mk} log \hat{p}_{mk} $$

The small value of purity of node indicated that a node contains observations from almost the same category. *Entropy* is the same as Gini Index, if the $m$th node is pure, the *entropy* is very small. 

Learn Before

Related

Learn After