Decision Tree (Classification): Complete Guide — Principles, Examples, and Python Implementation

Summary

The decision tree is one of the most popular and intuitive classification algorithms in supervised machine learning. Unlike models such as neural networks or support vector machines, the decision tree offers total transparency: each prediction can be traced and explained along a path of “if-then” rules. This article explores the mathematical principles, the inner workings of the CART algorithm, split criteria (Gini and Shannon entropy), overfitting management through pruning, and provides a complete Python implementation with scikit-learn, including tree visualization and split criterion comparison.

Mathematical Principle of the Classification Decision Tree

The CART Algorithm (Classification And Regression Trees)

The CART algorithm, introduced by Breiman, Friedman, Olshen, and Stone in 1984, constructs the tree in a recursive and greedy manner. At each step, it examines all characteristics and all possible thresholds, then selects the pair (feature, threshold) that maximizes the purity of the resulting subsets.

The process unfolds as follows:

1. Start with the root containing the entire training set.
2. For each feature j and each possible threshold t:
   – Split the data into two subsets: left (Xⱼ ≤ t) and right (Xⱼ > t).
   – Calculate the weighted impurity of the two.
3. Choose the split that minimizes the weighted impurity.
4. Repeat recursively on each subset until a stopping criterion is met.

The Gini Criterion

The Gini index measures the impurity of a node m. For a node containing samples from K classes:

Gini(m) = 1 – Σᵢ₌₁ᴷ pᵢ²

where pᵢ represents the proportion of samples of class i in the node.

Concrete example: a node contains 80 samples of class A and 20 of class B. Then p_A = 0.8 and p_B = 0.2, and:

Gini = 1 – (0.8² + 0.2²) = 1 – (0.64 + 0.04) = 1 – 0.68 = 0.32

A perfectly pure node (all samples belong to the same class) has a Gini index of 0. A maximally impure node (uniform distribution between two classes) has a Gini index of 0.5 (binary case). For K classes, the maximum is 1 – 1/K.

Shannon Entropy

Entropy, inspired by Claude Shannon’s information theory (1948), is another measure of impurity:

H(m) = -Σᵢ₌₁ᴷ pᵢ · log₂(pᵢ)

By convention, we set 0 · log₂(0) = 0.

Revisiting the previous example (80% A, 20% B):

H = -(0.8 · log₂(0.8) + 0.2 · log₂(0.2)) ≈ -(0.8 · (-0.322) + 0.2 · (-2.322)) ≈ 0.258 + 0.464 = 0.722

A pure node has an entropy of 0. A balanced two-class node has a maximum entropy of 1.0 (log₂(2) = 1).

Information Gain

Information Gain quantifies the impurity reduction provided by a split:

IG(parent, children) = Impurity(parent) – Σᵢ (nᵢ / n_parent) · Impurity(childᵢ)

where nᵢ is the number of samples in child subset i.

The CART algorithm systematically seeks the split that maximizes this information gain (or equivalently, that minimizes the weighted impurity of the children).

Why These Two Criteria Give Similar Results

In practice, Gini and entropy very often lead to nearly identical trees. The Gini criterion is slightly faster to compute (no logarithm), while entropy tends to produce slightly more balanced trees. The difference is generally marginal on real datasets.

Intuition: The Decision Tree as a Game of Twenty Questions

Imagine you’re playing twenty questions. Your partner is thinking of an animal, and you have to guess it by asking closed questions (yes/no answers). Your natural strategy will be to ask questions that reduce uncertainty as much as possible at each step.

“Is it a mammal?” is an excellent first question: it eliminates birds, reptiles, fish, and insects all at once. “Is it an animal whose name starts with the letter Z?” is a much less good question: in the worst case, it eliminates almost nothing.

The classification decision tree works exactly this way. Each internal node asks a question of the type “Is feature Xⱼ less than or equal to threshold t?” The question chosen is the one that separates the data into the purest possible two groups. We repeat the process until each leaf contains nearly homogeneous samples.

This analogy explains why decision trees are so popular: they are literally decision flowcharts that any human being can read and understand, without advanced mathematics training.

Complete Python Implementation with scikit-learn

Basic Example with the Wine Dataset

from sklearn.datasets import load_wine
from sklearn.tree import DecisionTreeClassifier, plot_tree
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score, classification_report
import matplotlib.pyplot as plt

# Loading the Wine dataset
wine = load_wine()
X, y = wine.data, wine.target

# Train/test split
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.25, random_state=42, stratify=y
)

