Stata:异常值检测算法-分离森林-iforest

发布时间:2023-01-14 阅读 406

Stata连享会   主页 || 视频 || 推文 || 知乎 || Bilibili 站

温馨提示: 定期 清理浏览器缓存,可以获得最佳浏览体验。

New! lianxh 命令发布了:
随时搜索推文、Stata 资源。安装:
. ssc install lianxh
详情参见帮助文件 (有惊喜):
. help lianxh
连享会新命令:cnssc, ihelp, rdbalance, gitee, installpkg

课程详情 https://gitee.com/lianxh/Course

课程主页 https://gitee.com/lianxh/Course

⛳ Stata 系列推文:

PDF下载 - 推文合集

作者:陈娉影 (中山大学)
邮箱chenpy57@mail2.sysu.edu.cn


目录


1. 简介

iforest 是 isolation forest (分离森林) 的简称,适用于连续数据的异常检测。其中,异常检测又称“离群点检测”,是机器学习领域里应用较为广泛的一类问题。“异常”在这里指“容易被孤立的点”,即分布稀疏且距离高密度的点比较远的数据。基于此,可总结出“异常”的两个特征:

  • 异常数据跟样本中大多数数据不太一样;
  • 异常数据在整体数据中占比较小。

一般的异常检测方法主要是通过对正常样本的描述,给出一个正常样本在特征空间中的区域,对于不在这个区域中的样本,视为异常。这类方法只优化正常样本的描述,而不优化异常样本的描述,可能造成大量误报或只检测到少量异常。

其次,异常数据的一般刻画方法必须用到各种统计、距离、密度的量化指标来描述异常数据跟其他样本的疏离程度。而 iforest 通过直接孤立异常点来刻画数据的疏离程度,不只针对正常样本,也不用借助其他量化指标,因此更为简单和高效。

2. 算法原理

2.1 基本思想

假设有一组一维数据 (见下图),对其进行随机切分来把点 A 和点 B 单独割开。首先,在最大值和最小值之间随机选取一个值 x,小于 x 的数据分为左边一组,大于等于 x 的分为右边一组。

然后,对左右两组数据分别重复上述步骤,直到某组中数据个数小于 2 才停止分割该组。由于点 B 与其他数据比较疏离,可能用很少的次数就分割出来;点 A 跟其他点聚在一起,大概率需要更多的次数才能切分出来。

从一维扩展到两维也是同样的 (见下图),只是变为沿着两个坐标轴随机切分来把点 A' 和 B' 分别分割出来。首先,随机选择一个特征维度,在最大值和最小值之间随机取值,再分左右两组。

接下来重复上述所有步骤,直到无法细分 (即只剩下一个数据点或剩下的数据全部相同)。由于点 B' 与其他数据点比较疏离,可能只需要几次切分就可以将它分出;而点 A' 需要的切分次数大概率会更多。

2.2 分离树的构建

iforest 采用二叉树 (每个节点有两个子节点或不再分叉) 分割数据,用数据在二叉树中的深度反应其“疏离”程度。所以分离树即二叉树的构建就是整个算法的第一步。

基于对上文基本思想的介绍,可以更容易地理解分离树的构建,即从连续型的全量数据集中抽取一批样本,然后执行以下步骤:

  1. 随机选择一个特征作为起始节点;
  2. 在该特征的最大值和最小值之间随机取一个值;
  3. 样本中小于该值的数据记到左分支,大于等于该值的记到右分支;
  4. 在左右两个分支中,重复步骤 1、2、3,直到满足如下条件:(1) 数据不可再分,即只包含一个数据或全部数据相同;(2) 二叉树达到限定的最大深度。

2.3 结合多棵分离树进行预测

构建好分离树就可以开始预测。分离树检测异常的原理是:异常值一般比较稀有,会很快地被分到叶子节点,所以异常值在分离树中从根节点到叶子节点的路径长度 h(x) 很短,故可据此来判断异常数值。

但只使用一棵树的结果作为判断依据过于武断,所以需要把多棵分离树结合起来,形成分离森林 (见下图)。

假设 itree 的训练样本中同样落在数据 x 所在叶子节点的样本数为 T.size,则 x 在这棵 itree 上的路径长度 h(x) 为:

