基于数据流的异常检测：Robust Random Cut Forest

2021-10-03 21:28:57

一、解决的问题

数据是实时产生的，对数据进行批处理所花费的成本太高了，数据产生的价值被低估
在高维数据下，如何能发现异常的维度？

If my time-series data with 30 features yields an unusually high anomaly score. How do I explain why this particular point in the time-series is unusual? Ideally I'm looking for some way to visualize "feature importance" for a specific data point.

二、业内的解决方案

1、Numenta公司提出的HTM算法模型

背景：在大多数情况下，传感器流的数量很大，人类很少有机会，更不用说专家干预了。因此，以无人监督的自动方式（例如，无需手动参数调整）操作通常是必要的。底层系统通常是非平稳的，探测器必须不断学习和适应不断变化的统计数据，同时进行预测。 Hierarchical Temporal Memory （HTM）网络以有原则的方式在各种条件下稳健地检测异常。
生产系统应该是高效的，非常容忍噪声数据，不断使用数据统计的变化，并检测非常微妙的异常，同时最大限度地减少误报。该算法在实时金融异常检测中表现较好，切已经得到商业化部署。HTM与序列预测中的一些现有算法相比是有利的，特别是复杂的非马尔可夫序列，HTM不断学习系统，自动适应不断变化的统计数据，这是一种与流分析特别相关的属性。
该公司开发的Grok系统，目前服务在AWS，针对物理机器进行异常检测。The Leading AIOPS Platform For Intelligent Incident Prediction And Self-Healing Operations In IT Service Assurance

2、Amazon Kinesis

2.1 应用场景

AWS Metering
Amazon S3 events
Amazon Cloud Watch Logs
Amazon.com online catalog
Amazon Go Video analysis

2.2 Kinesis - RRCF调用方式

-- creates a temporary stream.
CREATE OR REPLACE STREAM "TEMP_STREAM" (
  "passengers" INTEGER,
  "distance" DOUBLE,
  "ANOMALY_SCORE" DOUBLE);

-- creates another stream for application output.
CREATE OR REPLACE STREAM "DESTINATION_SQL_STREAM" (
  "passengers" INTEGER,
  "distance" DOUBLE,
  "ANOMALY_SCORE" DOUBLE);

-- Compute an anomaly score for each record in the input stream
-- using Random Cut Forest
CREATE OR REPLACE PUMP "STREAM_PUMP" AS
    INSERT INTO "TEMP STREAM"
    SELECT STREAM "passengers", "distance", ANOMALY_SCORE
    FROM TABLE (RANDOM_CUT_FOREST (
        CURSOR(SELECT STREAM * FROM "SOURCE_SQL_STREAM")))

-- Sort records by descending anomaly score, insert into output stream
CREATE OR REPLACE PUMP "OUTPUT_PUMP" AS
    INSERT INTO "DESTINATION_SQL_STREAM"
    SELECT STREAM * FROM "TEMP_STREAM"
    ORDER BY FLOOR("TEMP_STREAM".ROWTIME TO SECOND), ANOMALY_SCORE
DESC;

3、Azure IoT Edge, Azure Stream Analytic

下面的示例查询假设在2分钟的滑动窗口中以每秒120个事件的历史记录来统一输入每秒事件的速率。最终的SELECT语句提取并输出得分和异常状态，置信度为95％。

WITH AnomalyDetectionStep AS
(
    SELECT
        EVENTENQUEUEDUTCTIME AS time,
        CAST(temperature AS float) AS temp,
        AnomalyDetection_SpikeAndDip(CAST(temperature AS float), 95, 120, 'spikesanddips')
            OVER(LIMIT DURATION(second, 120)) AS SpikeAndDipScores
    FROM input
)
SELECT
    time,
    temp,
    CAST(GetRecordPropertyValue(SpikeAndDipScores, 'Score') AS float) AS
    SpikeAndDipScore,
    CAST(GetRecordPropertyValue(SpikeAndDipScores, 'IsAnomaly') AS bigint) AS
    IsSpikeAndDipAnomaly
INTO output
FROM AnomalyDetectionStep

4、SLS @ Alibaba Cloud

阿里云日志服务功能介绍

