A key component of many types of time series classification methods is an appropriate
dissimilarity measure. Elastic measures like DTW, LCS, ERP and EDR are methods that have
long been known in the time series community. The methods have flourished, particularly in
the last decade, and have been applied to many real problems in a variety of branches. All
of the above-mentioned measures have the common feature that they work in the time domain
and equalize for possible localized misalignment through some elastic adaptation. However,
being of quadratic time complexity, global constraints are often used to speed up
computation. Apart from this advantage, it has been shown by simulations that constrained
measures can also give better classification results than unconstrained measures.
In this paper, our aim is to verify experimentally the effects of the Sakoe–Chiba band on
classification (by the 1NN method) with the above-mentioned measures. Using rigorous
statistical analysis we demonstrate that it is possible to find global constraints which
lead to improvement of the classification accuracy for all methods. Additionally, for each
measure we suggest the best values of the parameter r (the size of the
band).
AbulO., BonchiF. and NanniM.,
Anonymization of moving objects databases by clustering and
perturbation, Information Systems35 (2010),
884–910.
2.
BagnallA. and LinesJ.,
Technical Report CMP-C14-01: An Experimental Evaluation of Nearest
Neighbour Time Series Classification, arXiv:1406.4757v1,
2014.
3.
BagnallA., BostromA., LargeJ.
and LinesJ.,
The great time series classification bake off: An experimental evaluation
of recently proposed algorithms, Extended Version
(2016), arXiv:1602.0711v1.
4.
BatistaG., WangX.
and KeoghE., A
complexityinvariant distance measure for time series,
Proceedings of the Eleventh SIAM Conference on Data Mining (SDM)
(2011).
5.
BergmannG., HommelG.,
Improvements of general multiple test procedures for redundant systems of
hypotheses, in BauerP., HommelG. and SonnemannE. (Eds),
Multiple Hypotheses Testing, Springer,
1988, pp. 110–115.
6.
BerndtD.J. and CliffordJ.,
Using dynamic time warping to find patterns in time
series, AAAI Workshop on Knowledge Discovery in
Databases, 1994,
pp.229–248.
7.
ChenL. and NgR.,
On The Marriage of Lp-norms and Edit Distance,
In: Proceedings of the Thirtieth International Conference on Very Large
Databases30, 2004, pp.
792–803.
8.
ChenL., ÖzsuM.T., OriaV.,
Robust and fast similarity search for moving object
trajectories, In Proceedings of the 2005 ACM SIGMOD
International Conference on Management of Data, New York,
ACM, NY, USA, pp.
491–502.
DauH.A., SilvaD.F., PetitjeanF., ForestierG., BagnallA., MueenA.
and KeoghE.,
Optimizing dynamic time warping’s window width for time series data
mining applications, Data Mining and Knowledge
Discovery (2018). 10.1007/s10618-018-0565-y.
11.
DemšarJ.,
Statistical comparisons of classifiers over multiple data
sets, Journal of Machine Learning Research7 (2006),
1–30.
12.
DingH., TrajcevskiG., ScheuermannP., WangX.
and KeoghE.,
Querying and mining of time series data: Experimental comparison of
representations and distance measures, Proc VLDB Endow1 (2008),
1542–1552.
13.
GarcíaS. and HerreraF.,
An extension on “statistical comparisons of classifiers over multiple
data sets” for all pairwise comons, Journal of Machine Learning
Research9 (2008),
2677–2694.
14.
GelerZ., KurbalijaV., RadovanovićM. and
IvanovićM.,
Impact of the sakoe-chiba band on the DTWTime-series distance measure for
kNN classification, In: Knowledge Science, Engineering and
Management, Lecture Notes in Computer Science8793 (2014),
105–114.
15.
GóreckiT.,
Using derivatives in a longest common subsequence dissimilarity measure
for time series classification, Pattern Recognition
Letters45C (2014),
99–105.
16.
GóreckiT. and ŁuczakM.,
Using derivatives in time series classification,
Data Mining and Knowledge Discovery26(2) (2013),
310–331.
17.
GóreckiT. and ŁuczakM.,
Multivariate time series classification with parametric derivative
dynamic time warping, Expert Systems with Applications42(5) (2015),
2305–2312.
18.
ImanR. and DavenportJ.,
Approximations of the critical region of the Friedman
statistic, Communications in Statistics - Theory and
Methods9(6) (1980),
571–595.
19.
ItakuraF.,
Minimum prediction residual principle applied to speech
recognition, IEEE Trans Acoustics Speech Signal Process23 (1975),
52–72.
20.
KeoghE. and PazzaniM.,
Dynamic Time Warping with Higher Order Features,
In Proc SIAM International Conference on Data Mining (SDM’2001) In
Chicago, USA2001.
21.
KeoghE., RatanamahatanaC.A.,
Exact indexing of dynamic time warping,
In: Proceedings of the 26th Int’l Conference on Very Large Data
Bases, Hong Kong2002, pp. 406–417.
KurbalijaV., RadovanovićM., GelerZ., IvanovićM.The Influence of Global Constraints on DTW and LCS Similarity Measures for
Time-Series Databases. In: DichevaD., MarkovZ. and StefanovaE., (Eds.),
Third International Conference on Software Services and Semantic Technologies
S3T 2011 SE - 10, Sringer Berlin Heidelberg,
2011 pp.67–74.
24.
KurbalijaV., RadovanovićM., GelerZ.
and IvanovićM.,
The influence of global constraints on similarity measures for
time-series databases, Knowledge-Based Systems56(1) (2014),
49–67.
25.
ŁuczakM.,
Hierarchical clustering of time series data with parametric derivative
dynamic time warping, Expert Systems with Applications62 (2016),
116–130.
PelekisN., KopanakisI., KotsifakosE.E.,
FrentzosE., TheodoridisY.,
Clustering Trajectories of Moving Objects in an Uncertain
World, In: Data Mining 2009 ICDM’09 Ninth IEEE International
Conference On, 2009, pp. 417–427
28.
RadovanovićM.,
NanopoulosA. and
IvanovićM.,
Timeseries classification in many intrinsic dimensions,
In 10th SIAM International Conference on Data Mining (SDM’2010),
Columbus, USA, 2010,
pp.677–688.
29.
RatanamahatanaC.A.,
KeoghE.,
Three myths about dynamic time warping data mining, In:
Proceedings of SIAM International Conference on DataMining
(SDM’05), 2005, pp.
506–510.
30.
SakoeH. and ChibaS.,
Dynamic programming algorithm optimization for spoken word
recognition, IEEE Transactions on Acoustics, Speech, and Signal
Processing26(1) (1978),
43–49.
31.
TomaševN. and MladenićD.,
Nearest Neighbor voting in high dimensional data: Learning from past
occurrences, Computer Science and Information Systems9 (2012),
691–712.
32.
VlachosM., KolliosG., GunopulosD.,
Discovering similar multidimensional trajectories, In:
Proceedings 18th International Conference on Data Engineering IEEE Comput
Soc, 2002, pp.
673–684.
33.
XiX., KeoghE., SheltonC., WeiL.,
RatanamahatanaC.A.Fast time series classification using numerosity reduction,
In: Proceedings of the 23rd International Conference on Machine Learning
ACM, New York NY, USA. 2006,
pp.1033–1040.
34.
WuX., KumarV., QuinlanJ.R., GhoshJ., YangQ.,
MotodaH., McLachlanG.J., NgA.,
LiuB., YuP.S.,
ZhouZ., SteinbachM., HandD.J. and SteinbergD.,
Top 10 algorithms in data mining, Knowledge
Information Systems14(1) (2008),
1–37.
35.
ZhangD., ZuoW.,
ZhangD., ZhangH.
and LiN.,
Classification of pulse waveforms using edit distance with real
penalty, EURASIP Journal on Advances in Signal
Processing28 (2010),
1–28.
