LSMA

LONDON SCHOOL OF MULTIOMICS & AI

Free course

Free course

0 of 35 lessons

Lesson 5 of 9

Module 4 · Machine learning

Trees and ensembles

Trees and ensembles

Trees and ensembles

Decision trees ask a series of yes-or-no questions. One tree is easy to read but unstable; hundreds of trees together, as random forests or gradient boosting, are among the strongest models for tables of data.

⏱ 12 min readModule 4 · Machine learningFree
Lesson at a glance7 steps · about 12 min
  1. A small tree you can read
  2. What this does
  3. Reading the output
  4. What this does
  5. Many trees: random forests and gradient boosting
  6. What this does
  7. Reading the output

Before you start. This lesson carries on in the notebook from Your first classifier. If you open a new notebook, or Colab has restarted, run this setup cell first. It repeats the loading, the split and the model from that lesson.

Python · setup
import numpy as np
import pandas as pd
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.linear_model import LogisticRegression

data = load_breast_cancer(as_frame=True)
df = data.frame
df["diagnosis"] = df["target"].map({0: "malignant", 1: "benign"})
X = df[data.feature_names]
y = (df["diagnosis"] == "malignant").astype(int)

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, stratify=y, random_state=42)
model = make_pipeline(StandardScaler(), LogisticRegression(max_iter=1000)).fit(X_train, y_train)

A small tree you can read

A decision tree classifies a sample by asking a series of yes-or-no questions about its features, such as "is the worst perimeter at most 112.80?". Each answer sends the sample down one branch, and the final box it reaches, a leaf, gives the prediction. To build the tree, the algorithm looks at every feature and every possible cut-off and picks the question that best separates malignant from benign in the training data. It then repeats the search inside each branch. The depth is the largest number of questions asked on the way to a leaf.

Python
from sklearn.tree import DecisionTreeClassifier, export_text

tree = DecisionTreeClassifier(max_depth=2, random_state=0).fit(X_train, y_train)
print(export_text(tree, feature_names=list(X.columns), decimals=2))
print(round(tree.score(X_test, y_test), 3))

What this does

  • The first line imports the tree model and export_text, a function that prints a fitted tree as indented text.
  • DecisionTreeClassifier(max_depth=2, random_state=0) creates a tree that may ask at most two questions in a row. random_state=0 fixes how ties between equally good questions are broken, so the tree is the same every run. .fit(X_train, y_train) grows it on the same training set as Your first classifier. Note that there is no scaler: a tree compares one feature at a time with a cut-off, so the units do not matter.
  • export_text prints the questions. feature_names=list(X.columns) tells it to use the real column names, and decimals=2 rounds the cut-offs to two decimal places.
  • The last line prints the test accuracy, rounded to three decimal places.
|--- worst perimeter <= 112.80 | |--- worst concave points <= 0.16 | | |--- class: 0 | |--- worst concave points > 0.16 | | |--- class: 1 |--- worst perimeter > 112.80 | |--- mean texture <= 14.95 | | |--- class: 0 | |--- mean texture > 14.95 | | |--- class: 1 0.921

Reading the output

Each |--- is a branch, and each extra level of indentation is one question deeper. Read the first question as "is the worst perimeter at most 112.80?" (<= means "less than or equal to"). If yes, the tree next asks about worst concave points; if no, it asks about mean texture. The class lines are the leaves. Because malignant was coded as 1 in Your first classifier, class: 0 means benign and class: 1 means malignant. The final number, 0.921, is the test accuracy: 105 of the 114 test masses correct. The figure draws the same tree as a diagram.

Trees and ensembles · LSMA free course The first question is whether worst perimeter is at most 112.80. If yes, the tree asks whether worst concave points is at most 0.16: yes gives benign, no gives malignant. If no, it asks whether mean texture is at most 14.95: yes gives benign, no gives malignant. TWO QUESTIONS, FOUR LEAVES worst perimeter ≤ 112.80 worst concave points ≤ 0.16 mean texture ≤ 14.95 yes no yes no yes no class 0 class 1 class 0 class 1 benign malignant benign malignant Answer each question; "yes" goes left, "no" goes right, until you reach a leaf.
The same tree as the printed output. A mass is sent down from the top; the colour of the leaf it reaches is the prediction. The cut-offs are in the features' original units, so a pathologist could apply them by hand.

Two questions classify 92.1% of the test masses correctly, and a pathologist could follow the logic. Without a depth limit, the tree keeps splitting until it fits the training data perfectly:

Python
deep = DecisionTreeClassifier(random_state=0).fit(X_train, y_train)
print("train", deep.score(X_train, y_train), "test", round(deep.score(X_test, y_test), 3),
      "depth", deep.get_depth())

What this does