三、算法原理

3.0、无监督树形异常检测算法发展历程

2008 - Isolation Forest Published
2013 - Survey on outlier detection
2016 - RRCF published in JMLR
2016 - RRCF available on Amazon Kinesis
2018 - RRCF available on Hydroserving

3.1 2008年Isolate Forest原理

1. 单棵树的构建过程

iTree是一种随机二叉树，每个节点要么有两个孩子，要么就是叶子节点，每个节点包含一个属性q和一个划分值p。
具体的构建过程如下：

从原始训练集合X种无放回的抽取样本子集
划分样本子集，每次划分都从样本中随机选择一个属性q，再从该属性中随机选择一个划分的值p，该p值介于属性q的最大与最小值之间
根据2中的属性q与值p，划分当前样本子集，小于值p的样本作为当前节点的左孩子，大于p值的样本作为当前的右孩子
重复上述2，3步骤，递归构建每个节点的左、右孩子节点，知道满足终止条件为止，通常终止条件为所有节点均只包含一个样本或者多个相同的样本，或者树的深度达到了限定的高度

2. 构建参数的说明

有两个参数控制着模型的复杂度：

每棵树的样本子集大小，它控制着训练数据的大小，论文中的实验发现，当该值增加到一定程度后，IForest的辨识能力会变得可靠，但没有必要继续增加下去，因为这并不会带来准确率的提升，反而会影响计算时间和内存容量，论文实现发现该参数取256对于很多数据集已经足够；
集成的树的数量，也可以理解为对原始数据的采样的次数，它控制着模型的集成度，论文中描述取值100就可以了；

3. 如何衡量样本的异常值

4. 一些缺点

Contains all points
Every leaf contains one distinct point
Each node separates bounding box of it's points in two halves

3.2 2016年RRCF原理

0. 为何会引入RRCF算法？

数据是持续产生的，数据中的时间戳是一个重要因素，而这个维度却经常被大家忽略
数据的结构和形态是未知的，需要设计一个鲁棒性的算法来应对各种复杂的场景需求
iTree是针对候选数据，进行N次无放回的采样，通过对静态数据集进行划分而得到。若针对流式数据，每次都要针对最新的数据进行采样，再去构造数据集，运行算法，得到相应的结果；
在针对流式数据的异常检测场景中，缺少对序列中时序的关系的考虑，算法仅仅把当前的点当做孤立的点进行建模；

1. 针对数据流进行采样建模

针对第一个上述的第一个问题：

可以采用一些采样策略（蓄水池采样）能准确的当前的数据点是否参与异常建模；
同时指定一个时间窗口长度，当建模的数据过期后，应该从模型中剔除掉；

2. 算法中核心的几个操作

构造Robust Random Cut Tree操作
从一个Tree中删除某个样本
插入一个新的样本到树结构中

3. 如何衡量样本的异常值

引用论文中的一段话

Let 0 be a left decision and 1 be a right decision. Thus,for x ∈ S, we can write its path as a binary string in the same manner of the isolation forest, m(x). We can repeat this for all x ∈ S and arrive at a complete model description:M(S) = ⊕x∈Sm(x), the appending of all our m(x) together. We will consider the anomaly score of a point x to be the degree to which including it causes our model description to change if we include it or not,

形象化的描述如下所示

上图左侧表示构造出来的树的结构，其中x是我们待处理的样本点，有图表示将该样本点删除后，动态调整树结构的形态。其中$q_0,...,q_r$表示从树的根节点编码到a节点的描述串。

利用上述公式的描述，可以得到具体的衡量分数，但是如果将上述分数直接转换为异常值，还需要算法同学根据自己的场景进行合理的转换

3.3 流式改造 - 蓄水池采样算法

算法大致描述：给定一个数据流，数据流长度N很大，且N直到处理完所有数据之前都不可知，请问如何在只遍历一遍数据（O(N)）的情况下，能够随机选取出m个不重复的数据。
具体的伪代码描述

int[] reservoir = new int[m];

// init
for (int i = 0; i < reservoir.length; i++)
{
    reservoir[i] = dataStream[i];
}

