Decision Trees &
Random Forests

By the end of this chapter, you will be able to:

Imagine you are a loan officer at a bank. A customer walks in and asks for a ₹5,00,000 personal loan. How do you decide? You might ask: "What is their annual income?" If it's above ₹8,00,000, you feel more confident. Then: "Do they have an existing loan?" If yes, you're cautious. "What's their credit score?" Above 750? Approve. Below 600? Reject.

Congratulations — you just built a decision tree in your head. Decision trees are one of the most natural, interpretable, and powerful machine learning algorithms. They mirror how humans actually make decisions: through a series of yes/no questions that partition the problem space.

Why Study Decision Trees in 2025?

• Interpretability: Trees are "white-box" models — you can trace every decision. Essential in finance, healthcare, and legal domains.
• No Preprocessing: Unlike SVMs and neural networks, trees don't need feature scaling, normalization, or one-hot encoding of ordinal features.
• Non-linearity: Trees capture complex, non-linear decision boundaries effortlessly.
• Foundation for Ensembles: Random Forests, Gradient Boosting (XGBoost, LightGBM, CatBoost) are all built on decision trees. These dominate Kaggle competitions and industry applications.
• Real-time Deployment: A trained tree is just a series of if-else statements — lightning fast at inference.

Chapter Roadmap

We begin by deriving entropy and information gain from scratch, then build the ID3, C4.5, and CART algorithms step by step. We'll work through complete numerical examples by hand, learn pruning strategies, extend to regression trees, and then level up to Random Forests. We'll implement everything from scratch in Python, then use scikit-learn and TensorFlow for production pipelines. Along the way, we'll explore real-world case studies from SBI's credit scoring to Microsoft's Kinect body tracking.

The Origins of Information Theory

The mathematical foundation of decision trees begins with Claude Shannon's groundbreaking 1948 paper "A Mathematical Theory of Communication." Shannon defined entropy as a measure of uncertainty or information content in a random variable. This concept, borrowed from thermodynamics, would become the cornerstone of the ID3 algorithm decades later.

Timeline of Key Developments

Leo Breiman: The Father of Random Forests

Leo Breiman (1928–2005) was a statistician at UC Berkeley whose work transformed machine learning. His 2001 paper "Random Forests" combined two of his earlier ideas — bagging (1996) and random subspace method — into a single, elegant framework. Breiman was also a vocal critic of traditional statistics, arguing in his famous 2001 paper "Statistical Modeling: The Two Cultures" that predictive modeling (algorithmic approach) was often more useful than explanatory modeling (data modeling approach).

J. Ross Quinlan's Legacy

Australian computer scientist J. Ross Quinlan developed both ID3 (1979) and its successor C4.5 (1993). C4.5 was ranked #1 in the "Top 10 Algorithms in Data Mining" by the IEEE International Conference on Data Mining in 2006. Quinlan later developed C5.0, a commercial version with boosting support and faster execution.

What is a Decision Tree?

A decision tree is a flowchart-like structure that maps observations (features) to conclusions (predictions). Think of it as a game of "20 Questions" where each question is carefully chosen to maximally reduce uncertainty about the answer.

The Three Major Algorithms

How Does a Decision Tree Learn?

The learning process follows a greedy, top-down, recursive partitioning strategy called TDIDT (Top-Down Induction of Decision Trees):

1. Start with all training data at the root node
2. Select the best feature (and threshold for continuous features) to split on
3. Create child nodes based on the split
4. Recurse on each child node with its subset of data
5. Stop when a stopping criterion is met (pure node, max depth, min samples, etc.)
6. Assign prediction to leaf nodes (majority class for classification, mean value for regression)

Regression Trees

While classification trees predict discrete labels, regression trees predict continuous values. The key differences:

• Splitting criterion: Instead of Gini or entropy, use variance reduction (or MSE reduction)
• Leaf prediction: Instead of majority vote, predict the mean value of training samples in that leaf
• Everything else stays the same: recursive splitting, pruning, the tree structure itself

Random Forests: The Ensemble Approach

A single decision tree is powerful but unstable — small changes in the data can produce completely different trees (high variance). Random Forests solve this by building many trees and averaging their predictions:

Why Does Random Forest Work?

