《异常检测——从经典算法到深度学习》

0 概论
1 基于隔离森林的异常检测算法
2 基于LOF的异常检测算法
3 基于One-Class SVM的异常检测算法
4 基于高斯概率密度异常检测算法
5 Opprentice——异常检测经典算法最终篇
6 基于重构概率的 VAE 异常检测
7 基于条件VAE异常检测
8 Donut: 基于 VAE 的 Web 应用周期性 KPI 无监督异常检测
9 异常检测资料汇总（持续更新&抛砖引玉）
10 Bagel: 基于条件 VAE 的鲁棒无监督KPI异常检测
11 ADS: 针对大量出现的KPI流快速部署异常检测模型
12 Buzz: 对复杂 KPI 基于VAE对抗训练的非监督异常检测
13 MAD: 基于GANs的时间序列数据多元异常检测
14 对于流数据基于 RRCF 的异常检测
15 通过无监督和主动学习进行实用的白盒异常检测
16 基于VAE和LOF的无监督KPI异常检测算法
17 基于 VAE-LSTM 混合模型的时间异常检测
18 USAD：多元时间序列的无监督异常检测
19 OmniAnomaly：基于随机循环网络的多元时间序列鲁棒异常检测
20 HotSpot：多维特征 Additive KPI 的异常定位
21 Anomaly Transformer: 基于关联差异的时间序列异常检测)

15. 通过无监督和主动学习进行实用的白盒异常检测

论文名称：Practical and White-Box Anomaly Detection through Unsupervised and Active Learning
发表于 ICCCN 2020
下载地址：https://netman.aiops.org/wp-content/uploads/2020/08/ICCCN2020-YaoWang.pdf
会议PPT：https://netman.aiops.org/wp-content/uploads/2020/09/icccn-2020-talk-ppt.pdf
个人翻译地址：笑颜网
论文源码未能找到，抱歉。

15.1 论文概述

论文提出的模型 iRRCF-Active，包含两部分：

改进的 RRCF：(improved Robust Random Cut Forests) ，即 iRRCF
Active learning ：主动学习。

首先了解一下 RRCF 用于异常检测的基本原理 14. 对于流数据基于 RRCF 的异常检测。

接着看论文中的图3，即对模型结构的总体概述：
在这里插入图片描述
三个部分：

训练。用到了改进的 RRCF ，怎么改进的后面再看。
检测。用到了主动学习，这个步骤与 Feedback 关系密切。
优化。也就是主动学习的一个指导部分，这部分最好提供一下人工标签进行指导。

15.2 训练（III-A Training）

15.2.1 预处理（Preprocessing）

论文主要是对相似的 KPI 进行集群，这里面用到了两个方法：

Dynamic Time Warping (DTW) 用来计算两个 KPI 之间的相似程度（《Using dynamic time warping to find patterns in time series》）。
DBSCAN 对大量的KPI 进行集群。

这样做的主要目的是节省训练的时间，集群后 KPI 的长度以及 KPI 的数量都会有所减少。

15.2.2 改进的RRCF（Improved RRCF）

此部分主要包括以下几个方面。

特征表示 Feature Representation

先看表2，这里列举了改进的 iRRCF 与原始的 RRCF 的区别。

在这里插入图片描述

过程	原 RRCF	改进的RRCF
特征表示	历史临近点	具有特征选择的时间序列统计特征
结点分割选择	只考虑维度的范围	也考虑尺寸的最大距离
结点分割阈值选择	按随机选择的间隔切割	以最稀疏的间隔剪切
异常值计算	只考虑兄弟姐妹（同级）结点	还要考虑节点深度

在这里插入图片描述

特征	适用条件
中值	少毛刺的
标准差	固定的
与之前区域的点的差异	周期的
与之前的点的差异	趋势的
与第一点的二阶差	满足以上4点
三阶指数平均	可预测性

节点切割尺寸(维度)选择 Node Cut Dimension Selection

由于不同的KPI通常具有不同的统计特征，因此这些特征可能不适用于每个KPI。因此，论文设计了一组统计指标，并计算每个KPI的值。接下来，我们根据这组指标确定哪些特征适合KPI（如上表所示）。即，根据KPI的情况选择相应条件下的特征。

