\section{Introduction}

Time series are sequences of values measured over time. Examples include
financial data, such as stock prices,  or medical data, such as blood sugar
levels. Classifying time series is an important class of problems
which is applicable to music classification~\citep{springerlink:10.1007/s11634-007-0016-x},
medical diagnostic~\citep{Sternickel2002109} or bioinformatics~\citep{Legrand2008215}.

Nearest Neighbor (NN) methods classify time series efficiently and accurately~\citep{1454226}.
The 1-NN method is especially simple: we merely have to find the nearest labeled instance.


We need to specify a distance: the Euclidean and Dynamic Time Warping~\citep{1163055} distances are popular choices.
However, we can also learn a distance based on some training data~\citep{yang2006distance,weinberger2009distance}.
Given the training data set made of classes of time series instances,
we can either learn a single (global) distance function, or learn one distance
function per class~\citep{csatari2010,paredes2000class,1221358}. That is, to compute the distance between a test element and an instance of class~$j$, we use
a distance function specific to class~$j$. 

Because the Euclidean distance is popular for NN classification, it is tempting to consider 
generalized ellipsoid distances~\citep{ishikawa1998mindreader}, that is, distances of the form
\begin{eqnarray*}
D(x,y) = (x-y)^{\top} M (x-y).
\end{eqnarray*}
When $M$ is a positive semi-definite matrix, the square root of this distance is a pseudometric:
it is symmetric, non-negative and it satisfies the triangle inequality ($\sqrt{D(x,y)}+\sqrt{D(y,z)}\leq \sqrt{D(x,z)}$).
Further, when $M$ is a positive definite matrix, then the square root becomes a
metric because $D(x,x)=0 \Rightarrow x=0$. 
When the matrix $M$ is the identity matrix, we recover the (squared) Euclidean distance.
We get the  Mahalanobis distance when solving for the matrix $M$ minimizing the sum of distances
$\sum_{x,y}D(x,y)$ (see~\S~\ref{sec:mathstuff}).
We can require $M$ to be diagonal, thus defining the diagonal Mahalanobis distance~\citep{1221358,ishikawa1998mindreader}.
In the more general case, solving
for $M$ can be difficult, as it often involves inverting a low-rank matrix.
Perhaps partly due to these mathematical difficulties, there has been no attempt to use the general
Mahalanobis distance to classify time series (to our knowledge). Thus, for the first time,
we apply the full-matrix Mahalanobis distance for time series classification. To solve
the mathematical difficulties, we use both an approach based on a pseudoinverse 
and on covariance shrinkage. With both the diagonal
and the covariance shrinkage approaches, the
square root of the distance $D$ is a metric (under mild assumptions) whereas our approach based on a  pseudoinverse merely
generates a pseudo-metric.

While we find that  the full-matrix Mahalanobis distance is not competitive when
relying on a pseudoinverse, we get good results with covariance shrinkage
or using the diagonal Mahalanobis distance. 
Moreover, we find that the class-based Mahalanobis distance
is preferable to the global Mahalanobis distance.


\section{Related Works}

Several distance functions are used for time series classification, such as
\begin{itemize}
\item Dynamic Time Warping (DTW)~\citep{ratanamahatana2004making}, 
\item DISSIM~\citep{frentzos2007index},
\item  Threshold
Queries~\citep{abfalg2006similarity}, 
\item Edit distances~\citep{chen:mln,chen2005robust}, 
\item Longest Common Subsequences (LCSS)~\citep{878994}, 
\item Swale~\citep{1247544},
\item  SpADe~\citep{chen2007spade}, 
\item and Cluster, Then Classify (CTC)~\citep{keogh1998enhanced}.
\end{itemize}
\cite{1454226} presented an extensive comparison of these distance functions and
concluded that DTW is among the best measures and that the accuracy of the Euclidean distance
converges to DTW as the size of the training set increases.

In a general Machine Learning setting, \cite{paredes2000class,1221358} compared Euclidean distance with the conventional and class-based Mahalanobis distances. 
 One of our contribution is to validate these generic results on time series: instead of tens of features, we have hundreds or even thousands of values which makes the problem mathematically more challenging: the rank of our covariance matrices are
 often tiny compared to their sizes. 

