Isolation Forest算法原理详解

作者:章华燕 编辑:栾志勇

前言

随着机器学习近年来的流行,尤其是深度学习的火热。机器学习算法在很多领域的应用越来越普遍。最近,作者在一家广告公司做广告点击反作弊算法研究工作。想到了异常检测算法,并且上网调研发现有一个算法非常火爆,那就是本文要介绍的算法 Isolation Forest,简称 iForest 。

南大周志华老师的团队在2010年提出一个异常检测算法Isolation Forest,在工业界很实用,算法效果好,时间效率高,能有效处理高维数据和海量数据,这里对这个算法进行简要总结。

iTree的构造

提到森林,自然少不了树,毕竟森林都是由树构成的,那么我们在看Isolation Forest(简称iForest)前,我们先来看看Isolation-Tree(简称iTree)是怎么构成的,iTree是一种随机二叉树,每个节点要么有两个女儿,要么就是叶子节点,一个孩子都没有。给定一堆数据集D,这里D的所有属性都是连续型的变量,iTree的构成过程如下:

  1. 随机选择一个属性Attr;
  2. 随机选择该属性的一个值Value;
  3. 根据Attr对每条记录进行分类,把Attr小于Value的记录放在左女儿,把大于等于Value的记录放在右孩子;
  4. 然后递归的构造左女儿和右女儿,直到满足以下条件:
    • 传入的数据集只有一条记录或者多条一样的记录;
    • 树的高度达到了限定高度;

iTree构建好了后,就可以对数据进行预测啦,预测的过程就是把测试记录在iTree上走一下,看测试记录落在哪个叶子节点。iTree能有效检测异常的假设是:异常点一般都是非常稀有的,在iTree中会很快被划分到叶子节点,因此可以用叶子节点到根节点的路径h(x)长度来判断一条记录x是否是异常点;对于一个包含n条记录的数据集,其构造的树的高度最小值为log(n),最大值为n-1,论文提到说用log(n)和n-1归一化不能保证有界和不方便比较,用一个稍微复杂一点的归一化公式:

s(x,n)就是记录x在由n个样本的训练数据构成的iTree的异常指数,s(x,n)取值范围为[0,1]异常情况的判断分以下几种情况:

  1. 越接近1表示是异常点的可能性高;
  2. 越接近0表示是正常点的可能性比较高;
  3. 如果大部分的训练样本的s(x,n)都接近于0.5,整个数据没有明显的异常。

由于是随机选属性,随机选属性值,一棵树这么随便搞肯定是不靠谱,但是把多棵树结合起来就变强大了;

iForest的构造

iTree搞明白了,我们现在来看看iForest是怎么构造的,给定一个包含n条记录的数据集D,如何构造一个iForest。iForest和Random Forest的方法有些类似,都是随机采样一部分数据集去构造每一棵树,保证不同树之间的差异性,不过iForest与RF不同,采样的数据量Psi不需要等于n,可以远远小于n,论文中提到采样大小超过256效果就提升不大了,并且越大还会造成计算时间的上的浪费,为什么不像其他算法一样,数据越多效果越好呢,可以看看下面这两个个图:

左边是原始数据,右边是采样了数据,蓝色是正常样本,红色是异常样本。可以看到,在采样之前,正常样本和异常样本出现重叠,因此很难分开,但我们采样之和,异常样本和正常样本可以明显的分开。

除了限制采样大小Ψ以外,我们还要给每棵iTree设置最大高度为l=ceilng(log2Ψ),这是因为异常数据记录都比较少,其路径长度也比较低,而我们也只需要把正常记录和异常记录区分开来,因此只需要关心低于平均高度的部分就好,这样算法效率更高,不过这样调整了后,后面可以看到计算h(x)需要一点点改进,先看iForest的伪代码:

IForest构造好后,对测试进行预测时,需要进行综合每棵树的结果,于是

E(h(x))表示记录x在每棵树的高度均值,另外h(x)计算需要改进,在生成叶节点时,算法记录了叶节点包含的记录数量,这时候要用这个数量Size估计一下平均高度,h(x)的计算方法如下:

对高维数据的处理

在处理高维数据时,可以对算法进行改进,采样之后并不是把所有的属性都用上,而是用峰度系数Kurtosis挑选一些有价值的属性,再进行iTree的构造,这跟随机森林就更像了,随机选记录,再随机选属性。

只使用正常样本

这个算法本质上是一个无监督学习,不需要数据的类标,有时候异常数据太少了,少到我们只舍得拿这几个异常样本进行测试,不能进行训练,论文提到只用正常样本构建IForest也是可行的,效果有降低,但也还不错,并可以通过适当调整采样大小来提高效果。

