RRCF：基于随机割森林的数据流异常检测模型

论文标题 ｜ Robust Random Cut Forest Based Anomaly Detection On Streams
论文来源 ｜ ICML 2016
论文链接 ｜ http://proceedings.mlr.press/v48/guha16.pdf
源码链接 ｜ python: https://github.com/kLabUM/rrcf | java: https://github.com/aws/random-cut-forest-by-aws

TL;DR

论文中提出一种基于随机割森林的数据流异常检测算法 RRCF (Robust Random Cut Forest)，主要是对于 iForest 模型进行优化改进，可以对输入数据流进行有效地表示和异常检测。实验中证明 RRCF 比 IForest 更加高效和准确。此外，RRCF 模型已经被 AWS 作为一项异常检测服务对外开源，说明了其在实际环境中的可用性。👍

Algorithm/Model

背景

论文中首先就引入异常检测的两个经典问题：

1. 如何定义异常？

2. 采用何种数据结构在动态流式数据中高效地检测异常？

对于第一点，作者从模型复杂度的来定义：如果模型的复杂度随着该某数据点增加那么该点就是异常点，这点和 IForest 思想类似。

对于第二点，作者采用随机化的方法来检测异常，因为在监督学习中该方法被证明是有效的，这点和 Dropout 思想有点类似。

综合以上两点，就提出了随机割森林的数据流异常检测方法 RRCF。

🌲 给定数据点集$S$ 随机割树 RRCT 的定义如下：

1. 随机选择一个特征维度，概率正比于$\frac{\ell_{i}}{\sum_{j} \ell_{j}}$，其中$\ell_{i}=\max _{x \in S} x_{i}-m i n_{x \in S} x_{i}$.
2. 选择样本点$X_{i} \sim Uniform\left[\min _{x \in S} x_{i}, \max _{x \in S} x_{i}\right]$ 符合均匀分布。
3. 划分集合$S_{1}=\left\{x \mid x \in S, x_{i} \leq X_{i}\right\}$，$S_2=S - S_1$。
4. 在$S_1$ 和$S_2$ 中重复以上步骤。

🌳 RRCF 就是 🌲 RRCT 的集合。

整体思路和 IForest 类似， 可以参考另一篇博文：iForest 异常检测算法及其 Python 实现。不同点就在于第 1 步：随机选择特征时的概率。

第二点需要考虑的即为 RRCF 是否包含足够的信息并且所构造的树相互独立，可以区分不同场景中异常点？

下面就是一系列理论和定义，大概就是为了说明论文中方法的合理性和异常可解释性，不看 🙈…

流式数据中 RRCF 动态维护

维护 RRCF 主要包含两种操作：添加节点和删除节点。

给定历史数据点$S$ 得到的森林为$RRCF(S)$，插入节点即为$RRCF(S)$ 中的$T$ 和新的数据点$p$ 生成新的树$T^{'}$ ，删除节点则反之。

删除节点

删除节点的 Algorithm 1 达到的效果如下图所示：

插入节点

---

---

论文中的算法描述太不精简了，可以参考下其它更加详细的描述。

1. 构造 RRCF 树

   

2. 插入节点

   

3. 删除节点

   

4. 计算异常分数

   

Experiments

从时间序列图能更加直观地观察出 RRCF 比 IForest 更加稳定和准确。

Thoughts

论文中将 iForest 思想进行改进并应用于动态流数据的异常检测中，虽然更改的点非常小但效果非常好，大佬还是大佬啊。

Contact