Decision Trees and the CART Algorithm

Decision Trees are non-parametric models that recursively partition the feature space, predicting targets using simple hierarchical decision rules.

Recursive Induction: The CART Algorithm

The CART algorithm builds binary trees by searching for a feature $k$ and threshold $t_k$ that minimize the weighted impurity of child nodes.

$J(k, t_k) = \frac{m_{\text{left}}}{m} I_{\text{left}} + \frac{m_{\text{right}}}{m} I_{\text{right}}$

where $I$ represents the impurity of a node, and $m$ is the number of samples.

Split Selection Logic

The CART algorithm is greedy: it searches for the best split at the current step rather than evaluating combinations globally. It does not guarantee finding the globally optimal tree.

Impurity Measures

• Gini Impurity: Probability of a random element being misclassified. $G = 1 - \sum_{i=1}^{C} p_i^2$
• Entropy: Quantifies node disorder or uncertainty. $H = -\sum_{i=1}^{C} p_i \log_2(p_i)$

For regression trees, CART minimizes Mean Squared Error (MSE), and leaves predict the average target value.

Regularization

Without constraints, decision trees grow until leaves are pure, causing overfitting. We regularize using stopping hyperparameters:

• max_depth: Limits depth.
• min_samples_split: Minimum samples required to split a node.
• min_samples_leaf: Minimum samples a leaf must contain.

skinparam backgroundColor transparent
rectangle "Is Feature X <= 2.5?" as Root
rectangle "Leaf: Class A" as Left
rectangle "Leaf: Class B" as Right
Root --> Left : Yes
Root --> Right : No

Example: Computing Impurity

The following example demonstrates calculating Gini impurity and Information Gain:

import numpy as np

# Calculate Gini Impurity: 1 - sum(p_i^2) for class probabilities p_i
def gini(labels):
  _, counts = np.unique(labels, return_counts=True)
  probs = counts / len(labels)
  return 1 - np.sum(probs**2)

# Unsplit parent node containing mixed classes
parent = [0, 0, 1, 1, 1, 1]

# Left and right child nodes after split
left = [0, 0]
right = [1, 1, 1, 1]

print(f"Parent Gini: {gini(parent):.4f}")
print(f"Left Child Gini: {gini(left):.4f}")
print(f"Right Child Gini: {gini(right):.4f}")

Parent Gini: 0.4444
Left Child Gini: 0.0000
Right Child Gini: 0.0000

Exercise

Test your understanding of Decision Tree scaling requirements:

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow (3rd ed.). O’Reilly Media.