--- author: "DSC365: Introduction to Data Science" title: "Decision Trees and Random Forests" date: October 27, 2026 format: revealjs: echo: true toc: true toc-depth: 1 toc-title: Outline slide-number: true menu: numbers: true chalkboard: src: chalkboard-fall2026.json --- ```{r echo=FALSE, message=FALSE, warning = FALSE} library(tidyverse) library(knitr) library(mosaic) library(infer) library(caret) hook_output = knit_hooks$get('output') knit_hooks$set(output = function(x, options) { # this hook is used only when the linewidth option is not NULL if (!is.null(n <- options$linewidth)) { x = xfun::split_lines(x) # any lines wider than n should be wrapped if (any(nchar(x) > n)) x = strwrap(x, width = n) x = paste(x, collapse = '\n') } hook_output(x, options) }) ``` # Announcements {.unlisted .unnumbered} **Lab 5** (Linear Models) - Due Tonight at 11:59 pm in Blueline **Quiz 3**: in class on Thursday (October ) - Covers: Prediction/KNN/Tree-Based Methods - If we don't get to it in class today, it won't be on the quiz, but you might need it for the lab. [Link so source code](decision-trees.qmd) [Link to pdf](decision-trees.pdf) # Tree-based machine learning methods ## Tree-Based Methods - Can be used for both regression and classification + *Regression* models $\longrightarrow$ *quantitative* response variable + *Classification* models $\longrightarrow$ *categorical* response - These involve stratifying or segmenting the predictor space into a number of simple regions # Example Classification Scenario ## Example: Marijuana legalization The General Social Survey is a wide-ranging survey conducted biannually to measure cultural shifts in American society. We can use the GSS to get an idea of how popular opinion has changed. **Goal**: Use Age to predict people’s opinion of marijuana legalization. ```{r, echo = FALSE} GSS <- read.csv("GSS2016.csv") table(GSS$GRASS) ``` ::: {.notes} Data Cleanings Steps (see `decision-trees-random-forests.R`) - Only going to look at one year, 2016, and remove "Not applicable" from our response - Want just two groups for responses: Legal and Not legal - Change variables to proper type (numeric - will have coercion) ::: ## Let's Clean Our Data! Yay! Data: [GSS2016.csv](GSS2016.csv) Data cleaning: [`decision-trees-random-forests.R`](decision-trees-random-forests.R) - Let's only look at one year, say 2016, and remove "Not applicable from our response" - Want just two groups for responses: Legal and Not legal - Change variables to proper type ```{r} #| code-line-numbers: "1-3|4-5|6" GSS <- GSS %>% filter(YEAR==2016) %>% filter(GRASS != 'Not applicable') GSS <- GSS %>% mutate(LEGAL = ifelse(GRASS=='Legal', 'Legal', 'Not legal')) GSS$AGE <- as.numeric(GSS$AGE) ``` ## Testing data v. Training data ```{r} set.seed(4) test_id <- sample(1:nrow(GSS), size=round(0.2*nrow(GSS))) TEST <- GSS[test_id,] TRAIN <- GSS[-test_id,] ``` How many people in the training data set support marijuana legalization? ```{r} TRAIN %>% group_by(LEGAL) %>% summarize(n=n()) ``` # Decision Trees: Classification ## What is a decision tree Decision trees: A tree-like model of decisions and their possible consequences - Has flowchart-like structure in which each... ```{r, echo=FALSE, fig.align='left',out.width="75%", fig.alt="Overview of the flowchart structure of a decision tree. The tree begins at a root decision node. Based on the test outcome of this decision node, this leads to other outcomes. These tests keep happening until we reach a terminal node of the decision tree which provides the predicted outcome."} knitr::include_graphics("./images/decision-tree.png") ``` ## How Decision Trees classify How to decide to split? - As the number of predictors increases, so does the number of possible trees. + Optimal decision trees do not exist (Hyafil & Rivest, 1976) + So several competing methods for building decision trees ## How Decision Trees classify (cont) {.smaller} Recursive Partitioning: Split infinite # of times until reach stopping criterion. **Split:** Gini Index (default): $$G = \sum_{k=1}^{K} \hat{p}_{mk}(1-\hat{p}_{mk})$$ where $\hat{p}_{mk}$ is the proportion of training observations in $m^{th}$ region from $k^{th}$ class. **Stop:** Complexity parameter ## Fitting A Decision Tree (Classification) ```{r} #install.packages('rpart') library(rpart) rpart(LEGAL~AGE, data=TRAIN, na.action = na.pass) ``` ## Visualizing a Decision Tree (Classification) ```{r, message=FALSE, fig.height=8, fig.width=10, eval = FALSE} #install.packages("rattle") library(rattle) tree <- rpart(LEGAL~AGE, data=TRAIN, na.action = na.pass) fancyRpartPlot(tree) ``` ```{r, echo = FALSE} tree <- rpart(LEGAL~AGE, data=TRAIN, na.action = na.pass) ``` ```{r, echo=FALSE, fig.align='center',out.width="75%", fig.alt="Decision tree for GSS data with just Age as an explanatory variable. There is a split at Age = 69, where those younger than 69 are classified as Legal, and those 69 and older are classified as Not Legal"} knitr::include_graphics("./images/tree1.png") ``` # Evaluation ## Evaluating a decision tree - Confusion Matrix - Classification Accuracy ## Evaluating a decision tree: Confusion Matrix ```{r} TRAIN <- TRAIN %>% mutate(Legal_Tree = predict(tree, type='class')) confusion_train <- tally(Legal_Tree~LEGAL, data=TRAIN) confusion_train ``` ```{r} TEST <- TEST %>% mutate(Legal_Tree = predict(tree, type='class', newdata = TEST)) confusion_test <- tally(Legal_Tree~LEGAL, data=TEST) confusion_test ``` ## Evaluating a decision tree: Classification Accuracy Training Accuracy: ```{r} sum(diag(confusion_train))/nrow(TRAIN) ``` Testing Accuracy: ```{r} sum(diag(confusion_test))/nrow(TEST) ``` ## Tuning Parameter: Complexity parameter Using recursive partitioning can overfit the training data - Prune Tree ```{r, message=FALSE} printcp(tree) ``` - Changing complexity parameter: ```{r, eval = FALSE} #| code-line-numbers: "2" rpart(LEGAL~AGE, data=TRAIN, na.action = na.pass, control = rpart.control(cp = 0.05)) ``` # Decision Trees for Regression ## Decision Trees (Regression) How to decide to split? - Find regions $(R_j)$ that minimizes the residual sum of squares $$RSS = \sum^{J}_{j=1}\sum_{i \in R_j}(y_i - \hat{y}_{R_j})^2$$ - Stops when you reach some criterion (cp) ## Fitting A Decision Tree (Regression) Let's suppose we want to use people’s political view (POLVIEWS) and marital status (MARITAL) to estimate people’s age. ```{r, eval = FALSE} tree2 <- rpart(AGE ~ POLVIEWS + MARITAL, data=TRAIN) fancyRpartPlot(tree2) ``` ```{r, echo = FALSE} tree2 <- rpart(AGE~POLVIEWS + MARITAL, data=TRAIN) ``` ```{r, echo=FALSE, fig.align='center',out.width="75%", fig.alt="A regression decision tree with an initial split for Marital status. For those who were never married or separated have a predicted age of 32. For those who are married or divorced, they have a predicted age of 52. Anyone in a different category has a predicted age of 69."} knitr::include_graphics("./images/tree2.png") ``` ## Prediction using Decision Tree We can still use the predict function to predict our regression decision tree outputs. ```{r} #| code-line-numbers: "1-3|1" TEST <- TEST %>% filter(MARITAL != "No answer") predict(tree2, TEST , method = "anova") %>% head() ```

