Problem 639150 · hard · Level 06 Heuristics & Optimization

Easy to Cut Off, Probably Odd

anomaly detection · isolation forest · random trees · recursion · seeded randomness

Odd points are easy to separate from the rest: cut the data at random places and an outlier ends up alone after very few cuts, while a point in a dense crowd needs many. Average this over many random trees and you have an anomaly score that needs no distances at all.

Write isolation_scores(points, trees, sample_size, seed) that returns one score per point, computed exactly like this. Use a single rng = random.Random(seed) for everything, in this order.

Building the trees. For each of the trees trees: draw rng.sample(range(n), sample_size) (the indices of its points), then build the tree on those points, recursively and depth first (the whole left subtree before the right one). The depth limit is L = ceil(log2(sample_size)). A node at depth depth (the root has depth 0) with the index list idx:

  • becomes a leaf storing len(idx) if len(idx) <= 1 or depth >= L;
  • otherwise picks a feature f = rng.randrange(d). If all points of idx have the same value of feature f, it becomes a leaf storing len(idx) (no new feature is drawn). Otherwise it draws t = rng.uniform(lo, hi), where lo and hi are the smallest and largest value of feature f in idx, and sends the points with value < t to the left child and the rest to the right child.

Scoring. The path length of a point x in a tree is the number of splits it passes on its way to a leaf (going left when x[f] < t), plus c(size) for the size of that leaf, where c(m) = 0 for m <= 1, c(2) = 1, and c(m) = 2·(ln(m - 1) + 0.5772156649015329) - 2·(m - 1)/m otherwise (the average path length a leaf of that size would still have needed). The score of x is 2 ** (-h / c(sample_size)), where h is its path length averaged over all trees. Every point of points is scored, sampled or not.

Scores near 1 mean "isolated quickly, probably an anomaly"; scores well below 0.5 mean "deep inside the crowd". machine_log(n, seed) gives normal machine readings to experiment with.

Examples

Input:  points = [[1], [2], [3], [4], [20]], trees = 1, sample_size = 5, seed = 1
Output: [0.40917716208281496, 0.3037725413732135, 0.3037725413732135, 0.5511556416958947, 0.7423985733390756]
Explanation: the tree cuts at 9.97 (20 is alone after one cut), then at 3.37 (4 is alone after two),
then at 1.98; the leaf {2, 3} is at the depth limit 3, so its points get 3 + c(2) = 4.
With c(5) = 2.327, the score of 20 is 2^(-1/2.327) = 0.742.

Input:  points = [[1], [2], [3], [4], [20]], trees = 3, sample_size = 4, seed = 0
Output: [0.3685283769505774, 0.3252968076440812, 0.3685283769505774, 0.6070653811168756, 0.6877436677788327]

Constraints

  • 2 <= sample_size <= len(points) <= 1000, 1 to 6 features, 1 <= trees <= 200
  • floats are compared with a tolerance of 1e-6

Goals

  • Build random splitting trees on samples of the data with an exactly specified use of randomness
  • Measure how quickly each point is isolated, correcting for leaves that stop early
  • Turn average path lengths into anomaly scores between 0 and 1
Starting Python…