Decision Trees and Gini Impurity: How CART Carves Up Data

Splitting the data one axis-aligned cut at a time

A CART decision tree (Classification And Regression Trees, Breiman et al. 1984) classifies points by asking a sequence of yes/no questions, each of the form "is feature x₁ less than some threshold t?" Every question is a single axis-aligned cut through the data, and the tree that results is just a nested sequence of these cuts, visualised as rectangles carving up the input space. On a genuinely nonlinear boundary like XOR, no single cut separates the classes, but two cuts in sequence, one per axis, isolate the four quadrants perfectly, which is exactly what you can watch happen level by level in the auto-grow animation.

Choosing the best split with Gini impurity

At each node, CART tries every feature and every candidate threshold and picks whichever split reduces Gini impurity the most. Gini impurity measures how mixed the classes are in a node:

Gini(node) = 1 − Σ p_k²

p_k   fraction of samples in the node belonging to class k

Gini = 0        node is pure, all one class
Gini = 0.5      node is maximally mixed (2-class, 50/50)

split_gain = Gini(parent) − ( n_left/n · Gini(left) + n_right/n · Gini(right) )

The algorithm greedily picks the split with the largest split_gain at every node, recursing independently on the left and right children. This is a greedy, locally-optimal search: each split is the best available right now, with no lookahead for splits that might pay off two levels deeper, which is why decision trees can be trained in roughly O(n·d·log n) time (n samples, d features) but are not guaranteed to find the globally smallest tree that fits the data.

Why deep trees memorise instead of learning

Left unchecked, CART keeps splitting until every leaf is pure or has one sample, which means it can carve an arbitrarily convoluted boundary around individual noisy points — textbook overfitting. On the Moons or Blobs datasets in this simulation you can watch this happen directly: early levels capture the real cluster structure, but by depth 6–8 the tree starts drawing thin fingers around individual outlier points, boundaries that will not generalise to new data. The usual remedies are limiting max depth, requiring a minimum number of samples per leaf, or growing the full tree and then pruning back branches that don't improve validation performance.

Gini impurity versus information gain

CART's Gini impurity and the alternative entropy/information-gain criterion (used by ID3 and C4.5) almost always pick very similar splits in practice; both are concave functions of the class proportions that are zero for a pure node and maximal at an even split. Gini is marginally cheaper to compute (no logarithm) and is the default in scikit-learn's implementation, which is one reason it has become the more common choice, though the resulting trees rarely differ meaningfully.

From one tree to a forest

A single tree is high-variance: retrain it on a slightly different sample and the early splits, which every later split depends on, can change completely. Random forests and gradient-boosted trees both build on exactly the mechanism shown here — many CART trees, each trained on a bootstrap resample and a random feature subset (forests) or each correcting the previous tree's residual errors (boosting) — and average or sum their predictions to trade the single tree's overfitting tendency for much better generalisation, at the cost of losing the single tree's easy interpretability.

Frequently asked questions

Try it live

Everything above runs in your browser — open Decision Tree Live and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.