更快更准的异常检测？交给分布式的 Isolation Forest 吧

导语

在异常检测的众多算法中，Isolation Forest算法有着非常重要的地位。这种从异常点的定义出发构建的检测模型往往在工业界更实用，除了带来令人惊喜的检测效果外，Isolation Forest算法也非常高效。目前公司的许多团队已经尝试了该算法在运维、安全等方面的应用，并且与其他异常检验算法相比，获得了更可靠的实验效果。作为一个广受欢迎的算法，Tesla平台发布了基于Spark实现的Isolation Forest分布式算法，以达到更快速的对海量数据进行异常检测的目的。

1. Isolation Forest算法介绍

Isolation Forest算法自2010年诞生至今受到了工业界的广泛认可。不同于其他基于距离与密度的异常检测算法，该算法从异常点的定义出发构建检测模型。实验发现，该算法的鲁棒性强，检测效果好，且时间复杂度低，特别在处理高维数据和海量数据方面具有独特优势。接下来本文详细介绍Isolation Forest算法以及其分布式实现。

1.1 算法原理

Isolation Forest（下文简称IForest）算法单纯的从异常点的概念出发来识别异常点，这与其他基于距离与密度的方法完全不同。那么IForest算法是如何定义异常值的呢?

• IForest中异常值的定义
• 在样本中占少数的那一类
• 与正常值的属性相比有很大不同

总体而言，iForest算法中的异常值就是那些“少而特殊”的样本。有了这个概念后，IForest采用了集成的方式来识别异常值。具体的做法是首先使用训练样本子集构建多棵isolation tree（下文简称ITree），然后多棵isolation tree构成一个IForest模型。在评估阶段，通过计算每个样本在IForest模型中的路径长度，就可以得到每个样本对应的异常得分（anomaly score）。下面我们详细说明。

1.1.1 训练阶段

ITree是一种随机二叉树，每个节点要么有两个孩子，要么就是叶子节点。每个节点包含一个属性q和一个划分值p。ITree的构建过程如下：

1. 从原始训练集X中无放回的抽取样本子集
2. 划分样本子集，每次划分都从样本中随机选择一个属性q，再从该属性中随机选择一个划分的值p，该p值介于属性q的最大与最小值之间。
3. 根据2中的属性q与值p，划分当前样本子集，小于值p的样本作为当前节点的左孩子，大于p值的样本作为当前节点的右孩子。
4. 重复上述2、3步骤，递归的构建每个节点的左、右孩子节点，直到满足终止条件为止。通常终止条件为所有节点均只包含一个样本或者多条一样的样本，或者是树的深度达到了限定的高度。

论文1中给出了ITree的详细构建过程：

当完成了多棵ITree的构建后，这些ITree就构成了IForest。有两个参数控制着IForest模型的复杂度。一个是每棵树的样本子集大小ψ\psiψ，它控制着训练数据的大小，论文中的实验发现，当该值增加到一定程度后，IForest的辨识能力会变得可靠，但没有必要继续增加下去，因为这并不会带来准确率的提升，反而会影响计算时间和内存容量，实现发现ψ\psiψ取256对于很多数据集已经足够；另外一个是ITree的个数t，它控制着模型的集成度，实验发现t取值100已经足够。

1.1.2 评估阶段

训练阶段构建了IForest模型，接下来就需要用测试集对模型进行评估了。这里的评估主要就是计算anomaly score，用S表示，其表达式如下：

其中h(x)表示样本x在某棵树中的路径长度，即从ITree的根节点出发到叶子节点截止所经过的边的个数e。E(h(x))则表示某个样本x在所有树中的平均路径长度。值得注意的是，如果样本x最终所落的叶子节点限制了树的高度，那么h(x)除了所经过的边的个数e之外，还需要加上一个调整值c(size)。c(size)的定义同下文，size代表那些本可以用来继续构建树（却因为定义了树的高度而被限制）从而增加树的高度的节点个数。

而

用于对h(x)进行标准化。的定义如下：

