Decision Trees & Random Forests

Introduction

While linear models like regression are powerful, they assume the relationship between data features is straight and uniform. However, real-world data is often messy, non-linear, and categorical. This is where Decision Trees shine. They mimic human decision-making: asking a series of yes/no questions to arrive at a conclusion.

Imagine a doctor diagnosing a patient: Does the patient have a fever? If yes, do they have a cough? If yes, it might be the flu. This branching logic is exactly how a Decision Tree operates.

But Decision Trees have a fatal flaw: they tend to overcomplicate things and memorize the training data (overfitting). To fix this, we combine hundreds of trees into a Random Forest. A single tree might make a flawed prediction, but a "council" of hundreds of trees voting on the outcome is incredibly robust and accurate. This concept is the foundation of modern tabular machine learning, leading to state-of-the-art algorithms like XGBoost.

Core Concepts Explained Intuitively

Decision Trees: Splitting the Data

A decision tree is built top-down from a root node. The tree evaluates all features and finds the one that best separates the data into distinct classes.

How does the tree know which question to ask first? It uses math to measure "purity." If a split creates a group that is 100% one class (e.g., all patients in this branch have the flu), it is highly pure. If it creates a 50/50 mix, it is highly impure. The tree seeks the split that maximizes purity.

There are two main mathematical ways to measure this impurity:

1. Gini Impurity: Measures the probability of misclassifying a randomly chosen element if it were randomly labeled according to the distribution of labels in the node. A Gini of 0 means perfect purity.
2. Information Gain (Entropy): Rooted in information theory, entropy measures the amount of chaos or unpredictability in a node. The tree tries to maximize Information Gain—which is the reduction in entropy after a split.

The Problem: Overfitting

If you let a Decision Tree grow without limits, it will keep asking questions until every single leaf node contains exactly one data point. It will achieve 100% accuracy on the training data, but it has essentially memorized the dataset. When given new data, it will fail miserably.

The Solution: Ensemble Learning and Random Forests

Ensemble Learning is the concept of combining multiple weak models to create one strong model.

A Random Forest is a specific type of ensemble called Bagging (Bootstrap Aggregating). It works like this:

1. Create hundreds of Decision Trees.
2. Bootstrap: Train each tree on a random subset of the data (with replacement).
3. Feature Randomness: When deciding how to split a node, each tree is only allowed to look at a random subset of the features.
4. Aggregate: For classification, have all trees vote on the final answer. For regression, take the average of all trees.

Because each tree sees slightly different data and different features, they make different mistakes. When they vote, the mistakes cancel out, leaving a highly accurate, generalized prediction.

Boosting: The Next Evolution (XGBoost)

While Random Forests train trees independently in parallel, Boosting trains trees sequentially. Each new tree focuses explicitly on correcting the errors made by the previous tree. XGBoost (Extreme Gradient Boosting) is currently the dominant algorithm for structured/tabular data in machine learning competitions, known for its extreme execution speed and accuracy.

Code Examples

1. Beginner Code Example: A Single Decision Tree

Let's build a simple decision tree classifier using Scikit-Learn.

from sklearn.datasets import load_breast_cancer
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
from sklearn import tree
import matplotlib.pyplot as plt

# Load dataset
data = load_breast_cancer()
X, y = data.data, data.target

# Split data
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# Initialize and train the Decision Tree
# max_depth=3 prevents the tree from growing too deep (preventing overfitting)
clf = DecisionTreeClassifier(max_depth=3, criterion='gini', random_state=42)
clf.fit(X_train, y_train)

# Predict and evaluate
preds = clf.predict(X_test)
print(f"Decision Tree Accuracy: {accuracy_score(y_test, preds) * 100:.2f}%")

# Visualize the tree
plt.figure(figsize=(15, 10))
tree.plot_tree(clf, filled=True, feature_names=data.feature_names, class_names=data.target_names)
plt.title("Visualized Decision Tree")
plt.show()

2. Intermediate Code Example: Random Forest

Now let's see how much better a Random Forest performs on the exact same data.

from sklearn.ensemble import RandomForestClassifier

# Initialize Random Forest with 100 trees
# n_estimators is the number of trees in the forest
rf_clf = RandomForestClassifier(n_estimators=100, random_state=42, n_jobs=-1)

# Train the model
rf_clf.fit(X_train, y_train)

# Predict and evaluate
rf_preds = rf_clf.predict(X_test)
print(f"Random Forest Accuracy: {accuracy_score(y_test, rf_preds) * 100:.2f}%")

# Feature Importance: Random Forests can tell us which features matter most
importances = rf_clf.feature_importances_
top_feature_index = importances.argmax()
print(f"Most important feature for prediction: {data.feature_names[top_feature_index]}")

3. Advanced Code Example: Gradient Boosting with XGBoost

XGBoost is not built into Scikit-Learn, so we use the xgboost library. It requires careful tuning but yields incredible results.