# Creating and training the classifier
clf = DecisionTreeClassifier(
    criterion='gini',
    max_depth=4,
    random_state=42
)
clf.fit(X_train, y_train)

# Predictions and evaluation
y_pred = clf.predict(X_test)
print(f"Accuracy : {accuracy_score(y_test, y_pred):.4f}")
print(f"\nClassification Report :\n{classification_report(y_test, y_pred, target_names=wine.target_names)}")

# Tree visualization
plt.figure(figsize=(20, 10))
plot_tree(
    clf,
    feature_names=wine.feature_names,
    class_names=wine.target_names,
    filled=True,
    rounded=True,
    fontsize=10
)
plt.title("Decision Tree — Wine Dataset (max_depth=4, Gini)")
plt.tight_layout()
plt.show()

Decision Boundary Visualization

import numpy as np
from sklearn.datasets import make_classification

# Generate synthetic 2D data for visualization
X_2d, y_2d = make_classification(
    n_samples=500,
    n_features=2,
    n_informative=2,
    n_redundant=0,
    n_clusters_per_class=1,
    random_state=42
)

# Training
clf_2d = DecisionTreeClassifier(max_depth=5, random_state=42)
clf_2d.fit(X_2d, y_2d)

# Grid for boundary visualization
xx, yy = np.meshgrid(
    np.linspace(X_2d[:, 0].min() - 0.5, X_2d[:, 0].max() + 0.5, 500),
    np.linspace(X_2d[:, 1].min() - 0.5, X_2d[:, 1].max() + 0.5, 500)
)
Z = clf_2d.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)

plt.figure(figsize=(10, 7))
plt.contourf(xx, yy, Z, alpha=0.3, cmap='RdYlBu')
plt.scatter(X_2d[:, 0], X_2d[:, 1], c=y_2d, edgecolors='black', cmap='RdYlBu', s=50)
plt.xlabel("Feature 1")
plt.ylabel("Feature 2")
plt.title("Decision Boundary — Classification Tree (max_depth=5)")
plt.colorbar(label="Predicted Class")
plt.show()

Gini vs Entropy Comparison

from sklearn.model_selection import cross_val_score

# Systematic comparison on the Wine dataset
results = {}
for crit in ['gini', 'entropy']:
    model = DecisionTreeClassifier(criterion=crit, random_state=42)
    scores = cross_val_score(model, X, y, cv=5, scoring='accuracy')
    results[crit] = scores
    print(f"{crit.capitalize()} : mean={scores.mean():.4f} (±{scores.std():.4f})")

# Comparison of tree depths
for crit in ['gini', 'entropy']:
    model = DecisionTreeClassifier(criterion=crit, random_state=42)
    model.fit(X_train, y_train)
    print(f"{crit.capitalize()} : tree depth = {model.get_depth()}, "
          f"number of leaves = {model.get_n_leaves()}")

This code reveals an interesting fact: on the Wine dataset, both criteria produce nearly identical performance. The Gini criterion is marginally faster in training time, but the difference is imperceptible on modestly-sized datasets.

Hyperparameter Guide

The power of the decision tree depends largely on proper hyperparameter tuning. Here are the most important ones:

criterion

• Values: 'gini' (default) or 'entropy'
• Role: Determines the impurity function used to evaluate the quality of a split.
• Advice: Start with 'gini'. If results are unsatisfactory, try 'entropy'. The difference is usually minimal.

max_depth

• Values: integer (default: None, no limit)
• Role: Limits the maximum depth of the tree.
• Advice: This is the most important hyperparameter for controlling overfitting. Start with values between 3 and 7, then adjust via cross-validation. A tree without a depth limit often memorizes the training data.

min_samples_split

• Values: integer ≥ 2 (default: 2) or float between 0 and 1
• Role: Minimum number of samples required to split an internal node.
• Advice: Increasing this value (e.g., to 10 or 20) forces the tree to be less deep and generalize more.

min_samples_leaf

• Values: integer ≥ 1 (default: 1) or float between 0 and 1
• Role: Minimum number of samples required in a leaf.
• Advice: Very useful for smoothing predictions in low-density regions. Values of 5 to 10 work well in practice.

max_features

• Values: integer, float, 'sqrt', 'log2', or None (default: None)
• Role: Maximum number of features examined at each split.
• Advice: None examines all features (default behavior). 'sqrt' or 'log2' are relevant when the number of features is high — this is the strategy used by random forests.

ccp_alpha (Cost-Complexity Pruning)