for (int i = m; i < dataStream.length; i++)
{
    // 随机获得一个[0, i]内的随机整数
    int d = rand.nextInt(i + 1);
    // 如果随机整数落在[0, m-1]范围内，则替换蓄水池中的元素
    if (d < m)
    {
        reservoir[d] = dataStream[i];
    }
}

通过对数据流进行采样，可以较好的从数据流中等概率的进行采样，通过RRCF中提供的DELETE方法，可以将置换出模型的数据动态的删除掉，将新选择的样本数据动态的加入到已经有的树中去，进而得到对应的CODISP值。

3.4 并行调用的改造

该算法同Isolation Forest算法一样，非常适合并行构建，在此不做太多的赘述，推荐读者使用Python一个并行的软件包Joblib，能非常方便的帮助用户开发。
传送门：Joblib: running Python functions as pipeline jobs

四、算法实验结果

4.1 多维度的流量场景实验

实验数据说明：（时间戳，流量，平均请求延迟，访问次数），数据每5秒聚合一个点
该实验结果是使用全量的数据进行RRCF树的构造，在对结果中的全部叶子节点去获取对应的CODISP值，可视化如下结果，其中第一条曲线表示：网站每5秒的请求流量情况；第二条曲线表示：网站每5秒的平均请求延迟情况；第三条曲线表示：网站每5秒的访问次数情况；第四条曲线表示：每个点的CODISP值的大小；
在实际场景中，可以通过对CODISP值的判别来判定具体点是否是异常;
使用数据的前1024个点做为基础模型的数据，去构造100棵树；针对余下的数据点逐点输入算法中去，采用蓄水池采样的策略，动态的对树内部的有效点进行增删，实时得到最新点的CODISP值，绘制结果如下图所示;

4.2 如何将CODISP分数转换成异常值

理解下算法的本质：某个点的删除，导致整体树结构发生变化的程度（目前使用受影响程度正比于树种点的数量），对于一个确定容量的树来说，可以通过设置具体的阈值，来判别异常
可以针对CODISP使用K-Sigma算法，得到具体的上界异常值

4.3 如何对检测到的异常进行可解释性描述

参考文献

Sudipto Guha, Nina Mishra, Gourav Roy, and Okke Schrijvers. "Robust random cut forest based anomaly detection on streams." In International Conference on Machine Learning, pp. 2712-2721. 2016.
Byung-Hoon Park, George Ostrouchov, Nagiza F. Samatova, and Al Geist. "Reservoir-based random sampling with replacement from data stream." In Proceedings of the 2004 SIAM International Conference on Data Mining, pp. 492-496. Society for Industrial and Applied Mathematics, 2004.
http://proceedings.mlr.press/v48/guha16-supp.pdf
Implementation of the Robust Random Cut Forest Algorithm for anomaly detection on streams. https://klabum.github.io/rrcf/scoring-rctree.html
亚马逊中关于该算法的参数说明 https://docs.aws.amazon.com/zh_cn/kinesisanalytics/latest/sqlref/sqlrf-random-cut-forest-with-explanation.html
亚马逊中关于该算法的具体例子说明 https://docs.aws.amazon.com/zh_cn/kinesisanalytics/latest/dev/app-anomaly-detection.html

码农公寓

一、解决的问题

二、业内的解决方案

1、Numenta公司提出的HTM算法模型

2、Amazon Kinesis

2.1 应用场景

2.2 Kinesis - RRCF调用方式

3、Azure IoT Edge, Azure Stream Analytic

4、SLS @ Alibaba Cloud

三、算法原理

3.0、无监督树形异常检测算法发展历程

3.1 2008年Isolate Forest原理

1. 单棵树的构建过程

2. 构建参数的说明

3. 如何衡量样本的异常值

4. 一些缺点

3.2 2016年RRCF原理

0. 为何会引入RRCF算法？

1. 针对数据流进行采样建模

2. 算法中核心的几个操作

3. 如何衡量样本的异常值

3.3 流式改造 - 蓄水池采样算法

3.4 并行调用的改造

四、算法实验结果

4.1 多维度的流量场景实验

4.2 如何将CODISP分数转换成异常值

4.3 如何对检测到的异常进行可解释性描述

参考文献

相关文章