Course contentsShow
← Machine Learning and Deep Learning
Lesson 289 of 3,5386. Tree-Based MethodsFree lesson

The CART Algorithm

Classification and Regression Trees algorithm: greedy recursive binary splitting and stopping criteria.

The CART Algorithm

What you'll learn: How the Classification and Regression Trees (CART) algorithm builds decision trees using a simple, greedy approach.

What is CART?

CART stands for Classification and Regression Trees—it's the most popular algorithm for actually building decision trees. While you've learned about splitting criteria like Gini impurity and entropy, CART is the systematic procedure that uses these criteria to construct the entire tree.

Greedy Recursive Binary Splitting

CART works through a greedy approach: at each step, it picks the single best split without looking ahead to future consequences. Here's the process:

  1. Start at the root: Consider all features and all possible split points
  2. Find the best split: Test every feature and threshold, choosing the one that gives the lowest impurity (Gini) or highest information gain (entropy)
  3. Create two child nodes: Split the data into left and right branches based on this optimal split
  4. Recurse: Repeat steps 1-3 on each child node independently

Think of it like organizing a messy closet: you first make the biggest, most helpful division (shirts vs. pants), then within each section, you make the next most helpful split (short-sleeve vs. long-sleeve), and so on. You're not planning five divisions ahead—just choosing what helps most right now.

Stopping Criteria

CART doesn't split forever. It stops when:

  • Maximum depth is reached
  • Minimum samples per node threshold is hit
  • A node becomes pure (all samples same class)
  • No split improves impurity beyond a minimum threshold

Without stopping criteria, trees would memorize training data perfectly—classic overfitting!

Key Takeaway: CART builds trees top-down using greedy recursive binary splitting, making locally optimal decisions at each node until stopping criteria are met.