Yahoo 大规模时列数据异常检测技术及其高性能可伸缩架构

本文是 Yahoo 在 ACM 国际会议上发布的一篇关于时序数据自动异常检测上的学术论文，对在智能监控尤其是趋势预测、异常数据监测和报警等方面的技术同学具有一定研究和参考价值，以下是中文翻译，部分内容进行了删改，附录是该论文的英文原文，方便读者查阅。由于笔者知识有限，内容翻译不恰当之处欢迎批评指正共同讨论。

作者介绍

彭冬 Andrew（微博 @AndrewPD，微信 justAstriver）

新浪微博广告业务部架构师，目前负责广告核心引擎基础架构、Hubble 系统、D+ 商业数据平台建设及基础架构团队管理工作。关注于计算广告、大数据、人工智能、高可用系统架构设计。 Innovation and Open, Technical,Extremely Perfect

关键词 : 智能监控 EGADS 故障检测 机器学习 Yahoo 趋势预测 模型

1. 摘要

本文介绍了大规模时序数据自动异常检测的通用和可扩展框架。能够在早期检测到系统异常，无论在维护用户数据一致性方面，还是在保护企业免受恶意攻击方面都发挥着非常关键的作用。用于异常检测的现有技术在可扩展性和易用性上都存在很大问题。我们在雅虎（EGADS）的系统设计了基于异常检测和预测模型构建的异常过滤层，用于准确地进行时序数据的异常检测。我们比较了我们的方法与其他异常检测系统对实时和合成数据的不同时间序列特征。EGADS 框架在精度和召回率上提高了 50%～60％。

2. 简介

虽然计算硬件和软件的快速发展已经极大提高了应用程序的可靠性，但是在大型集群中仍然存在大量的软件错误和硬件故障。系统要求 7*24 小时不间断运行，因此，对这些系统的持续监控就至关重要。从数据分析的角度来看，这意味着不间断地监控大量的时间序列数据，以便检测潜在的故障或异常现象。由于实际中的系统异常或者软件 BUG 可能会非常多，通过人工监控几乎是不可能的，因此非常有必要使用机器学习和数据挖掘技术进行自动化异常检测。

异常值本质上是一个数据点。通常，大多数应用程序中的数据是由一个或多个反映系统功能的程序产生的。当底层应用程序以不正常的方式运行时，它就会产生异常值。快速高效地发现这些异常值非常有价值，比如：入侵检测、信用卡欺诈、传感器事件、医疗诊断、执法等。

我们在雅虎的系统被称为 EGADS，它可以准确和可扩展地检测时间序列异常。 EGADS 将预测、异常检测和警报分为三个单独的组件，允许人员将自己的模型添加到任何组件中。本文重点介绍后两个组件。

EGADS 是首个灵活、准确且可扩展的异常检测综合系统。 EGADS 框架与异常检测基准数据已经一起开源，旨在帮助学者和行业合作开发新的异常检测模型。在雅虎，EGADS 每天被许多团队用于数百万次的时间序列异常检测工作。

整体架构

EGADS 框架由三个主要部分组成：时间序列建模模块（TMM）、异常检测模块（ADM）和报警模块（AM）。给定一个时间序列，TMM 组件模拟产生时间序列，由 ADM 和 AM 组件进行消费处理，分别计算误差并过滤不感兴趣的异常。这些组件在第 3 和 4 节中有详细描述。

EGADS 被构建为一个框架，可以轻松地集成到现有的监控基础设施中。在雅虎，我们内部的雅虎监控服务（YMS）每秒处理数百万个数据点。因此，对 YMS 进行可扩展、精准且自动化的异常检测至关重要。接下来我们将详细描述 YMS 的具体细节。

2.1 系统集成

EGADS 作为独立平台运行，可用作大型系统中的库。因此，设计 EGADS 和雅虎监控服务（YMS）之间的接口至关重要。 EGADS 与 YMS 的集成架构图如图 1 所示。

(点击放大图像)

图 1 EGADS-YMS 整体架构

