更快更准的异常检测?交给分布式的 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

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

卢欣的专栏

1 篇文章1 人订阅

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

Spark踩坑——java.lang.AbstractMethodError

百度了一下说是版本不一致导致的。于是重新检查各个jar包,发现spark-sql-kafka的版本是2.2,而spark的版本是2.3,修改spark-sql-...

1260
来自专栏拭心的安卓进阶之路

Java 集合深入理解(12):古老的 Vector

今天刮台风,躲屋里看看 Vector ! 都说 Vector 是线程安全的 ArrayList,今天来根据源码看看是不是这么相...

2537
来自专栏Phoenix的Android之旅

Java 集合 Vector

List有三种实现,ArrayList, LinkedList, Vector, 它们的区别在于, ArrayList是非线程安全的, Vector则是线程安全...

692
来自专栏xingoo, 一个梦想做发明家的程序员

AOE关键路径

这个算法来求关键路径,其实就是利用拓扑排序,首先求出,每个节点最晚开始时间,再倒退求每个最早开始的时间。 从而算出活动最早开始的时间和最晚开始的时间,如果这两个...

2637
来自专栏学海无涯

Android开发之奇怪的Fragment

说起Android中的Fragment,在使用的时候稍加注意,就会发现存在以下两种: v4包中的兼容Fragment,android.support.v4.ap...

3215
来自专栏赵俊的Java专栏

从源码上分析 ArrayList

1211
来自专栏alexqdjay

HashMap 多线程下死循环分析及JDK8修复

1.1K4
来自专栏desperate633

LeetCode Invert Binary Tree题目分析

Invert a binary tree. 4 / \ 2 7 / \ / \1 3 6 9 to4 / \ 7 2 / \ / \9 6 3 1 Tri...

981
来自专栏开发与安全

算法:AOV网(Activity on Vextex Network)与拓扑排序

在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们称之为AOV网(Activity on Vextex ...

3977
来自专栏MelonTeam专栏

ArrayList源码完全分析

导语: 这里分析的ArrayList是使用的JDK1.8里面的类,AndroidSDK里面的ArrayList基本和这个一样。 分析的方式是逐个API进行解析 ...

4699

扫码关注云+社区