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）