Temporal and Frequential Metric Learning for Time Series kNN Classication

Abstract

This work proposes a temporal and frequential metric learning framework for a time series nearest neighbor classication. For that, time series are embedded into a pairwise space where a combination function is learned based on a maximum margin optimization process. A wide range of experiments are conducted to evaluate the ability of the learned metric on time series kNN classication.

Keywords

• Metric learning
• Time series
• kNN
• Classication
• Spectral metrics

Introduction

Due to their temporal and frequential nature, time series constitute complex data to analyze by standard machine learning approaches [ 1 ]. In order to classify such challenging data, distance features must be used to bring closer time series of identical classes and separate those of dierent classes. Temporal data may be compared on their values. The most frequently used value-based metrics are the Euclidean distance and the Dynamic Time Warping dtw to cope with delays [ 2, 3 ]. They can also be compared on their dynamics and frequential characteristics [ 4, 5 ]. Promising approaches aims to learn the Mahalanobis distance or kernel function for a specic classier [ 6, 7 ]. Other work investigate the representation paradigm by representating objects in a dissimilarity space where are investigated dissimilarity combinations and metric learning [ 8, 9 ]. The idea in this paper is to combine basic metrics into a discriminative one for a kNN classier. In the metric learning context for a metric learning approach driven by nearest neighbors (Weinberger & Saul [ 6 ]), we extend the work of Do & al. in [ 10 ] to temporal and frequential characteristics. The main idea is to embed pairs of time series in a space whose dimensions are basic temporal and frequential metrics, where a combination function is learned based on a large margin optimization process.

The main contributions of the paper are a) propose a new temporal and frequential metric learning framework for a time series nearest neighbors classication, b) learn a combination metric involving amplitude, behavior and frequential characteristics and c) conduct large experimentations to study the ability of learned metric. The rest of the paper is organized as follows. Section 2 recalls briey the major metrics for time series. In Section 3, we present the proposed Copyright ⃝c2015 for this paper by its authors. Copying permitted for private and academic purposes. metric learning approach. Finally, Section 4 presents the experiments conducted and discusses the results obtained. 2

Time series metrics

Let xi = (xi1; :::; xiT ) and xj = (xj1; :::; xjT ) be two time series of time length T . Time series metrics fall at least within three main categories. The rst one concerns value-based metrics, where time series are compared according to their values regardless of their behaviors. Among these metrics are the Euclidean distance (dE ), the Minkowski distance and the Mahalanobis distance [ 3 ]. We recall the formula of dE :

vu T dE (xi; xj ) = tu∑(xit − xjt)2

t=1

The second category relies on metrics in the spectral representations. In some applications, time series may be similar because they share the same frequency characteristics. For that, time series xi are rst transformed into their Fourier representation x~i = [x~i1; :::; x~iF ], where x~if is a complex number (i.e. Fourier components), with F = 22T + 1 [ 5 ]. Then, one may use the Euclidean distance (dF F T ) between the module of the complex numbers x~if , noted |x~if |: vu F dF F T (xi; xj ) = tu∑(|x~if | − |x~jf |)2 f=1 Note that times series of similar frequential characteristics may have distinctive global behavior. Thus, to compare time series based on their behavior, a third category of metrics is used. Many applications refer to the Pearson correlation or its generalization, the temporal correlation coecient [ 4 ] dened as: Cortr(xi; xj ) = ∑(xit − xit′ )(xjt − xjt′ ) t;t′ √∑(xit − xit′ )2√∑(xjt − xjt′ )2 t;t′ t;t′ (1) (2) (3) where |t − t′| ≤ r, r ∈ [1; :::; T − 1] being a parameter that can be learned or xed a priori. The optimal value of r is noisy dependant. For r = T − 1, Eq. 3 leads to the Pearson correlation. As Cortr is a similarity measure, it is transformed into a dissimilarity measure: dCortr (xi; xj ) = 12 (1 − Cortr(xi; xj )). 3

Temporal and frequential metric learning for a large margin k NN Let X = {xi; yi}iN=1 be a set of N static vector samples, xi ∈ Rp, p being the number of descriptive features and yi the class labels. Weinberger & Saul proposed in [ 6 ] an approach to learn a dissimilarity metric D for a large margin kNN. It is based on two intuitions: rst, each training sample xi should have the same label yi as its k nearest neighbors; second, training samples with dierent labels should be widely separated. For this, they introduced the concept of target for each training sample xi. Target neighbors of xi, noted j i, are the k closest xj of the same class (yj = yi). The target neighborhood is dened with respect to an initial metric. The aim is to learn a metric D that pulls the targets and pushes the ones of dierent class.

