Decision Tree Best Binary Splithard

Decision Tree Best Binary Split

hard Classical ML from Scratch 20–25 min

NumPy allowed · plain Python earns 10 bonus points

Identify the optimal threshold for splitting a continuous feature by maximizing Gini impurity reduction.

Related Skills

Task

Implement best_binary_split(X_col, y): evaluate midpoints between consecutive sorted unique feature values. Find the threshold yielding maximum Gini gain, returning (best_threshold, best_gain).

Function Signature

best_binary_split(X_col: list[float], y: list[int]) -> tuple[float, float]

Examples

Example 1: Linearly Separable Split
Input: X_col = [1, 2, 7, 8]
y = [0, 0, 1, 1]
Output: [4.5, 0.5]

Example 2: Mixed Values Split
Input: X_col = [1, 2, 3, 4, 5]
y = [0, 1, 0, 1, 1]
Output: [3.5, 0.2133]

Constraints

2 <= len(X_col) == len(y) <= 1000
y consists of integers in `{0, 1}`.

Python3Saved ✓

def best_binary_split(X_col: list[float], y: list[int]) -> tuple[float, float]:

"""X_col: 1D feature values of length n.

y: binary target labels in {0, 1}.

Gini impurity: 1 - sum(p_k^2).

Evaluate candidate thresholds between adjacent sorted unique feature values.

Find split threshold <= t that maximizes Gini Gain = Gini(parent) - (N_L/N * Gini_L + N_R/N * Gini_R).

Return (best_threshold, best_gini_gain) rounded to 4 decimal places.

If all feature values are identical, return (0.0, 0.0)."""

# Your implementation here

pass

Case 1: Linearly Separable Split

Input: X_col = [1, 2, 7, 8]
y = [0, 0, 1, 1]

Expected: [4.5, 0.5]

Case 2: Mixed Values Split

Input: X_col = [1, 2, 3, 4, 5]
y = [0, 1, 0, 1, 1]

Expected: [3.5, 0.2133]