import xgboost as xgb
from sklearn.metrics import log_loss

# XGBoost uses its own optimized data structure called DMatrix
dtrain = xgb.DMatrix(X_train, label=y_train)
dtest = xgb.DMatrix(X_test, label=y_test)

# Define hyperparameters
params = {
    'max_depth': 3,          # Depth of each tree
    'eta': 0.1,              # Learning rate
    'objective': 'binary:logistic', # Binary classification
    'eval_metric': 'logloss' # Evaluation metric
}

# Train the model (boosting for 100 rounds)
num_rounds = 100
xgb_model = xgb.train(params, dtrain, num_rounds)

# Predict (XGBoost outputs probabilities, so we round them to get 0 or 1)
xgb_probs = xgb_model.predict(dtest)
xgb_preds = [1 if prob > 0.5 else 0 for prob in xgb_probs]

print(f"XGBoost Accuracy: {accuracy_score(y_test, xgb_preds) * 100:.2f}%")

Common Mistakes

1. Not Setting max_depth in Decision Trees:

   • Mistake: Initializing DecisionTreeClassifier() without constraints. The tree will grow until every leaf is pure, resulting in massive overfitting.
   • Fix: Always set hyperparameters like max_depth, min_samples_split, or min_samples_leaf to prune the tree and force generalization.

2. Scaling Features for Tree-Based Models:

   • Mistake: Spending time running StandardScaler or MinMaxScaler on data before feeding it to a Random Forest.
   • Fix: Tree-based models are invariant to the scale of the features. A split at Age > 50 is exactly the same conceptually as a split at Scaled_Age > 0.8. You do not need to scale features for trees.

3. Ignoring Feature Importances:

   • Mistake: Treating the Random Forest as a total black box.
   • Fix: Tree ensembles provide a .feature_importances_ attribute. Use this to remove useless features (reducing noise) and to explain the model's logic to stakeholders.

Interview Q&A

Q1: What is the difference between Gini Impurity and Entropy? A1: Both measure the node's impurity. Gini impurity is the probability of incorrectly classifying a randomly chosen element. Entropy is an information theory metric measuring the level of disorder. In practice, they perform very similarly, but Gini is slightly faster to compute because it doesn't require calculating logarithmic functions.

Q2: How does a Random Forest prevent overfitting? A2: By using Bagging (Bootstrap Aggregating) and Feature Randomness. Each tree is trained on a random sample of the data, and at each split, the tree can only choose from a random subset of features. This ensures the trees are de-correlated. Averaging many independent, un-correlated trees reduces the overall variance (overfitting) without increasing bias.

Q3: Contrast Bagging and Boosting. A3: Bagging (e.g., Random Forest) builds multiple independent trees in parallel and averages their predictions. Its main goal is to reduce variance. Boosting (e.g., XGBoost, AdaBoost) builds trees sequentially, where each new tree tries to correct the residual errors of the previous sequence. Its main goal is to reduce bias (and variance, if tuned correctly).

Q4: If a Random Forest is performing poorly, what hyperparameters should you tune? A4:

1. n_estimators: Increasing the number of trees generally improves performance until diminishing returns hit.
2. max_depth: Limiting tree depth controls overfitting.
3. max_features: Adjusting the number of features considered at each split (e.g., sqrt vs log2).

Q5: Can Decision Trees extrapolate data? A5: No. Unlike Linear Regression, which can predict values infinitely high if the input goes up, Decision Trees (and Random Forests) can only predict values within the range of the training data. If a house size is larger than any seen in training, the tree will just drop it into the highest value leaf node it knows.

Practice Problems

1. Problem: Train a Random Forest Regressor to predict housing prices. Extract and plot a bar chart of the top 5 most important features.

   • Hint: Use RandomForestRegressor and the feature_importances_ attribute paired with matplotlib.

2. Problem: Implement a single Decision Tree and intentionally cause it to overfit. Compare its training accuracy to its testing accuracy. Then, apply pruning (max_depth=4) and compare again.

   • Hint: An unconstrained tree will likely have 100% training accuracy but much lower testing accuracy.

3. Problem: Explain in plain English why a Random Forest with 10 trees might perform worse than a single Decision Tree, but a Random Forest with 500 trees will almost certainly perform better.

   • Hint: Think about the concept of the "Wisdom of the Crowds." A small crowd might be biased by a few loud voices.

Summary

• Decision Trees split data sequentially based on questions that maximize Information Gain or minimize Gini Impurity.
• Overfitting is the biggest weakness of single decision trees.
• Random Forests solve this by training hundreds of trees on random subsets of data and features, then voting on the outcome (Bagging).
• XGBoost (Boosting) trains trees sequentially, with each tree fixing the errors of the last, currently dominating tabular data benchmarks.
• Tree models do not require feature scaling and offer excellent interpretability via Feature Importances.