一.简介

孤立森林（Isolation Forest）于2008年由西瓜书作者周志华团队提出，凭借其线性的时间复杂度与优秀的准确率被广泛应用于工业界中结构化数据的异常检测。

孤立森林的基本理论基础有二：

异常数据占总样本量的比例很小；

异常点的特征值与正常点的差异很大。

对孤立森林的通俗理解

一句话总结孤立森林的基本原理：异常样本相较普通样本可以通过较少次数的随机特征分割被孤立出来。样本空间有一批数据，其有的地方分布密集，有的地方分布稀疏，如果该批数据大部分样本都分布密集，那么稀疏的那部分是不是就是所谓的离群点？那么孤立森林是如何找出这些离群点的呢？

例如：假设这批样本点有一个特征为年龄，孤立森林随机选择认为年龄>70为异常，年龄<=70为正常。此时相当于在样本空间，画出了一个超平面。接着孤立森林再选了一个特征为收入，认为收入>1w为异常，收入<=1W为正常，此时则又在样本空间画出了一个超平面......根据直觉，是不是分布稀疏位置的点可以通过较少次数的超平面划分被孤立出来，而分布密集位置的点需要更多次数的超平面划分才能被孤立。如下图所示，处于分布密集位置的用了11个超平面才被孤立，处于分布稀疏位置的用了4个超平面即被孤立。

假设一棵树通过这个方法认为是离群点，这一结果是未必准确的，因为随机选特征与阈值存在着诸多偶然性。但是如果引入bagging的思想，我用100棵树进行这样的随机分割，其中90颗的结论都是认为是离群点，那么这个结果就比较可信了。

二.算法细节

单棵树的训练

1.从训练数据中随机选择 Ψ 个点作为子样本，放入一棵孤立树的根节点；

2.随机指定一个维度，在当前节点数据范围内，随机产生一个切割点 p —— 切割点产生于当前节点数据中指定维度的最大值与最小值之间；

3.此切割点的选取生成了一个超平面，将当前节点数据空间切分为2个子空间：把当前所选维度下小于 p 的点放在当前节点的左分支，把大于等于 p 的点放在当前节点的右分支；

.在节点的左分支和右分支节点递归步骤 2、3，不断构造新的叶子节点，直到叶子节点上只有一个数据（无法再继续切割） 或树已经生长到了所设定的高度 。

如何整合多棵树的结果？

孤立森林与随机森林相似，都是通过随机采样数据来对每棵树进行训练，从而保证构建的森林的方差足够大，即每棵树之间越不相似越好。 在构建孤立森林时，需要设定两个参数：树的数量t和每棵树采样样本大小的最大值Ψ 。

孤立森林通过引入异常值函数s(x,n)来衡量记录x 是否为异常点

其中，E(h(x))为x在多棵树中的路径长度的期望值。

其中，c(n)为一个包含n个样本的数据集，树的平均路径长度，用来标准化记录x的路径长度。H(*)为调和数，ξ为欧拉常数，约为0.5772156649。

s(x,n)与E(h(x))的关系

isolation forest伪代码

一个树的最大高度

异常得分

如果异常得分接近 1，那么一定是异常点；

如果异常得分远小于 0.5，那么一定不是异常点；

如果异常得分所有点的得分都在 0.5 左右，那么样本中很可能不存在异常点。

三.FAQ

qes: 树的棵树如何选择？

ans: 通过下图可以发现，当t>=100后，划分上文提到的xi和x0的平均路径长度都已经收敛了，故因此论文中推荐t设置为100。

平均路径长度与t的关系

qes: 样本采样量Ψ如何取值？

ans:论文中推荐Ψ设置为256，其能够提供足够的细节给异常检测任务。下图展示了部分采样的作用，蓝色代表正常样本，红色代表异常样本。可以看出，在采样之前，正常样本和异常样本出现了重叠，因此很难分开，但通过采样之后，异常样本和正常样本可以明显的分开。另外采样可以降低计算时间和空间上的浪费。

参考：

https://www.jianshu.com/p/dbb98e9d8aa4

https://zhuanlan.zhihu.com/p/492469453