More generally, distance metric learning has an extensive literature~\citep{255644,hastie1996discriminant,1598381,short1980new}.
We refer the reader to \cite{weinberger2009distance} for a review.
 
A conventional distance-learning approach is to find an optimal generalized ellipsoid
distance with respect to a specific loss function. 
The LMNN algorithm proposed by \cite{weinberger2009distance} takes a different approach. It seeks to force nearest neighbors to
belong to the same class and it separates instances from different classes by a large margin. 
LMNN can be
formulated as a semi-definite programming problem. 
They also propose a modification
which they call multiple metrics LMNN as it learns different distances for each class.

There are many extensions and alternatives to NN classification. For example,
\cite{1558510} use instance weights to improve classification.
Meanwhile, \cite{1553530} learn a distance per instance.


\subsection{Dynamic Time Warping (DTW)}

As already stated, The DTW is one of the most accurate distance function for time-series classification. 
The DTW was invented
to recognize spoken words~\citep{sakoe1978dpa}, but it is also used
for various problems such as 
handwriting recognition~\citep{bahlmann2004wio,niels2005udt},
 chromosome classification~\citep{legrand2007ccu},
 networking~\citep{springerlink:10.1007/978-3-642-15880-3_8}
  or
  shape retrieval~\citep{TPAMI.2005.21,marzal2006cbs}.
  

  
For simplicity, consider two time series $x$ and $y$ of equal length ($n$).
  Recall that the $l_p$ distance between two 
  time series is \begin{eqnarray*}\sqrt[p]{\sum_{i=1}^n |x_i - y_i|^p}\end{eqnarray*} if $p$ is a positive
  integer or $\max_{i=1,\ldots,n} |x_i - y_i|$ if $p=\infty$.
 The $l_1$ distance is also called the Manhattan distance whereas
 the $l_2$ distance is the Euclidean distance.

The intuition behind the DTW is that one could speak the same sentence by 
speeding up and slowing down without changing the meaning of
the sounds.
 The DTW is a generalization of the $l_p$ distance which allows the
 data to be realigned.