其中表示欧拉常数

，通常取0.5772156649。

有了上述的评估公式，就可以得到测试集每个样本的异常值得分了，根据公式我们可以看出这个异常值得分在0到1之间。论文中给出了判断异常值的方法：

（1）如果某个样本的异常得分非常接近1，则该样本就可以被定义为异常点

（2）如果某个样本的异常得分远小于0.5，则其可以被非常安全的视作正常点

（3）如果所有样本的异常得分都接近0.5，则可以认为整个样本集没有明显的异常点

1.2 IForest算法总结

从上面关于IForest算法的介绍中我们可以看出，它是一种无监督的算法。不同于以往的基于距离或者密度的异常检测算法，IForest算法从异常点的概念出发，充分利用了数据集中异常点“少而特殊”的特点，通过构建随机二叉树从而识别那些距离根节点更近的异常样本。

相比其他异常算法，IForest算法的时间复杂度是线性的，同时占用的内存空间很少。通常使用较低的采样和较少的树就可以获得一个性能优异的模型，而无需考虑原始数据集的大小。

因此可以说IForest算法是一种准确率较高且计算性能高效的算法。由于IForest从异常点的定义出发构建的模型，因此使用中以下情况需要你注意：

（1）如果训练样本中异常样本的比例较高，违背了IForest的基本假设，最终的检测结果将会受影响；

（2）异常检测跟具体的应用场景紧密相关，算法检测出的“异常”不一定是我们实际想要的。所以在构建模型时，需要对特征进行筛选，过滤掉那些与检测目标不太相关的特征，以避免识别出的“异常”与你的“异常”定义有偏差。

2. IForest算法的分布式实现

IForest算法非常适合分布式计算，在训练阶段可以并行的构建多棵ITree，同时在评估阶段，所有样本可以并行的通过IForest模型计算其异常得分。相比与单机版的IForest算法，分布式的IForest算法的计算效率将更高，耗时也更少。下面是IForest算法的分布式实现原理图：

从上面的原理图可以看到，整个分布式IForest模型的建立过程非常清晰，首先训练阶段从原始样本集X中无放回的构建t棵ITree，为了提高效率以及方便实现，最好采用一开始无放回的采样足够多样本供t棵树构建模型，然后将这些样本按照相同的大小随机分配到各棵树中。此时，t棵树就可以根据1.1.1中的过程并行建立了。

由于各棵树的样本大小相同，同时构建都采用了随机方式，再加上算法对每棵树的深度都预先进行了设置，因此，各棵树的构建几乎能同时终止。此时，将所有ITree都collect到driver端形成了IForest模型。

评估阶段首先将预测样本分布式的存储，然后将IForest模型发送到各个executor端进行评估。详细的评估过程参考1.1.2中的内容。

3. Tesla上IForest算法的使用

IForest模块的算法参数介绍：

• 模型输入路径：如果之前使用该模块训练了IForest模型，此时就可以填写该模型路径直接对测试数据进行检测。没有IForest模型则不填
• 模型输出路径：当首次使用该模型训练IForest模型后，可将IForest模型保存至该路径下，方便下次直接使用。在已有IForest模型的情况下无需填写此项。
• 每棵树的样本数：训练阶段的$$\psi$$参数，每个ITree的构建都采用相同的样本个数，256是较为合适的值，过大对检测能力提升效果不大，且会影响运行时长，甚至导致内存溢出。
• 树的个数：训练阶段的t参数，控制着模型的集成度，100是较为合适的值，过大同样不能带来检测能力的提升，反而会影响计算性能。
• 树的最大深度：控制着每棵树的最大深度，在算法中，该参数用来控制异常点的覆盖度和隐藏度。过深或过浅的树都无法有效识别异常点。注意本模块中，树的根节点深度为1。

参考文献

1. Fei Tony Liu,Kai Ming Ting,Zhi-Hua Zhou. Isolation-Based Anomaly Detection.ACM Transactions on Knowledge Discovery from Data.Volume 6 Issue 1, March 2012