更快更准的异常检测?交给分布式的 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 条评论
登录 后参与评论

相关文章

来自专栏AI科技大本营的专栏

AI从入门到放弃2:CNN的导火索,用MLP做图像分类识别?

阅读本文的基础:我会认为你对BP神经网络有充分的了解,熟读过我上一篇文章,本文会大量引用上一篇文章的知识以及代码。

1362
来自专栏SimpleAI

【DL笔记6】从此明白了卷积神经网络(CNN)

从【DL笔记1】到【DL笔记N】,是我学习深度学习一路上的点点滴滴的记录,是从Coursera网课、各大博客、论文的学习以及自己的实践中总结而来。从基本的概念、...

1102
来自专栏AI研习社

为什么ResNet和DenseNet可以这么深?一文详解残差块为何有助于解决梯度弥散问题

传统的“提拉米苏”式卷积神经网络模型,都以层叠卷积层的方式提高网络深度,从而提高识别精度。但层叠过多的卷积层会出现一个问题,就是梯度弥散(Vanishing),...

3455
来自专栏AI科技评论

开发 | 为什么ResNet和DenseNet可以这么深?一文详解残差块为何有助于解决梯度弥散问题。

AI科技评论按:本文作者Professor ho,原文载于其知乎主页,雷锋网获其授权发布。 传统的“提拉米苏”式卷积神经网络模型,都以层叠卷积层的方式提高网络深...

4345
来自专栏大数据挖掘DT机器学习

kmeans聚类理论篇K的选择(轮廓系数)

kmeans是最简单的聚类算法之一,但是运用十分广泛。最近在工作中也经常遇到这个算法。kmeans一般在数据分析前期使用,选取适当的k,将数据分类后,然后分类...

5635
来自专栏小鹏的专栏

自己写个 Prisma

Sirajology的视频链接 前一段时间特别火的 Prisma 大家都玩了么,看了这篇文章后,你也可以自己写一个 Prisma 迷你版了。 ? 这个 i...

2345
来自专栏AI科技大本营的专栏

一文搞懂交叉熵在机器学习中的使用,透彻理解交叉熵背后的直觉

交叉熵(cross entropy)是深度学习中常用的一个概念,一般用来求目标与预测值之间的差距。以前做一些分类问题的时候,没有过多的注意,直接调用现成的库,用...

3375
来自专栏张俊红

最懒惰的算法—KNN

总第77篇 本篇介绍机器学习众多算法里面最基础也是最“懒惰”的算法——KNN(k-nearest neighbor)。你知道为什么是最懒的吗? 01|算法简介:...

3075
来自专栏机器人网

【深度学习】详细的神经网络架构图

将这些架构绘制成节点图的一个问题:它并没有真正展示这些架构的工作方式。比如说,变自编码器(VAE)可能看起来和自编码器(AE)一样,但其训练过程却相当不同。训练...

3516
来自专栏AI研习社

使用深度学习来理解道路场景

语义分割是深度学习的方法之一,通过语义分割,我们可以对图片中的每一个像素赋予含义,即将像素划分到一个预先设定的类中。从上边的 GIF 图可以看出,我们在语义切分...

1002

扫码关注云+社区