Estimating Dynamic Time Warping Distance Between Time Series with Missing Data

Abstract

Many techniques for analyzing time series rely on some notion of similarity between two time series, such as Dynamic Time Warping (DTW) distance. But DTW cannot handle missing values, and simple fixes (e.g., dropping missing values, or interpolating) fail when entire intervals are missing, as is often the case with, e.g., temporary sensor or communication failures. There is hardly any research on how to address this problem. In this paper, we propose two hyperparameter-free techniques to estimate the DTW distance between time series with missing values. The first technique, DTW-AROW, significantly decreases the impact of missing values on the DTW distance by modifying the optimization problem in the DTW algorithm. The second technique, DTW-CAI, can further improve upon DTW-AROW by exploiting additional contextual information when that is available (more specifically, more time series from the same population). We show that, on multiple datasets, the proposed techniques outperform existing techniques in estimating pairwise DTW distances as well as in classification and clustering tasks based on these distances. The proposed techniques can enable many machine learning algorithms to more accurately handle time series with missing values.