Decision Trees Advanced Techniques

Duration: 45 min

Decision Trees Advanced Techniques

Duration: 45 min

Cost-Complexity Pruning in Depth

Cost-complexity pruning balances tree accuracy against complexity. The effective alpha (α) parameter controls this tradeoff:

Minimizes: Impurity_error + α × (number of leaves)

How It Works:

1. Start with fully grown tree 2. For each α value, find the subtree minimizing the above criterion 3. This produces a sequence of nested subtrees 4. Use cross-validation to select optimal α

Each α produces a unique optimal subtree. As α increases, trees become simpler (fewer leaves). Plotting tree size vs. α shows this relationship.

Parameter Selection:

Use scikit-learn's cross_val_score with different ccp_alpha values. The α with highest cross-validated accuracy is optimal.

Important: Don't use training accuracy—it always favors larger trees. Cross-validation prevents selecting an overfit tree.

Feature Importance and Selection

Feature importance quantifies each feature's contribution to predictions. In decision trees, this measures information gained by each feature across all splits.

The importance of feature j is:

Importance_j = Σ(gain_t) for all nodes t splitting on feature j

Where gain_t is the information gain at node t.

Uses:

  • Identify key predictive features
  • Detect irrelevant features
  • Focus domain expertise on important features
  • Dimensionality reduction

Important caveat: Feature importance doesn't indicate causation or correlation strength. High importance means the feature helps separate classes in the training data, which doesn't guarantee real-world predictiveness or causality.

Limitations:

  • High-cardinality categorical features may get inflated importance
  • Correlated features split importance unevenly
  • Importance is specific to training data

import numpy as np
import pandas as pd
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
Load real dataset

cancer = load_breast_cancer()
X = cancer.data
y = cancer.target
feature_names = cancer.feature_names
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
Train tree

tree = DecisionTreeClassifier(max_depth=10, random_state=42)
tree.fit(X_train, y_train)
Get feature importances

importances = tree.feature_importances_
indices = np.argsort(importances)[::-1]
Display top features

importance_df = pd.DataFrame({
    'Feature': feature_names,
    'Importance': importances
}).sort_values('Importance', ascending=False)
print("Top 10 Important Features:")
print(importance_df.head(10))
Features with importance > threshold

threshold = np.mean(importances)
important_features = importance_df[importance_df['Importance'] > threshold]
print(f"\nFeatures above mean importance ({threshold:.3f}):")
print(important_features)

Handling Categorical Features

Decision trees naturally handle categorical features by splitting them into subsets. For example, "Color ∈ {red, blue}" vs "Color ∈ {green, yellow}".

Preprocessing Options:

1. One-Hot Encoding: Convert categorical to binary columns. Each category becomes a binary feature. - Pros: Standard, works with all algorithms - Cons: Increases dimensionality, loses ordinal information

2. Label Encoding: Assign integers to categories. Works when order doesn't matter. - Pros: Compact - Cons: Can be misleading (tree treats as ordered)

3. Ordinal Encoding: For ordinal categories (low/medium/high), assign ordered integers preserving semantics.

For decision trees, one-hot encoding is generally safer because trees can split any subset of categories without assuming order.

import pandas as pd
from sklearn.preprocessing import OneHotEncoder
from sklearn.tree import DecisionTreeClassifier
from sklearn.compose import ColumnTransformer
from sklearn.pipeline import Pipeline
Create mixed-type dataset

data = pd.DataFrame({
    'age': [25, 45, 35, 55, 30],
    'color': ['red', 'blue', 'red', 'green', 'blue'],
    'income': [30000, 80000, 50000, 120000, 45000],
    'target': [0, 1, 0, 1, 0]
})
X = data[['age', 'color', 'income']]
y = data['target']
Preprocessing pipeline

preprocessor = ColumnTransformer(
    transformers=[
        ('num', 'passthrough', ['age', 'income']),
        ('cat', OneHotEncoder(drop='first'), ['color'])
    ]
)
Full pipeline

pipeline = Pipeline([
    ('preprocessor', preprocessor),
    ('classifier', DecisionTreeClassifier(random_state=42))
])
pipeline.fit(X, y)
Get feature names after transformation

feature_names_after = (
    ['age', 'income'] + 
    pipeline.named_steps['preprocessor'].named_transformers_['cat'].get_feature_names_out(['color']).tolist()
)
Get importances

