Decision trees

A tree asks one question at a time, narrowing the data

Income < 45k?25 repaid, 35 defaultedyesPredict: default0 repaid, 19 defaultednoDebt ratio < 0.4?25 repaid, 16 defaultedPredict: repay22 repaid, 1 defaultedPredict: default3 repaid, 15 defaulted204510000.40.8income $kdebt ratioA decision tree asks one yes-or-no question at a time, and each answer narrows the data.Each split is chosen to make the groups below it as pure as possible. On the right the same two questions cut the 60 loans intoboxes. Trees handle mixed data with no scaling, and you can read every decision. A deep tree overfits, so depth is limited ormany trees are combined.

Each split makes the groups below it purer. Read the path, and you have the reason.

Decision trees · Going deeper

How a tree chooses a split: Gini impurity

GroupRepaid / allGini impurityAll loans25 / 600.486Income < 45k0 / 190nearly pureIncome ≥ 45k25 / 410.476still mixed: split again … and debt < 0.422 / 230.083nearly pure … and debt ≥ 0.43 / 180.278mostly defaultedweighted impurity after the first split: 0.325, down from 0.486A tree picks the split that lowers impurity the most.Gini impurity is 1 − p² − (1 − p)², where p is the share in one class: 0 for a pure group, 0.5 for an even mix. The algorithm triesevery feature and threshold and keeps the one with the lowest weighted impurity below it. Entropy and information gain work thesame way. Regression trees use the variance of the target instead.

Pick the split with the lowest weighted impurity.

Random forests

Many different trees vote, and their errors cancel

One new application, seven trees. Each tree was trained on a different random sample of rows and of features.tree 1repaytree 2repaytree 3defaulttree 4repaytree 5defaulttree 6repaytree 7repayvote: 5 repay, 2 default → repay (71%)A random forest trains many different trees and lets them vote.Each tree sees a bootstrap sample of the rows (bagging) and a random subset of features at each split, so the trees make differentmistakes. Averaged, those mistakes largely cancel: the forest overfits far less than any one tree. For a number, the trees’ answersare averaged instead. Robust and hard to get badly wrong, it is a common first serious model.

Bagging: each tree sees different rows and features. The majority wins.

Why forests work · Going deeper

Voting cancels independent errors; shared errors set the floor

Chance the majority is right: each tree right 70% of the time,errors independent1 tree70.0%5 trees83.7%25 trees98.3%101 trees100.0%Binomial: the sum of P(k trees right) for every k above half.Real trees err together: variance of theforest's average, as a share of one tree'sCorrelation between trees, ρ10 trees100 treesFloor0 (independent)10%1%0%0.337%31%30%0.773%70%70%share = ρ + (1 − ρ) ÷ nOut-of-bag: a bootstrap sample of n rows leaves out (1 − 1/n)ⁿ ≈ 36.8%of them, so each tree has unseen rows to be scored on for free.Averaging cancels only the errors that trees do not share, so a forest works to make its trees differ.If trees erred independently, 101 mediocre ones would be nearly always right. They do not: trained on the same table, they sharemistakes, and the correlation ρ sets a floor that no number of trees gets under. Bagging gives each tree different rows; trying onlya random subset of features at each split (√features is the usual default for classification) lowers ρ. More trees never overfit.

Variance of a forest falls to ρσ², so the trees are made to disagree.

Gradient boosting

Each new tree fixes the errors the earlier ones left

0510036xdashed: after round 1solid: after round 8Error left (RMSE) after each round01.1610.8820.7630.7140.6550.6160.5770.5280.49roundGradient boosting adds small trees one at a time, each fitted to the errors left so far.Round 1 fits a one-split tree to the data; every later tree is fitted to what is still wrong, and its answer is added at a learning rateof 0.5. Here eight such trees cut the error from 1.16 to 0.49. XGBoost, LightGBM and CatBoost implement this, and they winmost competitions on tabular data. More rounds can overfit, so the number of rounds is tuned on validation data.

