Decision Trees

A decision tree is a supervised learning algorithm that makes predictions by asking a sequence of simple questions. Each question corresponds to a split in the feature space, and the sequence of questions forms a tree structure.

The Idea

Rather than trying to find a single complex mathematical formula to separate the classes, a decision tree divides the problem into smaller, simpler pieces. It looks at all the features and finds the single split (a straight line parallel to an axis) that best separates the data into distinct classes.

It then repeats this process recursively on each side of the split, growing the tree deeper, until the regions are mostly pure (contain only one class) or it reaches a predefined limit.

Information Gain and Impurity

How does the tree decide where to split? It uses a metric called Gini impurity or Entropy to measure how mixed the classes are in a region.

• A region with 100% of a single class has an impurity of 0 (perfectly pure).
• A region with a 50/50 mix of two classes has maximum impurity.

The tree searches for the split that results in the largest drop in impurity, known as Information Gain.

Overfitting

Because decision trees can keep splitting until every single point is isolated in its own perfect box, they are extremely prone to overfitting. A fully grown tree will memorize the training data, capturing all the noise, and perform poorly on new data.

To prevent this, we typically restrict the tree's growth. Two common constraints are:

• Maximum Depth: Limit how many questions the tree can ask sequentially.
• Minimum Samples: Require a node to have a certain number of data points before allowing it to split again.

Using the Visual Lab

In this lab, you can watch a decision tree grow step by step.

1. Feature space: The raw data contains points from two classes.
2. First split: The tree finds the single horizontal or vertical line that best separates the classes, and creates the root node's children.
3. Grow tree: By adjusting the Max depth and Min samples sliders, you can control how aggressively the tree partitions the space. Watch how the 2D regions visually fragment into smaller boxes as the tree deepens.

Try increasing the max depth all the way up. What happens to the regions? Do they look like they capture the general pattern, or are they just drawing boxes around individual isolated points?