7333 Module 7 - Decision Trees

Entropy, Gini Coefficient, Partition Trees, Bagging, and Random Forest: A Study Guide

1. Entropy

Definition:

Entropy is a measure of disorder or randomness in a system. In information theory, entropy quantifies the uncertainty associated with a random variable. It is defined mathematically as:

Mathematical Representation: For a discrete random variable \(X\) with possible outcomes \(x_1, x_2, ..., x_n\) and probabilities \(p_1, p_2, ..., p_n\), entropy \(H(X)\) is given by:

\[ H(X) = - \sum_{i=1}^{n} p_i \log_2 p_i \]

Where: - \(p_i\) is the probability of occurrence of outcome \(x_i\) - The base of the logarithm is typically 2 (log base 2), measuring information in bits

Example: Fair Coin Flip If \(X\) represents the outcome of a fair coin flip, then: - \(p(\text{heads}) = 0.5\) - \(p(\text{tails}) = 0.5\)

Applying the entropy formula: \[ H(X) = - (0.5 \log_2 0.5 + 0.5 \log_2 0.5) = 1 \, \text{bit} \]

A higher entropy value indicates more disorder, while a lower entropy value represents more certainty or order.

Coding Representation in Python:

import numpy as np

def entropy(probabilities):
    return -np.sum(probabilities * np.log2(probabilities))

# Example: Fair coin flip
probs = np.array([0.5, 0.5])
print("Entropy:", entropy(probs))  # Output: 1.0

2. Gini Coefficient vs. Gini Impurity

Gini Coefficient (Economics)

The Gini Coefficient measures income inequality in economics. It ranges from 0 (perfect equality) to 1 (maximum inequality).

Gini Impurity (Decision Trees)

Gini Impurity is a measure used in classification problems to quantify how often a randomly chosen element would be incorrectly labeled.

Mathematical Representation: For a classification problem with \(k\) classes and probabilities \(p_1, p_2, ..., p_k\), the Gini impurity \(G(X)\) is calculated as:

\[ G(X) = 1 - \sum_{i=1}^{k} p_i^2 \]

Example: Fair Coin Flip \[ G = 1 - (0.5^2 + 0.5^2) = 0.5 \]

Coding Representation in Python:

def gini_impurity(probabilities):
    return 1 - np.sum(probabilities**2)

# Example: Fair coin flip
probs = np.array([0.5, 0.5])
print("Gini Impurity:", gini_impurity(probs))  # Output: 0.5

3. Partition Trees

Definition:

Partition trees (decision trees) are non-linear classifiers that recursively split data into regions to maximize information gain.

Key Concepts:

• CART (Classification and Regression Trees): The foundation for decision tree algorithms.
• Information Gain: The reduction in entropy or Gini impurity when making a split.
• Stopping Criteria:
  • Minimum information gain threshold
  • Maximum depth
  • Minimum samples per leaf

Coding Representation:

from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

# Load dataset
iris = load_iris()
X_train, X_test, y_train, y_test = train_test_split(iris.data, iris.target, test_size=0.2, random_state=42)

# Train decision tree classifier
clf = DecisionTreeClassifier(max_depth=3, criterion='gini')
clf.fit(X_train, y_train)

print("Decision Tree Score:", clf.score(X_test, y_test))

4. Bagging (Bootstrap Aggregation)

Definition:

Bagging is an ensemble technique that builds multiple models from bootstrap samples and combines their predictions.

Key Concepts:

• Bootstrap Sampling: Randomly selecting samples with replacement.
• Aggregation: Combining multiple models’ predictions (e.g., averaging for regression, majority vote for classification).

Coding Representation:

from sklearn.ensemble import BaggingClassifier

# Bagging with decision trees
bagging_clf = BaggingClassifier(base_estimator=DecisionTreeClassifier(), n_estimators=100, random_state=42)
bagging_clf.fit(X_train, y_train)

print("Bagging Classifier Score:", bagging_clf.score(X_test, y_test))

5. Random Forest

Definition:

Random forest is an extension of bagging that builds multiple decision trees and aggregates their results.

Key Concepts:

• Random Subsampling: Selecting a random subset of data and features.
• Overfitting Prevention: Averaging many trees reduces overfitting.
• Feature Importance: Identifying influential features based on split criteria.

Coding Representation:

from sklearn.ensemble import RandomForestClassifier

# Train Random Forest classifier
rf_clf = RandomForestClassifier(n_estimators=100, random_state=42)
rf_clf.fit(X_train, y_train)

