Machine Learning

Supervised Learning Classification

Decision Trees

A decision tree predicts by asking a sequence of yes/no questions about the input features, splitting the data into progressively smaller, more homogeneous grou

JrCodex·9 min read

Jr Codex ML Notes

Level: Intermediate Prerequisites: Chapter 2 Time to complete: ~30 minutes

Table of Contents

  1. A Model That Reasons Like a Flowchart
  2. How a Tree Makes a Prediction
  3. How a Tree Is Built: Choosing the Best Split
  4. Entropy and Information Gain
  5. Gini Impurity — a Faster Alternative
  6. Decision Trees for Regression
  7. Overfitting and Pruning
  8. Why Trees Don't Need Feature Scaling
  9. Strengths, Weaknesses & When to Use
  10. Summary & Next Steps

1. A Model That Reasons Like a Flowchart

A decision tree predicts by asking a sequence of yes/no questions about the input features, splitting the data into progressively smaller, more homogeneous groups — directly connecting to the AI Notes' rule-based expert systems, but with the rules learned automatically from data rather than hand-coded.

A Decision Tree, Visualized
─────────────────────────────────────────
                  Income > $50k?
                  /            \
                Yes              No
                /                  \
        Credit Score > 700?      Reject
          /            \
        Yes              No
        /                  \
     Approve              Review
─────────────────────────────────────────

2. How a Tree Makes a Prediction

from sklearn.tree import DecisionTreeClassifier
import numpy as np
 
X = np.array([
    [60000, 720],      # [income, credit_score]
    [45000, 680],
    [80000, 750],
    [30000, 600],
])
y = np.array([1, 0, 1, 0])      # 1 = approved, 0 = rejected
 
model = DecisionTreeClassifier(max_depth=2, random_state=42)
model.fit(X, y)
 
prediction = model.predict([[55000, 710]])
print(prediction)
 
# Visualizing the LEARNED tree structure
from sklearn.tree import export_text
tree_rules = export_text(model, feature_names=["income", "credit_score"])
print(tree_rules)
Following a Prediction Through the Tree
─────────────────────────────────────────
  New applicant: income=55000, credit_score=710

  Root question: "income <= 52500?" → NO (55000 > 52500)
      → go RIGHT
  Next question: "credit_score <= 715?" → YES (710 <= 715)
      → go LEFT
  → arrives at a LEAF node → PREDICTION made
─────────────────────────────────────────

3. How a Tree Is Built: Choosing the Best Split

The genuinely interesting part: how does the algorithm decide which feature to split on, and at what threshold, at each step?

The Greedy, Recursive Building Process
─────────────────────────────────────────
  1. Start with ALL training data at the ROOT
  2. Try every possible split (every feature, every threshold)
  3. Pick the split that makes the resulting two groups the
     MOST "pure" (Sections 4-5 define this precisely)
  4. Repeat RECURSIVELY on each resulting group
  5. Stop when a group is pure enough, or a stopping condition
     is reached (Section 7)
─────────────────────────────────────────

This Is a GREEDY Algorithm — Directly Connects to the AI Notes
─────────────────────────────────────────
  At each step, the tree picks the LOCALLY best split available
  RIGHT NOW, without considering whether a DIFFERENT split might
  lead to a better tree OVERALL a few levels down.

  This is conceptually the SAME greedy strategy discussed in the
  AI Notes' search chapter (Greedy Best-First Search) — fast,
  but not GUARANTEED to find the globally optimal tree.
─────────────────────────────────────────

4. Entropy and Information Gain

Entropy measures how "mixed" or "impure" a group of labels is — directly analogous to the physics concept of disorder.

import numpy as np
 
def entropy(labels):
    """Entropy of a set of class labels — 0 = perfectly pure, higher = more mixed."""
    _, counts = np.unique(labels, return_counts=True)
    probabilities = counts / len(labels)
    return -np.sum(probabilities * np.log2(probabilities))
 
pure_group = np.array([1, 1, 1, 1])              # all one class
mixed_group = np.array([1, 1, 0, 0])                # perfectly 50/50 mixed
somewhat_mixed = np.array([1, 1, 1, 0])                # mostly one class
 
