Decision Trees & CART Algorithm | AI & Machine Learning Engineering

Decision Trees partition complex feature spaces into a hierarchy of disjoint, axis-aligned hyper-rectangles. Unlike linear models that enforce global geometric boundaries, decision trees employ a greedy, non-parametric divide-and-conquer strategy that yields highly interpretable, piecewise-constant prediction regions.

Gini ImpurityInformation Theory

1 - sum(p_k^2)

Measures the expected error rate of random classification under the node label distribution.

1. Information-Theoretic Splitting Criteria#

At each node, the decision tree algorithm selects a feature $j$ and split threshold $\theta$ that maximizes the purity of the resulting child subsets.

Architecture Diagram

Rendering diagram...

Shannon Entropy and Information Gain#

In Information Theory, the "surprise" or self-information of observing an event with probability $p_k$ is:

I(p_k) = \log_2\left( \frac{1}{p_k} \right) = -\log_2(p_k)

The Shannon Entropy $H(S)$ is the expected surprise over all $K$ classes:

H(S) = \mathbb{E}[I(p)] = \sum_{k=1}^K p_k \cdot I(p_k) = -\sum_{k=1}^K p_k \log_2(p_k)

If a node is completely pure ( $p_1 = 1$ , $p_k = 0$ for $k > 1$ ), $H(S) = 0$ .
If classes are uniformly distributed ( $p_k = 1/K$ ), $H(S) = \log_2(K)$ reaches maximum uncertainty.

The Information Gain (IG) measures the reduction in entropy achieved by partitioning dataset $S$ into subsets $\{S_1, \dots, S_m\}$ :

IG(S, A) = H(S) - \sum_{v=1}^m \frac{|S_v|}{|S|} H(S_v)

2. Derivation of Gini Impurity from First Principles#

In the Classification and Regression Trees (CART) algorithm, Gini Impurity serves as a computationally efficient surrogate for entropy, avoiding transcendental logarithmic operations.

Step 1: Physical Experiment Formulation

Suppose we assign a label to an item drawn randomly from set $S$ according to the empirical class distribution $\{p_1, p_2, \dots, p_K\}$ . What is the probability that this randomly labeled item is misclassified?

Step 2: Probability of Misclassification

For a specific class $k$ , the probability that the drawn item actually belongs to class $k$ is $p_k$ . The probability that we incorrectly assign it a different label $j \ne k$ is $\sum_{j \ne k} p_j = (1 - p_k)$ .

Summing over all classes $k = 1, \dots, K$ :

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

Step 3: Expand and Simplify

Distribute the terms across the summation:

I_G(S) = \sum_{k=1}^K (p_k - p_k^2) = \sum_{k=1}^K p_k - \sum_{k=1}^K p_k^2

Because the class probabilities sum to unity ( $\sum_{k=1}^K p_k = 1$ ):

I_G(S) = 1 - \sum_{k=1}^K p_k^2

Mathematical Relationship Between Gini and Entropy#

Using the first-order Taylor series expansion of the natural logarithm $\ln(x) \approx x - 1$ centered at $x = 1$ , we have:

\ln(p_k) = -\ln\left(\frac{1}{p_k}\right) \approx -\left(\frac{1}{p_k} - 1\right) = 1 - \frac{1}{p_k}

Multiplying by $-p_k$ :

-p_k \ln(p_k) \approx p_k \left( 1 - p_k \right)

Summing over all classes reveals that Gini Impurity is the first-order polynomial Taylor approximation of Entropy:

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

3. Minimal Cost-Complexity Pruning#

Unconstrained decision trees grow until every leaf contains a single sample, causing severe overfitting (zero bias, massive variance).

To prevent overfitting, Breiman's CART applies Minimal Cost-Complexity Pruning by balancing misclassification risk with tree size:

R_\alpha(T) = R(T) + \alpha |T|

$R(T)$ : Empirical training error rate of subtree $T$ .
$|T|$ : Number of terminal leaf nodes in $T$ .
$\alpha \ge 0$ : Complexity parameter penalizing tree depth.
When $\alpha = 0$ : The full, unpruned tree minimizes the cost.
As $\alpha \to \infty$ : The root node alone with zero splits minimizes the cost.

4. From-Scratch Implementation: Zero Dependencies#

The following implementations construct a recursive binary decision tree classifier from scratch in Python and Rust using only native primitives.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
from typing import List, Optional, Tuple
from collections import Counter

