程序员经验分享-hwhale

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

2023-05-16

异常检测

离群点是在给定数据集中，与其他数据点显著不同的数据点。异常检测是找出数据中离群点(和大多数数据点显著不同的数据点)的过程。

离群点

真实世界中的大型数据集的模式可能非常复杂，很难通过查看数据就发现其模式。这就是为什么异常检测的研究是机器学习中极其重要的应用。

孤立森林原理

孤立森林(Isolation Forest)于2008年由西瓜书作者周志华团队提出，凭借其线性的时间复杂度与优秀的准确率被广泛应用于工业界中结构化数据的异常检测。

孤立森林

孤立森林的基本理论基础有二：

  1. 异常数据占总样本量的比例很小；
  2. 异常点的特征值与正常点的差异很大。
对孤立森林的通俗理解

一句话总结孤立森林的基本原理：异常样本相较普通样本可以通过较少次数的随机特征分割被孤立出来。样本空间有一批数据，其有的地方分布密集，有的地方分布稀疏，如果该批数据大部分样本都分布密集，那么稀疏的那部分是不是就是所谓的离群点？那么孤立森林是如何找出这些离群点的呢？

例如：假设这批样本点有一个特征为年龄，孤立森林随机选择认为年龄>70为异常，年龄<=70为正常。此时相当于在样本空间，画出了一个超平面。接着孤立森林再选了一个特征为收入，认为收入>1w为异常，收入<=1W为正常，此时则又在样本空间画出了一个超平面......根据直觉，是不是分布稀疏位置的点可以通过较少次数的超平面划分被孤立出来，而分布密集位置的点需要更多次数的超平面划分才能被孤立。如下图所示，处于分布密集位置的xi用了11个超平面才被孤立，处于分布稀疏位置的x0用了4个超平面即被孤立。

超平面划分

假设一棵树通过这个方法认为x0是离群点，这一结果是未必准确的，因为随机选特征与阈值存在着诸多偶然性。但是如果引入bagging的思想，我用100棵树进行这样的随机分割，其中90颗的结论都是认为x0是离群点，那么这个结果就比较可信了。

算法细节

单棵树的训练
单棵树训练的伪代码
  1. 从训练数据中随机选择 Ψ 个点作为子样本，放入一棵孤立树的根节点；
  2. 随机指定一个维度，在当前节点数据范围内，随机产生一个切割点 p —— 切割点产生于当前节点数据中指定维度的最大值与最小值之间；
  3. 此切割点的选取生成了一个超平面，将当前节点数据空间切分为2个子空间：把当前所选维度下小于 p 的点放在当前节点的左分支，把大于等于 p 的点放在当前节点的右分支；
  4. 在节点的左分支和右分支节点递归步骤 2、3，不断构造新的叶子节点，直到叶子节点上只有一个数据(无法再继续切割) 或树已经生长到了所设定的高度 。
如何整合多棵树的结果？

孤立森林与随机森林相似，都是通过随机采样数据来对每棵树进行训练，从而保证构建的森林的方差足够大，即每棵树之间越不相似越好。 在构建孤立森林时，需要设定两个参数：树的数量t和每棵树采样样本大小的最大值Ψ 。

孤立森林通过引入异常值函数s(x,n)来衡量记录x 是否为异常点

s(x,n)

其中，E(h(x))为x在多棵树中的路径长度的期望值。

c(n)
H(*)

其中，c(n)为一个包含n个样本的数据集，树的平均路径长度，用来标准化记录x的路径长度。H(*)为调和数，ξ为欧拉常数，约为0.5772156649。

s(x,n)与E(h(x))的关系
s(x,n)与E(h(x))的关系2
isolation forest伪代码
一个树的最大高度

FAQ