• Values: float ≥ 0 (default: 0.0)
• Role: Minimal Cost-Complexity Pruning parameter. The larger the value, the more the tree is pruned.
• Advice: This is the most rigorous pruning method. You can use clf.cost_complexity_pruning_path(X_train, y_train) to obtain the series of candidate alphas, then select the best one via cross-validation.

# Cost-complexity pruning example
path = clf.cost_complexity_pruning_path(X_train, y_train)
ccp_alphas = path.ccp_alphas[:-1]  # Exclude the last value

models = []
for alpha in ccp_alphas[:20]:  # Test the first 20 values
    tree = DecisionTreeClassifier(ccp_alpha=alpha, random_state=42)
    tree.fit(X_train, y_train)
    models.append((alpha, tree))

# Visualization of accuracy/complexity tradeoff
train_scores = [m.score(X_train, y_train) for _, m in models]
test_scores = [m.score(X_test, y_test) for _, m in models]

plt.figure(figsize=(10, 5))
plt.plot(ccp_alphas[:20], train_scores[:20], label='Training', marker='o')
plt.plot(ccp_alphas[:20], test_scores[:20], label='Test', marker='s')
plt.xlabel('ccp_alpha')
plt.ylabel('Accuracy')
plt.title('Cost-Complexity Pruning: bias-variance tradeoff')
plt.legend()
plt.xscale('log')
plt.grid(True, alpha=0.3)
plt.show()

Advantages and Limitations of the Classification Decision Tree

Advantages

• Total interpretability: The tree can be visualized and understood by non-experts. Each prediction is justifiable by a rule path.
• No normalization necessary: Unlike SVMs or k-nearest neighbors, decision trees are invariant to monotonic transformations of features.
• Natural handling of categorical and numerical variables.
• Implicit feature selection: The tree only uses relevant features, automatically ignoring noise.
• Robustness to outliers: Extreme values do not significantly affect the tree structure.
• Non-parametric: No assumptions about the underlying data distribution.

Limitations

• Overfitting: This is the main defect. A deep tree without regularization memorizes the training data and generalizes poorly. Pruning is indispensable.
• Instability: A slight variation in training data can produce a radically different tree. It is precisely this instability that random forests exploit.
• Orthogonal boundaries: The tree partitions the space into hyperplanes perpendicular to the axes. To capture diagonal relationships, it needs significant depth.
• Bias toward features with many modalities: The information criterion (entropy) favors features with a large number of unique values.
• Difficulty with extrapolation: Leaves always predict the mean of training classes; the tree cannot extrapolate or interpolate beyond these values.

4 Concrete Use Cases

1. Medical Diagnosis

The decision tree is used to build diagnostic trees in medicine. For example, classifying a tumor as benign or malignant from cytological features (mean radius, texture, perimeter, area, smoothness, etc.). The major advantage is transparency: a doctor can follow the decision path and understand exactly why the model made a particular diagnosis. This is crucial in a field where interpretability is as important as accuracy.

2. Banking Fraud Detection

In the financial sector, decision trees are used to classify transactions as legitimate or fraudulent. Features include amount, time, geographic location, merchant type, and account history. Although random forests and gradient boosting generally outperform a single tree in accuracy, a pruned tree remains extremely useful for establishing explicit detection rules audited by regulators.

3. Customer Segmentation in Marketing

A decision tree can identify the customer profiles most likely to respond positively to a marketing campaign. By segmenting the customer base according to demographic criteria (age, income, location) and behavioral criteria (purchase frequency, average basket), the tree produces clearly defined segments that can be acted upon by sales teams. This approach is particularly valued for its ability to communicate actionable insights.

4. Churn Prediction (Attrition)

In service industries (telecommunications, SaaS, streaming), predicting which customers are at risk of canceling is a strategic challenge. Decision tree classification identifies the most discriminating factors: contract length, number of calls to customer service, recent service usage, etc. The output is directly actionable: “Customers with a contract of less than 6 months AND more than 3 calls to support have a 78% churn risk.”

Conclusion

Decision tree classification remains a fundamental tool of supervised machine learning. Its strength lies in its unique balance between conceptual simplicity and predictive power. Although a single tree is rarely the most performant model on complex tasks, it is the fundamental building block of tree ensembles (random forests, gradient boosting) that dominate data science competitions.

Mastering the decision tree — its split criteria, hyperparameters, pruning mechanisms — is an indispensable prerequisite for understanding and effectively using these more advanced ensemble methods.

See Also

• Two Modules to Properly Secure Your Web Browser
• Testing the Primality of $2n^2 – 1$ in Python: Complete and Optimized Guide