Best Gini Split

This is the single decision a tree makes at every node, applied recursively.

The Gini impurity of a set of labels is

gini(S) = 1 - sum_c p_c^2

where p_c is the fraction of S with label c. A split on feature j at threshold t sends rows with X[i, j] <= t left and the rest right, and is scored by the size weighted impurity of the two children:

score = (n_left / n) * gini(left) + (n_right / n) * gini(right)

Consider only thresholds that are midpoints between consecutive unique values of a feature, so both children are non-empty. Return the (feature_index, threshold) with the lowest score, breaking ties by the lower feature index and then the lower threshold.

If no feature has more than one unique value, return (-1, 0.0).

Function signature

def best_split(X, y):

Example

Input

X = np.array([[1.0], [2.0], [3.0], [4.0]])
y = np.array([0, 0, 1, 1])
best_split(X, y)

Output

(0, 2.5)

Reasoning

The candidate thresholds are 1.5, 2.5 and 3.5. At 2.5 both children are pure, so the weighted Gini is 0. The other two thresholds each leave one mixed child, so 2.5 wins.

Constraints and notes

• Only try midpoints between consecutive unique values.
• Break ties by the lower feature index, then the lower threshold.
• Return (-1, 0.0) when no split is possible.