Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 111 ยท Trees and Ensembles

Decision Trees

Learn how decision trees split data using Gini impurity and entropy, compute information gain by hand, fit DecisionTreeClassifier, and read the tree as rules.

A decision tree predicts by asking a chain of yes/no questions about the features: "Is petal width at most 0.8? If yes, setosa. If no, is it at most 1.75?" and so on. Each question splits the data in two, and the leaves at the bottom hold the final answers. A tree is one of the few models you can print, read and explain to a non-technical colleague.

Trees need no feature scaling, handle numeric and binary features naturally, and capture nonlinear relationships and interactions without you engineering them. The price is that a single tree overfits easily (the next lesson, Controlling Tree Complexity, deals with that). They are also the building block of the strongest tabular models you will meet: random forests and gradient boosting.

How a tree is built

Pick a question A feature and a threshold.
Split the rows Left if yes, right if no.
Repeat Ask again inside each part.
Stop at a leaf Predict the majority class.
1 / 2

Impurity: how mixed is a group?

A node is pure if all its rows have the same label. The tree wants splits that produce purer children. Two common impurity measures, where each p is the share of one class in the node:

  • Gini impurity: 1 - sum(p ** 2). It is 0 for a pure node and 0.5 for a 50/50 two-class node. It is the scikit-learn default.
  • Entropy: -sum(p * log2(p)). It is 0 for a pure node and 1 bit for a 50/50 two-class node.

The information gain of a split is the parent's impurity minus the size-weighted average impurity of the two children. The tree tries every feature and every candidate threshold and takes the split with the largest gain.

Let us do that by hand on ten customers: their age and whether they bought a product.

Python Impurity and the best split, by hand

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The best threshold is 42.5: the left side (ages up to 40) has five people, one of whom bought, and the right side has five people who all bought. Its weighted Gini is 0.16, a gain of 0.32 over the parent's 0.48. The threshold 32.5 is a close second, which shows that the tree is simply comparing numbers, not understanding customers.

Real implementations do exactly this loop, only faster (they sort each feature once), and then recurse into each child.

Fitting a tree in scikit-learn

DecisionTreeClassifier follows the usual estimator API. Here is a small tree on the classic iris flowers (three species, four measurements; the dataset ships inside scikit-learn). export_text prints the learned rules.

Python DecisionTreeClassifier and export_text

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the printout like a flowchart. Setosa is isolated by the single question petal width <= 0.80. The two other species need more questions. Notice something instructive: at depth 3 the tree splits twice on petal length and both children still predict the same class. A split is chosen because it reduces impurity (the children are purer), even if the majority class in both children is unchanged. Impurity is a smoother signal than accuracy, which is why trees use it.

Other things to know:

  • predict_proba returns the class share in the leaf, so a tree's probabilities are coarse (a fully grown tree gives only 0 or 1).
  • feature_importances_ sums how much each feature reduced impurity. Here the petal measurements carry everything. Take this number with a grain of salt: Feature Importance and Interpretation explains its biases.
  • random_state matters: when two splits tie, the choice among features depends on the random seed.

Seeing the tree

plot_tree draws the same rules as a diagram. Each box shows the question, the impurity, the number of samples, the class counts and the majority class; box color follows the majority class.

Python plot_tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The root holds all 150 flowers with Gini about 0.667 (three equally common classes). One question separates setosa completely, giving a pure leaf with Gini 0. The remaining 100 flowers are split once more, and the two leaves are nearly pure.

Gini versus entropy

In practice the two criteria give very similar trees. Gini is slightly cheaper to compute (no logarithm); entropy penalizes mixed nodes a bit more. Try both and compare with cross-validation if you care, but do not expect a big difference.

Python Comparing the criteria

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both trees are fully grown here (no depth limit). They differ in size by a few leaves and by roughly one test row of accuracy, which on 45 test rows is just noise.

ID3, C4.5 and CART: the algorithm family

"Decision tree" is a family of algorithms that share one idea (split greedily on the feature that makes the groups purest) and differ in the details. Three names come up again and again.

Algorithm Split criterion Feature types Splits Output
ID3 (1986) Information gain (entropy) Categorical only One branch per category value Classification
C4.5 (1993) Gain ratio (information gain divided by split information) Categorical and numeric (numeric ones by threshold); handles missing values; has pruning Multiway for categories, binary for thresholds Classification
CART (1984) Gini impurity (classification) or squared error (regression) Numeric and categorical, always binary splits Binary only Classification and regression

Scikit-learn implements an optimized version of CART: every split is binary (a threshold on one feature), the default criterion is Gini, and the same machinery also fits regression trees. ID3 and C4.5 are mostly of historical and teaching interest, but they show two ideas you should know.

Information gain prefers features with many values. A column like a customer ID or a date splits the data into one tiny group per row. Every group is trivially pure, so the information gain is as large as it can be, yet the split teaches nothing about new data. C4.5 fixes this with the gain ratio: it divides the gain by the split information, the entropy of the sizes of the branches, which is large for splits into many small groups. The program below builds a twelve-day "should we ride a bike" table with an ID column and computes all three numbers by hand.

Python Information gain versus gain ratio, and a tiny ID3

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The day_id column has the maximum possible information gain (1.000 bit, the whole entropy), because each branch holds one day. ID3 would put it at the root and learn a lookup table of the training days. Its split information is 3.585 bits, which pulls its gain ratio down to 0.279, below wind (0.350), so C4.5 picks wind. The tree built without the ID column splits on wind first and then on sky, and gets every day right with a sensible set of rules: cloudy days are a yes, rainy days are a no, and sunny days depend on the wind. In scikit-learn the same danger exists (a unique-per-row column would be chosen by a fully grown tree), so remove identifiers before fitting.

