Isolation Forest.

孤立森林 (Isolation Forest, iForest) 是一个基于集成(Ensemble)和树模型的离群点快速异常检测方法，具有线性时间复杂度和高精准度。

iForest算法通过对样本点的孤立来检测异常值。假设用一个随机超平面来切割数据空间, 切一次可以生成两个子空间。之后再继续用一个随机超平面来切割每个子空间，循环下去，直到每子空间里面只有一个数据点为止。不难发现密度很高的数据簇需要被切很多次才会停止切割，但是那些密度很低的数据点很容易早停到一个子空间。

⚪ iForest的训练过程

iForest算法利用一种名为孤立树 (Isolation Tree, iTree) 的二叉搜索树结构来孤立样本。由于切割是随机的，所以需要用Ensemble的方法来得到一个收敛值（蒙特卡洛方法）。

iForest算法的训练过程如下：

  1. 从训练数据中随机选择$Ψ$个点样本点作为样本子集，放入树的根节点。
  2. 随机指定一个特征维度，在当前节点数据中随机产生一个切割点 $p$（切割点产生于当前节点数据中指定维度的最大值和最小值之间）。
  3. 以此切割点生成了一个超平面，然后将当前节点数据空间划分为2个子空间：把指定维度里小于 $p$ 的数据放在当前节点的左子节点，把大于等于 $p$ 的数据放在当前节点的右子节点。
  4. 在子节点中递归步骤2和3，不断构造新的子节点，直到子节点中只有一个数据（无法再继续切割）或子节点已到达限定高度。
  5. 循环1至4，直至生成 $T$ 个孤立树iTree。

之所以对树的高度做限制，是因为我们只关心路径长度较短的点，它们更可能是异常点；而并不关心那些路径很长的正常点。树的高度一般限制为$\lfloor \log_2 Ψ \rfloor$。

⚪ iForest的推理过程

训练出 $T$ 个iTree组成iForest后，可以将每个样本点带入iForest计算平均高度，之后再计算每个样本点的异常值分数。

对于每一个数据点 $x_i$，令其遍历每一个iTree $T$，计算点 $x_i$在iTree中的高度 $h(x_i)$：

\[h(x_i) = e+c(T.size)\]

其中$e$为样本$x_i$从树的根节点到叶节点的过程中经历的边的个数，即split次数。T.size表示和样本$x_i$同在一个叶子结点样本的个数，$C(T.size)$可以看做一个修正值，表示T.size个样本构建一个二叉树的平均路径长度，$c(n)$计算公式如下：

\[c(n) = 2H(n-1) -\frac{2(n-1)}{n}\]

其中$H(n)$是调和数，可以通过 $\ln(n) + 0.5772156649$（欧拉常数）来估算。加入该修正值的目的是使得异常和正常样本的路径长度差异更大（如果叶子结点的样本数越多，该样本是异常值的概率也较低）。

对样本$x_i$经过所有iTree的高度取平均后做归一化处理，可以得到该样本的异常值分数：

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

当样本的平均高度 $E(h(x))$ 显著小于二叉树的平均路径长度$c(n)$时，$s(x,n) \to 1$，数据点被认为是异常点；当样本的平均高度 $E(h(x))$ 显著大于二叉树的平均路径长度$c(n)$时，$s(x,n) \to 0$，数据点被认为是正常点。如果所有异常得分$s(x,n)$都在 0.5 左右，那么数据集中很可能不存在异常点。

下图为iTree的数目与每个样本点的平均高度的关系，可以看到数目选取在 $10$ 以内时，结果非常不稳定，当数目达到 $100$ 后就趋于收敛了。

⚪ iForest的优点和缺点

iForest算法的优点：

  1. 线性时间复杂度：由于iForest算法是集成算法的变种，所以有线性时间复杂度。通常树的数量越多，算法越稳定；
  2. 分布式加速：由于每棵树都是独立生成的，因此可部署在大规模分布式系统上来加速运算。

iForest算法的缺点：

  1. 对高维数据不友好：由于每次切数据空间都是随机选取一个维度，建完树后仍然有大量的维度信息没有被使用，导致算法可靠性降低；
  2. iForest只能检测全局稀疏点敏感，不擅长处理局部的相对稀疏点(Local Anomaly)。

⚪ 使用sklearn实现iForest

sklearn.ensemble.IsolationForest(
  n_estimators=100,      # iTree的数量
  max_samples='auto',    # 构建子树的样本数，默认min(256, N)
  contamination='auto',  # 异常数据占给定数据集的比例，用于在决策函数中定义阈值
  max_features=1.0,      # 构建每个子树的特征数
  bootstrap=False,       # 采样是有放回还是无放回
  n_jobs=None,           # 并行运行的作业数量
  random_state=None,     # 训练的随机性
  verbose=0,             # 打印日志的详细程度
  warm_start=False       # 是否重用上一次调用的结果
)

该函数提供的方法包括：