Decision Trees from Scratch: How Splits Actually Get Made

Last time, Sam compared XGBoost, LightGBM, and CatBoost on a practice dataset. Before trusting an ensemble of hundreds of trees, though, he wants to understand what a single tree actually does.

1. The ‘Messy Room’ Problem: Why We Need a Ruler for Chaos

Have you ever walked into a room where everything is in the wrong place? Socks on the bookshelf, books in the laundry basket, a stray shoe on the kitchen counter. You wouldn’t just move things randomly to clean it up. You’d group things together until every box held only one type of item.

Sam’s used-car practice data feels like that room—expensive and cheap cars jumbled together like socks on a bookshelf. He needs to sort them into clean, separate piles before he can trust a model to make predictions.

Think of a Decision Tree as a professional organizer. Its job is to take a messy pile of data and split it into smaller piles that are as ‘clean’ as possible. In data science, a perfectly clean pile is ‘pure.’ A box containing only blue socks is pure. A box containing socks, toys, and mail is ‘impure.’

To build a tree, we need a way to measure how messy a group is. A ruler for chaos. If we can’t measure the mess, we can’t know if a specific ‘if-then’ rule (like ‘Is the mileage over 50,000?’) actually made our data cleaner. Here’s what a messy starting point looks like in Python.

# Let's represent our 'items' as labels
# 1 = 'Expensive Car', 0 = 'Cheap Car'
group_a = [1, 1, 1, 1, 1]  # Perfectly clean (all expensive)
group_b = [1, 0, 1, 0, 1]  # Very messy (mixed)
group_c = [0, 0, 0, 0, 0]  # Perfectly clean (all cheap)

print(f"Group A: {group_a} - This looks very organized.")
print(f"Group B: {group_b} - This is pure chaos.")

• The comments establish the encoding scheme: 1 means “Expensive Car” and 0 means “Cheap Car” — binary labels are standard for two-class classification problems.
• group_a = [1, 1, 1, 1, 1] represents a perfectly clean group where every car is expensive — this is what a tree wants its leaf nodes to look like.
• group_b = [1, 0, 1, 0, 1] is the messy group: three expensive and two cheap cars mixed together — this is what the tree starts with and tries to split apart.
• group_c = [0, 0, 0, 0, 0] is the other perfectly clean extreme — all cheap, no mixing.
• The f-strings (f"Group A: {group_a} ...") use Python’s string interpolation to embed the list values directly into the output text, so you can see the data at a glance.

What we’re really after is the split that creates the cleanest sub-groups. But to find it, we need a mathematical way to turn ‘chaos’ into a number.

2. Gini Impurity: The ‘Wrong Guess’ Score

Picture a bag holding all the items from group_b — three 1s and two 0s. You reach in, pull one out, and guess what it is. How likely are you to be wrong?

That chance of a wrong guess is what Gini Impurity measures. It’s the probability of mislabeling a randomly chosen element if labels are assigned according to the distribution in the set.

• If the bag is 100% apples, you guess ‘apple’ every time. Wrong 0% of the time. Gini score: 0.
• If the bag is 50% apples and 50% oranges, you’re wrong a lot. High impurity.

Gini is just a shortcut, though. The formula: 1 - sum(squared probabilities of each label).

def calculate_gini(labels):
    if not labels: return 0
    counts = {}
    for l in labels:
        counts[l] = counts.get(l, 0) + 1
    
    impurity = 1
    for l in counts:
        prob_of_label = counts[l] / len(labels)
        impurity -= prob_of_label**2
    return impurity

print(f"Gini for Group A (Pure): {calculate_gini(group_a):.2f}")
print(f"Gini for Group B (Messy): {calculate_gini(group_b):.2f}")

• def calculate_gini(labels): defines a function that takes a list of class labels (like [1, 0, 1, 0, 1]) and returns a single impurity score.
• if not labels: return 0 is a guard clause — an empty list has zero impurity by convention, and this prevents a division-by-zero later.
• counts = {} initializes an empty dictionary to tally how many of each label appear in the list.
• counts[l] = counts.get(l, 0) + 1 is a classic Python idiom: .get(l, 0) returns the current count for label l (or 0 if it hasn’t been seen yet), then adds 1 — this builds a frequency dictionary in one pass.
• impurity = 1 starts the Gini at 1 and subtracts each squared probability — the formula is $1 - \sum p_i^2$.
• prob_of_label = counts[l] / len(labels) computes the proportion of the total that each label represents.
• impurity -= prob_of_label**2 subtracts the squared probability — a class that dominates the group contributes far more to the subtracted sum than a rare class does, so a lopsided group scores low impurity while an even split scores the maximum 0.5 for two classes.
• The f-string {calculate_gini(group_a):.2f} formats the returned float to 2 decimal places for cleaner output.

