Decision tree visualizer

Each dataset has 80 training points of two classes, A and B, with about one label in twelve flipped at random as noise. The tree is grown on those points, and the shaded regions show which class it would predict anywhere in the square. A separate set of 200 new points from the same source measures how well the tree generalizes. Click the plot to add training points of the chosen class.

• On Diagonal, raise the maximum depth step by step. Training accuracy climbs to 100%, while accuracy on new data peaks and then falls: the deep tree is drawing boxes around noise.
• Set the smallest leaf to 5 or 10 at full depth. The tree can no longer isolate single points, and accuracy on new data recovers.
• Try Checkerboard at depth 1. No single cut helps, because each half is still half A and half B; the tree needs two levels before it can see the pattern.
• Add a single point of the wrong class in the middle of a region and watch the deep tree carve out a box for it.

The tree-growing code is checked against scikit-learn's DecisionTreeClassifier: on every dataset, criterion, leaf size and depth tested, it picks the same root split and reaches the same training accuracy.

A decision tree is a model that makes a prediction by following a path of questions. Each internal node tests one feature against a threshold, such as "is income at most 40,000?", and sends the item left or right; each leaf holds a prediction, here the majority class of the training points that reached it. Reading the path from root to leaf gives a plain explanation of any single prediction.

Trees are learned from labelled examples. They handle numeric and categorical features without scaling, capture interactions between features naturally, and are fast to evaluate. On their own they are unstable and prone to overfitting, which is why the strongest tree-based methods combine many of them.

Finding the best possible tree is computationally hard, so tree learners grow one greedily, top down. The CART method, used here and in scikit-learn, works like this at each node:

1. For each feature, sort the node's points by that feature and consider a threshold halfway between each pair of neighbouring distinct values.
2. For each candidate, split the points into "at or below" and "above", and compute the impurity of each side, weighted by its size.
3. Keep the split with the lowest weighted impurity; the drop from the node's own impurity is the split's gain.
4. Repeat on each side, until a stopping rule applies: the maximum depth is reached, the node is pure, or a split would leave a side with fewer points than the minimum leaf size.

Because each choice is made locally, the tree can miss splits that only pay off one level later, which is exactly what the checkerboard data shows at depth 1.

An impurity measure scores how mixed a node is: zero when every point has the same class, highest when the classes are evenly mixed. With class proportions p_i:

Gini = 1 − Σ p_i² Entropy = − Σ p_i log₂ p_i

Gini is the probability that two points drawn at random, with replacement, have different classes; entropy is the average number of bits needed to say which class a point has, and the reduction in entropy from a split is called information gain. For a node with 30 points of one class and 10 of the other, Gini is 0.375 and entropy 0.811 bits. The two usually lead to the same or very similar trees; switch between them in the simulator to compare.

A tree with no limits keeps splitting until every leaf is pure, which on noisy data means building small regions around individual mislabelled points. Training accuracy reaches 100%, but those regions are wrong for new data. The table shows accuracy on 200 new points for the page's four datasets at different depths, averaged over 20 random samples of each:

Each split tests a single feature, so every boundary a tree draws is parallel to an axis, and its regions are boxes. Data whose true boundary is along an axis is easy: the two-cluster data reaches 80% on new points at depth 2, on average. A diagonal boundary has to be approximated by a staircase of small boxes, which needs many leaves and many points; a circle needs even more. Methods with oblique splits exist, but most libraries keep axis-aligned splits because they are fast to search and easy to read, and rely on ensembles to smooth the staircase.

Single trees change a lot when the training data changes slightly. Ensembles turn that weakness into a strength:

• Random forests (Leo Breiman, 2001) train many deep trees, each on a bootstrap resample of the data and considering only a random subset of features at each split, then take a majority vote. Averaging trees whose errors differ cancels much of their variance.
• Gradient boosting (Jerome Friedman, 2001) adds small trees one at a time, each fitted to the errors of the ensemble so far. Implementations such as XGBoost (2016), LightGBM (2017) and CatBoost are among the most widely used methods for tabular data.

Leo Breiman, Jerome Friedman, Richard Olshen and Charles Stone published Classification and Regression Trees in 1984, introducing CART with Gini impurity, binary splits and cost-complexity pruning. Independently, J. Ross Quinlan developed ID3, published in 1986 in "Induction of decision trees", which used information gain, and its successor C4.5 in 1993. Breiman's random forests followed in 2001, the same year as Friedman's gradient boosting machine.