Computer Engineering and Applications ›› 2020, Vol. 56 ›› Issue (22): 42-47.DOI: 10.3778/j.issn.1002-8331.1912-0320

Previous Articles     Next Articles

Multi-dimensional DTW Combined with Shape Feature and Context Information

WANG Jian, MAO Liming, YIN Aijun   

  1. College of Mechanical Engineering, Chongqing University, Chongqing 400044, China
  • Online:2020-11-15 Published:2020-11-13

结合形状特征及其上下文的多维DTW

王见,毛黎明,尹爱军   

  1. 重庆大学 机械工程学院,重庆 400044

Abstract:

Traditional Dynamic Time Warping(DTW) and its variants are widely used in the similarity analysis of multi-dimensional time series, but they usually only focus on the information of a single time point and ignore the context information, so it is possible to match two points with completely different shapes. Therefore, a multi-dimensional DTW algorithm combined with shape features and context information is proposed, which named Multi-Dimensional Contextual Dynamic Time Warping(MDC-DTW). MDC-DTW first computes the first-order derivative between two multivariate time series, then samples them, and uses matrix to store the information which encodes the first-order derivative of this time stamp and its local structure, finally uses DTW to get the similarity. To test the rationality of the MDC-DTW’s design, the algorithm is qualitatively and quantitatively analyzed, and the results show that the MDC-DTW’s design is reasonable. In an effort to understand the benefits of MDC-DTW, this paper empirically compares four state-of-the-art algorithms on five datasets, the results show that MDC-DTW has comparable accuracy and speed.

Key words: multivariate time series, similarity analysis, shape feature, context, Dynamic Time Warping(DTW)

摘要:

传统动态时间规整算法(Dynamic Time Warping,DTW)及其变种算法被广泛应用于多维时间序列的相似性分析,但它们通常只关注单个时间点的信息而忽略了上下文信息,从而很可能匹配两个形状完全不同的点。因此提出一种结合形状特征及其上下文的多维DTW算法(Multi-Dimensional Contextual Dynamic Time Warping,MDC-DTW)。该算法首先计算多维时间序列的一阶梯度,然后对其进行采样处理,并以多维梯度矩阵表示当前时间点的形状信息及其上下文信息,最后利用DTW求解多维时间序列间的最短匹配路径。为检测算法设计的合理性,对算法进行了定性分析和定量分析,实验结果表明MDC-DTW算法设计是合理的;为检测MDC-DTW的性能,选用5个多维时间序列数据集,并与4个优异的多维DTW算法进行对比实验,实验结果表明MDC-DTW具有较高的准确率和运行效率。

关键词: 多维时间序列, 相似性分析, 形状特征, 上下文, 动态时间规整算法(DTW)