The magic comes from decorrelation. If all trees are built on the same features, they'll be similar (correlated), and averaging them won't help much. By randomizing features, each tree captures different patterns. When you average many uncorrelated, individually-imperfect estimators, the errors cancel out.

Entropy: Measuring Uncertainty

Entropy quantifies the "impurity" or "disorder" in a dataset. For a random variable with K possible outcomes:

Intuition: Entropy is highest (= log₂K) when all classes are equally likely (maximum uncertainty), and lowest (= 0) when all samples belong to one class (complete certainty).

Binary Entropy Function

For a two-class problem (positive proportion p, negative proportion 1-p):

Information Gain

Information Gain measures how much entropy is reduced after splitting on a feature A:

Gain Ratio

C4.5 normalizes Information Gain by the feature's intrinsic value to avoid bias toward high-cardinality features:

Gini Impurity

CART uses Gini impurity — a faster-to-compute alternative to entropy:

Interpretation: Gini impurity equals the probability that two randomly chosen samples from the node would have different class labels. Perfect purity → Gini = 0.

Variance Reduction (Regression Trees)

Gini vs. Entropy: Mathematical Comparison

Out-of-Bag (OOB) Error Estimation

In bagging, each bootstrap sample contains ~63.2% of the data. The remaining ~36.8% are out-of-bag samples. For each sample xᵢ, we can predict using only the trees where xᵢ was OOB, giving a "free" validation estimate:

Feature Importance Measures

Deriving Entropy from First Principles

We want a function H(p₁, p₂, ..., pₖ) that measures "how surprised we are" by a random event. Shannon showed that the unique function satisfying three natural axioms is entropy.

Deriving Gini Impurity

Deriving the Relationship Between Entropy and Gini

For binary classification with positive proportion p, using the Taylor expansion of log₂(p) around p = 0.5:

Cost-Complexity Pruning Derivation

Example 1: Building a Decision Tree by Hand

H(S) = -(3/5)·log₂(3/5) - (2/5)·log₂(2/5)
     = -(0.6)·(-0.737) - (0.4)·(-1.322)
     = 0.442 + 0.529
     = 0.971 bits

H(Low) = -(1/3)·log₂(1/3) - (2/3)·log₂(2/3)
       = -(0.333)·(-1.585) - (0.667)·(-0.585)
       = 0.528 + 0.390
       = 0.918 bits

IG(S, Income) = 0.971 - [(2/5)·0 + (3/5)·0.918]
              = 0.971 - 0.551
              = 0.420 bits

IG(S, Credit) = 0.971 - [(3/5)·0 + (2/5)·0]
              = 0.971 - 0
              = 0.971 bits ← PERFECT SPLIT!

H(Yes) = -(2/3)·log₂(2/3) - (1/3)·log₂(1/3) = 0.918
H(No)  = -(1/2)·log₂(1/2) - (1/2)·log₂(1/2) = 1.000

IG(S, Employed) = 0.971 - [(3/5)·0.918 + (2/5)·1.000]
                = 0.971 - [0.551 + 0.400]
                = 0.971 - 0.951
                = 0.020 bits

Information Gain Summary:
  Credit Score: 0.971 ← WINNER (highest)
  Income:       0.420
  Employed:     0.020

Result: Split on Credit Score at the root!
  - Credit = Good → Pure leaf: Approve = Yes
  - Credit = Bad  → Pure leaf: Approve = No

Final Tree:
       [Credit Score?]
       /             \
    Good              Bad
     |                 |
  ✅ Yes            ❌ No

Example 2: Gini Impurity Computation

# Parent Gini
Gini(S) = 1 - (3/5)² - (2/5)²
        = 1 - 0.36 - 0.16
        = 0.48

# Split on Credit Score
Gini(Good) = 1 - (3/3)² = 1 - 1 = 0
Gini(Bad)  = 1 - (2/2)² = 1 - 1 = 0

Gini_split = (3/5)·0 + (2/5)·0 = 0
ΔGini = 0.48 - 0 = 0.48

# Split on Income
Gini(High) = 1 - (2/2)² = 0
Gini(Low)  = 1 - (1/3)² - (2/3)² = 1 - 0.111 - 0.444 = 0.444

Gini_split = (2/5)·0 + (3/5)·0.444 = 0.267
ΔGini = 0.48 - 0.267 = 0.213

# Split on Employed
Gini(Yes) = 1 - (2/3)² - (1/3)² = 0.444
Gini(No)  = 1 - (1/2)² - (1/2)² = 0.500

