Supervised Learning

If-Then Rules That Learn — The Most Interpretable Algorithm

Decision trees split data using simple if-then-else rules. They are easy to visualize, handle mixed data types, and form the basis for powerful ensemble methods.

Gini Impurity — Measuring node purity for optimal splits
Information Gain — Entropy-based splitting criterion
Pruning — Preventing overfitting by limiting tree complexity

"A decision tree is the only ML algorithm that can be explained to your grandmother."

Prerequisites

Before diving in, make sure you're comfortable with:

Basic Probability — Probability distributions, conditional probability
Information Theory Basics — Entropy (will be covered here)
Python — Lists, dictionaries, basic OOP concepts
Classification — What labels are, what accuracy means

Learning Objectives

After completing this tutorial, you will be able to:

Explain how decision trees recursively partition feature space
Compute Gini impurity and information gain (entropy)
Understand the CART algorithm and how it builds trees
Apply pruning strategies to prevent overfitting
Interpret feature importance from trained decision trees
Know when to use decision trees vs ensemble methods

Decision Trees — Complete Guide

Decision trees make predictions by learning simple rules from data — like a flowchart of if-then-else decisions.

How Decision Trees Work

Splitting Criteria

Gini Impurity

Information Gain (Entropy)

CART Algorithm

from sklearn.tree import DecisionTreeClassifier, export_text
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

iris = load_iris()
X_train, X_test, y_train, y_test = train_test_split(iris.data, iris.target, test_size=0.2)

tree = DecisionTreeClassifier(max_depth=3, criterion='gini', random_state=42)
tree.fit(X_train, y_train)
print(f"Accuracy: {tree.score(X_test, y_test):.3f}")
print(export_text(tree, feature_names=iris.feature_names))

for name, imp in zip(iris.feature_names, tree.feature_importances_):
    print(f"{name}: {imp:.3f}")

Pruning

Feature Importance

Real-World Applications

Credit Scoring

Banks use decision trees (and their ensemble variants) to assess loan eligibility. The tree learns rules like "income > $50K AND debt-to-income < 30% → approve." Interpretability is crucial for regulatory compliance — regulators require explaining why a loan was denied.

Medical Diagnosis

Decision trees provide clear diagnostic paths: "IF fever AND cough THEN flu." Doctors can follow the logic and validate it against medical knowledge. The transparency makes trees preferred over black-box models in clinical settings.

Customer Segmentation

Marketing teams use decision trees to identify customer segments. The rules are directly actionable: "IF age < 30 AND online_activity > 5 hours/day THEN target with social media ads."

Manufacturing Quality Control

Decision trees classify products as defective based on sensor readings. The rules identify which measurements are most predictive of defects, guiding process improvements.

Fraud Detection

Financial institutions use decision trees for initial fraud screening. The interpretable rules help investigators understand why a transaction was flagged, speeding up the investigation process.

Common Mistakes & How to Avoid Them

Mistake 1: Not pruning the tree

Problem: An unpruned tree grows until every leaf is pure — memorizing noise
Solution: Use max_depth, min_samples_leaf, or cost-complexity pruning (ccp_alpha)

Mistake 2: Using default parameters

Problem: Default settings often produce overfitting (no depth limit, min_samples=1)
Solution: Always tune max_depth (3-10), min_samples_split (5-20), min_samples_leaf (2-10)

Mistake 3: Trusting feature importance blindly

Problem: MDI feature importance is biased toward high-cardinality features (e.g., unique IDs)
Solution: Use permutation importance for more reliable estimates, especially with categorical features

Mistake 4: Using single decision tree for production

Problem: Single trees are unstable — small data changes create very different trees
Solution: Use ensemble methods (Random Forest, XGBoost) that average many trees

Mistake 5: Ignoring class imbalance

Problem: Trees favor majority class when classes are imbalanced
Solution: Use class_weight='balanced' or resample minority class

Interview Questions

Q1: What is the difference between Gini impurity and entropy? A: Both measure node impurity. Gini = is faster to compute; Entropy = comes from information theory. In practice, they produce very similar trees. CART uses Gini; ID3/C4.5 use entropy.

