孤立森林算法-异常点检测

前言

  在学习论文的过程中，出现了异常点的检测方法，异常点的检查方法有很多，例如基于偏差的方法（通过去除异常点，使得总体方差缩小）、基于距离的方法（计算邻居距离，异常点一般距离比较远）、基于密度的方法（正常点和近邻点密度是一样的，而异常点的密度和近邻点有较大差异）、深度学习方法等（编码器与解码器），本篇就只介绍孤立森林-iForest（Isolation Forest）。

1、异常点简介

  将异常点定义为“容易被孤立的离群点 (more likely to be separated)”——可以理解为分布稀疏且离密度高的群体较远的点。用统计学来解释，在数据空间里面，分布稀疏的区域表示数据发生在此区域的概率很低，因而可以认为落在这些区域里的数据是异常的。

2、 孤立森林介绍

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

  iForest使用了一套非常高效的策略。假设我们用一个随机超平面来切割数据空间, 切一次可以生成两个子空间（想象拿刀切蛋糕一分为二）。之后我们再继续用一个随机超平面来切割每个子空间，循环下去，直到每子空间里面只有一个数据点为止。直观上来讲，我们可以发现那些密度很高的簇是可以被切很多次才会停止切割，但是那些密度很低的点很容易很早的就被分到一个子空间了。

异常样本相较普通样本可以通过较少次数的随机特征分割被孤立出来。

  例如下图所示：处于分布密集位置的$x_i$用了11个超平面才被孤立，处于分布稀疏位置的$x_0$用了4个超平面即被孤立。

3、 算法思路

  Forest 由 t（论文中推荐取值为100，因为此时$x_i$，$x_0$平均路径长度已经趋于稳定,即收敛）个 iTree 组成，每个 iTree 是一个二叉树结构。该算法大致可以分为两个阶段，第一个阶段，我们需要训练出 t 棵孤立树，组成孤立森林。第二阶段，我们将每个样本点带入森林中的每棵孤立树，计算平均高度，之后再计算每个样本点的异常值分数。

第一阶段：生成t颗孤立树

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

如下图所示：

  我们来模拟一棵孤立树的训练过程，把这九个人作为一个子样本放入一棵孤立树的根节点：

  其中$h(x)$为一个数据点在一棵树中的高度，即从树的根节点需要经历几条边才能够到达叶子结点
  $E(h(x))$为$x$在所有iTree中的平均高度，高度越低，异常得分越高。
  $c(n)$用来归一化，即把异常得分的值限定在[0,1]之间，它表示的是在$n$个数据点下的平均高度（二叉搜索树中查找不成功的平均路径长度）。
$$c(n)=2H(n-1)-(2(n-1)/n)$$
  其中$H(i)$是谐波数(harmonic number)，可以近似为：
$$H(i)\approx ln(i)+0.5772156649$$

故可由（1）公式得到：
$\stackrel{◯}{1}$ 如果$E(h(x))$ $\to$ $c(n)$ ，那么$s$ $\to$ 0.5;

$\stackrel{◯}{2}$如果$E(h(x))$ $\to$ 0 ，那么$s$ $\to$ 1;

$\stackrel{◯}{3}$如果$E(h(x))$ $\to$ $n-1$ ，那么$s$ $\to$ 0;