How a tree asks questions, why it memorizes, and how averaging hundreds of decorrelated trees turns a fragile model into the most reliable workhorse in tabular ML
By the end of tonight you'll have both the concept and the working code — every objective maps to a cell you run yourself.
Gini impurity in plain English, greedy binary splits, and plot_tree — a model you can print on one page and hand to a manager.
An unlimited tree reaches 99% training accuracy by carving a leaf for every quirky booking. max_depth and min_samples_leaf are its regularization knobs.
Bootstrap rows, sample features at every split, average the votes. Decorrelated trees cancel each other's errors — variance reduction you can watch happen.
Impurity importance is biased toward high-cardinality columns; permutation importance on held-out data is not. Partial dependence shows the shape of the effect.
A business question, a dataset, a model — and the judgment to evaluate it.
Threshold choices from HW3 Part 1 — the range was 0.18 to 0.42, and the best memo explained why — and the residual plot that caught the most expensive houses in Part 2. Then the competition dataset: 83,573 hotel reservations from a city and a resort hotel in Portugal, 37% canceled, 32 columns — two of which are leaks.
'Is lead_time > 90 days?' 'Is deposit_type non-refundable?' A tree is a flowchart learned from data: at each node it picks the question that most reduces impurity. Gini = probability that two random guests from this node disagree on cancellation.
Depth 1 → 3 → 6 → unlimited. Training accuracy climbs to 99%; test accuracy peaks around depth 8–10 and then falls. The tree has memorized the training bookings. A validation curve over max_depth makes the sweet spot visible.
Stretch, coffee, compare competition baselines.
Bagging: fit 500 trees, each on a bootstrap sample, average their votes — variance drops. Random forest adds the twist: at every split, only a random subset of features is eligible, so the trees disagree more and the average improves more. Out-of-bag score: a free validation set built from the rows each tree never saw.
feature_importances_ (impurity) vs. permutation_importance on the test set — and the zero-signal trap: a pure-noise column and a unique booking-ID column both land in the top third by impurity — ahead of real signals like previous cancellations — and dead last by permutation. Then PartialDependenceDisplay: how cancellation probability actually moves with lead time.
Every team should have a leak-free pipeline and a forest submission by tonight. Next week, gradient boosting — the model that will probably win — and the tabular foundation models that might beat it.
Gini impurity and greedy splits, one question at a time.
Bootstrap, feature sampling, out-of-bag: why hundreds of noisy trees beat one careful one.
Notebooks, readings, explorers, and the stories behind the methods.
plot_tree, the depth validation curve, bagging vs. random forest, out-of-bag score, impurity vs. permutation importance (with the ID-column trap), and partial dependence plots.
Open in ColabAntonio, de Almeida & Nunes (2019). The course file holds the competition's 83,573 training bookings, 32 columns, 37% canceled — hosted in the repo for no-login loading. The 35,817 hidden test bookings exist only on Kaggle, so anything you learn from the course file is fair game.
View the dataWatch a tree grow split by split on a live dataset, with impurity shown at every node.
Open the explainerBootstrap samples, feature subsets, and the vote — animated. Why hundreds of noisy trees beat one careful one.
Open the explainerThe most beautiful explanation of a decision tree ever made: San Francisco vs. New York homes, split by split, as you scroll. Part 2 covers bias and variance. Ten minutes; show it to someone who has never heard of ML.
Scroll the story8.1 covers trees for regression and classification with the pruning story; 8.2 covers bagging, random forests, and boosting. Read 8.1–8.2.2 tonight, 8.2.3 next week.
Read Chapter 8 (free PDF)Why impurity importance misleads and how permutation importance fixes it — with the exact random-column example we reproduce in class.
Open the guideBernardi, Mavridis & Estevez (KDD 2019): what Booking.com learned deploying 150 production models, including that offline gains often don't translate to business value. Required reading for anyone who thinks the leaderboard is the goal.
Read the paper pageSearch the index for 'Decision and Classification Trees' and 'Random Forests Part 1'. The Gini walk-through is the clearest on the internet. Also embedded on this page.
Watch on YouTubeProf. Arslan's earlier notebook: a tree on synthetic blobs, the overfitting picture, bagging with 100 trees, and random-forest regression. The intuition, at a gentler pace. Hosted in the course repo — opens in Colab with one click.
Open in ColabDecision trees on the breast-cancer data, feature importances, random forests, and the original GradientBoostingClassifier — with the overfitting pictures.
Open in ColabOpen the notebook and build it with us.
Predict which bookings will cancel. Fit a single tree at several depths to watch overfitting, then a random forest, then ask the forest which features matter — twice, and notice the two answers disagree.
reservation_status, reservation_status_date, and (defensibly) assigned_room_type. Encode categoricals with OrdinalEncoder — trees don't need one-hot.
DecisionTreeClassifier at max_depth 2, 4, 6, 8, 12, None. Train vs. test AUC. Find the peak and the gap.
RandomForestClassifier(n_estimators=300, min_samples_leaf=5, oob_score=True, n_jobs=-1). Compare oob_score_ with the test score.
feature_importances_ vs. permutation_importance on the test set. Add a random noise column first and watch where each method ranks it.
import pandas as pd, numpy as np
from sklearn.model_selection import train_test_split
from sklearn.ensemble import RandomForestClassifier
from sklearn.inspection import permutation_importance
from sklearn.metrics import roc_auc_score
url = 'https://raw.githubusercontent.com/harslan/isom-835/master/public/data/hotel_bookings.csv'
df = pd.read_csv(url).sample(30_000, random_state=835) # subsample for speed in class
leaks = ['reservation_status', 'reservation_status_date', 'assigned_room_type']
X = df.drop(columns=['is_canceled'] + leaks)
X = X.apply(lambda c: c.astype('category').cat.codes if c.dtype == object else c).fillna(-1)
X['noise'] = np.random.default_rng(835).normal(size=len(X)) # a column with zero signal
y = df['is_canceled']
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.2, stratify=y, random_state=835)
rf = RandomForestClassifier(n_estimators=300, min_samples_leaf=5, oob_score=True, n_jobs=-1, random_state=835)
rf.fit(X_tr, y_tr)
print(f'OOB AUC-ish (accuracy): {rf.oob_score_:.3f} test AUC: {roc_auc_score(y_te, rf.predict_proba(X_te)[:, 1]):.3f}')
imp = pd.DataFrame({'impurity': rf.feature_importances_}, index=X.columns)
imp['permutation'] = permutation_importance(rf, X_te, y_te, scoring='roc_auc', n_repeats=5, random_state=835, n_jobs=-1).importances_mean
print(imp.sort_values('permutation', ascending=False).head(8).round(4))
print('noise column rank by impurity:', int((imp['impurity'] > imp.loc['noise', 'impurity']).sum()) + 1) The forest reaches an AUC around 0.94 on a 30k-row slice with no tuning and no scaling — that is why it is the first serious model most practitioners reach for. But look at the importance table: deposit_type, lead_time, and country lead by permutation, while the pure-noise column and a unique booking-ID column both sit in the top third by impurity. Impurity importance rewards columns that offer many split points, not columns that predict. If you report feature importance to a manager, report the permutation version.
A decision tree is a flowchart learned greedily from data: interpretable, scale-free, and high-variance. Depth and min_samples_leaf are its brakes; a single tree rarely ships.
A random forest is variance reduction by averaging decorrelated trees — bootstrap rows, sample features at every split. Hard to overfit by adding trees; the out-of-bag score is a free validation set.
Impurity importance lies about high-cardinality columns; permutation importance on held-out data does not. Partial dependence shows the shape of an effect, which is what a manager actually asks for.
Complete these before next Monday — they are the practice that makes the next session land.
Exam-style questions for the ideas in this session — Trees, Forests & Boosting. Every wrong answer names the misconception behind it.
Fit the residuals, again and again: HistGradientBoosting, LightGBM, XGBoost, early stopping — and the 2025–26 challengers, TabPFN and TabICL, that beat tuned boosting on small data with zero tuning. Plus the competition reveal.