程序员经验分享-hwhale

孤立森林(Isolation Forest)

2023-05-16

背景

现有的异常检测方法主要是通过对正常样本的描述，给出一个正常样本在特征空间中的区域，对于不在这个区域中的样本，视为异常。这些方法的主要缺点是，异常检测器只会对正常样本的描述做优化，而不会对异常样本的描述做优化，这样就有可能造成大量的误报，或者只检测到少量的异常。

异常的两个特点：异常数据只占很少量、异常数据特征值和正常数据差别很大。

孤立森林，不再是描述正常的样本点，而是要孤立异常点，由周志华教授等人于2008年在第八届IEEE数据挖掘国际会议上提出。

先了解一下该算法的动机。目前学术界对异常(anomaly detection)的定义有很多种，在孤立森林(iForest)中，异常被定义为“容易被孤立的离群点 (more likely to be separated)”，可以将其理解为分布稀疏且离密度高的群体较远的点。 在特征空间里，分布稀疏的区域表示事件发生在该区域的概率很低，因而可以认为落在这些区域里的数据是异常的。孤立森林是一种适用于连续数据(Continuous numerical data)的无监督异常检测方法，即不需要有标记的样本来训练，但特征需要是连续的。对于如何查找哪些点容易被孤立(isolated)，iForest使用了一套非常高效的策略。在孤立森林中，递归地随机分割数据集，直到所有的样本点都是孤立的。在这种随机分割的策略下，异常点通常具有较短的路径。

直观上来讲，那些密度很高的簇是需要被切很多次才能被孤立，但是那些密度很低的点很容易就可以被孤立。这里参考下面的图进行说明。

这里写图片描述

这里写图片描述

在图(a)和图(b)中，可以看到，正常点 xi 需要更多次的分割才能被孤立，而异常点 xo 需要较少的分割次数就能被孤立。这里的分割方式采用的是，随机选择一个特征以及拆分的值(这个值位于该特征的最小值和最大值之间)。图(c)展示了异常点的平均路径长度小于正常点的路径长度。

isolation tree (iTree)

定义：假设 T 是孤立树的一个节点，它要么是没有子节点的叶子节点，要么是只有两个子节点(Tl,Tr)的内部节点。每一步分割，都包含特征 q 和分割值p，将 q<p 的数据分到 Tl ，将 q≥p 的数据分到 Tr 。

给定 n 个样本数据X={x1,⋯,xn}，特征的维度为 d 。为了构建一棵孤立树，需要随机选择一个特征q及其分割值 p ，递归地分割数据集X，直到满足以下任意一个条件：(1)树达到了限制的高度；(2)节点上只有一个样本；(3)节点上的样本所有特征都相同。

异常检测的任务是给出一个反应异常程度的排序，常用的排序方法是根据样本点的路径长度或异常得分来排序，异常点就是排在最前面的那些点。

Path Length

定义： 样本点 x 的路径长度h(x)为从iTree的根节点到叶子节点所经过的边的数量。

Anomaly Score

给定一个包含 n 个样本的数据集，树的平均路径长度为

c(n)=2H(n−1)−2(n−1)n

其中 H(i) 为调和数，该值可以被估计为 ln(i)+0.5772156649 。 c(n) 为给定样本数 n 时，路径长度的平均值，用来标准化样本x的路径长度 h(x) 。

样本 x 的异常得分定义为

s(x,n)=2−E(h(x))c(n)

其中， E(h(x)) 为样本 x 在一批孤立树中的路径长度的期望。下图给出了s和 E(h(x)) 的关系。

这里写图片描述

由上图可以得到一些结论：

  • 当 E(h(x))→c(n) 时， s→0.5 ，即样本 x 的路径平均长度与树的平均路径长度相近时，则不能区分是不是异常。

  • 当E(h(x))→0时， s→1 ，即 x 的异常分数接近1时，被判定为异常。

  • 当E(h(x))→n−1时， s→0 ，被判定为正常。

