Isolation Forest and average/expected depth formula

The Isolation Forest algorithm (Liu, Fei Tony, Kai Ming Ting, and Zhi-Hua Zhou. "Isolation forest." 2008 Eighth IEEE International Conference on Data Mining. IEEE, 2008. - link: https://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/icdm08b.pdf?q=isolation-forest) tries to assign an anomaly score to observations according to the tree depth obtained by recursively (binary-) splitting them at random based on picking a random value within observed range from a random column at each time, until an observation is alone in a tree branch, given that rarer observations will need fewer splits to become isolated.

In the original paper that describes the Isolation Forest algorithm, it specifies that, since outliers are those which will take a less-than-average number of splits to become isolated and the purpose is only to catch outliers, the trees are built up until a certain height limit (corresponding to the height of a perfectly-balanced binary search tree - $$\lceil\log_2(n)\rceil$$), and if there’s more than 1 observation/row present in a tree that has already reached its height limit, when an observation falls into that node, it will add to it the expected path length for the sample size of that tree to obtain the final path length:

The formula for the expected path length in the paper is given as follows: $$c(n) = 2 H ( n - 1 ) - (2(n-1) / n)$$

With $$H(i) = \log(i) + 0.5772156649$$

Now, from what I understand, the purpose of that formula is to calculate an average depth if the process were continued for trees that divide observations at random. If there are 3 observations, there’s 2 possible ways to split them fully using binary trees:

    .
/ \
.   o
/ \
o   o
-----------
.
/ \
o   .
/ \
o   o


Both are equally likely, and the average path length under both is $$(1 + 2 + 2) / 3 = 1.67$$, but the formula gives $$c(3) = 1.21$$. Similarly, for 4 observations, there’s 3 possible ways to build the trees (plus the exact same ways with horizontal mirroring):

    .
/  \
.    .
/\    /\
o  o  o  o
------------
.
/ \
o   .
/ \
o   .
/ \
o   o
------------
.
/ \
o   .
/ \
.   o
/ \
o   o


In the first case, the average path length is $$2$$, while in the others it’s $$(1 + 2 + 3 + 3) / 4 = 2.25$$, but the first one has a $$\frac{1}{3}$$ probability of being chosen if splitting elements at random, for an overall average of $$2 \frac{1}{3} + 2.25 \frac{2}{3} = 2.167$$, but again the formula gives a lower number: $$c(4) = 1.85$$.

Am I understanding something incorrectly? What’s the formula meant to represent? I get that the actual average path length will be different according to the distribution of the data (e.g. if there's an outlier, chances are higher that the average path length from random uniform splits will be above the expected average, as there will be more splits having the longer structure than the balanced structure), but in any event the paper's formula gives numbers that are lower than the combinatorial average rather than higher.

I’ll answer myself with help from these other questions in the math section: https://math.stackexchange.com/questions/3333220/expected-average-depth-in-random-binary-tree-constructed-top-to-bottom https://math.stackexchange.com/questions/52572/do-harmonic-numbers-have-a-closed-form-expression

From the answer above, the actual expected depth when splitting at random a remaining sample size $$n$$ is given by $$2 (H(n) – 1)$$, where $$H(n)$$ is the harmonic number for $$n$$. The paper gives the formula $$2 H(n – 1) – 2 \frac{n-1}{n}$$, which gives the same result (https://en.wikipedia.org/wiki/Harmonic_number#Identities_involving_harmonic_numbers).

In addition, the paper uses an approximation for the harmonic number $$H(n)$$ which is the limit as $$n$$ tends to infinite (https://en.wikipedia.org/wiki/Harmonic_number#Calculation).

As such, if the sample size for which the approximate depth is determined is large, the actual vs. approximated results will be very close, and it’s not a big deal to use it for the expected average depth (from which the scores are calculated as $$2^{-\frac{E[d]}{c}}$$) in the whole data.

However, the paper also uses it to determine the expected sample size at the end of each node that reaches the height limit, which will be smaller numbers and might be within a range in which the approximation is far from the real results – this usage of the approximation seems quite wrong to me.

The difference between the paper’s approximation and the true value actually differ by less than $$10^{-5}$$ for values of $$n > 5000$$, and by less than $$10^{-3}$$ for values of $$n > 500$$, but for $$n = 4$$, which is reasonable to expect when reaching a height limit, the difference is rather large ($$2.166667 - 1.85 = 0.317$$).

UPDATE: Now, it seems clearly, there are 3 methods to calculate:

1. $$c(3)= 2H(3-1)-2(3-1)/3 =2(H(3)-1)=2(1+1/2+1/3-1)=1.667$$
2. $$c(3) = 2H(3-1)-2(3-1)/3 = 2(\log {(2)}+ 0.57721566)-4/3) = 1.20739$$
3. $$c(3) = 2(H(3)-1) = 2(\log 3+ 0.57721566-1) = 2(1.0986+0.57721566-1) = 1.35$$

method1 is accurate result.
method2 is approximate in the IForest papers and implemented in scikit-learn
method3 is formula simplification then approximate

when the sample size in leaf node is 3,
$$H(3) = 1+1/2+1/3 = 1.833$$
$$H(3)\approx log(3)+0.57721566$$ can be computed by np.log(3)+np.euler_gamma which is 1.675827
All is is different from your computation, Anywhere I am missed?

• $c(3)$ wouldn't be $H(3)$, but $2(H(3)-1)$ Dec 26, 2020 at 18:37
• $c(3) = 2(H(3)-1) = 2(\log 3+ 0.57721566-1) = 2(1.0986+0.57721566-1) = 1.35$, is still different your computation: "but the formula gives c(3)=1.21" Dec 27, 2020 at 3:17
• These are base-2 logarithms if you look at the formula. Dec 27, 2020 at 13:10
• Harmonic number is not $\ln n$ base-e logarithm?en.wikipedia.org/wiki/…. Base-e in scikit-learn, github.com/scikit-learn/scikit-learn/blob/…. from sklearn.ensemble._iforest import _average_path_length, _average_path_length([3]) , we can get sklearn's $c(3)$ is 1.207392, and $c(4)$ is $1.851655$, calculated by $2H(n–1)–2(n−1)/n$ but not $2(H(n)-1)$, which is different as the approx when $H(n-1)$ and $H(n)$ Dec 27, 2020 at 14:39