Adaptively constrained dynamic time warping for time series classification and clustering. (English) Zbl 1465.62151
Summary: Time series classification and clustering are important for data mining research, which is conducive to recognizing movement patterns, finding customary routes, and detecting abnormal trajectories in transport (e.g. road and maritime) traffic. The dynamic time warping (DTW) algorithm is a classical distance measurement method for time series analysis. However, the over-stretching and over-compression problems are typical drawbacks of using DTW to measure distances. To address these drawbacks, an adaptive constrained DTW (ACDTW) algorithm is developed to calculate the distances between trajectories more accurately by introducing new adaptive penalty functions. Two different penalties are proposed to effectively and automatically adapt to the situations in which multiple points in one time series correspond to a single point in another time series. The novel ACDTW algorithm can adaptively adjust the correspondence between two trajectories and obtain greater accuracy between different trajectories. Numerous experiments on classification and clustering are undertaken using the UCR time series archive and real vessel trajectories. The classification results demonstrate that the ACDTW algorithm performs better than four state-of-the-art algorithms on the UCR time series archive. Furthermore, the clustering results reveal that the ACDTW algorithm has the best performance among three existing algorithms in modeling maritime traffic vessel trajectory.
MSC:
| 62M10 | Time series, auto-correlation, regression, etc. in statistics (GARCH) |
| 62H30 | Classification and discrimination; cluster analysis (statistical aspects) |
| 62P30 | Applications of statistics in engineering and industry; control charts |
Keywords:
dynamic time warping; distance measure; time series classification; vessel trajectory clusteringSoftware:
shapeDTWReferences:
| [1] | Aghabozorgi, S.; Shirkhorshidi, A. S.; Wah, T. Y., Time-series clustering-a decade review, Information Syst., 53, 16-38 (2015) |
| [2] | Al-Zaidi, R.; Woods, J. C.; Al-Khalidi, M.; Hu, H. S., Building novel VHF-based wireless sensor networks for the Internet of marine things, IEEE Sens. J., 18, 2131-2144 (2018) |
| [3] | Atev, S.; Miller, G.; Papanikolopoulos, N. P., Clustering of vehicle trajectories, IEEE Trans. Intell. Transp. Syst., 11, 647-657 (2010) |
| [4] | Barbon, S.; Guido, R. C.; Vieira, L. S.; Fonseca, E. S.; Sanchez, F. L.; Scalassara, P. R.; Maciel, C. D.; Pereira, J. C.; Chen, S. H., Wavelet-based dynamic time warping, J. Comput. Appl. Math., 227, 271-287 (2009) · Zbl 1162.65421 |
| [5] | Batista, G. E.; Keogh, E. J.; Tataw, O. M.; De Souza, V. M., CID: an efficient complexity-invariant distance for time series, Data Mining and Knowledge Discovery, 28, 634-669 (2014) · Zbl 1294.62188 |
| [6] | Berndt, D. J.; Clifford, J., Using dynamic time warping to find patterns in time series, (Proc. of the 3rd International Conference on Knowledge Discovery and Data Mining. Proc. of the 3rd International Conference on Knowledge Discovery and Data Mining, Seattle, WA (1994)), 359-370 |
| [7] | Cai, Y.; Wang, H.; Chen, X.; Jiang, H., Trajectory-based anomalous behaviour detection for intelligent traffic surveillance, IET Intel. Transport Syst., 9, 810-816 (2015) |
| [8] | Y. Chen, E. Keogh, B. Hu, N. Begum, A. Bagnall, A. Mueen, G. Batista, The UCR time series classification archive, (2015) URL:www.cs.ucr.edu/∼eamonn/time_series_data. |
| [9] | Choong, M. Y.; Chin, R. K.Y.; Yeo, K. B.; Teo, K. T.K., Trajectory pattern mining via clustering based on similarity function for transportation surveillance, Int. J. Simulation-Sys Sci. Technol., 17, 19.11-19.17 (2016) |
| [10] | H.A. Dau, A. Bagnall, K. Kamgar, C.-C.M. Yeh, Y. Zhu, S. Gharghabi, C.A. Ratanamahatana, E. Keogh, The UCR time series archive, arXiv preprint arXiv:1810.07758, (2018). |
| [11] | Folgado, D.; Barandas, M.; Matias, R.; Martins, R.; Carvalho, M.; Gamboa, H., Time Alignment Measurement For Time Series, Pattern Recognit., 81, 268-279 (2018) |
| [12] | Gorecki, T.; Luczak, M., Using derivatives in time series classification, Data Mining and Knowledge Discovery, 26, 310-331 (2013) |
| [13] | Gupta, C.; Jain, A.; Tayal, D. K.; Castillo, O., ClusFuDE: Forecasting low dimensional numerical data using an improved method based on automatic clustering, fuzzy relationships and differential evolution, Eng. Appl. Artif. Intell., 71, 175-189 (2018) |
| [14] | Han, Y.; Zhu, L.; Cheng, Z.; Li, J.; Liu, X., Discrete optimal graph clustering, IEEE Transactions on Cybernetics, 50, 1697-1710 (2020) |
| [15] | Herbst, B.; Coetzer, H., On an offline signature verification system, (Proc. of the 9th Annual South African Workshop on Pattern Recognition (1998)), 39-43 |
| [16] | Itakura, F., Minimum prediction residual principle applied to speech recognition, IEEE T Acoust Speech, 23, 67-72 (1975) |
| [17] | Jeong, Y. S.; Jeong, M. K.; Omitaomu, O. A., Weighted dynamic time warping for time series classification, Pattern Recognit., 44, 2231-2240 (2011) |
| [18] | Keogh, E. J.; Pazzani, M. J., Derivative dynamic time warping, (Proc. of the 2001 SIAM International Conference on Data Mining (2001)), 1-11 |
| [19] | Krawczak, M.; Szkatuła, G., An approach to dimensionality reduction in time series, Information Sci., 260, 15-36 (2014) · Zbl 1329.62381 |
| [20] | Lam, J. S.L.; Cullinane, K. P.B.; Lee, P. T.-W., The 21st-century Maritime Silk Road: challenges and opportunities for transport management and practice, Transport Rev.., 38, 413-415 (2018) |
| [21] | Li, H.; Liu, J.; Liu, R.; Xiong, N.; Wu, K.; Kim, T., A dimensionality reduction-based multi-step clustering method for robust vessel trajectory analysis, Sensors, 17, 1792 (2017) |
| [22] | Li, H.; Liu, J.; Wu, K.; Yang, Z.; Liu, R.; Xiong, N., Spatio-temporal vessel trajectory clustering based on data mapping and density, IEEE Access, 6, 58939-58954 (2018) |
| [23] | Liao, T. W., Clustering of time series data—a survey, Pattern Recognit., 38, 1857-1874 (2005) · Zbl 1077.68803 |
| [24] | Lines, J.; Bagnall, A., Time series classification with ensembles of elastic distance measures, Data Mining and Knowledge Discovery, 29, 565-592 (2015) · Zbl 1405.68295 |
| [25] | Liu, J.; Li, H.; Yang, Z.; Wu, K.; Liu, Y.; Liu, R. W., Adaptive Douglas-Peucker algorithm with automatic thresholding for AIS-based vessel trajectory compression, IEEE Access, 7, 150677-150692 (2019) |
| [26] | Loh, W.-K.; Mane, S.; Srivastava, J., Mining temporal patterns in popularity of web items, Information Sci., 181, 5010-5028 (2011) |
| [27] | Morel, M.; Achard, C.; Kulpa, R.; Dubuisson, S., Time-series averaging using constrained dynamic time warping with tolerance, Pattern Recognit., 74, 77-89 (2018) |
| [28] | Morris, B.; Trivedi, M., Learning trajectory patterns by clustering: Experimental studies and comparative evaluation, (2009 IEEE Conference on Computer Vision and Pattern Recognition. 2009 IEEE Conference on Computer Vision and Pattern Recognition, Miami, FL, USA (2009)), 312-319 |
| [29] | Niennattrakul, V.; Ratanamahatana, C. A., On clustering multimedia time series data using k-means and dynamic time warping, (2007 International Conference on Multimedia and Ubiquitous Engineering (MUE’07). 2007 International Conference on Multimedia and Ubiquitous Engineering (MUE’07), Seoul, Korea (2007)), 733-738 |
| [30] | Petitjean, F.; Forestier, G.; Webb, G. I.; Nicholson, A. E.; Chen, Y. P.; Keogh, E., Faster and more accurate classification of time series by exploiting a novel dynamic time warping averaging algorithm, Knowledge and Information Systems, 47, 1-26 (2016) |
| [31] | Saini, R.; Roy, P. P.; Dogra, D. P., A novel point-line duality feature for trajectory classification, The Visual Computer, 35, 415-427 (2019) |
| [32] | Sakoe, H.; Chiba, S., Dynamic-programming algorithm optimization for spoken word recognition, IEEE Transactions on Acoustics Speech and Signal Processing, 26, 43-49 (1978) · Zbl 0371.68035 |
| [33] | Salvador, S.; Chan, P., Toward accurate dynamic time warping in linear time and space, Intell. Data Analysis, 11, 561-580 (2007) |
| [34] | Shanker, A. P.; Rajagopalan, A. N., Off-line signature verification using DTW, Pattern Recognit. Lett., 28, 1407-1414 (2007) |
| [35] | Sharma, A.; Sundaram, S., An enhanced contextual DTW based system for online signature verification using Vector Quantization, Pattern Recognit. Lett., 84, 22-28 (2016) |
| [36] | Silva, D. F.; Giusti, R.; Keogh, E.; Batista, G. E.A. P.A., Speeding up similarity search under dynamic time warping by pruning unpromising alignments, Data Mining and Knowledge Discovery, 32, 988-1016 (2018) · Zbl 1416.62528 |
| [37] | Soto, J.; Castillo, O.; Melin, P.; Pedrycz, W., A new approach to multiple time series prediction using MIMO fuzzy aggregation models with Modular Neural Networks, Int. J. Fuzzy Syst., 21, 1629-1648 (2019) |
| [38] | Tu, F.; Ge, S. S.; Choo, Y. S.; Hang, C. C., Sea state identification based on vessel motion response learning via multi-layer classifiers, Ocean Eng., 147, 318-332 (2018) |
| [39] | Velichko, V. M.; Zagoruyko, N. G., Automatic recognition of 200 words, Int. J. Man Mach. Stud., 2, 223-234 (1970) |
| [40] | Wan, Y.; Chen, X.; Shi, Y., Adaptive cost dynamic time warping distance in time series analysis for classification, J. Comput. Appl. Math., 319, 514-520 (2017) · Zbl 1360.62463 |
| [41] | Yoshimural, M.; Yoshimura, I., An application of the sequential dynamic programming matching method to off-line signature verification, 299-310 (1997), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg |
| [42] | Yu, C.; Luo, L.; Chan, L. L.-H.; Rakthanmanon, T.; Nutanong, S., A fast LSH-based similarity search method for multivariate time series, Information Sci., 476, 337-356 (2019) |
| [43] | Yuan, G.; Sun, P. H.; Zhao, J.; Li, D. X.; Wang, C. W., A review of moving object trajectory clustering algorithms, Artificial Intell. Rev., 47, 123-144 (2017) |
| [44] | Zhang, J.; Li, H.; Gao, Q.; Wang, H.; Luo, Y., Detecting anomalies from big network traffic data using an adaptive detection approach, Information Sci., 318, 91-110 (2015) |
| [45] | Zhang, W.; Goerlandt, F.; Montewka, J.; Kujala, P., A method for detecting possible near miss ship collisions from AIS data, Ocean Eng., 107, 60-69 (2015) |
| [46] | Zhang, Z.; Tavenard, R.; Bailly, A.; Tang, X.; Tang, P.; Corpetti, T., Dynamic time warping under limited warping path length, Information Sci., 393, 91-107 (2017) |
| [47] | Zhao, J.; Itti, L., Shapedtw: shape dynamic time warping, Pattern Recognit., 74, 171-184 (2018) |
| [48] | Zhao, L.; Shi, G., A novel similarity measure for clustering vessel trajectories based on Dynamic Time Warping, The J. Navigat., 72, 290-306 (2019) |
| [49] | Zhao, L.; Shi, G., A trajectory clustering method based on Douglas-Peucker compression and density for marine traffic pattern recognition, Ocean Eng., 172, 456-467 (2019) |
| [50] | Zheng, Y., Trajectory data mining: an overview, ACM Transactions on Intell. Syst. Technol., 6, 1-41 (2015) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
