Decision TreesSummary
One page to revise from — the ideas first, then the formulas.
- A decision tree predicts by asking yes/no questions about the features, one after another. The first question is the root node, every question is a decision node, and every path ends in a leaf node that holds the prediction.
- Each question compares one feature with a cut-off, like "length ≤ 10.25 cm?". On a chart, every question is a straight cut and every leaf is a box.
- Entropy measures how mixed a box is: 0 when it is pure, and 1 — the largest value for two kinds — for a 50/50 mix.
- Information gain is the entropy before a cut minus the weighted average entropy after it. Training tries every cut on every feature and asks the one with the largest gain.
- Training repeats this inside every new box — recursive partitioning — until the boxes are pure or the tree is deep enough.
- A tree grown until every leaf is pure overfits: perfect on its training data, worse on new data. Pruning (a maximum depth, a minimum leaf size) stops it early.
- Trees are unstable: a small change in the data can change the whole tree. Many trees voting together — a random forest — fix this.
Entropy, two kinds
Information gain