Decision trees

How a split is chosen: purity

Picture two jars of marbles. One holds only blue marbles. The other is half blue, half red. The first jar is pure: everything in it is one kind. The second is as mixed as two colors get.

A good question splits the customers into two groups that are each as pure as possible. Ideally the stayers end up on one side and the churners on the other. To compare questions, the tree needs a number for how mixed a group is. The usual one is Gini impurity.

Here's one way to picture it. Pick one customer from the group at random and put them back. Then pick again. Gini impurity is the chance that your two picks have different labels.

• If everyone in the group stayed, your two picks always match. The impurity is 0.
• If the group is half stayers and half churners, they differ half the time. The impurity is 0.5.

As a formula:

One symbol at a time:

• $G$ is the Gini impurity of one group.
• $k$ stands for a class, such as "stayed" or "churned".
• $p_k$ is the share of the group in class $k$. If 3 of 4 customers stayed, the share for "stayed" is 0.75.
• $\sum_k$ uses the Greek letter sigma. It means "add this up over every class", like a for loop.

In plain words: for each class, take its share of the group and square it. Add those squares up, then subtract the total from 1.

Worked example

A group of 5 customers: 4 stayed and 1 churned.

1. Shares: 4 ÷ 5 = 0.8 stayed, and 1 ÷ 5 = 0.2 churned.
2. Squares: 0.8 × 0.8 = 0.64, and 0.2 × 0.2 = 0.04.
3. Add them: 0.64 + 0.04 = 0.68.
4. Subtract from 1: 1 − 0.68 = 0.32.

So the impurity is 0.32. The group is mostly one class, but not completely.

The same calculation in Python. np.unique counts how many of each label there are. Dividing the counts by the total turns them into shares.

import numpy as np

def gini(labels):
    _, counts = np.unique(labels, return_counts=True)
    p = counts / counts.sum()
    return 1 - np.sum(p ** 2)

print("all stay:      ", gini([0, 0, 0, 0]))
print("half and half: ", gini([0, 1, 0, 1]))
print("1 in 5 churn:  ", round(gini([0, 0, 0, 0, 1]), 3))

It prints 0.0, 0.5 and 0.32. A pure group scores 0. A 50/50 group scores 0.5, which is the most mixed a group with two classes can be.

Note: some tree software measures mixing with entropy, which you met in Phase 2, instead of Gini. The results are usually similar.

Scoring a question

A question splits one group into two sides. The left side holds the examples at or below the cutoff. The right side holds the ones above it.

To score the question, the tree finds the Gini impurity of each side. Then it averages the two, giving each side weight by its size. A side with more customers counts for more. Lower scores are better.

• $n$ is the number of examples in the group before the split.
• $n_L$ is the number that go left.
• $G_L$ is the Gini impurity of the left side.
• $n_R$ is the number that go right.
• $G_R$ is the Gini impurity of the right side.

In plain words: take each side's impurity and multiply it by that side's share of the examples. Add the two results. That's the question's score.

Worked example

Six customers, with the days since each one's last order:

Before any split, 4 stayed and 2 churned. The shares are 2/3 and 1/3, so the impurity is 1 − (4/9 + 1/9) = 4/9, about 0.444.

Now try the question "days since last order 60 or fewer?":

1. Left side: the customers at 10, 30 and 60 days. All 3 stayed, so its impurity is 0.
2. Right side: the customers at 120, 200 and 300 days. One stayed and 2 churned, so its impurity is 4/9, about 0.444.
3. Each side holds 3 of the 6 customers, a share of 1/2.
4. Score: 1/2 × 0 + 1/2 × 0.444 = 0.222.

One question cut the mixing in half, from 0.444 to 0.222.

print(1 - (0.5 ** 2 + 0.5 ** 2))

Trying every question

The tree tries every feature and every possible cutoff, and keeps the question with the lowest score. Then it repeats the search inside each side, and inside those sides, and so on.

This approach is greedy. At each step it takes the best question right now. It never looks ahead to check whether a different question would lead to a better tree later. Think of a shopper who grabs the cheapest item in each aisle without planning the whole basket. It's fast and usually good enough, but it doesn't promise the best possible tree.

scikit-learn, the library used here, puts each cutoff halfway between two neighboring values, such as 180.5 between 180 and 181. That's why its printed cutoffs often end in .50.

days    = [10, 30, 60, 120, 200, 300]
churned = [0,  0,  0,  1,   0,   1]

def gini(labels):
    n = len(labels)
    return 1 - sum((labels.count(c) / n) ** 2 for c in set(labels))

def split_score(cutoff):
    left = [y for d, y in zip(days, churned) if d <= cutoff]
    right = [y for d, y in zip(days, churned) if d > cutoff]
    n = len(churned)
    return len(left) / n * gini(left) + len(right) / n * gini(right)

print(f"no split yet:   {gini(churned):.3f}")
for cutoff in days[:-1]:
    print(f"days <= {cutoff:>3}:  {split_score(cutoff):.3f}")

Depth: from too simple to memorizing

Think of two students preparing for an exam with last year's paper. One learns the main ideas. The other memorizes every answer word for word. The second scores 100% on the old paper and struggles on the new one.

A tree that's left to grow acts like the second student. It keeps splitting until every leaf is pure. Real data is noisy: some customers leave for reasons no column records. So on noisy data, pure leaves mean a leaf for nearly every customer. The tree is perfect on its training data and poor on new data. You control how far it grows with:

• max_depth: the most questions it can ask in a row.
• min_samples_leaf: every leaf must hold at least this many training examples. A leaf with one customer is a memory, not a pattern.
• Pruning: grow the full tree, then cut back branches that don't help on validation data (data held back from training).

The code below holds back 30% of the customers as a test set (test_size=0.3). The tree never trains on them. stratify keeps the share of churners the same in both parts. Then it trains trees of growing depth, where None means no limit. For each tree it prints the number of leaves, and its accuracy on training and test data. Accuracy is the share of customers it predicts correctly.

import pandas as pd
import requests
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier

df = pd.DataFrame(requests.get("https://api.gradient.test/v1/customers").json()["data"])
features = ["days_since_last_order", "orders_last_year", "support_tickets", "trail_club", "tenure_months", "avg_order_value"]
X_tr, X_te, y_tr, y_te = train_test_split(df[features], df["churned"], test_size=0.3, random_state=0, stratify=df["churned"])
for depth in [1, 2, 3, 5, 8, None]:
    t = DecisionTreeClassifier(max_depth=depth, random_state=0).fit(X_tr, y_tr)
    print(f"max_depth {str(depth):<5} leaves {t.get_n_leaves():>3}  train {t.score(X_tr, y_tr):.3f}  test {t.score(X_te, y_te):.3f}")

Training accuracy climbs to 1.0 as depth grows. Test accuracy peaks early and then slides. The gap between the two is overfitting: the deep tree has memorized its training customers. It gets its own lesson soon.

Strengths and weaknesses

Why no rescaling? A tree only asks whether one feature is above a cutoff. Measure time in weeks instead of days and a cutoff of 182 days becomes 26 weeks. The same customers land on the same side.

Why step-shaped? Every customer who reaches a leaf gets that leaf's prediction. Nudge a feature and the prediction stays put until it crosses a cutoff. Then it jumps.

Why unstable? The first question shapes everything below it. Change a few rows, and a different first question might win by a hair. Then the whole tree underneath changes too.

Instability and overfitting are exactly what ensembles fix. They grow many trees and combine their answers.