A Gini score of 0.48 for Group B means the set is roughly 48% ‘messy.’ Closer to 0 means a cleaner split.

3. Entropy: The ‘Surprise’ Factor

Another way to measure impurity is Entropy. Gini tracks the probability of being wrong; Entropy tracks information, or surprise.

A fair coin lands heads — you’re not shocked, because there was real uncertainty. But if I tell you a two-headed coin landed heads, I’ve given you nothing new. You already knew it would happen.

This is the hardest part: Entropy uses logarithms (log2 specifically), since logs count bits of information. A perfectly pure group has Entropy 0. A perfect 50/50 split gives Entropy 1.0.

import math

def calculate_entropy(labels):
    if not labels: return 0
    counts = {}
    for l in labels:
        counts[l] = counts.get(l, 0) + 1
    
    entropy = 0
    for l in counts:
        p = counts[l] / len(labels)
        entropy -= p * math.log2(p)
    return entropy

print(f"Entropy for Group B: {calculate_entropy(group_b):.2f}")

• import math brings in Python’s math module to access math.log2 — the base-2 logarithm function that Entropy requires.
• The counts dictionary-building loop is identical to the Gini function — same frequency tally, same idiom.
• entropy = 0 starts at zero and adds each term (via -=), whereas Gini starts at 1 and subtracts — both accumulate but from different baselines.
• p = counts[l] / len(labels) computes the probability of each label, exactly as in Gini.
• entropy -= p * math.log2(p) is the key difference from Gini: instead of squaring the probability, Entropy multiplies each probability by its own base-2 logarithm — this measures “information content” in bits. For any p between 0 and 1, log2(p) is negative, so the product p * log2(p) is negative too — which is exactly why the line subtracts (-=) rather than adds: subtracting a negative number adds a positive amount of entropy.
• math.log2(p) would crash if p were 0, but the guard if not labels and the dictionary loop (which only visits labels that exist) prevent that edge case.

Gini Impurity — the probability of misclassifying a randomly chosen element if it were labeled according to the class distribution:

$\text{Gini}(S) = 1 - \sum_{i=1}^{C} p_i^2$

Entropy — the “surprise” or information content of a set, measured in bits:

$H(S) = -\sum_{i=1}^{C} p_i \log_2(p_i)$

Information Gain — the reduction in impurity after splitting set $S$ on attribute $A$:

$IG(S, A) = \text{Impurity}(S) - \sum_{v \in \text{values}(A)} \frac{|S_v|}{|S|} \cdot \text{Impurity}(S_v)$