此外，异常检测还需要几个支撑组件来驱动完成。首先，所有的异常检测模型都是离线批处理（batch）产生的，然后应用到实时环境（real time）。其中批处理由三个步骤组成：

• 监测数据（即监控的时间序列数据）批量存储在 Hadoop 集群上
• 批量模型生成器针对这些数据运行，并为目标时间序列构建模型
• 模型存储在模型数据库中

然后在线实时流使用这些存储的模型，具体步骤如下：

• 数据流入 Storm 进行流式处理
• 集群中的一个模块调用 EGADS ADM，根据存储在模型数据库中的模型来评估输入数据点
• 如果存在异常，则将其发送到由组合规则和其他包含特定逻辑组成的辅助规则流（见第 4 节）
• 根据规则，如果异常是警报事件，则生成事件，存储在状态数据库中，并转发到警报路由系统
• 警报路由系统应用路由配置规则将警报发送给相应的处理人员

2.2 可扩展性

EGADS 的监控需要每秒分析超过百万级数据点和亿级别时间序列。要求在 CPU 负载、I/O 和内存占用方面具有可扩展性，并且数据点的处理需要尽可能高效。这意味着需要预先计算尽可能多的模型。从磁盘读取模型是不切实际的，会降低性能，因此模型应该存储在内存中。另一方面，为了控制成本，模型应尽可能小。

异常检测算法

在本节中，我们给出了 EGADS 支持的异常检测算法。目前，EGADS 能够检测出三类异常：

(点击放大图像)

在以下章节中，我们给出了EGADS 当前用于检测上述异常类型的方法。

3.1 异常检测

检测异常值是许多监控应用中最重要的功能。EGADS 提供了两类用于检测输出的算法，本节对这两类算法进行了描述。

3.1.1 插件方法

EGADS 中异常值检测的第一类方法称为插件方法。为了模拟输入时间序列的正常行为，可以业务和时序数据的特点来插入大量的时间序列模型和预测模型（例如 ARIMA、指数平滑、Kalman 滤波、状态空间模型等）。这就是为什么我们将这个总体策略称为插件方法。应该注意的是，所有这些模型都在 EGADS 中用于时间序列预测，这是我们框架的另一个特征 ; 然而，由于本文的重点是异常检测，更多关于 EGADS 的建模和预测特征的细节我们不进行更深入的讨论。

(点击放大图像)

如果错误超出某些固定阈值，则会发出警报。这种简单的方法在某些情况下可能会起作用，但是对于大多数的方法来说，它不会是一个很好的策略，因为它不能捕获到错误的具体信息。

(点击放大图像)

通过对相对误差进行阈值处理，可以检测异常值，同时对所期望值的幅度进行归一化。虽然这些阈值确定了异常检测模块的敏感度，然而，很难确定异常检测的最佳度量。事实上，给定时间序列的最优度量的选择取决于时间序列的性质以及TMM 性能。例如，如果我们处理一个非常规则的时间序列，我们有一个准确的模型，使用预测误差进行异常检测可能就足够了，因为它预期是正态分布的。在其他情况下，最佳度量可能在预测误差和相对误差之间存在某种差异。因此，EGADS 默认跟踪一组偏差度量，使用系统的人可以创建自己的错误度量。在第4 节中描述的警报模块（AM）中使用这些错误度量以及其他功能（如时间序列特征）来了解用户的偏好并过滤不重要的异常。

3.1.2 基于分解的方法

EGADS 中第二类异常值检测方法是基于时间序列分解的思想，在时间序列分析中，通常将时间序列分解为：趋势、季节性和噪声三个要素。通过监测噪声分量，可以捕获异常值。更准确地说，如果点 Xt 的噪声分量的绝对值大于某个阈值，则可以认为 Xt 为异常值。

3.2 变点检测

