基于二叉树的ensemble异常检测算法.doc
《基于二叉树的ensemble异常检测算法.doc》由会员分享,可在线阅读,更多相关《基于二叉树的ensemble异常检测算法.doc(2页珍藏版)》请在三一文库上搜索。
1、基于二叉树的ensemble异常检测算法iForest (Isolation Forest)是由Liu et al. 1 提出来的基于二叉树的ensemble异常检测算法,具有效果好、训练快(线性复杂度)等特点。1. 前言iForest为聚类算法,不需要标记数据训练。首先给出几个定义:划分(partition)指样本空间一分为二,相当于决策树中节点分裂;isolation指将某个样本点与其他样本点区分开。iForest的基本思想非常简单:完成异常点的isolation所需的划分数大于正常样本点(非异常)。如下图所示:xi 样本点的isolation需要大概12次划分,而异常点x0指需要4次左右
2、。因此,我们可以根据划分次数来区分是否为异常点。但是,如何建模呢?我们容易想到:划分对应于决策树中节点分裂,那么划分次数即为从决策树的根节点到叶子节点所经历的边数,称之为路径长度(path length)。假设样本集合共有n个样本点,对于二叉查找树(Binary Search Tree, BST),则查找失败的平均路径长度为其中,H(i)为harmonic number,可估计为ln(i)+0.5772156649。那么,可建模anomaly score:其中,h(x)为样本点x的路径长度,E(h(x)为iForest的多棵树中样本点x的路径长度的期望。特别地,当s值越高(接近于1),则表明该点越可能为异常点。若所有的样本点的s值都在0.5左右,则说明该样本集合没有异常点。2. 详解iForest采用二叉决策树来划分样本空间,每一次划分都是随机选取一个属性值来做,具体流程如下:停止分裂条件:树达到了最大高度;落在孩子节点的样本数只有一个,或者所有样本点的值均相同;为了避免错检(swamping)与漏检(masking),在训练每棵树的时候,为了更好地区分,不会拿全量样本,而会sub-sampling样本集合。iForest的训练流程如下:sklearn给出了iForest与其他异常检测算法的比较。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 二叉 ensemble 异常 检测 算法
链接地址:https://www.31doc.com/p-3416783.html