Hands-on lab — Day 162: Decision Trees

"""
Tests for reference Decision Tree implementation.
"""
import pytest
import numpy as np
from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier
import tree_lib as tree


def test_gini_impurity_exact_values():
    # Pure: G = 0.0
    assert tree.compute_gini(np.array([0, 0, 0, 0])) == 0.0
    # 50/50 binary: G = 1 - (0.5^2 + 0.5^2) = 0.50
    assert tree.compute_gini(np.array([0, 1])) == 0.50
    # 3-class equal: G = 1 - 3*(1/3)^2 = 1 - 1/3 = 2/3 = 0.6666...
    assert np.isclose(tree.compute_gini(np.array([0, 1, 2])), 2.0 / 3.0)


def test_entropy_exact_values():
    # Pure: H = 0.0
    assert tree.compute_entropy(np.array([1, 1, 1])) == 0.0
    # 50/50 binary: H = 1.0 bit
    assert np.isclose(tree.compute_entropy(np.array([0, 1])), 1.0)


def test_find_best_split_linear_separation():
    # Feature 0 clearly separates: x <= 5.0 -> class 0, x > 5.0 -> class 1
    X = np.array([[2.0, 10.0], [4.0, 12.0], [6.0, 1.0], [8.0, 3.0]])
    y = np.array([0, 0, 1, 1])
    
    feat, thresh, gini = tree.find_best_split(X, y)
    assert feat == 0
    assert thresh == 5.0
    assert gini == 0.0 # Perfect split


def test_iris_dataset_benchmark():
    iris = load_iris()
    X, y = iris.data, iris.target
    
    scratch_tree = tree.DecisionTreeClassifierScratch(max_depth=3)
    scratch_tree.fit(X, y)
    scratch_preds = scratch_tree.predict(X)
    scratch_acc = np.mean(scratch_preds == y)
    
    sk_tree = DecisionTreeClassifier(max_depth=3, criterion="gini", random_state=42)
    sk_tree.fit(X, y)
    sk_preds = sk_tree.predict(X)
    sk_acc = np.mean(sk_preds == y)
    
    assert scratch_acc >= 0.95
    assert sk_acc >= 0.95
    assert abs(scratch_acc - sk_acc) < 0.05

"""
Decision Trees reference library implementation.
"""
import numpy as np


def compute_gini(y: np.ndarray) -> float:
    """
    Compute Gini impurity:
    G = 1 - sum_{k=1}^K p_k^2
    """
    y = np.asarray(y, dtype=int)
    if len(y) == 0:
        return 0.0
    _, counts = np.unique(y, return_counts=True)
    probs = counts / len(y)
    return float(1.0 - np.sum(probs ** 2))


def compute_entropy(y: np.ndarray, eps: float = 1e-15) -> float:
    """
    Compute Shannon entropy (base 2):
    H = - sum_{k=1}^K p_k * log2(p_k)
    """
    y = np.asarray(y, dtype=int)
    if len(y) == 0:
        return 0.0
    _, counts = np.unique(y, return_counts=True)
    probs = counts / len(y)
    probs = np.clip(probs, eps, 1.0)
    return float(-np.sum(probs * np.log2(probs)))


def find_best_split(X: np.ndarray, y: np.ndarray) -> tuple[int, float, float]:
    """
    Exhaustively evaluate all features and thresholds to find split minimizing weighted child Gini impurity:
    Returns (best_feature_idx, best_threshold, best_weighted_gini).
    """
    X = np.asarray(X, dtype=float)
    y = np.asarray(y, dtype=int)
    N, D = X.shape
    
    current_gini = compute_gini(y)
    if current_gini == 0.0 or N < 2:
        return -1, 0.0, current_gini
        
    best_feat = -1
    best_thresh = 0.0
    best_gini = float("inf")
    
    for feat_idx in range(D):
        values = np.unique(X[:, feat_idx])
        if len(values) < 2:
            continue
            
        # Candidate thresholds at midpoints between sorted unique values
        thresholds = (values[:-1] + values[1:]) / 2.0
        
        for t in thresholds:
            left_mask = X[:, feat_idx] <= t
            right_mask = ~left_mask
            
            n_l, n_r = np.sum(left_mask), np.sum(right_mask)
            if n_l == 0 or n_r == 0:
                continue
                
            gini_l = compute_gini(y[left_mask])
            gini_r = compute_gini(y[right_mask])
            weighted_gini = (n_l / N) * gini_l + (n_r / N) * gini_r
            
            if weighted_gini < best_gini:
                best_gini = weighted_gini
                best_feat = feat_idx
                best_thresh = float(t)
                
    return best_feat, best_thresh, float(best_gini)