这里写图片描述

孤立树的特点

孤立森林作为孤立树的总体，将具有较短路径长度的点识别为异常点，不同的树扮演不同异常识别的专家。

已经存在的那些异常检测的方法大部分都期望有更多的数据，但是在孤立森林中，小数据集往往能取得更好的效果。样本数较多会降低孤立森林孤立异常点的能力，因为正常样本会干扰隔离的过程，降低隔离异常的能力。子采样就是在这种情况下被提出的。

swamping和masking是异常检测中比较关键的问题。swamping指的是错误地将正常样本预测为异常。当正常样本很靠近异常样本时，隔离异常时需要的拆分次数会增加，使得从正常样本中区分出异常样本更加困难。masking指的是存在大量异常点隐藏了他们的本来面目。当异常簇比较大，并且比较密集时，同样需要更多的拆分才能将他们隔离出来。上面的这两种情况使得孤立异常点变得更加困难。

造成上面两种情况的原因都与数据量太大有关。孤立树的独有特点使得孤立森林能够通过子采样建立局部模型，减小swamping和masking对模型效果的影响。其中的原因是：子采样可以控制每棵孤立树的数据量；每棵孤立树专门用来识别特定的子样本。

下面两张图说明了上述的现象。

这里写图片描述

这里写图片描述

iForest用于异常检测

基于iForest的异常检测包括两个步骤：训练阶段，基于训练集的子样本来建立孤立树；测试阶段，用孤立树为每一个测试样本计算异常分数。

训练阶段

在训练阶段，iTree的建立是通过对训练集的递归分隔来建立的，直到所有的样本被孤立，或者树达到了指定的高度。树的高度限制 l 与子样本数量ψ的关系为 l=ceiling(log2(ψ)) ，它近似等于树的平均高度。树只生长到平均高度，而不继续生长的原因是，我们只关心路径长度较小的那些点，它们更有可能是异常点，而并不关系路径很长的正常点。详细的训练过程如算法1和算法2所示。

这里写图片描述

这里写图片描述

子样本大小 ψ 和树的数量 t 的经验值：ψ=256， t=100 。

评估阶段

在评估阶段，每一个测试样本的异常分数由期望路径长度 E(h(x)) 得到， E(h(x)) 是将样本通过孤立森林中的每一棵树得到的。具体过程见算法3。

这里写图片描述

Example

这里写图片描述

这里写图片描述

这里写图片描述

参考

[1] Liu, Fei Tony, Kai Ming Ting, and Zhi-Hua Zhou. “Isolation forest.” Data Mining, 2008. ICDM’08. Eighth IEEE International Conference on. IEEE, 2008.

[2] 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.

[3] Preiss, Bruno R. Data structures and algorithms with object-oriented design patterns in Java. John Wiley, 2000.

[4] https://www.jianshu.com/p/5af3c66e0410?utm_campaign=maleskine

[5] http://scikit-learn.org/stable/modules/generated/sklearn.ensemble.IsolationForest.html

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

