时间序列异常检测的那些事

近半年工作, 一大部分时间在探索监控报警的智能降噪. 用这篇博客整理个人点点滴滴的思考, 希望可以不断的持续更新..

背景介绍

监控的重要性不言而喻, 它就相当于 SRE 的眼睛. 但由于监控系统静态规则的局限性, 经常会产生一些误报, e.g.冲高回落, 小流量剧烈波动. 轻则形成针对人的「DDOS攻击」, 重则导致真正的故障被忽略(狼来了的故事, 对报警的麻木). 所以如何利用算法自动识别噪音, 已成为当务之急, 并且会大大降低人肉处理报警的成本, 为公司节省成本.

准确率量化

个人认为算法的效果量化是最为关键的一步, 故提到最开头. 就像优化程序的性能一样, 不做 profile, 像个无头苍蝇一样去尝试, 肯定是无疾而返. 而效果的量化又分为 人工标记 + 回归测试:

1) 人工标记

在报警详情页底部会有一个立即处理的按钮, 点击后处理的页面就会像支付宝收银台一样咻的一下弹出来, 供人工标记噪音还是异常, 并同时提供关闭转发报警和关闭报警的功能.

2) 回归测试

当标记的数据正负样本不平衡的情况下,准确率这个评价指标有一定的缺陷. 举个极端的例子: 若标记的数据样本中95个为噪音, 5个为异常, 算法自己判断所有报警为噪音, 最后的准确率为95%. 但当一个故障异常真的发生时, 报警被判断为噪音是无法接受的.

所以引入Precision, Recall和F-Score的概念, 也就是说我们对 Recall 的要求是非常高的, 情愿发出100次警报,把其中5次异常都预测正确了, 也不要只识别正确其他95次噪音.

画个图: 下图中正方形代表所有告警, 左半部分代表人工标记为异常的告警, 右半部分反之(噪音). 而中间的圆圈代表算法识别正确的结果, precision 和 recall 就跃然纸上了 XD:
UNADJUSTEDNONRAW_thumb_5d09

举个栗子:
标记样本: 90个为噪音, 10个为异常.
算法结果: 5个为异常(判断正确), 95个为噪音

1
2
3
4
5
6
# 1. 准确率:   
accuracy = (5 + 90) / 100 = 95%
# 2. F Score:
precision = 5 / 5 = 100%
recall = 5 / 10 = 50%
f1 = 2 * 100% * 50% / (100% + 50%) = 66%

整体流程

第一步: 数据聚合

由于一些监控业务量过小, 导致波动很大, 所以在配置监控时就会设置 N 分钟的聚合, e.g. 总量 最近10分钟求和与上10分钟求和的环比下跌巴拉巴拉. 也是在牺牲报警实效性(一定的延迟)的情况下, 获取更加平滑的数据的一种策略.

所以在收到报警第一步, 就是对数据 根据配置的 N 分钟做聚合操作. 一开始是自己写了一个聚合的函数, 后来发现 pandas 有对应很优雅的函数(resample), 分享一下:

1
2
3
# 按时间聚合:
df = df.set_index('ds')
df = df.resample('30T', level=0, label='right', closed='right').sum()

第二步: 基线算法:

说明一下, 下文异常检测的场景, 更多是实时检测最新一个点的数据(聚合后)是否异常.

环比

对于现实中绝大部分的异常或故障, 最直观的表现就是突然的下跌(请求量, 成功量), 所以根据数据环比生成基线, 并检测异常是一种最简单也是最有效的策略.

1) 移动平均/加权移动平均/指数加权移动平均: 因为监控数据最大的一个特性就是有序, 所以理论上当前时刻的点与越靠近它的点关联越大. 指数加权移动平均(EWMA)就是这个特性的最佳实践, 而且这个公式真的是太优雅了:

1
2
3
4
5
6
7
8
EWMA(1) = p(1)  // 有时也会取前若干值的平均值。α越小时EWMA(1)的取值越重要。

EWMA(i) = α * p(i) + (1-α) * EWMA(i – 1) //α是一个0-1间的小数,称为smoothing factor.
如果α = 0.2, l = [p(1), p(2), p(3), p(4)]
EWMA(1) = p(1)EWMA(i) = 0.2 * p4 + 0.8 * (0.2*p3 + 0.8 * (0.2 * p3 + 0.8 * p4))= 0.2(p4 + 0.8*p3 + 0.8*0.8*p2 + 0.8*0.8*0.8*p1)= 0.2(p4 + 0.8^1*p3 + 0.8^2*p2 + 0.8^3*p1)
所以为什么叫做指数加权移动平均!! 而且系数α越大, 越靠近当前时间的点, 权重越大, 曲线的平稳性越差.

(ps. 这个公式真的太优雅了)

但在应用的过程中也发现一定的缺点: 上升下降福度大的曲线, 即使是指数加权移动平均拟合较差, 会出现一定延迟:
(暂时没有图, 自己脑补一下吧)

根本原因是之前(moving average和EWMA), 我们假设相邻两个点的趋势(Δy/Δx)是一样的, 但现实往往不是这样的, 所以前人发明了一个东西叫做 Double EWMA, 开始既考虑量(level), 也考虑趋势(trend). 公式还是一贯的简洁优雅:

但是.. 聪明的你一细想, 数据都是具有周期性的, 既然已经考虑了量(level)和趋势(trend), 是否可以把过去14天, 每天这个点的周期数据(seasonal)也考虑进去呢?

这个东西叫做 Triple EWMA, 其实就是大名鼎鼎的 Holt-Winters Method! 但这已经不仅仅是环比了, 是环比+同比的综合决策, 所以留个悬念, 留到第三部分介绍.

2) 曲线拟合 - 多项式回归(polynomial regression): 最近在学吴恩达的机器学习课程, 看到 linear regression 的时候, 灵机一动, 这不是完全为环比基线而生的, 具体不展开了, 只能说效果还是挺不错的.

同比

很有趣的一个事实: 就算是小众业务的流量, 每分钟一二十的请求量, 每天的趋势和量级几乎是一致的: 24h的规律, 白天上涨, 晚上下跌. 所以自创的一种同比算法: 当今日与历史趋势一致时(余弦相似性), 平移历史数据作为今日的基线.

环比 + 同比

外卖订单量预测异常报警模型实践 那篇文章给我的最大启发是异常检测可以将数据抽象为一个二维的矩阵, 去检测右下角的那个点是否为异常:

上文提到的 Triple EWMA(Holt-Winters Method), 就是对这个抽象模型的最佳实践(level+trend+seasonal):

Facebook 开源了一个周期性异常检测的开源库, 叫做 prophet, 我实验了一下, 还是挺友好的(下图为真实监控数据, 一月八号为预测):

30 min 聚合后的效果:

第三步: 阈值算法

静态阈值明显不合理, 需要根据历史振幅区间(选取3-sigma去除异常点后的最大值和最小值)生成阈值.

第四步: 汇总结果

投票者的模式: 只要大于或等于两个结果判断为噪音, 就认为此报警为噪音.

Reference:

感谢这些让我受启发的好文章:

  1. https://grisha.org/blog/2016/01/29/triple-exponential-smoothing-forecasting/
  2. https://tech.meituan.com/2017/04/21/order-holtwinter.html
  3. http://facebook.github.io/prophet/