Decision Trees
Study Notes — Machine Learning
1. What Is a Decision Tree?
A decision tree is a supervised machine learning algorithm that models decisions as a tree-like
graph. It learns a hierarchy of if-else questions from data and uses these questions to predict an
outcome for new samples.
Decision trees can be used for both classification (predicting a category) and regression
(predicting a continuous value). They are one of the most interpretable ML models because
their logic can be read top-to-bottom like a flowchart.
2. Anatomy of a Decision Tree
Key components
• Root node — the topmost node; contains the entire dataset and the first (best) split.
• Internal nodes — intermediate nodes where further splits occur based on feature
conditions.
• Branches — the outcomes of a split condition (e.g., Yes/No, <= threshold / > threshold).
• Leaf nodes — terminal nodes that produce the final prediction (class label or numeric
value).
• Depth — the length of the longest path from the root to a leaf.
3. How the Tree Learns (Training)
At each node, the algorithm searches for the best feature and threshold to split the data. 'Best'
is defined by an impurity measure — the goal is to create child nodes that are as pure
(homogeneous) as possible.
Splitting criteria
Gini impurity 1 - Σ(pᵢ²) Probability of misclassifying a random
sample. 0 = perfectly pure node.
Entropy -Σ pᵢ · log₂(pᵢ) Measures disorder/uncertainty in a
node. Used by C4.5 and ID3.
Information gain H(parent) - Σ H(child) Reduction in entropy after a split.
Algorithm maximises this.
MSE (regression) Σ(yᵢ - ŷ)² / n Used for regression trees. Split
minimises mean squared error.
The algorithm is greedy — it picks the locally optimal split at each step (not guaranteed to find
the globally optimal tree). It continues recursively until a stopping criterion is met.
4. Stopping Criteria & Pruning
An unconstrained tree will grow until each leaf contains a single training sample — perfectly
accurate on training data, but extremely overfit. Regularisation is essential.
Pre-pruning (early stopping) — stop growing when:
• Maximum tree depth is reached (e.g., max_depth = 5)
• A node contains fewer than min_samples_split samples
• A split would produce a child with fewer than min_samples_leaf samples
• The improvement in impurity is below a threshold (min_impurity_decrease)
Post-pruning — trim after full growth:
• Cost-complexity pruning (ccp_alpha in sklearn) — removes subtrees that add little
predictive value, penalised by tree size
• Reduced error pruning — remove branches if validation accuracy doesn't decrease
5. Pros and Cons
Pros Cons
Highly interpretable — easy to visualise and Prone to overfitting, especially on noisy or small
explain to non-technical stakeholders datasets
No feature scaling or normalisation required Unstable — small changes in data can produce
very different trees
Handles both numeric and categorical features Biased towards features with more unique values
natively
Implicitly handles missing values Can struggle with diagonal decision boundaries
Useful for feature importance analysis Weaker predictive performance than ensemble
methods
6. Key Algorithms & Variants
• ID3: ID3 — uses entropy & information gain; categorical features only; no pruning.
• C4.5: C4.5 — improves on ID3 with gain ratio, handles numeric features and missing
values.
• CART: CART — uses Gini impurity; produces binary splits; supports both classification
and regression.
• Random Forest: Random Forest — ensemble of many decision trees, each trained on
a bootstrap sample with random feature subsets. Reduces variance and overfitting
drastically.
• Gradient Boosted Trees: Gradient Boosted Trees (XGBoost, LightGBM) — sequential
ensemble where each tree corrects errors of the previous. State-of-the-art for tabular
data.
7. Key Hyperparameters (sklearn)
Parameter Default Effect
max_depth None Limits tree depth. Most important
regularisation knob.
min_samples_split 2 Minimum samples to attempt a split. Higher =
simpler tree.
min_samples_leaf 1 Minimum samples in a leaf. Prevents tiny leaf
nodes.
max_features None Number of features considered at each split.
Adds randomness.
criterion 'gini' Impurity measure: 'gini' or 'entropy' for
classifiers; 'squared_error' for regressors.
ccp_alpha 0.0 Complexity parameter for cost-complexity
pruning. Higher = more pruning.
8. When to Use a Decision Tree
• You need an interpretable, explainable model (e.g., medical, legal, or financial
decisions).
• Your data has non-linear relationships or interactions between features.
• You want a quick baseline model before trying complex ensembles.
• Features are mixed types (numeric and categorical) with no preprocessing overhead.
Avoid single decision trees when you need high predictive accuracy on complex tasks — prefer
Random Forest or gradient boosted trees instead.
Decision Trees — Study Notes