This tree has no max_depth, so it keeps asking questions until every leaf holds training masses of only one class. The print line reports three things: the accuracy on the training set, the accuracy on the test set (rounded to three places), and get_depth(), the number of questions on the longest path from the top to a leaf.

train 1.0 test 0.93 depth 8

100% on training data and 93% on test data is overfitting in one line: the tree learned the noise as well as the pattern.

Reading the output: the tree is right about every one of the 455 training masses (1.0), but only 93% of the test masses (0.93, which is 106 of 114). It needed eight questions in a row to get there. The deep tree does beat the depth-2 tree on the test set, but only slightly, and the gap between its training and test scores shows it has memorised details that do not carry over. Single trees have a second weakness: they are unstable. Remove a few training masses and the first question can change, and with it the whole tree below.

Depth is not the only way to stop a tree growing. min_samples_leaf=10, for example, forbids any leaf with fewer than 10 training masses, so the tree cannot carve out a branch for one odd sample. Whichever control you use, choose its value by cross-validation, as in Cross-validation and data leakage, not by comparing test scores. Here, 0.921 against 0.93 is a difference of one test mass, far too small to choose between them.

Trees also have a distinctive shape. Their predictions jump at each cut-off and are flat in between, so a mass with a worst perimeter of 112.79 and one of 112.81 can get different answers, while two masses of very different sizes beyond the last cut-off get the same one. A tree cannot predict beyond the range it was trained on: it simply repeats the answer of the outermost leaf. That matters more for regression, in the next lesson, than here.

Go deeper: how a tree scores a question

“Best separates” has a precise meaning. By default scikit-learn uses Gini impurity: 1 minus the sum of the squared class shares in a group. A group that is all one class scores 0; a 50:50 group scores 0.5.

Take a node with 40 malignant and 60 benign masses: 1 − (0.4² + 0.6²) = 0.48. A question splits it into 50 masses with 5 malignant, scoring 1 − (0.1² + 0.9²) = 0.18, and 50 with 35 malignant, scoring 1 − (0.7² + 0.3²) = 0.42. Weighted by size, the children score 0.5 × 0.18 + 0.5 × 0.42 = 0.30. The question lowers the impurity by 0.18. The tree tries every feature and cut-off, and keeps the question with the largest drop.

Many trees: random forests and gradient boosting

A random forest trains hundreds of trees, each on a random sample of rows and features, and averages their votes. Gradient boosting builds trees one after another, each correcting the errors of the last. Compare them fairly with the same cross-validation folds:

An ensemble is a model made of many models. The two kinds here combine trees in opposite ways. In a random forest, each tree sees a different random sample of the training rows (drawn with replacement, so some rows appear twice and others not at all) and, at each split, only a random subset of the features. The trees make different mistakes, and averaging their votes cancels much of the instability of a single tree. In gradient boosting, each new tree is usually small, and it is fitted to what the trees so far still get wrong; the final prediction adds up all their contributions.

The two also respond differently to their settings. In a forest, more trees make the average steadier and almost never make it worse; past a few hundred, they mostly cost time. The setting that matters more is how many features each split may consider, max_features: fewer makes the trees more different from each other. A forest also gives a free check. Each tree leaves out about a third of the rows when it draws its sample, and RandomForestClassifier(oob_score=True) scores every row using only the trees that did not see it, the out-of-bag score.

Boosting is the opposite: every extra tree fits the remaining errors more closely, so too many trees can overfit. Its key settings are the number of rounds, max_iter, and the learning_rate, which scales down each tree's contribution. A smaller learning rate needs more rounds but usually generalises better. HistGradientBoostingClassifier can stop early when a held-out part of the training data stops improving; by default it does this only on datasets larger than 10,000 rows, so here it runs its full 100 rounds.

Trees and ensembles · LSMA free course Left: a random forest grows many trees independently, each on a random sample of rows and features, and averages their votes. Right: gradient boosting grows trees one after another, each correcting the errors left by the trees before it, and adds their contributions. 1 · RANDOM FOREST 2 · GRADIENT BOOSTING Trees grown side by side Trees grown one after another each: random rows, random features Average all the votes here: 300 trees each fixes what the last left wrong Add up their corrections trees are usually small
Forests reduce the instability of single trees by averaging many independent ones; boosting builds accuracy step by step. Each small tree icon stands for a whole tree. Schematic, not to scale.
Python
from sklearn.ensemble import RandomForestClassifier, HistGradientBoostingClassifier
from sklearn.model_selection import StratifiedKFold

