Apply the decision tree method to regression problems. Basically, it is to recursively divide (one of the remaining) predictor space(s) into 2 parts which leads to the greatest reduction in the total RSS. The processs repeats until a creterion (for instance, there're no more than 5 observations in one region) is met.

Given an observation, we can figure out the region it falls into and use the mean value in that region as the prediction.
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 trees

Apply the decision tree method to regression problems. It is quite similar to regression trees except that a qualitative, not quantitive, response is needed. This leads to following differences:
* The criterion for making the binary splits is no longer RSS.
* The most commonly class in the region, rather than the mean value, is used as the prediction result. 
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. 

Classification trees

1. Regression trees
2. Classification trees

University of Michigan - Ann Arbor

A decision tree divides the prediction space into a series of simple regions according to the stratifying criteria. Decision trees can be applied to both regression and classification problems and can thus be of two types.

Decision Tree

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

Linear Regression Model: 
$$ f(X) = \beta_0 + \sum_{j=1}^{p} X_j \beta_j $$
Regression Trees Model: 
$$ f(x) = \sum_{m=1}^{M} c_m · 1(x \in R_m) $$
Linear regression is a good choice if the relationship between predictive variables and response variables can be well fitted by linear models. On the other hand, the tree method is more appropriate if the relationship is highly nonlinear and complex. 


Trees VS. Linear Models

1) Decision trees are easily explainable to others

2) Compared to other statistical methods like regression, some believe that trees are much more similar to human decision making

3) Decision trees can be displayed graphically, which make them easy to interpret

4) There is no need to create dummy variables when handling qualitative predictors


Advantages to Using Decision Trees

1) Although trees may be easier to understand and interpret, they do not provide the same level of predictive accuracy compared to traditional regression and classification methods

2) Small changes in data can cause large changes in the final estimated tree

3) Not fit for continuous variables - While working with continuous numerical variables, decision tree loses information, when it categorizes variables in different categories.

4) Overfitting - Can create over-complex trees that do not generalize the data well and suffer from high variance. This problem gets solved by setting constraints on model parameters and pruning.


Disadvantages to Using Decision Trees

Types of decision trees

The algorithm required to build a decision tree involves 3 steps:

1. Start with an empty tree

2. Split on the feature with the highest information gain

3. Recurse with step 2

Creating a minimally sized tree which minimizes training error is actually an extremely hard, (NP-Hard) problem). To approximate this optimal solution, we build a tree by greedily splitting on the feature which results in the most information gain, i.e., pick the feature to split on that more certainly leads to a classification. 


Learning Decision Trees

Approaches for improving decision trees' predictions 

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

Leaf nodes: the end of a branch that represents an object

Nodes: split points

Pure node: all in this category are in one class; perfect classification

Mixed node: a mixture of classes that requires further splitting

Split point: the threshold that separates one class from another

Informativeness of split: a measure of how much information is gained from that node; the decision tree builds nodes the split points based on which gives the most informative split

Decision Tree Terms

https://scikit-learn.org/stable/auto_examples/tree/plot_cost_complexity_pruning.html

Post pruning decision trees with cost complexity pruning

Max depth controls the maximum depth or the number of split points the decision can have and it's the most common parameter used to reduce tree complexity and thus reduce overfitting. The min samples leaf parameter is the threshold that controls what the minimum number of data instances has to be in a leaf to avoid splitting it further. This setting also reduces tree complexity. Finally, max leaf nodes limits the total number of nodes that are leaves of the tree.

Scikit learn key decision tree parameters

- N_estimators: sets # of small decision trees to use in the ensemble 
   - More trees can lead to overfitting
   - Chosen to best exploit the speed and memory capabilities
- Learning_rate: controls emphasis on fixing errors from previous iteration 
   - Adjusted given n_estimators
- The above two are typically tuned together 
   - Small learning rate requires more n estimators to maintain model complexity 
- Max_depth: typically set to a small value (3-5) for most applications
Can effect model complexity


Decision tree key parameters

- Training builds a series of small decision trees 
- Each tree attempts to correct errors from previous stage 
- The learning rate controls how hard each tree tries to correct remaining mistakes from previous round
   - High learning rate: more complex trees 
   - Low learning rate: simpler trees 


Gradient Boosted Decision Trees 

A decision tree of depth 2 is visualized below. Using the 'value' attribute of each leaf, find the accuracy score for the tree of depth 2 and the accuracy score for a tree of depth 1. What is the improvement in accuracy between the model of depth 1 and the model of depth 2?

Learn Before

Related

Learn After