Salient Subsequence Learning for Time Series Clustering

Qin Zhang, Jia Wu, Member, IEEE, Peng Zhang, Guodong Long, Chengqi Zhang, Senior Member, IEEE

TPAMI 2018

什么是shapelet？

shapelet是时间序列的子序列，具有判别性，其在某种意义上最大程度地代表类。

从树叶分类说起，自然是根据树叶的形状分类

将每个树叶用一个一维的时间序列来表示

根据shapelets分类

shapelets的优点

• 可解释性好
• 结果更精确，因为考虑的是局部特征，而非全局特征(很容易收到噪声和扭曲的影响)
• 速度更快，时间复杂度为O(mn)(m为时间序列长度，n为shapelet长度)

主要贡献

• USSL 无监督的shapelet学习，用于时间序列聚类，结合了pseudo-class labels, spectral analysis, regularized least-squares techniques and shapelet regularization
• 在UCR Time Series数据集上进行了验证，是state-of-the-art

目前方法存在的问题

• 最初通过扫描整个时间序列来获取shapelets的候选模板，时间复杂度很高

  Synthetic Control dataset 包含600个时间序列， 长度为60，候选模板有1:098 × 10^6个

• 最近Grabocka等人提出一种基于回归学习的方法，寻找shapelets，大大减少了时间复杂度，但是需要标记

USSL框架

无监督的shapelet学习

• Shapelet-transformed Representation

• Pseudo-class Labels

• Spectral Analysis

• Least-squares Minimization

• Shapelet Similarity Minimization

• Unsupervised Salient Subsequence Learning
  

  第一部分是谱正则化项，以保持时间序列之间的局部结构。第二部分通过最小化shapelets之间的相似性来使其多样化。第三部分则为学习最佳伪类标签和伪分类器的最小二乘正则化。

• coordinate descent algorithm 坐标下降法

  当要优化的函数含有多个自变量时，每次只更新一个自变量，固定其他自变量

实验

数据集：UCR Time Series 中的36个时间序列

评价指标

• Rand Index
  
• NMI(Normalized Mutual Information)
  

实验结果

• 等长的时间序列聚类
  

• 不等长的时间序列聚类