From Cuts to a Score

An isolation forest has been grown on a table of card payments. Every tree was built on a random sample of sample_size rows and split at random until each point stood alone. For each payment you want to score, you're given its path length in every tree: the number of cuts it took to isolate it.

Raw path lengths are hard to compare: a tree grown on 256 rows needs more cuts for everyone than a tree grown on 16. So the average path length is measured against $c(n)$ , the path length an ordinary point is expected to need in a random tree built on $n$ rows:

c(n) = 2H(n-1) - \frac{2(n-1)}{n}

where $H(i)$ is the harmonic number

H(i) = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{i}, \qquad H(0) = 0

Use this exact sum, not an approximation of it. A point whose path lengths average $\bar h$ gets the anomaly score

s = 2^{-\bar h / c(n)}

with $n$ = sample_size. A score near 1 means the point was cut off far faster than an ordinary point; a score around 0.5 means it took about as many cuts as expected.

Task: write isolation_scores(path_lengths, sample_size). path_lengths[i] is the list of point i's path lengths, one per tree. Return one score per point, in order, each rounded to 4 decimal places. sample_size is at least 2.

From Cuts to a Score

Examples

Hints