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

相关文章

来自专栏程序猿

数据挖掘算法之决策树算法

数据挖掘算法之 决策树算法 机器学习中,决策树是一个预测模型;它代表的是对象属性值与对象值之间的一种映射关系。树中每个节点表示某个对象,每个分叉路径则...

2855
来自专栏UAI人工智能

基于RLLAB的强化学习 REINFORCE 算法解析

1332
来自专栏吉浦迅科技

【阿星的学习笔记(2)】使用Tensorflow实作卷积神经网络(CNN)

Lady之前已经向各位介绍一个朋友阿星(Ashing)以及他的机器学习读书笔记! 阿星也是我们手撕深度学习算法微信群的热心群友!接下来,Lady我也会陆续分享这...

33110
来自专栏专知

【最新TensorFlow1.4.0教程02】利用Eager Execution 自定义操作和梯度 (可在 GPU 运行)

点击上方“专知”关注获取更多AI知识! 【导读】主题链路知识是我们专知的核心功能之一,为用户提供AI领域系统性的知识学习服务,一站式学习人工智能的知识,包含人工...

4706
来自专栏智能算法

深度学习三人行(第3期)---- TensorFlow从DNN入手

1532
来自专栏IT派

一文带你入门Tensorflow

导语:此文编译自FCC(FreeCodeCamp),作者为Déborah Mesquita,该作者利用神经网络和TensorFlow进行了机器文本分类,并提出了...

4169
来自专栏ATYUN订阅号

解决多标签分类问题(包括案例研究)

由于某些原因,回归和分类问题总会引起机器学习领域的大部分关注。多标签分类在数据科学中是一个比较令人头疼的问题。在这篇文章中,我将给你一个直观的解释,说明什么是多...

5366
来自专栏深度学习自然语言处理

神经网络基础模型--Logistic Regression的理论和实践

1 概述 Logistic Regression 即 逻辑回归,属于监督学习,输入x(特征数据),输出为0或1(显然是二分类)。为什么要用逻辑回归讲神经...

34715
来自专栏机器之心

教程 | 斯坦福CS231n 2017最新课程:李飞飞详解深度学习的框架实现与对比

选自Stanford 作者:李飞飞等 机器之心编译 参与:Smith、蒋思源 斯坦福大学的课程 CS231n (Convolutional Neural Ne...

2918
来自专栏专知

【论文笔记】基于实体、属性和关系的知识表示学习

1543

扫码关注云+社区