时间序列异常检测 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 条评论
登录 后参与评论

相关文章

来自专栏CreateAMind

变分自编码器(Variational Autoencoder, VAE)通俗教程,细节、基础、符号解释很齐全

1143
来自专栏CreateAMind

变分自编码器(Variational Autoencoder, VAE)通俗教程,细节、基础、符号解释很齐全

现在有一个数据集DX(dataset, 也可以叫datapoints),每个数据也称为数据点。

803
来自专栏机器之心

学界 | ReQuest: 使用问答数据产生实体关系抽取的间接监督

选自 arXiv 机器之心编译 参与:Nurhachu Null、李泽南 在这篇伊利诺伊大学、南加州大学与上海交大合作的 WSDM 2018 论文中,研究人员提...

33411
来自专栏AI科技评论

学界 | 清华大学自动化系张长水教授:神经网络模型的结构优化

AI科技评论按:3月4日,中国人工智能学会AIDL第二期【人工智能前沿讲习班】在北京中科院自动化所举行,本期主题为【机器学习前沿】,由周志华教授担任学术主任,前...

3579
来自专栏机器学习之旅

应用:多算法识别撞库刷券等异常用户

在运营业务中,绝大多数公司会面临恶意注册,恶意刷接口,恶意刷券等流量问题,此类问题的常规解决方案都是拍定单位时间内的ip访问上限次数、qps上限次数等等,会存在...

822
来自专栏技术点滴

多柱汉诺塔最优算法设计探究

多柱汉诺塔最优算法设计探究 引言 汉诺塔算法一直是算法设计科目的最具代表性的研究问题,本文关注于如何设计多柱汉诺塔最优算法的探究。最简单的汉诺塔是三个柱子(A、...

2279
来自专栏企鹅号快讯

伯克利人工智能研究:针对深度神经网络的物理对抗例子

AiTechYun 编辑:Yining ? 深度神经网络(DNNs)在各种应用领域都取得了巨大的进展,包括图像处理、文本分析和语音识别。深度神经网络也被作为许多...

2027
来自专栏专知

【论文笔记】基于实体、属性和关系的知识表示学习

1443
来自专栏人工智能头条

优秀的排序算法如何成就了伟大的机器学习技术(视频+代码)

【导读】在机器学习中,支持向量机(SVM)算法是针对二分类任务设计的,可以分析数据,识别模式,用于分类和回归分析。训练算法构建一个模型,将新示例分配给一个类别或...

722
来自专栏悦思悦读

计算机是怎么理解人类语言的?

让计算机理解人类语言 “教”计算机理解人类的自然语言这部分工作,称作自然语言理解(Natural Language Understanding / NLU)。 ...

3538

扫码关注云+社区