Shapelet : 一种象形化的时间序列特征提取方法

对时间序列的分析涉及生产生活中的方方面面，像监控告警、股票分析、营销预测等等，很多场景中，我们都有及时掌握海量时序数据中特征，快速决策的需求。传统的统计分析方法能展示时序上宏观的数理信息，然而其趋势的变化（或者说是曲线的走势）才更能说明一些问题，挖掘更多重要直观的价值出来。

2009年，来自加州大学河滨分校的 Eamonn Keogh 教授和他的学生 叶乐翔 在数据挖掘顶级会议KDD上发表了一篇论文《Time Series Shapelets: A New Primitive for Data Mining》，首次提出了时序数据中的 Shapelet 的概念。他们受树叶轮廓的启发，借鉴象形文字的思想，提出了一种描述时序子序列形态的方法，打开了时间序列数据挖掘的新方向。

Eamonn Keogh

加州大学河滨分校的 Eamonn Keogh 教授是时间序列领域的顶级大牛，从事时间序列领域相关研究20多年，谷歌学术显示其学术成果引用量5w+，h-index 100+，发表了诸如 SAX / Shapelet / DTW / Matrix Profile 等影响时间序列发展方向的著名成果。创立了UCR 时间序列国际公开数据集，至今仍是做时序实验必跑的参考数据集之一。更多信息参访Eamonn教授的主页：

http://www.cs.ucr.edu/~eamonn/

概述

顾名思义，Shapelet可以拆成Shape与let，Shape是形状，-let表示“小”的后缀，Shapelet即表示时间序列的“小形状”，即一个子序列。这个子序列是这段时间序列数据中一个特别的子序列，其能表达时序数据中最显著的特点（显然，shapelet和趋势，周期分量一样，也是时序数据本身的一种特别的分量），其提出主要是为了解决早期使用KNN进行时间序列分类的一些问题。

时间序列分类中，knn的思路很简单，一条样本的m个时间步的数据就是这条样本的m个特征，然后使用knn来进行分类即可。然而KNN用于时间序列分类会有两个问题：

1. 计算开销大
2. 可解释性差

因此，Shapelet的设计思路则非常简单直观，不仅降低了计算开销，并且可解释性很好。具体的，文中给了一个例子：

从上图可以看到，shapelet是蓝色曲线中标红的部分，即为左边这个叶子对应的时序数据最显著的特点，这里可以直接只用这段数据来代替全量的序列数据，然后再进行KNN的分类算法。

大荨麻与荨麻叶马鞭草通过shapelet进行区别

上图所展示的两种叶子整体形状相似，如果从全局的角度不易区分。若只关注叶柄部分，shapelet帮助提出了钝角与直角的区别，使得的分类大大简化，理解也更容易。

将叶子的轮廓转化为一段时序数据（一维数据），然后用这段子序列在长时序中进行匹配，进而通过不同叶子（具有明确类型标识的外物）来对时序进行分类，这样的方法避免了海量数据复杂的KNN匹配搜寻，极大降低了计算开销，同时让分类具有可解释性，便于理解。

除此之外，基于shapelet对时序数据进行分类能够很好的提高时序数据的性能。如上图，两个叶子对应的时序数据有很多个时间步都是类似的，那么基于距离的计算很明显会收到大部分相似的时间点对应的数据的影响，但是现在我们提取出其中最明显的部分，那么模型能够更加关注不同时序样本之间显著的不同。

算法模型

上面提到，Shapelet算法目标找到容易区分的部分，作为整个时间序列的特征。这样的方法有很多的优点：1) 可解释性好，方便于专家经验相互验证；2) 分类速度快；3) 在一些场景中，局部特征的捕捉比全局特征的捕捉准确度更高。那么Shapelet算法具体该如何实现呢，本章节为大家做详细阐述。

01问题定义

从I个长度M的时间序列实例的数据集（以

表示）中学习K个长度为L的Shapelet，以

表示，每个时间序列被分为J=M-L个片段。

定义第k个Shapelet

与第i个时间序列

之间的最小距离为

，可以认为

Shapelet与和它最相似的时间序列片段之间的距离，j是被shapelet分成的片段窗口。

在这里距离的度量一般采用欧式距离。以一个子序列作为窗口在完整的时间序列上进行步长为1的滑动，当窗口滑过整个时间序列后，子序列的相似性就全部计算出来了。基于此，如何定义显著子序列，以及如何提取显著子序列，是Shapelet算法所关注的重点问题。

02术语定义

时间序列的距离 Dist(T,R)：将两个长度相同的时间序列T和R作为输入，并返回一个非负值d，即T和R之间的距离。这里要求函数Dist对称；即Dist(R,T)=Dist(T,R)。

从时间序列到其子序列的距离 SubsequenceDist(T, S) ：它将时间序列T和子序列S作为输入，并返回非负值d，取最小的d即从T到S的距离。SubsequenceDist(T, S ) = min(Dist (T, S’ ))，S'表示所有选取的子序列。可以理解为:

熵：作为模型表现的评判依据。一个时间序列数据集D由A和B两个类组成，当A类中的对象比例为p(A)，B类中对象的比例为p(B)，则D的熵为:

在决策树中，每次分割策略将整个数据集D分成两个子集，D1和D2。因此，在对每个数据集进行加权后，剩余的信息由每个子集的加权熵定义。如果D1中的对象的分数为f(D1)，D2中的对象分数为f(D2)，则拆分后D的总熵为