总结

  1. iForest具有线性时间复杂度。因为是ensemble的方法,所以可以用在含有海量数据的数据集上面。通常树的数量越多,算法越稳定。由于每棵树都是互相独立生成的,因此可以部署在大规模分布式系统上来加速运算。
  2. iForest不适用于特别高维的数据。由于每次切数据空间都是随机选取一个维度,建完树后仍然有大量的维度信息没有被使用,导致算法可靠性降低。高维空间还可能存在大量噪音维度或无关维度(irrelevant attributes),影响树的构建。对这类数据,建议使用子空间异常检测(Subspace Anomaly Detection)技术。此外,切割平面默认是axis-parallel的,也可以随机生成各种角度的切割平面,详见“On Detecting Clustered Anomalies Using SCiForest”。
  3. iForest仅对Global Anomaly 敏感,即全局稀疏点敏感,不擅长处理局部的相对稀疏点 (Local Anomaly)。目前已有改进方法发表于PAKDD,详见“Improving iForest with Relative Mass”。
  4. iForest推动了重心估计(Mass Estimation)理论发展,目前在分类聚类和异常检测中都取得显著效果,发表于各大顶级数据挖掘会议和期刊(如SIGKDD,ICDM,ECML)。

注意

目前燕哥还没有发现有Java开源库实现了该算法。目前只有Python机器学习库scikit-learn的0.18版本对此算法进行了实现。而我的项目绝大多数都是Java实现的,因此我需要自己实现该算法。算法源码已实现并开源到我的GitHub上,读者可以下载源码并用IDEA集成开发环境直接打开项目,并运行测试程序以查看算法的检测效果:https://github.com/JeemyJohn/AnomalyDetection

参考文献

  • http://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/icdm08b.pdf
  • https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/ensemble/iforest.py
  • http://scikit-learn.org/dev/modules/generated/sklearn.ensemble.IsolationForest.html

理解了Isolation Forest算法吗?

推荐阅读

  1. 普里姆(Prim)算法
  2. 红黑树算法
  3. Tarjan算法

原文发布于微信公众号 - 机器学习算法全栈工程师(Jeemy110)

原文发表时间:2017-08-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏闪电gogogo的专栏

压缩感知重构算法之压缩采样匹配追踪(CoSaMP)

压缩采样匹配追踪(CompressiveSampling MP)是D. Needell继ROMP之后提出的又一个具有较大影响力的重构算法。CoSaMP也是对OM...

24410
来自专栏hadoop学习笔记

处理数据缺失的结构化解决办法

数据缺失是数据科学家在处理数据时经常遇到的问题,本文作者基于不同的情境提供了相应的数据插补解决办法。没有完美的数据插补法,但总有一款更适合当下情况。

70
来自专栏机器之心

教程 | 从零开始PyTorch项目:YOLO v3目标检测实现(下)

选自Medium 作者:Ayoosh Kathuria 机器之心编译 参与:Panda 前几日,机器之心编译介绍了《从零开始 PyTorch 项目:YOLO v...

1.4K6
来自专栏计算机视觉与深度学习基础

计算机视觉与图像处理学习笔记(一)

写在前面:因学习需要,本人根据章毓晋的《计算机视觉教程》和冈萨雷斯的《数字图像处理》两本书进行学习,中间会穿插相关实践,会有对opencv的学习,以此笔记记录学...

2106
来自专栏SimpleAI

【DL笔记5】一文上手TensorFlow,并搭建神经网络实现手写数字识别

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

726
来自专栏机器之心

教程 | 如何用PyTorch实现递归神经网络?

选自Nvidia.devblogs 作者:James Bradbury 参与:Jane W、吴攀 从 Siri 到谷歌翻译,深度神经网络已经在机器理解自然语言方...

27612
来自专栏AI科技评论

大会 | CVPR 2018论文解读:真实监控场景中的异常事件检测

AI 科技评论按:本文为上海交通大学林天威为 AI 科技评论撰写的独家稿件,未经许可不得转载。 安防作为近年最热门的计算机视觉研究落地方向,与视频分析研究有着很...

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

R语言与机器学习(分类算法)K-近邻算法

最近在学习数据挖掘,对数据挖掘中的算法比较感兴趣,打算整理分享一下学习情况,顺便利用R来实现一下数据挖掘算法。 数据挖掘里我打算整理的内容有...

35811
来自专栏小小挖掘机

windows下使用word2vec训练维基百科中文语料全攻略!(三)

训练一个聊天机器人的很重要的一步是词向量训练,无论是生成式聊天机器人还是检索式聊天机器人,都需要将文字转化为词向量,时下最火的词向量训练模型是word2vec,...

3275
来自专栏AI研习社

TensorFlow 中 RNN 实现的正确打开方式

上周写的文章《完全图解 RNN、RNN 变体、Seq2Seq、Attention 机制》介绍了一下 RNN 的几种结构,今天就来聊一聊如何在 TensorFlo...

3898

扫码关注云+社区