ENID
Lensa ML

Decision Trees & Splitting

Step 1 of 6: What is a Decision Tree?

Nodes, branches & leaves

-3-2-10123-3-2-10123
Depth
1
Regions
2
Accuracy
67%

A decision tree splits data by asking yes/no questions. At depth 1 it makes one axis-aligned cut, and each colored region predicts one class. One cut can't separate interleaved clusters.

Drag max depth from 1 to 4 and count the regions. A tree of depth d has at most 2^d leaves, so depth 4 allows up to 16, but this tree stops at 8 because some nodes are already pure and need no further split. Each leaf is one rectangle in the data space. Predicting means walking from the root to a leaf, which takes at most d comparisons, so trees are very fast at inference. The path also explains the prediction: it is the list of questions the input answered on the way down.

Step 2 of 6: Splitting Criteria

Gini impurity & information gain

x = 0.0L: 15r + 0gR: 0r + 15g
Gini left
0.000
Gini right
0.000
Weighted Gini
0.000
Info gain
1.000

Strong split: the line lands between the clusters. The left side is mostly red (100% pure) and the right mostly green (100% pure). A weighted Gini of 0.00 means the children are much purer than the parent.

Drag the split threshold x, and click any card to see its formula. Gini impurity is 1 − Σ p_i², and entropy is −Σ p_i log₂ p_i. For two classes at 50/50, Gini is 0.5 and entropy is 1 bit, the parent's value here, so information gain reaches its maximum of 1.0 for a perfect split. Any threshold in the gap between x ≈ −0.9 and x ≈ 0.8 achieves it. CART, the algorithm behind scikit-learn's trees, uses Gini by default, while ID3 and C4.5 use information gain. The two usually choose the same split.

Step 3 of 6: Growing the Tree

Recursive partitioning

Tree structurey≤0.1Data space-3-2-10123-3-2-10123
Depth
1
Leaves
2
Accuracy
67%
Gini reduction
0.056

With one split, the root asks the single best question it found. Its two children are leaves, and each still mixes both classes.

Raise max depth one level at a time and follow the tree diagram on the left alongside the data space on the right. The algorithm is greedy: at each node it tries every feature and every midpoint between sorted values, keeps the best split, and never revisits it. That makes training fast, but the tree it builds is not guaranteed to be the best possible tree. This tree chooses splits by information gain, and the Gini reduction card measures the result. Real implementations also stop on rules such as a minimum number of samples per leaf.

Step 4 of 6: Overfitting a Tree

When trees memorize noise

traintest
Depth
2
Train acc
79%
Test acc
92%
Gap
-13%

Shallow tree: train 79%, test 92%. One boundary ignores the 8 mislabeled training points, so test beats train.

Drag max depth from 1 to 8 and watch the train and test accuracy cards move apart. The training set has 38 points, 8 of them placed deep in the other class's territory as label noise, and the test set (diamonds) has 26 clean points. Each extra level lets the tree wrap more of the noisy points in small regions of their own. Deep trees have low bias and high variance: a small change in the training data can produce a very different tree, which is the weakness that random forests were designed to fix.

Step 5 of 6: Pruning

Simplifying for generalization

traintest
Alpha
0.000
Leaves
18/18
Train acc
92%
Test acc
77%

No pruning: this is the depth-8 overfit tree from step 4 with 18 leaves. Train 92% but test only 77%. Increase alpha to start removing noise-fitting branches.

Drag alpha up from 0 on its log scale and watch the leaf count fall. CART's cost-complexity pruning minimizes R(T) + α·|T|, where R(T) is the tree's training error and |T| is its number of leaves, so every leaf has to earn its place. This demo runs CART's weakest-link procedure: it keeps collapsing the subtree that adds the least training error per leaf removed, until that cost exceeds alpha. At alpha = 0.01, the tree drops from 18 leaves to 6 and test accuracy rises from 77% to 85%. Past about 0.013 only the root split remains, with 79% train and 92% test accuracy. In practice alpha is chosen by cross-validation, for example through scikit-learn's ccp_alpha parameter.

Step 6 of 6: Decision Boundaries

Axis-aligned regions

traintest
Depth
3
Regions
7
Train acc
97%
Test acc
90%

More depth creates finer axis-aligned rectangles. Unlike an SVM or a neural network, a tree cannot draw a diagonal or curved boundary, so it needs many splits to approximate one.

Change max depth and look at the shape of the colored grid. Every boundary segment is horizontal or vertical because each split tests a single feature. A diagonal boundary such as x = y needs a staircase of many splits, while logistic regression or a linear SVM draws it with one line. Oblique trees, which split on weighted combinations of features, avoid the staircase but cost more to train. Ensembles also smooth it out: averaging hundreds of trees in a random forest gives a boundary far less jagged than any single tree's.

What is a decision tree?

A decision tree is a model that predicts by asking a sequence of yes/no questions about the input, such as "is x ≤ 0.4?". Each internal node holds one question, each branch is an answer, and each leaf holds a prediction: the majority class for classification or the mean target for regression. Training grows the tree greedily, picking at each node the question that best separates the training labels.

Trees handle numeric and categorical features, need no feature scaling, and can be read as a set of if-then rules, which makes them popular in credit scoring, medical triage, and other settings where a decision has to be explained. A single deep tree overfits easily, so trees are most often used as building blocks. Random forests average hundreds of them, and gradient boosting libraries such as XGBoost and LightGBM add them up one at a time. Those ensembles remain among the strongest models for tabular data.

Key ideas

  • A decision tree predicts by routing an input through a series of feature-threshold questions to a leaf.
  • Each split is chosen greedily to give the largest drop in impurity, measured by Gini or entropy.
  • Every split tests one feature, so the decision regions are axis-aligned rectangles.
  • Deeper trees fit the training data more closely and memorize noise more easily.
  • Pruning and limits on depth or leaf size trade some training accuracy for better test accuracy.
  • Trees need no feature scaling and are the base learners in random forests and gradient boosting.

Common questions

Can decision trees be used for regression?

Yes. A regression tree predicts the mean target value of the training points in each leaf and picks the splits that most reduce squared error. Its prediction is a step function that is constant within each region. CART handles classification and regression with the same algorithm.

Do decision trees need feature scaling?

No. A split compares one feature to a threshold, so any monotonic transformation of that feature, such as standardizing it or taking its log, leaves the set of possible splits unchanged. Distance-based methods such as k-nearest neighbors and SVMs are different and need scaled features.

How do decision trees handle categorical features?

A tree can split a categorical feature by sending some categories left and the rest right. Many libraries expect numeric input, so categories are often one-hot or ordinal encoded first. LightGBM and CatBoost can split on categorical features directly.

How is feature importance computed for a decision tree?

The usual measure adds up the impurity reduction from every split that uses a feature, weighted by the number of samples reaching that split, and normalizes the totals. It is cheap to compute but tends to favor features with many distinct values. Permutation importance, which measures how much accuracy drops when one feature's values are shuffled, is a common cross-check.

Related explainers

References

  1. James, Witten, Hastie & Tibshirani, "An Introduction to Statistical Learning", chapter 8: Tree-Based Methods
  2. Quinlan (1986), "Induction of Decision Trees", Machine Learning
  3. Breiman, Friedman, Olshen & Stone (1984), "Classification and Regression Trees"

Last updated