Best Threshold Split

Problem

Find the threshold that maximizes information gain when splitting samples by feature value. Candidate thresholds are midpoints between consecutive distinct feature values, and a valid split needs samples on both sides; ties keep the smallest threshold. Return [threshold, gain] with entropy in bits, or [0.0, 0.0] when no valid split exists.

Hint

Sort the distinct feature values, try each gap, and keep the best gain with a small epsilon for tie handling.

Test cases

case 1

in: [[1,2,3,4],["a","a","b","b"]]

expected: [2.5,1]

case 2

in: [[1,1,1],["a","b","a"]]

expected: [0,0]

case 3

in: [[1,2,3,4,5,6],["a","a","a","b","b","b"]]

expected: [3.5,1]

case 4

in: [[1,2,3],["a","b","a"]]

expected: [1.5,0.2516291673878229]

case 5

in: [[5],["a"]]

expected: [0,0]

Starter codePython

import math
def best_threshold_split(features, labels):
    # Your code here
    pass

5 test cases · run your code against them in the editor