models = {
    "Logistic regression": make_pipeline(StandardScaler(), LogisticRegression(max_iter=1000)),
    "Decision tree (depth 2)": DecisionTreeClassifier(max_depth=2, random_state=0),
    "Random forest": RandomForestClassifier(n_estimators=300, random_state=0),
    "Gradient boosting": HistGradientBoostingClassifier(random_state=0),
}
cv = StratifiedKFold(n_splits=5, shuffle=True, random_state=1)
for name, m in models.items():
    s = cross_val_score(m, X_train, y_train, cv=cv, scoring="roc_auc")   # training set only
    print(f"{name:24s} AUC {s.mean():.3f} ± {s.std():.3f}")

What this does

  • The imports bring in the two ensemble models and StratifiedKFold, which makes stratified folds.
  • models is a dictionary: each key is a name for printing, each value an unfitted model. n_estimators=300 asks the forest for 300 trees. HistGradientBoostingClassifier is scikit-learn's fast version of gradient boosting: it first sorts each feature's values into a limited number of bins, which makes the search for good questions much quicker on large datasets.
  • StratifiedKFold(n_splits=5, shuffle=True, random_state=1) defines five stratified folds, with the rows shuffled first in a fixed, repeatable way. Making this one object, cv, and passing it to every model means all four are tested on exactly the same five folds.
  • The loop takes each name and model in turn, runs cross_val_score on the 455 training masses only, with AUC as the score, and prints one line. The 114 test masses stay sealed, as in Cross-validation and data leakage. In the f-string, {name:24s} pads the name to 24 characters so the columns line up, {s.mean():.3f} prints the mean with three decimals, and {s.std():.3f} prints the standard deviation of the five fold scores.
Logistic regression AUC 0.993 ± 0.007 Decision tree (depth 2) AUC 0.892 ± 0.050 Random forest AUC 0.990 ± 0.006 Gradient boosting AUC 0.993 ± 0.003

Reading the output

Each line is one model: its mean AUC over the five folds of the training set, then ± the standard deviation across folds. The depth-2 tree is clearly behind (0.892) and also the least consistent (± 0.050): its folds vary the most. The other three are within about 0.004 of each other, which is smaller than the fold-to-fold spread of logistic regression or the forest. On these data, the differences between logistic regression, the forest and boosting are too small to call.

This is the same judgement you made in Comparisons and uncertainty: when the spread of each estimate is as large as the gap between them, the gap is not evidence. Using the same folds for every model helps, because each model faces exactly the same easy and hard masses, so the fold-by-fold differences are fairer than comparing means from different splits. Even so, five fold scores are few, and they are not fully independent, because the training sets overlap. Treat a ± from cross-validation as a rough guide to spread, not as a formal error bar.

A pitfall when comparing many models is to try a dozen, keep the best and report its score. The best of twelve scores is partly luck, the same selection effect as picking genes from noise. Decide in advance which few models you will compare, and confirm the winner on the sealed test set.

The ensembles beat the single tree easily, but here they do not beat logistic regression: the pattern in these data is close to linear. Trees do not need scaled features, and they shine when effects interact or are not straight lines.

A pattern is linear when the effect of each feature adds up in a straight-line way: more of a feature always pushes the risk the same direction by the same amount. Effects interact when the effect of one feature depends on another, for example when a gene raises risk only in patients who also carry a particular mutation. A tree captures that naturally by asking one question inside the branch of another; logistic regression cannot, unless you add the combination as a feature yourself.

051015Normalised expressionGene AGene BGene CGene DGene EGene FNormalTumour
Comparing models side by side with the same folds. Illustrative data.

The key papers are Breiman (2001), “Random forests”, Machine Learning, and Friedman (2001), “Greedy function approximation: a gradient boosting machine”, Annals of Statistics. scikit-learn’s HistGradientBoostingClassifier is inspired by LightGBM (Ke et al. 2017, NeurIPS). XGBoost (Chen and Guestrin 2016, KDD) is another widely used library.

When citing, say which implementation and version you used, because their defaults differ. One caution about forests: their built-in feature_importances_ can favour features with many distinct values, as Strobl et al. (2007, BMC Bioinformatics) showed. Permutation importance on held-out data, shown in Tuning, interpreting and reporting, is the safer choice.

Key point

Always include a simple model in a comparison. If logistic regression is as good as a forest, prefer it: it is faster, easier to explain and more likely to hold up at a new site.

A second example, from the output above: gradient boosting has the same mean as logistic regression (0.993) and a smaller spread (± 0.003 against ± 0.007). That difference in spread is not meaningful with five folds. When two models are this close, the choice should rest on other grounds: how clearly you can explain the model, how fast it runs, and how it behaves on data from elsewhere.

Further reading · Module 4Chicco 2017: ten practical tips for machine learning in biology. · All reading for this course

Check your understanding

1. A tree scores 100% on training data and 93% on test data. This shows:

2. How does a random forest make a prediction?

3. Why use the same cv object for every model?

Up next

Lesson 6

Regression: predicting a number

Ask BioTutor

Create a free website with Framer, the website builder loved by startups, designers and agencies.