异常检测-孤立森林

Posted on   |   In

iForest

iForest (Isolation Fores,孤立森林)是一种用于异常检测的模型，由周志华老师和他的学生等在2008年提出。孤立森林的基本思想是异常对象比起正常对象更容易被孤立。而孤立森林由多棵孤立树组成。孤立树来自于不断从样本数据中随机选择特征，并随机选择一个分割点进行二元划分生成子树，直到叶子节点中的每一个元素都被孤立，或者达到预先设置的最大高度。下面说一下孤立森林的特点以及算法的详细步骤。

下采样

与一般的异常检测方法需要大量的数据不同，孤立森林需要的数据量非常小。甚至需要通过下采样来增加检测的性能。在论文中，推荐的下采样值为 256 。并且论文中也提到，这个值可以用于很大范围的数据集。下采样值为 256 表示从原始样本中随机抽取 256 个数据(无放回)来训练一颗孤立树。每生成一棵树都需要重新进行采样。这里可以看出，孤立森林也是采样了提升方法中的装袋。即通过自助法从原始数据集中通过随机抽样的方式生成多个数据子集，并通过这些子集训练多个分类器以提高分类正确率。不同的是，在孤立森林中训练的是孤立树，而不是分类树

随机选择

在进行孤立树的生成时，用于进行分割的特征和分割点都是随机选择的。

无监督

孤立森林是无监督异常检测算法，因此训练样本与测试样本相同。

详细算法

孤立森林主要分为训练和检测两个阶段。

训练

训练阶段主要是生成孤立树和孤立森林。孤立树与二元分类树结构相同，同样是使用超平面对样本空间不断划分。当对样本进行检测时，需要将样本输入孤立树，并判断样本最终落在哪个叶子节点。对于一个森林，论文中推荐由100 棵孤立树组成。孤立树对训练样本不断进行划分直到样本被孤立(叶子节点中只含有一个样本)，或者生长到最大高度。最大高度 $l$ 由 下采样数 $ψ$ 控制。公式为:
$$
l = ceiling(log2 ψ)
$$
生成一颗孤立树的算法如下:

算法1: $iTree(X,e,l)$

输入: $X$ - 输入数据，$e$ - 当前树的高度，$l$ - 最大高度

输出: 一棵孤立树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
> if e >= l or |X|  <=1 then:
>     return exNode{ size <- |X| }
> else 
>     let Q be a list attributes in X
>     randomly select an attribute q ∈ Q
>     randomly select a split point p from max and min
>     values of attribute q in X
>     Xl ← filter(X,q < p)
>     Xr ← filter(X,q ≥ p)
>     return inNode{Left ← iTree(Xl,e + 1,l),
>     Right ← iTree(Xr,e + 1,l),
>     SplitAtt ← q,
>     SplitValue ← p}
> end if
>

其实就是不断随机选择特征和分割点对训练样本进行划分，划分的方式与二元分类树相同。直到:

  1. 该节点只包含一个元素
  2. 树达到了最大高度

每生成一课孤立树就要对原始数据进行一次采样，并生成一个子集用于训练。生成的所有孤立树组合为一个孤立森林。

检测

检测阶段使待检测的样本输入每一颗孤立树，并得到该样本经历的平均高度。样本最终的异常得分由以下公式给出:
$$
c(n) = 2H(n − 1) − (2(n − 1)/n)
$$

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

其中 $n$ 该树接受的训练样本数量。平均高度 $h(x)$ 分两种情况进行计算:

  1. 样本 $x$ 最终落在 size 为 1 的叶子节点:

    $h(x)=从根节点开始到叶子节点经过的边数$

  2. 样本 $x$ 最终落在 size > 1 的叶子节点:

    $h(x)=从根节点开始到叶子节点经过的边数 + c(该孤立树的样本大小)$

size 表示训练时落在该叶子节点的训练样本数量。

通过计算每一颗孤立树的$h(x)$，求得平均$E(h(x))$，并计算异常得分$s(x,n)$。异常得分为一个归一化的值，代表的意义:

  1. 如果一个待检测样本的异常得分趋近于1，则该样本是一个异常点
  2. 如果一个待检测样本的异常得远小于0.5，则该样本应该被视为正常点
  3. 如果所有待检测的样本得分都约为0.5，则数据中没有十分异常的样本

SCiForest

SCIForest(Isolation Forest with Split-selection Criterion) 是孤立森林的改进版。熟悉决策树的同学应该知道，孤立森林是使用平行于坐标轴的超平面对数据集进行划分。对于全局异常点来说，这种方法比较有用。但是对于局部异常点，平行坐标轴的划分方式往往无法将局部异常点较近的数据分开。因此 SCIForest 先将数据映射到一个随机的超平面(而不是孤立森林中映射到坐标轴在的平面)，对于映射后的数据，再使用一个最有超平面将其划分开，使得划分后的两组数据标准差最小。

SCiForest 与 iForest 的最大区别是 SCiForest 用来对数据划分的超平面不是平行于坐标轴的，这一点类似于斜决策树。

SCiForest 提升了 iForest 对Scattered anomalies和Clustered anomalies的检测能力，论文中对其定义如下:

Scattered anomalies are anomalies scattered outside the range of normal
points.

Clustered anomalies are anomalies which form clusters outside the
range of normal points

这也就是异常检测中经常遇到的 masking(屏蔽) 问题。

参考

[1] Liu F T, Kai M T, Zhou Z H. Isolation Forest[C]// Eighth IEEE International Conference on Data Mining. IEEE, 2009:413-422.

[2] Liu F T, Kai M T, Zhou Z H. On Detecting Clustered Anomalies Using SCiForest[C]// European Conference on Machine Learning and Knowledge Discovery in Databases. Springer-Verlag, 2010:274-290.