Isolation Forest Score Function Theory

Question

Isolation Forest Score Function Theory

Samyak Shah

2022年5月29日 11:07

I am currently reading this paper on isolation forests. In the section about the score function, they mention the following. For context, $h(x)$ is definded as the path length of a data point traversing an iTree, and $n$ is the sample size used to grow the iTree.

The difficulty in deriving such a score from $h(x)$ is that while the maximum possible height of iTree grows in the order of $n$, the average height grows in the order of $log(n)$. Normalization of $h(x)$ by any of the above terms is either not bounded or cannot be directly compared.

So herein lies my first question. What do they mean that the normalization of $h(x)$ by any of the above terms is either not bounded or cannot be directly compared? The final score function in this paper is given by

$$s(x,n)=2^{-\frac{E(h(x))}{c(n)}}$$

where

$$c(n)=2H_{n-1}-2(n-1)/n$$

is the average path length of an unsuccessful search from BST Theory. Note how they are taking the expectation of the path. So in that case we are averaging all the values anyway, so why can we not use the growth of the average height of the tree? Additionally they don't even mention the analytical form of average height here, which from what I gather is $2\sqrt{\pi n}$ reference, though I have not read this reference thoroughly and may be mistaken.

Am I missing something here?

Topic anomaly-detection decision-trees random-forest

Category Data Science

Ben Reiniger · Accepted Answer · 2019年4月17日 02:36

I'm not certain on your first question; the paper does seem poorly written in this part. They seem to be arguing that taking just $E(h(x))/n$ or $E(h(x))/\log n$ are inappropriate. The former tends to zero regardless of $x$, but the latter should be reasonable. Indeed, since $c(n)\sim 2\log n$, it's not far off from what they end up doing. (Exponentiation pushes the scores into the range $[0,1]$ which is nice, and using the more exact $c(n)$ calibrates things better for "(c) if all the instances return $s\approx 0.5$, then the entire sample does not really have any distinct anomaly.")

The rest of the confusion seems to be stemming from what set we're averaging over. In the isolation forest paper, the averaging is of the depths of (the leaf containing) $x$ over multiple trees in the isolation forest. In the other reference, the average is of the height of all binary trees on $n$ nodes.

Isolation Forest Score Function Theory

About