Data Science Stack Exchange is a question and answer site for Data science professionals, Machine Learning specialists, and those interested in learning more about the field. It only takes a minute to sign up.
Sign up to join this community
I have multiple time series sequences and I want for each new time series to find the most alike old one.
The answer to your questions depend a lot on the nature of the data represented in the time series. You should ask yourself some questions to better understand what might or might not work, e.g.:
Normally, the answers to those questions are that series are not perfectly aligned and that variations in scale are also fine as long as the shape is similar. For these scenarios, the classical measure is Dynamic Time Warping (DTW). There are lower bounds for DTW that are very efficient computationally. The research of Professor Keogh might be interesting if you need theoretical foundation for it.
Also, normally euclidean distance and Manhattan distance are not very appropriate for time series due to their sensitivity to signal transformations (e.g. shifts), but actually they are often used in practice.
There is this very cool idea in a paper by Ryabko[1] which is not yet very well known. This is called the telescope distance $D_H$.
To make a valid assessment about two time series, just looking at the data is not enough. You need to compare the underlying stochastic process that generates them, i.e. you want to compare two probability distributions. And the telescope distance is precisely a metric on the space of probability distributions.
It goes like this (kind of formidable to the uninitiated). For a set of functions $\mathbf{H} = (\mathcal{H_1, H_2, \ldots})$, the telescope distance is defined as
$$D_{\mathbf{H}}(P, Q) \equiv \sum_{k=1}^{\infty} w_k \sup_{h \in \mathcal{H_k}} | E_P [h(X_1,\ldots,X_k)] - E_Q [h(Y_1, \ldots,Y_k)]|$$
where $P,Q$ are the distribution that generates $X$ and $Y$ respectively, and $w_k$ are some exponentially decaying weights (see the paper for details). You don't know $P$ and $Q$; all you got are the time series.
It turns out you could use the following empirical quantity $\hat{D}$ to estimate the true telescope distance,
$$ \small \hat{D}_{\mathbf{H}}(X_{1:n}, Y_{1:m}) \equiv \sum_{k=1}^{min(m,n)} w_k \sup_{h \in \mathcal{H_k}} \big|\frac{1}{n-k+1} \sum_{i=1}^{n-k+1} h(X_{i:i+k-1})- \frac{1}{m-k+1} \sum_{i=1}^{m-k+1} h(Y_{i:i+k-1}) \big| $$ where $X_{1:n}$ and $Y_{1:m}$ are your observed time series. Notice the nice thing about this metric is, the two time series don't have to be equal in length.
Now, everything seems to be fine except that you notice you need the $h(\ldots)$? And it's not just one function, but a sequence of functions.
The cool idea is that these $h(\ldots)$s could be modeled as a binary-classifier well known in machine learning. For example, one could use SVM for these $h$ to discriminate between a subsequence $X$ and a subsequence of $Y$.
Once you've trained these binary classifiers, and there are $min(n,m)$ of them, you run them through the subsequences of the same length of $X$ and $Y$, sum them up and you're done.
[1]Ryabko, D., & Mary, J. (2013). A binary-classification-based metric between time-series distributions and its use in statistical and learning problems. The Journal of Machine Learning Research, 14(1), 2837-2856.
I think you are looking for the distance between two functions, which to my knowledge is a rather complex mathematical field (sorry for not being able to give a reference, but I know I read a book about it once).
To answere your second point: I got some decent results using dynamic time warping (https://en.wikipedia.org/wiki/Dynamic_time_warping). It should be available for every software kit. In python, there is a package fastdtw (https://pypi.python.org/pypi/fastdtw) that does a good job.
And I think that scaling will make a difference, no matter which method you use.
A good thing that you could try on top of Euclidian distance and DTW would be:
DBA which is a sidegrade to DTW, here is an example
Telescopic distance (as suggested by horaceT) here is a link that one of the authors gave me, this should prove more concrete than the math only.
as ncasas mentioned "Normally, the answers to those questions are that series are not perfectly aligned and that variations in scale are also fine as long as the shape is similar" then DTW is good.
The Q is: what if the shape is not similar but the subsequence of TS1 is similar to TS2? Then you shall have a look at subsequence time series clustering. I've found this idea couple of days ago and realized there is a research paper about it already. Here you have the link: https://arxiv.org/abs/1810.11624
Please remember that comparing subsequence TS is meaningfull as long as you choose right metric for clusters distance computation and it shall be based on clusters shape as per "An Alternate Measure for Comparing Time Series Subsequence Clusters" paper.
