异常检测算法之孤立森林原理介绍

1. 算法起源

Isolation Forest(简称iForest)，我们习惯称为孤立森林，起源于2008年的一篇论文《Isolation Forest》，由莫纳什大学的两位教授和周志华教授共同完成，在11年他们又一起发表了《Isolation-based Anomaly Detection》，这两篇论文算是确定了这个算法的基础。

论文1

论文2

2. 算法特点

大多数基于模型的异常检测算法会先规定正常点的范围或模式，如果某个点不符合规定的模式或者正常范围内，那么模型会将其判定为异常点，而孤立森林的不同之处在于：

它基于孤立的概念检测异常，不使用任何距离或密度测量，省去了基于距离计算的主要计算成本。

它使用子采样的方式作集成，这样能够实现 (i) 较低的线性时间复杂度和较小的内存需求，以及 (ii) 有效处理 swamping(误报) 和 masking(漏报) 的影响。

它在包含大量不相关属性的高维问题以及训练样本中无法获取到异常标签时也能表现较好。

比如密度测量假设”正常点出现在密集区域，而异常点出现在稀疏区域”，而距离测量的假设是”正常点离它的邻居很近，而异常点离它的邻居很远”，但实际中高密度和短距离并不总是意味着正常实例，特别是在在局部环境中测量时，具有这些特征的点可能是全局数据集中的异常。但是基于路径长度的iForest就没有这块的歧义，在如下被正常点包围的异常模式中，iForest通过高异常分数(>0.7)可以将13个异常点与周围的正常点分开。

3. 算法应用

异常是指具有与正常实例不同的数据特征的数据模式，因此异常检测可应在各类不同的领域，iForest可以用于：

网络安全中的攻击检测

金融交易欺诈检测

天文学恒星检测

疾病侦测

噪声数据过滤等

4. 算法实现

1）算法假设

异常数据点很少且不同(few and different)：

异常样本占比不能太高

异常样本和正常样本差异较大

2）算法思想

使用孤立树(iTree)的二叉树结构来分割样本，异常样本更容易快速落入叶子结点，也就是异常样本更有可能被切分在离根节点更近的地方。这种检测机制很简单，但有效又高效。

3）算法过程

算法总共分两步：1）训练iForest模型；2）基于训练好的模型和异常得分公式计算每个数据点的异常得分。

孤立森林通过引入二叉树来实现，每个树都应用了一个过程：从训练集中随机选择Ψ个点作为子样本，从中随机选取一个特征，通过在所选特征q的最大值和最小值之间随机选择一个值p来分割数据点，生成分区（左、右分支），然后基于每个分区重复前面随机过程递归地分割数据，直到所有的观察值不可或者树已经生长到了所设定的高度。

上图就是对子样本进行切割训练的过程。图中展示了有135个点组成的高斯分布，左图中一个正态点xi需要12个随机分区才能被隔离，右图中一个异常xo只需要隔离四个分区。

正是因为一棵树的切割过程是完全随机的，因此需要通过集成的方式来使结果收敛。当从头开始重复切到指定的t次后，得到了t棵树，训练过程就结束了。

附.训练过程的伪代码：

其中，代码1展现的是孤立树的创建，代码2为每棵孤立树的生长即训练过程。

接下来就是通过训练好的这 t 棵树来评估检测性能了，即计算异常分数 s。对于每个样本 x，需要计算其在每棵树上的情况，然后通过下面的公式计算s：

其中：

h(x)：为样本在iTree上的路径长度(PathLength)，样本落入到叶子节点经过的边的数量。

E(h(x))：为样本在t棵iTree的路径长度的均值。

c(Ψ)：为用Ψ‍个样本构建一个BST二叉搜索树的平均路径长度。这个是用来对样本x的路径长度h(x)进行标准化处理，而iTree和BST的结构具有等价性，就借鉴BST的做法去估计平均路径长度。

其中H(i)(harmonic number)是可以通过ln(i)+0.5772156649(欧拉常数)估计出来的。

得分较高的异常值代表路径长度较低，而异常观测孤立出来会比正常观测需要更少的步骤，因此可以通过异常分数将异常点检测出来。

之所以要对h(x)进行这样的标准化处理，因为h(x)不仅收到样本本身影响，也与抽样的样本子集有关系。虽然iTree的最大可能高度以ψ的顺序增长，但平均高度以logψ的顺序增长，当需要可视化或比较来自不同子采样大小的模型的路径长度时，一般的归一化处理要么没有界限，要么无法直接比较。因此需要引入一个可比较的标准化的异常分数。

从公式中可以发现，s值域为(0,1)。当PathLength越小，s越接近1，此时样本为异常值的概率越大，而观测点的平均路径长度和树的平均路径长度的关系可能存在以下三种情况:

当E(h(x)）-> 0， s(x,Ψ)= 1

当E(h(x)）-> Ψ-1， s(x,Ψ‍)= 0

当E(h(x)）= c(Ψ)， s(x,Ψ)=1/2

对应的解释为：

如果观测点的异常得分接近 1，路径长度非常小，那么判断为异常点；

如果异常得分远小于 0.5，路径长度非常大，那么判断不是异常点；

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

附.PathLength计算的伪代码

其中 c(size) 是一个adjustment项，因为有一些样本点还没有被孤立出来，树就停止生长了，该项对其路径长度给出修正。

4）关于训练参数问题

height limit：树的深度。之所以限制树深，因为我们只关心路径长度较短的点，它们更可能是异常点，而并不关心那些路径很长的正常点，无需让树不断生长，耗费资源。

subsampling size：ψ‍，每次抽样的样本数。论文建议256即可，一般大样本可以覆盖，大于256，性能上不会有大的提升，反而会增加处理时间和内存大小。而且子抽样可以很好地处理swamping和masking的问题。

左图为原始数据分布情况，右图对应子样本分布，◦表示正常实例，△表示异常。

Number of trees：树的个数。建议100，路径长度通常在t=100之前收敛得很好，如果特征和样本规模比较大，可以适当增加。树过少结果可能不稳定，但过多则白白浪费了系统开销。

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

题图来源：网站Pexels