Definition
A decision tree is a model that predicts by asking a series of yes-or-no questions about the features, following a path from the root to a leaf. It learns which questions to ask by choosing, at each step, the split that best separates the classes, using measures such as Gini impurity or information gain.
In simple words
It's a game of 20 Questions. Is income above 50,000? If yes, is the loan under 5 lakhs? If yes, approve. Each question splits people into smaller, more similar groups. Training is just finding the best questions and the best order.
Overview
- A decision tree predicts by asking a sequence of yes/no questions about features.
- Internal nodes test a feature, branches are answers and leaves hold predictions.
- Splits are chosen to make groups as pure as possible, measured by Gini impurity or entropy (classification) or variance (regression).
- Trees need no scaling and handle mixed feature types and non-linear patterns.
- Deep trees overfit; limits such as max_depth and min_samples_leaf, or pruning, control them.
- Their readable rules make them popular where decisions must be explained.
Why it matters
Trees are easy to explain, work with little preparation, and handle both numbers and categories without scaling. They're also the building block of random forests and XGBoost, which are among the best methods for tabular data.
Key terms
- Node and leaf
- A node asks a question about a feature; a leaf gives a prediction.
- Split
- Dividing the data at a node by a rule such as area > 1,200.
- Gini impurity
- A measure of how mixed the classes are in a node; 0 means pure.
- Entropy and information gain
- Entropy measures uncertainty; information gain is how much a split reduces it.
- Maximum depth
- A limit on how many questions a path can ask, controlling complexity.
- Ensemble
- Combining many models, such as many trees in a random forest, for better predictions.
Types
Decision trees come in several types and algorithms, and they are controlled by a few types of setting.
1. Classification trees
Trees whose leaves predict a class.
- How it works: Each split maximises the drop in Gini impurity or entropy; a leaf predicts the majority class of its training examples and its class proportions as probabilities.
- Example: A tree deciding loan approval from income, credit history and existing debts.
- When to use it: Use them for explainable classification and as building blocks of forests and boosting.
2. Regression trees
Trees whose leaves predict a number.
- How it works: Splits minimise the squared error within groups; each leaf predicts the mean target of its examples, giving a step-shaped function.
- Example: Predicting delivery time from distance bands, time of day and weather.
- When to use it: Use them for non-linear numeric prediction, usually inside ensembles.
3. Tree algorithms: ID3, C4.5 and CART
Classic methods for growing trees.
- How it works: ID3 (Quinlan, 1986) uses information gain on categorical features; C4.5 adds gain ratio, numeric features and pruning; CART (Breiman et al., 1984) makes binary splits with Gini or squared error and is what scikit-learn uses.
- Example: scikit-learn's DecisionTreeClassifier implements an optimised version of CART.
- When to use it: Know them to read the literature and understand why trees split the way they do.
4. Pre-pruning (growth limits)
Stopping a tree from growing too far.
- How it works: max_depth, min_samples_split, min_samples_leaf and max_leaf_nodes stop splitting early; values are tuned by cross-validation.
- Example: Limiting a tree to depth 4 so that its rules fit on one page for doctors to review.
- When to use it: Use them to prevent overfitting and to keep trees readable.
5. Post-pruning (cost-complexity pruning)
Growing a full tree and then cutting back branches that do not help.
- How it works: ccp_alpha trades tree size against training error; larger values remove more branches; the best value is chosen on validation data.
- Example: Pruning a 40-leaf tree to 9 leaves with almost no loss in test accuracy.
- When to use it: Use it when you want the simplest tree that performs well.
Explained in detail
How a tree chooses its questions
At each node the algorithm considers every feature and many possible thresholds, and picks the split that makes the resulting groups as pure as possible. Gini impurity for a node is 1 minus the sum of the squared class proportions. A node with 50 per cent of each class has Gini 0.5; a node with only one class has Gini 0. The algorithm picks the split that reduces the weighted impurity of the children the most, then repeats on each child. This greedy, top-down procedure is the CART algorithm, published by Leo Breiman and colleagues in 1984; the ID3 and C4.5 algorithms of Ross Quinlan use entropy instead.
Strengths and weaknesses
| Strengths | Weaknesses |
|---|---|
| Easy to read and explain as a set of if-then rules | A deep tree overfits, memorising noise in the training data |
| No need to scale features | Unstable: small changes in data can produce a very different tree |
| Handles numbers and categories, and non-linear patterns | Predictions are step-like rather than smooth for regression |
| Shows which features matter through feature importance | Biased towards features with many possible split points |
Controlling overfitting
- max_depth limits how many questions a path can ask; depths of 3 to 10 are common starting points.
- min_samples_leaf requires each leaf to contain enough examples, so it cannot be built around one odd case.
- Pruning grows a large tree and then removes branches that do not improve validation performance.
- Choose these settings by comparing validation or cross-validation scores.
Forests and boosting
A single tree is rarely the most accurate model, but combinations of trees are among the most powerful methods for tabular data. A random forest, introduced by Breiman in 2001, trains hundreds of trees, each on a random sample of rows and with a random subset of features at each split, and averages their votes; the randomness makes the trees disagree in useful ways and the average is far more stable. Gradient boosting builds trees one after another, each correcting the errors of the previous ones. Libraries such as XGBoost, LightGBM and CatBoost implement boosting very efficiently and are frequent winners of machine-learning competitions on spreadsheet-style data.
How it works
- Start with all the data at the root.
- Try every possible split of every feature.
- Choose the split that makes the child groups purest.
- Repeat on each child, until a stopping rule applies, such as a maximum depth.
- Each leaf predicts its majority class, or its average for regression.
| Algorithm | Split measure | Note |
|---|---|---|
| ID3 | Information gain | Categorical features |
| C4.5 | Gain ratio | Handles numbers and missing values |
| CART | Gini (or variance for regression) | Used by scikit-learn |
The maths
- The share of class k in this group
A group has 6 "yes" and 4 "no". One split gives left: 5 yes, 0 no. Right: 1 yes, 4 no.
Parent Gini = 1 − (0.6² + 0.4²) = 1 − 0.52 = 0.48 Left Gini = 1 − (1² + 0²) = 0 Right Gini = 1 − (0.2² + 0.8²) = 1 − 0.68 = 0.32 Weighted = (5/10)(0) + (5/10)(0.32) = 0.16 Impurity falls from 0.48 to 0.16, so this is a good split.
In code
scikit-learn can print the learned tree as readable rules. That's the great strength of this model.
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, export_text
iris = load_iris()
X_train, X_test, y_train, y_test = train_test_split(iris.data, iris.target, random_state=0)
tree = DecisionTreeClassifier(max_depth=2, random_state=0).fit(X_train, y_train)
print(export_text(tree, feature_names=list(iris.feature_names)))
print("Test accuracy:", round(tree.score(X_test, y_test), 3))Output
|--- petal width (cm) <= 0.80 | |--- class: 0 |--- petal width (cm) > 0.80 | |--- petal length (cm) <= 4.95 | | |--- class: 1 | |--- petal length (cm) > 4.95 | | |--- class: 2 Test accuracy: 0.895
Common mistakes
- Leaving depth unlimited, which leads to overfitting.
- Trusting one tree too much. Small data changes can produce a very different tree, so forests are more stable.
- Scaling features for a tree. It isn't needed, because trees only compare values with thresholds.
Check yourself
Summary
- A tree predicts through a series of yes-or-no questions.
- It picks splits that make groups purest (Gini or entropy).
- It's easy to read and easy to overfit, so limit its depth.
Finished reading?
Sources: scikit-learn user guide