MACHINE LEARNING / 3. DECISION TREES

Decision Trees

Interpretable splits — the building block of ensemble methods

EXPLANATION

A decision tree recursively splits the feature space into regions, making predictions based on the majority class (classification) or mean value (regression) in each region.

At each node, it finds the split that best separates the data. Metrics for finding best split:
• Gini Impurity → measures class mixing. Gini = 1 - Σpᵢ² (used in CART)
• Information Gain / Entropy → entropy = -Σpᵢ·log(pᵢ) (used in ID3, C4.5)
• MSE reduction → for regression trees

Key hyperparameters:
• max_depth → how deep the tree grows. Deeper = more overfit
• min_samples_split → min samples needed to split a node
• min_samples_leaf → min samples in a leaf node

Decision trees are highly interpretable but overfit badly on their own. Their real power comes from ensembles — Random Forest and Gradient Boosting both use trees as base learners.

DATA FLOW

Feature space splitting:

  Is age > 30?
      ├── YES: Is income > 50k?
      │         ├── YES: → Predict "Buy"    (leaf)
      │         └── NO:  → Predict "No Buy" (leaf)
      └── NO:  Is student?
                ├── YES: → Predict "Buy"    (leaf)
                └── NO:  → Predict "No Buy" (leaf)

  Gini at a node: 1 - (p_class1² + p_class2²)
  Pure node (all same class): Gini = 0
  Max impurity (50/50 split): Gini = 0.5

CODE

PYTHON
1from sklearn.tree import DecisionTreeClassifier, DecisionTreeRegressor, export_text, plot_tree
2from sklearn.datasets import make_classification, load_iris
3from sklearn.model_selection import train_test_split
4from sklearn.metrics import accuracy_score
5import matplotlib.pyplot as plt
6
7# ── Classification tree ───────────────────────────────────────────
8iris = load_iris()
9X_train, X_test, y_train, y_test = train_test_split(
10    iris.data, iris.target, test_size=0.2, random_state=42
11)
12
13tree = DecisionTreeClassifier(
14    max_depth=4,              # limit depth to prevent overfitting
15    min_samples_split=10,     # need 10+ samples to split
16    min_samples_leaf=5,       # leaves need 5+ samples
17    criterion="gini",         # "gini" or "entropy"
18    random_state=42,
19)
20tree.fit(X_train, y_train)
21print(f"Accuracy: {accuracy_score(y_test, tree.predict(X_test)):.4f}")
22
23# ── Print the tree as text ────────────────────────────────────────
24print(export_text(tree, feature_names=iris.feature_names))
25
26# ── Visualize the tree ────────────────────────────────────────────
27fig, ax = plt.subplots(figsize=(16, 8))
28plot_tree(tree, feature_names=iris.feature_names,
29          class_names=iris.target_names, filled=True, ax=ax)
30plt.savefig("tree.png", dpi=150, bbox_inches="tight")
31
32# ── Feature importance ────────────────────────────────────────────
33importances = tree.feature_importances_
34for fname, imp in zip(iris.feature_names, importances):
35    print(f"{fname:25s}: {imp:.4f}")
36
37# ── Overfitting vs depth ──────────────────────────────────────────
38train_scores, test_scores = [], []
39for depth in range(1, 20):
40    t = DecisionTreeClassifier(max_depth=depth, random_state=42)
41    t.fit(X_train, y_train)
42    train_scores.append(accuracy_score(y_train, t.predict(X_train)))
43    test_scores.append(accuracy_score(y_test, t.predict(X_test)))
44
45# plot: train goes to 1.0, test peaks then drops → classic overfitting
← PREV2. Logistic RegressionNEXT →4. Random Forest