Decision trees

Warm-up

One question before the lesson. Choose an answer and check it.

Try it yourself

Pick an input and drag the threshold to split the students, and watch the Gini impurity of each side and the gain. Find the best split, then grow the tree a level at a time and compare its accuracy on the training and validation students.

Practice problems

Work each problem out on paper, then type your answer and press Check. Every problem has hints and a full solution.

Programming exercise

Write Gini impurity, entropy, the best split and a whole decision tree in plain Python. Save tree.py and test_tree.py in the same folder, fill in each function in tree.py, and run the tests:

python test_tree.py

"""Decision trees: programming exercise. Write a decision tree classifier in plain Python: Gini impurity and entropy,splitting a group, finding the best question, and growing the whole tree.Run the tests from this folder:     python test_tree.py A point is a list of numbers, such as [hours studied, hours slept], andfeature is a position in it: 0 for the first number, 1 for the second. Alabel is 1 or 0. A group's labels are a list of 1s and 0s."""  def gini(labels):    """Return the Gini impurity of the labels: 1 - p**2 - (1 - p)**2, where p is the share of 1s. An empty list has Gini 0."""    raise NotImplementedError  def entropy(labels):    """Return the entropy of the labels in bits: -p * log2(p) - (1 - p) * log2(1 - p). Leave out a term whose share is 0."""    raise NotImplementedError  def split(points, labels, feature, threshold):    """Return (left, right): the labels of the points whose feature is less than threshold, and the labels of the rest."""    raise NotImplementedError  def weighted_impurity(left, right):    """Return the Gini of each side, weighted by its share of all the labels: len(left)/n * gini(left) + len(right)/n * gini(right)."""    raise NotImplementedError  def best_split(points, labels):    """Return (feature, threshold, gain) for the question with the largest gain.     Try every feature, in order, and every threshold halfway between two    neighbouring different values of that feature. The gain is the group's    Gini minus the split's weighted impurity. If two questions have the same    gain, keep the first one found. Return None if no question has a gain    above 0.    """    raise NotImplementedError  def build(points, labels, depth):    """Grow a tree, at most depth questions deep.     A leaf is {"leaf": 1} or {"leaf": 0}: what most of its labels are (a tie    gives 1). A question is {"feature": f, "threshold": t, "below": tree,    "above": tree}, where below is the tree for the points whose feature is    less than t. Make a leaf when depth is 0 or no question has a gain.    """    raise NotImplementedError  def predict(tree, point):    """Follow the tree's questions for the point and return the label of the leaf it reaches."""    raise NotImplementedError  def accuracy(tree, points, labels):    """Return the share of the points the tree labels right."""    raise NotImplementedError 

Stuck? Write gini first, then split, then best_split, which tries every threshold halfway between neighbouring values. build calls itself on each side. The Solution tab has one way to write each function.

In practice: trees in real projects

Controlling the size. scikit-learn’s DecisionTreeClassifier grows until every leaf is pure unless you stop it. The usual controls are max_depth, min_samples_leaf (the fewest training examples a leaf may hold) and min_samples_split. Choose them on a validation set, or with cross-validation.

Categories and missing values. Trees split numbers by thresholds, so a category such as a city is usually turned into numbers first, one column per city. Some libraries, such as LightGBM, split categories and handle missing values directly.

Importance can mislead. The impurity-based importance of this lesson favours inputs with many different values, which offer more thresholds to try. Permutation importance, which shuffles one input on the validation set and measures how much worse the model gets, is a fairer check.

Test your knowledge

1. 01A group has 6 passes and 2 fails. What is its Gini impurity?Show answer

   p = 6 ÷ 8 = 0.75, so Gini = 1 − 0.75² − 0.25² = 1 − 0.5625 − 0.0625 = 0.375.

2. 02How does a tree choose its first question?Show answer

   It tries every input and every threshold, splits the training examples, and works out the impurity of the two sides, each weighted by its share. It picks the question that lowers the impurity most, the largest gain.

3. 03Why does a fully grown tree overfit?Show answer

   It keeps splitting until each leaf is pure, so its last questions separate a few training examples, often by their noise. It is perfect on the training data and worse on new data. Limit the depth or the leaf size.

4. 04Does a decision tree need its inputs scaled?Show answer

   No. Each question compares one input with a threshold. Changing the input’s unit moves the threshold the same way, and the tree makes the same predictions.

5. 05What does a leaf of a regression tree predict?Show answer

   The mean of the training values that reach it. A split is chosen to lower the squared error most, and the tree’s predictions form a staircase.

Exit ticket

One last question on the main idea of the lesson.