--- title: "Decision Trees (and k-Nearest-Neighbours)" output: html_document: default pdf_document: default --- ```{r setup, include=FALSE} knitr::opts_chunk$set(echo = TRUE, message = FALSE, warning = FALSE, fig.width = 6, fig.height = 4) library(ggplot2) ``` Alongside [neural networks](neural_networks.html), the other workhorse for prediction — especially on **tabular** data — is the **decision tree**, and its ensemble cousin the **random forest**. We'll motivate them by comparing how different classifiers carve up the input space. ## The running example: oranges vs. lemons Each fruit has a **width** and a **height**; we want to label it *orange* or *lemon*. A toy dataset: ```{r fruit-data} set.seed(1) n <- 40 lemons <- data.frame(width = rnorm(n, 5.5, 0.7), height = rnorm(n, 7.5, 0.7), fruit = "lemon") oranges <- data.frame(width = rnorm(n, 7.5, 0.7), height = rnorm(n, 7.0, 0.7), fruit = "orange") fruit <- rbind(lemons, oranges) fruit$fruit <- factor(fruit$fruit) ggplot(fruit, aes(width, height, color = fruit, shape = fruit)) + geom_point(size = 2) + scale_color_manual(values = c(lemon = "goldenrod", orange = "darkorange")) + labs(title = "Classify a new fruit from width & height") ``` ## Four ways to draw the boundary Every classifier we've met carves the feature space differently. - **k-nearest-neighbours (kNN)** — to label a new point, take its $k$ nearest training points and let them **vote**. ($k = 1$ is the plain nearest-neighbour of the [neural networks](neural_networks.html) notes.) The boundary is a patchwork of little **islands** around clusters of each class. - **Logistic regression** — a single **straight line** (a hyperplane in higher dimensions): one side orange, the other lemon. - **Neural network** — logistic regression with a more flexible function: a **smooth curved** boundary. - **Decision tree** — repeatedly split the space in half on one feature at a time, giving a boundary of **axis-parallel rectangles**. ### kNN, concretely ```{r knn} library(class) set.seed(2) train_idx <- sample(nrow(fruit), 60) train <- fruit[train_idx, ] test <- fruit[-train_idx, ] pred <- knn(train = train[, c("width", "height")], test = test[, c("width", "height")], cl = train$fruit, k = 5) mean(pred == test$fruit) # accuracy ``` kNN needs no "training" beyond storing the data, but it must search all of it at prediction time, and "nearest" uses raw distances, so feature scaling matters. ## A decision tree A tree asks a sequence of yes/no questions. At each **internal node** a question like "is width > 6.5?" sends you left or right; each **leaf** gives a label. It looks like an upside-down tree — root at top, leaves at the bottom. ```{r tree} library(rpart) tree <- rpart(fruit ~ width + height, data = fruit, method = "class") par(mar = c(1, 1, 1, 1)) plot(tree, margin = 0.1); text(tree, use.n = TRUE, cex = 0.9) ``` Read a prediction by walking root-to-leaf. Notice a tree may **ignore** a feature entirely if it isn't useful, and may **split on the same feature more than once** at different thresholds. Let's see the rectangular boundary it induces: ```{r tree-boundary} grid <- expand.grid( width = seq(min(fruit$width), max(fruit$width), length.out = 200), height = seq(min(fruit$height), max(fruit$height), length.out = 200)) grid$pred <- predict(tree, grid, type = "class") ggplot() + geom_tile(data = grid, aes(width, height, fill = pred), alpha = 0.3) + geom_point(data = fruit, aes(width, height, color = fruit, shape = fruit), size = 2) + scale_fill_manual(values = c(lemon = "goldenrod", orange = "darkorange")) + scale_color_manual(values = c(lemon = "goldenrod", orange = "darkorange")) + labs(title = "A decision tree splits into axis-parallel rectangles") ``` ## What can a tree represent? In principle **any** boolean function of the inputs — including patterns a straight line *can't* separate. The classic one is **XOR / checkerboard**: label $1$ on two diagonally-opposite corners, $0$ on the other two. ```{r xor} xor_df <- data.frame( x1 = c(0, 0, 1, 1), x2 = c(0, 1, 0, 1), label = factor(c(0, 1, 1, 0))) xor_df ``` No straight line separates the two labels, so **logistic regression fails here** — but a small tree handles it easily (split on `x1`, then on `x2` within each half). A caveat about that intuition, though: in **two** dimensions lots of things aren't linearly separable, but with **many** features (say 50), a separating hyperplane usually *does* exist — our 2-D geometric intuition misleads us. So logistic regression works far more often than the XOR picture suggests. The flip side: some simple-looking functions are **hard** for trees. The **parity** function (output 1 iff an odd number of inputs are 1) is a high-dimensional checkerboard; a tree can represent it but needs to split on every feature repeatedly, so it takes a large tree and lots of data. As you allow bigger trees (more nodes, more depth), the **hypothesis space** — the set of labelings the tree can express — grows; logistic regression's is always just "which hyperplane?" ## How a tree is learned Finding the *optimal* tree is NP-hard, so in practice we use a **greedy heuristic**: grow the tree top-down, at each step picking the split that looks best *right now*, then **recurse** on each side. ``` learn(data): if all labels in `data` are the same -> make a leaf else: pick the feature (and threshold) whose split is "best" partition data into S0, S1 by that split learn(S0); learn(S1) # recurse on each side ``` Details: - **Discrete feature** → one branch per category. **Continuous feature** → pick a **threshold**. You don't try every real number: only values *present in the data* can matter, so you try thresholds between adjacent observed values. - **Which split is "best"?** Simplest: try each feature's best threshold and take the one giving the lowest **error rate**, where a not-yet-pure node is labeled by **majority vote**. One subtlety — error count can *stay the same* after a useful split, so real implementations use an information-theoretic score (information gain / Gini) instead of raw error. Same idea, more sensitive. ## Random forests A single tree is easy to overfit and sensitive to the data. The fix that dominates tabular-data competitions (e.g. on Kaggle) is the **random forest**: grow **many** trees — each on a random resample of the data and a random subset of features — and **average their predictions**. Many trees ⇒ a "forest" (the name is a mild joke). You rarely build these by hand; a library does it. Empirically, for a plain table of features with labels, a random forest is often the most accurate off-the-shelf choice. ## Interpretability Trees are often sold as **interpretable**: you can read the learned tree and say "outlook matters most; if it's sunny, then humidity matters." True for a *small* tree. But two caveats: a tree past a few branches is hard to hold in your head, and because it was built **greedily**, the feature at the root isn't guaranteed to be the genuinely most important one. And a random forest — an average of many trees — loses this transparency almost entirely. So "interpretable" is real but limited. ## Summary - **kNN**: vote among the $k$ nearest training points; boundary is islands; no training, but stores and searches all data. - Classifiers carve space differently — **line** (logistic regression), **smooth curve** (neural net), **axis-parallel rectangles** (tree), **islands** (kNN). - A **decision tree** asks yes/no questions down to leaf labels; it can represent any boolean function (including XOR, which defeats a linear model), but some functions (parity) need a huge tree. - Trees are learned **greedily** (optimal is NP-hard): pick the best split, recurse; thresholds come from values in the data; score splits by information gain. - **Random forests** — averages of many trees — are the go-to for tabular data, trading interpretability for accuracy. ## References - Builds on [neural networks](neural_networks.html) (nearest-neighbour, the model comparison) and [logistic regression](logistic_regression.html) (the linear boundary). - Hastie, Tibshirani & Friedman, *The Elements of Statistical Learning*, Ch. 9 (trees) and Ch. 15 (random forests).