Decision Tree Classifier with Bagging - Supervised Learning

Decision Tree Classifier with Bagging

Grow a full classification tree with recursive Gini splits (build_tree, predict_tree), then combine trees trained on bootstrap samples by majority vote (bagging_predict).

Background

A single deep tree has low bias but high variance: small changes in the data change the tree. Bagging (bootstrap aggregating) averages many such trees to cut the variance; random forests add per-split feature subsampling on top. This problem uses the impurity from Gini Impurity for Decision-Tree Splits.

Gini impurity

gini(S)          = 1 - sum_c p_c^2            # p_c = fraction of S with class c
split impurity   = (n_L * gini(L) + n_R * gini(R)) / n

Growing the tree (build_tree)

At a node holding samples S at depth depth (the root has depth 0):

1. The node is a leaf if max_depth is not None and depth >= max_depth, or len(S) < min_samples_split, or S is pure.
2. Otherwise search every feature f (in increasing order) and every threshold t (in increasing order), where the thresholds are the midpoints between consecutive distinct sorted values of feature f within S. A sample goes left if x[f] <= t, right otherwise.
3. Start with best = gini(S). A candidate replaces the current best only if its split impurity is lower by more than 1e-12. So ties keep the earlier candidate (smaller feature index, then smaller threshold), and a split is made only if it strictly reduces impurity.
4. If no candidate qualified, the node is a leaf; otherwise recurse on both sides with depth + 1.

A leaf predicts the majority class of its samples; ties go to the smallest class label.

Tree format

• Leaf: {'leaf': True, 'value': c} with c a Python int
• Internal node: {'leaf': False, 'feature': f, 'threshold': t, 'left': subtree, 'right': subtree} with f an int and t a float

Bagging (bagging_predict)

1. Create rng = np.random.default_rng(seed) once.
2. For each of the n_estimators trees, in order: draw idx = rng.integers(0, n, size=n) (sampling with replacement), fit build_tree(X_train[idx], y_train[idx], max_depth, min_samples_split), and predict X_test.
3. Each test sample gets the class with the most votes (hard voting); ties go to the smallest label.

Inputs

• X, X_train, X_test: float arrays (n_samples, n_features)
• y, y_train: non-negative integer labels (n_samples,)
• max_depth: int or None; min_samples_split: int (default 2); n_estimators, seed: ints

Expected Return Format

• build_tree(X, y, max_depth=None, min_samples_split=2): the root node dict (format above)
• predict_tree(tree, X): int array (n_samples,)
• bagging_predict(X_train, y_train, X_test, n_estimators=10, max_depth=None, min_samples_split=2, seed=0): int array (n_test,)

Conventions vs scikit-learn

• Same as DecisionTreeClassifier(criterion='gini'): midpoint thresholds, <= goes left, max_depth and min_samples_split mean the same. sklearn shuffles the features at each node, so it breaks exact ties at random (fixed by random_state); here ties are deterministic.
• BaggingClassifier averages the trees' predicted probabilities (soft voting) when it can; here you use hard majority voting.

Constraints

• NumPy only; no sklearn.

Follow-up

• What does a random forest change (max_features), and why does decorrelating the trees help more than adding trees?
• About 63.2% of the distinct samples land in each bootstrap sample. How can the remaining "out-of-bag" samples estimate test error for free?

Input: build_tree(np.array([[2.0, 3.0], [1.0, 1.0], [3.0, 1.0], [6.0, 5.0], [7.0, 7.0], [8.0, 6.0], [4.0, 4.0], [5.0, 2.0]]), np.array([0, 0, 0, 1, 1, 1, 0, 1]), max_depth=1)
Output: {'leaf': False, 'feature': 0, 'threshold': 4.5, 'left': {'leaf': True, 'value': 0}, 'right': {'leaf': True, 'value': 1}}

Input: predict_tree(tree, np.array([[0.0, 0.0], [4.5, 1.0], [4.5, 6.0], [9.0, 9.0]]))  # tree: same data, no max_depth
Output: array([0, 0, 0, 1])

import numpy as np

def build_tree(X, y, max_depth=None, min_samples_split=2):
    """
    Grow a classification tree with Gini splits.

    Args:
        X: Features, array (n_samples, n_features)
        y: Non-negative integer labels, array (n_samples,)
        max_depth: Maximum depth (root = depth 0), or None for no limit
        min_samples_split: Nodes with fewer samples become leaves

    Returns:
        Root node: {'leaf': True, 'value': c} or
        {'leaf': False, 'feature': f, 'threshold': t, 'left': ..., 'right': ...}
        (c and f Python ints, t a Python float)
    """
    # Your code here
    pass

def predict_tree(tree, X):
    """Return the predicted class for each row of X, as an int array (n_samples,)."""
    # Your code here
    pass

def bagging_predict(X_train, y_train, X_test, n_estimators=10, max_depth=None,
                    min_samples_split=2, seed=0):
    """
    Bagging: trees on bootstrap samples drawn with rng = np.random.default_rng(seed)
    (idx = rng.integers(0, n, size=n) per tree), combined by majority vote.

    Returns:
        Predicted classes for X_test, int array (n_test,) (vote ties -> smallest label)
    """
    # Your code here
    pass