在一些文献里有提到一种基于时间窗口的变点检测技术，在 EGADS 中，目前采用基于模型的方法。在这些方法中，时间序列的预期行为通过 3.1.1 节中提到的建模技术建模。我们结合 3.1.1 节中描述的插件方法来计算输入时间序列的残差序列（或模型预测的偏差）。然后我们对残差序列应用绝对变化点检测的方法来检测残差分布。我们使用内核密度估计（Kernel Density Estimation）、非参数估计残差分布和 Kullback-Leibler（KL 距离，常用来衡量两个概率分布的距离）来测量分布变化。

3.3 检测异常时间序列

(点击放大图像)

报警

异常检测的最终目标是产生准确和及时的警报。 EGADS 通过两阶段过程实现这一点，首先通过阈值选择产生一组候选异常，然后根据给定的规则过滤不相关的异常。

4.1 阈值选择

阈值选择的作用是根据异常检测模块（ADM）产生的偏差度量选择合适的阈值。目前，EGADS 基于以下两种阈值选择算法实现：

（a）Kσ 偏差

（b）密度分布

第一种方法是参数化的，并假定数据正态分布，有明确的平均值和标准偏差。依靠高斯分布，并基于“3sigma 规则”（即：其中 99.73％的样本位于平均值的三个标准偏差之内）。因此，根据 Kσ中的 K 值，可以确定在时间 t 观测样品的可能性。根据所需的敏感度，可以测量给定的样品是否在 K = 2 或 1 的所有样品的 95.45％或 68.27％之内。请注意，这里的假设是以我们的偏差度量是正态分布为前提的。 第二种方法是非参数的，对于偏差度量不是正态分布的情况是有用的。基本思想是找到偏差度量分布的低密度区域。一种方法是使用诸如局部离群因子（LOF）的算法。通过将对象的局部密度与其邻居的局部密度进行比较，可以识别具有相似密度的区域，以及具有比邻居密度明显更低的密度的点，这些点被认为是异常值。

4.2 过滤

表 1 EGADS 所使用的时序数据特征表

(点击放大图像)

图2 显示了样本时间序列的特征曲线。请注意，以dc 开始的指标是在时间序列上经过调整后（即删除趋势和季节性数据后）得到的。在第6.2 节中，我们将看看这些时间序列特征如何影响模型性能。

(点击放大图像)

图2：EGADS 提取的时间序列及其特征的一个示例

实验研究

6.1 数据

用于实验的数据集由 1:1 的合成数据和真实数据混合而成。我们创建了一个合成的时间序列生成工具，该工具已经随着框架和基准数据开源。使用该工具，通过指定长度、幅度、异常数、异常类型、异常大小、噪声水平、趋势和季节性来生成合成时间序列。真实数据集使用了雅虎会员登录数据 (YML)。合成和真实数据在时间序列都包含 3000 个数据点，YML 数据包含了 3 个月的数据点。除非另有说明，所有实验均以 1000 次随机选取的时间序列进行，结果取平均值。还要注意，合成和真实数据都有异常标签，方便测量精度和召回率。

6.2 建模实验

时间序列建模（由 EGADS 中的 TMM 组件捕获）是异常检测的基本部分。通常情况下，异常检测与底层时间序列模型一样好。由于大量的候选模型，模型选择变得至关重要，并且取决于时间序列特征和可用资源。在下面的实验中，我们展示了时间序列特征对模型性能的影响，并显示了精度，实验中使用的模型和误差度量分别参见表 2 和 3。

表 2 用于建模实验的模型列表

(点击放大图像)

表3 用于建模实验的指标列表

(点击放大图像)

6.2.1 时间序列特征和性能

为了证明时间序列特征对模型性能的影响，我们比较了不同模型的时间序列与不同特征的误差度量（见 4.2 节）。图 3 显示了时间序列特征在模型行为中起着重要作用。例如，季节性模式的 Olympic 模型在数据集上表现不佳，没有季节性和强劲趋势。 EGADS 能够跟踪历史时间序列特征和模型性能，使用这些历史信息，EGADS 选择由表 3 中描述的误差度量判断的最佳模型（给定时间序列特征）。实际上，基于数据特征进行模型选择比针对每个模型执行交叉验证要快得多。

(点击放大图像)

图3 具有不同特性的时间序列性能

