Decision Trees and Random Forest Ensembles in Machine Learning

While linear and logistic regression find flat hyperplane boundaries, real-world data contains non-linear patterns, feature interactions, and hierarchical dependencies. Decision Trees model decisions through intuitive recursive flowcharts, while Random Forests combine hundreds of randomized trees into powerful, robust ensemble systems that consistently dominate tabular machine learning benchmarks.

Decision Tree Mechanics: Recursive Binary Splitting

A Decision Tree makes predictions by passing a sample down from a root node through a sequence of internal decision tests. At each node, the algorithm picks the single feature ( j ) and threshold ( t ) that splits the training samples into two purest child subsets.

Mathematical Splitting Criteria: Entropy vs Gini Impurity

1. Information Gain & Shannon Entropy (Used in ID3 & C4.5)

Entropy measures the degree of disorder, uncertainty, or impurity in a set of training labels ( S ):

Where ( p_i ) is the proportion of samples belonging to class ( i ). If a node contains 50% positive and 50% negative samples, ( H(S) = 1.0 ) (maximum disorder). If all samples belong to the same class, ( H(S) = 0.0 ) (pure).

Information Gain (IG) is the expected reduction in entropy achieved by partitioning on attribute ( A ):

2. Gini Impurity (Used in CART & scikit-learn)

Gini Impurity measures the probability that a randomly chosen element from the set would be incorrectly labeled if it were randomly labeled according to the distribution of labels:

Gini impurity is computationally faster than entropy because it avoids expensive logarithmic calculations while yielding virtually identical tree splits.

The Achilles' Heel: Overfitting & Tree Pruning

A decision tree allowed to grow without constraints will split until every single leaf contains a solitary sample. This produces a tree that has 100% training accuracy but memorizes noise, suffering from severe high variance.

• Pre-Pruning (Early Stopping): Stopping tree growth before full depth is reached by setting constraints: max_depth, min_samples_split, min_samples_leaf, or max_leaf_nodes.
• Post-Pruning (Cost-Complexity Pruning): Growing the tree to full depth, then pruning back branches that contribute minimal validation performance using parameter ( alpha ).

Random Forests: Ensemble Bagging with Feature Randomization

Invented by Leo Breiman in 2001, a Random Forest is an ensemble of decorrelated decision trees that radically reduces variance without increasing bias. It achieves this through two layers of randomization:

Prediction Aggregation: For classification, the forest takes a majority vote: ( hat{y} = ext{mode}(hat{y}_1, dots, hat{y}_B) ). For regression, it computes the mean: ( hat{y} = rac{1}{B} sum_{b=1}^B hat{y}_b ).

Out-Of-Bag (OOB) Evaluation: Free Validation

Because each bootstrap tree uses only ~63% of the dataset, the remaining ~37% of samples left out are called Out-of-Bag (OOB) samples. Evaluating each sample on the subset of trees that never saw it during training produces an unbiased OOB Score, providing built-in cross-validation without needing an external test set!

from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.ensemble import RandomForestClassifier
from sklearn.metrics import classification_report, accuracy_score

# 1. Load Real Diagnostic Dataset
data = load_breast_cancer()
X, y = data.data, data.target
feature_names = data.feature_names

# 2. Train/Test Split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42, stratify=y)

# 3. Train Random Forest with 100 Trees and OOB scoring
rf = RandomForestClassifier(
    n_estimators=100,
    max_depth=6,
    max_features='sqrt',
    oob_score=True,
    random_state=42
)
rf.fit(X_train, y_train)

# 4. Evaluation
test_preds = rf.predict(X_test)
print(f"Random Forest Test Accuracy : {accuracy_score(y_test, test_preds):.2%}")
print(f"Out-Of-Bag (OOB) Validation : {rf.oob_score_:.2%}
")

# 5. Extract Top 5 Most Important Features
importances = rf.feature_importances_
top_indices = importances.argsort()[-5:][::-1]
print("Top 5 Most Discriminative Features:")
for idx in top_indices:
    print(f"  {feature_names[idx]:28s}: {importances[idx]:.4f}")