Bag-of-Temporal-SIFT-Words for Time Series Classi cation

Abstract

Time series classi cation is an application of particular interest with the increase of data to monitor. Classical techniques for time series classi cation rely on point-to-point distances. Recently, Bag-ofWords approaches have been used in this context. Words are quantized versions of simple features extracted from sliding windows. The SIFT framework has proved e cient for image classi cation. In this paper, we design a time series classi cation scheme that builds on the SIFT framework adapted to time series to feed a Bag-of-Words. Experimental results show competitive performance with respect to classical techniques.

Keywords

• time series classi cation
• Bag-of-Words
• SIFT
• BoTSW

Introduction

Copyright c 2015 for this paper by its authors. Copying permitted for private and academic purposes. words correspond to the description of local gradients around keypoints, that are rst extracted from the time series. This approach can be seen as an adaptation of the SIFT framework to time series.

This paper is organized as follows. Section 2 summarizes related work, Section 3 describes the proposed Bag-of-Temporal-SIFT-Words (BoTSW) method, and Section 4 reports experimental results. Finally, Section 5 concludes and discusses future work. 2

Related work

Our approach for time series classi cation builds on two well-known methods in computer vision: local features are extracted from time series using a SIFTbased approach and a global representation of time series is built using Bagof-Words. This section rst introduces state-of-the-art methods in time series classi cation, then presents standard approaches for extracting features in the image classi cation context and nally lists previous works that make use of such approaches for time series classi cation.

Data mining community has, for long, investigated the eld of time series classi cation. Early works focus on the use of dedicated metrics to assess similarity between time series. In [ 11 ], Ratanamahatana and Keogh compare Dynamic Time Warping to Euclidean Distance when used with a simple kNN classi er. While the former bene ts from its robustness to temporal distortions to achieve high e ciency, ED is known to have much lower computational cost. Cuturi [ 4 ] shows that DTW fails at precisely quantifying dissimilarity between non-matching sequences. He introduces Global Alignment Kernel that takes into account all possible alignments to produce a reliable dissimilarity metric to be used with kernel methods such as Support Vector Machines (SVM). Douzal and Amblard [ 5 ] investigate the use of time series metrics for classi cation trees.

So as to e ciently classify images, those rst have to be described accurately. Both local and global descriptions have been proposed by the computer vision community. For long, the most powerful local feature for images was SIFT [ 10 ] that describes detected keypoints in the image using the gradients in the regions surrounding those points. Building on this, Sivic and Zisserman [ 13 ] suggested to compare video frames using standard text mining approaches in which documents are represented by word histograms, known as Bag-of-Words (BoW). To do so, authors map the 128-dimensional space of SIFT features to a codebook of few thousand words using vector quantization. VLAD (Vector of Locally Aggregated Descriptors) [ 6 ] are global features that build upon local ones in the same spirit as BoW. Instead of storing counts for each word in the dictionary, VLAD preserves residuals to build a ne-grain global representation.

Inspired by text mining, information retrieval and computer vision communities, recent works have investigated the use of Bag-of-Words for time series classi cation [ 1, 2, 9, 12, 14 ]. These works are based on two main operations: converting time series into Bag-of-Words (a histogram representing the occurrence of words), and building a classi er upon this BoW representation. Usually, classical techniques are used for the classi cation step: random forests, SVM, neural networks, kNN. In the following, we focus on explaining how the conversion of time series into BoW is performed in the literature. In [ 2 ], local features such as mean, variance, extremum values are computed on sliding windows. These features are then quantized into words using a codebook learned by a class probability estimate distribution. In [ 14 ], discrete wavelet coe cients are extracted on sliding windows and then quantized into words using k-means. In [ 9, 12 ], words are constructed using the SAX representation [ 8 ] of time series. SAX symbols are extracted from time series and histograms of n-grams of these symbols are computed. In [ 1 ], multivariate time series are transformed into a feature matrix, whose rows are feature vectors containing a time index, the values and the gradient of time series at this time index (on all dimensions). Random samples of this matrix are given to decision trees whose leaves are seen as words. A histogram of words is output when the di erent trees are learned. Rather than computing features on sliding windows, authors of [ 15 ] rst extract keypoints from time series. These keypoints are selected using the Di erences-of-Gaussians (DoG) framework, well-known in the image community, that can be adapted to onedimensional signals. Keypoints are then described by scale-invariant features that describe the shapes of the extremum surrounding keypoints. In [ 3 ], extraction and description of time series keypoints in a SIFT-like framework is used to reduce the complexity of Dynamic Time Warping: features are used to match anchor points from two di erent time series and prune the search space when nding the optimal path in the DTW computation.

