Efficient Shapelet Discovery for Time Series Classification（TKDE）

时间序列shapelets是一种鉴别子序列，近年来被发现用于时间序列分类(TSC)。很明显，shapelets的质量对TSC的准确性至关重要。然而，主要的研究集中在从一些候选shapelet中建立精确的模型。为了确定这些候选者，现有的研究出奇地简单，例如，枚举某些固定长度的子序列，或随机选择一些子序列作为shapelet候选者。然后，主要的计算工作就是从候选对象构建模型。在本文中，我们提出了一种新的高效的shapelet发现方法，称为BSPCOVER，以发现一组高质量的候选shapelet用于模型构建。具体来说，BSPCOVER通过滑动窗口的符号聚合近似生成大量候选对象，然后分别通过布鲁姆过滤器和相似性匹配删除相同和高度相似的候选对象。接下来，我们提出了一个p-Cover算法，以有效地确定最大表示每个时间序列类的判别形状候选。最后，任何现有的shapelet学习方法都可以用来建立分类模型。我们用著名的时间序列数据集和代表性的最先进的方法进行了广泛的实验。结果表明，BSPCOVER方法使现有方法的速度提高了70倍以上，其精度往往与现有方法相当或更高。

背景：

Shapelet发现不仅显著提高了模型构建的效率，而且常常提高了模型构建的准确性。

1）候选人的数量很大

2）这些shapelets应该具有足够的辨别能力来对时间序列进行分类

3）由于对一些大型数据集的建模效率问题，只能选择相对较小的候选集

 

框架：

 

 The core of BSPCOVER then consists of three main steps

1.BSPCOVER为每个时间序列类派生一个bloom过滤器，以有效地删除其他类中也存在的相同SAX单词

2. 第二步是对类似SAX单词进行非度量的基于距离的修剪，这消除了所有类中存在的类似SAX单词的影响。首先，原始时间序列之间的距离违反了时间序列的固有性质——三角不等式，时间序列的离散表示继承了这个性质。其次，在两种情况下，类似的SAX词会被删减。首先，类似的SAX词存在于不同的类中，它们都被删除了。在第二种情况下，对于同一类中的单词，只能保留一个具有代表性的单词以供进一步处理

3. 对于类中的每一组类似SAX单词，我们将它们的词汇频率作为权重计算。然后，我们设计SAX单词的加权位图结构来量化shapelet候选词的质量，利用这些候选词发现一组具有最大权重的SAX单词，并表示每个类中的所有实例。然后将形状簇选择问题形式化为加权位图覆盖问题，该问题可以从经典的加权集覆盖问题简化而来。

4. 我们将SAX单词转换回时间序列的原始表示。现有的学习方法可以用于修改所选的shapelets，进一步提高精度。在本文中，我们对LTS[9]进行了修改，建立了一vs rest分类器。

 

 EFFICIENT SAX SUBSEQUENCE COMPUTATION

概述。将原始时间序列数据简化为SAX序列，然后使用滑动窗口生成可变长度的SAX单词(Algo. 1)。从大量的SAX单词中挖掘一些高质量的SAX单词是低效的。我们的主要技术计算一小组SAX候选词，如下所示。一、我们为每个类构造一个bloom filter来高效地修剪所有类中存在的相同SAX单词，并为每个剩余的SAX单词构建一个位图结构(Algo. 2);2我们删除所有类中出现的类似SAX单词，然后定义每个SAX单词的加权位图(Algo. 3);ⅲ。我们将发现问题表述为加权集覆盖问题，并提出一种启发式方法来解决它(算法4和算法5)。

 

Bloom filter and bitmap of SAX words 

 我们提出在BSPCOVER中使用bloom过滤器来有效地删除没有区别的SAX单词

 

 

 Building compact representation ofSAXwords

 

 Similar SAX word pruning

减少用于模型构建的过多SAX单词的一种自然技术是删除所有类中存在的类似SAX单词 

 

 SAX word cover for model building

详细介绍了用BSPCOVER方法计算建立模型的SAX字的方法。简而言之，通过找到覆盖时间序列实例的最小子集，而不是直接发现SAX单词，该问题被表述为加权位图覆盖问题。我们提供了一些定义来解释下面的方法。 

 

 

 

  Parameter settings

Cost model for setting parameters：我们提出了BSPCOVER的成本模型来分析其对数据集d的效率。BSPCOVER的效率主要由三个部分贡献:

I. the number of iterations I; II. the number of cover times p; and III. other factors , such as program initialization and operating system. 

实验部分 

 

 

 总结：1）这篇找shapelets的论文，在寻找高精度的shaplet方面结合了bloom filter,bitmap压缩方法。这是文中比较大创新组合。最后将问题转化为寻找最小集合覆盖问题，使得问题得到了提升。

2）值得学习的地方在于 文中写作上 每个算法都有详细的例子和过程图形展示，应该说写作上表达的效果很好。