Boosting adds trees in sequence, each fitted to the remaining residuals.

Boosting settings · Going deeper

Small learning rate, many rounds, and early stopping to choose

01002003000.91.11.31.5boosting rounds (trees added)validation error (RMSE)XGBoost parameterDefaultWhat it doeseta (learning_rate)0.3shrinks what each new tree addsmax_depth6deeper trees: more overfittingsubsample1share of rows each tree seescolsample_bytree1share of columns each tree seeslambda, alpha1, 0L2 and L1 penalty on leaf valuesmin_child_weight1smallest leaf allowed (hessian sum)early_stopping_roundsoffstop when validation stops improvingeta 1 (dashed): best at round 18, error 0.994; at round 300, 1.077eta 0.3 (purple): best at round 97, error 0.987; at round 300, 1.015eta 0.1: best at round 291, error 0.989; at round 300, 0.991A lower learning rate needs more rounds; in return the minimum is flatter and stopping late costs less.One-split trees are boosted on 80 generated points and scored on 200 others. At eta 1 the error bottoms out at round 18 and climbs8% by round 300 as later trees fit noise. At 0.3 the best round is 97 and the climb 3%; at 0.1 it is 291 and 0%. The recipe: a loweta, many rounds, and early stopping on a validation set to choose the count. Subsampling rows and columns adds the forest's trick.

Lower eta with more rounds, and stop on the validation error.

k-means clustering

k centres move until each sits in the middle of its group

1. Drop k centres anywhere (here k = 3, badly placed).2. Give each point to its nearest centre.3. Move each centre to the mean of its points.4. Repeat 2 and 3 until nothing moves.dashed: each centre’s path; rings: where it settledk-means moves k centres until each sits at the middle of its own group.You choose k. The elbow method tries several values and picks the one after which adding a centre barely reduces the spread.Results depend on the starting points, so it runs several times. It finds round, similar-sized groups; scale the features first.Uses: customer segments, grouping documents, compressing colours in an image.

Assign each point to the nearest centre, move centres to the mean, repeat.

Choosing k · Going deeper

The elbow shows where extra clusters stop paying

90 points, no labels12345670800kspread inside clusters (inertia)the elbow23456700.20.40.60.8kmean silhouette0.500.620.540.490.410.43Inertia always falls as k grows, so look for the bend, and check it with the silhouette.Inertia is the summed squared distance from each point to its centre: 734 at k = 1, 128 at 3, 60 at 7. It can only go down, so thelowest value is no guide; the elbow is where the drop slows. The silhouette compares each point's distance to its own cluster with thenearest other one (1 = tight and separate, 0 = overlapping) and has a true peak, here at k = 3. Generated data, best of 12 starts for each k.

Inertia always falls with k; the silhouette score peaks at a good k.

Choosing an algorithm

Start from the task; for tables, try boosted trees first

TaskTypical algorithmsSageMaker AI built-inPredict a numberlinear regression, gradient boostingXGBoost, Linear LearnerPredict a classlogistic regression, random forest, boostingXGBoost, Linear Learner, k-NNGroup without labelsk-means, hierarchical clusteringk-meansFind the odd one outisolation forest, Random Cut ForestRandom Cut ForestFewer columnsPCAPCARecommendcollaborative filtering, factorisationFactorization MachinesForecast a seriesARIMA, DeepAR, gradient boostingDeepARImages, text, audioneural networks (lesson 6)Object Detection, BlazingTextFor tables of data, start with gradient-boosted trees and a linear model, and compare.Neural networks win on images, sound and text; on tabular data boosted trees usually match or beat them at a fraction of the cost.Choose by the task, the amount of data, how much the model must be explained, and the cost to train and serve. Explainability candecide it: a lender may have to state why an application was refused.

Match the task to a family, then compare against a simple baseline.

Lesson complete

You finished “Trees, forests and clustering”

Nicely done.

Open in a new tab