Gini_split = (3/5)·0.444 + (2/5)·0.500 = 0.467
ΔGini = 0.48 - 0.467 = 0.013

# Same winner: Credit Score (ΔGini = 0.48)

Example 3: Random Forest Feature Importance

# Tree 1: Splits on Feature A (ΔGini=0.15), then Feature B (ΔGini=0.10)
# Tree 2: Splits on Feature B (ΔGini=0.20), then Feature C (ΔGini=0.08)
# Tree 3: Splits on Feature A (ΔGini=0.18), then Feature A (ΔGini=0.05)

Total ΔGini per feature:
  Feature A: 0.15 + 0.18 + 0.05 = 0.38
  Feature B: 0.10 + 0.20       = 0.30
  Feature C: 0.08              = 0.08
  Total:                         0.76

Normalized Feature Importance:
  Feature A: 0.38 / 0.76 = 0.500 (50%)
  Feature B: 0.30 / 0.76 = 0.395 (39.5%)
  Feature C: 0.08 / 0.76 = 0.105 (10.5%)

Decision Tree Classifier — Complete Implementation

import numpy as np
from collections import Counter

class Node:
    """Represents a node in the decision tree."""
    def __init__(self, feature=None, threshold=None,
                 left=None, right=None, *, value=None):
        self.feature = feature      # Index of feature to split on
        self.threshold = threshold  # Threshold for the split
        self.left = left            # Left child (feature <= threshold)
        self.right = right          # Right child (feature > threshold)
        self.value = value          # Prediction (for leaf nodes)

    def is_leaf(self):
        return self.value is not None


