基于形状的时间序列相似性度量及模式发现算法

Shape-based Time Series Similarity Metric and Pattern Discovery Algorithm

针对目前时间序列模式发现中使用的时间序列相似性度量易受尺度(scale)和平移的影响,不适应基于形状的时间序列模式发现,本文提出了一种重标和平移不变的时间序列相似性度量:Sh 度量,给出度量的性质及其证明。同时提出了基于Sh度量的时间序列形状模式发现算法,并对算法的有限次迭代终止性和时间复杂性进行了证明。论文最后通过对人工数据和太阳黑子数据的实验证明了本文提出的Sh度量及基于形状的时间序列模式发现算法的有效性。

Pattern discovery from time series is of fundamental importance. One of the largest groups of technique for the problem of pattern discovery in time series is clustering based on some kind of similarity metric. The similarity metric recently used in time series clustering are affected by the scale and baseline so that this is a problem as objective is to capture the shape, not the value. In order to surmount the problem, another similarity metric is proposed based on shape similarity, which is called Sh metric. We give the property of this similarity and corresponding proof. Then we propose a time series shape pattern discovery algorithm based on Sh metric, prove that the algorithm is terminated in finite iteration, and provide the time complexity. Finally the experiments on synthetic datasets and sunspot datasets demonstrate that the time series shape similarity metric: Sh metric and the time series shape pattern algorithm based on Sh metric are effective.