=Paper=
{{Paper
|id=Vol-1425/paper6
|storemode=property
|title=Temporal and Frequential Metric Learning for Time Series kNN Classification
|pdfUrl=https://ceur-ws.org/Vol-1425/paper6.pdf
|volume=Vol-1425
|dblpUrl=https://dblp.org/rec/conf/pkdd/DoCMR15
}}
==Temporal and Frequential Metric Learning for Time Series kNN Classification==
https://ceur-ws.org/Vol-1425/paper6.pdf
Proceedings 1st International Workshop on Advanced Analytics and Learning on Temporal Data
AALTD 2015
Temporal and Frequential Metric Learning
for Time Series kNN Classi cation
Cao-Tri Do123 , Ahlame Douzal-Chouakria2 , Sylvain Marié1 , and Michèle
Rombaut3
1
Schneider Electric, France
LIG, University of Grenoble Alpes, France
2
3
GIPSA-Lab, University of Grenoble Alpes, France
Abstract. This work proposes a temporal and frequential metric learn-
ing framework for a time series nearest neighbor classi cation. 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 classi cation.
Keywords: Metric learning, Time series, kNN, Classi cation, Spectral metrics.
1 Introduction
Due to their temporal and frequential nature, time series constitute complex
data to analyze by standard machine learning approaches [1]. In order to clas-
sify 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 met-
rics 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 dis-
tance or kernel function for a speci c classi er [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 k NN
classi er. 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 frequen-
tial 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 fre-
quential metric learning framework for a time series nearest neighbors classi ca-
tion, b) learn a combination metric involving amplitude, behavior and frequen-
tial 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
brie y the major metrics for time series. In Section 3, we present the proposed
Copyright⃝
c 2015 for this paper by its authors. Copying permitted for private and academic
purposes.
2 C.-T. Do, A. Douzal-Chouakria, S. Marié, M. Rombaut
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 :
v
u T
u∑
Ed (x , x ) = t (x − x )2
i j it jt (1)
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
T
components), with F = 22 + 1 [5]. Then, one may use the Euclidean distance
(dF F T ) between the module of the complex numbers x̃if , noted |x̃if |:
v
u F
u∑
dF F T (xi , xj ) = t (|x̃if | − |x̃jf |)2 (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 coe cient [4] de ned as:
∑
(xit − xit′ )(xjt − xjt′ )
t,t′
Cortr (xi , xj ) = √∑ √∑ (3)
(xit − xit′ )2 (xjt − xjt′ )2
t,t′ t,t′
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 }N
i=1 be a set of N static vector samples, xi ∈ R , p being the
p
number of descriptive features and yi the class labels. Weinberger & Saul pro-
posed in [6] an approach to learn a dissimilarity metric D for a large margin
Temporal and Frequential Metric Learning for Time Series k NN Classif. 3
k NN. 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 de ned 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 sam-
ples. 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 identi-
cal 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. De ne 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 de ne 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 dh ). Other
2
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 dif-
ferent 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.
Learning the combined metric Dw . Let {xij , yij }Ni,j=1 be the training set with
yij = −1 if yj = yi and +1 otherwise. Learning Dw for a large margin k NN
classi er can be formalized as the following optimization problem:
4 C.-T. Do, A. Douzal-Chouakria, S. Marié, M. Rombaut
∑ ∑ 1 + yil
min Dw (xij ) + C .ξijl
w,ξ
i,j i
2
i,j i,l
| {z } | {z }
pull push
s.t. ∀j i, yl ̸= yi , (4)
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 .x̄ij is a L1-
j 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 classi cation problem. When C is in nite, 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 ||w1||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 classi ed based on a standard k NN and Dw .
4 Experiments
In this section, we compare k NN classi er 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 proto-
cols 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 k NN error rate
2. Minimize ddintra
inter
if several parameter values obtain the minimum k NN 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
Temporal and Frequential Metric Learning for Time Series k NN Classif. 5
all reported results (Table 3), the best one is indexed with a star and the ones
signi cantly similar from the best one (Z-test at 1% risk) are in bold [16].
Dataset Nb. Class Nb. Train Nb. Test TS length
SonyAIBO 2 20 601 70
MoteStrain 2 20 1252 84
GunPoint 2 50 150 150
PowerCons 2 73 292 144
ECG5Days 2 23 861 136
SonyAIBOII 2 27 953 65
Coee 2 28 28 286
BME 3 48 102 128
UMD 3 46 92 150
ECG200 2 100 100 96
Beef 5 30 30 470
DiatomSizeReduction 4 16 306 345
FaceFour 4 24 88 350
Lighting-2 2 60 61 637
Lighting-7 7 70 73 319
OliveOil 4 30 30 570
Table 1. Dataset description giving the number of classes (Nb. Class), the number of
time series for the training (Nb. Train) and the testing (Nb. Test) sets, and the length
of each time series (TS length).
Method Parameter Parameter range
dCortr r [1, 2, 3, , ..., T ]
D2 , D 3 C [10−3 , 0.5, 1, 5, 10, 20, 30, ..., 150]
Table 2. Parameter ranges
From Table 3, we can see that temporal metrics dE and dCortr alone per-
forms better one from the other depending on the dataset. Using a frequential
metric alone such as dF F T brings signi cant improvements for some datasets
(SonyAIBO, GunPoint, PowerCons, ECG5Days). It can be observed that one
basic metric is su cient 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 with-
out 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
6 C.-T. Do, A. Douzal-Chouakria, S. Marié, M. Rombaut
Metrics
Dataset Basic Learned combined
dE dCortr dF F T D2 D3
SonyAIBO 0.305 0.308 0.258* 0.308 0.259
MoteStrain 0.121* 0.264 0.278 0.210 0.277
GunPoint 0.087 0.113 0.027* 0.113 0.073
PowerCons 0.370 0.445 0.315* 0.384 0.410
ECG5Days 0.203 0.153 0.006* 0.153 0.156
SonyAIBOII 0.141 0.142 0.128* 0.142 0.142
Coee 0.250 0* 0.357 0* 0*
BME 0.128 0.059* 0.412 0.059* 0.078
UMD 0.185* 0.207 0.315 0.207 0.185*
ECG200 0.120 0.070* 0.166 0.070* 0.070*
Beef 0.467 0.300* 0.500 0.300* 0.367
DiatomSizeReduction 0.065* 0.075 0.069 0.075 0.075
FaceFour 0.216 0.216 0.239 0.216 0.205*
Lighting-2 0.246 0.246 0.148* 0.246 0.213
Lighting-7 0.425 0.411 0.315 0.411 0.288*
OliveOil 0.133* 0.133* 0.200 0.133* 0.133*
Table 3. Error rate of 1NN classi er for dierent metrics. D2 is computed using dE
and dCortr ; D3 uses the 3 basic metrics. The metric with the best performance for
each dataset is indicated by a star (*) and the ones with equivalent performances are
in bold.
(dE , dCortr ). However, it does not always improve the results (GunPoint, Pow-
erCons, 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 classi cation, we propose to learn a metric as a
combination of temporal and frequential metrics based on a large margin opti-
mization 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 L1-
norm 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.
Temporal and Frequential Metric Learning for Time Series k NN Classif. 7
References
1. T.C. Fu, A review on time series data mining, Engineering Applications of
Arti cial Intelligence, 2011.
2. H. Sakoe and S. Chiba, Dynamic Programming Algorithm Optimization for Spo-
ken Word Recognition, IEEE transactions on acoustics, speech, and signal pro-
cessing, 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, Classi cation 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 classi cation and change detection of ecosystem
dynamics, 2011.
6. K. Weinberger and L. Saul, Distance Metric Learning for Large Margin Nearest
Neighbor Classi cation, Journal of Machine Learning Research, 2009.
7. M. Gönen 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 Learn-
ing for large margin kNN Classi cation of time series, EUSIPCO, 2015.
11. E. Keogh, Q. Zhu, B. Hu, Y. Hao, X. Xi, L. Wei, and C.A. Ratanama-
hatana, The UCR Time Series Classi cation/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 Tempo-
ral Matching for Time Series Classi cation, Advances in Intelligent Data Analysis
XII, 2013.
15. IBM Cplex (http://www-01.ibm.com/software/commerce/optimization/cplex-
optimizer/), .
16. T. Dietterich, Approximate Statistical Tests for Comparing Supervised Classi -
cation Learning Algorithms, 1997.