隔离森林算法（Liu、Fei Tony、Kai Ming Ting 和 Zhi-Hua Zhou。“隔离森林。”2008 第八届 IEEE 国际数据挖掘会议。IEEE，2008。-链接：https ://cs.nju.edu .cn/zhouzh/zhouzh.files/publication/icdm08b.pdf?q=isolation-forest ) 尝试根据通过递归（二进制）随机拆分它们获得的树深度为观察分配异常分数每次从随机列观察到的范围内的值，直到观察在树枝中单独存在，因为较少的观察将需要较少的分裂才能成为孤立的。

在描述隔离森林算法的原始论文中，它指定，由于异常值是那些需要少于平均数量的分割才能成为孤立的值，并且目的只是为了捕捉异常值，所以树会一直建立，直到一定的高度限制（对应于完美平衡二叉搜索树的高度 -$\lceil\log_2(n)\rceil$)，并且如果在已经达到其高度限制的树中存在超过 1 个观察值/行，则当观察值落入该节点时，它将向其添加该树的样本大小的预期路径长度以获得最终路径长度：

论文中预期路径长度的公式如下：

和

现在，据我了解，该公式的目的是计算平均深度，如果该过程继续用于随机划分观察的树木。如果有 3 个观察值，则有 2 种可能的方法可以使用二叉树将它们完全拆分：

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

两者的可能性相等，两者下的平均路径长度为$(1 + 2 + 2) / 3 = 1.67$，但公式给出$c(3) = 1.21$. 同样，对于 4 次观察，有 3 种可能的方式来构建树（加上与水平镜像完全相同的方式）：

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

在第一种情况下，平均路径长度为$2$, 而在其他人中是$(1 + 2 + 3 + 3) / 4 = 2.25$，但第一个有一个$\frac{1}{3}$如果随机拆分元素，则被选中的概率，总体平均值为$2 \frac{1}{3} + 2.25 \frac{2}{3} = 2.167$，但公式再次给出了一个较低的数字：$c(4) = 1.85$.

我是否理解错误？公式是什么意思？我知道实际的平均路径长度会根据数据的分布而有所不同（例如，如果存在异常值，随机均匀分割的平均路径长度将高于预期平均值的可能性更高，因为会有更多的分割具有比平衡结构更长的结构），但无论如何，该论文的公式给出的数字低于组合平均值而不是更高。