print(f"Pure group entropy: {entropy(pure_group):.3f}")           # 0.0 — no disorder at all
print(f"50/50 mixed entropy: {entropy(mixed_group):.3f}")           # 1.0 — MAXIMUM disorder (binary case)
print(f"Somewhat mixed entropy: {entropy(somewhat_mixed):.3f}")       # ~0.81 — in between
Information Gain — Choosing the Best Split
─────────────────────────────────────────
  Information Gain = entropy(BEFORE split) - weighted_average(
                        entropy(AFTER split, each resulting group)
                      )

  The tree tries EVERY possible split and picks the one with the
  HIGHEST information gain — the split that reduces disorder
  (makes the resulting groups purer) the MOST.
─────────────────────────────────────────

def information_gain(parent_labels, left_labels, right_labels):
    n = len(parent_labels)
    n_left, n_right = len(left_labels), len(right_labels)
 
    parent_entropy = entropy(parent_labels)
    weighted_child_entropy = (
        (n_left / n) * entropy(left_labels) + (n_right / n) * entropy(right_labels)
    )
    return parent_entropy - weighted_child_entropy
 
parent = np.array([1, 1, 1, 0, 0, 0])
# Splitting into two PERFECTLY pure groups
left_good_split = np.array([1, 1, 1])
right_good_split = np.array([0, 0, 0])
print(f"Information gain (good split): {information_gain(parent, left_good_split, right_good_split):.3f}")      # 1.0 — maximum possible
 
# Splitting into two groups that are STILL mixed
left_bad_split = np.array([1, 1, 0])
right_bad_split = np.array([1, 0, 0])
print(f"Information gain (bad split): {information_gain(parent, left_bad_split, right_bad_split):.3f}")      # much lower

5. Gini Impurity — a Faster Alternative

Gini impurity measures the same underlying idea (how mixed a group is) with a formula that avoids expensive logarithm calculations, making it the faster, more commonly used default.

def gini_impurity(labels):
    _, counts = np.unique(labels, return_counts=True)
    probabilities = counts / len(labels)
    return 1 - np.sum(probabilities ** 2)
 
print(f"Pure group Gini: {gini_impurity(pure_group):.3f}")           # 0.0
print(f"50/50 mixed Gini: {gini_impurity(mixed_group):.3f}")            # 0.5 — maximum for binary case
Entropy vs Gini — Which to Use
─────────────────────────────────────────
  Entropy:    slightly more computationally expensive (uses
                log2), historically associated with the ID3/C4.5
                tree-building algorithms

  Gini:          faster to compute (no logarithms), scikit-learn's
                   DEFAULT criterion, and in PRACTICE produces
                   very SIMILAR trees to entropy in the vast
                   majority of cases
─────────────────────────────────────────

from sklearn.tree import DecisionTreeClassifier
 
model_gini = DecisionTreeClassifier(criterion="gini")        # scikit-learn's default
model_entropy = DecisionTreeClassifier(criterion="entropy")     # an available alternative

6. Decision Trees for Regression

The same splitting logic applies to predicting continuous values — instead of entropy/Gini, splits are chosen to minimize the variance (or MSE, Module 3, Chapter 4) within each resulting group.

from sklearn.tree import DecisionTreeRegressor
import numpy as np
 
X = np.array([[1200], [1800], [2400], [1500], [3000]])
y = np.array([250000, 340000, 410000, 275000, 500000])
 
model = DecisionTreeRegressor(max_depth=3, random_state=42)
model.fit(X, y)
 
print(model.predict([[2000]]))
Classification vs Regression Trees — What Changes
─────────────────────────────────────────
  Classification (Sections 2-5):    splits chosen to minimize
                                       ENTROPY/GINI; leaf predicts
                                       the MAJORITY class

  Regression (this section):           splits chosen to minimize
                                          VARIANCE/MSE (Module 3,
                                          Ch.4); leaf predicts the
                                          AVERAGE target value of
                                          examples reaching it
─────────────────────────────────────────

7. Overfitting and Pruning

