Regression Stump [medium]

v1 분류 stump 는 0-1 오류 최소화. 회귀에는 SSE (sum of squared errors) 최소화로 같은 알고리즘을 일반화. GBM (Gradient Boosting Regressor) 의 기본 블록.

알고리즘

각 특성 $j$ 와 threshold $t$:

1. 왼쪽 = $\{i : X_{i,j} \le t\}$, 오른쪽 = 나머지.
2. 각 영역 예측 = y 평균:
   • $\mu_l = \text{mean}(y_\text{left})$, $\mu_r = \text{mean}(y_\text{right})$
3. SSE: $\text{SSE}(j, t) = \sum_{i \in L} (y_i - \mu_l)^2 + \sum_{i \in R} (y_i - \mu_r)^2$

$(j^*, t^*) = \arg\min_{j, t} \text{SSE}$. 대응하는 $\mu_l, \mu_r$ 반환.

효율 $O(N \log N)$

단순 구현은 $O(N^2 D)$. 정렬 + 누적합 $(cumsum, cumsum\_sq)$ 으로 $O(N D)$ 로 가능하지만, 이 과제는 정확성만 요구.

예측 규칙

def predict(x, feature, threshold, left, right):
    return left if x[feature] <= threshold else right

과제

함수 fit_regression_stump(X, y) 를 완성하세요.

• X shape (N, D), y shape (N,) 실수.
• 반환: (feature, threshold, left_mean, right_mean) — int, float, float, float.
• 어떤 특성도 threshold 로 의미있게 split 못하면 feature=0, threshold=min(X[:,0])-1, left_mean=right_mean=y.mean().

테스트 케이스

#	이름	검증
1	반환 4-tuple
2	명확 분리 (step function) → 정확 복원
3	feature 0/1 혼합: 올바른 특성 선택	다른 특성이 더 정보적
4	리프 평균 = 실제 y 평균
5	단일 값만 있는 특성 스킵
6	threshold 가 데이터 중점
7	SSE 는 parent variance 보다 작거나 같음