孤立森林(Isolation Forest) 的相关文章

  • TF踩坑笔记

    遇到领导要求出demo xff0c 尬 xff0c 好久没撸ML了 xff0c 工作两年信息流打杂 xff0c 以前也就叶公好龙毕业前VS编译了一波caffe跑了几个demo xff0c 尬出天际 xff0c 这两天踩坑不少 xff0c 留

  • MDK Trace功能

    RealView MDK可以轻松实现TRACE功能 针对ARM Cortex M3内核的芯片 xff0c 只需要要RealView MDK软件和ULINK2仿真器就可以直接实现TRACE功能 xff0c 不需要额外的TRACE硬件仿真器支持

  • 史上最快速的安装Tensorflow方法

    pip install i https pypi tuna tsinghua edu cn simple tensorflow 这里修改成自己需要安装的框架

  • 软件工程师面试经典问题

    大部分内容来自 高质量C 43 43 C 编程指南 和 嵌入式程序员应知道的0x10个问题 的补充整理 1 如何避免重复包含头文件 xff1f 答 xff1a 使用 ifndef define endif 2 include lt file

  • ubuntu18.04安装Realsense D435i 摄像头的SDK和ROS Wrapper

    1 安装参考链接 2 报错链接 3 没有找到rgbd launch 无法定位软件包

  • 写论文感悟

    无论最终结果怎么样 xff0c 这段过程值得纪念 xff0c 经常上的学术论坛是小木虫 xff0c 主要关注的版面是 xff1a 学术交流区 文献求助区 硕博家园 1 文献阅读和管理经验 xff0c 见 xff1a http muchong

  • ubuntu下python版本如何切换

    添加版本python版本管理 shell里执行 xff1a sudo update alternatives install usr bin python python usr bin python2 100 sudo update alt

  • Python函数的参数传递以及是否会改变外部变量的值

    这个问题是由听课时的例子引出的 xff1a 二分查找的递归实现 xff0c 以下是烂代码 xff1a 除去递归实现 xff0c 代码中参数传递的错误一言难尽 Python参数传递 1 如果没有将外部变量传递到函数中 xff0c 函数内部可以

  • OpenLTE开源代码结构解析（一）

    跟踪了一个在将开源组织 OpenLTE xff08 将4G通信网络LTE开源 xff09 xff0c 现将自己梳理整理的一些文档Post出来 xff0c 请有相同兴趣的朋友指点 xff1a 一 xff0c 系统介绍 OpenLTE是一位Mo

  • OpenLTE开源代码结构解析（二）

    对eNodeB的一些配置以及代码结构进行说明 xff0c 如下 xff1a 一 xff0c eNodeB配置结构 控制进程 xff08 传递eNB配置命令 xff09 eNB按照配置进程的配置命令工作 1 xff0c 在一个Tab窗口运行L

  • java.sql.SQLException: ORA-28000: the account is locked

    java sql SQLException ORA 28000 the account is locked 原创 2017年04月25日 17 25 10 标签 xff1a oracle 密码 958 1 现象 xff1a 项目启动时报了

  • 程序猿就是用来改变世界的

    先来一个自我介绍 xff0c 我是一个大三的老学姐 xff0c 专业是软件工程 说真的 xff0c 高考完当我知道我的录取专业是软件工程 xff0c 我一脸懵 xff0c 我什么时候填了这个专业 但是我现在想告诉你 xff0c 这是一个很神

  • DMA周期挪用(cycle-steal)

    周期挪用是指利用CPU不访问 存储器的那些周期来实现DMA操作 xff0c 此时DMA可以使用总线而不用通知CPU也不会妨碍CPU的工作 周期挪用并不减慢CPU的操作 xff0c 但可能需要复杂的时序电路 xff0c 而且 数据传送过程是不

  • 【软件笔记------Orcad Capture CIS 17.2/pads vx2.7】------ orcad&pads PCB设计简要教程

    目录 一 Orcad原理图库1 库添加1 1 新建库1 2 添加库 2 库编辑2 1 元件添加2 2 多PART元件添加2 3属性编辑 3 注意事项 二 原理图1 快捷键2 快捷图标3 选择过滤器4 插入图片5 栅格6 自动编号7 封装分配

  • 《飞控介绍》

    飞控 xff1a 即为导航飞控系统 xff0c 也叫自驾仪 物体运动的三个轴 xff08 多旋翼 xff09 俯视多旋翼时 xff1a 与中心纵向的轴叫做纵轴 xff08 x轴 xff09 与中心横向的轴叫做横轴 xff08 y轴 xff0

  • docker镜像仓库

    前言 镜像 xff0c 可以理解为将应用程序和运行环境打包成 应用模板 xff0c 是容器的上层抽象 容器是镜像的运行实例 xff0c 启动时传入相应的参数 xff0c 即可运行应用程序 二者的关系类似于代码中的 类和对象 要以容器的方式运

  • 杂谈我的IT梦

    误打误撞进入IT 我个人认为我还有是属于能说会道的 xff0c 比较善于与人沟通 xff0c 表达能力也可以 xff0c 所以当初我准备选的专业是医药营销 xff0c 因为那个时候根据我的分析 xff0c 医药是个很可观的赚钱领域 xff0

  • Ubuntu更新sudo apt update库报错

    sudo apt update报错 evyn 64 ubuntu sudo apt update E 文件 list 第 1 行的记录格式有误 etc apt sources list d ros latest list Suite E 无

  • 孤立森林（Isolation Forest）从原理到实践

    异常检测 离群点是在给定数据集中 xff0c 与其他数据点显著不同的数据点 异常检测是找出数据中离群点 和大多数数据点显著不同的数据点 的过程 离群点 真实世界中的大型数据集的模式可能非常复杂 xff0c 很难通过查看数据就发现其模式 这就

  • 一个C++程序员的学习经历

    正在上网的时候有这个念头的 xff0c 所以急急忙忙找了一些学习编程的高人的感想 xff1a 我开始学VC时就是自己一个人在啃 xff0c 也没什么人指导 xff0c 当时没有条件上网 xff0c 资料特别少 xff0c 在书店里随便买本书

