Loading Curriculum...

Artificial Intelligence (AI) Machine Learning

DecisionTrees

Lesson 8/19

Machine Learning • Decision Trees

Split the space, then vote

Decision trees build a rule list by repeatedly choosing the next split that reduces impurity. In the lab, each step expands one node—until the leaves become confident.

Click the plot to infer with the current tree

Beginner friendly

What are Decision Trees?

A flowchart for predictions.

A decision tree asks a sequence of questions like a “choose-your-path” story. Each question is a split on one feature (e.g., $x_1 \le t$ ). At the end, each leaf outputs a class.

Real-life analogy

Think of triage in a clinic: “Is temperature high?” → “Is cough severe?” → then decide the next action.

Visual diagram

A tree turns data into regions

Every split carves a rectangle.

Processing view

For every node, we try candidate thresholds and compute how “mixed” the labels are (impurity). We pick the split that makes left/right nodes more pure.

Prediction view

At inference time, you follow splits until you reach a leaf. The leaf’s class is a majority vote based on its training subset.

Core intuition

Why splitting helps

Uncertainty → less uncertainty.

A node is “mixed” when it contains both classes. A good split creates two smaller sets where each set is closer to pure. The result is a tree that turns complex shapes into axis-aligned rectangles.

What you can watch in this lab

• Regions change after each expansion step.
• The tree diagram grows node-by-node.
• Impurity is lowered as steps progress.

Split intuition

“Pick the split that makes leaves calmer.”

In every step, the lab chooses a split with the highest impurity gain under your constraints.

Current step explanation

Computing tree…

Interactive simulation

Decision Tree Builder

Expand one node per step.

step: 0/0

Loading Lab...

Tree visual

Computing…

Highlighted node is the most recently expanded split.

Controls

Max depth4

Min samples split8

Impurity metricgini

Min impurity gain0.03

Threshold candidates14

Animation speed620ms

Learning Playground

PatternXOR

Points130

Feature noise18%

Label noise10%

Upload CSV (x1,x2,y)

Mathematical explanation

Impurity is the “mixing” score

A tree chooses the split that reduces impurity the most.

Gini impurity

G=2p(1-p)

If all labels are class 1 or class 0, then $p\in\{0,1\}$ and impurity becomes 0. Mixed nodes have higher impurity.

Entropy (optional)

H=-p\log p-(1-p)\log(1-p)

Entropy measures uncertainty. Trees can use entropy or Gini—your slider switches the scoring rule.

Impurity gain (what we maximize)

Gain=I_{parent}-\Big(\frac{n_L}{n}I_L+\frac{n_R}{n}I_R\Big)

The algorithm keeps expanding the node with the biggest impurity gain that also satisfies your split constraints.

Step-by-step workflow

Input → Processing → Learning → Prediction → Output

Input

Features (x1, x2) + labels (y)

Processing

Try candidate splits and compute impurity gain

Learning

Expand the next node that improves purity most

Prediction

Follow splits until a leaf

Output

Class + confidence from leaf frequency

Real-world applications

Where decision trees are used

Explainability + fast rules.

Credit decisions

Use splits on income, age, debt ratio to approve or decline.

Medical triage

Decision paths create human-auditable rules.

Fraud detection

Explainable rules for suspicious transactions.

Why companies like them

• Interpretable: you can read the decision path.
• Handles non-linear boundaries naturally.
• Can be fast at inference (just follow splits).

Visualization

State transitions + region heatmap

How the model’s shape evolves.

Impurity “trend” across steps

Chart

What to click for intuition

Use Step Forward to watch how regions change from a coarse guess (root leaf) into a more refined partition (deeper splits).

Click the plot after a few steps: the same point will jump between regions if the tree has not expanded enough yet.

Code implementation

Python example

Clear and beginner-friendly.

Python (tiny CART-style)

python

# Decision Tree (from scratch, tiny CART-style demo)
import math

def gini(labels):
    n = len(labels)
    if n == 0: return 0.0
    p1 = sum(labels) / n
    return 2 * p1 * (1 - p1)

def split(points, axis, thr):
    left = [p for p in points if (p["x1"] if axis=="x1" else p["x2"]) <= thr]
    right = [p for p in points if (p["x1"] if axis=="x1" else p["x2"]) > thr]
    return left, right