这允许我们定义任何拆分策略的信息增益, 拆分前后熵表示为

，假设拆分策略为sp，那么

当使用shapelet的距离作为拆分策略时，数据集的一个类中的大多数时间序列对象都接近SubsequenceDist下的shapelet，而另一个类中的大多数时间序列对象则远离它。使用暴力算法，给定一个候选shapelet，计算候选对象与数据集中每个时间序列对象之间的距离。根据距离对候选对象排序进行排序，并在两个相邻距离之间找到一个最佳分割点.

最佳分割点（OSP）：一个时间序列数据集D由A和B两类组成。对于shapelet候选者S，我们选择一些距离阈值dth，并将D分为D1和D2，这样对于D1中的每个时间序列对象T，SubsequenceDist(T, S)<dth， 对于D2中的每个时间序列对象T，SubsequenceDist(T, S)>dth。

Shapelet：给对应一个包含两个类别的时间序列D, Shapelet (D)是一个子序列，对于任何子序列S，与它相对应的最佳分割点为

由于shapelet只是任何长度小于或等于我们数据集中最短时间序列长度的时间序列，因此它可以拥有无限多的可能形状。做一个合理的假设，一个类中的时间序列对象可能包含一些类似的子序列，把这些子序列是看做shapelet的候选对象。

03寻找Shapelet

从上一章节可以知道，只要能将时序数据通过某一距离阈值分为两类，都可以作为shapelet的候选对象，那么这样的shapelet可能有多少个候选对象呢？举个例子，数据集有200个实例，每个实例的长度为275。如果设置shapelet最小长度MINLEN=3，最大长度MAXLEN=275，将有7480200个shapelet候选者。如何在这么多候选者里面找到最优的shapelet？下面介绍几种方法：

暴力算法

正所谓“暴力出奇迹”，最简单最容易想到的就是暴力搜索：先产生所有可能长度的子序列作为候选shapelet的集合；初始最大信息增益为0， 然后检测每个候选集中的shapelet能够多好地区分A、B两类。直观理解，如下图所示，计算每个时间序列到候选对象的距离， 将其放在实数线上，并标注上类别

子序列丢弃

在蛮力法中，通过计算T和每个长度为|S|的子序列的欧氏距离并选择最小值，得到时间序列T到子序列S的距离。当前存在一个最小距离时，我们不再计算每个子序列与候选序列之间的确切距离，而是可以在部分距离超过目前已知的最小距离时停止计算距离，这样达到提高效率的目的。如下图所示：

熵剪枝

可以使用一种叫做早期熵剪枝的新思想，以避免在寻找形状元素时需要进行大量的距离计算。在brute-force算法中，获取候选对象与其每个对象的最近匹配子序列之间的距离是最昂贵的计算，而计算信息增益所需的时间并不重要。不必等到每个时间序列对象到候选对象的所有距离，而是根据当前观察到的距离计算信息增益的上界。如果在搜索过程中的任何时候，上界不能超过目前为止的最佳信息增益，我们将停止距离计算并从考虑中删去该特定的候选对象。如下图：

通过测量10个时间序列到目前为止最佳候选对象的距离，并根据距离将他们排列成一维表示。A类的6个对象中有5个（用圆圈表示）比来自B类的4个对象中的任何一个（用正方形表示）更接近候选对象。此外，在分割点右侧的5个对象中，只有一个A类对象与B类对象混淆。最佳分割点用一条垂直虚线表示，到目前为止最好的信息增益为：

算法发展

‍Shapelet算法的提出改变了固有的时间序列特征分析的思路，越来越多的工作转移到了挖掘时序数据的形态特征上来。同时，Shapelet对时序中局部特征的挖掘，天然的适用于Attention网络对局部强特征的注意力加强，成为后续很多时序深度神经网络架构中的重要一环。本章节对后续技术的发展做简要梳理，欢迎大家持续补充。

Shapelet增强

1. Logical-shapelets: an expressive primitive for time series classification (KDD 2011)
2. Fast-shapelets: a fast algorithm for discovering robust time series shapelets (SDM 2013)
3. Classification of time series by shapelet transformation (DMKD 2014)
4. Learning time-series shapelets (KDD 2014)
5. Efficient Learing of Timeseries Shapelets (AAAI 2016)

Shapelet聚类与分类

1. Clustering time series using unsupervised-shapelets (ICDM 2012)
2. Scalable Clustering of Time Series with U-Shapelets (SDM 2015)
3. Matrix Profile I: All Pairs Similarity Joins for Time Series: A Unifying View That Includes Motifs, Discords and Shapelets (ICDM 2016)

Shapelet + Graph

1. Time2Graph: Revisiting Time Series Modeling with Dynamic Shapelets (AAAI 2020)
2. Time-Series Event Prediction with Evolutionary State Graph (WSDM 2021）
3. Time2Grpah+: Bridging Time Series and Graph Representation Learning via Multiple Attentions (TKDE 2021)

Shapelet + 神经网络

1. Learning Multivariate Shapelets with Multi-Layer Neural Networks (ACDL 2018)
2. Learning multivariate shapelets with multi-layer neural networks for interpretable time-series classification (ADAC 2021)
3. ShapeNet: A Shapelet-Neural Network Approach for Multivariate Time Series Classification （AAAI 2021）