Decision Tree Builder

About

A decision tree classifies by asking a sequence of yes/no questions about the features, such as "is the fruit narrower than 6.4 cm?". Each answer sends the example down one branch until it reaches a leaf, which predicts the most common class among the training examples that ended up there.

In this lab you grow the tree yourself. Select a leaf, choose a feature and slide the threshold, and watch the scatter plot split into two boxes while the inspector reports how much purer the two halves are. Or press Best split and let the algorithm pick the split with the largest information gain, exactly as CART does.

Every box in the plot is a leaf of the tree. That is the whole secret of decision trees: they carve the feature space into axis-aligned rectangles and assign each rectangle a class.

A good first session

1. On the fruit data, try a few splits by hand. Can you beat the gain that Best split finds for the root?
2. Press Grow fully with max depth 12 and look at the train and test accuracy. Then look at the accuracy-by-depth chart.
3. Drag the pruning strength up until test accuracy stops improving, and apply it.
4. Switch to Loans and notice the staircase a tree needs to follow a diagonal boundary.

How CART works

CART, short for Classification And Regression Trees, was introduced by Breiman, Friedman, Olshen and Stone in 1984 and is still the algorithm behind scikit-learn's DecisionTreeClassifier. It grows the tree greedily, one split at a time.

1. Measure impurity

Impurity scores how mixed a node is. It is zero when every example has the same class and largest when the classes are evenly mixed.

Gini impurity and entropy for a node where p_k is the share of class k.

Worked example: a node with 6 apples and 2 lemons has p = (0.75, 0.25). Gini = 1 - 0.5625 - 0.0625 = 0.375. Entropy = -(0.75 log₂ 0.75 + 0.25 log₂ 0.25) ≈ 0.811 bits. Gini tops out at 0.5 for two classes and 0.667 for three; entropy at 1 and 1.585 bits. The two usually pick the same or very similar splits.

2. Score every candidate split

For each feature, sort the node's examples by that feature and consider a threshold halfway between each pair of neighbouring distinct values. A split's quality is the drop in impurity from parent to children, with each child weighted by its share of the examples. With entropy this drop is the classic information gain.

Gain of splitting node P into left L and right R, where n counts examples.

The small chart in the inspector plots this gain for every threshold of the selected feature. The best split is the highest point across both features' curves.

3. Recurse, then stop

Split the children the same way, and keep going until a node is pure, reaches the maximum depth, or cannot be split without leaving fewer than the minimum samples in a leaf. Greedy choices are not globally optimal (finding the optimal tree is NP-hard), but they are fast and work well in practice.

Overfitting and pruning

Grown to full depth, a tree can isolate every training point in its own box and reach 100% training accuracy, noise and all. Those tiny boxes around mislabelled points are memorisation, and they hurt accuracy on new data. The accuracy-by-depth chart shows the signature: training accuracy climbs steadily while test accuracy peaks early and then flattens or falls.

Pre-pruning: stop early

Limits such as maximum depth and minimum samples per leaf stop growth before it memorises. They are simple, but they can stop too soon: a split that looks useless alone can enable very useful splits below it. XOR-like patterns are the classic case.

Post-pruning: grow, then cut back

CART's own answer is minimal cost-complexity pruning. Grow the full tree, then for a penalty α find the subtree that minimises training error plus α times the number of leaves. Each branch survives only if it removes more error than it costs in leaves. Sweeping α from 0 upwards gives a nested sequence of ever-smaller trees; in practice α is chosen by cross-validation. The pruning slider in this lab runs exactly this computation and previews which branches would go.

Cost-complexity criterion. R(T) is the training misclassification rate, |T| the number of leaves.

Trees in practice

A single tree is easy to explain but unstable: move a few training points and the root split can change, reshaping everything below it. The most successful methods keep the tree as a building block and combine hundreds of them.

On tabular data with meaningful columns, tree ensembles remain very hard to beat. A NeurIPS 2022 benchmark by Grinsztajn, Oyallon and Varoquaux found that tree-based models still outperformed deep networks on typical medium-sized tabular datasets, partly because trees cope well with irregular functions and uninformative features.

Things trees do well, and less well

• No feature scaling needed: only the order of values matters to a threshold.
• Mixed feature types and interactions are handled naturally by nested questions.
• Boundaries are axis-aligned, so smooth or diagonal patterns need many splits.
• They cannot extrapolate: outside the training range a leaf just repeats its value.