def best_split(points, min_samples=8):
    impurity_before = gini([p["y"] for p in points])
    best = None
    for axis in ["x1","x2"]:
        values = sorted({p[axis] for p in points})
        for i in range(len(values)-1):
            thr = (values[i] + values[i+1]) / 2
            left, right = split(points, axis, thr)
            if len(left) < min_samples or len(right) < min_samples:
                continue
            labelsL = [p["y"] for p in left]
            labelsR = [p["y"] for p in right]
            impurity_after = (len(left)/len(points))*gini(labelsL) + (len(right)/len(points))*gini(labelsR)
            gain = impurity_before - impurity_after
            if best is None or gain > best["gain"]:
                best = {"axis": axis, "thr": thr, "gain": gain}
    return best

Optional frameworks

In production you’ll typically use libraries like scikit-learn. The lab code exists to make the “split choice” logic visible, not to replace battle-tested implementations.

Mental map

• Choose an impurity metric.
• Find the best split threshold.
• Recurse with stopping rules.
• Prune or limit depth to avoid overfitting.

Common mistakes & limitations

How decision trees fail

Overfitting happens easily when trees get too deep.

Overfitting (too much depth)

A deep tree can memorize noise. Watch the region grid become very jagged, especially with label noise.

Noisy data

If labels are inconsistent, impurity gain becomes unstable. Use min impurity gain and min samples split.

Axis-aligned limitation

Each split is a rectangle boundary (x1 or x2). Some patterns need many splits to approximate.

Quick fix recipe

• Reduce max depth.

• Increase min samples split.

• Raise min impurity gain to avoid tiny improvements.

Final summary

Cheat sheet + interview questions

Memorize these patterns.

Key takeaways

• Trees expand nodes by maximizing impurity gain.
• Each split adds an axis-aligned rectangle boundary.
• Depth limits/pruning help generalization.

Important formulas

Gini=2p(1-p)

Gain=I_p-\Big(\frac{n_L}{n}I_L+\frac{n_R}{n}I_R\Big)

Interview questions

• Why do impurity metrics matter?
• What causes overfitting in trees?
• What’s the difference between Gini and entropy?

Loading Lab...

Machine Learning • Decision Trees

Split the space, then vote

Decision trees build a rule list by repeatedly choosing the next split that reduces impurity. In the lab, each step expands one node—until the leaves become confident.

Click the plot to infer with the current tree

Beginner friendly

What are Decision Trees?

A flowchart for predictions.

A decision tree asks a sequence of questions like a “choose-your-path” story. Each question is a split on one feature (e.g., $x_1 \le t$ ). At the end, each leaf outputs a class.

Real-life analogy

Think of triage in a clinic: “Is temperature high?” → “Is cough severe?” → then decide the next action.

Visual diagram

A tree turns data into regions

Every split carves a rectangle.

Processing view

For every node, we try candidate thresholds and compute how “mixed” the labels are (impurity). We pick the split that makes left/right nodes more pure.

Prediction view

At inference time, you follow splits until you reach a leaf. The leaf’s class is a majority vote based on its training subset.

Core intuition

Why splitting helps

Uncertainty → less uncertainty.

What you can watch in this lab

• Regions change after each expansion step.
• The tree diagram grows node-by-node.
• Impurity is lowered as steps progress.

Split intuition

“Pick the split that makes leaves calmer.”

In every step, the lab chooses a split with the highest impurity gain under your constraints.

Current step explanation

Computing tree…

Interactive simulation

Decision Tree Builder

Expand one node per step.

step: 0/0

Loading Lab...

Tree visual

Computing…

Highlighted node is the most recently expanded split.

Controls

Max depth4

Min samples split8

Impurity metricgini

Min impurity gain0.03

Threshold candidates14

Animation speed620ms

Learning Playground

PatternXOR

Points130

Feature noise18%

Label noise10%

Upload CSV (x1,x2,y)

Mathematical explanation

Impurity is the “mixing” score

A tree chooses the split that reduces impurity the most.

Gini impurity

G=2p(1-p)

If all labels are class 1 or class 0, then $p\in\{0,1\}$ and impurity becomes 0. Mixed nodes have higher impurity.