CHAID, C5.0 and MARS: more members of the family

Besides ID3, C4.5 and CART there are a few other well-known tree algorithms.

  • CHAID (Chi-squared Automatic Interaction Detector) chooses splits with a statistical test instead of an impurity measure. For each categorical feature it builds a contingency table of feature value against target class and computes the chi-squared test's p-value; the feature with the smallest p-value (the strongest association with the target) is used for the split, provided it is below a threshold. Categories that behave the same way are merged first (with the same test), and the split is multiway: one branch per remaining group of categories, not just two. CHAID stops when no split is significant, so the tree is pruned by design. It is very popular in market research and survey analysis, because its trees are wide, shallow and easy to read, and every split comes with a p-value. Continuous features must be binned first.
  • C5.0 is the commercial successor of C4.5: faster, more memory efficient, with boosting built in, rule-set output and more accurate trees on large data.
  • MARS (Multivariate Adaptive Regression Splines) is not a tree but is often listed with them: it builds a regression model from piecewise linear "hinge" functions chosen in a forward-and-backward search, similar in spirit to recursive partitioning.

Scikit-learn does not include CHAID. The example below computes the CHAID-style test by hand with scipy: for every categorical feature of a customer table it builds the contingency table with the target and prints the chi-squared statistic and p-value. The feature with the smallest p-value would be the root split.

Python The chi-squared test that drives a CHAID split

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Contract type and plan are strongly related to churn, so they get tiny p-values, while region and device are not significant and would never be used. The root split is the contract (monthly customers churn at about 42%, yearly ones at about 12%), and inside the monthly contracts the plan is the best next split. Real CHAID software also merges categories with similar churn rates before it splits (here, "standard" and "premium" would likely be merged), and adjusts the p-values for the many comparisons it makes (a Bonferroni correction). The price of this approach is that it works with categorical inputs and discards much of the information in continuous features; for numeric data, CART-style trees are the better default.

Decision tree regression

A regression tree predicts a number instead of a class. The structure is the same, but the leaves store the mean of the training targets that reach them, and the split criterion measures squared error instead of class impurity. For each candidate split, the algorithm computes the sum of squared deviations from each child's mean and picks the split that makes that total smallest. This is the same as maximizing the variance reduction.

The consequence is a prediction that is a step function: constant inside each leaf and jumping at the thresholds. That is perfect for data with plateaus and poor for smooth trends, which a tree must approximate with many small steps. And since a tree never predicts outside the range of targets it saw, it cannot extrapolate: a linear model continues a trend past the edge of the data, a tree stays flat.

The example generates a noisy series with three plateaus. It finds the best first split by brute force, checks it against scikit-learn, and then shows what depth does to the score.

Python Regression trees: best split by hand, and depth versus overfitting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The brute-force search puts the first split at 3.99, the same threshold as scikit-learn, and the one split cuts the squared error from 8,000 to about 3,770. The depth-2 tree recovers the three plateaus almost exactly: it cuts at about 4.0 and 7.0 and predicts about 20, 35 and 25, which is how we generated the data. Deeper trees chase the noise. The training Rยฒ climbs to 1.0 while the test Rยฒ falls from 0.78 (depth 2) to 0.57 (no limit), the same overfitting story as for classification trees (Controlling Tree Complexity).

Which one should you use? In practice, use scikit-learn's CART trees (DecisionTreeClassifier and DecisionTreeRegressor) with a depth limit or pruning, and move to random forests or gradient boosting when accuracy matters. Know ID3 and C4.5 for interviews and for the gain-ratio idea.

Strengths and weaknesses

Strengths

  • Easy to explain and audit; the rules can be written down.
  • No scaling or normalization needed, and it is not affected by monotone transforms of a feature.
  • Handles mixed feature types and finds interactions on its own.

Weaknesses

  • A fully grown tree memorizes the training set (training accuracy of 1.0 is a warning, not a victory).
  • Small changes in the data can produce a very different tree: high variance.
  • Splits are axis-aligned, so a diagonal boundary needs a staircase of splits.
  • Predictions are piecewise constant: regression trees cannot extrapolate beyond the target values they saw.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the Gini impurity of a node that contains only one class?

    With a single class p = 1, so 1 - 1^2 = 0. Zero means perfectly pure.
  2. 2. How does a decision tree choose a split?

    Trees are greedy: at each node they evaluate feature/threshold candidates and choose the highest information gain, without looking ahead.
  3. 3. A tree has training accuracy 1.00 and test accuracy 0.86. What is the most likely explanation?

    A fully grown tree can memorize the training rows. The gap between training and test scores signals overfitting. Scaling plays no role for trees.
  4. 4. Why do trees not need feature scaling?

    A split asks 'feature <= threshold'. Multiplying the feature by a constant just moves the threshold, so the resulting partition is unchanged.

Summary

  • A tree predicts with a chain of threshold questions; leaves hold the predictions.
  • Splits are chosen greedily by the largest drop in impurity (Gini or entropy), weighted by child size.
  • DecisionTreeClassifier is fit like any estimator; export_text and plot_tree show the rules.
  • Gini and entropy usually give near-identical trees.
  • Trees are interpretable and need no scaling, but unconstrained trees overfit.

Next: Controlling Tree Complexity.