class Node:
    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 DecisionTreeClassifierScratch:
    """
    Binary / Multiclass Decision Tree Classifier using CART algorithm.
    """
    def __init__(self, max_depth: int = 3, min_samples_split: int = 2):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.root = None

    def _majority_class(self, y: np.ndarray) -> int:
        classes, counts = np.unique(y, return_counts=True)
        return int(classes[np.argmax(counts)])

    def _build_tree(self, X: np.ndarray, y: np.ndarray, depth: int = 0) -> Node:
        N, D = X.shape
        num_classes = len(np.unique(y))
        
        # Base cases: pure node, max depth reached, or too few samples
        if num_classes == 1 or depth >= self.max_depth or N < self.min_samples_split:
            return Node(value=self._majority_class(y))
            
        feat_idx, thresh, best_gini = find_best_split(X, y)
        if feat_idx == -1:
            return Node(value=self._majority_class(y))
            
        left_mask = X[:, feat_idx] <= thresh
        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(feature=feat_idx, threshold=thresh, left=left_child, right=right_child)

    def fit(self, X: np.ndarray, y: np.ndarray):
        X = np.asarray(X, dtype=float)
        y = np.asarray(y, dtype=int)
        self.root = self._build_tree(X, y, depth=0)
        return self

    def _traverse_single(self, x: np.ndarray, node: Node) -> int:
        if node.is_leaf:
            return node.value
        if x[node.feature] <= node.threshold:
            return self._traverse_single(x, node.left)
        return self._traverse_single(x, node.right)

    def predict(self, X: np.ndarray) -> np.ndarray:
        X = np.asarray(X, dtype=float)
        return np.array([self._traverse_single(x, self.root) for x in X], dtype=int)

lesson_id: D162
day: 162
kind: tree-algorithms
languages:
  - python
setup_commands:
  - python3 -m venv .venv
  - .venv/bin/pip install -r requirements/requirements.txt
run_commands:
  - .venv/bin/python examples/tree_lib.py
test_commands:
  - ./tests/run_tests.sh
cleanup_commands:
  - rm -rf .venv __pycache__ .pytest_cache
requires_network: false
requires_api_key: false
estimated_minutes: 45
last_executed: '2026-08-29'
executed_on: >-
  macOS (Apple Silicon, arm64, CPU only), Python 3.14.0, numpy 2.5.2,
  scikit-learn 1.9.0, pytest 9.1.1, scipy 1.15.2 -- bash tests/run_tests.sh -> 4 checks,
  0 failure(s), exit 0. pytest examples -v -> 4 passed. pytest starter -v -> 2 passed.
  Verified recursive binary tree splitting, Gini and Entropy impurity reductions, axis-aligned partitioning, and scikit-learn accuracy parity.

numpy==2.5.2
scikit-learn==1.9.0
pytest==9.1.1
scipy==1.15.2

"""
Tests for starter Decision Tree implementation.
"""
import pytest
import numpy as np
import tree_lib as tree


def test_gini_stub():
    with pytest.raises(NotImplementedError):
        tree.compute_gini(np.array([0, 1]))


def test_fit_stub():
    clf = tree.DecisionTreeClassifierScratch()
    with pytest.raises(NotImplementedError):
        clf.fit(np.zeros((10, 2)), np.zeros(10))

"""
Decision Trees starter library.
"""
import numpy as np


def compute_gini(y: np.ndarray) -> float:
    """Compute Gini impurity: G = 1 - sum(p_k^2)."""
    raise NotImplementedError("Implement compute_gini")


