AI · 07 Artificial Intelligence

Decision Trees, Random Forests & Boosting

Decision Trees, Random Forests & Boosting

A decision tree scores 100% on its training rows and 90.2% on new ones: it memorized. A hundred trees voting score 94.4%. We grow trees on a real table, then work through Gini impurity by hand, depth and pruning, bagging and random forests, boosting round by round, why tree models still lead on tabular data (and when they don't), feature importance, and a leak through row IDs that scores a perfect, useless 100%. Every number on screen is real output from code you can run.

Chapters

Cheat sheet

Code

Try it yourself (pip install scikit-learn)
from sklearn.datasets import load_breast_cancer
from sklearn.ensemble import HistGradientBoostingClassifier, RandomForestClassifier
from sklearn.model_selection import cross_val_score, train_test_split
from sklearn.tree import DecisionTreeClassifier

X, y = load_breast_cancer(return_X_y=True) # label: 0 = malignant, 1 = benign
print(f"rows: {len(y)}, columns: {X.shape[1]}, malignant: {sum(y == 0)}, benign: {sum(y == 1)}")
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=0, stratify=y) # 25% held out
print(f"train: {len(y_train)} rows, test: {len(y_test)} rows")

models = {
"one decision tree": DecisionTreeClassifier(random_state=0),
"random forest, 100 trees": RandomForestClassifier(random_state=0),
"gradient boosting, 100 rounds": HistGradientBoostingClassifier(random_state=0),
}
print("model".ljust(30), " train test 5-fold CV")
for name, model in models.items():
model.fit(X_train, y_train)
cv = cross_val_score(model, X, y, cv=5).mean()
print(name.ljust(30), f"{model.score(X_train, y_train):6.1%} {model.score(X_test, y_test):6.1%} {cv:9.1%}")

tree = models["one decision tree"]
print(f"the single tree: depth {tree.get_depth()}, {tree.get_n_leaves()} leaves")

What we got (test / 5-fold CV): one tree 90.2% / 91.7%, random forest 94.4% / 96.3%, gradient boosting 93.7% / 96.5%. All three score about 100% on their training rows, so ignore that column.

Sources

Transcript

So far, our classifiers have drawn one straight cut through the data. Today's model asks questions instead: yes or no, one after another, like a flowchart. Here's one, a decision tree trained on a real medical table. On its own training rows, it scores one hundred percent. On rows it has never seen, ninety point two.

It memorized. Now grow a hundred trees, each a little different, and let them vote: ninety-four point four, on the same rows. Which raises a classic interview question: why does a random forest beat a single decision tree? Let's find out.

This is Just Known. From unknown, to known. Episode seven: decision trees, random forests, and boosting. Our table is a classic benchmark bundled with scikit-learn: the Breast Cancer Wisconsin dataset. Five hundred sixty-nine rows, each a sample of cells, with thirty columns measured from a microscope image: things like radius, texture and smoothness, each as an average, a spread, and a worst case.

Each row is labeled malignant or benign. It's a teaching dataset, not a diagnostic tool. In episode two, a tiny tree sorted Iris flowers. Now let's watch one find its own questions. We keep a quarter of the rows for testing: four hundred twenty-six to train on, a hundred forty-three to test.

To see what a tree does, let's give it just two columns we can draw: mean radius across, and mean texture up. A tree starts with one question, like: is the mean radius at most fifteen? To find the best one, it tries every column and every possible cut, and scores how cleanly each one separates the two classes. The winner: mean radius, at most fifteen point oh five. On the yes side, two hundred ninety-five rows, eighty-seven and a half percent benign.

On the no side, a hundred thirty-one rows, ninety-three percent malignant. That score is called impurity, and the classic one is Gini impurity: the chance you'd mislabel a random row from a group, if you guessed in the group's own proportions. A pure group scores zero. A fifty-fifty mix scores one half. Before the split, our training rows score point four six eight.

After it, the yes side scores point two one nine, and the no side point one two eight. Weighted by size, that averages point one nine one. The question with the biggest drop wins. The other popular score is entropy; its drop is called information gain, and here it picks the same question. Gini comes from CART, in nineteen eighty-four; entropy, from Ross Quinlan's ID3, in his nineteen eighty-six paper.

Then the tree repeats the search inside each side: the radius again on one, the texture on the other. Every cut is straight, across or up, so the tree carves the chart into boxes. The final boxes are the leaves. Each leaf predicts its majority class, so a new row follows the questions down to a leaf. And because a tree only compares values with cuts, you never need to rescale the columns.

So what can go wrong? Left alone, a tree keeps asking until every leaf is pure. At depth one: eighty-nine percent on training rows, eighty-eight on test rows. Grown all the way, it's twelve questions deep, with fifty-one leaves, and twenty of them hold a single training row. Training: one hundred percent.

Test: eighty-one point eight. That's overfitting, from episode five. On all thirty columns, it's milder: one hundred, against ninety point two. The fix: stop the tree early, or cut it back. Cap the depth, require more rows per leaf, or prune the weakest branches.

Let cross-validation choose how hard, and our tree shrinks to two leaves, scoring eighty-eight point one on the test. Even a pruned tree has a deeper problem: it's unstable. Train it on slightly different rows, and you can get a different tree, starting with a different first question. Leo Breiman turned that into a strength. In nineteen ninety-six, he proposed bagging: train many trees, each on a bootstrap sample, a random draw of the rows with replacement.

