AAAI 2020: 时序转化为图用于可解释可推理的异常检测-阿里云开发者社区

开发者社区> 笃林> 正文

AAAI 2020: 时序转化为图用于可解释可推理的异常检测

简介: Time2Graph: Revisting Time Series Modeling with Dynamic Shapelets 原文地址 整体导读 文章提出了带有时间意识的Shapelet,除了可以挖掘时序中的异常状态之外,可以自动感知异常状态所在时间位置上的敏感度; 文章尝试捕捉不同Shapelet之间的关系,提出了通过图结构(Graph)对这种关系进行表达的方法,在挖掘异常变化轨迹的同时也具备良好的可解释性。
+关注继续查看

motiv.jpg

Time2Graph: Revisting Time Series Modeling with Dynamic Shapelets

原文地址

整体导读

  • 文章提出了带有时间意识的Shapelet,除了可以挖掘时序中的异常状态之外,可以自动感知异常状态所在时间位置上的敏感度;
  • 文章尝试捕捉不同Shapelet之间的关系,提出了通过图结构(Graph)对这种关系进行表达的方法,在挖掘异常变化轨迹的同时也具备良好的可解释性。文章发表在人工智能领域顶级会议 AAAI 2020

时序建模中的挑战

时间序列建模旨在发现数据中的时空依赖关系,学术界对此有广泛研究,例如异常检测[2],语音识别[3]等。这里的关键问题是如何提取时间序列中代表性的特征。以前的工作很大一部分从经典的特征工程和表示学习入手,这些方法具有很好的可解释性,但主要依靠人的经验,在复杂的场景下很难做到通用化。近年来随着深度学习的发展,许多工作开始尝试一些复杂的模型方法来自动的挖掘特征。然而,尽管这些方法取得了良好的效果[4,5],但由于模型的复杂度高以及难以对结果很好的解释,许多方法不能很好地满足实际工业落地的需求。
基于以上背景为出发,该文尝试通过Shapelet[6], 一种可自动挖掘具有代表特征的时序子序列的方法出发,通过分析不同Shapelet之间的关系,构建Graph进行表示,提供一种可推理可解释且具有良好表现的时序模型。

动机:动态的Shapelet

Shapelet,代表一类可以在分类场景中提供直接的解释性和见解的时间序列子序列[6],并且基于Shapelet的模型在各种研究中都被证明是有前景的[7,8,9]。
截屏2020-05-13 下午2.59.42.png
上图展现了一个Shapelet的案例。每一个Shapelet(或理解为子序列波形)会在整个时序中找到最匹配的位置,以及匹配程度。现有的工作主要着眼于静态的分析Shapelet。但是,在现实世界中,Shapelet通常是动态的,这体现在两个方面:

  • 首先,出现在不同时间段的同一个Shapelet可能会产生不同的影响。例如,在检测到窃电用户的场景下,夏季或冬季的低电耗比春季更可疑,因为制冷或供暖设备的使用使得用电量应该更高。
  • 其次,确定Shapelet的演化方式对于全面理解时间序列至关重要。实际上,在特定时间具有较小值的Shapelet很难将窃电用户与确实消耗少量电的普通用户区分开。一种替代方法是识别曾经具有高电耗的Shapelet,但突然消耗很少的用户。换句话说,这里的一个重要线索是Shapelet如何随时间演变。

该文章将能够反映其在不同时间片上的代表性的时序子序列称为具有时间意识的Shapelet(Time-aware Shapelet)。此外,为了深入挖掘Shapelet的动态性和相关性,文章提出了一种新颖的方法,通过提取具有时间感知的Shapelet并构建Shapelet演化图来学习时间序列的表示,具体的可以参考发表在 AAAI 2020 的全文[1]。