Let d1; :::; dh:::; dp be p given dissimilarity metrics that allow to compare samples. The computation of a metric always takes into account a pair of samples. Therefore, we used the pairwise representation introduced in Do & al. [ 10 ]. In this space, a vector xij represents a pair of samples (xi; xj ) described by the p basics metrics dh: xij = [d1(xi; xj ); :::; dp(xi; xj )]T . If xij = 0 then xj is identical to xi according to all metrics dh. A combination function D of the metrics dh can be seen as a function in this space. We propose in the following to use a linear combination of dh: Dw(xi; xj ) = ∑h wh:dh(xi; xj ). Its pairwise notation is Dw(xij ) = wT :xij . To ensure that Dw is a valid metric, we set wh ≥ 0 for all h = 1:::p. The main steps of the proposed approach to learn the metric, detailed hereafter, can be summarized as follows:

1. Embed each pair (xi; xj ) into the pairwise space Rp.

2. Scale the data within the pairwise space. 3. Dene for each xi its targets. 4. Scale the neighborhood of each xi. 5. Learn the combined metric Dw.

Data scaling. This operation is performed to scale the data within the pairwise space and ensure comparable ranges for the p basic metrics dh. In our experiment, we use dissimilarity measures with values in [0; +∞[. Therefore, we propose to Z-normalize their log distributions.

Target set. For each xi, we dene its target neighbors as the k nearest neighbors xj (j i) of the same class according to an initial metric. In this paper, we choose a L2-norm of the pairwise space as the initial metric (√∑h d2h). Other metrics could be chosen. We emphasize that target neighbors are xed a priori (at the rst step) and do not change during the learning process.

Neighborhood scaling . In real datasets, local neighborhoods can have very different scales. To make the target neighborhood spreads comparable, we propose for each xi to scale its neighborhood vectors xij such that the L2-norm of the farthest target is 1.

N Learning the combined metric Dw. Let {xij ; yij }i;j=1 be the training set with yij = −1 if yj = yi and +1 otherwise. Learning Dw for a large margin kNN classier can be formalized as the following optimization problem: {z pull i; yl ̸= yi;

} | Dw(xil) − Dw(xij) ≥ 1 − ijl ijl ≥ 0 wh > 0 ∀h = 1:::p Note that the "pull" term ∑Dw(xij ) = ∑wT :xij = N:k:wT :xij is a L1j i j i Mahalanobis norm weighted by the average target sample. Therefore, it behaves like a L1-norm in the optimization problem. The problem is very similar to a C-SVM classication problem. When C is innite, we have a "strict" problem: the solver will try to nd a direction in the pairwise space for which only targets are in the close neighborhood of each xi, and a maximum margin 1 . ||w||2 Let xtest be a new sample to classify and xtest;i (i = 1; :::; N ) the corresponding vectors into the pairwise embedding space. After xtest;i normalization according to the Data Scaling step, xtest is classied based on a standard kNN and Dw. 4

Experiments

In this section, we compare kNN classier performances for several metrics on reference time series datasets [1114] described in Table 1. To compare with the reference results in [ 3, 11 ], the experiments are conducted with the same protocols as in Do &. al. [ 10 ]: k is set to 1; train and test set are given a priori. Due to the current format to store the data, small datasets with short time series were retained and the experiments are conducted on one runtime.

In this experimentation, we consider basic metrics dE , dF F T and dCortr then, we learn a combined metric Dw according to the procedure described in Section 3. First, two basic temporal metrics are considered in D2 (dE and dCortr ) as in Do & al. [ 10 ]. Second, we consider a combination between temporal and frequential metrics in D3 (dE , dCortr and dF F T ). Cplex library [ 15 ] has been used to solve the optimization problem in Eq. 4. We learn the optimal parameter values of these metrics by minimizing a leave-one out cross-validation criterion. As the training dataset sizes are small, we propose a hierarchical error criterion: 1. Minimize the kNN error rate 2. Minimize ddiinnttrear if several parameter values obtain the minimum kNN error. where dintra and dinter stands respectively to the mean of all intraclass and interclass distances according to the metric at hand. Table 2 gives the range of the grid search considered for the parameters. In the following, we consider only the raw series and don’t align them using a dtw algorithm for example. For all reported results (Table 3), the best one is indexed with a star and the ones signicantly similar from the best one (Z-test at 1% risk) are in bold [ 16 ].

From Table 3, we can see that temporal metrics dE and dCortr alone performs better one from the other depending on the dataset. Using a frequential metric alone such as dF F T brings signicant improvements for some datasets (SonyAIBO, GunPoint, PowerCons, ECG5Days). It can be observed that one basic metric is sucient on some databases (MoteStrain, GunPoint, PowerCons, ECG5Days). In other cases, learning a combination of these basic metrics reach the same performances on most datasets or achieve better results (UMD). The new approach allows to extend combination functions to many metrics without having to cope with additional parameters in grid search and without to test every basic metrics alone to retained the best one. It also extends the work done in [ 6 ] for single distance to multiple distances. Adding metrics such as dF F T improves the performances on some datasets (SonyAIBO, GunPoint, UMD, FaceFour, Lighting-2, Lighting-7) than considering only temporal metrics (dE , dCortr ). However, it does not always improve the results (GunPoint, PowerCons, ECG5Days). This might be caused by the fact that our framework is sensitive to the choice of the initial metric (L2-norm) or maybe, some steps in the algorithm should be improved to make the combination better. 5

Conclusion

For nearest neighbor time series classication, we propose to learn a metric as a combination of temporal and frequential metrics based on a large margin optimization process. The learned metric shows good performances on the conducted experimentations. For future work, we are looking for some improvements. First, the choice of the initial metric is crucial. It has been set here as the L2-norm of the pairwise space but a dierent metric could provide better target sets. Otherwise, using an iterative procedure (reusing Dw to generate new target sets and learn Dw again) could be another solution. Second, we note that the L1norm on the "pull" term leads to sparcity. Changing it into a L2-norm could allow for non-sparse solutions and also extend the approach to non-linear metric combination functions thanks to the Kernel trick. Finally, we could extend this framework to multivariate, regression or clustering problems.

References

1. T.C. Fu , A review on time series data mining , Engineering Applications of Articial Intelligence , 2011 .

2. H. Sakoe and S. Chiba , Dynamic Programming Algorithm Optimization for Spoken Word Recognition, IEEE transactions on acoustics, speech , and signal processing, 1978 .

3. H. Ding , G. Trajcevski, and P. Scheuermann , Querying and Mining of Time Series Data : Experimental Comparison of Representations and Distance Measures , in VLDB , 2008 .

4. A. Douzal-Chouakria and C. Amblard , Classication trees for time series , Pattern Recognition journal , 2011 .

5. S. Lhermitte , J. Verbesselt , W.W. Verstraeten , and P. Coppin , A comparison of time series similarity measures for classication and change detection of ecosystem dynamics , 2011 .

6. K. Weinberger and L. Saul , Distance Metric Learning for Large Margin Nearest Neighbor Classication , Journal of Machine Learning Research , 2009 .

7. M. Gnen and E. Alpaydin , Multiple kernel learning algorithms , The Journal of Machine Learning Research , vol. 12 , pp. 22112268 , 2011 .

8. R. Duin , M. Bicego , M. Orozco-alzate, S. Kim, and M. Loog, Metric Learning in Dissimilarity Space for Improved Nearest Neighbor Performance , pp. 183192 .

9. A. Ibba , R. Duin , and W. Lee , A study on combining sets of dierently measured dissimilarities , in Proceedings - International Conference on Pattern Recognition , 2010 , pp. 33603363 .

10. C. Do , A. Douzal-Chouakria , S. MariØ, and M. Rombaut , Multiple Metric Learning for large margin kNN Classication of time series , EUSIPCO, 2015 .

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

12. K. Bache and M. Lichman, UCI Machine Learning Repository (http://archive .ics.uci.edu/ml), 2013 .

13. LIG-AMA Machine Learning Datasets Repository (http://ama.liglab.fr/resourcestools/datasets/), 2014 .

14. C. Frambourg , A. Douzal-Chouakria , and E. Gaussier , Learning Multiple Temporal Matching for Time Series Classication, Advances in Intelligent Data Analysis XII, 2013 .

15. IBM Cplex (http://www-01.ibm.com/software/commerce/optimization/cplexoptimizer/), .

16. T. Dietterich, Approximate Statistical Tests for Comparing Supervised Classication Learning Algorithms , 1997 .