The first question of a decision tree is the one that makes its two sides as pure as possible. The candidate questions are "is feature f at most t?", where for each feature t ranges over the midpoints (a + b) / 2 of every two neighbouring distinct values a < b of that feature in the data. A question sends the rows with X[i][f] <= t left and the others right, and its score is the Gini impurity of the two sides weighted by their sizes, (n_left · G(left) + n_right · G(right)) / n with G(S) = 1 - Σ pᵢ².
Write best_split(X, y) that returns the tuple (f, t, score) of the question with the lowest score. Scores that differ by less than 1e-9 count as equal; among equal scores choose the smallest f, then the smallest t. If no feature has two distinct values, return None.
The setup provides make_survey(n, seed), which returns (X, y): n spots [km east, km north] around a phone mast, labelled "signal" or "none", with 10% wrong readings. Some tests use it.
Examples
Input: X = [[2.0, 1], [3.0, 0], [5.0, 1], [7.0, 0], [8.0, 1]], y = ["no", "no", "yes", "yes", "yes"]
Output: (0, 4.0, 0.0)
Explanation: "feature 0 at most 4.0?" separates the two labels perfectly.
Input: X = [[1, 5], [2, 6], [3, 7], [4, 8]], y = ["a", "a", "b", "b"]
Output: (0, 2.5, 0.0)
Explanation: "feature 1 at most 6.5?" is just as good; the tie goes to the smaller feature.
Input: make_survey(150, 3)
Output: (1, 2.1500000000000004, 0.4301114122252334)
Constraints
1 <= len(X) <= 3000,1 <= len(X[0]) <= 6; labels are strings or integers- floats are compared with a tolerance of
1e-6
Goals
- Search every feature and every midpoint threshold for the split with the lowest weighted Gini impurity
- Update the class counts of the two sides incrementally while sweeping a sorted feature
- Apply a tie rule that is robust to rounding