importances = pipeline.named_steps['classifier'].feature_importances_
importance_df = pd.DataFrame({
    'Feature': feature_names_after,
    'Importance': importances
}).sort_values('Importance', ascending=False)
print("Feature Importances with Categorical Features:")
print(importance_df)

Tree Ensembles: Random Forests and Beyond

Single trees are unstable and prone to overfitting. Ensembles combine many trees to reduce variance and improve generalization.

Random Forest:

Trains multiple trees on bootstrap samples (random sampling with replacement) of the training data. Each tree uses random feature subsets at splits, decorrelating trees. Predictions average across all trees.

Advantages:

  • Much more stable than single trees
  • Excellent generalization
  • Built-in feature importance
  • Handles high-dimensional data well
  • Parallelizable

Gradient Boosting:

Sequentially trains trees, each correcting previous trees' errors. Each new tree predicts residuals from previous predictions.

Advantages:

  • Superior predictive accuracy
  • Handles complex non-linear relationships
  • Provides feature importance

Disadvantages:

  • Sequential training (slower)
  • More hyperparameters to tune
  • Higher overfitting risk

Extremely Randomized Trees (Extra Trees):

Like Random Forest but splits are randomized, not optimized. Trades some accuracy for faster training.

from sklearn.ensemble import RandomForestClassifier, GradientBoostingClassifier
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
Create dataset

X, y = make_classification(
    n_samples=1000, n_features=20, n_informative=10,
    n_classes=2, random_state=42
)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
Single tree baseline

single_tree = DecisionTreeClassifier(max_depth=10, random_state=42)
single_tree.fit(X_train, y_train)
single_accuracy = accuracy_score(y_test, single_tree.predict(X_test))
Random Forest

rf = RandomForestClassifier(n_estimators=100, max_depth=10, random_state=42, n_jobs=-1)
rf.fit(X_train, y_train)
rf_accuracy = accuracy_score(y_test, rf.predict(X_test))
Gradient Boosting

gb = GradientBoostingClassifier(n_estimators=100, learning_rate=0.1, random_state=42)
gb.fit(X_train, y_train)
gb_accuracy = accuracy_score(y_test, gb.predict(X_test))
print(f"Single Tree Accuracy: {single_accuracy:.3f}")
print(f"Random Forest Accuracy: {rf_accuracy:.3f}")
print(f"Gradient Boosting Accuracy: {gb_accuracy:.3f}")
Feature importances

importance_comparison = pd.DataFrame({
    'Feature': [f'F{i}' for i in range(X.shape[1])],
    'Single Tree': single_tree.feature_importances_,
    'Random Forest': rf.feature_importances_,
    'Gradient Boosting': gb.feature_importances_
})
print("\nTop 5 Features by Each Model:")
for model in ['Single Tree', 'Random Forest', 'Gradient Boosting']:
    top_features = importance_comparison.nlargest(5, model)[['Feature', model]]
    print(f"\n{model}:")
    print(top_features)

Limitations of Decision Trees

While powerful, trees have important limitations:

Bias Toward Balanced Features: Trees tend to favor features that naturally create balanced splits, even if less important for prediction.

Bias Toward High-Cardinality Features: Features with many unique values can create many splits, inflating their importance despite potentially being less predictive.

Instability: Small training data changes cause different trees. Bootstrap-based ensembles mitigate this.

Greedy Construction: Splits are locally optimal, not globally optimal. A globally better split might exist.

Linear Relationships: Trees create step-function approximations of linear relationships, requiring many splits and deep trees.

Regression Extrapolation: Tree regression never extrapolates beyond training data range (predictions capped at max/min training values).

Demonstrate tree instability

np.random.seed(42)
bootstrap_accuracies = []
Train multiple trees on different bootstrap samples

for seed in range(50):
    # Bootstrap sample
    indices = np.random.choice(len(X_train), size=len(X_train), replace=True)
    X_boot = X_train[indices]
    y_boot = y_train[indices]
    
    # Train tree
    tree_boot = DecisionTreeClassifier(max_depth=10, random_state=seed)
    tree_boot.fit(X_boot, y_boot)
    
    # Evaluate
    acc = accuracy_score(y_test, tree_boot.predict(X_test))
    bootstrap_accuracies.append(acc)
print(f"Single Tree Accuracy Range: {min(bootstrap_accuracies):.3f} - {max(bootstrap_accuracies):.3f}")
print(f"Single Tree Std Dev: {np.std(bootstrap_accuracies):.4f}")
print(f"Random Forest Std Dev (more stable): ~0.01")
Demonstrate linear relationship problem

