← Gym/Bagging Classifier
00:00/ 40 min

🧭 Do not search for the first 15 minutes. When stuck: re-read the requirements → define I/O → choose the data structure → trace a small example by hand → write code.

Implement a bagging classifier over decision stumps, without sklearn. Half of this problem is reproducibility — the same seed must always produce the same result, so the random-number protocol has to be followed exactly.

Base learner: the decision stump

A depth-1 tree. Its best split is found by minimizing weighted Gini.

  • Candidate thresholds: sort each feature's values, drop duplicates, take the midpoint of adjacent pairs
  • Left = X[:, f] <= t, right = the rest
  • Weighted Gini = ∣L∣nG(L)+∣R∣nG(R)\frac{|L|}{n}G(L) + \frac{|R|}{n}G(R), where G(S)=1−∑cpc2G(S) = 1-\sum_c p_c^2
  • On a tie: lower feature index → lower threshold
  • Each side predicts the majority class of its training rows, 0 on a draw
  • If no split is possible (every feature has a single value), always predict the overall majority class (0 on a draw)

Bagging

python
model = BaggingClassifier(n_estimators=10, seed=42)
model.fit(X, y)
pred = model.predict(X)      # a list of n 0/1 values

Random-number protocol — follow this exactly

python
rng = np.random.default_rng(seed)
for i in range(n_estimators):
    idx = rng.integers(0, n_samples, size=n_samples)   # sample with replacement
    # fit one stump on X[idx], y[idx]

Create rng once and make the call above exactly once per estimator, in order. Deviate from this and the same seed yields different results.

Prediction

Collect the stumps' predictions and take a majority vote. 0 on a draw.

Binary classification only

y is 0 or 1.

Level 1 · Decision stump

Build the base learner first.

python
fit_stump(X, y) -> dict

It returns one of these two shapes.

python
{"feature": int, "threshold": float, "left": 0|1, "right": 0|1}
{"feature": None, "threshold": None, "left": c, "right": c}   # no split possible
  • The split and tie rules match the shared spec.
  • Round the threshold to 6 decimal places.
  • When no split is possible, feature and threshold are None, and both left and right hold the overall majority class (0 on a draw).
python
predict_stump(stump, X) -> list
  • For each row, left when X[:, feature] <= threshold, otherwise right.
  • When feature is None, return the left value for every row.