def compute_entropy(y: np.ndarray) -> float:
    """Compute Shannon entropy: H = -sum(p_k * log2(p_k))."""
    raise NotImplementedError("Implement compute_entropy")


def find_best_split(X: np.ndarray, y: np.ndarray) -> tuple[int, float, float]:
    """Find the feature and threshold that minimize weighted child Gini impurity."""
    raise NotImplementedError("Implement find_best_split")


class DecisionTreeClassifierScratch:
    def __init__(self, max_depth: int = 3, min_samples_split: int = 2):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.tree = None

    def fit(self, X: np.ndarray, y: np.ndarray):
        """Fit decision tree recursively."""
        raise NotImplementedError("Implement fit")

    def predict(self, X: np.ndarray) -> np.ndarray:
        """Predict class labels for X."""
        raise NotImplementedError("Implement predict")

#!/usr/bin/env bash
# Day 162 lab harness: "Decision Trees"
set -u

LAB_DIR="$(cd "$(dirname "${BASH_SOURCE[0]}")/.." && pwd)"
cd "$LAB_DIR"

PYTHON="${PYTHON:-../../../../.venv-tools/bin/python3}"
PYTEST="${PYTEST:-../../../../.venv-tools/bin/pytest}"

CHECKS=0
FAILURES=0

ok() {
  CHECKS=$((CHECKS + 1))
  echo "  ok: $1"
}

fail() {
  CHECKS=$((CHECKS + 1))
  FAILURES=$((FAILURES + 1))
  echo "  FAIL: $1"
}

echo "=== 1. Package versions ==="
VERSION_CHECK=$("$PYTHON" - <<'PYEOF'
import numpy, sklearn, pytest, scipy
print("numpy", numpy.__version__)
print("scikit-learn", sklearn.__version__)
print("pytest", pytest.__version__)
print("scipy", scipy.__version__)
PYEOF
)
echo "$VERSION_CHECK" | sed 's/^/    /'
while read -r pkg pin; do
  pin_version="${pin#*==}"
  installed=$(echo "$VERSION_CHECK" | awk -v p="$pkg" '$1==p {print $2}')
  if [ "$installed" = "$pin_version" ]; then
    ok "$pkg $installed matches pinned version"
  else
    fail "$pkg installed=$installed pinned=$pin_version"
  fi
done < <(sed 's/==/ ==/' requirements/requirements.txt)

echo ""
echo "=== 2. Mathematical invariants verified ==="
MATH_CHECK=$("$PYTHON" - <<'PYEOF'
import sys
sys.path.insert(0, "examples")
import numpy as np
import tree_lib as tree

# Gini on balanced 2-class is exactly 0.50
assert tree.compute_gini(np.array([0, 1])) == 0.5, "Gini binary 0.5 failed"

# Entropy on balanced 2-class is exactly 1.0
assert abs(tree.compute_entropy(np.array([0, 1])) - 1.0) < 1e-9, "Entropy binary 1.0 failed"

# Pure node impurity is strictly 0.0
assert tree.compute_gini(np.zeros(10)) == 0.0
assert tree.compute_entropy(np.zeros(10)) == 0.0

print("MATH_OK")
PYEOF
)

if [ "$MATH_CHECK" = "MATH_OK" ]; then
  ok "Gini and Entropy mathematical impurity bounds verified"
else
  fail "Mathematical verification failed: $MATH_CHECK"
fi

echo ""
echo "=== 3. Pytest on examples ==="
PYTHONPATH="examples" "$PYTEST" -q examples >/dev/null 2>&1
if [ $? -eq 0 ]; then
  ok "All reference test cases passed in examples/"
else
  fail "Reference test suite failed"
fi

echo ""
echo "=== 4. Pytest on starter ==="
PYTHONPATH="starter" "$PYTEST" -q starter >/dev/null 2>&1
if [ $? -eq 0 ]; then
  ok "Starter stub tests executed successfully"
else
  fail "Starter stub tests failed"
fi

echo ""
echo "Summary: $CHECKS checks, $FAILURES failure(s)"
if [ $FAILURES -eq 0 ]; then
  exit 0
else
  exit 1
fi