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

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 系列推文：

• 全部 | Stata入门 | Stata教程 | Stata资源 | Stata命令
• 计量专题 | 论文写作 | 数据分享 | 专题课程
• 结果输出 | Stata绘图 | 数据处理 | Stata程序
• 回归分析 | 面板数据 | 交乘项-调节 | IV-GMM
• 内生性-因果推断 | 倍分法DID | 断点回归RDD | PSM-Matching | 合成控制法
• Probit-Logit | 时间序列 | 空间计量 | 分位数回归 | 生存分析 | SFA-DEA
• 文本分析-爬虫 | Python-R-Matlab | 机器学习
• Markdown | 工具软件 | 其它

☝ 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(n-1)$ 可用 $ln(n-1)$+0.5772156649 (欧拉常数) 估算。综合多棵 itree 后 $x$ 最终的异常分值 $Score(x)$ 为：

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

由异常分值的公式可得，若 $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

• 专题：数据处理

  • winsor2：离群值和异常值的缩尾处理
  • Stata：离群值！离群值？离群值！
• 专题：Stata程序

  • Stata：随机森林算法简介与实现
• 专题：机器学习

  • 机器学习：随机森林算法的Stata实现

相关课程

免费公开课

• 直击面板数据模型 - 连玉君，时长：1小时40分钟，课程主页，Bilibili 站版
• Stata 33 讲 - 连玉君, 每讲 15 分钟. 课程主页，课件，Bilibili 站版
• Stata 小白的取经之路 - 龙志能，时长：2 小时，课程主页
• 部分直播课 课程资料下载 (PPT，dofiles等)

最新课程-直播课

• Note: 部分课程的资料，PPT 等可以前往 连享会-直播课 主页查看，下载。

⛳ 课程主页

⛳ 课程主页

关于我们

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

连享会小程序：扫一扫，看推文，看视频……

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

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

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