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

相关文章

来自专栏闪电gogogo的专栏

SAMP论文学习

SAMP:稀疏度自适应匹配追踪 实际应用中信号通常是可压缩的而不一定为稀疏的,而且稀疏信号的稀疏度我们通常也会不了解的。论文中提到过高或者过低估计了信号的稀疏度...

35012
来自专栏开心的学习之路

知识篇——聚类算法应用

时隔两月开始继续储备机器学习的知识,监督学习已经告一段落,非监督学习从聚类开始。 非监督学习与监督学习最大的区别在于目标变量事先不存在,也就是说 监督学习...

2945
来自专栏杨熹的专栏

Instance Based Learning

Udacity Machine Learning Instance Based Learning ---- Supervised Learning 给你一...

2674
来自专栏AI研习社

使用 Spark, LSH 和 TensorFlow 检测图片相似性

作为一个视觉数据处理平台,拥有从海量图片中学习并理解其内容的能力是非常重要的。为了检测几近重复的相似图片,我们使用了一套基于 Spark 和 TensorFlo...

502
来自专栏生信技能树

用R语言做逻辑回归

用R语言做逻辑回归 jmzeng(jmzeng1314@163.com) 回归的本质是建立一个模型用来预测,而逻辑回归的独特性在于,预测的结果是只能有两种,tr...

36610
来自专栏机器学习算法原理与实践

word2vec原理(二) 基于Hierarchical Softmax的模型

    word2vec原理(二) 基于Hierarchical Softmax的模型

682
来自专栏黄成甲

数据分析之对应分析

还有一种探索性分析方法叫做对应分析。对应分析能够把一个交叉表结果通过图形的方式展现出来,用以表达不同变量之间以及不同类别之间的关系。对应分析实际也是“降维”方法...

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

李飞飞团队最新论文:如何对图像中的实体精准“配对”?

编译 | 费棋 【导语】近日,李飞飞的斯坦福大学视觉实验室发布了一篇即将在 CVPR 2018上要介绍的论文 Referring Relationships(指...

3358
来自专栏机器学习算法原理与实践

强化学习(三)用动态规划(DP)求解

    在强化学习(二)马尔科夫决策过程(MDP)中,我们讨论了用马尔科夫假设来简化强化学习模型的复杂度,这一篇我们在马尔科夫假设和贝尔曼方程的基础上讨论使用动...

633
来自专栏机器学习之旅

理论:Logistic使用前提

工程效果经验,坏样本个数至少要是你的特征变量个数的10倍以上;总样本个数要是你的特征变量个数的20-30倍以上。比如假设你会采用10变量,理论上,你例子中的高血...

382

扫码关注云+社区