Decision Tree

A decision tree classifies a point by playing twenty questions with it. Starting at the root, it asks a yes/no question like petal_width < 0.8, follows the matching branch, asks again, and keeps going until it reaches a leaf that just outputs a label. The cleverness is entirely in *which* question to ask at each node — and that choice is made greedily, one node at a time.

What makes a split good — impurity

A node is pure when every point in it shares one label, and impure when its labels are mixed. The tree scores impurity and picks the split that drops it the most. The most common score is Gini impurity: for a node with class proportions p₁, p₂, …, it is 1 - Σ pᵢ². Pure nodes score 0; a perfectly even 50/50 mix of two classes scores 0.5 (its maximum for two classes).

A worked split

Say a node holds 8 points: 4 class A and 4 class B — Gini 1 - (0.5² + 0.5²) = 0.5. We test the split x < 3. It sends {4 A, 1 B} left and {0 A, 3 B} right. We score each child and weight by how many points fall in it:

left  (5 pts): 1 - ((4/5)^2 + (1/5)^2) = 1 - (0.64 + 0.04) = 0.32
right (3 pts): 1 - ((0/3)^2 + (3/3)^2) = 1 - (0 + 1)        = 0.00
weighted = (5/8)*0.32 + (3/8)*0.00 = 0.20

Impurity fell from 0.50 to a weighted 0.20 — a gain of 0.30. The tree compares this against every other candidate feature < threshold and keeps the single best one, then recurses on each child.

1. 1At the current node, try every feature and every candidate threshold.
2. 2For each candidate, split the points and compute the weighted child impurity.
3. 3Keep the split with the largest impurity drop; create two child nodes.
4. 4Recurse on each child until it is pure, too small, or hits the depth limit.
5. 5Make each leaf predict the majority class of the points that reached it.