Is Rain the Better Question?

A commuter logged how she got to work: X[i] = [temperature in °C, rain in mm] and y[i] is "bike" or "bus". A decision tree could start with a question like "is rain at most 2 mm?". How good is that question?

The question "is feature f at most t?" sends every example with X[i][f] <= t to the left side and the others to the right. Write split_report(X, y, f, t) that returns a tuple (n_left, n_right, gini, gain):

• n_left, n_right: the number of examples on each side;
• gini: the Gini impurity of the two sides weighted by their sizes, (n_left · G(left) + n_right · G(right)) / n, where G(S) = 1 - Σ pᵢ² over the label proportions of S;
• gain: the information gain, H(all) - (n_left · H(left) + n_right · H(right)) / n, where H(S) = -Σ pᵢ log₂ pᵢ is the entropy in bits.

An empty side has impurity and entropy 0.

Examples

Input:  X = [[12, 0], [18, 0], [22, 0], [9, 3], [15, 6], [25, 1]]
        y = ["bike", "bike", "bike", "bus", "bus", "bike"], f = 1, t = 2.0
Output: (4, 2, 0.0, 0.9182958340544896)
Explanation: the four dry days are all "bike" and the two wet ones "bus", so both sides are
pure. The whole log (4 bike, 2 bus) has entropy 0.918 bits, all of which is gained.

Input:  the same log, f = 0, t = 13.5
Output: (2, 4, 0.4166666666666667, 0.044110417748400965)

Constraints

• 1 <= len(X) <= 10**4, 0 <= f < len(X[0]); labels are strings or integers
• floats are compared with a tolerance of 1e-6

Goals

• Divide labelled examples by a threshold question on one feature
• Score the split by the size-weighted Gini impurity of its two sides
• Compute the information gain: the entropy of the whole minus the weighted entropy of the sides