Time series classification in the dissimilarity space combines the advantages of the dynamic time warping and the rich mathematical structure of Euclidean spaces. We applied dimension reduction using PCA followed by support vector learning on dissimilarity representations to 43 UCR datasets. Results indicate that time series classification in dissimilarity space has potential to complement the state-of-the-art.
2.1
A time series of length n is an ordered sequence x = (x1; : : : ; xn) with features xi 2 R sampled at discrete points of time i 2 [n] = f1; : : : ; ng. To define the DTW distance between time series x and y of length n and m, resp., we construct a grid G = [n] [m]. A warping path in grid G is a sequence = (t1; : : : ; tp) consisting of points tk = (ik; jk) 2 G such that 1. t1 = (1; 1) and tp = (n; m) 2. tk+1 tk 2 f(1; 0); (0; 1); (1; 1)g (boundary conditions) (warping conditions) for all 1 along
k < p. The cost of warping x = (x1; : : : ; xn) and y = (y1; : : : ; ym) is defined by d (x; y) =
X (xi
yj )2; (i;j)2 where (xi yj )2 is the local transformation cost of assigning features xi to yj . Then the distance function
d(x; y) = min d (x; y); is the dynamic time warping (DTW) distance between x and y, where the minimum is taken over all warping paths in G. 2.2
Let (T ; d) be a time series space T endowed with the DTW distance d. Suppose that we are given a subset
P = fp1; : : : ; pkg
T of k reference time series pi 2 T , called prototypes henceforth. The set P of prototypes gives rise to a function of the form : T ! Rk;
x 7! (d(x; p1); : : : ; d(x; pk)); where Rk is the dissimilarity space of (T ; d) with respect to P. The k-dimensional vector (x) is the dissimilarity representation of x. The i-th feature of (x) represents the dissimilarity d(x; pi) between x and the i-th prototype pi. 2.3
Suppose that
X = f(x1; y1); : : : ; (xn; yn)g
T
is a training set consisting of n time series xi with corresponding class labels
yi 2 Y. Learning in dissimilarity space proceeds in three steps: (
The performance of a classifier learned in dissimilarity spaces crucially depends on a proper dissimilarity representation of the time series. We distinguish between two common approaches: 1. Prototype selection: construct a set of prototypes P from the training set X . 2. Dimension reduction: perform dimension reduction in the dissimilarity space.
There are numerous strategies for prototype selection. Naive examples include all elements of the training set X and sampling a random subset of X . For more sophisticated selection methods, we refer to [8]. Dimension reduction of the dissimilarity representation includes methods such as, for example, principal component analysis (PCA). 3
The goal of this experiment is to assess the performance of the following classifiers
in dissimilarity space: (
We considered 43 datasets from the UCR time series datasets [4], each of which comes with a pre-defined training and test set. For each dataset we used the whole training set as prototype set. To embed the training and test examples into a dissimilarity space, we computed their DTW distances to the prototypes.
We trained all SVMs with RBF-kernel using the embedded training examples. We selected the parameters and C of the RBF-kernel over a two-dimensional grid with points ( i; Cj ) = (2i; 2j ), where i; j are 30 equidistant values from [ 10; 10]. For each parameter configuration ( i; Cj ) we performed 10-fold crossvalidation and selected the parameters ( ; C ) with the lowest average classification error. Then we trained the SVM on the whole embedded training set using the selected parameters ( ; C ). Finally, we applied the learned model to the embedded test examples for estimating the generalization performance.
For PCA+SVM we performed dimension reduction using PCA prior training of the SVM. We considered the q first dimensions with highest variance, where q 2 f1; 1 + a; 1 + 2a; : : : : ; 1 + 19ag with a being the closest integer of k=20 and k is the dimension of the dissimilarity space. For each q, we performed hyperparameter selection for the SVM as described above. We selected the parameter configuration (q ; ; C ) that gave the lowest classification error. Then we applied PCA on the whole embedded training set, retained the first q dimensions and trained the SVM on the embedded training set after dimension reduction. 80 S 60 D -‐ D E 40 20 0 100 80 VM60 S+ CPA40 20 0 Finally we reduced the dimension of the embedded test examples and applied the learned model. 3.2
Figure 1 shows the scatter plots of predictive accuracy of the nearest neighbor using DTW against all three dissimilarity space methods and Table 1 shows the error rates of all classifiers for each dataset.
The first observation to be made is that the dissimilarity space endowed with the Euclidean space is less discriminative than the time series space endowed with the DTW distance. As shown by Figure 1, nearest neighbor (NN) with DTW performed better than the ED-DS classifier in 34 out of 42 cases. Since the DTW distance is non-Euclidean, dissimilarity spaces form a distorted representation of the time series space in such a way that neighborhood relations are not preserved. In most cases, these distortions impact classification results negatively, often by a large margin. In the few cases where the distortions improve classification DTW
ED-DS
SVM results, the improvements are only small and could also be occurred by chance due to the random sampling of the training and test set.
The second observation to be made is that the SVM using all prototypes complements NN+DTW. Better and worse predictive performance of both classifiers is balanced. This shows that powerful learning algorithms can partially compensate for poor representations.
The third observation to be made is that SVM+PCA outperformed all other classifiers. Furthermore, SVM+PCA is better than NN+DTW in 28 and worse in 9 out of 42 cases. By reducing the dimension using PCA, we obtain better dissimilarity representations for classification. Table 1 highlights relative improvements and declines of PCA+SVM compared to NN+DTW with 10% or more in blue and red color, respectively. We observe a relative change of at least 10% in 27 out of 43 cases. This finding supports our hypothesis that learning on dissimilarity representations complements NN+DTW. 4
This paper is a first step to explore dissimilarity space learning for time series classification under DTW. Results combining PCA with SVM on dissimilarity representations are promising and complement nearest neighbor methods using DTW in time series spaces. Future work aims at exploring further elastic distances, prototype selection, dimension reduction, and learning methods.