Best split on one feature
Medium15 min12 hidden tests
A credit tree is choosing its first split on applicant income, in thousands of dollars. Labels are 1 for applicants who defaulted and 0 for those who repaid. Write best_split(x, y) that tries every threshold between neighboring income values and returns the one with the lowest weighted Gini impurity, together with that impurity. Applicants with income at or below the threshold go left, the rest go right.
Drag the threshold along income
weighted Gini = (n_left · G_left + n_right · G_right) / nAt 27.5: left 1 (1 defaulted), Gini 0; right 5 (3 defaulted), Gini 0.48. Weighted (1 × 0 + 5 × 0.48) / 6 = 0.4. The lowest is 0.2222, at 57.5.
Threshold 27.5, weighted Gini 0.4.
Examples
The best cut leaves one side pure
best_split([20, 35, 50, 65, 80, 95], [1, 1, 1, 0, 0, 1])
returns (57.5, 0.222222)
Unsorted incomes, and a perfect split exists
best_split([42, 18, 30, 55, 25, 61], [0, 1, 1, 0, 1, 0])
returns (36, 0)
Requirements
xis a list of n numbers andya list of n int labels, n >= 1.xmay be unsorted and may repeat values.- Candidate thresholds are the midpoints between consecutive distinct values of
x, sorted. Left isx <= tand right isx > t. - Weighted Gini = (n_left * gini(left) + n_right * gini(right)) / n, where gini is 1 minus the sum of squared class shares.
- Return a tuple
(threshold, weighted_gini)of two floats. On a tie, keep the smaller threshold. - If
xhas only one distinct value, there is no split: return(None, gini(y)).
The idea behind it
A decision tree grows by asking one yes or no question at a time, such as "is income at most 57.5?". For a numeric feature, the only thresholds worth trying sit between neighboring distinct values. Any threshold in the same gap sends the same applicants left, so trees use the midpoint. Each candidate splits the node into two children. The split's quality is the weighted Gini impurity: each child's impurity, weighted by its share of the applicants. Weighting matters because a child with two pure applicants should not outweigh a mixed child with fifty. The tree keeps the split with the lowest weighted impurity, then repeats inside each child. Real libraries sort each feature once and update the class counts as the threshold slides, but they compute the same score.