In this paper, we design a time series classi cation technique based on the extraction and the description of keypoints using a SIFT framework adapted to time series. The description of keypoints is quantized using a k-means algorithm to create a codebook of words and classi cation of time series is performed with a linear SVM fed with normalized histograms of words. 3

Bag-of-Temporal-SIFT-Words (BoTSW) method

The proposed method is adapted from the SIFT framework [ 10 ] widely used for image classi cation. It is based on three main steps : (i) detection of keypoints (scale-space extrema) in time series, (ii) description of these keypoints by gradient magnitude at a speci c scale, and (iii) representation of time series by a BoW, words corresponding to quantized version of the description of keypoints. These steps are depicted in Fig. 1 and detailed below.

Following the SIFT framework, keypoints in time series correspond to local extrema both in terms of scale and location. These scale-space extrema are identi ed using a DoG function, which establishes a list of scale-invariant keypoints. Let L(t; ) be the convolution ( ) of a Gaussian function G(t; ) of width with a time series S(t):

L(t; ) = G(t; ) S(t): DoG is obtained by subtracting two time series ltered at consecutive scales: D(t; ) = L(t; ksc )

L(t; ); where ksc controls the scale ratio between two consecutive scales. A keypoint is detected at time index t and scale j if it corresponds to an extremum of D(t; ksjc ) in both time and scale (8 neighbors : 2 at the same scale, and 6 in adjacent scales) If a point is higher (or lower) than all of its neighbors, it is considered as an extremum in the scale-space domain and hence a keypoint of S.

Next step in our process is the description of keypoints. A keypoint at (t; j) is described by gradient magnitudes of L( ; ksjc ) around t. nb blocks of size a are selected around the keypoint. Gradients are computed at each point of each block and weighted using a Gaussian window of standard deviation a 2nb so that points that are farther in time from the detected keypoint have lower in uence. Then, each block is described by storing separately the sums of magnitude of positive and negative gradients. Resulting feature vector is of dimension 2 nb.

Features are then quantized using a k-means algorithm to obtain a codebook of k words. Words represent di erent kinds of local behavior in the time series. For a given time series, each feature vector is assigned to the closest word of the codebook. The number of occurrences of each word in a time series is computed. The BoTSW representation of a time series is the normalized histogram (i.e. frequency vector) of word occurrences. These histograms are then passed to a classi er to learn how to discriminate classes from this BoTSW description. 4

Experiments and results

In this section, we investigate the impact of both the number of blocks nb and the number of words k in the codebook (de ned in Section 3) on classi cation error rates. Experiments are conducted on 20 datasets from the UCR repository [ 7 ]. We set all parameters of BoTSW but nb and k as follows : = 1:6, ksc = 21=3, a = 8. These values have shown to produce stable results. Parameters nb and k vary inside the following sets : f2; 4; 6; 8; 10; 12; 14; 16g and 2i; 8 i 2 f2::10g respectively. Codebooks are obtained via k-means quantization. Two classi ers are used to classify times series represented as BoTSW : a linear SVM or a 1NN classi er. Each dataset is composed of a train and a test set. For our approach, the best set of (k; nb) parameters is selected by performing a leave-one-out crossvalidation on the train set. This best set of parameters is then used to build the classi er on the train set and evaluate it on the test set. Experimental error rates (ER) are reported in Table 1, together with baseline scores publicly available at [ 7 ]. 0.5 0.4 te 0.3 rrao rrE 0.2

BoTSW coupled with a linear SVM is better than both ED and DTW on 11 datasets. It is also better than BoTSW coupled with a 1NN classi er on 13 datasets. We also compared our approach with classical techniques for time series classi cation. We varied number of codewords k between 4 and 1024. Not surprisingly, cross-validation tends to select large codebooks that lead to more precise representation of time series by BoTSW. Fig. 2 shows undoubtedly that, for Yoga dataset, (left) the larger the codebook, the better the results and (right) the choice of the number nb of blocks is less crucial as a wide range of values yield competitive classi cation performance.

