Decision Trees & Information Gain (CART)

Recursive binary partitioning, Gini impurity, and greedy splitting mechanisms.

⏱ 15 min read🎯 Prerequisites: Basic Python, Probabilities & Entropy

💡 1. Core Intuition & Concepts

Classification and Regression Trees (CART) construct non-parametric predictive models by recursively partitioning feature space into axis-aligned rectangular regions with homogeneous target distributions.

📐 2. Mathematical Formulations & Derivations

Gini Impurity Metric

I_G(S) = 1 - \sum_{k=1}^K p_k^2 \qquad p_k = \frac{|\{x \in S : y = k\}|}{|S|}

Measures probability of incorrectly classifying a randomly chosen element from set S.

Shannon Entropy Impurity

H(S) = -\sum_{k=1}^K p_k \log_2(p_k)

Measures average information uncertainty in bits.

Split Information Gain

\Delta I = I(S_{\text{parent}}) - \left( \frac{|S_L|}{|S|} I(S_L) + \frac{|S_R|}{|S|} I(S_R) \right)

Greedy criterion to select optimal feature f and split threshold θ.

⚙️ 3. Step-by-Step Computational Mechanism

Evaluate Potential Thresholds

Iterate over all features j and candidate thresholds θ from unique sorted values.

Partition Dataset

Split into left branch S_L = {x : x_j <= θ} and right branch S_R = {x : x_j > θ}.

Compute Impurity Reduction

Select split (j*, θ*) maximizing weighted impurity drop ΔI.

Recurse or Form Leaf

Continue splitting until maximum depth, minimum sample leaf, or pure node is reached.

💻 4. Code from Scratch (python)

cart.py

import numpy as np

class DecisionTreeNode:
    def __init__(self, feature=None, threshold=None, left=None, right=None, *, value=None):
        self.feature = feature
        self.threshold = threshold
        self.left = left
        self.right = right
        self.value = value

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

class DecisionTreeScratch:
    """Binary Decision Tree Classifier using Gini Impurity from scratch."""
    def __init__(self, min_samples_split=2, max_depth=10):
        self.min_samples_split = min_samples_split
        self.max_depth = max_depth
        self.root = None

    def _gini(self, y):
        counts = np.bincount(y)
        probs = counts / len(y)
        return 1.0 - np.sum(probs ** 2)

    def fit(self, X, y):
        self.root = self._grow_tree(X, y)

    def _grow_tree(self, X, y, depth=0):
        n_samples, n_feats = X.shape
        n_classes = len(np.unique(y))

        if depth >= self.max_depth or n_classes == 1 or n_samples < self.min_samples_split:
            leaf_val = np.argmax(np.bincount(y))
            return DecisionTreeNode(value=leaf_val)

        best_feat, best_thresh, best_gain = None, None, -1
        current_gini = self._gini(y)

        for feat in range(n_feats):
            thresholds = np.unique(X[:, feat])
            for thresh in thresholds:
                left_idx = X[:, feat] <= thresh
                right_idx = ~left_idx
                if len(y[left_idx]) == 0 or len(y[right_idx]) == 0:
                    continue

                gain = current_gini - (len(y[left_idx]) / n_samples * self._gini(y[left_idx]) +
                                       len(y[right_idx]) / n_samples * self._gini(y[right_idx]))
                if gain > best_gain:
                    best_gain, best_feat, best_thresh = gain, feat, thresh

        if best_gain <= 0:
            return DecisionTreeNode(value=np.argmax(np.bincount(y)))

        left_idx = X[:, best_feat] <= best_thresh
        left = self._grow_tree(X[left_idx], y[left_idx], depth + 1)
        right = self._grow_tree(X[~left_idx], y[~left_idx], depth + 1)
        return DecisionTreeNode(best_feat, best_thresh, left, right)

🧠 5. Comprehension Checkpoint

Answer all 1 questions correctly to complete the chapter · 0 / 1 done

Q1/1 What is the Gini impurity of a perfectly pure node containing only 1 class?

In the catalog

Decision tree (CART, ID3, C4.5)

Finished this chapter?

Learn ML from Scratch: Beginner to Advanced