qes: 为什么需要对树的高度做限制？
ans: 之所以对树的高度做限制，是因为我们只关心路径长度较短的点，它们更可能是异常点，而并不关心那些路径很长的正常点
qes: 树的棵树如何选择？
ans: 通过下图可以发现，当t>=100后，划分上文提到的xi和x0的平均路径长度都已经收敛了，故因此论文中推荐t设置为100。

平均路径长度与t的关系

qes: 样本采样量Ψ如何取值？
ans:论文中推荐Ψ设置为2^8或256，其能够提供足够的细节给异常检测任务。下图展示了部分采样的作用，蓝色代表正常样本，红色代表异常样本。可以看出，在采样之前，正常样本和异常样本出现了重叠，因此很难分开，但通过采样之后，异常样本和正常样本可以明显的分开。另外采样可以降低计算时间和空间上的浪费。

部分采样的效果

qes: isolation forest的复杂度如何？
ans: 训练一个iforest的时间复杂度为o(tΨlogΨ)。

实践中的参数调节

我们使用sklearn中的孤立森林，进行参数调节讲解，一般任务默认参数即可。import sklearn.ensemble.IsolationForest as iforest

  1. n_estimators : int, optional (default=100) 指定该森林中生成的随机树数量

  2. max_samples : int or float, optional (default=”auto”)
    用来训练随机数的样本数量，即子采样的大小
    如果设置的是一个int常数，那么就会从总样本X拉取max_samples个样本来生成一棵树iTree
    如果设置的是一个float浮点数，那么就会从总样本X拉取max_samples * X.shape[0]个样本,X.shape[0]表示总样本个数
    如果设置的是"auto"，则max_samples=min(256, n_samples)，n_samples即总样本的数量
    　　如果max_samples值比提供的总样本数量还大的话，所有的样本都会用来构造数，意思就是没有采样了，构造的n_estimators棵iTree使用的样本都是一样的，即所有的样本

  3. contamination : float in (0., 0.5), optional (default=0.1)
    取值范围为(0., 0.5),表示异常数据占给定的数据集的比例
    数据集中污染的数量，其实就是训练数据中异常数据的数量，比如数据集异常数据的比例。定义该参数值的作用是在决策函数中定义阈值。如果设置为'auto'，则决策函数的阈值就和论文中定义的一样
    在版本0.20中有变化：默认值从0.1变为0.22版本中的'auto'

  4. max_features : int or float, optional (default=1.0)
    指定从总样本X中抽取来训练每棵树iTree的属性的数量，默认只使用一个属性
    如果设置为int整数，则抽取max_features个属性
    如果是float浮点数，则抽取max_features * X.shape[1]个属性

  5. bootstrap : boolean, optional (default=False)
    如果为True，则各个树可放回地对训练数据进行采样。如果为False，则执行不放回的采样。

  6. n_jobs : int or None, optional (default=None)
    在运行fit()和predict()函数时并行运行的作业数量。除了在joblib.parallel_backend上下文的情况下，None表示为1。设置为-1则表示使用所有可用的处理器

  7. behaviour : str, default=’old’
    决策函数decision_function的行为，可以是'old'和'new'。设置为behaviour='new'将会让decision_function去迎合其他异常检测算法的API，这在未来将会设置为默认值。正如在offset_属性文档中详细解释的那样，decision_function变得依赖于contamination参数，以0作为其检测异常值的自然阈值。
    New in version 0.20：behaviour参数添加到了0.20版本中以实现后向兼容
    behaviour='old'在0.20版本中以经弃用，在0.22版本中将不能使用
    behaviour参数将在0.22版本中弃用，将在0.24版本中移除

  8. random_state : int, RandomState instance or None, optional (default=None)
    如果设置为int常数，则该random_state参数值是用于随机数生成器的种子
    如果设置为RandomState实例，则该random_state就是一个随机数生成器
    如果设置为None，该随机数生成器就是使用在np.random中的RandomState实例

  9. verbose : int, optional (default=0) 训练中打印日志的详细程度，数值越大越详细

  10. warm_start : bool, optional (default=False)
    当设置为True时，重用上一次调用的结果去fit,添加更多的树到上一次的森林1集合中；否则就fit一整个新的森林

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

