Where Should the Tree Cut?

A refurbishing shop prices second-hand laptops with a regression tree. Its first question is about a laptop's age in years: is the age at most $t$? Each of the two leaves then predicts the average price of the training laptops that land in it.

To choose $t$, the tree can't use Gini or entropy: those measure how mixed a group of categories is. For numbers like price, it measures the mess with variance, which is how far the prices in a group sit from that group's own average:

Here $|G|$ is the number of laptops in group $G$ and $\bar{p}_G$ is their average price. A split of $n$ laptops into a left group $L$ and a right group $R$ is scored by the weighted variance

and the best split is the one with the lowest score. Its variance reduction is the variance of all $n$ prices minus that score.

Candidate thresholds: sort the distinct ages and try the midpoint between each neighbouring pair. Laptops with age $\le t$ go left, and the rest go right.

Task: write best_regression_split(ages, prices) and return a tuple (threshold, left_mean, right_mean, reduction) for the best split, every value rounded to 4 decimal places.

• ages and prices are the same length, and ages is not sorted.
• Several laptops can share an age, and a threshold never separates them.
• If two thresholds tie for the lowest score, return the smaller one.
• If every laptop has the same age, no split is possible: return None.

This is the question a decision tree asks whenever it predicts a number instead of a category. Each leaf predicts its group's average, so the split that keeps each group's prices tight around its own average is the split whose two averages make the smallest errors.