一个通用时间序列的在线异常检测的简单算法

Question

我正在处理大量的时间序列数据。 这些时间序列基本上是每隔10分钟收集的网络测量，其中一些是周期性的（即带宽），而另一些则不是（即路由流量的数量）。

我需要一个简单的算法来进行在线“异常值检测”。基本上，我想在内存中（或者硬盘上）保存每个时间序列的整个历史数据，并且在实时场景中检测任何异常值（每次捕获新样本时）。 如何最好地实现这些结果？

我目前正在使用移动平均值以消除一些噪声，但是接下来该怎么做呢？像标准差、mad等简单方法对整个数据集并不起作用（我不能假设时间序列是稳定的），我希望有更“准确”的东西，理想情况下是一个黑盒子：

double outlier_detection(double* vector, double value);

其中vector是包含历史数据的双精度数组，返回值为新样本"value"的异常分数。

- Gianluca

---

你可能还想尝试在stats.stackexchange.com上问问 - 这是专门用于统计问题的StackOverflow。 - Matt Parker

目前已在http://stats.stackexchange.com/questions/1142发布了几个回答，针对一般时间序列的在线异常检测，提供了简单的算法。 - Rob Hyndman

Answer 1

这是一个庞大而复杂的主题，答案将取决于(a)您希望在这方面投入多少努力和(b)您希望您的异常检测有多有效。一种可能的方法是自适应滤波，通常用于噪声消除耳机等应用程序。您拥有一个过滤器，它不断适应输入信号，有效地将其滤波系数与信号源的假设短期模型相匹配，从而减少均方误差输出。这将给您一个低水平的输出信号（残差误差），除非当您得到一个异常值时，这将导致一个峰值，这将很容易检测（阈值）。如果您认真对待这种技术，请阅读有关自适应滤波、最小均方滤波器等的内容。

- Paul R

---

谢谢您的回复。这似乎是一个不错的方法，但如果信号表现出高季节性（即很多网络测量同时具有每日和每周模式，例如夜间与白天或周末与工作日之间的差异），那该怎么办？自适应滤波器能否对此进行建模？在我的理想世界中，我希望能够检测到发生在星期天早上的交通高峰，而同样的值在星期一可能完全正常。 - Gianluca

只要您的滤波器中有足够的术语来建模各种周期性，那么它应该可以正常工作 - 自适应滤波器将消除这些频率，只留下残余噪声。 - Paul R

再次感谢，我想尝试一种基于这个东西的算法。您知道是否有一些通用库可以在进行真正的实现之前对该方法进行初步模拟（这可能需要一些时间）吗？ - Gianluca

你可以在MATLAB中（或者像Octave这样的免费克隆版本）很快很容易地原型化这个项目。请参考http://www.mathworks.com/matlabcentral/fileexchange/3649-lms-algorithm-demo。 - Paul R

Answer 2

我建议采用以下方案，可以在一天左右实现：

训练

• 收集尽可能多的样本以存储在内存中
• 使用每个属性的标准差去除明显的异常值
• 计算并存储相关矩阵和每个属性的平均值
• 计算并存储所有样本的马氏距离

计算“异常程度”：

对于要了解其“异常程度”的单个样本：

• 从训练中检索均值、协方差矩阵和马氏距离
• 计算您的样本的马氏距离“d”
• 返回“d”所处的百分位数（使用来自训练的马氏距离）

那将是您的异常值得分：100％是极端异常值。

---

PS. 在计算马氏距离时，请使用相关矩阵，而不是协方差矩阵。如果样本测量值在单位和数量上变化，则这种方法更为健壮。

- Ytsen de Boer