class DecisionTreeClassifier:
    """Decision Tree Classifier built from scratch.
    
    Implements the CART algorithm with Gini impurity or Entropy.
    Supports both classification and can be extended for regression.
    
    Parameters:
        max_depth (int): Maximum depth of the tree
        min_samples_split (int): Minimum samples needed to split
        criterion (str): 'gini' or 'entropy'
        max_features (int): Max features to consider at each split
    """
    
    def __init__(self, max_depth=100, min_samples_split=2,
                 criterion='gini', max_features=None):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.criterion = criterion
        self.max_features = max_features
        self.root = None
        self.n_classes_ = None
        self.feature_importances_ = None
    
    def fit(self, X, y):
        """Build the decision tree from training data."""
        self.n_classes_ = len(set(y))
        self.n_features_ = X.shape[1]
        self.feature_importances_ = np.zeros(self.n_features_)
        
        # Determine max_features to consider at each split
        if self.max_features is None:
            self.max_features_ = self.n_features_
        else:
            self.max_features_ = min(self.max_features, self.n_features_)
        
        self.root = self._build_tree(X, y, depth=0)
        
        # Normalize feature importances
        total = self.feature_importances_.sum()
        if total > 0:
            self.feature_importances_ /= total
        
        return self
    
    def _build_tree(self, X, y, depth):
        """Recursively build the decision tree."""
        n_samples, n_features = X.shape
        n_classes = len(set(y))
        
        # Stopping conditions
        if (depth >= self.max_depth
            or n_classes == 1
            or n_samples < self.min_samples_split):
            leaf_value = self._most_common_label(y)
            return Node(value=leaf_value)
        
        # Select random subset of features (for Random Forest support)
        feature_indices = np.random.choice(
            n_features, self.max_features_, replace=False
        )
        
        # Find the best split
        best_feature, best_threshold = self._best_split(
            X, y, feature_indices
        )
        
        if best_feature is None:
            leaf_value = self._most_common_label(y)
            return Node(value=leaf_value)
        
        # Split the data
        left_mask = X[:, best_feature] <= best_threshold
        right_mask = ~left_mask
        
        # Track feature importance (Gini importance)
        n_total = len(y)
        n_left = left_mask.sum()
        n_right = right_mask.sum()
        importance = (
            self._impurity(y)
            - (n_left / n_total) * self._impurity(y[left_mask])
            - (n_right / n_total) * self._impurity(y[right_mask])
        )
        self.feature_importances_[best_feature] += importance * n_total
        
        # Recursively build children
        left_child = self._build_tree(X[left_mask], y[left_mask], depth + 1)
        right_child = self._build_tree(X[right_mask], y[right_mask], depth + 1)
        
        return Node(best_feature, best_threshold, left_child, right_child)
    
    def _best_split(self, X, y, feature_indices):
        """Find the best feature and threshold to split on."""
        best_gain = -1
        best_feature, best_threshold = None, None
        
        parent_impurity = self._impurity(y)
        n_total = len(y)
        
        for feature_idx in feature_indices:
            # Get sorted unique thresholds
            thresholds = np.unique(X[:, feature_idx])
            
            for threshold in thresholds:
                left_mask = X[:, feature_idx] <= threshold
                right_mask = ~left_mask
                
                if left_mask.sum() == 0 or right_mask.sum() == 0:
                    continue
                
                # Weighted impurity of children
                n_left = left_mask.sum()
                n_right = right_mask.sum()
                child_impurity = (
                    (n_left / n_total) * self._impurity(y[left_mask])
                    + (n_right / n_total) * self._impurity(y[right_mask])
                )
                
                gain = parent_impurity - child_impurity
                
                if gain > best_gain:
                    best_gain = gain
                    best_feature = feature_idx
                    best_threshold = threshold
        
        return best_feature, best_threshold
    
    def _impurity(self, y):
        """Compute impurity (Gini or Entropy)."""
        counts = np.bincount(y.astype(int))
        probabilities = counts / len(y)
        
        if self.criterion == 'gini':
            return 1.0 - np.sum(probabilities ** 2)
        elif self.criterion == 'entropy':
            # Filter out zero probabilities to avoid log(0)
            probabilities = probabilities[probabilities > 0]
            return -np.sum(probabilities * np.log2(probabilities))
    
    def _most_common_label(self, y):
        """Return the most common class label."""
        counter = Counter(y)
        return counter.most_common(1)[0][0]
    
    def predict(self, X):
        """Predict class labels for samples in X."""
        return np.array([self._traverse_tree(x, self.root) for x in X])
    
    def _traverse_tree(self, x, node):
        """Traverse the tree to make a prediction for a single sample."""
        if node.is_leaf():
            return node.value
        
        if x[node.feature] <= node.threshold:
            return self._traverse_tree(x, node.left)
        else:
            return self._traverse_tree(x, node.right)
    
    def score(self, X, y):
        """Return accuracy on the given data."""
        predictions = self.predict(X)
        return np.mean(predictions == y)
    
    def print_tree(self, node=None, indent=""):
        """Print a text representation of the tree."""
        if node is None:
            node = self.root
        
        if node.is_leaf():
            print(f"{indent}Predict: {node.value}")
            return
        
        print(f"{indent}Feature[{node.feature}] <= {node.threshold:.4f}?")
        print(f"{indent}├── Yes:")
        self.print_tree(node.left, indent + "│   ")
        print(f"{indent}└── No:")
        self.print_tree(node.right, indent + "    ")


# ========== TESTING THE DECISION TREE ==========
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split

# Generate synthetic data
X, y = make_classification(
    n_samples=200, n_features=4, n_informative=3,
    n_redundant=0, random_state=42
)
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42
)

# Train our Decision Tree
dt = DecisionTreeClassifier(max_depth=5, criterion='gini')
dt.fit(X_train, y_train)

print(f"Training Accuracy: {dt.score(X_train, y_train):.4f}")
print(f"Testing Accuracy:  {dt.score(X_test, y_test):.4f}")
print(f"\nFeature Importances: {dt.feature_importances_}")
print(f"\nTree Structure:")
dt.print_tree()

Random Forest Classifier — Complete Implementation

