CART (Classification and Regression Trees) › Example
Machine Learning from ScratchAll chapters CART (Classification and Regression Trees) › ExampleOne section · Sections in this chapter5 / 9 ↓
Reading tools Definitions & inline links
Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.
Article links
Make inline references clickable
Let's work through a concrete example to understand how CART builds a decision tree step by step. We'll use a simple classification problem with two features and three classes.
Dataset Setup
Consider the following training data:
| Sample | Feature 1 (X₁) | Feature 2 (X₂) | Class |
|---|---|---|---|
| 1 | 2.5 | 1.2 | A |
| 2 | 3.1 | 2.8 | B |
| 3 | 1.8 | 3.2 | A |
| 4 | 4.2 | 1.5 | C |
| 5 | 2.9 | 2.1 | B |
| 6 | 1.5 | 2.9 | A |
| 7 | 3.8 | 2.3 | C |
| 8 | 2.2 | 1.8 | A |
Step 1: Calculate Initial Gini Impurity
First, we calculate the Gini impurity for the root node (all samples):
- Class A: 4 samples (50%)
- Class B: 2 samples (25%)
- Class C: 2 samples (25%)
Step 2: Evaluate All Possible Splits
Split on X₁ ≤ 2.5:
Left child (X₁ ≤ 2.5): Samples 1, 3, 6, 8
- Class A: 4 samples (100%)
- Class B: 0 samples (0%)
- Class C: 0 samples (0%)
Right child (X₁ > 2.5): Samples 2, 4, 5, 7
- Class A: 0 samples (0%)
- Class B: 2 samples (50%)
- Class C: 2 samples (50%)
Weighted Gini impurity:
Information gain:
Split on X₂ ≤ 2.0:
Left child (X₂ ≤ 2.0): Samples 1, 4, 8
- Class A: 2 samples (66.7%)
- Class B: 0 samples (0%)
- Class C: 1 sample (33.3%)
Right child (X₂ > 2.0): Samples 2, 3, 5, 6, 7
- Class A: 2 samples (40%)
- Class B: 2 samples (40%)
- Class C: 1 sample (20%)
Weighted Gini impurity:
Information gain:
Step 3: Select Best Split
The split on X₁ ≤ 2.5 provides the highest information gain (0.375), so we choose this as our first split.
Step 4: Continue Building the Tree
We now have two child nodes. The left child (X₁ ≤ 2.5) is already pure (all samples are class A), so it becomes a leaf node. The right child (X₁ > 2.5) still has mixed classes and needs further splitting.
For the right child, we repeat the process:
- Current samples: 2, 4, 5, 7
- Classes: B, C, B, C
The best split would be on X₂ ≤ 2.1, which would separate the classes perfectly.
Final Tree Structure
Root: X₁ ≤ 2.5?
├── Yes → Class A (Leaf)
└── No → X₂ ≤ 2.1?
├── Yes → Class B (Leaf)
└── No → Class C (Leaf)
This example demonstrates how CART greedily selects splits that maximize information gain at each step, ultimately creating a tree that perfectly classifies the training data.