孤立森林（Isolation Forest）从原理到实践 的相关文章

  • TX 下常用的查询指令

    查看Jetson TX2 L4T版本 head n 1 etc nv tegra release 查看系统版本 cat etc lsb release 查看系统l内核 uname a 查看内存 free m 查看CPU详情 lscpu 查看

  • ubuntu远程桌面控制另一台电脑：teamviewer或VNC.附带远程rviz打不开解决方法

    远程控制方案 xff1a 1 xff1a teamviewer xff1b 2 xff1a VNC 43 vnc viewer xff1b 3 xff1a VNC 43 系统自带桌面共享 1 xff0c 搜索ubunutu安装teamvie

  • 《控制论导论》读书：基本概念

    前言 本系列读书笔记主要来自W R Ashby的 控制论导论 一书 该书最先成于上个世纪60年代 xff0c 如今已绝版且未再版 Ashby本人对控制论在生物医学领域的应用有深入的研究 xff0c 该书也进行了一定阐释 作为一个对复杂系统理

  • 每周五条-002

    2020 4月第4周 职场 假如开发人员 耍大牌 xff0c 十有八九是井底之蛙 xff0c 盲目自大 产品 产品不能一直靠人手动维护它正常运作 xff0c 一定要让客户自己有功能来解决实际问题 有些一时找不到原因的异常问题习惯了软件公司自

  • visual svn修改新url地址方法(linux,windows,centos)

    在工作环境调整时 有的时候SVN服务器的地址需要修改 xff0c 此时我们如何修改本地库的地址 xff0c 而不用重新下载呢 xff1f SVN中有一个简单的解决办法 xff1a 1 环境为windows7 在工作复本的根目录上右键 gt

  • 小公司项目经理的一天，记录我普通的一天

    团队5人 xff0c 电子商务Web项目 xff0c 前段时间离职2人 xff0c 尚未补充 xff0c 手下现有一个开发组长 一个程序员 一个美术设计 一个运营专员 xff0c 还算一个完整的战斗单位 直接汇报对象 xff0c 几乎是老总

  • 关于ASP.NET木马ASPXSPY的初步处理研究

    前段时间服务器中了木马了 xff0c 经过排查 xff0c 截获了ASPXSPY木马 该木马是用ASP NET写的 xff0c 为了知己知彼 xff0c 就将木马拷到本地运行研究 xff0c 发现功能真的很强大 xff0c 自认为服务器设置

  • 身于“乱世”，我们程序员应该如何打算？

    不仅要低头拉车 xff0c 还要抬头看路 在周末夜深人静的时候就要思考一下人生 此 乱世 虽非战火纷飞 民不聊生的彼乱世 xff0c 但是整个社会的观感确实让人不得不焦虑 xff1a 不断飞涨的物价 xff0c 让买猪肉鸡蛋都觉得有压力 x

  • 开发人员流失之痛和团队重建之困

    最近笔者正在经历人员流失和团队重建的难题 xff0c 趁周末整理一下思路 xff0c 准备重整旗鼓 今年也算是多事之秋 xff0c 作为公司一员 xff0c 于公于私都有些坐不住了 面对开发人员 xff08 当然其他部门也有辞职 一个一个的

  • 从电影《三傻大闹宝莱坞》看IT新手应如何学习？

    三傻大闹宝莱坞 电视上又在放 xff0c 又看了一遍 xff0c 觉得很赞 很喜剧 很有意义 很励志 追求卓越 xff0c 成功将不穿裤子追着你跑 代替富翁主人儿子去读大学的兰乔在学校干了很多离经叛道的事情 xff0c 由此也产生了许多爆笑

  • 程序员，2012，不再生活在别处

    2011走到了尽头 xff0c 这一年有太多事情值得去书写和记忆 xff1a 浪漫的自行车户外婚礼 xff0c 历尽艰辛迎来了小宝宝 xff0c 整个部门业绩比去年增长了几倍 阳春三月 xff0c 黄道吉日 xff0c 在一群年轻朝气的自行

  • RTX, uCOS-II, FreeRTOS embOS, uCOS-III的综合性能PK

    这5款OS的PK主要分为以下四个方面 1 FLASH和RAM的需求对比 2 功能对比 3 实时性对比 4 安全性对比 1 FLASH和RAM的需求对比 RTX uCOS II FreeRTOS embOS uCOS III FLASH lt

  • 当段子手已经hi起来的时候，产品经理也来瞎逼逼一下faceid

    苹果发布会后 xff0c 各种段子满天飞 xff0c 着实热闹了一把 比较经典的包袱是 xff1a 老婆被老公刷脸 xff1b 被打成熊猫后没法报警 xff1b 韩国人没法用 xff1b 比较正式的疑问是 xff1a 双胞胎怎么办 xff1

  • SQL 2005安装时报已经安装了同名实例的问题解决。（无法正确卸载干净时最管用）

    最近重装SQL2005 xff0c 卸载后报 SQL 2005此计算机上已经安装了同名实例 说明原来的安装没有卸载干净 需要按照如下办法 1 停止服务 停止所有与SQL Server相关的服务 2 清楚残留的安装 使用windows ins

  • .NET Reflector 7.6.1.824安装及破解（刚试了，绝对能用）

    首先下载在这里http download csdn net detail gattaca2011 4578752 xff0c 不要到官网去了 xff0c 因为官网已经是8 0了 然后就是安装 xff0c 运行注册机 xff08 注意断网 x

  • 稍微冷门一点的经验，phpnow不能打开默认页的问题处理

    因为本地调试项目需要 xff0c 需要使用 phpnow 下载安装都很简单 xff0c 可是安装后127 0 0 1显示不出默认页 xff0c 而且一直处于加载状态 尝试 开始以后是一个网卡绑定了多个IP的问题 xff0c 于是移除多个IP

  • 每周五条-001

    2019 第2周 忙碌而焦虑 1 微信 微信支付服务商帐号是不能收款的 xff0c 如果同一个公司已经是服务商 xff0c 也不能在该服务商下创建本身的普通商户号 解决办法直接申请普通商户号 2 微信 听了两天的公开课 xff0c 最大的感

  • OpenWrt 学习笔记【1】LEDE17 安装huawei E8372

    写在前面的话 xff1a 路由器本身刷了LEDE后只是作为千兆交换机和手机wifi共享器 家中光线猫位置尴尬 xff0c 被关在入户的接线盒里 xff0c 信号差的一塌糊涂 xff0c 本来只是在luci界面直接尝试路由器自身2 4Gwif

  • Python3.6.2 pip install 报 【Fatal error in launcher: Unable to create process using ' " ' 】

    win10pro 原来的同事装了3 6 x xff0c 但是啥库都没安 xff0c 另一台自己的电脑原先安过需要的库 xff08 如h5py xff0c tf xff0c mkl等等 xff09 直接一波操作打压缩包拷过去解压覆盖 xff0

  • Keras2.2.2离线安装依赖包依赖Keras2.1.6解决方法。

    离线使用pip install 本地的whl包 xff0c 结果发现keras2 2 2安装失败 xff0c 照着提示依赖找到了Keras Applications 1 0 4与Keras Preprocessing 1 0 2 xff0c

随机推荐

  • 系统时间【linux基础】

    基础tip 备忘 who命令 1 xff09 who b 查看最后一次系统启动的时间 xxxxx 64 XXXXX who b system boot 2019 02 10 20 15 2 xff09 who r 查看当前系统运行时间 xx

  • 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 很难通过查看数据就发现其模式 这就

热门标签