异常检测算法-RRCF(Robust Random Cut Forest)

最近部门架构变化，方向由原来的CV切换到了AIops，需要用到监控数据的根因分析和异常检测。因此把AIops里的常用算法整理一下，在异常检测里比较有名的莫过于RRCF里，是亚马逊改进了周志华老师提出的孤立森林（Isolation Forest）产生的，因此在介绍RRCF的原理之前我们需要科普一下孤立森林（Isolation Forest）。

1. 孤立森林（Isolation Forest）

1.1 原理简介

孤立森林对异常点的定义为“容易被孤立的点”，我们可以理解为在样本空间中分布较为稀疏，且距离密度高的群体距离较远的点，而在样本空间中分布较为稀疏代表着这个样本点发生的概率较低，并且距离密度高也就是大部分正常的样本距离较远，当样本落入到这种区域我们可以将其判定为异常点。

孤立森林是一种无监督学习的算法，它不需要大量的标注样本。由该算法对异常的定义可以得知，它希望在我们的数据中，异常数据是占很少的一部分，并且异常样本的数据与正常样本相差较大（较容易区分）。当样本中存在大量异常数据时，算法会将其认为是正常样本。

孤立森林是如何找到那些异常的点的呢？用简单的话来说，算法用随机的超平面对样本空间进行切割，知道每个子空间包含一个样本点为止。那些密度较低的簇会很容易被划分开，而那些密度较高的簇可能需要多个超平面才能将里面的样本点“孤立”开。下面我们对其进行算法流程进行阐述：

孤立森林是由很多可独立的子树构成，每棵子树的训练过程如下：

从样本N中随机抽选K个点作为样本子集，放入树的根节点中

随机从样本特征中选取一个特征，在该特征值的最大值与最小值区间内随机选取一个值p作为划分值

以次切割点作为一个超平面，将样本空间划分为两个字空间，将小于划分值p的点放在左子节点中，大于等于划分值p的放入右子节点中；

对步骤3中生成的两个子节点重复步骤2和步骤3，直到子节点中止存在一个点，那么将该子节点作为叶子结点，或者当树的高度达到限定高度时，停止划分；

因为每次选取特征和划分值都是随机的，因此我们需要使用ensemble的方式，来让算法结果收敛。那么孤立森林是如何计算样本的异常得分的呢？我们需要知道下面几个定义：

路径长度：样本$x$的路径长度$h(x)$为从树的根节点到包含x到叶节点所经历的边数；

树的平均路径长度：给定一个包含$n$个样本的树，它的平均路径长度为：

$c(n)=2H(n-1)-2\frac{(n-1)}{n}$

其中$H(x)$为调和函数，该值可以被估计为$ln(x)+0.5772156649$。

那么给定样本$x$时，它的异常得分为：

$s(x,n)=2^{-\frac{E(h(x))}{c(n)}}$

当$E(h(x))\rightarrow{c(n)}$时，$s(x,n)\rightarrow0.5$，也就是孤立森林计算出样本点$x$的路径长度为平均路径长度，这时我们无法判断这个点是否为异常；

当$E(h(x))\rightarrow{0}$时，$s(x,n)\rightarrow{1}$，也就是孤立森林计算出样本点$x$的路径长度接近0，这时这个样本可以认为是一个很好被切分出来的异常点；

当$E(h(x))\rightarrow{n-1}$时，$s(x,n)\rightarrow{0}$，也就是孤立森林计算出样本点$x$的路径长度接近$n-1$，这时这个样本很难被单独划分开，因此判定为正常；

1.2 算法的优缺点

孤立森林的优点有以下两点：

由于每棵树都是独立的，因此在分布式的系统中加速计算；
不同与聚类算法，它不需要计算点与点之间的距离或者簇的密度，模型为线性时间的复杂度，速度快，系统开销小；

而它的缺点也很明显：