class RandomForestClassifier:
    """Random Forest Classifier built from scratch.
    
    Uses bootstrap aggregating (bagging) with feature randomness.
    Each tree is a DecisionTreeClassifier (from above).
    
    Parameters:
        n_estimators (int): Number of trees in the forest
        max_depth (int): Maximum depth of each tree
        min_samples_split (int): Minimum samples to split a node
        max_features (str or int): 'sqrt', 'log2', or integer
        criterion (str): 'gini' or 'entropy'
        oob_score (bool): Whether to compute OOB score
    """
    
    def __init__(self, n_estimators=100, max_depth=None,
                 min_samples_split=2, max_features='sqrt',
                 criterion='gini', oob_score=False,
                 random_state=None):
        self.n_estimators = n_estimators
        self.max_depth = max_depth if max_depth else 100
        self.min_samples_split = min_samples_split
        self.max_features = max_features
        self.criterion = criterion
        self.oob_score = oob_score
        self.random_state = random_state
        self.trees = []
        self.oob_score_ = None
        self.feature_importances_ = None
    
    def _get_max_features(self, n_features):
        """Determine the number of features to consider."""
        if self.max_features == 'sqrt':
            return int(np.sqrt(n_features))
        elif self.max_features == 'log2':
            return int(np.log2(n_features))
        elif isinstance(self.max_features, int):
            return min(self.max_features, n_features)
        else:
            return n_features
    
    def fit(self, X, y):
        """Build the random forest from training data."""
        if self.random_state:
            np.random.seed(self.random_state)
        
        n_samples, n_features = X.shape
        max_feat = self._get_max_features(n_features)
        
        self.trees = []
        oob_predictions = {}  # {sample_idx: [predictions]}
        
        for i in range(self.n_estimators):
            # Bootstrap sample
            bootstrap_indices = np.random.choice(
                n_samples, size=n_samples, replace=True
            )
            oob_indices = list(
                set(range(n_samples)) - set(bootstrap_indices)
            )
            
            X_bootstrap = X[bootstrap_indices]
            y_bootstrap = y[bootstrap_indices]
            
            # Build tree with feature randomness
            tree = DecisionTreeClassifier(
                max_depth=self.max_depth,
                min_samples_split=self.min_samples_split,
                criterion=self.criterion,
                max_features=max_feat
            )
            tree.fit(X_bootstrap, y_bootstrap)
            self.trees.append(tree)
            
            # Collect OOB predictions
            if self.oob_score and len(oob_indices) > 0:
                oob_preds = tree.predict(X[oob_indices])
                for idx, pred in zip(oob_indices, oob_preds):
                    if idx not in oob_predictions:
                        oob_predictions[idx] = []
                    oob_predictions[idx].append(pred)
        
        # Compute OOB score
        if self.oob_score:
            correct = 0
            total = 0
            for idx, preds in oob_predictions.items():
                majority = Counter(preds).most_common(1)[0][0]
                if majority == y[idx]:
                    correct += 1
                total += 1
            self.oob_score_ = correct / total if total > 0 else 0
        
        # Aggregate feature importances
        self.feature_importances_ = np.mean(
            [tree.feature_importances_ for tree in self.trees],
            axis=0
        )
        
        return self
    
    def predict(self, X):
        """Predict class labels using majority vote."""
        # Get predictions from all trees
        all_predictions = np.array([
            tree.predict(X) for tree in self.trees
        ])  # Shape: (n_estimators, n_samples)
        
        # Majority vote for each sample
        majority_votes = []
        for i in range(X.shape[0]):
            votes = all_predictions[:, i]
            majority = Counter(votes).most_common(1)[0][0]
            majority_votes.append(majority)
        
        return np.array(majority_votes)
    
    def predict_proba(self, X):
        """Predict class probabilities (vote proportions)."""
        all_predictions = np.array([
            tree.predict(X) for tree in self.trees
        ])
        
        probas = []
        for i in range(X.shape[0]):
            votes = all_predictions[:, i]
            counts = Counter(votes)
            prob = [counts.get(c, 0) / self.n_estimators
                    for c in range(self.n_classes_)]
            probas.append(prob)
        
        return np.array(probas)
    
    def score(self, X, y):
        """Return accuracy on the given data."""
        return np.mean(self.predict(X) == y)


# ========== TEST RANDOM FOREST ==========
rf = RandomForestClassifier(
    n_estimators=50, max_depth=10,
    max_features='sqrt', oob_score=True,
    random_state=42
)
rf.fit(X_train, y_train)

print(f"Random Forest Results:")
print(f"Training Accuracy: {rf.score(X_train, y_train):.4f}")
print(f"Testing Accuracy:  {rf.score(X_test, y_test):.4f}")
print(f"OOB Score:         {rf.oob_score_:.4f}")
print(f"Feature Importances: {rf.feature_importances_}")

Regression Tree — From Scratch

