作者 | 追光者

研究 | 机器学习与时间序列

出品 | AI蜗牛车

一、Address

来自于ICML2016的一篇paper

Robust Random Cut Forest Based Anomaly Detection On Streams

• 论文地址：http://proceedings.mlr.press/v48/guha16.html

• 论文源码：https://github.com/kLabUM/rrcf

二、 Introduction

随着物联网和传感器的数据爆炸性增长，在大多数情况下，数据都是流式传输的，在这种场景下，输入流会存在增加，修改，更新等动态变化。此时，有两个核心问题：

（1）我们如何定义异常？

（2）我们使用什么样的数据结构来有效地检测动态数据流上的异常？

作者从模型复杂性的角度来看待这个问题，如果一个点的复杂性随着这个点的加入而显著增加，那么这个点就是一个异常。

三、Model

RRCF 由一组 RRCT(robust random cut tree)组成,一个 RRCT 由以下方式定义:

3.1 RRCF

RRCF 由一组 RRCT(robust random cut tree)组成,一个 RRCT 由以下方式定义:

1. Choose a random dimension proportional to , where

2. Choose Uniform

3. Let and and recurse on and .

3.2 定义异常

本文对异常的定义基于以下两个思路：

1. 一个异常现场通常很容易描述，例如一群戴着黑色帽子人群里的带红色帽子的人

2. 一个异常的存在会使得我们的注意力转移到这个新的观察上

所以，定义异常的一个基本任务是量化注意力的转移

给定一个样本S的树T (S)和一个点p，当包含点p的联合分布与排除点p的分布显著不同时，我们将其标记为异常，这就引出了本文所使用的异常的定义。

首先定义模型复杂度：

其中点 ， 为树T的深度（表示一个点所需的位数对应于它在树中的深度。）

然后定义位距离（位移）：

将点x的位位移或位移定义为所有其他点的模型复杂度的增加，即，对于集合Z，为了捕捉x引入的外部性，定义

作者把一个点x的异常分数视为包含它会导致模型改变的程度：

colloders：

举个例子，某个戴了红色帽子的人在一片黑色帽子的人群中属于异常点，而colloders就是红色帽子旁边的人戴着深红色（接近黑色）的人，这些人的存在会对识别红色（异常）存在一定干扰，在实际使用时,为了防止出现串谋者(colloders)的干扰,可以使用特定采样的一组点而不是一个点来定义异 常值，这样可以进一步增加算法的鲁棒性。

考虑到串谋者的影响，作者定义异常score的方法如下：

异常分数

CoDISP(Collusive Displacement):

3.2 核心操作

删除节点

插入节点

3.3 与孤立森林对比

上图为孤立森林的建树方法，孤立森林算法使用了与RRCF相似的方法，但是修改了要切割的维度为均匀随机选择的。孤立森林的优点是不同的维数是独立处理的，并且算法对不同维数的缩放是不变的。

但是在实际任务中，不同维度的相关性往往是未知的。更多区别可以在Experiments中体现

四、Experiments

作者进行了两类实验，第一个是使用合成数据：

上面的是孤立森林，下面的是CODISP。

在第一个明显变化点，CODISP是比孤立森林更早检测出来的。

第二个实验是使用了纽约出租车委员会的出租车乘客数据进行流计算实验

如果使用Shingle，那么Shingle的大小就很重要，因为太小的Shingle可能会在信号中捕捉到自然变化的噪声，并触发假警报。另一方面，过大的Shingle可能会增加找到警报所需的时间，或者完全错过警报。(Shingle可以简单理解成样本数量)

五、Conclusion

本文采用了一种基于模型的异常定义，它能够捕捉模型添加/删除一个点的差异效果。实验表明，这个算法在对抗报警疲劳和捕捉更多漏报异常方面有很大的前景。RRCF还可以帮助检测流中的变更点，一个变化点是时间t中的一个时刻，在时间t之前，数据分布为d1，在时间t之后，数据分布为d2，并且d1与d2完全不同随着时间的推移，通过维护一个sketch序列，可以比较两个sketch，以确定分布是否发生了变化（Delete操作）。

更多精彩内容（请点击图片进行阅读）

公众号：AI蜗牛车

保持谦逊、保持自律、保持进步

个人微信

备注：昵称+学校/公司+方向

如果没有备注不拉群！

拉你进AI蜗牛车交流群