6.2.2 时序模型的可扩展性

如第 2 节所述，时序模型需要高性能技术以支持大规模（例如每秒数百万点）数据流的实时计算，因此需要在模型大小、训练时间和准确性之间进行权衡。 这种权衡在图 4（a）和 4（b）中可以看出。 例如，从图中可以看出，季节性天性模型训练很快，但是具有较大的存储要求和较高的平均误差。 在雅虎，首先设定了资源和模型训练时间的目标，然后选择相应的模型。 换句话说，目标是在资源和模型建立时间限制下使得表 3 中的错误减到最小。

(点击放大图像)

图4 模型大小与训练时间的权衡

6.3 异常检测实验

在本节中，我们比较了开源系统与 EGADS，参考的开源系统如表 4 所示。

表 4 开源异常检测模型（系统）列表

(点击放大图像)

在图5 显示了对6.1 节中描述的数据的测试结果，比较方法采用：

(点击放大图像)

图5 异常模型在不同数据集上的表现（观察到在所有数据集上没有最好的单一模型）

结果可以看出，没有一个最佳的异常检测模型能适合所有业务场景，不同的算法需要结合检测不同类型的异常来确定。例如，Twitter 在数据集上表现最好，而ExtremeLowDensity 模型在上表现最好。但是，EGADS 的设计初衷是在用户对数据类型的时间序列和异常类型不了解的情况下，该系统能够优雅和稳健地处理数据中存在的各种异常现象。因此，EGADS 被构建为将一组异常检测模型组合成一个最佳框架的库。这些模型的异常被转发到过滤组件以进行精确的异常检测。

6.4 异常过滤实验

异常的重要性往往取决于实际应用场景。具体来说，一些用户可能对展示恶意攻击的时间序列行为感兴趣，而其他用户可能对收入有兴趣。

为了解决这个要求，过滤阶段扫描所有模型的所有异常，并使用分类为作为真正的模型。在 YM 用例的过滤阶段使用的模型是基于 AdBoost 的增强树模型。模型中使用的特征参见表 1。AdaBoost 的核心原理是在变化的数据上进行适合一系列 weak learners（例如，小决策树），最后的结果是通过组合加权多数表决产生的。图 6 中的实验结果表明，在滤波阶段使用不同的模型特征，得到比较好的精确率和召回率。

(点击放大图像)

图6：使用不同类型特征的过滤阶段的精度

结论

异常检测是许多具有故障应用的实时监控系统的核心部分, 比如检测、欺诈检测、网络入侵检测等等。尽管它至关重要，但实际上实施全自动异常检测系统是一项极具挑战性的任务，这些挑战通常导致解决方案不可扩展或并非高度专业化的，也导致了较高的误报率。

在本文中，我们介绍了EGADS——雅虎实现的通用异常检测系统，对不同的Yahoo 属性和数百万个时间序列进行自动监控和警报。正如我们在本文中所描述的，Hadoop 上的EGADS 并行架构以及Storm 的流处理机制使得它能够在雅虎的数百万个时序数据集上执行实时异常检测。此外，EGADS 采用不同的时间序列建模和异常检测算法来处理不同的监控场景。通过将这一组算法与机器学习机制结合到警报模块中，EGADS 能自动适应对用户重要的异常检测用例。所有这些功能都有效地创建了一个功能强大的异常检测框架，它是通用且可扩展的。我们对真实数据集和综合数据集的展示实验表明，与其竞争对手的解决方案相比，我们的框架具有优越的适用性。

EGADS 的设计本质上是可扩展的，它为向系统插入新的模型和算法提供了一种简单的机制。我们的框架及其所有数据集都已经开源。

原文地址： Generic and Scalable Framework for Automated Time-series Anomaly Detection

感谢蔡芳芳对本文的审校。

给InfoQ 中文站投稿或者参与内容翻译工作，请邮件至 editors@cn.infoq.com 。也欢迎大家通过新浪微博（ @InfoQ ， @丁晓昀），微信（微信号： InfoQChina ）关注我们。