class DecisionTreeRegressor:
    """Decision Tree Regressor using variance reduction."""
    
    def __init__(self, max_depth=10, min_samples_split=2):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.root = None
    
    def fit(self, X, y):
        self.root = self._build_tree(X, y, depth=0)
        return self
    
    def _build_tree(self, X, y, depth):
        n_samples = X.shape[0]
        
        # Stopping conditions
        if depth >= self.max_depth or n_samples < self.min_samples_split:
            return Node(value=np.mean(y))
        
        # If variance is very small, stop
        if np.var(y) < 1e-7:
            return Node(value=np.mean(y))
        
        best_feature, best_threshold = self._best_split(X, y)
        
        if best_feature is None:
            return Node(value=np.mean(y))
        
        left_mask = X[:, best_feature] <= best_threshold
        right_mask = ~left_mask
        
        left_child = self._build_tree(X[left_mask], y[left_mask], depth + 1)
        right_child = self._build_tree(X[right_mask], y[right_mask], depth + 1)
        
        return Node(best_feature, best_threshold, left_child, right_child)
    
    def _best_split(self, X, y):
        """Find best split by maximizing variance reduction."""
        best_var_reduction = -1
        best_feature, best_threshold = None, None
        parent_var = np.var(y)
        n = len(y)
        
        for feature_idx in range(X.shape[1]):
            thresholds = np.unique(X[:, feature_idx])
            for t in thresholds:
                left = y[X[:, feature_idx] <= t]
                right = y[X[:, feature_idx] > t]
                
                if len(left) == 0 or len(right) == 0:
                    continue
                
                # Weighted variance of children
                weighted_var = (
                    (len(left) / n) * np.var(left)
                    + (len(right) / n) * np.var(right)
                )
                var_reduction = parent_var - weighted_var
                
                if var_reduction > best_var_reduction:
                    best_var_reduction = var_reduction
                    best_feature = feature_idx
                    best_threshold = t
        
        return best_feature, best_threshold
    
    def predict(self, X):
        return np.array([self._traverse(x, self.root) for x in X])
    
    def _traverse(self, x, node):
        if node.is_leaf():
            return node.value
        if x[node.feature] <= node.threshold:
            return self._traverse(x, node.left)
        return self._traverse(x, node.right)


# Test Regression Tree
from sklearn.datasets import make_regression

X_reg, y_reg = make_regression(
    n_samples=200, n_features=3, noise=10, random_state=42
)
X_tr, X_te, y_tr, y_te = train_test_split(X_reg, y_reg, test_size=0.2)

dtr = DecisionTreeRegressor(max_depth=6)
dtr.fit(X_tr, y_tr)

preds = dtr.predict(X_te)
mse = np.mean((preds - y_te) ** 2)
print(f"Regression Tree MSE: {mse:.2f}")

TensorFlow Decision Forests (TF-DF) is Google's library for training decision tree models within the TensorFlow ecosystem. It supports Random Forests, Gradient Boosted Trees, and CART.

# ========== TensorFlow Decision Forests ==========
# Install: pip install tensorflow_decision_forests

import tensorflow_decision_forests as tfdf
import tensorflow as tf
import pandas as pd
import numpy as np
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

# ---- Step 1: Load and Prepare Data ----
iris = load_iris()
df = pd.DataFrame(iris.data, columns=iris.feature_names)
df['species'] = iris.target

# Split
train_df, test_df = train_test_split(df, test_size=0.2, random_state=42)

# Convert to TensorFlow Datasets
train_ds = tfdf.keras.pd_dataframe_to_tf_dataset(
    train_df, label="species", task=tfdf.keras.Task.CLASSIFICATION
)
test_ds = tfdf.keras.pd_dataframe_to_tf_dataset(
    test_df, label="species", task=tfdf.keras.Task.CLASSIFICATION
)

# ---- Step 2: Train a Random Forest ----
rf_model = tfdf.keras.RandomForestModel(
    num_trees=300,
    max_depth=16,
    min_examples=5,
    task=tfdf.keras.Task.CLASSIFICATION,
    verbose=0
)
rf_model.fit(train_ds)

# ---- Step 3: Evaluate ----
rf_model.compile(metrics=["accuracy"])
evaluation = rf_model.evaluate(test_ds, return_dict=True)
print(f"TF-DF Random Forest Accuracy: {evaluation['accuracy']:.4f}")

# ---- Step 4: Feature Importance ----
inspector = rf_model.make_inspector()
print("\nFeature Importances (NUM_AS_ROOT):")
for fi in inspector.variable_importances()["NUM_AS_ROOT"]:
    print(f"  {fi[0].name}: {fi[1]:.4f}")

