时间序列异常检测 EGADS Surus iForest

时间序列异常检测

(原文链接:http://wurui.cc/tech/time-series-anomaly-detection/)

本文总结了我在时间序列异常算法方面的一些经验。读者需要对常规机械学习算法有一定的了解。希望本文能帮助有相关需求的工程师快速切入。

EGADS Java Library

EGADS (Extendible Generic Anomaly Detection System)(https://github.com/yahoo/egads)是Yahoo一个开源的大规模时间序列异常检测项目。它的框架主要由两个模块构成,一个是时间序列构造模块,另一个是异常检测模块。给定一段时间的离散值(构成一个序列),时间序列模块会学习这段序列的特征,并试图重新构建一个和原序列尽量接近的序列。结果和原序列一同送入异常检测模块,基于不同的算法(原则,阈值),异常点会被标记出来。

Time-series Modeling Module

时间序列构造模块提供了多种算法。简单介绍如下:

Olympic Model(Seasonal Naive)一个简单的窗口模型,对点Px的预测为点Px前n个值的Smoothed Average.

Exponential Smoothing Model 一个平滑模型,由简单的数列获得。ETS模型可以自动选择Single、Double、Triple里面匹配最好的输出。

Moving Average Model 也是平滑模型,点Px的预测值取邻近点的平均值。

Regression Models 一般是线性回归,特殊例子或者异常偏差特别大的时候有用。

Anomaly Detection Module

异常检测模块

ExtremeLowDensityModel 超低密度模型,很简单有效的密度模型。

AdaptiveKernelDensityChangePointDetector 拐点检测模型

KSigmaModel 经典K-sigma模型

DBScanModel(Density-Based Spatial Clustering of Applications with Noise)又是一个基于密度的模型,在空间中作聚类,如果目标序列可以比较好的分类的话会有不错的效果。

实践经验。

序列构造自动选优

不同类型的数据可能适合不同的模型。选择AutoForecastModel,程序会自动把所有TMM都跑一遍,并推选偏差值最小的模型送入异常检测模块。值得注意的是,这里自动选取的标准只关注了还原度,但还原度高并不直接代表能更好的查找异常,在使用本方法的时候要留意在心。

多数投票算法

不同的异常检测算法从不同的角度定义了异常。实践过程中我发现,单一异常算法并不能找出所有异常点,同时还会出现一系列的假阳性异常。使用Majority Voting,规定半数以上算法识别为异常的点才输出为结果,在实际数据中提供了远高于单一算法的准确度。

Surus

Surus(https://github.com/Netflix/Surus)是Netflix开源的一个项目,因为Netflix内部大量使用Pig和Hive,Surus主要的功能是提供RPCA的Pig/Hive封装。核心算法Robust PCA是Java实现的,可以单独调用。

Netflix首先对他们的问题定了一个基调。Profile是一个非常好的习惯,对决策者来说可以提供命中率,也就提高了团队效率。问题的特征定义如下:

高纬度。数据集纬度高,数据间相互交织,人工检测基本不可能。

最低加阳性。作为异常检测问题,我们不希望有过多的假阳性报警来干扰监控人员。

周期性。每小时/每天/每周/每月这样的周期性数据如果不妥善处理,某些周期性的行为可能误报为异常。实际数据中,每天固定时段的峰值数据相对于大部分采样点都可能被判定为异常,但实际为周期性正常现象。

数据并不是均匀分布的。像Netflix在两年中实现了高增长,算法需要足够健壮来处理非均匀分布的数据集(增长性数据是一个普遍现象,如长期来看的股市指数等)。

算法细节

Robust PCA是一个非常常见的主要成分提取算法。RPCA本质其实是一个矩阵分解算法。目标是将输入X分解为X=L+S+E。L代表了X的low rank approximation(低秩估计)。而低秩估计本质就是将矩阵中相关性强的行投影到更低维的线性空间,实现了一个降维平滑的功能,同时剔除了冗余信息,提取了矩阵特征。提取完主要成分L后,获得了剩下的稀疏矩阵S,和噪点E。

这里做异常检测的时候简单认为低秩矩阵L就能大部分还原输入序列。异常点的特征应该就表现在S或者E中。实际应用中可以把RPCA作为一个时间序列构造模型添加入EGADS中,用后者的异常检测模块提取异常。

Isolation Forest

上面两个项目使用了若干种类的异常检测算法。如基于模型的(统计模型,线性模型);基于距离的(K临近等聚类算法);基于密度模型的(Extreme Low Density Model)。隔离森林(Isolation Forest)跟他们都有比较明显的区别。论文代码(https://sourceforge.net/projects/iforest/?source=navbar)

在训练阶段,小样本抽样更利于获得优质的分类结果。

因为不用计算点与点直接的距离,计算时间大大优于各种基于距离的算法。

同样因为小样本抽样后迭代,时间、空间复杂度都可以维持在相当低的水平。

基于上一点,iForest有能力处理超高维,超大规模的数据。

iForest适用场景需要符合两个要求:1. 异常点非常少 2. 异常点的某些属性要跟正常点非常不同。

iForest是基于随机森林的算法。对异常的分类能力基于两个假设:

数据集中少数的异常点会形成少量的聚类。

异常点具有明显不同的属性,使他们很快在分类中被区分出来。正常点很难被分类,而存在于树的更深层。

上图横坐标表示了随机森林的迭代过程。选取一个异常点Xo和一个正常点Xi。纵轴代表了点Xo和Xi在迭代中被区分出时树深度的平均值。可以明显的看到,正常节点平均需要12次随机分类,而异常点只需要4次多就可以被区分出来。

上图展示了小规模随机抽样同样可以达到非常好的聚类效果。这在处理大规模数据的时候尤其有用,在多篇文章中,iForest因为这一特性被推荐为首选算法。实现方面有R,Java,Python,搜索一下就有。

BENCHMARKING ALGORITHMS FOR DETECTING ANOMALIES IN LARGE DATASETS

这篇论文(http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.188.6153)使用了比较常见,简单易得的算法,基于学术界认可的标准数据集,进行了一系列性能,准确度试验,希望得到异常检测这一问题的一个基准。

本文使用了以下几种算法,因为是调用的Weka,所以算是比较简单的试验。

K邻近

多层神经网络(Multi-layer Perceptron) 可以简单认为是一个复杂参数学习的分类器。

基于密度的聚类算法:LOF (Local Outlier Factor)

随机森林(random forest)

Isolation Forest

经过一系列试验,结论中推举了以下步骤:

如果是维度非常高的数据,用J48选Attribute。

用iForest预选异常点,标准为score > 0.50

把ANN,J48,RF作为一个组合再处理2步得到的异常点。

被较多算法标注为异常的点就认为有高可信度。

主要数据集

KDDCUP99(http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html)网络流数据。常用入侵检测数据,学术界大量使用。不过据说后来被证明不太可靠。

Amazon监控数据(https://github.com/numenta/NAB/tree/master/data)Amazon EC2性能检测的真实检测数据,放出的数据有真实异常,并且有人工标注。

内部威胁数据(https://www.cert.org/insider-threat/tools/index.cfm)CERT人造的内部威胁数据。人造的方法还是比较科学的,不过异常模式比较简单,知道答案倒推就很容易。不过要自己发现异常就需要比较大的工作量了。

原文发布于微信公众号 - 人工智能LeadAI(atleadai)

原文发表时间:2018-01-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

深度 | 从数据结构到Python实现:如何使用深度学习分析医学影像

选自Medium 作者:Taposh Dutta-Roy 机器之心编译 运用深度学习技术进行图像和视频分析,并将它们用于自动驾驶汽车、无人机等多种应用场景中已成...

83490
来自专栏用户2442861的专栏

循环神经网络——实现LSTM

网络回忆:在《循环神经网络——介绍》中提到循环神经网络用相同的方式处理每个时刻的数据。

24020
来自专栏智能算法

10 种机器学习算法的要点(附 Python 和 R 代码)

本文由 伯乐在线 - Agatha 翻译,唐尤华 校稿。 英文出处:SUNIL RAY。欢迎加入翻译组。 前言 谷歌董事长施密特曾说过:虽然谷歌的无人驾驶汽车和...

46950
来自专栏人工智能头条

揭秘Kaggle神器xgboost

23120
来自专栏AI科技大本营的专栏

多图|入门必看:万字长文带你轻松了解LSTM全貌

作者 | Edwin Chen 编译 | AI100 第一次接触长短期记忆神经网络(LSTM)时,我惊呆了。 原来,LSTM是神经网络的扩展,非常简单。深度学...

34670
来自专栏数据科学与人工智能

【算法】10 种机器学习算法要点

小编邀请您,先思考: 1 你熟悉那些机器学习算法? 2 你如何应用机器学习算法? 前言 谷歌董事长施密特曾说过:虽然谷歌的无人驾驶汽车和机器人受到了许多媒体关注...

38890
来自专栏AI科技评论

开发 | TOP5%Kaggler:如何在 Kaggle 首战中进入前 10%

Introduction Kaggle 是目前最大的 Data Scientist 聚集地。很多公司会拿出自家的数据并提供奖金,在 Kaggle 上组织数据竞赛...

59680
来自专栏语言、知识与人工智能

基于深度学习的FAQ问答系统

| 导语 问答系统是信息检索的一种高级形式,能够更加准确地理解用户用自然语言提出的问题,并通过检索语料库、知识图谱或问答知识库返回简洁、准确的匹配答案。相较于...

11.4K110
来自专栏崔庆才的专栏

自然语言处理全家福:纵览当前NLP中的任务、数据、模型与论文

组合范畴语法(CCG; Steedman, 2000)是一种高度词汇化的形式主义。Clark 和 Curran 2007 年提出的标准解析模型使用了超过 400...

87000
来自专栏Python中文社区

Python机器学习工具:Scikit-Learn介绍与实践

Scikit-learn 简介 官方的解释很简单: Machine Learning in Python, 用python来玩机器学习。 什么是机器学习 机...

22370

扫码关注云+社区

领取腾讯云代金券