Chapter 5 - Decision Trees

Question 1

Terminal Nodes

Answer 1

Terminal Nodes/Leaves represent the partitions of the predictor space

Question 2

Internal Nodes

Answer 2

Internal Nodes are points along the tree where splits occur

Question 3

Branches

Answer 3

Branches are lines that connect any 2 nodes

Question 4

Stump

Answer 4

A decision tree with only one internal node is called a stump

Question 5

Decision Tree Making Algorithm

Answer 5

1. Construct a large tree with g terminal nodes using recursive binary splitting.
2. Obtain a sequence of best subtrees, as a function of lambda, using cost complexity pruning
3. Choose lambda by applying k-fold cross valiation. Select the lambda that results in the lowest cross-validation error.
4. The best subtree is the subtree created in step 2 with the selected lambda value.

Question 6

Recursive Binary Splitting

Answer 6

A top down and greedy approach to creating decision trees

Question 7

Classification Error Rate (Em)

Answer 7

The fraction of training observations that do not belong to the most frequent category.
Em = 1- maxc(pm,c)

Question 8

Gini Index (Gm)

Answer 8

The sum from c = 1 to w of pm,c(1-pm,c)

Question 9

Cross Entropy (Dm)

Answer 9

The negative sum from c = 1 to w of pm,c * lnpm,c

Question 10

Residual Mean Deviance

Answer 10

deviance / n - g

Question 11

Pure Node

Answer 11

A node is said to be pure if all the observations in that node are of the same category

Question 12

Classification Error Rate Sensitivitiy

Answer 12

Classification error rate is not as sensitive to node impurity as the Gini index and the cross entropy are.

Question 13

Error Rate Preferences

Answer 13

Gini index and cross entropy are preferred over classification error rate in tree-growing. Classification error rate is generally preferred in tree-pruning if prediction accuracy is the ultamite goal.

Question 14

Cost Complexity Pruning Lambda

Answer 14

Cost complexity pruning uses a lambda in its minimization function similar to lasso regression. The higher the value of lambda - the higer the complexity penalty and the smaller the resulting tree and also variance. When lambda = 0 the fitted tree is the largest possible. When lambda is suffuiciantly large, the fitted tree is the simplest tree only consisting of the root node and makes no splits.

Question 15

Regression Trees vs Linear Models

Answer 15

If the relationship between the response and the predictors is well approximated by a linear model then linear models will likely outperform trees. If the above relationship is highly non-linear or more complex than a linear model can handle, then trees will likely outperform linear models.

Question 16

Advantages of Trees

Answer 16

Easy to interpret and explain. Can be presented visually. Manage categorical variables without the need of dummy variables. Mimic human decision making.

Question 17

Disadvantages of Trees

Answer 17

Not robust - A small change in the data can cause a large change in the final tree. Do not have the same degree of predictive accuracy as other statistical methods.

Question 18

Bagging Algorithm

Answer 18

1. Create b bootstrap samples from the original training dataset.
2. Construct a decision tree for each bootstrap sample using recursive binary splitting
3. Predict the response of a new observation by averaging the predictions (regression trees) or by using the most frequent category (classification trees) across all b trees.

Question 19

Bagging Properties

Answer 19

General purpose procedures that works for many statistical methods - unusual for time series data. Bagging reduces varaince, but it is difficult to intrepret the whole bagged model. Increasing b does not cause overfitting. Each bagged tree uses about 2/3 of the original observations.

Question 20

Out of Bag Observations (OOB)

Answer 20

The observations that are not used to train a particular bagged tree are called out-of-bag observations. OOB error is a valid estaimate of test error.

Question 21

Random Forests Algoritm

Answer 21

1. Create b bootstrap samples from the orignial training dataset.
2. Construct a decision tree for each bootstrap sample using recursive binary splitting. At each split, a random subset of k variables are considered.
3. Predict the response of a new observation by averaging the predictions (regression trees) or by using the most frequent category (classification trees) across all b trees.

Question 22

Random Forests Properties

Answer 22

Bagging is a special case of random forests where k = p. Random forests reduce variance by averaging the results of decorrelated trees. Increasing b does not cause overfitting. Decreaing k reduces the correlation between predictions.

Question 23

Boosting Algorithm

Answer 23

Let z1 be the actual response variable y.
1. For k = 1, 2, … , b:
Use recursive binary splitting to fir a tree with d splits to the data with zk as the response.
Update zk by subtracting lambda * fk(X)
2. Calculate the boosted model prediction as f(X) = sum from k=1 to b of lambda * fk(x)

Question 24

Boosting Properties

Answer 24

It grows trees sequentially by using information from previous trees. Increasing b can cause overfitting, and b is usually selected by cross-validation. Boosting reduces bias. d, the interation depth, controls the complexity of the boosted model - a tree with d splits has d+1 terminal nodes and if d = 1 the model is an additive model. lambda, the shrinkage parameter controls the rate at which boosting learns - Boosting is an example of slow learning and typically lambda is between 0 and 1. A small lambda may require a large b to achieve a good model