孤立森林

1 孤立森林

isolation，意为孤立/隔离，是名词，其动词为isolate，forest是森林，合起来就是“孤立森林”了，也有叫“独异森林”，好像并没有统一的中文叫法。可能大家更习惯用其英文的名字isolation forest，简称iForest。

iForest算法用于挖掘异常(Anomaly)数据，或者说离群点挖掘，总之是在一大堆数据中，找出与其它数据的规律不太符合的数据。通常用于网络安全中的攻击检测和流量异常等分析，金融机构则用于挖掘出欺诈行为。对于找出的异常数据，然后要么直接清除异常数据，如数据清理中的去除噪声数据，要么深入分析异常数据，比如分析攻击、欺诈的行为特征。

2 算法原理

与随机森林由大量决策树组成一样，iForest森林也由大量的树组成。iForest中的树叫isolation tree，简称iTree。iTree树和决策树不太一样，其构建过程也比决策树简单，因为其中就是一个完全随机的过程。

假设数据集有N条数据，构建一颗iTree时，从N条数据中均匀抽样(一般是无放回抽样)出ψ个样本出来，作为这颗树的训练样本。

在样本中，随机选一个特征，并在这个特征的所有值范围内(最小值与最大值之间)随机选一个值，对样本进行二叉划分，将样本中小于该值的划分到节点的左边，大于等于该值的划分到节点的右边。

这样得到了一个分裂条件和左、右两边的数据集，然后分别在左右两边的数据集上重复上面的过程，直接达到终止条件。终止条件有两个，一个是数据本身不可再分(只包括一个样本，或者全部样本相同)，另外一个是树的高度达到log2(ψ)。不同于决策树，iTree在算法里面已经限制了树的高度。当然不限制也可以，只是算法为了效率考虑，只需要达到log2(ψ)深度即可。

把所有的iTree树构建好了，就可以对测数据进行预测了。预测的过程就是把测试数据在iTree树上沿对应的条件分支往下走，直到达到叶子节点，并记录这过程中经过的路径长度h(x)，即从根节点，穿过中间的节点，最后到达叶子节点，所走过的边的数量(path length)。

最后，将h(x)带入，计算每条待测数据的异常分数(Anomaly Score)，其计算公式为：

$ s(x,n) = 2^{(-frac{E( { h(x) })} { c(n) } )} $

其中 $ c(n) = 2H(n − 1) − (2(n − 1)/n) $ 是二叉搜索树的平均路径长度，用来对结果进行归一化处理, 其中的H(k)可以通过公式 $ H(k) = ln(k) + xi $来估计，$xi$是欧拉常数，其值为0.5772156649。

$ h(x)$ 为路径长度，$ E(h(x)) $ 为森林中所有iTree树的平均路径长度。

使用异常分数，具有以下性质：

1. 1、如果分数越接近1，其是异常点的可能性越高；

2. 2、如果分数都比0.5要小，那么基本可以确定为正常数据；

3. 3、如果所有分数都在0.5附近，那么数据不包含明显的异常样本。

上面的步骤，可以总结为两步：

1. 1、训练：从训练集中进行采样，并构建iTree树；

2. 2、测试：对iForest森林中的每颗iTree树进行测试，记录path length，然后根据异常分数计算公式，计算每条测试数据的anomaly score。

3 算法特点

在论文中，也比较了其它的常用异常挖掘的算法。比如常用的统计方法，基于分类的方法，和基于聚类的方法，这些传统算法通常是对正常的数据构建一个模型，然后把不符合这个模型的数据，认为是异常数据。而且，这些模型通常为正常数据作优化，而不是为异常数据作优化。而iForest可以显示地找出异常数据，而不用对正常的数据构建模型。

由于异常数据的两个特征（少且不同： few and different）

1. 1、异常数据只占很少量;

2. 2、异常数据特征值和正常数据差别很大。

异常数据的这两个特征，确定了算法的理论基础。因此，构建二叉树型结构的时候，异常数据离根更近，而正常数据离根更远，更深。算法为了效率考虑，也限定了树的深度：ceil(log2(n))，这个值近似于树的平均深度，因为只需要关心那些低于平均高度的数据点，而不需要树进行完全生成。

算法只需要两个参数：树的多少与采样的多少。实验发现，在100颗树的时候，路径的长度就已经覆盖得比较好了，因此选100颗也就够了。采样，是为了更好的将正常数据和异常数据分离开来。有别于其它模型，采样数据越多，反面会降低iForest识别异常数据的能力。因为，通常使用256个样本，这也是scikit-learn实现时默认使用的采样数。

由于算法只需要采样数据256条样本，并且对树的深度也有限制，因此，算法对内存要求很低，且处理速度很快，其时间复杂度也是线性的。

不像其它算法，需要计算距离或者密度来寻找异常数据，iForest算法可以很好的处理高维数据和大数据，并且也可以作为在线预测。假设采样为256条，结点最大为511个，假设一个节点占b字节，共使用t颗树，那么需要的内存只有511tb字节，基本上只需要几M到几十M的内存就够了。数据还显示，预测287,748条数据只花了7.6秒。

另外，iForest既能发现群异常数据，也能发现散点异常数据。同时也能处理训练数据中不包含异常数据的情况。