Entropy (optional)

H=-p\log p-(1-p)\log(1-p)

Entropy measures uncertainty. Trees can use entropy or Gini—your slider switches the scoring rule.

Impurity gain (what we maximize)

Gain=I_{parent}-\Big(\frac{n_L}{n}I_L+\frac{n_R}{n}I_R\Big)

The algorithm keeps expanding the node with the biggest impurity gain that also satisfies your split constraints.

Step-by-step workflow

Input → Processing → Learning → Prediction → Output

Input

Features (x1, x2) + labels (y)

Processing

Try candidate splits and compute impurity gain

Learning

Expand the next node that improves purity most

Prediction

Follow splits until a leaf

Output

Class + confidence from leaf frequency

Real-world applications

Where decision trees are used

Explainability + fast rules.

Credit decisions

Use splits on income, age, debt ratio to approve or decline.

Medical triage

Decision paths create human-auditable rules.

Fraud detection

Explainable rules for suspicious transactions.

Why companies like them

• Interpretable: you can read the decision path.
• Handles non-linear boundaries naturally.
• Can be fast at inference (just follow splits).

Visualization

State transitions + region heatmap

How the model’s shape evolves.

Impurity “trend” across steps

Chart

What to click for intuition

Use Step Forward to watch how regions change from a coarse guess (root leaf) into a more refined partition (deeper splits).

Click the plot after a few steps: the same point will jump between regions if the tree has not expanded enough yet.

Code implementation

Python example

Clear and beginner-friendly.

Python (tiny CART-style)

python

# Decision Tree (from scratch, tiny CART-style demo)
import math

def gini(labels):
    n = len(labels)
    if n == 0: return 0.0
    p1 = sum(labels) / n
    return 2 * p1 * (1 - p1)

def split(points, axis, thr):
    left = [p for p in points if (p["x1"] if axis=="x1" else p["x2"]) <= thr]
    right = [p for p in points if (p["x1"] if axis=="x1" else p["x2"]) > thr]
    return left, right

def best_split(points, min_samples=8):
    impurity_before = gini([p["y"] for p in points])
    best = None
    for axis in ["x1","x2"]:
        values = sorted({p[axis] for p in points})
        for i in range(len(values)-1):
            thr = (values[i] + values[i+1]) / 2
            left, right = split(points, axis, thr)
            if len(left) < min_samples or len(right) < min_samples:
                continue
            labelsL = [p["y"] for p in left]
            labelsR = [p["y"] for p in right]
            impurity_after = (len(left)/len(points))*gini(labelsL) + (len(right)/len(points))*gini(labelsR)
            gain = impurity_before - impurity_after
            if best is None or gain > best["gain"]:
                best = {"axis": axis, "thr": thr, "gain": gain}
    return best

Optional frameworks

In production you’ll typically use libraries like scikit-learn. The lab code exists to make the “split choice” logic visible, not to replace battle-tested implementations.

Mental map

• Choose an impurity metric.
• Find the best split threshold.
• Recurse with stopping rules.
• Prune or limit depth to avoid overfitting.

Common mistakes & limitations

How decision trees fail

Overfitting happens easily when trees get too deep.

Overfitting (too much depth)

A deep tree can memorize noise. Watch the region grid become very jagged, especially with label noise.

Noisy data

If labels are inconsistent, impurity gain becomes unstable. Use min impurity gain and min samples split.

Axis-aligned limitation

Each split is a rectangle boundary (x1 or x2). Some patterns need many splits to approximate.

Quick fix recipe

• Reduce max depth.

• Increase min samples split.

• Raise min impurity gain to avoid tiny improvements.

Final summary

Cheat sheet + interview questions

Memorize these patterns.

Key takeaways

• Trees expand nodes by maximizing impurity gain.
• Each split adds an axis-aligned rectangle boundary.
• Depth limits/pruning help generalization.

Important formulas

Gini=2p(1-p)

Gain=I_p-\Big(\frac{n_L}{n}I_L+\frac{n_R}{n}I_R\Big)

Interview questions

• Why do impurity metrics matter?
• What causes overfitting in trees?
• What’s the difference between Gini and entropy?