Decision Trees

A decision tree sorts examples into classes with yes-or-no questions about their features, picking each question so the groups it makes are as unmixed as possible (the Gini impurity), with max_depth to limit how many questions it asks and no need to rescale the features first.

Journeyman · AI Basics · Python · Updated

By

After this lesson you can

  • Train a DecisionTreeClassifier with max_depth and random_state, and compare its right answers on training and test rows as the depth grows
  • Explain how a tree picks each question by the Gini impurity of the groups it makes, and why a tree needs no feature scaling

Key takeaways

  • A decision tree classifies with yes-or-no questions such as "weight at most 104 grams?", and each leaf at the end of a path names a class.
  • At each step the tree tries every feature and cut-off and keeps the question whose two groups are least mixed. Your textbook calls the measure of mixing the Gini impurity.
  • max_depth limits how many questions any path can ask, and random_state makes every run build the same tree.
  • A tree compares one feature with one number at a time, so changing a feature's units, grams to kilograms, doesn't change its guesses.
  • Trees are easy to read and need little preparation, but a deep tree memorizes its training rows and a small change in the data can grow a different tree.

At Three Rivers Fruit Packers, apples, pears and plums roll down one belt, and each has to land in the right box. A new packer learns it the way people learn most sorting jobs: by asking questions. "Is it small? Then it's a plum. Big and red? Probably an apple." A model that sorts with questions like these is a decision tree, and it's the classifier people reach for when the rules behind a guess have to be read by a person: a loan check, a support ticket's queue, a fruit's box.

Regression Trees used questions to guess a number. This lesson's trees guess a category. The example for the whole chapter is fruit.csv, 450 fruits of our own made-up data, 150 of each kind, with each fruit's weight in grams, its diameter in centimeters, its sugar (in degrees Brix, the scale fruit growers use) and its skin redness from 0 to 10. It comes with Exercise: Fruit Sorter. Each code block is one notebook cell, run in order.

One question isn't enough

Ask a tree for just one question, with max_depth=1:

import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, export_text

fruit = pd.read_csv("fruit.csv")
features = ["weight_g", "diameter_cm", "sugar_brix", "skin_redness"]
X = fruit[features]
y = fruit["fruit"]
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42, stratify=y)

one_question = DecisionTreeClassifier(max_depth=1, random_state=0)
one_question.fit(X_train, y_train)
print(export_text(one_question, feature_names=features, show_weights=True))
|--- weight_g <= 104.00
|   |--- weights: [0.00, 0.00, 120.00] class: plum
|--- weight_g >  104.00
|   |--- weights: [120.00, 120.00, 0.00] class: apple

The split is stratified, as in Stratified Splits: 360 training fruits, 120 of each kind. The weights are how many training fruits of each class, in the order apple, pear, plum, end up on each side. "Weight at most 104 grams?" (<= is read "less than or equal to") catches all 120 plums and nothing else. The other side is 120 apples and 120 pears, a perfect tie, and a tie goes to the class listed first, so the tree calls every big fruit an apple. Plums are small; apples and pears overlap in size, so this tree is right about only half the big fruits.

How a tree picks a question

A tree grows one question at a time. For each feature, it tries every cut-off between the values it has seen and asks: which question leaves the two groups least mixed? The usual measure is the Gini impurity (read "jee-nee"): the chance that two fruits drawn at random from a group, the first put back, are different kinds. A pure group scores 0. Here it is by hand, for the root and two candidate first questions:

def gini(counts):
    total = sum(counts)
    return 1 - sum((count / total) ** 2 for count in counts)


def split_gini(left, right):
    n = sum(left) + sum(right)
    return sum(left) / n * gini(left) + sum(right) / n * gini(right)


print("All 360 fruits:", round(gini([120, 120, 120]), 3))
print("weight_g <= 104:", round(split_gini([0, 0, 120], [120, 120, 0]), 3))
print("skin_redness <= 5.05:", round(split_gini([26, 107, 46], [94, 13, 74]), 3))
All 360 fruits: 0.667
weight_g <= 104: 0.333
skin_redness <= 5.05: 0.557

