A decision tree is a statistical and machine learning model that makes predictions by splitting data into smaller and smaller groups. Each split asks a question about one variable, such as whether a study time is above 5 hours or whether a tumor size is below 2 cm. The final endpoints, called leaves, give a predicted class or numerical value.
Decision trees matter because they are easy to visualize, explain, and use for both classification and regression problems.
A tree is built by choosing splits that make the resulting groups more pure or more useful for prediction. For classification, common split criteria include Gini impurity and entropy, which measure how mixed the classes are in a node. For regression, a tree often chooses splits that reduce the sum of squared errors within the groups.
Because a tree can become too detailed and memorize training data, pruning and ensemble methods such as random forests are used to improve performance on new data.
Key Facts
- A decision tree predicts by following a path from the root node through decision nodes to a leaf node.
- For classification, a leaf often predicts the most common class among the training examples in that leaf.
- Gini impurity for a node is G = 1 - sum(p_i^2), where p_i is the fraction of examples in class i.
- Entropy for a node is H = -sum(p_i log2(p_i)), where lower entropy means a purer group.
- Information gain is IG = impurity(parent) - weighted average impurity(children).
- Random forests combine many decision trees and often predict by majority vote for classification or averaging for regression.
Vocabulary
- Root node
- The root node is the first node in a decision tree where all training data enter before any splits occur.
- Split
- A split is a rule that divides data into groups based on the value of one feature.
- Leaf node
- A leaf node is an endpoint of the tree that gives the final prediction.
- Impurity
- Impurity measures how mixed the classes are within a node, with lower impurity meaning the node is more uniform.
- Overfitting
- Overfitting happens when a model matches the training data too closely and performs poorly on new data.
Common Mistakes to Avoid
- Choosing the split with the most branches automatically, which is wrong because a split should be judged by how much it improves prediction or reduces impurity.
- Reading every branch in the tree, which is wrong because each prediction follows only one path from the root to one leaf.
- Assuming a deeper tree is always better, which is wrong because very deep trees can memorize noise and overfit the training data.
- Ignoring the size of leaf groups, which is wrong because predictions from very small leaves can be unstable and sensitive to individual data points.
Practice Questions
- 1 A node contains 30 examples: 18 are class A and 12 are class B. Compute the Gini impurity of the node using G = 1 - sum(p_i^2).
- 2 A parent node with 100 examples has Gini impurity 0.48. A split creates a left child with 40 examples and Gini impurity 0.20, and a right child with 60 examples and Gini impurity 0.30. Compute the weighted child impurity and the information gain.
- 3 A decision tree performs very well on training data but much worse on test data. Explain what is likely happening and describe one way to reduce the problem.