print("Random Forest Score:", rf_clf.score(X_test, y_test))

6. Bagging Exercise

Task:

Replication of Bagging Results Using Scikit-Learn

Summary of Findings from the Paper

Leo Breiman’s 1994 paper on Bagging Predictors introduced bootstrap aggregation (bagging) as a method to improve the accuracy of classifiers and regression models by reducing variance. Key findings include: - Bagging works best for unstable models (e.g., decision trees and neural networks). - Misclassification rates for classification trees dropped significantly across multiple datasets. - 50 bootstrap replicates were commonly used in classification tasks. - 25 bootstrap replicates were used in regression tasks. - The most notable accuracy improvements were seen in classification trees.

---

Replicating the Experiment Using Scikit-Learn

Below is a Python implementation of bagging using a Decision Tree Classifier on the Breast Cancer dataset, following Breiman’s approach.

Implementation in Python

import numpy as np
from sklearn.ensemble import BaggingClassifier
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 dataset
data = load_breast_cancer()
X, y = data.data, data.target

# Split data into training and testing sets
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# Train a single Decision Tree (without bagging)
dt = DecisionTreeClassifier(random_state=42)
dt.fit(X_train, y_train)
y_pred_dt = dt.predict(X_test)
accuracy_dt = accuracy_score(y_test, y_pred_dt)

# Train a BaggingClassifier with 50 bootstrap samples (following Breiman's recommendation)
bagging = BaggingClassifier(base_estimator=DecisionTreeClassifier(), n_estimators=50, random_state=42)
bagging.fit(X_train, y_train)
y_pred_bagging = bagging.predict(X_test)
accuracy_bagging = accuracy_score(y_test, y_pred_bagging)

# Print results
print(f"Accuracy of single Decision Tree: {accuracy_dt:.4f}")
print(f"Accuracy with Bagging (50 estimators): {accuracy_bagging:.4f}")

---

Results & Discussion

• The Decision Tree Classifier will have higher variance and could overfit to training data.
• The Bagging Classifier (50 estimators) improves accuracy by reducing variance, leading to better generalization.
• Breiman’s study found an average misclassification reduction of 20-47% for decision trees with bagging.

---

Discussion Questions for the Live Session

1. In modern applications, would 50 bootstrap replicates still be the best choice?
   Should we use an adaptive method to determine the number of bootstraps dynamically?

2. Does bagging improve interpretability or just accuracy?
   How does bagging affect the interpretability of decision trees, and should we sacrifice interpretability for performance?

3. What are the trade-offs of bagging vs. other ensemble methods like boosting?
   While bagging reduces variance, boosting reduces bias. In what situations should one be preferred over the other?

---

This experiment is an attempt to replicate Breiman’s findings and demonstrates the effectiveness of bagging in improving model accuracy.

Discussion Questions:

• How does the number of bootstrap samples affect model performance?
• What are the trade-offs between bagging and a single decision tree?
• When would you use random forests over bagging?

Summary:

• Entropy quantifies randomness and information gain.
• Gini Impurity measures classification uncertainty.
• Partition Trees recursively split data for decision-making.
• Bagging builds multiple models using bootstrap aggregation.
• Random Forests improve bagging by introducing feature randomness.

Three Relevant Questions for the Professor:

1. Regarding Entropy and Gini Impurity:
   How do we decide when to use entropy versus Gini impurity as the criterion for splitting in a decision tree? Are there specific datasets or conditions where one consistently outperforms the other?

2. On Bagging and Random Forests:
   In practical applications, is there a recommended threshold for the number of bootstrap samples or decision trees in a random forest to balance model performance and computational efficiency?

3. Overfitting in Partition Trees:
   What are the best strategies to prevent overfitting in partition trees besides limiting depth and minimum samples per leaf? Would pruning be preferable to max-depth constraints?

---

Three Key Takeaways from the Asynchronous Work:

1. Information Gain and Model Performance:
   Both entropy and Gini impurity help measure disorder and information gain, which guides decision tree splits. Lower entropy or Gini impurity indicates a more informative decision boundary.

2. Bagging Enhances Generalization:
   Bootstrap aggregation (bagging) reduces overfitting by averaging multiple weak models, creating a more robust and generalizable ensemble model.

3. Random Forests Leverage Feature Randomness:
   Unlike bagging alone, random forests introduce feature randomness in addition to bootstrapped sampling, ensuring that individual decision trees remain uncorrelated, which improves overall predictive accuracy and model robustness.