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