Each tree sees about two thirds of the rows, some twice. Across a hundred such samples, our trees opened with five different columns. Then they vote. In two thousand one, Breiman added a twist and called it a random forest: at every split, a tree may only look at a random handful of columns. By default, scikit-learn tries the square root of the column count, five of our thirty.

That forces the trees to differ. Here are the forest's hundred trees, tested alone. The worst scores eighty-six percent, the best ninety-five point eight, the average ninety point eight. Together, they score ninety-four point four, better than ninety-three of their own trees. Their mistakes fall on different rows: seventy-two test rows fool some of the trees, but never most of them, so the vote gets them right.

And no, forests aren't immune to overfitting: this one scores ninety-nine point eight percent on its own training rows. Boosting works the other way: one small tree at a time, each fixing what the others got wrong. It starts with one guess for every row: the base rate, sixty-two point seven percent benign. Then it fits a small tree to what's left, the gap between each row's label and the prediction so far, and adds a tenth of it. That tenth is the learning rate.

The next tree works on what's left. One malignant row starts at sixty-three percent benign. After three trees, it's below one half. After fifty, under one percent. The idea took off with AdaBoost, in the mid-nineties.

Jerome Friedman's gradient boosting, in two thousand one, made it general: each new tree follows the slope of the loss, like episode three's walk downhill. For the first two rounds, the test score doesn't move: the nudges are still too small, so every row is called benign. By round three, ninety point two percent. By round ten, it's ninety-three point seven, and then it only wobbles by a few rows. Meanwhile, the training score hits one hundred percent by round fifty.

So boosting can memorize too. The usual guard is early stopping: stop adding trees when a held-out validation score stops improving. Two libraries made gradient boosting famous. XGBoost: its twenty sixteen paper counted it in seventeen of the twenty-nine winning solutions on Kaggle's blog in twenty fifteen. And LightGBM, published in twenty seventeen, which buckets values into histograms to train much faster.

The one we're using, histogram gradient boosting in scikit-learn, is inspired by it. A twenty twenty-two benchmark of forty-five medium-sized tables found tree-based models still ahead of deep learning: tables tend to have irregular patterns and useless columns, and trees cope with both better. But that's a benchmark finding, not a law. On our small, clean table, a plain logistic regression from episode four averages ninety-seven point seven percent over fifty splits, ahead of both. Always try the simple baseline.

Trees also show which columns they rely on. Impurity importance adds up how much purity each column bought, across the forest. The top columns all describe size and shape: worst perimeter, worst radius, worst concave points. But that's measured on training data, and it favors columns with many unique values. A fairer check is permutation importance: shuffle one column in the test rows, and see how far the score drops.

Shuffle worst perimeter, and accuracy drops by just one point four percentage points. Why so little? Radius, perimeter and area all measure size, so the forest leans on another one. And importance tells you what the model uses, not what causes what. Here's a sneakier way to fool yourself.

Say the file was saved sorted by diagnosis, and someone added a row number column. We let a tree use it. Its only question: is the row number at most two hundred eleven point five? On a random test split, that's one hundred percent. Perfect, and useless.

Give the test rows the numbers new rows would get, bigger than any it trained on, and it calls every one benign: sixty-two point nine percent, catching zero of the fifty-three malignant rows. Timestamps leak the same way, if the positive cases were all logged in one batch. So drop row numbers and other identifiers, split by time when time matters, and if a column looks too good to be true, it probably is. You can run this yourself, in about twenty lines of scikit-learn. The code is in the description.

Hold back a quarter of the rows, and fit three default models: one decision tree, a forest of a hundred trees, and a hundred rounds of boosting. On the training rows, all three score about a hundred percent, so ignore that column. On the test rows: ninety point two for the tree, ninety-four point four for the forest, and ninety-three point seven for boosting. One split is noisy, so it also cross-validates over five: ninety-one point seven, ninety-six point three, and ninety-six point five. Both ensembles beat the single tree.

Interview corner. Why does a random forest beat a single decision tree? And how is boosting different? Pause here, and try answering in thirty seconds.

Here's a strong answer. A single deep tree has low bias but high variance: it memorizes easily, and small changes in the data change the whole tree. A random forest trains many deep trees, each on a bootstrap sample of the rows, with a random subset of columns at each split, and averages their votes. Their errors are only partly correlated, so averaging cancels much of the variance. Boosting trains small trees one after another, each fitted to the errors left so far, technically the gradient of the loss, and adds each with a small learning rate.

That mainly reduces bias. It often scores a little higher, but needs tuning and early stopping. To stand out: more trees don't make a forest overfit, though its deep trees still can, and on tabular data, gradient-boosted trees are often the model to beat. Let's recap. A decision tree asks yes-or-no questions, each chosen to make its groups purer, and grown all the way, it memorizes.

A random forest averages many varied trees, so their mistakes cancel. Boosting adds small trees one at a time, each fixing what's left. And beware columns that are too good to be true. Every model so far has learned from labels: someone gave it the right answers. But what if nobody did?

That's episode eight: learning without labels. This is Just Known. From unknown, to known.

Note: the Breast Cancer Wisconsin data is a classic teaching benchmark, not a diagnostic tool. Tree shapes in the forest pictures are illustrative; the scores are real.
Narration voice generated with Google Gemini text-to-speech.