Note of Isolation Forest

论文：https://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/icdm08b.pdf

一、介绍

作者认为，异常数据存在两个显著的特性：

• 数量少，甚至是极少
• 与正常数据有显著的属性值差异

简单来说，异常是少且非常不同的。

因此，作者要做的就是找出这些异常点，而不是为正常数据建模（传统方法）。作者提出用树的结构去做这件事，并且在论文中会证明异常点更接近根节点（深度浅），正常点离根节点更远（深度深）。

作者称其构造的树为iTree或者Isolation Tree，称构造的树的集合为iForest或Isolation Forest。并且声称iForest只有两个参数：树的数量、子采样(sub-sampling)的大小；且只需要非常小的树的数量和非常小的子采样的大小就可以达到很好地检测效果和收敛效果。

二、Isolation and Isolation Trees

所谓Isolation，就是将一个实例同其他实例分隔开来。因为异常实例是非常少且非常不同的，因此异常实例是对这种分隔很敏感的。

有明显不同的属性值的实例就很容易分隔出来，而且往往比较早就被分隔出来，这也就意味着这些异常实例有比较短的“路径”，也即在树上有较浅的深度。

所谓Isolation Tree，是一棵完全二叉树，每一个节点要么没有孩子要么一定有两个孩子。构造树时，随机地选择数据的一个属性（特征）和随机的该属性的一个值，将数据分为两个部分，对每一个子部分数据再重复这个过程，直到：

• 树的深度达到限制，
• 或者子部分的数据只剩一个，
• 或者子部分的数据的每一个属性值完全相同。

假设所有样本都不一样，那么最终的iTree的叶子节点个数一定是n，非叶子节点数一定是n-1，那么总的叶子节点数就是2n-1，因此iTree的内存需求是线性的且有明确上限（2n-1）。

异常检测的任务是对每一个实体给定一个异常分数（等级），作者用每一个实体的平均路径长度（也即异常分数）对这些数据进行排序，而所谓的异常，就是在这个排好序的列表中靠前的那些。

路径长度h(x)：就是一个实体从根节点到其所在叶子节点的路径长度。

异常分数：

其中E(h(x))是一堆Isolation Tree 的h(x)的均值，c(n)是BST平均搜索失败的平均长度：

 

 

且：

s是h(x)的单调递减函数；0 < s <= 1，0 < h(x) <= n-1。用这个异常分数，可以做出下面的判断：

• 如果实例返回的s非常接近1，那么可以确定是异常无疑了
• 如果实例返回的s远小于0.5，那么也可以确定绝对不会是异常了
• 如果实例返回的s非常接近0.5，那么就无法判断是否是异常（可能是特征不够或者特征差异小）

三、Isolation Trees 的特征

隔离森林在小样本上表现更好；更多的样本反而会影响iForest的能力，因为正常样本会干扰隔离过程，影响不正常样本的树的深度。子采样可以为iForest提供一个小样本的环境。

异常检测的两个常见问题：swamping，masking：

• Swamping：正常点离异常点很近，就容易把正常点错误地标记为了异常点
• Masking：异常点过多，掩盖了他们自己作为异常的存在，容易为认为是正常点

利用子采样的特性，iForest可以有效减轻Swamping和Masking的影响：

• 子采样可以控制样本数据的大小
• 每一棵Isolation tree 都不一样，因为每一次子采样的数据集完全不一样，这就使得每一棵树上的异常点都不一样

四、使用iForest进行异常检测

使用iForest进行异常检测主要分为两个步骤：

• 训练：对样本数据进行子采样，构造Isolation Tree；
• 测试：将测试数据放到树里面，得到测试数据的异常分数

4.1 训练过程

对给定训练数据进行子采样，根据子采样的样本集构建树（构建过程见第二部分的描述），树的深度限制L由子采样的大小ψ确定：L=ceiling(log2 ψ)。

算法：

 

iForest有两个输入参数：子采样大小ψ和树的数量t

• 子采样大小ψ控制训练数据的大小，当ψ达到一定值时，再增加ψ值不会带来检测性能上的提升，却会增加内存和时间的消耗；作者发现256是一个比较合适的数值
• 树的数量t控制整个树集合的大小；作者发现100是个比较合适的数值

训练过程的时间复杂度是：O(tψlogψ)

4.2 评估过程

让验证集的每个实例通过iForest的每一棵树，使用下面的PathLength方法计算每个实例通过的路径长度，然后再用计算s(x,ψ)（第二部分给出的方程），得到每个实例的异常分数。

评估过程的时间复杂度是：O(ntlogψ)