A decision tree makes predictions by asking a sequence of yes/no questions about the features: is petal length < 2.45 cm? If yes, predict setosa. If no, is petal width < 1.75 cm?, and so on, until a leaf gives the answer. Trees are easy to read, handle mixed feature types, need no scaling, and capture interactions and non-linear effects naturally.
Measuring a good split: impurity
Trees are grown greedily from the top. At each node, try every feature and every threshold, and pick the split that makes the two child nodes as pure as possible (each dominated by one class). Two common impurity measures, where is the fraction of class in a node:
- A pure node (all one class) has Gini 0 and entropy 0.
- A 50/50 node of two classes has Gini 0.5 and entropy 1 bit, the maximum for two classes.
- The quality of a split is the parent's impurity minus the weighted average of the children's (weighted by how many examples go to each). With entropy, that drop is called information gain.
Overfitting, and how to stop it
Keep splitting and a tree can always reach pure leaves, one per training example if necessary: perfect training accuracy, and a model that has memorised noise. Trees are controlled by limiting their maximum depth, requiring a minimum number of examples per leaf, or growing fully and then pruning branches that don't help on validation data. Their boundaries are always made of axis-aligned rectangles, which is a limitation for diagonal boundaries.
A single deep tree is a high-variance model: change a few training examples and the top split can change, and everything below it with it. That instability is a weakness on its own and, as the next lesson shows, a strength when you combine many trees.
A decision tree greedily picks the split that most reduces impurity, then recurses. Deep trees overfit; depth limits and pruning rein them in.