异常检测-孤立森林增补版

Posted on   |   In

最近又补了一下孤立森林的增补版，也就是发表在 Isolation-Forest 之后的 Isolation-based Anomaly Detection 。这篇文章主要增加了关于孤立森林为什么比其他检测器表现优秀的原因，另外还增加了一些新的调节检测效果的内容。这篇文章准备对上一篇一些没有讲清楚的概念进行进行一些补充，以及对 Isolation-based Anomaly Detection 中增加的内容也会做一些说明。

相关概念

孤立

孤立是孤立森林的一大核心思想，孤立森林认为：异常点较正常点更容易被孤立。这里给出孤立的定义:

采用某种划分方式对样本空间进行划分，形成多个子空间。如果某个子空间中只含有一个样本，或一类完全相同的样本，那么这个(些)样本被孤立。

对应到孤立森林中即是使用平行与坐标轴的超平面对样本进行划分。如果某个叶子节点中只含有一个或一类完全样本，那么这个(些)样本被孤立。

高度与异常值

从理想情况来看，到最后每一个叶子节点都只含有个样本，也就是说所有的样本都成功被孤立。而此时，孤立样本的异常程度就与样本落在节点的高度成反比。也就是落在越靠近根节点的样本越容易被孤立，异常的程度也就越高。

但是由于数据不是均匀分布，所以每次进行划分时左右两个子节点获得的数据量不一定均匀的。而由于数的最大高度被设置为$log(x)$，$x$ 为样本的个数，除非每一个节点的样本被均分，否则某几个叶子节点最后的样本数量一定会大于1。而这种情况导致了这些节点上的样本都没有成功被孤立，也就无法单纯通过判断的节点的高度来判断异常程度。因此论文中提出了使用修正值进行修正:

1
2
3
4
5
6
if n > 2:　// n表示形成一颗书的样本个数
	c(n) = 2H(n-1) - 2(n-2)
else if n = 2:
	c(n) = 1
else:
	c(n) = 0

这里的 c(n) 就是用来进行修正的函数。其中的 $H(x)$ 表示调和级数，可以使用$log(x) + 0.5772156649$ 来近似。c(n) 的含义是一颗二叉树搜索树未成功搜索的平均高度。对应孤立树也就是样本未被孤立的平均高度。而最终的修正结果如下，对与孤立树 $T$，样本$x$落在叶子节点为$N$，修正之后的高度为:
$$
h(x) = e + c(N.size)
$$
这是可以理解的，因为x落在的叶子节点如果还含有其他的样本，那么根据这些样本还可以生成新的子树，因此在原本的高度$e$加上这些样本继续生成子树的平均高度来进行修正(这里其实应该加上成功搜索的高度，但是估计是为了统一，因此采用未搜索成功的高度)。最终异常得分为:
$$
s(x,\psi)=2^{-\frac{E(hx)}{c(\psi)}}
$$
相当于将样本的高度除以了树的平均高度进行了标准化。从这个公式可以看出:

  • 如果一个样本的平均高度远大于树的未成功搜索高度，那么得分趋近与0。该样本正常。
  • 如果一个样本的平均高度远小于未成功搜索的树的高度，那么得分趋近于１，该样本异常。
  • 如果一个样本集合中所有高度约等于未成功搜索的树的高度，那么这些样本得分趋近与0.5。该样本集合无明显异常。

新增内容

hlim

检测时如果大于hlim，则直接返回检测结果。不需要进行到叶子节点才返回。hlim影响了孤立森林的检测行为。比较直观的是，当 hlim=1 时，一些小的团会被全部检测为异常点。当 hlim=6 时，小的团附近的点会被检测未异常点。

处理高维数据

当涉及到维度很高的数据时，论文中采用了一种kurtosis方式来选取一些子特征来构建孤立树。具体选取方式还没看，如果有时间看了再补上。

为什么孤立森林更由于基于距离和密度的异常检测

  1. 基于距离的方式无法处理多密度的情况
  2. 有可能局部密度高的地方从全局来看是异常点，也可能局部密度低的地方从全局来看是正常点
  3. 这两种方式对参数选取十分敏感
  4. 这两种参数计算复杂度很高