X_linear = np.random.randn(200, 1)
y_linear = 2  X_linear.ravel() + np.random.randn(200)  0.5
X_lin_train, X_lin_test, y_lin_train, y_lin_test = train_test_split(
    X_linear, y_linear, test_size=0.2, random_state=42
)
from sklearn.tree import DecisionTreeRegressor
from sklearn.linear_model import LinearRegression
from sklearn.metrics import r2_score
tree_reg = DecisionTreeRegressor(max_depth=3, random_state=42)
tree_reg.fit(X_lin_train, y_lin_train)
tree_r2 = r2_score(y_lin_test, tree_reg.predict(X_lin_test))
lin_reg = LinearRegression()
lin_reg.fit(X_lin_train, y_lin_train)
lin_r2 = r2_score(y_lin_test, lin_reg.predict(X_lin_test))
print(f"\nLinear Data - Tree R²: {tree_r2:.3f}, Linear Model R²: {lin_r2:.3f}")
print("Linear models better capture linear relationships")

Gradient Boosting in Depth

Gradient Boosting builds trees sequentially, each correcting previous residuals. Unlike Random Forest (parallel independent trees), boosting is sequential.

How Gradient Boosting Works:

1. Fit initial tree to target y 2. Compute residuals: r = y - predictions 3. Fit next tree to residuals 4. Add new tree's predictions (scaled by learning rate) to overall prediction 5. Repeat steps 2-4

Learning rate (shrinkage) controls contribution of each tree. Lower rates (0.01-0.1) improve generalization but require more iterations.

Advantages:

  • Superior predictive accuracy
  • Natural feature importance
  • Handles mixed feature types
  • Works for regression and classification

Disadvantages:

  • Sequential (slow to train)
  • More hyperparameters to tune
  • Prone to overfitting if not careful
  • Less interpretable than single trees

from sklearn.ensemble import GradientBoostingClassifier
Gradient Boosting with tuned hyperparameters

gb = GradientBoostingClassifier(
    n_estimators=200,
    learning_rate=0.05,  # Lower rate, more conservative
    max_depth=4,
    min_samples_split=5,
    subsample=0.8,  # Use 80% of samples for each tree
    random_state=42
)
gb.fit(X_train, y_train)
gb_pred = gb.predict(X_test)
gb_accuracy = accuracy_score(y_test, gb_pred)
print(f"Gradient Boosting Accuracy: {gb_accuracy:.3f}")
Feature importance

gb_importance = pd.DataFrame({
    'Feature': feature_names,
    'Importance': gb.feature_importances_
}).sort_values('Importance', ascending=False)
print("GB Feature Importance:")
print(gb_importance.head())

XGBoost and LightGBM: Production-Grade Gradient Boosting

Popular implementations optimized for speed and performance:

XGBoost (eXtreme Gradient Boosting):

  • Regularization built-in (L1/L2 penalties)
  • Handles missing values automatically
  • Parallel tree construction
  • Production-proven

LightGBM (Light Gradient Boosting Machine):

  • Faster training (leaf-wise tree growth vs level-wise)
  • Lower memory usage
  • Better for large datasets
  • Growing adoption

XGBoost (requires: pip install xgboost)

from xgboost import XGBClassifier
xgb = XGBClassifier(
    n_estimators=200,
    learning_rate=0.05,
    max_depth=4,
    random_state=42,
    n_jobs=-1
)
xgb.fit(X_train, y_train)
xgb_pred = xgb.predict(X_test)
xgb_accuracy = accuracy_score(y_test, xgb_pred)
print(f"XGBoost Accuracy: {xgb_accuracy:.3f}")

Algorithm Comparison: When to Use What

Decision Trees:

  • Use when interpretability is paramount (regulatory requirement)
  • Small datasets
  • When you need to understand exact decision logic

Random Forest:

  • Default for tabular data
  • Good accuracy, fast training
  • Reduces overfitting dramatically vs single tree
  • Less interpretable

Gradient Boosting:

  • Need maximum predictive accuracy
  • Willing to tune hyperparameters
  • Larger datasets (1000+ samples)
  • More training time acceptable

Logistic Regression:

  • Linear relationships
  • Need interpretable coefficients
  • Resource-constrained
  • When simplicity is valued

Benchmark comparison