Win-Tie-Lose scores (see Table 2) show that coupling BoTSW with a linear SVM reaches competitive performance with respect to the literature.

As it can be seen in Table 1, BoTSW is (by far) less e cient than both ED and DTW for dataset Adiac. As BoW representation maps keypoint descriptions into words, details are lost during this quantization step. Knowing that only very few keypoints are detected for these Adiac time series, we believe a more precise representation would help. 5

Conclusion

BoTSW transforms time series into histograms of quantized local features. Distinctiveness of the SIFT keypoints used with Bag-of-Words enables to e ciently and accurately classify time series, despite the fact that BoW representation ignores temporal order. We believe classi cation performance could be further improved by taking time information into account and/or reducing the impact of quantization losses in our representation.

Acknowledgments

This work has been partly funded by ANR project ASTERIX (ANR-13-JS020005-01), Region Bretagne and CNES-TOSCA project VEGIDAR.

References

1. M. G. Baydogan and G. Runger . Learning a symbolic representation for multivariate time series classi cation . DMKD , 29 ( 2 ): 400 { 422 , 2015 .

2. M. G. Baydogan , G. Runger, and E. Tuv . A Bag-of-Features Framework to Classify Time Series . IEEE PAMI , 35 ( 11 ): 2796 { 2802 , 2013 .

3. K. S. Candan , R. Rossini , and M. L. Sapino . sDTW: Computing DTW Distances using Locally Relevant Constraints based on Salient Feature Alignments . Proc. VLDB , 5 ( 11 ): 1519 { 1530 , 2012 .

4. M. Cuturi . Fast global alignment kernels . In Proc. ICML , pages 929 { 936 , 2011 .

5. A. Douzal-Chouakria and C. Amblard . Classi cation trees for time series . Elsevier Pattern Recognition , 45 ( 3 ): 1076 { 1091 , 2012 .

6. H. Jegou , M. Douze , C. Schmid , and P. Perez . Aggregating local descriptors into a compact image representation . In Proc. CVPR , pages 3304 { 3311 , 2010 .

7. E. Keogh , Q. Zhu , B. Hu , Y. Hao , X. Xi , L. Wei , and C. A. Ratanamahatana . The UCR Time Series Classi cation/Clustering Homepage , 2011 . www.cs.ucr.edu/~eamonn/time_series_data/.

8. J. Lin , E. Keogh , S. Lonardi , and B. Chiu . A symbolic representation of time series, with implications for streaming algorithms . In Proc. ACM SIGMOD Workshop on Research Issues in DMKD , pages 2 { 11 , 2003 .

9. J. Lin , R. Khade , and Y. Li . Rotation-invariant similarity in time series using bag-of-patterns representation . IJIS , 39 : 287 { 315 , 2012 .

10. D. G. Lowe . Distinctive image features from scale-invariant keypoints . IJCV , 60 ( 2 ): 91 { 110 , 2004 .

11. C. A. Ratanamahatana and E. Keogh . Everything you know about dynamic time warping is wrong . In Proc. ACM SIGKDD Workshop on Mining Temporal and Sequential Data , pages 22 { 25 , 2004 .

12. P. Senin and S. Malinchik. SAX-VSM: Interpretable Time Series Classi cation Using SAX and Vector Space Model . Proc. ICDM , pages 1175 { 1180 , 2013 .

13. J. Sivic and A. Zisserman. Video Google : A text retrieval approach to object matching in videos . In Proc. ICCV , pages 1470 { 1477 , 2003 .

14. J. Wang , P. Liu, M. F.H. She , S. Nahavandi , and A. Kouzani . Bag-of-words Representation for Biomedical Time Series Classi cation . BSPC , 8 ( 6 ): 634 { 644 , 2013 .

15. J. Xie and M. Beigi . A Scale-Invariant Local Descriptor for Event Recognition in 1D Sensor Signals . In Proc. ICME , pages 1226 { 1229 , 2009 .