Decision Trees

Learning Objectives

• ✓Compute Gini, Entropy and Information Gain to choose a split
• ✓Understand how CART scans thresholds on numeric features, and the cardinality trap
• ✓Control overfitting with max_depth, min_samples_leaf and pruning
• ✓Assess stability with K-Fold and Stratified K-Fold
• ✓Tune hyperparameters with GridSearchCV and RandomizedSearchCV

Decision Trees & Split Criteria

A decision tree asks a chain of Yes/No questions, each one splitting the data into two purer branches, and the result is a set of If-Then rules readable in plain language; it needs no scaling and captures nonlinear relationships. Purity is measured by Gini (max 0.5, sklearn's default because it avoids computing a $\log$) or Entropy (max 1.0 bit with two classes). Each node picks the feature-and-threshold pair with the largest Gain.

# 12 patients: 5 High, 7 Low
gini_root = 1 - (5/12)**2 - (7/12)**2         # = 0.486

# Split on "Smoker = Yes?":
#   YES branch (4 High, 1 Low)
#   NO  branch (1 High, 6 Low)
gini_yes = 1 - (4/5)**2 - (1/5)**2            # = 0.320
gini_no  = 1 - (1/7)**2 - (6/7)**2            # = 0.245

gini_child = 5/12 * gini_yes + 7/12 * gini_no # = 0.276
gini_gain  = gini_root - gini_child           # = 0.210 → take this split

Choosing Split Thresholds & the CART Algorithm

A numeric feature has infinitely many thresholds in theory, but you only need the midpoints between consecutive values — with $n$ samples that is $n-1$ candidate thresholds. CART repeats at each node: scan every feature times every threshold, keep the split with the largest Gain, then recurse. The algorithm is greedy, so it only optimizes locally. Watch for cardinality bias: the more distinct values a column has the easier it reaches a high Gain — an ID column would seize the root node immediately.

Controlling Overfitting

A tree left to grow freely splits until each leaf holds a single sample, reaching 100% train accuracy while test sits around 74%. The first approach is to stop early: try max_depth 3–6, min_samples_leaf 10–50, and max_leaf_nodes in place of max_depth — of these min_samples_leaf usually works better because it forces every rule to rest on enough samples. The second approach is post-pruning via ccp_alpha, letting the tree grow fully then removing branches that do not justify their complexity.

from sklearn.tree import DecisionTreeClassifier

for depth in [None, 3, 4, 6]:
    t = DecisionTreeClassifier(max_depth=depth, random_state=42)
    t.fit(X_train, y_train)
    print(f"depth={str(depth):>4}  train={t.score(X_train, y_train):.3f}  "
          f"test={t.score(X_test, y_test):.3f}")

# depth=None  train=1.000  test=0.740   ← memorizes every sample
# depth=   6  train=0.884  test=0.772
# depth=   4  train=0.836  test=0.791   ← narrowest gap
# depth=   3  train=0.801  test=0.778   ← starting to get too crude

tree = DecisionTreeClassifier(max_depth=4, min_samples_leaf=20,
                              random_state=42).fit(X_train, y_train)

Cross-Validation

A single train/test split gives a result that depends on that particular split. K-Fold lets each part serve as the test set exactly once, then reports the mean alongside the standard deviation; K = 5 or 10 is standard. Stratified K-Fold preserves the class ratio within each fold, so it is required on imbalanced data. Every preprocessing step must live inside the pipeline, otherwise information from the test set leaks back into training.

from sklearn.model_selection import cross_val_score, StratifiedKFold
from sklearn.pipeline import make_pipeline
from sklearn.impute import SimpleImputer

# Preprocessing goes INSIDE the pipeline so nothing leaks between folds
pipe = make_pipeline(SimpleImputer(strategy="median"), tree)

skf = StratifiedKFold(n_splits=5, shuffle=True, random_state=42)
scores = cross_val_score(pipe, X, y, cv=skf, scoring='accuracy')
print(f'CV Accuracy: {scores.mean():.3f} ± {scores.std():.3f}')
# [0.79, 0.83, 0.77, 0.81, 0.80] → 0.800 ± 0.020

Hyperparameter Tuning

GridSearchCV walks every combination in the grid, so it is guaranteed to find the best configuration in it, at a cost that multiplies fast. RandomizedSearchCV samples a fixed number of combinations at random and usually does better in large spaces, because only a few parameters actually matter. An efficient routine: sweep randomly and wide to localize the good region, then place a narrow grid around it. Two diagnostic tools go with this: the Learning Curve and the Validation Curve.

from sklearn.model_selection import GridSearchCV, RandomizedSearchCV
from scipy.stats import randint

# Step 1 — wide sweep, only 50 draws instead of the whole space
rand = RandomizedSearchCV(
    DecisionTreeClassifier(random_state=42),
    {'max_depth': randint(2, 20),
     'min_samples_leaf': randint(1, 60),
     'criterion': ['gini', 'entropy']},
    n_iter=50, cv=skf, n_jobs=-1, random_state=42
).fit(X_train, y_train)
print("Good region:", rand.best_params_)

# Step 2 — narrow grid around the region just found
param_grid = {
    'max_depth': [3, 4, 5, 6],
    'min_samples_leaf': [10, 20, 30],
    'criterion': ['gini', 'entropy'],
}  # 4×3×2 = 24 combinations × 5-fold = 120 fits
grid = GridSearchCV(DecisionTreeClassifier(random_state=42),
                    param_grid, cv=skf, n_jobs=-1).fit(X_train, y_train)
print("Best params:", grid.best_params_)
print("Best CV Acc:", grid.best_score_)