**Caution**: Can only predict using categorical variables located in the Training Set # Comparison with other methods ## Trees Versus Linear Models - If the relationship between the features and the response is well approximated by a linear model: + Linear regression

- If instead there is a highly nonlinear and complex relationship between the features and the response as indicated by model: + Decision trees ## Advantages and Disadvantages of Decision Trees **Advantages**


**Disadvantages** # Random Forests ## Random Forests A random forest is collection of decision trees^[A collection of trees is called a forest.] that are aggregated by majority rule When to use random forest: - large number of variables, no idea which are important - potential collinearity in predictors ## Building a Random Forest {.scrollable .smaller} In building a random forest, each time a split in a tree is considered, a random sample of $m$ predictors is chosen as split candidates from the full set of $p$ predictors. - each time a split is considered, a fresh set of $m$ random predictors are selected - Only one of the $m$ variables is selected for the split - $m$ is a *tuning parameter*. Typically use $m \approx \sqrt{p}$, Hence, at each split in the tree, the algorithm is not even allowed to consider a majority of the available predictors. Why is this a good thing? - Roughly speaking, randomness is a method of search: You are searching the space of all possible trees for the "best" or "most explanatory." So randomly picking variables can help you discover the most important/most explanatory predictors. # Example: Identifying Important Variables ## Fit random forest {.scrollable .smaller} **Goal**: Which variables are most important for predicting views on marijuana legalization? ```{r, echo=FALSE} #install.packages('randomForest') ``` The code below will fit a model to predict `LEGAL` using all the other variables. ```{r, message=FALSE, eval=FALSE} #| code-line-numbers: "4-6" library(randomForest) forest_grass <- randomForest(as.factor(LEGAL)~NEWSFROM+HAPPY+RELIG+COURTS+ENERGY+EDUC+ENVIR+POLVIEWS+PARTYID+REGION+INCOME+SEX+DEGREE+AGE+MARITAL+BALLOT, data=TRAIN, na.action = na.omit, ntree=201, mtry=4) forest_grass ``` - `na,action = na.omit` ignores observations with missing data - `ntree = 201` is the number of trees in the forest (odd so there won't be ties) - `mtry = 4` the number $m$ of variables to use at each split (note: there's a total of $p = 16$ predictors, and $m = 4 = \sqrt{p} = \sqrt{16}$) ## Fit random forest (cont) {.unlisted .scrollable .smaller} Here's the actual output. Explanation below the output ```{r, message=FALSE} library(randomForest) forest_grass <- randomForest(as.factor(LEGAL)~NEWSFROM+HAPPY+RELIG+COURTS+ENERGY+EDUC+ENVIR+POLVIEWS+PARTYID+REGION+INCOME+SEX+DEGREE+AGE+MARITAL+BALLOT, data=TRAIN, na.action = na.omit, ntree=201, mtry=4) forest_grass ``` Interpreting the output: > `OOB estimate of error rate: 33.96%` For each tree, some of the data is held out (as testing data). This error rate is the average, over those trees, of the test error. ## Test predictions ```{r} TEST <- TEST %>% mutate(Legal_RF = predict(forest_grass, type='class', newdata = TEST)) TEST$Legal_RF[1:5] confusion_test <- tally(Legal_RF~LEGAL, data=TEST) sum(diag(confusion_test))/nrow(TEST) ``` Classification accuracy above 50% is better than random guessing, but still worse than a decision tree just using `AGE` ## Variable Importance {.scrollable} Since each tree in a random forest uses a different set of variables, we want to keep track of which variables seem to be the most consistently influential. :::: {.columns} ::: {.column width="50%"} ```{r} randomForest::importance(forest_grass) %>% as.data.frame() %>% rownames_to_column() %>% arrange(desc(MeanDecreaseGini)) ``` ::: ::: {.column width="50%"} - Table shows how much the Gini index decreases when a variable is included - From previous slides, we want to _minimize_ Gini index, so the largest _decrease_ corresponds to the _most useful_ variables ::: :::: # Summary ## Modeling Data {.smaller .scrollable} - [**Linear model**](../../08-statistical-foundations/slides/linear-models/linear-models.html) + The basic model for *regression* only + easy interpretation, but strict assumptions + Use [cross-validation (CV)](../../09-cv-and-knn/slides/cv.html) to ensure quality of model - [**KNN:**](../../09-cv-and-knn/slides/knn.html) + Can be applied to *regression* and *classification* + fast, no assumptions, can add data anytime. + large number of variables can lower quality + use CV to decide $k$ - **Decision tree:** + Can be applied to *regression* and *classification.* + good data visualization + high variance - **Random Forest:** + a collection of tree models; can be applied to *regression* and *classification.* + Hard to interpret, but can output variable importance + Can be useful for *variable selection* + outperforms linear model when variables are no linearly independent ## Variable Selection {.scrollable} Ultimately, a model is a way to convert input variables into output predictions. Which variables should you use? **Variable Selection** is a hard problem - Variable importance (from a few slides ago) is one way - the $R^2$ value from a [linear regression](../../08-statistical-foundations/slides/linear-models/linear-models.html) is another A few more methods will come up over the remainder of the semester, but there is no single best way to do it.