To compute the DTW between $x$ and $y$, you must find a 
many-to-many matching between the data points in  $x$ and the data points
in $y$. That is each data point from one series must be matched with at least
one data point with the other series. One such matching is the trivial one, which maps the
first data point from $x$ to the first data point in $y$, 
the second data point in $x$ to the second data point in $y$, and so on.
Write the
set matches $(i,j)$ as $\Gamma$ so that the trivial matching
is just $\Gamma=\{(1,1), (2,2), \ldots, (n,n) \}$.
The $l_p$ cost corresponding to a matching is defined as
\begin{eqnarray*}\sqrt[p]{\sum_{(i,j)\in \Gamma} |x_i - y_j|^p}\end{eqnarray*} if $p$ is 
in an integer or 
$\max_{(i,j)\in \Gamma} |x_i - y_j|$ if $p=\infty$.
Typically, $p$ is either 1 or 2: for our purposes we
assume $p=2$.
For a given $p$, the DTW is defined as the minimal cost
over all allowed matchings $\Gamma$.
Typically, we require matchings to be monotonic: 
if both $(i,j)$ and $(i+1,j')$ are in $\Gamma$ then $j'\geq j$,
that is, we cannot warp back in time.
Moreover, some matches might be forbidden, maybe because
the data points are too far apart~\citep{itakura1975mpr,sakoe1978dpa}.
\cite{Yu20112787} has proposed learning this warping constraint
from the data.
Except when $p= \infty$, the DTW fails to satisfy the
triangle inequality:
the DTW is not a metric distance.

The computational cost of the DTW is sometimes a challenge~\citep{Salvador2007561}.
To alleviate this problem, several strategies have been proposed
including lower bounds and R*-tree indexes~\citep{ratanamahatana2005tmd,Lemire:2009:FRT:1542560.1542887,Ouyang:2010:HDS:1884499.1884520}.



\cite{Gaudin:2006:ATW:1193211.1193725} proposed a weighted 
version of the DTW called Adaptable Time Warping. Instead of
computing $\sum_{(i,j)\in \Gamma} |x_i - y_j|^p$, it computes
$\sum_{(i,j)\in \Gamma} M_{i,j}|x_i - y_j|^p$ where $M$ is some matrix.
Unfortunately, finding the optimal matrix $M$ can be a challenge.
\cite{Jeong2010} investigated another form of weighted DTW
where you seek the minimize 
\begin{eqnarray*}\sqrt[p]{\sum_{(i,j)\in \Gamma} w_{|i-j|}|x_i - y_j|^p}\end{eqnarray*}
where $w$ is some weight vector.
Many other variations on the DTW  distance have been
proposed, e.g.,~\cite{springerlink:10.1007/s11634-006-0004-6}.


\section{Mahalanobis distance}
\label{sec:mathstuff}

 For completeness, we derive the Mahalanobis distance~\citep{mahalanobis1936generalized} as an optimal form of generalized ellipsoid distance.
We seek $M$ minimizing
\begin{eqnarray*}
\sum_{x,y \in S}{(x-y)^{\top} M (x-y)} = \sum_{x,y \in S}{\left(\sum_{k=1}^n\sum_{l=1}^n{(x_k-y_k) m_{kl}
(x_l-y_l)}\right)}
\end{eqnarray*}
where $S$ is some class of time series. We add a regularization constraint on the determinant ($\det(M) =
1$). 

We solve the minimization
problem by the Lagrange's multiplier method with the Lagrangian
\begin{eqnarray*}
L(M,\lambda) &=& \sum_{x,y \in S}\left(\sum_{k=1}^n\sum_{l=1}^n{(x_k-y_k) m_{k,l} (x_l-y_l)}\right) - \lambda (\det M -1).
\end{eqnarray*}

We want to compute the derivative of the
Lagrangian, and of $\det(M)$, with respect
to $m_{k,l}$. By Laplace expansion, we have for all $l$ that
\begin{eqnarray*}\det(M) = \sum_{k=1}^n{(-1)^{k+l} m_{k,l} \det(M_{k,l})} = 1\end{eqnarray*} where $M_{k,l}$ is the $(k,l)$ minor of $M$: an $(n-1)\times(n-1)$ matrix
obtained by deleting $k$-th row and $l$-th column of $M$.
Thus, we have ${\partial \det(M)}/{\partial m_{k,l}} = (-1)^{k+l} \det(M_{k,l}) $. 
Setting the derivatives to zero, we get
\begin{eqnarray*}
\frac{\partial L(M,\lambda)}{\partial m_{k,l}} = \sum_{x,y \in S}{(x_k-y_k)(x_l-y_l)} -
\lambda (-1)^{k+l} \det(M_{k,l})  = 0
\end{eqnarray*}
and therefore
\begin{eqnarray*}
\det(M_{k,l}) = \frac{\sum_{x,y \in S}{(x_k-y_k)(x_l-y_l)}}{\lambda (-1)^{k+l}}.
\end{eqnarray*}
Because $\det(M)=1$ and using Cramer's rule, the inverse matrix $M^{-1}$ can be represented as
\begin{eqnarray*}
m_{k,l}^{-1} = \frac{(-1)^{k+l} \det(M_{k,l})}{\det(M)} = (-1)^{k+l} \det(M_{k,l}).
\end{eqnarray*}
Hence, we have
\begin{eqnarray*}
m_{k,l}^{-1} = \frac{\sum_{x,y \in S}{(x_k-y_k)(x_l-y_l)}}{\lambda }.
\end{eqnarray*}
Thus, we have that 
$M^{-1} \propto C$ where $C$ is the covariance matrix. Because we require $M$ to be positive definite and to satisfy $\det(M)=1$, we set $M = (\det(C))^{\frac{1}{n}} C^{-1}$ which produces the Mahalanobis distance\footnote{The original Mahalanobis distance is defined with $M=C^{-1}$}.


Our derivation assumes that the covariance matrix is (numerically) invertible.
This fails in practice.
In \S~\ref{sec:computing}, we review some solutions.




\section{Computing Mahalanobis distances for time series}
\label{sec:computing}


 As a rule of thumb, the covariance matrix becomes singular when the number of instances is smaller or about the same as the number of attributes. 
 This is a common problem with time series: whereas individual time series might have thousands of samples, there may only be a few labeled time series in each class.


The most straight-forward solution is to limit the matrix $M$ to its diagonal--thus producing a weighted Euclidean distance.
Revisiting the derivation of \S~\ref{sec:mathstuff} where we require $m_{k,l}=0$ for $k\neq l$, we get that the inverse of the Mahalanobis matrix $M$ must be equal to the inverse
of the diagonal of the covariance matrix:
$M^{-1} \propto \mathrm{diag} ( C )$. As long as the variance of
each attribute in our training sets is different from zero -- a condition
satisfied in practice in our experiments, the problem
is well posed and the result is a positive-definite matrix.
In such a diagonal case, the number of parameters
to learn grows only linearly with the number of attributes in the time series.
In contrast, the number of elements in the full covariance matrix grows 
quadratically. The speed of the computation of the distances also depends
on the number of non-zero elements in the Mahalanobis matrix $M$.

 Alas, the diagonal Mahalanobis  distance fails to take into account the information
 off the diagonal in the covariance matrix. 
See Figure \ref{fig:signcov} for the covariance matrix of a class of time series. It is clear from the figure that the covariance matrix has significant values off the diagonal.
There are even block-like patterns in the matrix corresponding to specific time intervals.
 
\begin{figure}
\centering

\subfloat[Sample of time series]{

	\includegraphics[width=0.69\columnwidth]{cylindersignal.pdf}

	}
\subfloat[Sample covariance]{

	\includegraphics[width=0.29\columnwidth]{cylindercovariance.pdf}

	}
\caption{\label{fig:signcov} The Cylinder class from the CBF data set and its sample covariance.
Higher absolute values in the matrix are presented using darker colors.
}
\end{figure}
 
 Could it be that non-diagonal Mahalanobis  distance could be superior or at least
 competitive with the diagonal Mahalanobis  distance? 
 It is tempting to use banded matrices, but the restriction of a positive definite
matrix to a band may fail to be positive definite. Block-diagonal matrices~\citep{Matton20101303} can preserve positive definiteness, but learning which blocks
to use in the context of time series might be difficult.
Instead, we propose two approaches: one is based on the widely used Moore-Penrose pseudoinverse, and the other is covariance shrinkage.
See Figure \ref{fig:signmatrices} for the three different covariance estimates of the same class.

\begin{figure}
\centering

\subfloat[Sample covariance]{

	\includegraphics[width=0.3\columnwidth]{funnel-samplecov-crop.pdf}

	}
\subfloat[Shrinked covariance]{

	\includegraphics[width=0.3\columnwidth]{funnel-shrinkage-crop.pdf}

	}
\subfloat[Diagonal covariance]{

	\includegraphics[width=0.3\columnwidth]{funnel-diagonal-crop.pdf}

	}
\caption{\label{fig:signmatrices}
The covariance estimates of the Funnel class in the CBF data set.
Large absolute values are in darker colors.
Both the shrinked
and diagonal covariances are positive definite whereas
the sample covariance matrix is singular. }
\end{figure}

The approach based on the pseudoinverse is based on the singular value decomposition (SVD). We write the SVD as $C= U\Sigma V^*$ where $\Sigma$ is a diagonal matrix with eigenvalues $\lambda_1, \lambda_2,\ldots$ and $U$ and $V$ are unitary matrices.
The Moore-Penrose pseudoinverse is given by $V\Sigma^+ U^*$ where $\Sigma^+$
is the diagonal matrix made of the eigenvalues $1/\lambda_1, 1/\lambda_2,\ldots$ with
the convention that $1/0=0$. The pseudo-determinant is the product of the non-zero eigenvalues of $\Sigma$.
We set $M$ equal to the
pseudoinverse of the covariance matrix---normalized so that it has a pseudo-determinant
of one. This solution is equivalent to projecting the time series data on the 
subspace corresponding to the non-zero eigenvalues of $\Sigma$. That is, the matrix $M$ will be singular.

Covariance shrinkage is an estimation method for problems with small number of instances and large number of attributes~\citep{stein}. It has better theoretical and practical properties for such data sets as the estimated covariance matrix is guaranteed to be non-singular.
Let $x_1, x_2, \ldots, x_n$ be a set of time series. We write $x_{i}= (x_{i1},x_{i2},\ldots,x_{ip}) $ where $x_{ik}$ is the $k^{\mathrm{th}}$ value (attribute) of the time series $x_i$.
One element of the (sample) covariance matrix $S$ is\begin{eqnarray*}
s_{ij} = \frac{1}{n-1} \sum_{k=1}^n (x_{ki} - \bar x_i )(x_{kj} - \bar x_j )
 \end{eqnarray*}
 where $\bar x_i = \frac{1}{n} \sum_{k=1}^n x_{ki}$.
It is positive semi-definite but can be singular. 
To fix the problem that $S$ is singular, we can replace it
with  an estimation of the form \begin{eqnarray*}C^*=\lambda T + (1- \lambda) S\end{eqnarray*} for some suitably chosen
target $T$. If $T$ is a  positive definite matrix and $\lambda\in (0,1]$, we have that  $\lambda T + (1- \lambda) S$ 
must be positive definite. Moreover, 
the smallest eigenvalue of $\lambda T + (1- \lambda) S$ must be at least as large as $\lambda$ times the smallest eigenvalue of $T$.
We have used the target recommended by \cite{schafer2005shrinkage} which is the diagonal of the unrestricted covariance estimate, $T = \mathrm{diag} ( C )$.
It is positive definite in our examples. For $\lambda$, we use the estimation proposed by \cite{schafer2005shrinkage}: it is computationally inexpensive.


Thus, finally, we consider six types of Mahalanobis distances: two localities (global or class-based) and three estimators (pseudoinverse, shrinkage, or diagonal).

\section{Experiments}

The main goal of our experiments is to evaluate Mahalanobis distances and the class-based approach on time series. 
A secondary goal is to evaluate the LMNN method.

We begin all tests with training data set made of classes of instances. When applicable,
distances are learned from this data set. We then attempt to classify some test
data using 1-NN and we report the classification error.

The code for the experiments is available online~\citep{ourmatlabcode} with instructions on how the results can
be reproduced. For LMNN, we use the source code provided by \cite{lmnncode} for the experiments
with default parameters.


\subsection{Data sets}
We use the UCR time series classification benchmark~\citep{keoghbenchmark} for our experiments as it includes
diverse time series data sets from many domains. 
It has predefined training-test splits for the experiments,
so the results can be compared across different papers. 
We removed the two data that are not z-normalized by default (Beef and Coffee).
Indeed, z-normalization improves substantially the classification accuracy---irrespective of the chosen distance.
Thus, for fair results, we should z-normalize them, but this may create confusion with previously
reported numbers. 
We also removed the Wafer data set as all distances classify it nearly perfectly.
The remaining 17~data sets were used for the comparison of different methods.

\subsection{Best Mahalanobis distance for 1-NN accuracy}

We compare the various Mahalanobis distances in Table~\ref{tab:ourresultsforMahalanobis}. We have left out the Moore-Penrose pseudoinverse, because its error rates were twice as high on average compared to the other variants.
What is immediately apparent is that the class-based metrics give better classification results.


The diagonal Mahalanobis is somewhat better and they are also considerably faster computationally, but the shrinkage estimate yields significantly better results for several data sets (e.g.~Adiac and Face~(four)).
Thus, out of the six variations, we recommend the class-based shrinkage estimate and the class-based diagonal Mahalanobis distance.

\begin{table}
\caption{\label{tab:ourresultsforMahalanobis}Classification error for the various Mahalanobis distances.}
\centering
\begin{tabular}{l|cccc}\hline
\multirow{2}{*}{Data set}           & \multicolumn{2}{c}{Shrinkage}  & \multicolumn{2}{c}{Diagonal}              \\
             & global &  class-based         & global & class-based \\\hline
50 words			& 0.36		& 0.71	&  0.34			&  \textbf{0.32}\\
Adiac               & 0.33     & \textbf{0.28}          &  0.37         &  0.36\\
CBF                 &  0.52     & \textbf{0.04} &  0.16         &   0.05 \\
ECG                 &  0.13     & 0.09          &0.10           & \textbf{0.08}     \\
Fish                &  0.33     & \textbf{0.15}          & 0.19 & 0.18  \\
Face (all)          &  0.31     & 0.27	&  0.32         & \textbf{0.25}\\ 
Face (four)         &  0.45     & \textbf{0.10}          & 0.16         &0.17  \\ 
Gun-Point           &  \textbf{0.06}     & 0.10          & 0.10          & 0.11 \\
Lighting-2          &  0.49     & 0.31 &  \textbf{0.25}          &  \textbf{0.25}  \\
Lighting-7          &  0.59     & 0.32          & 0.36          &  \textbf{0.23} \\
OSU Leaf            &  0.69     & 0.69 & \textbf{0.46}          & \textbf{0.46}    \\
OliveOil          &0.17			& 0.17  & 0.17          &\textbf{0.13}  \\
Swedish Leaf        & 0.25     & \textbf{0.14}          & 0.21          & 0.18 \\
Trace               &  0.27     & 0.09 & 0.21          & \textbf{0.07}   \\
Two Patterns        &  \textbf{0.10}     & \textbf{0.10} & 0.12          &  0.12\\
Synthetic Control   &  0.23     & 0.10 & 0.13          &  \textbf{0.09}\\
Yoga              & 0.24 		& 0.21	& \textbf{0.17}         & \textbf{0.17}	 \\\hline
\# of best errors   & 2 & 6 & 3 & 10 \\ \hline
\end{tabular}
\end{table}


\subsection{Comparing competitive distances}

How do the class-based Mahalanobis distances fare compared to competitive distances? Computationally,
the diagonal Mahalanobis is inexpensive compared to schemes such as the DTW or LMNN\@.
Regarding the 1-NN classification error rate, we give the results in Table~\ref{tab:ourresults}. 
As expected~\citep{1454226}, no distance is better on all data sets. However, because the diagonal Mahalanobis distance is closely related
to the Euclidean distance, we compare their classification accuracy.
In two data sets, the Euclidean distance outperformed the class-based Mahalanobis distance and only by small differences (0.09 versus 0.10-0.12). Meanwhile, the class-based diagonal Mahalanobis outperformed the Euclidean distance 12 times, and sometimes by large margins (0.07 versus 0.24 and 0.05 versus 0.15).

The LMNN is also competitive: its classification error is sometimes half that of the Euclidean distance. 
However, the class-based LMNN gets the best result among all methods only twice as opposed to
five~times for the global LMNN. Moreover, the global LMNN significantly outperforms the class-based
LMNN on the Two Patterns data set (0.05 versus 0.24). For time series data sets, the class-based LMNN is not an improvement over the global LMNN.

We have to note that DTW has the lowest error rates and provides best results for half of the data sets, but it is much slower than Mahalanobis distances.

\begin{table}
\caption{\label{tab:ourresults}Classification errors for some competitive schemes.  We use class-based Mahalanobis distances. For the 50~words data set, the LMNN computation fails because it has a class with only one instance.}
\centering 
\begin{tabular}{l|ccccccc}\hline
\multirow{1}{*}{Data set}           & \multirow{1}{*}{Euclidean} & \multirow{1}{*}{DTW}           & \multicolumn{2}{c}{C.-b. Mahalanobis} & \multicolumn{2}{c}{LMNN}  &  \\
             &  &     &   shrink.   & diag.  &    & c.-b. \\\hline
50 words			&  0.37		& \textbf{0.31}	& 0.71	&   0.32				& ---			 & ---\\
Adiac               &  0.39     & 0.40          & 0.28         &   0.36               & \textbf{0.23}      & 0.32\\
CBF                 &  0.15     & \textbf{0.00} & 0.04         &   0.05               &  0.15           &  0.15 \\
ECG                 &  0.12     & 0.23          & 0.09           & 0.08        	&  0.10          & \textbf{0.07}\\
Fish                &  0.22     & 0.17      	& 0.15	     & 0.18                 &  \textbf{0.13}  & 0.14\\
Face (all)          &  0.29     & 0.19			& 0.27        & 0.25         &  \textbf{0.16}           & 0.20\\ 
Face (four)         &  0.22     & 0.17          & \textbf{0.10}     & 0.17                  & 0.16   &  0.16\\ 
Gun-Point           &  0.09     & 0.09          & 0.10        & 0.11                 &\textbf{0.05}      & 0.09\\
Lighting-2          &  0.25     & \textbf{0.13} & 0.31          & 0.25                 &  0.41            & 0.34\\
Lighting-7          &  0.42     & 0.27          & 0.32         &  \textbf{0.23}       &  0.51            &  0.48\\
OSU Leaf            &  0.48     & \textbf{0.41} & 0.69         & 0.46                 & 0.57             & 0.54\\
OliveOil          &\textbf{0.13}&\textbf{0.13}  & 0.17         &\textbf{0.13}         & \textbf{0.13}    & \textbf{0.13}\\
Swedish Leaf        &  0.21     & 0.21          & \textbf{0.14}   & 0.18        & 0.21            & 0.19\\
Trace               &  0.24     & \textbf{0.00} & 0.09          & 0.07                 & 0.20            & 0.20\\
Two Patterns        &  0.09     & \textbf{0.00} & 0.10          &  0.12                & 0.05		  	& 0.24\\
Synthetic Control   &  0.12     & \textbf{0.01} & 0.10          & 0.09                 & 0.03          & 0.09\\
Yoga              & 0.17 		& \textbf{0.16}	& 0.21          & 0.17					& 0.18		 & 0.18 \\
\hline
\# of best errors   & 1 & 9 & 2 & 2 & 5 & 2\\ \hline
\end{tabular}
\end{table}

\subsection{Effect of the number of instances per  class}

Whereas Table~\ref{tab:ourresults} shows that the Mahalanobis distances are far superior to the Euclidean distance on some data sets, this result
 is linked to the number of instances
per class. For example, on the Wafer data set (which we removed), there are many instances per class (500), and correspondingly, all distances give a negligible classification error.

Thus, we considered three different synthetic time-series data sets with varying numbers of instances per class:
Cylinder-Bell-Funnel (CBF)~\citep{921732},
  Control Charts (CC)~\citep{pham1998ccp} and
 Waveform~\citep{breiman1998car}.
Test sets have 1\,000~instances per class whereas training sets have between 10 to 1\,000 instances.
We repeated each test ten times, with different training sets.
Fig.~\ref{fig:synthdatasets} shows that whereas the class-based diagonal Mahalanobis
is superior to the Euclidean distance when there are few instances, this benefit
is less significant as the number of instances increases. Indeed, the classification
accuracy of the Euclidean distance grows closer to perfection and it becomes more difficult
for alternatives to be far superior.

\begin{figure}
\centering\includegraphics[width=0.8\columnwidth]{synthdatasets}
\caption{\label{fig:synthdatasets}Ratios of the 1-NN classification accuracies using the class-based diagonal Mahalanobis and Euclidean distances}
\end{figure}


\section{Conclusion}
The Mahalanobis distances have received little attention for time series classification and we are not
surprised given their poor performance
as a 1-NN classifier when used in a straight-forward manner. However, by learning one Mahalanobis distance per class we get a competitive classifier when using either covariance shrinkage or a diagonal approach.
Moreover, the diagonal Mahalanobis distance is particularly appealing computationally: we only
need to compute the variances of the components.
Meanwhile, we get good results with the LMNN on time series data, though it is more expensive. 
The DTW is superior, but computationally expensive.


\begin{acknowledgements}
This work is supported by NSERC grant 261437.
\end{acknowledgements}

\bibliographystyle{spbasic}