Plain English	Statistical symbol	Python equivalent
Probability of label $i$	$p_i$	counts[l] / len(labels)
Gini Impurity of set $S$	$\text{Gini}(S) = 1 - \sum p_i^2$	1 - sum(prob**2)
Entropy of set $S$	$H(S) = -\sum p_i \log_2 p_i$	-sum(p * math.log2(p))
Weighted child impurity after split	$\sum \frac{	S_v
Information Gain from split $A$	$IG(S, A)$	gini(parent) - weighted_child_impurity

Why use this over Gini? Entropy is slightly more sensitive to changes in the middle of the distribution. In practice, they usually lead to the same tree, but Entropy is the classic way to measure ‘Information Gain.’

Criterion	Gini Impurity	Entropy
Computational cost	Lower (no log calculation)	Higher (log₂ per term)
Sensitivity near 50/50 splits	Less sensitive	More sensitive
Range (binary)	0 to 0.5	0 to 1.0
Typical result	Same tree as Entropy	Same tree as Gini

Rule of thumb: Use Gini (the default in most libraries) when you want speed; reach for Entropy when you need slightly more sensitivity to balanced splits or when you’re following the classic Information Gain literature.

4. Information Gain: The ‘Is it Worth it?’ Test

Now we have a ruler. How does the tree actually use it? It uses Information Gain.

Before a split, the tree measures the messiness of the ‘Parent’ group. Then it simulates a split (say, ‘Mileage < 50k’) and calculates the average messiness of the two resulting ‘Child’ groups.

Information Gain = (Messiness Before) - (Messiness After)

A high Gain means the split did real work cleaning things up. Zero Gain means it accomplished nothing. So let’s calculate it.

def information_gain(parent, left_child, right_child):
    # We weight the children by their size
    weight_l = len(left_child) / len(parent)
    weight_r = len(right_child) / len(parent)
    
    gain = calculate_gini(parent) - (weight_l * calculate_gini(left_child) + weight_r * calculate_gini(right_child))
    return gain

# Example: Splitting a group of 4 cars
parent_cars = [1, 0, 1, 0]
left_split = [1, 1]  # All expensive
right_split = [0, 0] # All cheap

gain = information_gain(parent_cars, left_split, right_split)
print(f"Information Gain of this split: {gain:.2f}")

• def information_gain(parent, left_child, right_child): takes the original group and the two sub-groups created by a candidate split — the function works with any impurity measure (Gini or Entropy) since it calls calculate_gini internally.
• weight_l = len(left_child) / len(parent) computes what fraction of the parent’s rows ended up in the left child — a larger child gets more weight, so its impurity matters more to the overall score.
• weight_r = len(right_child) / len(parent) does the same for the right child; note that weight_l + weight_r always equals 1 (assuming every row goes to one side or the other).
• gain = calculate_gini(parent) - (weight_l * calculate_gini(left_child) + weight_r * calculate_gini(right_child)) is the Information Gain formula in one line: parent impurity minus the size-weighted average of the children’s impurities.
• parent_cars = [1, 0, 1, 0] is a 50/50 split — maximally impure for a two-class problem, so Gini is 0.5 (the worst case for binary).
• left_split = [1, 1] and right_split = [0, 0] are both perfectly pure (Gini = 0), so the gain is 0.5 - (0.5*0 + 0.5*0) = 0.5 — the maximum possible for a binary split.

The result is 0.50. Since the maximum Gini for two classes is 0.50, we went from total mess to perfectly clean. A clear win.

5. Building the Best Split: A Step-by-Step Walkthrough

A Decision Tree is just a fast accountant. It scans every column and every possible value to find the split with the highest Information Gain.

Here’s a fresh four-row toy dataset for the car-price example. We want to predict whether a car is ‘Expensive’ (1) or ‘Cheap’ (0).

# Data: [Mileage, Is_Electric (1/0)], Label: [Is_Expensive (1/0)]
data = [
    [50000, 0, 0], # High mile, gas, cheap
    [10000, 1, 1], # Low mile, electric, expensive
    [80000, 0, 0], # High mile, gas, cheap
    [5000, 0, 1],  # Low mile, gas, expensive
]

# Let's test two possible splits:
# Split 1: Is the car Electric?
# Split 2: Is Mileage < 20,000?

parent_labels = [0, 1, 0, 1]

# Split 1 results (Electric vs Gas)
# Electric cars: [1] | Gas cars: [0, 0, 1]
electric_gain = information_gain(parent_labels, [1], [0, 0, 1])

# Split 2 results (Mileage < 20k)
# Low miles: [1, 1] | High miles: [0, 0]
mileage_gain = information_gain(parent_labels, [1, 1], [0, 0])

With both candidate gains calculated, we can compare them and let the tree pick a winner.

print(f"Gain from 'Is Electric': {electric_gain:.2f}")
print(f"Gain from 'Low Mileage': {mileage_gain:.2f}")

if mileage_gain > electric_gain:
    print("The tree chooses Mileage as the first branch!")

• Each row in data is [Mileage, Is_Electric, Is_Expensive] — the first two values are features, and the third is the label the tree is trying to predict.
• parent_labels = [0, 1, 0, 1] extracts just the labels from the four rows — two cheap (0) and two expensive (1), so the parent is maximally mixed.
• electric_gain = information_gain(parent_labels, [1], [0, 0, 1]) simulates splitting by “Is Electric?”: the electric group [1] is pure (one expensive car), but the gas group [0, 0, 1] is still mixed (two cheap, one expensive), so the gain is only partial.
• mileage_gain = information_gain(parent_labels, [1, 1], [0, 0]) simulates splitting by “Mileage < 20,000”: both children are perfectly pure — low-mileage cars are all expensive, high-mileage cars are all cheap — so the gain is maximal.
• if mileage_gain > electric_gain: is the tree’s actual decision logic: whichever candidate split has the higher Information Gain wins and becomes the node’s split rule.
• The print statements reveal which split the tree would choose — in this case, mileage wins because it separates the classes perfectly while the electric split leaves the gas group messy.

The ‘Low Mileage’ split gives two perfectly pure groups—max gain. The tree picks it, then moves on.

So what did we pick up today?

1. Impurity just means a group is mixed.
2. Gini and Entropy are two ways to measure that mess.
3. Information Gain tells you whether a split actually organized the data.
4. The Tree is a loop that tries every split and keeps the one with the biggest Gain.

That’s the takeaway. Even complex models like XGBoost or CatBoost (covered in Part 4) build on these same pieces. They just do it faster, with more trees.

A single tree is easy to read but fragile—Sam wants to see what happens when you combine many of them.

Next up: Random Forests vs. Gradient Boosting—teams of trees voting on Sam’s listings for a ‘wisdom of the crowd’ effect. Try it on your own data, and see if you can spot the pure groups yourself.

Check Your Understanding

Questions below move from simple recall up to open-ended design, roughly following Bloom’s Taxonomy.

Remember What does a Gini Impurity score of 0 mean, and what does a score of 0.5 mean for a two-class problem?

Understand In your own words, explain what “Information Gain” measures, using the article’s formula (Messiness Before - Messiness After).

Apply Using the article’s calculate_gini formula (1 - sum(squared probabilities of each label)), calculate the Gini Impurity for a group of 5 cars where 4 are “Expensive” (1) and 1 is “Cheap” (0).

Analyze The article’s Section 5 example shows the “Low Mileage” split achieves a gain of 0.50 (perfectly clean children) while the “Is Electric” split achieves a lower gain (impure children — the gas group [0, 0, 1] still mixes cheap and expensive cars). The article says a Decision Tree “scans every column and every possible value” to find the split with the highest Information Gain. Walk through why scanning every column and every possible value guarantees finding the highest-gain split, and what that guarantee costs as rows and columns grow.

Evaluate The article says Gini and Entropy “usually lead to the same tree” and calls Entropy “slightly more sensitive to changes in the middle of the distribution.” Critique the practice of picking one over the other by default (e.g., always using Gini because it’s faster to compute, without checking Entropy): when might that sensitivity difference actually change which split a tree picks?

Create Design a 4-row toy dataset (like the article’s mileage/electric example) with two candidate splits where the Entropy-based gain and the Gini-based gain would disagree about which split is better. You don’t need to compute exact numbers — just describe the label distribution in each candidate split’s children that would create that disagreement.

---

Related articles

• P04: XGBoost vs. LightGBM vs. CatBoost: How to Actually Choose Without a Math Degree) — where Sam compared the three major gradient-boosting libraries on a used-car practice dataset before tackling the real HomeMatch model.
• P06: Random Forests vs. Gradient Boosting: Why Teams of Trees Win) — the next step for Sam: combining many single trees into ensembles that vote on whether a listing will sell fast.

References & Further reading

• Breiman, L., Friedman, J., Olshen, R., & Stone, C. (1984). Classification and Regression Trees. Belmont, CA: Wadsworth International Group. — the foundational CART text that formalized Gini Impurity as a splitting criterion and established the recursive tree-building algorithm still used today.
• Quinlan, J. R. (1986). “Induction of Decision Trees.” Machine Learning, 1(1), 81–106. — introduced the ID3 algorithm and popularized Entropy-based Information Gain as the splitting criterion for decision-tree construction.
• Kaggle: House Prices — Advanced Regression Techniques — a competition where tree-based models (random forests, gradient boosting) dominate the leaderboard for tabular housing prediction — the same domain Sam is working in at HomeMatch.
• scikit-learn: Decision Trees documentation — official docs covering both Gini and Entropy (criterion parameter), tree depth control, and practical tips for avoiding overfitting.

---