Decision trees are notoriously prone to overfitting — an unconstrained tree can keep splitting until every single training example sits in its own perfectly "pure" leaf, memorizing the training data entirely (Module 1, Chapter 4's overfitting, in an extreme, visually obvious form).

from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score
import numpy as np
 
np.random.seed(0)
X = np.random.randn(200, 2)
y = (X[:, 0] + X[:, 1] > 0).astype(int)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
 
for max_depth in [1, 3, 5, None]:      # None = UNLIMITED depth
    model = DecisionTreeClassifier(max_depth=max_depth, random_state=42)
    model.fit(X_train, y_train)
    train_acc = accuracy_score(y_train, model.predict(X_train))
    test_acc = accuracy_score(y_test, model.predict(X_test))
    print(f"max_depth={str(max_depth):>4}: train acc={train_acc:.3f}, test acc={test_acc:.3f}")
Pre-Pruning — Stopping Tree Growth Early
─────────────────────────────────────────
  max_depth:              maximum number of levels in the tree
  min_samples_split:         minimum examples required to
                                 justify a further split
  min_samples_leaf:              minimum examples required in
                                    any final leaf
  max_leaf_nodes:                   caps the total number of
                                       leaves

  All of these are HYPERPARAMETERS (Module 7 covers systematic
  tuning) — controlling tree complexity DIRECTLY, exactly the
  Module 1, Ch.4 bias-variance dial for this algorithm.
─────────────────────────────────────────

from sklearn.tree import DecisionTreeClassifier
 
# Post-pruning: grow a full tree, then TRIM BACK branches that don't
# genuinely improve validation performance (cost-complexity pruning)
model = DecisionTreeClassifier(ccp_alpha=0.01, random_state=42)      # higher alpha = MORE aggressive pruning
model.fit(X_train, y_train)

8. Why Trees Don't Need Feature Scaling

Directly reprising Module 2, Chapter 3's claim, now explained precisely: a tree's splits are threshold comparisons within one feature at a time ("is income > 52,500?") — entirely unaffected by whether income is measured in dollars, thousands of dollars, or any other scale, since the RELATIVE ORDERING of values within that one feature stays identical regardless of scale.

import numpy as np
from sklearn.tree import DecisionTreeClassifier
 
X_original = np.array([[50000], [60000], [70000], [80000]])
X_scaled = X_original / 1000      # same relative ordering, different scale
 
y = np.array([0, 0, 1, 1])
 
tree_original = DecisionTreeClassifier(random_state=42).fit(X_original, y)
tree_scaled = DecisionTreeClassifier(random_state=42).fit(X_scaled, y)
# Both trees find EQUIVALENT splits — just at different numeric thresholds
# (e.g. "income > 65000" vs "income > 65") — scaling changes NOTHING structurally

9. Strengths, Weaknesses & When to Use

Strengths
─────────────────────────────────────────
  - Highly INTERPRETABLE — the tree structure itself IS the
    explanation (directly connects to the AI Notes' Explainable
    AI chapter's "interpretable by design" category)
  - No feature scaling required
  - Naturally handles NON-LINEAR relationships and feature
    INTERACTIONS, unlike Chapter 1's logistic regression
  - Handles both classification AND regression
─────────────────────────────────────────

Weaknesses
─────────────────────────────────────────
  - PRONE to overfitting without careful pruning (Section 7)
  - UNSTABLE — small changes in training data can produce a
    VERY different tree structure (high variance, Module 1, Ch.4)
  - Greedy building (Section 3) doesn't guarantee the globally
    optimal tree
─────────────────────────────────────────

This instability weakness is precisely what motivates Module 5's ensemble methods — Random Forests specifically address a decision tree's high variance by combining MANY trees together, trading away some interpretability for substantially better, more stable predictions.

10. Summary & Next Steps

Key Takeaways

  • Decision trees predict via a sequence of learned yes/no threshold questions, built greedily by choosing, at each step, the split that most reduces impurity.
  • Entropy and Gini impurity both measure how "mixed" a group of labels is; information gain (or Gini reduction) determines the best split at each step.
  • Decision trees for regression split to minimize variance/MSE instead of entropy/Gini, with each leaf predicting the average target value of examples reaching it.
  • Unconstrained trees overfit severely — pre-pruning (max_depth, min_samples_leaf) and post-pruning (cost-complexity pruning) directly control this via Module 1, Chapter 4's bias-variance dial.
  • Trees don't need feature scaling (splits are threshold comparisons within one feature, unaffected by scale), and their interpretability is a genuine strength — but their high variance/instability motivates Module 5's ensemble methods.

Concept Check

  1. Why is decision tree building described as a "greedy" algorithm, and what's the trade-off this implies?
  2. What's the difference between what a classification tree's split criterion optimizes versus a regression tree's?
  3. Why don't decision trees require feature scaling, unlike KNN (Chapter 2)?

Next Chapter

→ Chapter 4: Support Vector Machines

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index