# ---- Step 5: Train a CART Decision Tree ----
cart_model = tfdf.keras.CartModel(
    max_depth=6,
    task=tfdf.keras.Task.CLASSIFICATION,
    verbose=0
)
cart_model.fit(train_ds)
cart_model.compile(metrics=["accuracy"])
cart_eval = cart_model.evaluate(test_ds, return_dict=True)
print(f"\nTF-DF CART Accuracy: {cart_eval['accuracy']:.4f}")

# ---- Step 6: Gradient Boosted Trees ----
gbt_model = tfdf.keras.GradientBoostedTreesModel(
    num_trees=300,
    max_depth=6,
    learning_rate=0.1,
    task=tfdf.keras.Task.CLASSIFICATION,
    verbose=0
)
gbt_model.fit(train_ds)
gbt_model.compile(metrics=["accuracy"])
gbt_eval = gbt_model.evaluate(test_ds, return_dict=True)
print(f"TF-DF GBT Accuracy: {gbt_eval['accuracy']:.4f}")

# ---- Step 7: Save and Load Model ----
rf_model.save("saved_rf_model")
loaded_model = tf.keras.models.load_model("saved_rf_model")
print("\nModel saved and loaded successfully!")

# ========== Complete Scikit-Learn Pipeline ==========
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.tree import (
    DecisionTreeClassifier, DecisionTreeRegressor,
    plot_tree, export_text
)
from sklearn.ensemble import RandomForestClassifier, RandomForestRegressor
from sklearn.model_selection import (
    train_test_split, cross_val_score, GridSearchCV
)
from sklearn.metrics import (
    accuracy_score, classification_report,
    confusion_matrix, roc_auc_score
)
from sklearn.datasets import load_iris, load_breast_cancer
from sklearn.inspection import permutation_importance

# ---- 1. Decision Tree on Iris 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 with Gini (default)
dt_gini = DecisionTreeClassifier(
    criterion='gini', max_depth=4,
    min_samples_split=5, random_state=42
)
dt_gini.fit(X_train, y_train)

# Train with Entropy
dt_entropy = DecisionTreeClassifier(
    criterion='entropy', max_depth=4,
    min_samples_split=5, random_state=42
)
dt_entropy.fit(X_train, y_train)

print("=== Decision Tree Results ===")
print(f"Gini Accuracy:    {dt_gini.score(X_test, y_test):.4f}")
print(f"Entropy Accuracy: {dt_entropy.score(X_test, y_test):.4f}")

# Print tree rules as text
print("\nTree Rules (Gini):")
print(export_text(dt_gini, feature_names=iris.feature_names))

# Feature importances
print("Feature Importances (Gini-based):")
for name, importance in zip(iris.feature_names, dt_gini.feature_importances_):
    print(f"  {name}: {importance:.4f}")

# ---- 2. Visualize the Tree ----
fig, ax = plt.subplots(figsize=(20, 10))
plot_tree(
    dt_gini, feature_names=iris.feature_names,
    class_names=iris.target_names, filled=True,
    rounded=True, fontsize=10, ax=ax
)
plt.title("Decision Tree - Iris Dataset")
plt.tight_layout()
plt.savefig("decision_tree_iris.png", dpi=150)
plt.show()

# ---- 3. Cost-Complexity Pruning ----
# Get the pruning path
path = dt_gini.cost_complexity_pruning_path(X_train, y_train)
ccp_alphas = path.ccp_alphas
impurities = path.impurities

# Train trees for each alpha
trees = []
for alpha in ccp_alphas:
    tree = DecisionTreeClassifier(
        ccp_alpha=alpha, random_state=42
    )
    tree.fit(X_train, y_train)
    trees.append(tree)

# Plot accuracy vs alpha
train_scores = [t.score(X_train, y_train) for t in trees]
test_scores = [t.score(X_test, y_test) for t in trees]

fig, ax = plt.subplots()
ax.plot(ccp_alphas, train_scores, 'o-', label="Train")
ax.plot(ccp_alphas, test_scores, 'o-', label="Test")
ax.set_xlabel("Cost-Complexity Alpha")
ax.set_ylabel("Accuracy")
ax.set_title("Cost-Complexity Pruning")
ax.legend()
plt.show()

