Improve IsolationForest average depth evaluation

matwey · matwey · commit 08699447bae2 · 2020-03-19T15:01:22.000+03:00
The equation in the original paper is undersimplified:

    c(n) = 2 H(n-1) - 2 (n-1) / n,

where H(k) ~ (ln(k) + gamma)

The definition of the harmonic number is:

    H(n) = sum_{j=1}^{n} (1 / j)

then it follows that:

    H(n) = H(n-1) + 1 / n

and then:

    c(n) = 2 H(n-1) - 2 (n-1) / n = 2 ( H(n-1) - 1 + 1 / n ) =
         = 2 (H(n) - 1)

Here we use simplier equation to save calculations.
diff --git a/sklearn/ensemble/_iforest.py b/sklearn/ensemble/_iforest.py
@@ -501,9 +501,7 @@ def _average_path_length(n_samples_leaf):
 
     average_path_length[mask_1] = 0.
     average_path_length[mask_2] = 1.
-    average_path_length[not_mask] = (
-        2.0 * (np.log(n_samples_leaf[not_mask] - 1.0) + np.euler_gamma)
-        - 2.0 * (n_samples_leaf[not_mask] - 1.0) / n_samples_leaf[not_mask]
-    )
+    average_path_length[not_mask] = 2.0 * (np.log(n_samples_leaf[not_mask])
+                                           + np.euler_gamma - 1.0)
 
     return average_path_length.reshape(n_samples_leaf_shape)
