Isolation Forest: anomaly detection via random splits

The problem, from first principles

Every tree in this curriculum so far picked its splits to separate classes well (Gini impurity, information gain) or fit a target well (variance reduction) — both require knowing what "good" means, which requires labels or targets. Anomaly detection often has neither: there's no "anomalous" label to train against, only a hunch that outliers should somehow be distinguishable from normal points using their raw features alone.

From theory to code

Implement build_isolation_tree, path_length, isolation_forest_fit, and anomaly_scores. No labels anywhere — this is unsupervised, "anomalous" is never told to the model, it falls out of how easy a point is to isolate. Splits are purely random: a random feature, a random threshold within that feature's observed range, no Gini impurity or information gain involved at all.

Constraints

• build_isolation_tree(input, max_depth, rng) picks a random feature and a random threshold within its observed range at every split; stops at a leaf when max_depth runs out, <=1 samples remain, or the chosen feature is constant.
• path_length(tree, x, current_depth=0) returns the split-count depth plus a leaf-size correction, never just the raw split count.
• isolation_forest_fit(input, n_trees, max_depth, seed=None) builds n_trees independent trees, each on the full input (no bootstrapping).
• anomaly_scores(forest, input, sample_size) returns one score per row of input, always in (0, ~1], higher meaning more anomalous.

Hints

Open one at a time. Each gives away a little more than the last.