# ---- 4. Random Forest Pipeline ----
cancer = load_breast_cancer()
X_train, X_test, y_train, y_test = train_test_split(
    cancer.data, cancer.target, test_size=0.2, random_state=42
)

rf = RandomForestClassifier(
    n_estimators=200,
    max_depth=10,
    min_samples_split=5,
    max_features='sqrt',
    oob_score=True,
    random_state=42,
    n_jobs=-1  # Use all CPU cores
)
rf.fit(X_train, y_train)

print("\n=== Random Forest Results ===")
print(f"Training Accuracy: {rf.score(X_train, y_train):.4f}")
print(f"Testing Accuracy:  {rf.score(X_test, y_test):.4f}")
print(f"OOB Score:         {rf.oob_score_:.4f}")
print(f"\n{classification_report(y_test, rf.predict(X_test))}")

# ---- 5. Permutation Importance ----
perm_importance = permutation_importance(
    rf, X_test, y_test, n_repeats=30, random_state=42
)

# Sort by importance
sorted_idx = perm_importance.importances_mean.argsort()[::-1]
print("Top 10 Features (Permutation Importance):")
for idx in sorted_idx[:10]:
    print(f"  {cancer.feature_names[idx]}: "
          f"{perm_importance.importances_mean[idx]:.4f} "
          f"± {perm_importance.importances_std[idx]:.4f}")

# ---- 6. Hyperparameter Tuning with GridSearchCV ----
param_grid = {
    'n_estimators': [50, 100, 200],
    'max_depth': [5, 10, 15, None],
    'min_samples_split': [2, 5, 10],
    'max_features': ['sqrt', 'log2']
}

grid_search = GridSearchCV(
    RandomForestClassifier(random_state=42, oob_score=True),
    param_grid,
    cv=5,
    scoring='accuracy',
    n_jobs=-1,
    verbose=1
)
grid_search.fit(X_train, y_train)

print(f"\nBest Parameters: {grid_search.best_params_}")
print(f"Best CV Score:   {grid_search.best_score_:.4f}")
print(f"Test Score:      {grid_search.score(X_test, y_test):.4f}")

Foundational Papers

1. Shannon, C.E. (1948). "A Mathematical Theory of Communication." Bell System Technical Journal, 27, 379-423.
2. Quinlan, J.R. (1986). "Induction of Decision Trees." Machine Learning, 1(1), 81-106. [ID3 paper]
3. Breiman, L., Friedman, J., Olshen, R., & Stone, C. (1984). Classification and Regression Trees. Wadsworth. [CART book]
4. Quinlan, J.R. (1993). C4.5: Programs for Machine Learning. Morgan Kaufmann. [C4.5 book]
5. Breiman, L. (1996). "Bagging Predictors." Machine Learning, 24(2), 123-140.
6. Breiman, L. (2001). "Random Forests." Machine Learning, 45(1), 5-32.

Advanced References

7. Shotton, J., et al. (2011). "Real-Time Human Pose Recognition in Parts from Single Depth Images." CVPR. [Kinect paper]
8. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning, 2nd ed. Springer. Chapters 9-10.
9. Grinsztajn, L., et al. (2022). "Why do tree-based models still outperform deep learning on tabular data?" NeurIPS.
10. Louppe, G. (2014). "Understanding Random Forests: From Theory to Practice." PhD Thesis, University of Liège.
11. Chen, T. & Guestrin, C. (2016). "XGBoost: A Scalable Tree Boosting System." KDD.
12. Breiman, L. (2001). "Statistical Modeling: The Two Cultures." Statistical Science, 16(3), 199-231.

Indian References

13. RBI (2023). "Framework for Responsible and Ethical Use of AI/ML in Financial Services." Reserve Bank of India.
14. Sharma, V. & Kumar, R. (2020). "Credit Scoring in Indian Banking: A Comparative Study." Indian Journal of Finance.
15. ISRO (2021). "Land Use Land Cover Classification using Machine Learning." NRSC Technical Report.

Online Resources

• scikit-learn Documentation: Decision Trees
• scikit-learn Documentation: Random Forests
• TensorFlow Decision Forests: tf-df
• Visual Introduction to Machine Learning: R2D3
• Distill.pub: "Feature Visualization" — related to understanding tree-based feature importance