In an isolation forest the anomaly score of a point is given by:


Now supposedly c(m) is the average length to termination in the search tree. And, E(h(x)) is the expected length to termination for the particualr point in question.

What is the difference there? What I am missing or can anyone explain the terms (on a high level) in a better way?


Edit: just wrote a post on this, bit of a dive into the score function: https://deltag270510082.wordpress.com/2021/04/15/1437/

First, c(m) comes from binary search tree, which i'll explain, I've always seen it as c(n) in isolationForest terms. They're the same thing though.

c(n) is the average length from root to external node, and the function is actually taken from the average length of unsuccessful searches in a binary tree search - this works out to be the same thing, because an isolationTree is of the same form. It is a constant for a given data set, and the function is derived from BST. We use it because it's conveniently already derived for us.

What the isolationForest algorithm does is find a value for anomaly score, above which data points will be considered outliers. The anomalies are the data points that are easiest to isolate, and thus have the shortest path from root to terminal node. The path length (or branch depth or whatever, the sum of the edges traversed) for an anomaly will then be much shorter than that of a normal point.

E(h(x)) is the average length from root to external node for a specific data point, averaged over a group of trees. (Remember, we're giving the same data to each tree, it's just cutting it up differently). If this data point is anomalous in some of those trees, it's going to drag its path length average down. If the isolationForest is well optimized, anomalies will have very short paths in every tree and the average path length will be much less than c(m), and you can see how that works out in the expression for anomaly score s: as the ratio E(h(x))/c(n) approaches 0, s approaches 1.

So the closer to 1 the anomaly score, the more likely it is an anomaly. The closer to 0, the more 'normal' the data point.

If E(h(x)) is exactly equal to c(n) - unlikely - the anomaly score will be 0.5 and all that can be said is that it is not an anomaly, because if they are equal, x is an inlier by definition. Fun thing to think about: what would happen if you changed the exponent base from 2 to 3? Or some other number?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.