Novel Approaches Towards Fast and Accurate Time series Classification

A time series is a collection of values made or recorded over time. Dynamic Time Warping (DTW) is an algorithm for measuring similarity between two time series. DTW is one the most successful similarity measure in time series data mining. First-Nearest-Neighbor Dynamic Time Warping (1-NN DTW) is the most widely used classification method on time series. Multiple recent studies show that for the problem of time series classification, 1-NN DTW is very hard to beat. The disadvantage of DTW is its quadratic complexity in the length of time series. The focus of this research is improving the efficiency of DTW while retaining its accuracy level on time series classification. The first contribution of this thesis is that, it proposes a new approximation called Control Chart Approximation (CCA). CCA representation approximates raw time series by transforming them into a set of segments with aggregated values and durations forming a reduced 3-dimensional vector. The CCA transformation attempts to reduce noise, dimensionality, and storage of time series, while retaining the significant features of the original time series. The second contribution of this thesis is extension of DTW in three dimension space as a distance measure for a 1-NN classifier. The method is called 1-Nearest Neighbor 3-Dimensional Dynamic Time Warping (1-NN 3D DTW). CCA and 1-NN 3D DTW, have focused on the reduction of data, while improving the processing time of 1-NN DTW on classification of long time series. The third contribution consists of developing Blocked Dynamic Time Warping (BDTW), a new similarity measure which works on run-length encoded time series. BDTW algorithm utilizes the repetition of values in time series to calculate the exact DTW for any- two-valued time series, and to calculate a close approximation of DTW for more-than-two-valued time series with repetition of any values. By combining BDTW and Adaptive Piecewise Constant Approximation (APCA) method, a new DTW approximation method is proposed which works for all type of time series (even without repetition of values). The effectiveness of the 3D DTW and BDTW are shown on different applications, using the case studies and 85 datasets in UCR time series classification archive.