其中,H(n1) 可用 ln(n1)+0.5772156649 (欧拉常数) 估算。综合多棵 itree 后 x 最终的异常分值 Score(x) 为:

其中,E(h(x)) 表示数据 x 在多棵 itree 中的路径长度的均值,ψ 表示单棵 itree 的训练样本数,C(ψ) 表示用 ψ 条数据构建的二叉树的平均路径长度,主要用于归一化。

由异常分值的公式可得,若 x 在多棵分离树中的平均路径长度越短,得分越接近 1,x 越异常;若 x 在多棵分离树中的平均路径长度越长,得分越接近 0,数据 x 越正常;若 x 在多棵分离树中的平均路径长度接近整体均值,则得分约为 0.5。

3. iforest 命令

命令安装:

copy "https://github.com/adallak/stataiforest/archive/refs/heads/main.zip" "iforest.zip", replace
unzipfile "iforest.zip", replace
adopath + "./stataiforest-main"
cd "./stataiforest-main"
* To build Mata libraries run
do make_liforest  //这一步很重要,定义 mata 函数

命令语法:

iforest varlist [if] [in] [, options]

其中,options 包括:

  • ntrees(#):总体中用的分离树数量,默认值为 200。
  • samplesize(#):为训练每棵分离树而从数据中提取的样本大小,必须小于观察值个数 n。
  • maxdepth(#):树的最大深度,默认值为 log2 (samplesize)。
  • extlevel(#):指定用于分割数据的超平面的自由度,必须小于数据的观察值个数 n。
  • nohist:不要绘制估计得分的直方图 (不加此选项则默认绘制估计得分的直方图)。
  • hist_options(#):直方图选项。

4. 命令使用

. clear all
. set seed 20327015
. gendata, n(600) p(2) type(cluster) // 随机生成矩阵
. mat X = r(X)  // 将生成的 X1、X2 (二维)的、400 个观察值的矩阵录入矩阵 X
. mat Y = r(Y)  // 若观测值异常,则允许 1 的二进制向量
. svmat X       // 将矩阵 X 中的数据转化为数据,变量为 X1,X2,X3
. svmat Y       // 异常则记 Y1=1,否则为 0
. iforest X1 X2, extlevel(1) ntrees(100) samplesize(256) // 使用 iforest 命令对观测值进行估分
. mat list e(Score)   // 列出 iforest 估计的得分。
. estat metric Y1     // 当真实目标 Y 已知时,我们可以找到预测的最佳阈值

 iForest estimated AUC score .893287037 
  Threshold   | Sens.     Spec.     TDR       F1
--------------+-----------------------------------
        .1    | 1.00      0.00      0.10      0.18
       .15    | 1.00      0.00      0.10      0.18
        .2    | 1.00      0.00      0.10      0.18
       .25    | 1.00      0.00      0.10      0.18
        .3    | 1.00      0.00      0.10      0.18
       .35    | 0.90      0.69      0.24      0.38
        .4    | 0.90      0.69      0.24      0.38
       .45    | 0.87      0.77      0.29      0.44
        .5    | 0.68      0.97      0.72      0.70*
       .55    | 0.68      0.97      0.72      0.70
        .6    | 0.68      0.97      0.72      0.70
       .65    | 0.47      0.99      0.78      0.58
        .7    | 0.35      0.99      0.78      0.48
       .75    | 0.12      1.00      0.88      0.21
        .8    | 0.02      1.00      1.00      0.03
       .85    | 0.00      1.00        .      0.00
        .9    | 0.00      1.00        .      0.00

.                     // 结果表明,0.5 是最佳阈值,故使用该值进行预测
. predict Yhat, threshold(0.7) // 设定正常值占 70% 进行预测,异常值记为 1,否则为 0
. ifroc Y1                     // 也可以通过可视化 ROC 来评估算法的性能

 iForest estimated AUC score .893287037 
  Threshold   | Sens.     Spec.     TDR       F1
--------------+-----------------------------------
        .1    | 1.00      0.00      0.10      0.18
       .15    | 1.00      0.00      0.10      0.18
        .2    | 1.00      0.00      0.10      0.18
       .25    | 1.00      0.00      0.10      0.18
        .3    | 1.00      0.00      0.10      0.18
       .35    | 0.90      0.69      0.24      0.38
        .4    | 0.90      0.69      0.24      0.38
       .45    | 0.87      0.77      0.29      0.44
        .5    | 0.68      0.97      0.72      0.70*
       .55    | 0.68      0.97      0.72      0.70
        .6    | 0.68      0.97      0.72      0.70
       .65    | 0.47      0.99      0.78      0.58
        .7    | 0.35      0.99      0.78      0.48
       .75    | 0.12      1.00      0.88      0.21
        .8    | 0.02      1.00      1.00      0.03
       .85    | 0.00      1.00        .      0.00
        .9    | 0.00      1.00        .      0.00

Isolation Forest model for Y1
Number of observations =      600
Area under ROC curve   =   0.8933

5. 结语

分离森林算法主要有两个参数:一个是分离树的个数;另一个是训练单棵分离树时抽取样本的数目。实验表明,当设定为 100 棵树,256 个抽样样本数时,大多数情况下就可以取得不错的效果。这也体现了算法的简单、高效。以下是需要注意的几个问题:

第一,构建分离森林的方法和随机森林类似,都是随机采样部分数据来构建每一棵树,保证不同树之间的差异。但是区别在于分离森林要限制样本的大小。因为采样前初始样本过大时正常值和异常值会有重叠,但采样后较小的子样本可以有效地区分正常值和异常值 (如下图所示:初始数据和采样数据,即采样前和采样后)。

第二,要限制分离树的最大深度。因为异常值比较少,其路径一般比较短。深度设置得过大,会产生很多没有意义的计算,浪费时间和资源。

第三,如果训练样本中异常样本的比例比较高,违背了先前提到的异常检测的基本假设,可能最终的效果会受影响。

第四,异常检测与具体应用场景紧密相关,算法检测出的“异常”不一定是实际所需。比如,在识别虚假交易时,异常的交易未必就是虚假的交易。所以,在选择特征时,需要过滤相关性较低的特征,以免识别出一些不太相关的“异常”。

6. 参考资料

  • 机器学习-异常检测算法 (一):Isolation Forest -Link-
  • Python机器学习笔记:异常点检测算法——Isolation Forest -Link-
  • 孤立森林(Isolation Forest)从原理到实践 -Link-
  • 高效优雅的异常检测算法——iForest -Link-
  • adallak/stataiforest -Link-

7. 相关推文

Note:产生如下推文列表的 Stata 命令为:
lianxh 异常 离群 随机森林, m
安装最新版 lianxh 命令:
ssc install lianxh, replace

相关课程

免费公开课

最新课程-直播课

专题 嘉宾 直播/回看视频
最新专题 文本分析、机器学习、效率专题、生存分析等
研究设计 连玉君 我的特斯拉-实证研究设计-幻灯片-
面板模型 连玉君 动态面板模型-幻灯片-
面板模型 连玉君 直击面板数据模型 [免费公开课,2小时]
  • Note: 部分课程的资料,PPT 等可以前往 连享会-直播课 主页查看,下载。

课程主页

课程主页

关于我们

  • Stata连享会 由中山大学连玉君老师团队创办,定期分享实证分析经验。
  • 连享会-主页知乎专栏,400+ 推文,实证分析不再抓狂。直播间 有很多视频课程,可以随时观看。
  • 公众号关键词搜索/回复 功能已经上线。大家可以在公众号左下角点击键盘图标,输入简要关键词,以便快速呈现历史推文,获取工具软件和数据下载。常见关键词:课程, 直播, 视频, 客服, 模型设定, 研究设计, stata, plus, 绘图, 编程, 面板, 论文重现, 可视化, RDD, DID, PSM, 合成控制法

连享会小程序:扫一扫,看推文,看视频……

扫码加入连享会微信群,提问交流更方便

✏ 连享会-常见问题解答:
https://gitee.com/lianxh/Course/wikis

New! lianxh 命令发布了:
随时搜索连享会推文、Stata 资源,安装命令如下:
. ssc install lianxh
使用详情参见帮助文件 (有惊喜):
. help lianxh