随机推荐

  • Mac mini 2018 win10 外接显卡终极教程

    Mac mini 2018 win10 外接N卡应该算是最简单了 但是有些小问题 xff0c 比如说总是需要插拔雷电3的线材 xff0c 对于强迫症或者偏执来说总是感觉不爽 一种解决方案是用refind 启动方法 xff0c 将refind

  • Layui上传系列之二（多文件分块上传优化实现）

    接下来 xff0c 就要实现layui的uploader分块上传了 xff0c 在官网上没有提到分块上传 xff0c 倒是有一个多文件选择后 xff0c 显示文件列表的例子 目录 现状分析 我的做法 功能优化 上代码了 现状分析 对于我们能

  • tigervnc+noVNC远程使用RViz

    写在前面 遇到了远程桌面访问ubuntu系统并使用RViz的需要 xff0c 试了常用的vnc4server xff0c 在没有外接显示器的情况下 xff0c vnc4server需要虚拟一个显示器出来 xff0c 虚拟显示器可以使用Xvf

  • VINS-Mono融合轮式编码器和GPS（三）：后端优化

    VINS Mono融合轮式编码器和GPS xff08 三 xff09 xff1a 后端优化 开篇介绍理论目标函数IMU约束1 残差2 优化变量3 Jacobian4 协方差 实践配合代码查看 开篇 项目地址VINS GPS Wheel xf

  • ROS-Gazebo (一):关于Gazebo无法加载模型,长时间卡在开始界面的问题解决方法

    在使用ROS Gazebo的过程中首先遇到的问题就是长时间加载不出模型 来 通常的解决方法是 从官方模型库下载号所有的基本模型 然后解压到 gazebo models文件夹里面就可以了 具体的下载地址和详细的操作方式可以 百度或者谷歌 34

  • 用SST89E516RD自制51单片机仿真器

    原文网址 xff1a http www1 eccn com tech06 te074653 asp 用SST89E516RD自制51单片机仿真器 文 xff0f 吴汉清 单片机实验和开发中最重要的一个环节就是程序的调试 xff0c 在业余条

  • Latex （一） 安装和环境变量的设置

    一 安装 Tex有很多不同的版本 xff0c 很多人喜欢用ctex xff0c 但是最推荐是官方版本Texlive 搜了很多资料 xff0c 一般windows的话 xff0c 可以将Tex live 43 Tex studio作为标配 x

  • KITTI 数据集 参数—— tracking devkit中的rotation_y和alpha角

    根据devkit中的readme txt和cs overview pdf的描述以及根据通过对数据集做的小实验总结的 xff0c 如果过有错误的地方欢迎指正 61 61 61 61 61 61 61 61 61 61 61 61 61 61

  • 拯救者Y7000P 安装Ubuntu16.04问题解决

    先列一下问题 xff1a 1 wifi开不来了 xff1b 2 触摸板没法用 3 休眠后打不开 目前1 3 xff0c 解决了 xff0c 但是2依然没法解决 xff0c 不过问题不大 xff0c 大不了用鼠标 首先 xff0c 问题的原因

  • VSCode python调试库代码以及添加相关扩展支持opencv

    调试python 代码的时候可以再launch json 文件中添加 justMycode 34 false 来调试安装的包的代码 由于opencv 底层调用的C xff0c 所以如果要在代码提示中正确提示可能要安装额外插件 xff1a 比

  • vscode python包的引用一些问题

    个人使用vscode碰到的一些python包的引用问题以及尝试解决的一些办法 xff0c 可能只适用我自己的情况 项目目录大概如下 xff1a lib是根目录下的一个文件夹 xff0c 里面每个文件夹都是一个python 包 xff0c 都

  • MATLAB 矩阵的化简rref()函数

    在用MATLAB求解线性方程组的时候 xff0c 可以使用 rref 函数对矩阵进行化简 xff0c 从而很方便直观的得到原方程的解 xff0c 举一个简单的例子 xff1a 解下列线性方程组 则用MATLAB的rref函数解上述方程组的代

  • MATLAB求符号函数的函数值的方法

    在MATLAB中定义函数的方法有许多种 xff0c 比较常用的一种是定义符号变量 x 和 y 举一个简单的例子 xff1a 对函数 y 61 x 2 用上述方法的MATLAB语言如下 xff1a syms x y y 61 x 2 要想画出

  • C++寻找数组最大值和最小值

    寻找数组中的最大最小值 include lt iostream gt using namespace std include lt algorithm gt int main int n cin gt gt n int p 61 new i

  • Excel如何同时查找多个数据

    在使用多个excel表的时候 xff0c 有时需要在一个表中查找另一个表中的某些信息 xff0c 怎样能一步到位 xff0c 将所有要查找的信息一次找出来而不是一个个的Ctrl 43 F xff1f 这是前几天帮辅导员老师统计新生的数据时遇

  • python tkinter 全部组件（widget）及事件类型（event）一览

    对于一个简单的GUI程序设计来说 xff0c 我觉得无非就是三个要素 xff0c widget xff08 部件 xff09 xff0c layout xff08 布局 xff09 xff0c event xff08 事件的响应 xff09

  • DS18B20 1-WIRE ROM搜索算法详解

    转自 xff1a http blog sina com cn s blog 57ad1bd20102uxxw html 1 WIRE 搜索算法详解 xff08 1 xff09 0 前言 美信公司 xff08 http www maximin

  • 关于python tkinter 多线程依然无响应问题

    今天解决了一个GUI程序的多线程问题 因为GUI程序在执行高IO操作的时候容易出现假死和无响应的状态 xff0c 所以需要用到多线程 但我的程序开了线程之后依然是无响应状态 几次尝试 xff0c 终于找到问题所在 1 首先 xff0c 我的

  • Ubuntu内核的查看、更新、卸载、取消及启用自动更新

    1 查看当前内核版本 xff1a uname r 2 升级内核 xff1a sudo apt get update sudo apt cache search linux image 查看可用内核 在选择合适的内核后 xff0c sudo

  • 孤立森林(Isolation Forest)

    背景 现有的异常检测方法主要是通过对正常样本的描述 xff0c 给出一个正常样本在特征空间中的区域 xff0c 对于不在这个区域中的样本 xff0c 视为异常 这些方法的主要缺点是 xff0c 异常检测器只会对正常样本的描述做优化 xff0

热门标签