Decision Trees: Learning from Data

1. Introduction: Beyond Linear Boundaries

In the previous lesson, we learned Logistic Regression, which maps continuous scores to probabilities via the Sigmoid curve. However, Logistic Regression assumes a linear relationship between input features and the log-odds of the positive class. In original feature space, its decision boundary is strictly a flat hyperplane ($\mathbf{w}^T \mathbf{x} + b = 0$).

In reality, human decision-making and natural phenomena rarely follow flat diagonal hyperplanes. Consider how a loan officer evaluates an applicant:

• "Is the applicant's credit score greater than 700?" $\rightarrow$ If Yes, check: "Is monthly income $\ge$ BDT 60,000?"
• If No, check: "Do they have a co-signer with verified collateral?"

This sequence of hierarchical, conditional if-else questions mirrors the internal mechanics of a Decision Tree. Decision Trees are intuitive, non-parametric supervised algorithms that recursively partition feature space into orthogonal, axis-aligned boxes. They solve both Classification and Regression tasks without requiring feature scaling or linear assumptions.

2. The Architectural Anatomy of a Decision Tree

To master Decision Trees, one must understand their structural building blocks:

3. Classification Trees vs. Regression Trees

While both tree variants share identical recursive hierarchical structures, their split criteria and prediction engines differ fundamentally:

4. Splitting Criteria: Gini Impurity, Shannon Entropy & Information Gain

How does a Decision Tree decide which feature and which numerical threshold to split on? It systematically tests every candidate threshold for every feature and picks the split that yields the highest reduction in impurity.

4.1 Gini Impurity ($I_G$)

Gini Impurity measures the probability that a randomly chosen sample from a node would be incorrectly classified if randomly labeled according to the class distribution within that node:

Where $K$ is the number of classes, and $p_k$ is the fraction of samples in node $t$ belonging to class $k$.

4.2 Shannon Entropy ($H$)

Borrowed from Claude Shannon's Information Theory, Entropy measures the average level of "information", surprise, or uncertainty in a random variable:

By convention, if $p_k = 0$, then $0 \log_2(0) \equiv 0$. For a pure binary node, $H(t) = 0$ bits. For a 50/50 binary split, $H(t) = -[0.5 \log_2(0.5) + 0.5 \log_2(0.5)] = 1.0$ bit.

4.3 Information Gain (Impurity Reduction)

When a parent node $t$ is split into left child $t_L$ and right child $t_R$, the Information Gain (IG) is the difference between parent impurity and weighted child impurities:

5. The Recursive Binary Splitting Algorithm

Decision Trees grow using a Greedy Top-Down Recursive Partitioning strategy:

1. Greedy Choice: At each node, the algorithm identifies the single best feature and split point that maximizes immediate impurity reduction. It does not look ahead to see if a sub-optimal current split might lead to a superior overall tree later.
2. Continuous Thresholds: For a continuous feature with $N$ unique values, the algorithm sorts the values and tests the $N-1$ midpoints between adjacent samples: $\theta_i = \frac{x_{(i)} + x_{(i+1)}}{2}$.
3. Recursion: The data is partitioned into two disjoint subsets. The algorithm repeats the exact same procedure recursively on both subsets.
4. Stopping Conditions: Recursion stops when a node is 100% pure ($I = 0$), reaches max_depth, has fewer samples than min_samples_split, or the impurity reduction drops below min_impurity_decrease.

6. Regression Trees & Piecewise Constant Prediction

In Regression Trees, the splitting objective is to minimize the total Mean Squared Error:

Where $\bar{y}_t$ is the arithmetic average of target values in node $t$.

7. Hyperparameter Tuning & Overfitting Control

If allowed to grow without constraints, a Decision Tree will continue splitting until every single training point occupies its own leaf node ($I_G = 0$). This achieves 100% training accuracy but results in catastrophic overfitting—memorizing noise and failing on new test data.

8. Complete Scikit-Learn Python Pipeline

Below is a complete, production-grade workflow demonstrating synthetic classification data creation, 70/15/15 stratified partitioning, validation depth tuning, tree visualization, and out-of-sample evaluation:

# Step 1: Scientific & Machine Learning Imports
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, plot_tree
from sklearn.metrics import (
    accuracy_score, precision_score, recall_score,
    f1_score, classification_report, confusion_matrix
)

