Ramer-Douglas-Peucker Dynamic Time Warping (RDP-DTW): A Novel Data Reduction Based Dynamic Time Warping method for Time Series Classification

In this paper, we propose a variant of DTW that is based on Ramer Douglas Peucker line simplification algorithm (RDPLSA). We call the proposed method Ramer Douglas Peucker Dynamic Time Warping (RDP-DTW). The RDP-DTW is used here for time series classification with the specific aim of accurately and rapidly evaluating the similarity between two given time series without losing much of the significant data information. For that purpose, the RDP-DTW is combined with the 1NN (1 Nearest Neighbor) classifier. The proposed RDP-DTW consists of two steps. The first is a line simplification approach (RDPLSA). The RDPLSA proceeds to selecting the most significant points on the line of the time series according to a simplification tolerated error (say, $\epsilon$-Simp). The RDPLSA recursively partitions the line data and controls the compression quality based on $\epsilon$-Simp. This step is performed on the two-time series to match. The second step is to adjust the dynamic time warping (DTW) alignment method on the two obtained time series generated after dimension reduction. Experimental results are carried out on the $\mathbf{8 5}$ benchmark datasets from the UCR (University of California at Riverside) time-series classification archive. Results show the outperformance of the proposed method over 1NN LE-DTW (Local Extrema DTW) [1] a recently published time series classifier and the 1NN ED (Euclidean distance) classifier, on the number of wins and the average error rates.