专栏首页郭耀华‘s Blog【异常检测】孤立森林(Isolation Forest)算法简介

【异常检测】孤立森林(Isolation Forest)算法简介

简介  

  工作的过程中经常会遇到这样一个问题,在构建模型训练数据时,我们很难保证训练数据的纯净度,数据中往往会参杂很多被错误标记的脏数据,而数据的质量决定了最终模型性能的好坏。如果进行人工二次标记,成本会很高,我们希望能使用一种无监督算法帮我们做这件事,异常检测算法可以在一定程度上解决这个问题。

  异常检测分为离群点检测(outlier detection)以及奇异值检测(novelty detection)两种.

  • 离群点检测:适用于训练数据中包含异常值的情况,例如上述所提及的情况。离群点检测模型会尝试拟合训练数据最集中的区域,而忽略异常数据。
  • 奇异值检测:适用于训练数据不受异常值的污染,目标是去检测新样本是否是异常值。 在这种情况下,异常值也被称为奇异点。

  孤立森林 (Isolation Forest, iForest)是一个基于Ensemble的快速离群点检测方法,具有线性时间复杂度和高精准度,是符合大数据处理要求的State-of-the-art算法。由南京大学周志华教授等人于2008年首次提出,之后又于2012年提出了改进版本。适用于连续数据(Continuous numerical data)的异常检测,与其他异常检测算法通过距离、密度等量化指标来刻画样本间的疏离程度不同,孤立森林算法通过对样本点的孤立来检测异常值。具体来说,该算法利用一种名为孤立树(iTree)的二叉搜索树结构来孤立样本。由于异常值的数量较少且与大部分样本的疏离性,因此,异常值会被更早的孤立出来,也即异常值会距离iTree的根节点更近,而正常值则会距离根节点有更远的距离。此外,相较于LOF,K-means等传统算法,孤立森林算法对高纬数据有较好的鲁棒性。其可以用于网络安全中的攻击检测,金融交易欺诈检测,疾病侦测,和噪声数据过滤等。

  举个例子:

  对于如何查找哪些点是否容易被孤立,iForest使用了一套非常高效的策略。假设我们用一个随机超平面来切割数据空间, 切一次可以生成两个子空间(想象拿刀切蛋糕一分为二)。之后我们再继续用一个随机超平面来切割每个子空间,循环下去,直到每子空间里面只有一个数据点为止。直观上来讲,我们可以发现那些密度很高的簇是可以被切很多次才会停止切割,但是那些密度很低的点很容易很早的就停到一个子空间了。上图里面黑色的点就很容易被切几次就停到一个子空间,而白色点聚集的地方可以切很多次才停止。

算法

  怎么来切这个数据空间是iForest的设计核心思想,本文仅介绍最基本的方法。由于切割是随机的,所以需要用Ensemble的方法来得到一个收敛值(蒙特卡洛方法),即反复从头开始切,然后平均每次切的结果。iForest 由 个 iTree 组成,每个 iTree 是一个二叉树结构。该算法大致可以分为两个阶段,第一个阶段我们需要训练出 颗孤立树,组成孤立森林。随后我们将每个样本点带入森林中的每棵孤立树,计算平均高度,之后再计算每个样本点的异常值分数。

  第一阶段,步骤如下:

  (1)从训练数据中随机选择Ψ个点样本点作为样本子集,放入树的根节点。

  (2)随机指定一个维度(特征),在当前节点数据中随机产生一个切割点 p(切割点产生于当前节点数据中指定维度的最大值和最小值之间)。

  (3)以此切割点生成了一个超平面,然后将当前节点数据空间划分为2个子空间:把指定维度里小于 的数据放在当前节点的左子节点,把大于等于 的数据放在当前节点的右子节点。

  (4)在子节点中递归步骤(2)和(3),不断构造新的孩子节点,直到子节点中只有一个数据(无法再继续切割)或子节点已到达限定高度。

  (5)循环(1)至(4),直至生成 个孤立树iTree

  第二阶段:

  获得t个iTree之后,iForest 训练就结束,然后我们可以用生成的iForest来评估测试数据了。对于每一个数据点 xi,令其遍历每一颗孤立树(iTree),计算点 xi 在森林中的平均高度好h(xi),对所有点的平均高度做归一化处理。异常值分数的计算公式如下所示:

  其中

H(i) 是调和数,可以通过 ln(i) + 0.5772156649(欧拉常数)来估算。分值越小表示数据越为异常。

示例:

>>> from sklearn.ensemble import IsolationForest
>>> X = [[-1.1], [0.3], [0.5], [100]]
>>> clf = IsolationForest(random_state=0).fit(X)
>>> clf.predict([[0.1], [0], [90]])
array([ 1,  1, -1])

补充:

  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)。

参考文章:

孤立森林(Isolation Forest)算法简介

iForest (Isolation Forest)孤立森林 异常检测 入门篇

Liu, Fei Tony, Kai Ming Ting, and Zhi-Hua Zhou. "Isolation forest."Data Mining, 2008. ICDM'08. Eighth IEEE International Conference on. IEEE, 2008.

