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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
DTW is referred to as a distance, but this should not be interpreted as being a metric, as it does not satisfy the triangular inequality [22] .
- 2.
To apply DTW on multivariate time series, the cost function can be defined as the squared Euclidean distance between the two time samples [32].
- 3.
Instead of saving \(\phi _{j, j'}\), backtracking can also be performed by selecting the direction that minimizes the cumulative cost by complying with the restrictions in (6).
- 4.
There is only a single matched time sample because DTW-AROW matches each missing value with exactly one sample in the other time series (see Sect. 4).
- 5.
The reason for using DTW-AROW instead of the original DTW is the fact that, on rare occasions, the representatives \(\mathcal {Z}\) obtained by DBAM may still contain missing values (see line 8 of Algorithm 2), so as the imputed time series data \(\hat{\mathcal {X}}\).
- 6.
References
Abanda, A., Mori, U., Lozano, J.A.: A review on distance based time series classification. Data Min. Knowl. Disc. 33(2), 378–412 (2019)
Cao, W., Wang, D., Li, J., Zhou, H., Li, L., Li, Y.: Brits: bidirectional recurrent imputation for time series. In: Advances in Neural Information Processing Systems, vol. 31 (2018)
Dau, H.A., et al.: Hexagon-ML: the UCR time series classification archive, October 2018. https://www.cs.ucr.edu/~eamonn/time_series_data_2018/
deJong, J., et al.: Deep learning for clustering of multivariate clinical patient trajectories with missing values. GigaScience 8(11), 134 (2019)
Fang, C., Wang, C.: Time series data imputation: a survey on deep learning approaches. arXiv preprint arXiv:2011.11347 (2020)
Fox, W.R.: Finding groups in data: an introduction to cluster analysis (1991)
Gemmeke, J.F., Virtanen, T., Hurmalainen, A.: Exemplar-based sparse representations for noise robust automatic speech recognition. IEEE Trans. Audio Speech Lang. Process. 19(7), 2067–2080 (2011)
Hubert, L., Arabie, P.: Comparing partitions. J. Classif. 2, 193–218 (1985)
Humpherys, J., Jarvis, T.: Foundations of Applied Mathematics, Volume 2: Algorithms, Approximation, Optimization. SIAM (2020)
Javed, A., Lee, B.S., Rizzo, D.M.: A benchmark study on time series clustering. Mach. Learn. App. 1, 100001 (2020)
Jr., J.L.H., Lehmann, E.L.: rank methods for combination of independent experiments in analysis of variance. Ann. Math. Statist. 33(2), 482–497 (1962)
Kendall, M.G.: A new measure of rank correlation. Biometrika. 30(1–2), 81–93 (1938)
Lepot, M., Aubin, J.B., Clemens, F.: Interpolation in time series: an introductive overview of existing methods, their performance criteria and uncertainty assessment. Water. 9(10), 796 (2017)
Li, G., Choi, B., Xu, J., Bhowmick, S.S., Chun, K.P., Wong, G.L.H.: Efficient Shapelet discovery for time series classification. IEEE Trans. Knowl. Data Eng. 34(3), 1149–1163 (2022)
Lin, S., Wu, X., Martinez, G., Chawla, N.V.: Filling Missing Values on Wearable-Sensory Time Series Data, pp. 46–54 (2020). https://doi.org/10.1137/1.9781611976236.6
Luo, Y., Cai, X., Zhang, Y., Xu, J., et al.: Multivariate time series imputation with generative adversarial networks. In: Advances in Neural Information Processing Systems, vol. 31 (2018)
Ma, Q., Chen, C., Li, S., Cottrell, G.W.: Learning representations for incomplete time series clustering. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, pp. 8837–8846 (2021)
Madrid, F., Imani, S., Mercer, R., Zimmerman, Z., Shakibay, N., Keogh, E.: Matrix Profile XX: finding and visualizing time series motifs of all lengths using the matrix profile. In: 2019 IEEE International Conference on Big Knowledge (ICBK), pp. 175–182. IEEE, Beijing, China, November 2019. https://doi.org/10.1109/ICBK.2019.00031, https://ieeexplore.ieee.org/document/8944710/
McKnight, P.E., McKnight, K.M., Sidani, S., Figueredo, A.J.: Missing data: a gentle introduction. Guilford Press (2007)
Meert, W., et al.: wannesm/dtaidistance: v2.3.5, January 2022. https://doi.org/10.5281/zenodo.5901139
Moritz, S., Bartz-Beielstein, T.: Imputets: time series missing value imputation in r. R J. 9(1), 207 (2017)
Müller, M.: Information Retrieval for Music and Motion, vol. 2. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74048-3
Oehmcke, S., Zielinski, O., Kramer, O.: KNN ensembles with penalized DTW for multivariate time series imputation. In: 2016 International Joint Conference on Neural Networks (IJCNN), pp. 2774–2781 (2016)
Park, H.S., Jun, C.H.: A simple and fast algorithm for k-medoids clustering. Expert Syst. App. 36(2, Part 2), 3336–3341 (2009). https://doi.org/10.1016/j.eswa.2008.01.039, https://www.sciencedirect.com/science/article/pii/S095741740800081X
Pearson, K.: VII. mathematical contributions to the theory of evolution.–III. regression, heredity, and panmixia. Philos. Trans. R. Soc. London. Ser. A. 187, 253–318 (1896)
Pedregosa, F., et al.: Scikit-learn: machine learning in Python. J. Mach. Learn. Res. 12, 2825–2830 (2011)
Petitjean, F., Ketterlin, A., Gançarski, P.: A global averaging method for dynamic time warping, with applications to clustering. Pattern Recogn. 44(3), 678–693 (2011)
Pratama, I., Permanasari, A.E., Ardiyanto, I., Indrayani, R.: A review of missing values handling methods on time-series data. In: 2016 International Conference on Information Technology Systems and Innovation (ICITSI), pp. 1–6 (2016). https://doi.org/10.1109/ICITSI.2016.7858189
Räsänen, T., Kolehmainen, M.: Feature-based clustering for electricity use time series data. In: Kolehmainen, M., Toivanen, P., Beliczynski, B. (eds.) ICANNGA 2009. LNCS, vol. 5495, pp. 401–412. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04921-7_41
Sakoe, H., Chiba, S.: Dynamic programming algorithm optimization for spoken word recognition. IEEE Trans. Acoust. Speech Signal Process. 26(1), 43–49 (1978)
Satopaa, V., Albrecht, J., Irwin, D., Raghavan, B.: Finding a "kneedle" in a haystack: Detecting knee points in system behavior. In: 2011 31st International Conference on Distributed Computing Systems Workshops, pp. 166–171 (2011)
Shokoohi-Yekta, M., Hu, B., Jin, H., Wang, J., Keogh, E.: Generalizing DTW to the multi-dimensional case requires an adaptive approach. Data Min. Knowl. Disc. 31, 1–31 (2017)
Sitaram, D., Dalwani, A., Narang, A., Das, M., Auradkar, P.: A measure of similarity of time series containing missing data using the mahalanobis distance. In: 2015 Second International Conference on Advances in Computing and Communication Engineering, pp. 622–627 (2015). https://doi.org/10.1109/ICACCE.2015.14
Wothke, W.: Longitudinal and multigroup modeling with missing data. In: Modeling Longitudinal and Multilevel Data, pp. 205–224. Psychology Press (2000)
Xu, D., Tian, Y.: A comprehensive survey of clustering algorithms. Ann. Data Sci. 2(2), 165–193 (2015)
Yazdanbakhsh, O., Dick, S.: Multivariate time series classification using dilated convolutional neural network. arXiv preprint arXiv:1905.01697 (2019)
Yoon, J., Jordon, J., van der Schaar, M.: GAIN: missing data imputation using generative adversarial nets. In: Dy, J., Krause, A. (eds.) Proceedings of the 35th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 80, pp. 5689–5698. PMLR, 10–15 July 2018
Acknowledgement
This research received funding from the Flemish Government under the “Onderzoeksprogramma Artificiële Intelligentie (AI) Vlaanderen” programme.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Yurtman, A., Soenen, J., Meert, W., Blockeel, H. (2023). Estimating Dynamic Time Warping Distance Between Time Series with Missing Data. In: Koutra, D., Plant, C., Gomez Rodriguez, M., Baralis, E., Bonchi, F. (eds) Machine Learning and Knowledge Discovery in Databases: Research Track. ECML PKDD 2023. Lecture Notes in Computer Science(), vol 14173. Springer, Cham. https://doi.org/10.1007/978-3-031-43424-2_14
Download citation
DOI: https://doi.org/10.1007/978-3-031-43424-2_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-43423-5
Online ISBN: 978-3-031-43424-2
eBook Packages: Computer ScienceComputer Science (R0)