本文开始展示的图中显示了一个来自真实用电记录的具体示例,它可以更好地展现该文章构建图的动机:图a显示了窃电用户在一年中的用电情况:1月到5月是没被抓时的用电曲线,之后是被抓后正常的用电情况。文章给每个月分配了最有代表性的Shapelet,并在图b中显示了两个有意思的Shapelet(#72和#67),以及它们的时间意识因素,其中深色区域表示Shapelet相对于浅色区域更具区分性。Shapelet演变图如图c所示,说明了Shapelet在正常情况下如何从一个转移到另一个:对于正常的用电量记录,其Shapelet的过渡有一条清晰的路径(#90→#67→# 85)。但是,对于异常数据,他们走一条不明显的路径(#85→#72→#7),这表明Shapelet转移路径的连通性可以为检测异常时间序列提供了参考标准。最后,文章将学习到的Shapelet和时间序列表示的问题转化为图嵌入问题,并用图算法进行解决。

捕捉具有时间意识的Shapelet

正式地,一个Shaplet 是代表某个类别的时序片段。更确切地说,它可以通过某些特定的指标,将时序分成两个较小的集合,一个接近而另一个远离,例如对于时间序列分类任务,可以将正样本和负样本放入不同的组中,具体可以形式化为

这里表示相对于特定组的距离,函数接受两个有限集作为输入,返回一个标量值以指示这两个集合有多远,它可以是信息增益或集合上的一些不相似性度量,即KL散度。

为了捕获Shapelet 的动态性,文章定义了两个因素来定量测量Shapelet在不同水平上的时序影响。具体来说,文章介绍一个局部因素来表示特定Shapelet的第n个元素的内部重要性。之后,Shapelet 与时序片段之间的距离可以被重新定义为

这里指的是DTW距离的最佳对齐。另一方面,在全局范围内,文章旨在衡量跨段的时间效应对Shapelet的判别力的影响。直觉上Shapelet在不同的时间步长可能代表完全不同的含义,这里可以直接通过添加段级权重来测量此类偏差。正式地,文章里设定了一个全局因素捕获跨段影响,然后Shapelet 与时序之间的距离可以写为

然后给定一个分类任务,这里可以建立一套监督学习方法,以选择最重要的具有时间意识的Shapelet,并可以为每一个Shapelet学习其相应的时间因素。特别地,这里有一个从所有子序列中选择出的作为shapelet候选者的片段池,以及一组带标签的时间序列 。对于每个候选者,都有以下目标函数:

在分别从Shapelet候选者那里学习了时序因素之后,文章选择损失最小的前K个shapelet作为最终的具有时间意识的Shapelet。

构建Shapelet演化图

Shapelet 演化图是有向加权图,其中由K个顶点所组成,每个顶点表示一个shapelet,每个有向边 与其权重,表示在相同的时间序列中,shapelet 跟着另一个shapelet 的出现概率。这里的关键思想是,图中的路径可以自然反映出shapelet的演变及其过渡模式,然后可以将图嵌入算法应用于学习shapelet以及时间序列表示。
文章首先分配每个时序片段到距离最近的几个Shapelets。详细地说,这里将shapelet的赋值概率标准化为

这里有

的预定义约束,。然后,对于每个对,文章从shapelet创建加权边,并通过权重合并所有的重复边。最后,将从每个节点获得的边缘权重归一化为1,这自然会解释每对节点之间的边缘权重。

时序表示学习

最后,文章对如上构造的Shapelet演化图来学习Shaplet和给定时间序列的表示。首先采用现有的图形嵌入算法DeepWalk[10]来获得顶点(shapelet)的表示向量,然后对于在时间序列中的每个片段,将其分配到不同的shapelet及其权重。最后连接或聚合所有这些嵌入向量以获得原始时间序列的表示向量。然后可以将时间序列嵌入应用于各种下行任务,请参考本文的实验部分[1]。

评价结果

文章对来自UCR-Archive [11]的三个公共基准数据集,和来自中国国家电网和中国电信的两个真实世界数据集进行时间序列分类任务。实验结果如下表所示:
exp.jpg
文章还进行了广泛的消融实验和观察研究,以验证其提出的框架。在这里,文章在不同的时间步上构建了Shapelet演化图,以更深入地了解shapelet动态演变,如下图所示。它显示了两个图表,一个表示一月,另一个表示七月。在1月,Shapelet#45具有较大的输入/输出度,并且在1月和2月(深色区域)突出显示了其对应的时间意识分数。这表明45号Shapelet很可能在年初开始成为一种常见模式。至于7月份,Shapelet#45不再像1月份那样重要。同时,Shapelet#42(在1月几乎是一个孤立点)在7月变得非常重要。尽管在构造Shapelet演化图时没有明确考虑季节性信息,但包含的时机因素意味着它们已被纳入图生成过程中。
vis.jpg

Reference

[1] Cheng, Z; Yang, Y; Wang, W; Hu, W; Zhuang, Y and Song, G, 2020, Time2Graph: Revisiting Time Series Modeling with Dynamic Shapelets, In AAAI, 2020
[2] Chandola V, Banerjee A, Kumar V, et al. Anomaly detection: A survey[J]. ACM Computing Surveys, 2009, 41(3).
[3] Shimodaira, H.; Noma, K.-i.; Nakai, M.; and Sagayama, S. 2002. Dynamic time-alignment kernel in support vector machine. In _NIPS’02_, 921–928.
[4] Malhotra, P.; Ramakrishnan, A.; Anand, G.; Vig, L.; Agar- wal, P.; and Shroff, G. 2016. Lstm-based encoder- decoder for multi-sensor anomaly detection. _arXiv preprint arXiv:1607.00148_.
[5] Johnson, M.; Duvenaud, D. K.; Wiltschko, A.; Adams, R. P.; and Datta, S. R. 2016. Composing graphical models with neu- ral networks for structured representations and fast inference. In _NIPS’16_, 2946–2954.
[6] Ye, L., and Keogh, E. 2011. Time series shapelets: a novel technique that allows accurate, interpretable and fast classifi- cation. DMKD. 22(1):149–182.
[7] Bostrom, A., and Bagnall, A. 2017. Binary shapelet trans- form for multiclass time series classification. In TLSD- KCS’17. 24–46.
[8] Hills, J.; Lines, J.; Baranauskas, E.; Mapp, J.; and Bagnall, A. 2014. Classification of time series by shapelet transformation. DMKD. 28(4):851–881
[9] Lines, J.; Davis, L. M.; Hills, J.; and Bagnall, A. 2012. A shapelet transform for time series classification. In _KDD’12_, 289–297.
[10] Perozzi, B.; Al-Rfou, R.; and Skiena, S. 2014. Deepwalk: Online learning of social representations. In _KDD_, 701–710.
[11] Dau, H. A.; Keogh, E.; Kamgar, K.; Yeh, C.-C. M.; Zhu, Y.; Gharghabi, S.; Ratanamahatana, C. A.; Yanping; Hu, B.; Begum, N.; Bagnall, A.; Mueen, A.; and Batista, G. 2018. The ucr time series classification archive. https://www.cs.ucr.edu/~eamonn/time_series_data_2018/.

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Kafka+Flink 实现准实时异常检测系统
异常检测可以定义为“基于行动者(人或机器)的行为是否正常作出决策”,这项技术可以应用于非常多的行业中,比如金融场景中做交易检测、贷款检测;工业场景中做生产线预警;安防场景做入侵检测等等。 根据业务要求的不同,流计算在其中扮演着不同的角色:既可以做在线的欺诈检测,也可以做决策后近实时的结果分析、全局预警与规则调整等。
2650 0
【转】mysql的cardinality异常,导致索引不可用
 转自:http://ourmysql.com/archives/1343    前段时间,一大早上,就收到报警,警告php-fpm进程的数量超过阈值。最终发现是一条sql没用到索引,导致执行数据库查询慢了,最终导致php-fpm进程数增加。
536 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
4480 0
【监控杂谈之异常检测】什么是异常
# 写在系列开头 集团在异常检测方面做了很多积淀,本系列将开始总结一些常见的问题以及解决办法,为后来人或者感兴趣的人快速上手,权当抛砖引玉,如有兴趣或者问题可以留言或@冷愁 本章作为整体概述,站在运维的角度、日常应急处理的视角,描述现有遇到的问题,在后续的篇章中会针对每一个遇到的问题提供响应的解决方案 ## 什么是异常检测 在开始之前,我们需要聊聊什么是异常检测。 引用维
5957 0
使用OpenApi弹性释放和设置云服务器ECS释放
云服务器ECS的一个重要特性就是按需创建资源。您可以在业务高峰期按需弹性的自定义规则进行资源创建,在完成业务计算的时候释放资源。本篇将提供几个Tips帮助您更加容易和自动化的完成云服务器的释放和弹性设置。
7757 0
kylin_异常_01_java.io.FileNotFoundException: /developer/apache-kylin-2.3.0-bin/tomcat/conf/.keystore
一、异常现象 kylin安装完,启动后,控制正常,kylin后台也能正常访问。但是去看kylin的日志,却发现报错了: SEVERE: Failed to load keystore type JKS with path conf/.
2371 0
准实时异常检测系统
本文为您介绍利用实时计算设计准实时(延迟在100ms以内)异常检测系统。 背景介绍 比如一家银行要做一个实时的交易检测,判断每笔交易是否是正常交易:如果用户的用户名和密码被盗取,系统能够在盗取者发起交易的瞬间检测到风险来决定是否冻结这笔交易。
4322 0
+关注
5
文章
0
问答
来源圈子
更多
阿里云存储基于飞天盘古2.0分布式存储系统,产品包括对象存储OSS、块存储Block Storage、共享文件存储NAS、表格存储、日志存储与分析、归档存储及混合云存储等,充分满足用户数据存储和迁移上云需求,连续三年跻身全球云存储魔力象限四强。
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载