Dynamic time warping

Algorithm

Biology

Time series

Data mining

Computer science

Paleontology

Physics

Trajectory

Pattern recognition (psychology)

Mathematics

Astronomy

Artificial intelligence

Geometry

Series (stratigraphy)

Measure (data warehouse)

Cluster analysis

Point (geometry)

Machine learning

Information Sciences

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.

Adaptively constrained dynamic time warping for time series classification and clustering