A question's score is its two groups' Gini, each weighted by its share of the fruits. The weight question halves the mixing; the redness question barely helps, because plums come in every shade. So the tree asks about weight first, then repeats the search inside each group. It picks the best question for right now, never planning ahead; your textbook calls this a greedy search, and the method CART. scikit-learn's criterion="gini" is the default; "entropy" is another measure of mixing.

max_depth: how many questions

for depth in [1, 2, 3, 4, None]:
    tree = DecisionTreeClassifier(max_depth=depth, random_state=0)
    tree.fit(X_train, y_train)
    train_right = (tree.predict(X_train) == y_train).sum()
    test_right = (tree.predict(X_test) == y_test).sum()
    print("max_depth", depth, "| leaves", tree.get_n_leaves(),
          "| training", train_right, "of 360 | test", test_right, "of 90")
max_depth 1 | leaves 2 | training 240 of 360 | test 60 of 90
max_depth 2 | leaves 3 | training 321 of 360 | test 78 of 90
max_depth 3 | leaves 5 | training 331 of 360 | test 82 of 90
max_depth 4 | leaves 9 | training 340 of 360 | test 84 of 90
max_depth None | leaves 35 | training 360 of 360 | test 85 of 90

Each end of a path is a leaf, and it names a class. With no limit (None), the tree keeps asking until every leaf holds one kind: 35 leaves, every training fruit right. That perfect training score is the warning sign from Regression Trees: the tree has memorized apples and pears that overlap, which is overfitting. On these 90 test fruits it still did well; Overfitting and Underfitting in Module 4 shows how to choose a depth honestly. Comparing right answers on the test fruits is a first, rough measure; Accuracy names it in the next chapter.

random_state=0 matters as it did for regression trees: the tree looks at the features in a shuffled order, and a fixed seed makes every run build the same tree.

No scaling needed, and what trees are bad at

Weights run into the hundreds of grams; redness runs from 0 to 10. A tree doesn't care, because each question compares one feature with one number. Measure the weights in kilograms, and the cut-off moves to 0.104 while every guess stays the same:

tree = DecisionTreeClassifier(max_depth=3, random_state=0)
tree.fit(X_train, y_train)
kg_train = X_train.assign(weight_g=X_train["weight_g"] / 1000)
kg_test = X_test.assign(weight_g=X_test["weight_g"] / 1000)
kg_tree = DecisionTreeClassifier(max_depth=3, random_state=0)
kg_tree.fit(kg_train, y_train)
same = (kg_tree.predict(kg_test) == tree.predict(X_test)).sum()
print("Same guess for", same, "of 90 test fruits")
Same guess for 90 of 90 test fruits

(assign gives a copy of the table with one column replaced.) That's a real strength: little preparation, and rules a person can read. The honest weaknesses: a deep tree memorizes, a small change in the training rows can grow a different tree, and every question cuts one feature at a time, so a boundary that runs at a slant takes many small steps. Random Forests, in Module 4, answers the second one with many trees whose guesses are combined into one.

Check yourself

2 questions to try on the lesson page.

So what

A decision tree learns the questions a good packer would ask, choosing each one to leave the least mixed groups, and how many it may ask is the setting that decides whether it learns the pattern or memorizes the fruit.

Sources

  • scikit-learn, Decision Trees, User Guide: trees are simple to understand and interpret and need little data preparation (no normalization); they can overfit, which limiting the maximum depth helps avoid; they can be unstable, since small variations in the data might give a completely different tree, which ensembles mitigate; scikit-learn uses an optimized version of CART, searching greedily over every feature and threshold (midpoints between sorted values) for the split that minimizes the impurity; the Gini impurity formula.
  • scikit-learn 1.9.1, DecisionTreeClassifier, API reference: criterion defaults to "gini" ("log_loss" and "entropy" are the others); max_depth=None expands nodes until all leaves are pure; the features are randomly permuted at each split, so random_state must be fixed for the same tree every run; in a tie, predict gives the class with the lowest index in classes_; get_n_leaves.
  • scikit-learn 1.9.1, export_text, API reference: a text report of a tree's rules; show_weights=True shows the number of samples of each class at each leaf.
  • scikit-learn, Importance of Feature Scaling, example: tree-based models are almost not affected by scaling.

Key terms

Related