Interpretability is as important in data analytics on time series data as in other areas of analytics. For this reason, k-Nearest Neighbour methods have an important part to play; however coming up with e ective similarity/distance measures is not straightforward given the nature of time series data. In this paper we survey the state-of-the-art distance measures used for time series analysis and evaluate their e ectiveness on sample regression and classi cation tasks. In some circumstances, a `global' method such as Dynamic Time Warping is e ective, whereas for other datasets `feature-based' methods work better.
Introduction
k-Nearest Neighbour (k-NN) methods have a special status in data analytics
because of the importance of explanation and insight. Because k-NN methods
are transparent they produce models that are interpretable. This is also true in
time series analysis [
In this paper we provide a short survey of recent methods that address these
challenges. The methods we consider are:
{ Dynamic Time Warping (DTW): Because two time series may be
fundamentally similar but o set or slightly distorted, DTW allows the time axis
to be warped to identify underlying similarities [
These three methods are described in detail in the next section. Then an evaluation of the performance of these methods on time series classi cation and regression tasks is presented in section 3. The evaluation also covers the thorny issue of parameter selection associated with these methods. 2
In this section, we discuss the three methods (DTW, SAX, and SFA) covered in our analysis. The three methods we consider, all require parameter tuning. A hold-out test strategy is emplyed, where all parameter tuning is done through cross-validation on the training set before testing on the hold-out set. The parameters chosen are also presented in this section. 2.1
To nd the distance between two data series, the Euclidean distance formula
is an obvious choice. But when dealing with time series data where the series
may be displaced in time, the Euclidean distance may be large when the two
series are similar, just o slightly on the time line (see Figure 1(a)). To tackle
this situation Dynamic Time Warping o ers us the exibility of mapping the
two data series in a non-linear fashion by warping the time axis [
Initially, when we restrict our algorithm with no warping allowed, the data points are linearly mapped between the two data series based on the common time axis value. As seen in Figure 1(b), the algorithm does a poor job of matching the time series. But when we grant the DTW algorithm the exibility of considering a warping window, the algorithm performs remarkably when mapping the data-points following the trend of the time series data, which can be visualized in Figure 1(c). 2.2
Several symbolic representations of a time series data have been developed in
recent decades with the objective of bringing the power of text processing
algorithms to bear on time series problems. Keogh et al. provide an overview of
these methods in their 2003 paper [
Symbolic Aggregate Approximation (SAX) is one such algorithm that achieves
dimensionality and numerosity reduction and provides a distance measure that
is a lower bound on corresponding distance measures on the orignal series [
proximation (PAA) in its algorithm for dimensionality reduction. The fundamental idea behind the algorithm is to reduce the dimensionality of a time series by slicing it into equal-sized fragments which are then represented by the average of the values in the fragment.
PAA approximates a time series X of length n into vector X = (x1; x2; :::; xm) of any arbitrary length m 6 n, where each of xi is computed as follows: xi = m n mn i
X
j= mn (i 1)+1
xj
(1)
This simply means that in order to reduce the size from n to m, the original time
series is rst divided into m fragments of equal size and then the mean values for
each of these fragments are computed. The series constructed from these mean
values is the PAA approximation of the original time series. There are two cases
worth noting when using PAA. When m = n the transformed representation
is alike to the original input, and when m = 1 the transformed representation
is just the mean of the original series [
After the PAA transformation of the time series data, the output goes through
another discretization procedure to obtain a discrete representation of the series.
The objective is to discretize these levels into a bins of roughly equal size. These
levels will typically follow a Gaussian distribution so these bins will get larger
(a) Raw time series data. (b) Time series after PAA di-(c) Mapping of discretized
mensionality reduction. bins to symbols in SAX.
away from the mean. The breakpoints separating these discretized bins form a
sorted list B = 1; :::; a 1, such that the area under a N (0; 1) Gaussian curve
from i to i+1 = a1 . 0 and a are de ned as 1 and 1 respectively [
When all the breakpoints are computed, the original time series is discretized as follows. First, the PAA transformation of the time series is performed. Then each of the PAA coe cients less than the smallest breakpoint 1 is mapped to the symbol s1, and all coe cients between breakpoints 1 and 2 (second smallest breakpoint) are mapped to the symbol s2, and so on, until the last PAA coe cient gets mapped. Here, s1 and s2 belongs to a set of symbols S = (s1; s2; :::; sm) to which the time series is mapped by SAX, where m is the size of symbol pool.
SAX also has a sliding window implemented in its algorithm, the size of which can be adjusted. It extracts the symbols present in that window frame and creates a word, which is just the concatenated sequence of symbols in that frame. This sliding window is then shifted to the right and another word is extracted corresponding to the new frame. This goes on until the window hits the end of the time series, and we get a \bag-of-words" representing that time series.
Once the data is converted to this symbolic representation, one can use this
bag-of-words representation for calculating the distance between two time series
using a string distance metric such as Levenshtein distance [
SFA was introduced by Schafer et al. in 2012 as an alternative method to SAX
built upon the idea of dimensionality reduction by symbolic representation.
Unlike SAX which works on the time domain, SFA works on the frequency
domain. In the frequency domain, each dimension contains approximate
information about the whole time series. By increasing the dimensionality one can add
detail, thus improving the overall quality of the approximation. In the time
domain, we have to decide on a length of the approximation in advance and a pre x
of this length only represents a subset of the time series [
Let X(t) be the continuous signal which is the source of the data. Let N
samples be denoted x[0]; x[
N 1 F (!k) , X x(tn)e j!ktn ; k = 0; 1; 2; :::; N 1 (2) n=0
Simply stated, DFT analyzes a time domain signal x(n) to determine the
signal's frequency content X[k]. This is achieved by comparing x[n] against
signals known as sinusoidal basis functions, using correlation. The rst few basis
functions correspond to gradually changing regions and describe the coarse
distribution, while later basis functions describe rapid changes like gaps or noise.
Thus employing only the rst few basis functions yields a good approximation
of the time series[
The DFT Approximation is a part of the preprocessing step of SFA algorithm, where all time series data are approximated by computing DFT coe cients. When all these DFT coe cients are calculated, multiple discretisations are determined from all these DFT approximations using Multiple Coe cient Binning (MCB) as shown in Figure 3. MCB helps in mapping the coe cients to their symbols, and concatenates it to form an SFA word. Thus, this converts the time series into its symbolic representation.
As in SAX, there is a sliding window present here which serves the same purpose of extracting a word representing the data in that frame. Thus, the output of SFA for a given source time series is a bag-of-words symbolically representing the entire series in lower dimension. 3
When it comes to distance measures, Euclidean distance is a popular choice. It
is easily implemented and has linear time complexity. Moreover, it is
parameterfree, and is competitive against more complex approaches, notably when working
on a large dataset. Nevertheless, Euclidean distance is very sensitive to noise and
data being out of phase or warped in time, because of xed mapping of the points
of two time series[
Another distance measure worth considering is the Levenshtein distance, also
popularly known as Edit distance, when working on the string or symbolic
representation of the time series. Edit distance measures the distance between two
strings, by computing the number of edits (insertion, deletion or substitution)
required to match the strings. The Edit Distance on Real sequences (EDR)[
The Wagner-Fischer algorithm [
We compare the three methods (DTW, SAX and SFA) used in time series classi cation or regression in a k-Nearest Neighbour model against the baselines of k-NN with Euclidean distance, and random 5-NN. Note that, SAX and SFA produces a symbolic representation of the time series, so we use EDR and WF as the underlying distance metric.
The evaluation of these methods was conducted on three separate datasets (details below). One of the datasets contains ordered classes so it is included in both the regression and classi cation evaluations. 3.1
In the evaluation we consider one classi cation and two regression problems.
{ Proximal Phalanx TW This is one of the standard datasets from the UCR
collection [
Jumping Data The Jump Height and Jump Class datasets come from the same
study. Ten participants (3 females, 7 males, age: 26.6 2.2, weight: 80.1 7.4 kg
, height: 1.8 0.1 m) were recruited for this case-study. The Human Research
Ethics Committee at University College Dublin approved the study protocol
and written informed consent was obtained from all participants before testing.
Participants did not have a current or recent musculoskeletal injury that would
impair performance of Countermovement Jumps (CMJs) . Participants were
equipped with a Shimmer 3 inertial measurement unit (IMU) 1 on their dominant
foot. The IMU was con gured to stream wide-range, tri-axial accelerometer data
( 16 g) at 1024 Hz. AMTI Force-plate data 2 was also collected concurrently
at 1000 Hz. This was used as a gold-standard tool to derive time in the air for
each jump [
The length of the IMU signals in each le ranged from 1231 to 6710 samples. The time-series used was the acceleration magnitude, derived from the accelerometer x, y and z signals whereby:
Am = q
A2x + A2y + Az2 The target variable for the regression problem was time in the air in seconds, derived from the gold-standard force-plate data.
Note: Each sample in the datasets mentioned above consists of a single univariate time-series on which the models are trained to predict its target label. The unequal length of time-series was tackled by padding with 0's at the end of the shorter time-series when a pairwise distance was computed, between two time-series. 3.2
Parameter selection can have a signi cant impact on performance in Machine Learning and this is particularly true for the algorithms considered here. Here is a brief account of the parameter selection required for each of the methods. 1 http://www.shimmersensing.com/products/shimmer3-imu-sensor 2 https://www.amti.biz DTW As mentioned, DTW gives the exibility of mapping two time-series data warped in time in a non-linear fashion, with the help of a warping window. Thus, nding an optimal warping window is crucial for the algorithm. After cross-validation on the training data, we set the warping window for ProximalPhalanxTW, JumpingHeight and Jumping datasets to be 2, 26 and 26 respectively.
SAX The implementation of SAX [
Note that as the parameter search space is high, we opted on setting the
NRstrategy and z-threshold to be static on an optimum value following our
preliminary experiments. The most in uential parameters to this model are sliding
window size, PAA size and alphabet size.
SFA The implementation of SFA [
Note k-NN has only one parameter, the neighbourhood size (k). We chose to go with the best k value for each model by measuring its performance by 10-fold cross-validation on the train set. 3.3
This section deals with the performance of the three methods, DTW, SAX, and SFA against two baseline models, Euclidean distance (ED) and Random 5-NN. For SAX and SFA we consider both EDR and WF string distance measures so we evaluate ve candidates against two baselines.
Figure 4 illustrates the performance of the models on time-series regression task over two datasets. Mean Absolute Percentage Error (MAPE) metric was employed to evaluate the performance, where a lower MAPE score signi es better performance. While DTW does not perform well on the Jump Height task it is the best model on the Proximal Phalanx task. Here, we can see that SFA with WF is consistent than the other models, showing robustness.
Figure 5 shows the performance on the classi cation tasks. Here the measure is classi cation accuracy so higher is better. When it comes to time-series classi cation we can see DTW performed best, and SFA-WF comes a close second. The WF string distance measure shows a signi cant impact when working on the Jumping dataset.
One overall conclusion we can draw is that SFA-WF always performs well. DTW does well except in the Jump Height regression task. We propose that this is due to the global nature of DTW which seeks a mapping across the whole time series. This is less appropriate in the Jump Height task where sub-regions of the time series are particularly important in predicting the outcome. 4
When it comes to time-series regression and classi cation, k-NN-DTW is one of
the most robust and well-performing methods on a wide array of datasets. SFA
performs signi cantly better than SAX due to the fact, that SFA builds upon
DFT, which is signi cantly more accurate than the PAA dimensionality
reduction technique SAX employs[
This publication has resulted from research supported in part by a grant from Science Foundation Ireland (SFI) under Grant Number 16/RC/3872 and is cofunded under the European Regional Development Fund.