在这里插入图片描述
在提取数据特征以后， RRCF 会随机地选择分割尺寸（维度），并进行分割，来构建多棵决策树。首先看左边的图片（Fig. 4 (a)），首先把特征 1 进行分割，根据值是否大于 107.65 分割成两棵子树，进而下一步根据特征 2 进一步分割。**因为 Feature 1和 Feature 2 特征明显 (distinguishing)，所以只需要分割成两层就可以区分所有样本。 ** 右边的图（Fig. 4(b)）表示对于不明显的特征，需要分割成更多层才能把所有样本分开。（注意两张图片 Feature 2 是没有关系的，个人认为这样处理不妥，不如把右边的特征 2 改成特征 5 ）

节点分割阈值选择 Node Cut Threshold Selection

原始RRCF随机选择最大和最小特征值之间的值作为切割阈值。对于高分辨特征，其数据往往具有聚集分布，因此稀疏切割的效果要比密集切割的效果好得多。因此，在iRRCF中，在选择切割维度后，我们特别关注该维度中的数据分布，并增加稀疏分布中的切割概率。从形式上讲，这个过程可以总结如下：

将从训练集中提取的特征划分为 $N$ 个区间 $l_0, h_0,l_1,h_1,...,l_{N-1},h_{N-1}]$
计算每个区间的特征密度 $d_i = Count(p, p\in [l_i, h_i])$ 。
选择一个与 $\frac{d_i}{\sum_j {d_j}}$ 成比例的随机区间 $i$ 。
选择 $X_i \sim Uniform[l_i, h_i]$ 。

异常值计算 Anomaly Score Calculation

在RRCF中，每个样本将落在树中的一个叶节点上，原始RRCF林将计算每个样本的异常得分 $C oD i s p$ ，以表征异常程度。 $C oD i s p$ 的计算过程如下：

找到每棵树的叶子中样本 $x_i$ 的叶子结点 $N o d e$ 。
计算 $N o d e$ 的兄弟结点以及父结点为根的子树中的样本数，记作 $S_{Node.sibling}$ 和 $S_{Node.parent}$ ，计算 $CoDisp_{Node} = \frac{S_{Node.sibling}}{S_{Node.parent}}$ 。
在树上上升一级， $N o d e = N o d e . p a re n t$
重复 2 与 3 步骤 $N$ 次，其中 $N$ 是使用的特征的数量。
$CoDisp_T$ 是每一个 $CoDisp_{Node}$ 的最大值。
对于样本 $x_i$ 的最终的 $CoDisp_{x_i}$ 为 $CoDisp_T$ ，其中 $\in forest$

15.3 检测 (Detection)

15.3.1 候选标签推荐 Candidate Labels Recommendation

这部分的内容可以概述为：如何协助操作员，把最需要人工标记的部分推给操作员进行手动标记，标记完了后，可以更好地维护更新模型。

具体内容大致包括：

选择30个最不正常的段。获得这些标签可以进一步确认明显的异常并消除误报。
选择30个最不确定的异常片段。时间序列的异常检测是一个二元分类问题。获得此类标签可以进一步改善分类结果的边界，还可以提高识别模糊异常的准确性。
根据异常评分将数据分为10组，每组选择3个异常片段，概率中等。获取这些标签可以捕获操作员对算法评估产生的不同程度的异常的偏好，然后有助于确定哪一组更可能成为异常和正常情况之间的边界点。

在这里插入图片描述
iRRCF中这些策略的详细实现如图5 所示。根据第四节中的实验，策略 1 被证明比其他两种策略更有效。因此，论文在模型中采用了策略 1。

15.3.2 模型优化 Model Optimization

模型优化：原始RRCF基于实时数据维护动态树集合。当新数据点到达时，RRCF执行插入过程，并使用该数据点更新模型中的每个树。此过程会导致额外的计算，从而减慢检查过程。考虑到实际中异常的数量相对较少，可以根据数据的异常程度有选择地更新树。为了确保模型能够及时覆盖极端特征的变化，需要更新两类数据点。一种类型是连续异常段中的第一个异常点，另一种类型是在特定维度上被判断为正常但极度异常的点。我们统称这两类点为极端点。此外，为了获得某些特殊曲线的缓慢变化趋势，iRRCF-Active还将在两类数据点长时间未出现时，以较低的频率使用正常点更新模型。我们的方案如算法1所示。

论文中算法1 则是指异常值计算与模型优化，具体内容如图所示：

在这里插入图片描述
关于 CODISP§ ，请参照上面异常值计算部分。