孤立森林不适用于维度较高的样本数据。因为当树的样本量确定之后，树的高度确定了。当样本维度较高时，会存在建完树之后仍有大量的特征信息未被使用，从而导致了算法的准确性。并且高纬样本空间中可能会存在一些无关的维度或者噪音维度，这些也会对树的构建产生影响；
孤立森林只对Global Abnormaly敏感，也就是全局稀疏点敏感，而对于局部稀疏点（Local Abnormal）的检测效果并不是特别明显

2. 稳健随机采伐森林（Robust Random Cut Forest）

孤立森林虽然复杂度低，适合并行计算。但是在业务场景里，我们通常是实时流数据。在面对流式数据时，孤立森林会有以下几点问题：

数据是随着时间的流逝而产生的，孤立森林会遗漏时间这个维度；

孤立森林的每棵树在建立候选样本集合时，采用的是针对整体样本的无放回抽样，而在流式数据中，我们需要每次对最新的数据进行采样，构建出数据集；

孤立森林在面对流式数据时，每次来一个点都要重新去构建树，整体耗时以及复杂度较高；

针对第二个问题，我们可以采用蓄水池算法来代替整体无放回抽样。

针对第三个问题，对于RRCF来说，树的构建方式与孤立森林是一致的，但是论文里做出了两个定理的证明

对于点p来说，由数据集N构建的树T1，将p点从Tree1中删除得到的树T2与直接由数据集N-p构建的树T3得到的概率分布是一致的;

对于点p来说，由数据集N构建的树T1，将p点插入到Tree1中得到的树T2与直接由数据集N+p构建的树T3得到的概率分布是一致的；

这两个定理意味着，我们要计算由插入或者删除某个点带来的树的复杂度的变化，只需要通过将点直接从树上插入或者删除，而不需要在使用新的数据集来构建树，这是RRCF可以应用于流式数据的理论依据。

2.1 RRCF的相关定义

那么对于RRCF来说，异常是如何来判定的呢？下面先介绍几个定义

叶子结点：对于叶子结点，通常用一个由0，1组成的向量来表示它，比如（0，1，0，1），其中0代表父节点的左孩子，1代表父节点的右孩子。而向量则是从树的根节点出发，到达该叶结点所走过的路径；

树：树则是用所有的叶子结点的向量来表示，树的复杂度则可以由所有叶子结点在树中的深度之和来表示；

点的displacement：将该点从树中删除后，树复杂度的变化量为点的displacement。而点的displacement代表了该点的异常程度，displacement越大，则点的异常程度越大；

点的displacement刻画了删除该点后树的复杂度的变化，但是树中存在和异常点非常相近的点时，这个时候删除了异常点对整棵树的结构影响并不会很大，这个时候很有可能会漏检。此时需要使用到点的co- displacement来代替它刻画异常程度。

点的co-displacement：它不仅仅删除改节点来计算树的复杂度变化量，还会去计算删除改节点的父节点，祖父节点，曾祖父节点…每删除一个点集，计算模型复杂度的变化量，该点的co-displacement为所有变化量的最大值。

2.2 RRCF检测流程

RRCF的检测流程可以分为冷启动和热启动两种：

热启动

在热启动过程中，我们会预先获得一批数据，整个异常检测流程如下：

对数据进行采样分区，对每一个分区进行建树操作，得到RRCF模型；

将待检测点插入到每棵树中，计算点的co-disp；

计算所有树的co-disp的均值作为异常得分，将异常得分与阈值进行比较，判断是否为异常；

将待检测点从所有树中删除；

随机选取一颗树，替换树中最旧的点；

冷启动

冷启动不需要预先获取数据来训练好树模型，而是从一颗空树开始，不断的插入点，等到树里的点到达设定的tree size后，再对树进行删除替换点；

初始化N颗空树；

将待检测点插入到每棵树中，就是那点的co-disp；

计算所有树的co-disp的均值作为异常得分，将异常得分与阈值进行比较，判断是否为异常；

将检测点从所有树中删除；

判断树的大小是否到达tree size，如果到达了，则随机选取一颗树，替换树中最旧的点，否则直接将点插入到树中；

在冷启动的检测流程中，我们一般在树未到达tree size时，不会去计算异常得分，等到树构建完成再进行异常的判断；