Problem 565505 · hard · Level 05 Advanced Algorithms & Graphs

A Tree for the Phone Mast

decision trees · recursion · Gini impurity · greedy algorithms · stopping rules · tie-breaking

A phone company surveyed spots around a mast and noted whether there was signal. Grow a decision tree that predicts it. A tree is either a leaf, which is simply a label, or a dictionary

{"feature": f, "threshold": t, "left": <tree>, "right": <tree>}

that sends a spot x to "left" if x[f] <= t and to "right" otherwise.

Write grow_tree(X, y, max_depth, min_size). Growing a node that holds some of the rows (the root holds all of them, at depth 0):

  1. The node becomes a leaf with the node's majority label if its depth equals max_depth, or it has fewer than min_size rows, or all its labels are equal, or no split exists (no feature has two distinct values among its rows).
  2. Otherwise it asks the best question for its rows, as in the previous problem: every feature f and every midpoint t = (a + b) / 2 of neighbouring distinct values a < b of that feature among the node's rows; the lowest size-weighted Gini impurity of the two sides wins; scores within 1e-9 of each other count as equal, and ties go to the smaller f, then the smaller t.
  3. The rows with x[f] <= t grow the "left" subtree and the others the "right" one, both at depth + 1. A node is split even if both of its subtrees end up predicting the same label.

The majority label is the most common label among the node's rows; on a tie, the one that occurs first among them (rows keep the order of X).

The setup provides make_survey(n, seed) (spots [km east, km north] labelled "signal" or "none") and tree_stats(tree), which returns (number of leaves, depth, accuracy on 2000 new spots). Some tests use them.

Examples

Input:  X = [[1], [2], [3], [4]], y = ["a", "b", "b", "a"], max_depth = 2, min_size = 2
Output: {"feature": 0, "threshold": 1.5, "left": "a",
         "right": {"feature": 0, "threshold": 3.5, "left": "b", "right": "a"}}
Explanation: the thresholds 1.5 and 3.5 both score 1/3; the smaller one wins.

Input:  the same, max_depth = 1
Output: {"feature": 0, "threshold": 1.5, "left": "a", "right": "b"}

Input:  make_survey(150, 3), max_depth = 2, min_size = 2
Output: {"feature": 1, "threshold": 2.1500000000000004,
         "left": {"feature": 0, "threshold": 5.35, "left": "none", "right": "none"},
         "right": {"feature": 1, "threshold": 8.25, "left": "signal", "right": "none"}}

Constraints

  • 1 <= len(X) <= 3000, 1 <= len(X[0]) <= 4, 0 <= max_depth <= 12, 1 <= min_size
  • the largest trees have a few hundred leaves: recounting every candidate threshold from scratch at every node is too slow for them
  • floats are compared with a tolerance of 1e-6

Goals

  • Grow a classification tree greedily, one best split at a time
  • Stop at the maximum depth, at small or pure nodes, and when no split exists
  • Follow exact tie rules for splits and for the majority label so that the tree is unique
Starting Python…