1

According to "Computing and Visualizing Dynamic Time Warping Alignments in R: The dtw package" by T. Giorgino, "the DTW distance is not in general symmetric". From how I understand this, if there is a query time series X and a reference time series Y, the DTW distance will not necessarily be the same if Y were the query time series and X were the reference.

I'm confused. How can this be the case? And how should we interpret DTW distance given this asymmetry?

irene
  • 155
  • 6

2 Answers2

3

There are many different versions of DTW. Most often, different versions of DTW use a different step pattern (where can the sequences move with respect to each other, and what is the cost of this). In most cases a symmetric step pattern is used, and then DTW distance will be symmetric. However, if an asymmetric step pattern is used, DTW distance can be asymmetric as well.

However: Even with a symmetric step pattern (even with the default pattern) DTW distance is not a metric. It is easy to produce some examples where the triangle inequality is violated. So it is never easy to interpret DTW distance in terms of a metric.

How would you interpret an asymmetric DTW distance? If you are not using an asymmetric step pattern, this will not happen, so there is no special interpretation. If you use an asymmetric step pattern, there probably is a reason for deviating from the default pattern. So the interpretation depends on that reason as well.

From the reference you posted: "Several step patterns have been discussed in the literature. A classic paper by Sakoe and Chiba (1978) classifies them according to two properties: their symmetry (symmetric/asymmetric), and the bounds imposed on the slope expressed through a parameter P. The eight step patterns shown in Sakoe and Chiba (1978, Table I) are pre-defined in dtw, with names symmetricP1, asymmetricP05, and so on.1 All of them are normalizable."

LiKao
  • 2,329
  • 1
  • 17
  • 25
  • I am currently studying time series clustering, and it seems if I want to cluster time series based on the shape, I should be looking at DTW distance as the metric. Apparently that has been done (or at least it was referenced in the paper on kmlShape). However, if it's not a metric, am I doing anything wrong by using DTW distance (with symmetric step patterns) as the "metric" in clustering (like agglomerative clustering)? – irene Apr 01 '20 at 12:15
  • 1
    @irene I have worked with DTW in my diploma thesis, which was a while ago. I know there are some clustering approaches based on DTW, but I am not sure about the details (except that means based clustering does not work). There is a direct question on DTW based clustering (https://stats.stackexchange.com/questions/131281/dynamic-time-warping-clustering) but the tendency seems skeptical of that approach. – LiKao Apr 01 '20 at 12:56
  • Thanks for the link! – irene Apr 02 '20 at 08:58
  • It's a tough choice accepting an answer (@EamonnKeogh's response is extremely useful to me, since I'm doing clustering AND he is an authority on this!), but since my question asked about how asymmetry can happen, I think this is the direct answer to that. – irene Apr 03 '20 at 15:46
3

First, you say "DTW distance as the metric". It is important to know that DTW is not a metric, it is only a measure. https://www.cs.unm.edu/~mueen/DTW.pdf

It is perfectly possible to use DTW for clustering (of any kind). The one thing that makes a big difference is setting the warping constraint. This seems hard, given the lack of labels. But there are ways to do this, see [a]

In general, for clustering, no subsequcne is privilgled or special, so you want to use a classic symmetric implementation of DTW [a].

If scaiblity is an issue, then you should use LB_keogh pruining to speed things up.

There are 128 nice test datasets here https://www.cs.ucr.edu/~eamonn/time_series_data_2018/

Email me is you need more help.

[a] https://www.cs.ucr.edu/~eamonn/CIKM_2016_DTW_clustering.pdf Semi-Supervision Dramatically Improves Time Series Clustering under Dynamic Time Warping

Eamonn Keogh
  • 31
  • 1