class TreeNode:
    def __init__(
        self,
        feature_index: Optional[int] = None,
        threshold: Optional[float] = None,
        left: Optional['TreeNode'] = None,
        right: Optional['TreeNode'] = None,
        leaf_value: Optional[int] = None
    ):
        self.feature_index = feature_index
        self.threshold = threshold
        self.left = left
        self.right = right
        self.leaf_value = leaf_value

    @property
    def is_leaf(self) -> bool:
        return self.leaf_value is not None

class DecisionTreeFromScratch:
    def __init__(self, max_depth: int = 4, min_samples_split: int = 2):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.root: Optional[TreeNode] = None

    @staticmethod
    def _gini_impurity(labels: List[int]) -> float:
        if not labels:
            return 0.0
        total = len(labels)
        counts = Counter(labels)
        sum_p_squared = sum((cnt / total) ** 2 for cnt in counts.values())
        return 1.0 - sum_p_squared

    def _best_split(self, X: List[List[float]], y: List[int]) -> Tuple[Optional[int], Optional[float]]:
        num_samples = len(X)
        num_features = len(X[0])
        current_gini = self._gini_impurity(y)

        best_gain = -1.0
        best_feature = None
        best_threshold = None

        for feat in range(num_features):
            # Extract unique values as candidate thresholds
            values = set(row[feat] for row in X)
            for val in values:
                left_y = [y[i] for i in range(num_samples) if X[i][feat] <= val]
                right_y = [y[i] for i in range(num_samples) if X[i][feat] > val]

                if not left_y or not right_y:
                    continue

                p_left = len(left_y) / num_samples
                p_right = len(right_y) / num_samples
                weighted_gini = p_left * self._gini_impurity(left_y) + p_right * self._gini_impurity(right_y)
                gain = current_gini - weighted_gini

                if gain > best_gain:
                    best_gain = gain
                    best_feature = feat
                    best_threshold = val

        return best_feature, best_threshold

    def _build_tree(self, X: List[List[float]], y: List[int], depth: int = 0) -> TreeNode:
        num_samples = len(X)
        num_classes = len(set(y))

        # Stopping criteria: pure node, max depth, or insufficient samples
        if depth >= self.max_depth or num_classes <= 1 or num_samples < self.min_samples_split:
            most_common = Counter(y).most_common(1)[0][0]
            return TreeNode(leaf_value=most_common)

        feature, threshold = self._best_split(X, y)
        if feature is None:
            most_common = Counter(y).most_common(1)[0][0]
            return TreeNode(leaf_value=most_common)

        # Partition children
        left_X, left_y, right_X, right_y = [], [], [], []
        for i in range(num_samples):
            if X[i][feature] <= threshold:
                left_X.append(X[i])
                left_y.append(y[i])
            else:
                right_X.append(X[i])
                right_y.append(y[i])

        left_child = self._build_tree(left_X, left_y, depth + 1)
        right_child = self._build_tree(right_X, right_y, depth + 1)
        return TreeNode(feature_index=feature, threshold=threshold, left=left_child, right=right_child)

    def fit(self, X: List[List[float]], y: List[int]) -> None:
        self.root = self._build_tree(X, y, depth=0)

    def _traverse(self, sample: List[float], node: TreeNode) -> int:
        if node.is_leaf:
            return node.leaf_value
        if sample[node.feature_index] <= node.threshold:
            return self._traverse(sample, node.left)
        return self._traverse(sample, node.right)

    def predict(self, X: List[List[float]]) -> List[int]:
        return [self._traverse(sample, self.root) for sample in X]

if __name__ == "__main__":
    X_train = [[2.0, 3.0], [1.0, 1.0], [5.0, 6.0], [6.0, 8.0], [1.5, 2.0], [7.0, 7.0]]
    y_train = [0, 0, 1, 1, 0, 1]

    clf = DecisionTreeFromScratch(max_depth=3)
    clf.fit(X_train, y_train)
    preds = clf.predict([[1.2, 1.8], [6.5, 7.2]])
    print(f"Predictions: {preds}")

5. Active Knowledge Checks#

Concept check

What is the operational advantage of Gini Impurity over Shannon Entropy in the CART decision tree algorithm?

Concept check

In Cost-Complexity Pruning R_alpha(T) = R(T) + alpha * |T|, what role does parameter alpha play?