基于数据流的异常检测:Robust Random Cut Forest-阿里云开发者社区

开发者社区> 阿里云存储服务> 正文
登录阅读全文

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

简介: 一、解决的问题 数据是实时产生的,对数据进行批处理所花费的成本太高了,数据产生的价值被低估 在高维数据下,如何能发现异常的维度? If my time-series data with 30 features yields an unusually high anomaly score.

一、解决的问题

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

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

image

  • 下面的示例查询假设在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

image

三、算法原理

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。
具体的构建过程如下:

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

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

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

image

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操作
    image
  • 从一个Tree中删除某个样本
    image
  • 插入一个新的样本到树结构中
    image
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,

  • 形象化的描述如下所示
    image

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

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

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值的判别来判定具体点是否是异常;
    image
  • 使用数据的前1024个点做为基础模型的数据,去构造100棵树;针对余下的数据点逐点输入算法中去,采用蓄水池采样的策略,动态的对树内部的有效点进行增删,实时得到最新点的CODISP值,绘制结果如下图所示;
    image

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

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

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

  • 该部分比较复杂,请等下一篇文章的分享

参考文献

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:

阿里云存储基于飞天盘古2.0分布式存储系统,产品多种多样,充分满足用户数据存储和迁移上云需求。

官方博客
存储产品
客户案例