标题：时间序列“小形状”：数据挖掘的新原型

ABSTRACT

• 本文解决的是时间序列分类问题；
• 之前的方法主要是基于KNN的（欧式/DTW）距离分类，有三个问题：
  • 可解释性差；
  • 需要存储、搜索整个数据集。
  • 考虑整体特征，易受噪声影响。

1. INTRODUCTION

• 基本做法：shapelet是数据集中某个序列的一个子序列。分类是让数据集中所有序列和这个子序列计算距离，再设定一个阈值，小于这个阈值的是一类，大于这个阈值的是一类。
• 优化目标：分类的优化目标是信息增益。
• 挑战：如何找到一个最优的shapelet

2. RELATED WORK AND BACKGROUND

• 不等长序列距离度量：遍历所有长序列的子序列，找到距离最小的即为距离
• 熵：一个数据集D分成A，B两个类，其熵值为
  
  p(A),p(B)为A，B所占比例
• 信息增益：将一个数据集D分类后，熵值的变化。
  • 选择信息增益的一个原因是可以轻易扩展成多分类问题。
• 最优分割点：给定一个子序列做shapelet，选择哪个分类阈值可以获得最高的分类信息增益。
• shapelet：最优子序列+最优分割点就是shapelet

3. FINDING THE SHAPELET

3.1 Brute-Force Algorithm

最简单的寻找shapelet的方法就是暴力遍历：

1. 找出数据集中序列的所有子序列；
2. 每个子序列依次作为shapelet候选子序列进行检验；
3. 检验时首先计算Candidate和数据集中所有序列的距离，获得距离直方图；
4. 根据这个距离直方图找一个最优分割点，返回该情况下的信息增益。

3.2 Subsequence Distance Early Abandon

距离计算可以剪枝，即如果当前的部分欧式距离已经超过BSF，那么直接放弃掉。

3.3 Admissible Entropy Pruning

candidate检验也可以利用上界来进行剪枝。假设现在根据某个candidate做了一半的距离直方图，那么信息增益的上界就是把剩下的一半，一半（总量的1/4）放给距离0，一半放给距离最大值+1，此时信息增益是理论最大的。
如果这个上界的信息增益也不如BSF，那么直接进入下一个candidate。