Q2: Why are decision trees unstable? A: Small changes in data can cause very different splits at the root, cascading to completely different trees. This high variance is why we use ensemble methods (Random Forest, Gradient Boosting) that average many trees.

Q3: How does pruning help prevent overfitting? A: Pruning removes branches that provide little predictive power. Pre-pruning limits tree growth (max_depth, min_samples). Post-pruning grows a full tree then removes branches using a validation set or cost-complexity criterion.

Q4: What is the computational complexity of building a decision tree? A: At each node, we evaluate all features and all split points. For N samples and d features: O(N × d × log N) per split, with O(N × d × log N) total for the tree. This is efficient compared to many other algorithms.

Q5: How do decision trees handle missing values? A: Some implementations (C4.5, XGBoost) handle missing values by: (1) sending them down both branches with weighted fractions, (2) learning the optimal direction for missing values, (3) using surrogate splits (backup splits that approximate the primary split).

Q6: What are the advantages of decision trees over logistic regression? A: Trees handle nonlinear relationships without feature engineering, work with mixed data types (numerical + categorical), provide interpretable rules, require no feature scaling, and naturally handle feature interactions.

Q7: When should you use a single decision tree vs an ensemble? A: Single trees: when interpretability is critical (medical, legal), small datasets, or as a baseline. Ensembles: when prediction accuracy matters more than interpretability, large datasets, or when stability is important.

Practice Exercise

Challenge: Decision Tree Analysis

from sklearn.tree import DecisionTreeClassifier, plot_tree
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split, cross_val_score
import matplotlib.pyplot as plt

# Load data
data = load_breast_cancer()
X_train, X_test, y_train, y_test = train_test_split(data.data, data.target, test_size=0.2, random_state=42)

# Test different max_depth values
for depth in [2, 3, 5, 10, None]:
    tree = DecisionTreeClassifier(max_depth=depth, random_state=42)
    cv_scores = cross_val_score(tree, X_train, y_train, cv=5)
    tree.fit(X_train, y_train)
    test_score = tree.score(X_test, y_test)
    print(f"Depth={str(depth):>4s}: CV={cv_scores.mean():.3f}±{cv_scores.std():.3f}, Test={test_score:.3f}")

# Best model visualization
best_tree = DecisionTreeClassifier(max_depth=3, random_state=42)
best_tree.fit(X_train, y_train)

plt.figure(figsize=(20, 10))
plot_tree(best_tree, feature_names=data.feature_names, class_names=data.target_names,
          filled=True, rounded=True, fontsize=8)
plt.title("Decision Tree for Breast Cancer Diagnosis")
plt.tight_layout()
plt.savefig("decision_tree.png", dpi=150)
plt.show()

# Feature importance
importances = best_tree.feature_importances_
for name, imp in sorted(zip(data.feature_names, importances), key=lambda x: -x[1])[:10]:
    print(f"  {name}: {imp:.3f}")

Bonus challenges:

Compare Gini vs Entropy criteria — do they produce different trees?
Implement post-pruning using cost-complexity pruning
Visualize the decision boundaries using matplotlib

Comparison Table

Decision Trees vs Other Algorithms

Aspect	Decision Tree	Random Forest	Logistic Regression
Interpretability	★★★★★ (rules)	★★★☆☆ (aggregate)	★★★★★ (coefficients)
Accuracy	★★★☆☆	★★★★★	★★★★☆
Overfitting Risk	High (without pruning)	Low (averaging)	Low (regularization)
Feature Scaling	Not required	Not required	Required
Nonlinear	Yes (naturally)	Yes	No (without features)

Key Formulas Reference

Formula	Expression	Context
Gini Impurity		Splitting criterion (CART)
Entropy		Splitting criterion (ID3/C4.5)
Information Gain		Best split selection
Cost-Complexity		Pruning criterion
Feature Importance		MDI importance

Key Takeaways

What to Learn Next

-> Random Forest Ensemble of decision trees for better accuracy and stability.

-> XGBoost Gradient boosting taken to the extreme — state-of-the-art performance.

-> Ensemble Methods Bagging, boosting, and stacking for stronger models.

Decision Trees — Complete Guide with Visualizations