Decision trees: entropy and Gini
A decision tree predicts by asking a sequence of yes/no questions about single features, each chosen to make the resulting groups as pure as possible.
Why it matters
Many real datasets are tables with mixed feature types and rules like "if income is low and the loan is large, risk is high". Trees learn such rules automatically, need no feature scaling, and can be read by a person. They are also the building block of random forests and gradient boosting, which win most competitions on tabular data.
The idea
A decision tree asks a series of yes/no questions about features, like 'age < 30?'. At each step it picks the question that makes the groups purest. Purity is measured with Gini impurity or entropy.
The game '20 Questions'. Good questions split the possibilities in useful ways.
In 20 Questions you can ask anything. A tree asks about one feature and one threshold at a time, so a diagonal boundary needs many steps, like a staircase.
How it works
- Start with all the training points in one node and measure how mixed it is with Gini impurity, 1 − Σ pₖ², or with entropy.
- Try every feature and every possible threshold, for example "x < 3?".
- Score each split by the impurity of the two sides, weighted by how many points each side holds. Keep the split with the lowest score.
- Repeat inside each side, and keep splitting.
- Stop when a node is pure, too small, or the tree reaches its maximum depth.
- To predict, follow the questions from the root down to a leaf, and answer with that leaf's majority class (or, for regression, its average value).
Key points
- Gini impurity = 1 − Σ pₖ². 0 is pure; 0.5 is the worst for two classes.
- Each split looks at one feature and one threshold, so boundaries are made of axis-aligned steps.
- No feature scaling needed; mixed feature types are easy.
- A tree grown without limits memorises the training data. Limit the depth or the leaf size, or prune.
- Small changes in the data can change the whole tree: high variance. Forests fix this (next topic).
- Feature importance comes from how much each feature reduces impurity across the tree.
Common mistakes
- Growing trees with no depth limit and trusting the training accuracy.
- Expecting a smooth diagonal boundary from a single tree.
- Reading a tree's splits as causes. A split shows that a feature helps to predict, not that it causes the outcome.
Not true: A tree grown until it fits its training data perfectly is equally accurate on new data.
In fact: A tree with no depth limit memorises the training data, noise included. Limit its depth or its leaf size, or prune it.
Not true: A single decision tree can draw a smooth diagonal boundary.
In fact: Each split tests one feature against one threshold, so the boundary is made of steps along the axes. A diagonal becomes a staircase.
Part of Unit 2: Classical ML, built by you in the free ML Foundations course.