from sklearn.metrics import accuracy_score, f1_score
models = {
    'Decision Tree': DecisionTreeClassifier(max_depth=10, random_state=42),
    'Random Forest': RandomForestClassifier(n_estimators=100, max_depth=10, random_state=42),
    'Gradient Boosting': GradientBoostingClassifier(n_estimators=100, learning_rate=0.1, random_state=42),
    'Logistic Regression': LogisticRegression(max_iter=1000, random_state=42)
}
results = []
for name, model in models.items():
    model.fit(X_train, y_train)
    y_pred = model.predict(X_test)
    
    acc = accuracy_score(y_test, y_pred)
    f1 = f1_score(y_test, y_pred)
    
    results.append({'Model': name, 'Accuracy': acc, 'F1-Score': f1})
    print(f"{name}: Accuracy={acc:.3f}, F1={f1:.3f}")
results_df = pd.DataFrame(results).sort_values('Accuracy', ascending=False)
print("\nRanked by Accuracy:")
print(results_df)

Avoiding Common Decision Tree Pitfalls

1. Overfitting without Pruning:

Solution: Use cross-validation to select max_depth, min_samples_split

2. Biased Toward High-Cardinality Features:

Features with many unique values get inflated importance. Solution: Use Permutation Importance instead of built-in importance.

from sklearn.inspection import permutation_importance
Permutation importance (more robust)

perm_importance = permutation_importance(
    tree, X_test, y_test, n_repeats=10, random_state=42
)
perm_importance_df = pd.DataFrame({
    'Feature': feature_names,
    'Importance': perm_importance.importances_mean
}).sort_values('Importance', ascending=False)

3. Ignoring Feature Scaling:

Trees are scale-invariant, but when comparing with other algorithms, scale matters.

4. Not Handling Multicollinearity:

Correlated features split importance unevenly. Not harmful to predictions but hurts interpretability.

Production Deployment Considerations

Model Serialization:

Save trained models for inference:

import pickle
Save

with open('model.pkl', 'wb') as f:
    pickle.dump(tree, f)
Load

with open('model.pkl', 'rb') as f:
    tree_loaded = pickle.load(f)

Performance Monitoring:

Track metrics on production data. If accuracy drops significantly, retrain.

Inference Speed:

Decision trees predict quickly (O(log n) depth). Suitable for real-time applications.

Explanation Generation:

Extract decision rules from tree for user explanation:

from sklearn.tree import export_text
tree_rules = export_text(tree, feature_names=feature_names)
print(tree_rules)  # Readable decision rules

Key Takeaways

  • Cost-complexity pruning uses cross-validation to balance accuracy and model complexity
  • Feature importance reveals predictive contribution but doesn't imply causation
  • Categorical features should be one-hot encoded for decision trees
  • Tree ensembles (Random Forest, Gradient Boosting) dramatically improve stability and accuracy
  • Trees struggle with linear relationships and can be unstable on single samples
  • Gradient Boosting builds trees sequentially, correcting previous errors
  • Algorithm choice depends on accuracy needs, interpretability, and computational constraints
  • Common pitfalls include overfitting, feature bias, and deployment considerations
  • Production models require monitoring and periodic retraining

Quiz

Q1: In cost-complexity pruning, as α increases, the tree:

  • A) Becomes deeper
  • B) Becomes simpler with fewer leaves ✓
  • C) Gets better training accuracy
  • D) Requires more features

Q2: Feature importance in a decision tree measures:

  • A) Correlation with target
  • B) Total information gain across all splits using that feature ✓
  • C) Frequency of feature appearance
  • D) The feature's p-value

Q3: For categorical features, one-hot encoding is preferred for trees because:

  • A) It reduces dimensionality
  • B) It's faster to compute
  • C) It allows trees to split any subset of categories without assuming order ✓
  • D) It guarantees better accuracy

Q4: Random Forests improve on single trees primarily by:

  • A) Using deeper trees
  • B) Training on more data
  • C) Averaging predictions across many trees trained on bootstrap samples ✓
  • D) Using entropy instead of Gini

Q5: Compared to single decision trees, tree instability means:

  • A) The tree can't make predictions
  • B) Small training changes cause large prediction changes ✓
  • C) The tree always overfits
  • D) Bootstrap aggregation makes instability worse

Q6: For linear relationships, decision trees are inefficient because:

  • A) They can't learn linear patterns
  • B) They require many splits to approximate straight lines ✓
  • C) They always use one-hot encoding
  • D) Their feature importance becomes zero

← Back ▶ Run in Colab