Best Gini Split [medium]

v1 Gini 는 한 분포의 불순도. CART 결정트리에서는 한 특성의 어느 threshold 에서 자를 때 불순도 감소가 최대인지 찾아야 함 — 이것이 splitting criterion.

Gini Gain

부모 노드의 Gini $G_p$, 분할 시 왼쪽/오른쪽 자식 $G_l, G_r$ 과 샘플 비율 $w_l = n_l / n$, $w_r = n_r / n$:

$\text{Gain} = G_p - (w_l G_l + w_r G_r)$

Gini Gain 최대 가 가장 정보적인 분기점.

알고리즘

1. 부모 $G_p$ 계산 (전체 라벨에서).
2. 특성 값을 정렬. 가능한 threshold = 인접값의 중점.
3. 각 threshold 에서:
   • 왼쪽 = $x < t$, 오른쪽 = $x \ge t$.
   • 자식 Gini 와 가중 평균 계산.
   • Gain 산출.
4. Gain 이 최대인 threshold 반환.

naive 구현은 $O(N^2 K)$. 더 빠른 구현은 정렬 한 번 후 누적 count 로 $O(N K)$.

엣지

• 모든 라벨 동일 → 분할 의미 없음, gain = 0. 반환 threshold = 중앙값 OK.
• 특성 값이 모두 같음 → 분할 불가, threshold 는 그 값, gain = 0.

과제

함수 best_gini_split(feature, labels, num_classes) 를 완성하세요.

• feature shape (N,) 실수.
• labels shape (N,) 정수 [0, K).
• 반환: (best_threshold, best_gain) — 둘 다 Python float.
• 빈 자식이 발생하는 threshold 는 제외 (양쪽 최소 1 샘플).

테스트 케이스

#	이름	검증
1	반환 2-tuple
2	완벽 분리 가능 → gain > 0, threshold 가 분리점 근처
3	같은 라벨만 → gain = 0
4	Gain 계산 검증: 수동 계산과 일치
5	최소성: gain 은 parent_gini - 가중 자식 gini
6	3-클래스 데이터에서도 동작
7	sklearn DecisionTree 의 분기 기준과 비슷 (단일 분기)