SDM 2021丨RecForest：基于重构和完全随机森林的异常检测模型

论文标题丨Reconstruction-based Anomaly Detection with Completely Random Forest
论文来源丨SIAM/SDM 2021
论文链接丨http://129.211.169.156/publication/sdm21anomalyCRF.pdf
源码链接丨https://github.com/xuyxu/RecForest

TL;DR

基于 AutoEncoder 重构的异常检测器一般需要大量的训练数据集而且模型模型包含大量的超参数，因此周志华老师团队的这篇论文中提出了一个基于完全随机森林重构的异常检测模型 RecForest。主要具备三个优点：（1）相比于 AutoEncoder，树模型训练速度快而且超参数少（2）相比于当前的树异常检测模型，RecForest 可以挖掘和处理高维数据集中的离群属性和无关属性（3）相比于当前 baselines 挖掘离群属性，RecForest 运行速度更高。实验部分在多个数据集中验证了 RecForest 的有效性和运行效率。

Definition

相关工作不再细述，可以参考历史中基于树模型异常检测的两篇博客：

论文符号表示

Algorithm/Model

RecForest 主要包括三步：

Bounding Boxes and Completely Random Forest
Anomaly Detection with RecForest
RecForest for Outlying Aspects Mining

边界和完全随机森林

针对样本 $\mathbf{x}$ 的边界是指输入空间中包围目标 $\mathbf{x}$ 邻近区域的矩形框，给定边界后重构的 $\mathbf{x}$ 被定义为边界的中心。

RecForest 的主要目标是为每个样本生成边界，以生成重构样本。📢 注意：RecForest 只有在边界框足够小可以捕获与样本 $\mathbf{x}$ 相关的局部邻域时才有效。

至于如何为每个样本生成边界，论文中用到的就是完全随机树（completely random tree）。

给定一棵树， $\mathbf{x}$ 的边界被定义为 $\mathbf{x}$ 从树的根节点遍历到的叶节点区域。为了缩小边界，论文中采用完全随机森林的中所有完全随机树的边界交集作为样本 $\mathbf{x}$ 的边界。

定义 1：边界框 $\mathbf{B}$

$\mathbf{B}=\left\{\mathbf{x} \in \mathbb{R}^{d} \mid L_{i} \leq x_{i} \leq U_{i}, \forall i=1, \ldots, d\right\}$

定义 2：集合 $\mathcal{D}$ 最小边界框 $\mathbf{B}_{\mathcal{D}}$

$\begin{aligned} L_{i}^{\mathbf{B}_{\mathcal{D}}} &=\min \left\{x_{i} \mid \forall \mathbf{x} \in \mathcal{D}\right\} \\ U_{i}^{\mathbf{B}_{\mathcal{D}}} &=\max \left\{x_{i} \mid \forall \mathbf{x} \in \mathcal{D}\right\} \end{aligned}$