Liu, Fei Tony, Kai Ming Ting, and Zhi-Hua Zhou. "Isolation-based anomaly detection."ACM Transactions on Knowledge Discovery from Data (TKDD)6.1 (2012): 3.

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!
本文分享自作者个人站点/博客:https://www.cnblogs.com/guoyaohua/复制
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 使用孤立森林进行无监督的离群检测

    孤立森林是一种简单但非常有效的算法,能够非常快速地发现数据集中的异常值。理解这个算法对于处理表格数据的数据科学家来说是必须的,所以在本文中将简要介绍算法背后的理...

    deephub
  • 使用孤立森林进行异常检测

    异常检测是对罕见的观测数据进行识别,这些观测数据具有与其他数据点截然不同的极值。这类的数据被称为异常值,需要被试别和区分。造成这些异常现象的原因有很多:数据的可...

    deephub
  • 【python数据挖掘实战】之一:异常检测

    等,有着重要的作用。由于在以上场景中,异常的数据量都是很少的一部分,因此诸如:SVM、逻辑回归等分类算法,都不适用,因为:

    统计学家
  • 异常点检测算法

    在进行机器学习建模之前,首先要对数据中存在的异常点样本进行过滤,异常点,也叫做离群点,对数据的归一化,以及后续建模的准确性都会造成影响。因此,必须先去除异常点,...

    生信修炼手册
  • 异常检测怎么做,试试孤立随机森林算法(附代码)

    从银行欺诈到预防性的机器维护,异常检测是机器学习中非常有效且普遍的应用。在该任务中,孤立森林算法是简单而有效的选择。

    机器之心
  • 四种检测异常值的常用技术简述

    在训练机器学习算法或应用统计技术时,错误值或异常值可能是一个严重的问题,它们通常会造成测量误差或异常系统条件的结果,因此不具有描述底层系统的特征。实际上,最...

    用户3578099
  • 理论结合实践,一文搞定异常检测技术

    数据集汇总的异常数据通常被认为是异常点、离群点或孤立点,特点是这些数据的特征与大多数数据不一致,呈现出"异常"的特点,检测这些数据的方法称为异常检测。

    数据STUDIO
  • 14种数据异常值检验的方法!

    来源:宅码 作者:AI 本文收集整理了公开网络上一些常见的异常检测方法(附资料来源和代码)。不足之处,还望批评指正。 一、基于分布的方法 1. 3sigma ...

    张俊红
  • 机器学习中有哪些形式简单却很巧妙的 idea?

    作者:桔了个仔 https://www.zhihu.com/question/347847220/answer/836019446

    Datawhale
  • 文末福利|特征工程与数据预处理的四个高级技巧

    用于创建新特征,检测异常值,处理不平衡数据和估算缺失值的技术可以说,开发机器学习模型的两个最重要的步骤是特征工程和预处理。特征工程包括特征的创建,而预处理涉及清...

    磐创AI
  • 学会五种常用异常值检测方法,亡羊补牢不如积谷防饥

    在统计学中,是并不属于特定族群的数据点,是与其它值相距甚远的异常观测。离群点是一种与其它结构良好的数据不同的观测值。

    统计学家
  • 深入机器学习系列之异常检测

    今天要给大家介绍的是异常检测(Anomaly Detection), 它是机器学习的一个重要分支,实际应用领域广泛,更与我们的生活息息相关。那么什么是异常检测?...

    数据猿
  • 【机器学习】孤立森林

    本文介绍了一种基于树集成的异常检测方法,其核心思想是“异常点是容易被孤立的离群点”。首先介绍了孤立森林算法的设计思路。然后介绍了孤立森林算法的特点和适用场景。最...

    yuquanle
  • 学会五种常用异常值检测方法,亡羊补牢不如积谷防饥

    在统计学中,离群点是并不属于特定族群的数据点,是与其它值相距甚远的异常观测。离群点是一种与其它结构良好的数据不同的观测值。

    机器之心
  • 运用孤立森林异常检测算法,过滤异常数据

    在上述场景中,异常的数据与整个测试数据样本相比是很少的一部分,常见的分类算法例如:SVM、逻辑回归等都不合适。而孤立森林算法恰好非常适合上述场景,首先测试数据具...

    机器学习AI算法工程
  • 无监督︱异常、离群点检测 一分类——OneClassSVM

    OneClassSVM两个功能:异常值检测、解决极度不平衡数据 因为之前一直在做非平衡样本分类的问题,其中如果有一类比例严重失调,就可以直接用这个方式来做:On...

    悟乙己
  • 异常点检测算法小结

    异常点检测,有时也叫离群点检测,英文一般叫做Novelty Detection或者Outlier Detection,是比较常见的一类非监督学习算法,这里就对异...

    zenRRan
  • Isolation Forest算法原理详解

    作者:章华燕 编辑:栾志勇 前言 随着机器学习近年来的流行,尤其是深度学习的火热。机器学习算法在很多领域的应用越来越普遍。最近,作者在一家广告公司做广告...

    机器学习算法工程师
  • 第 439 期 Python 周刊

    链接: https://www.youtube.com/watch?v=tPYj3fFJGjk

    爱写bug

扫码关注云+社区

领取腾讯云代金券