IPS: Instance Profile for Shapelet Discovery for Time Series Classification

时间序列分类(TSC)一直是研究的热点之一。时间序列shapelets(或简称shapelets)是一种判别子序列，最近被发现在解决TSC方面既有效又可解释。然而，众所周知，shapelet发现的计算成本很高。最近，矩阵轮廓(matrix profile)被提出用于高效的模体发现和异常检测。初步实验表明，直接采用矩阵剖面方法对TSC进行分类并不会带来更高的分类精度。本文确定了这种采用的两个主要问题:1)“shapelets”的不一致，以及2)shapelets多样性的缺乏。针对这些问题，本文提出了shapelets实例概要，称为IPS，用于TSC的shapelets发现。其主要挑战是利用实例概要(instance profile, IP)以稳健的方式捕获shapelets特征，进而高效地发现高质量的shapelets。首先，我们使用IP来生成大量的shapelet候选集。接下来，使用新的分布感知布隆过滤器(DABF)有效地修剪与shapelets定义不一致的候选集。提出了3个效用函数来衡量shapelet候选集，并使用DABF高效地计算这些效用函数。使用UCR Archive数据集，在IPS上与12种最先进的方法进行了全面的实验。与目前最先进的BSPCOVER算法相比，效率平均提高了25倍。IPS的精度与现有工作相当或更高。此外，选择一个案例来说明shapelets的可解释性。

阅读者总结：这篇论文值得学习的地方是 应用布隆过滤器在shapelets中。其次论文对问题本身的分析比较深入，shapelets问题一直有大量研究工作，可以说是一个很老的问题，但是作者很巧妙的分析了传统方法上的局限性，可以看出来，作者对传统matrix profile进行了深入和实际的实验，并发现了matrix profile在处理shapelets上的低效。

从方法本身来说，在解决shaplets上不是很新颖，基本上套路，找候选对象，然后剪枝候选对象。

整个论文在方法上的起始：对问题的考虑是逐渐完善的过程，分析一个要解决的问题时，在逻辑上要清楚如何把问题拆解，对每个小问题，要解决的目标要明确，然后深入分析该小问题涉及到的范围，然后设计模型，比如各种索引，各种统计分析方法等。最后将整个小问题进行整合，成为整个大问题的结果。在这个流程中，每个小问题的分解，道路上要将明白，这样各个部分就能衔接上。

问题：

这种发现shapelets的方法存在两个主要问题，这可能会对shapelets的质量产生不利影响(详见第II-B节)。简而言之，该指标可以将a类和B类的不一致识别为shapelets(第1期，不一致识别为“shapelets”)，这可能在矩阵剖面之间有很大的差异。这种情况与shapelets的定义相矛盾，shapelets通常靠近一个类，但远离其他类[35]。之前的工作[37]将所有时间序列实例连接为一个长实例，这降低了shapelets的多样性(第2期，shapelets多样性的缺乏)，尽管可以通过选取topk shapelets[37]来缓解这一问题。然而，top-k shapelets可能彼此相似，仍然存在第2个问题。 

 方法：

提出instance profile  以及分布感知过滤器distribution-aware bloom filter (DABF)

 面临两个问题：

Baseline：

 

1st issue: Discords as “shapelets”. 

2nd issue: Lack of shapelet diversity.

第二个问题是MP基线方法将一个类的时间序列连接成一个长时间序列(如图1所示)。MP构建在连接的时间序列上，基线方法不一定找到代表整个类的shapelets。当用这种形状粒进行分类时，准确率不高。

 

 

B. Distribution-aware bloom filter (DABF)

首先介绍了分布感知的布隆过滤器(distributed -aware bloom filter, DABF)，它返回查询是否接近集合中的大多数元素。答案要么是“可能在集合中”，要么是“肯定不在集合中”。提出了距离敏感的布隆过滤器[15]，用于判断查询是否与集合中的元素相近。与布隆过滤器[4]、[6]类似，距离敏感的布隆过滤器的回答要么是“可能接近某个元素”，要么是“绝对不接近”。但是，前面的两个过滤器并不是专门为我们的情况设计的，以检查子序列是否接近Φ中的大多数元素 

接下来，我们提出了分布感知布隆过滤器(DABF)来解决O(N)中的查询。DABF是一种数据结构，用于测试查询是否接近集合中的大多数元素。数据集D的DABF由每个类的DABFC组成，DABFC由一组位置敏感哈希(LSH)函数和时间序列子序列的距离分布组成，表示为DABFC = (LSHC, DistributionC)。DABF构建过程如图7所示。

 利用LSH函数将产生候选序列的整个时间序列哈希到桶中(也称为聚类)，并根据每个桶(聚类)的中心与原始桶的距离对桶进行排序。

C. Shapelet candidate pruning with DABF

在这一小节中，我们将介绍如何用DABF对不符合shapelets定义的候选集进行剪枝。在我们的例子中，我们想要查询一个候选元素是否接近集合中的大多数元素。因此，定义“大多数元素”是很重要的。 

 Top-k shapelet selection

从没有被DABF过滤的候选集中，我们对候选集进行评分，然后选择与候选集相似的top-k。我们提出了三个效用函数，分别从类内、类间和时间序列实例中为候选者打分。

 

 接下来，将motif候选集和同样来自类别C的原始时间序列实例之间的距离纳入分数。实例内工具(定义13)是针对shapelets的特点而设计的，即同一类中的时间序列实例应该更接近shapelets

 实验

跳过。。。。。。。。。