# Step 2: Generate Synthetic Customer Churn Dataset (1,000 samples, 5 features)
X, y = make_classification(
    n_samples=1000,
    n_features=5,
    n_informative=3,
    n_redundant=1,
    n_classes=2,
    weights=[0.70, 0.30],
    random_state=42
)
feature_names = ["income", "age", "credit_score", "visits", "prev_default"]

# Step 3: Stratified 70/15/15 Partitioning (Train, Validation, Test)
X_train, X_temp, y_train, y_temp = train_test_split(
    X, y, test_size=0.30, random_state=42, stratify=y
)
X_val, X_test, y_val, y_test = train_test_split(
    X_temp, y_temp, test_size=0.50, random_state=42, stratify=y_temp
)
print(f"Partition Sizes: Train={len(X_train)}, Val={len(X_val)}, Test={len(X_test)}")

# Step 4: Hyperparameter Tuning: Select Optimal Depth on Validation Set
candidate_depths = [1, 2, 3, 4, 5, 7, 10, None]
best_depth = 3
best_val_f1 = 0.0

for d in candidate_depths:
    tree = DecisionTreeClassifier(
        criterion="gini",
        max_depth=d,
        min_samples_leaf=5,
        random_state=42
    )
    tree.fit(X_train, y_train)
    val_pred = tree.predict(X_val)
    f1 = f1_score(y_val, val_pred, zero_division=0)
    if f1 > best_val_f1:
        best_val_f1 = f1
        best_depth = d

print(f"Selected Optimal Depth: {best_depth} (Validation F1 = {best_val_f1:.3f})")

# Step 5: Refit Selected Model on Combined Development Set (Train + Val)
X_dev = np.vstack([X_train, X_val])
y_dev = np.concatenate([y_train, y_val])

final_model = DecisionTreeClassifier(
    criterion="gini",
    max_depth=best_depth,
    min_samples_leaf=5,
    random_state=42
)
final_model.fit(X_dev, y_dev)

# Step 6: Final Unseen Test Evaluation
y_test_pred = final_model.predict(X_test)
print(f"\n=== FINAL TEST EVALUATION (Depth = {best_depth}) ===")
print(f"Accuracy  : {accuracy_score(y_test, y_test_pred):.4f}")
print(f"Precision : {precision_score(y_test, y_test_pred, zero_division=0):.4f}")
print(f"Recall    : {recall_score(y_test, y_test_pred, zero_division=0):.4f}")
print(f"F1-Score  : {f1_score(y_test, y_test_pred, zero_division=0):.4f}")
print(f"\nConfusion Matrix:\n{confusion_matrix(y_test, y_test_pred)}")

# Step 7: Inspect Feature Importances (Mean Decrease in Impurity)
importances = pd.DataFrame({
    "Feature": feature_names,
    "Importance": final_model.feature_importances_
}).sort_values(by="Importance", ascending=False)
print(f"\nFeature Importance Breakdown:\n{importances}")

9. Feature Importance: Mechanics & Pitfalls

Scikit-Learn computes feature importance using Mean Decrease in Impurity (MDI):

The score represents the total weighted impurity reduction brought about by feature $x_j$ normalized to sum to $1.0$.

10. Decision Tree Regression with Scikit-Learn

Predicting continuous outcomes (e.g. apartment price based on square footage) using DecisionTreeRegressor:

from sklearn.tree import DecisionTreeRegressor
from sklearn.metrics import mean_absolute_error, mean_squared_error, r2_score

# Fit Regression Tree with bounded depth to prevent extreme step overfitting
reg_tree = DecisionTreeRegressor(
    max_depth=3,
    min_samples_leaf=5,
    criterion="squared_error",
    random_state=42
)
reg_tree.fit(X_train[:, :1], y_train)

# In-Sample & Out-of-Sample Predictions
y_pred = reg_tree.predict(X_test[:, :1])
print(f"MAE : {mean_absolute_error(y_test, y_pred):.2f}")
print(f"RMSE: {np.sqrt(mean_squared_error(y_test, y_pred)):.2f}")
print(f"R²  : {r2_score(y_test, y_pred):.3f}")

11. Advantages & Architectural Limitations

12. Head-to-Head: Logistic Regression vs. Decision Trees

13. Summary & Key Takeaways