• +86-156-1535-0639
  • jianpengqi@126.com

Storm流分布式异常检测结果验证

  • QI-Jianpeng

在面向流数据异常检测的时候必要的一步就是对算法进行正确性验证. 从数据来看可以分为两类, 带标签的数据以及不带标签的数据. 带标签的数据可以使用算法结果与其进行比较, 计算Recall, Precision 或者Accuracy等. 但面对不带标签的数据, 在正确性评估上可能只能与现有的成熟的算法进行比较, 这里就会存在一个ground truth的问题, 所以尽量使用带标签的数据对算法进行验证.

本文基于距离的异常检测, 对算法结果与已有的算法进行评估.

在流式数据下进行异常检测会引入窗口(Sliding Window)的概念, 这里指的是time-based. 在一个窗口往前滑动的过程中会有新的数据加入以及旧数据过期, 这也就意味着针对一个点$p$来说, 当窗口长度为$w$时,$p$可能有$w$个状态. 为什么说可能有呢? 因为在一个窗口$W$内可能存在一些时间戳是不存在数据的, 当不存在数据的时间戳进入或者离开时间窗口时, $p$的状态是不受任何影响的. 当把一个数据文件的异常检测结果保存下来的时候你可能会发现明明保存的是每个点的id, 为什么异常结果文件会比源文件还要大? 如果异常点很多的时候, 每个异常点对应的可能是$w$个状态, 那就对应着$w$条记录. 所以异常结果文件变大.

在分布式环境下可能会遇到异常检测的结果重复的问题, 因为基于距离的异常检测除了在负载均衡打破了空间连续性外, 在边界点的处理上也会遇到一些问题. 这里的处理具有一定的技巧性, 不做赘述.

到这里, 我们开始异常检测的验证. 为了能够方便的验证结果, 我们需要输出的信息会包含有4个字段. window_start, window_end, id, timestamp. 其中window_start, window_end分别为当前时间窗口的开始结束时间, 当然, window刚开始还未填充满的那几个时刻不做过多研究. id为异常点id,timestamp为异常点本身自带的时间戳(Storm下采用Window计算时, withTimestamp()方法指定的时间戳).对于一条记录: 2, 6, 100, 3, 表示的是当时间窗口是从2 ~ 6时, 在时间戳为3时出现的id = 100的数据点为异常点. 因此这里额外隐含了一条信息, timestamp $\in$ [window_start, window_end]. 当然, 这个timestamp可有可无.这里是考虑如果是一个点在连续的运动的话, 那就含有了意义.

当我们对数据进行验证时, 就可以根据窗口开始结束的信息, 将每个窗口一一对应, 来计算相对于对比算法的Recall, Precision 或者Accuracy等(还是有个ground truth的问题, 对比算法不可能做到100%).