How to efficiently calculate euclidean distance matrix for several timeseries

Question

I have 6 timeseries data as follows namely t1, t2, t3, t4, t5 and t6.

import numpy as np
series = np.array([
     [0., 0, 1, 2, 1, 0, 1, 0, 0],
     [0., 1, 2, 0, 0, 0, 0, 0, 0],
     [1., 2, 0, 0, 0, 0, 0, 1, 1],
     [0., 0, 1, 2, 1, 0, 1, 0, 0],
     [0., 1, 2, 0, 0, 0, 0, 0, 0],
     [1., 2, 0, 0, 0, 0, 0, 1, 1]])

I want to create a euclidean distance matrix from these 6 timeseries as in the format of (i.e. 6*6 where x denotes the corresponding euclidean distance):

     t1  t2  t3  t4  t5  t6
t1    0   x   x   x   x   x
t2    x   0   x   x   x   x
t3    x   x   0   x   x   x
t4    x   x   x   0   x   x
t5    x   x   x   x   0   x
t6    x   x   x   x   x   0

I am currently constructing this matrix manually as follows (In this SO question: Efficient and precise calculation of the euclidean distance this method has got the hightest performance).

e.g., to calculate euclidean distance between t3 and t6.

def eudis(v1, v2):
    dist = [(a - b)**2 for a, b in zip(v1, v2)]
    dist = math.sqrt(sum(dist))
    return dist

eudis(t3, t6)

However, I am sure that there could be more easy and computationally efficient way to do this in python. Please let me know if you have suggestions.

I am happy to provide more details if needed.

Hi EmJ! Does this [SO thread](https://stackoverflow.com/a/1401828/2402281) help you? More specifically, the usage of [np.linalg.norm](https://numpy.org/doc/stable/reference/generated/numpy.linalg.norm.html)? I did not benchmark it but I'd assume that numpy is pretty much optimized (to be evaluated though). — tafaust, Jun 08 '20 at 09:04

Stef · Accepted Answer · 2020-06-08T12:27:06.730

2

You can also use pdist to get the distance matrix:

from scipy.spatial.distance import pdist, squareform
squareform(pdist(series))

Performance comparison with pure numpy and euclidean_distances solutions:

So for relatively small datasets (up to about 20 series with 200 elements each) pdist is fastest, for larger datasets euclidean_disances performs much better. pure numpy is mostly slower and may fail to allocate the intermediate array for large datasets.
Tested with np.random.randint(0, 100, (n, 10*n)).astype('int16'), numpy 1.17.4, scipy 1.4.1, sklearn 0.23.1, python 3.8.2, Win10 64bit.

edited Jun 08 '20 at 12:27

answered Jun 08 '20 at 09:21

Stef

28,728
2
24
52

thanks a lot for the nice comparison. since i have a larger dataset the insights you have provided is really useful. thank you :) – EmJ Jun 08 '20 at 13:16

score 2 · Answer 2 · answered Jun 08 '20 at 09:29

2

You can create a distance matrix in simple numpy in one line, you don't need anything else.

np.sqrt(((series[:,None,:] - series)**2).sum(axis=2))

answered Jun 08 '20 at 09:29

Mercury

3,417
1
10
35

very nice solution, but you can run into memory problems for larger time series – Stef Jun 08 '20 at 10:24
You're right, it'll scale poorly for larger series. – Mercury Jun 08 '20 at 10:34

score 1 · Answer 3 · answered Jun 08 '20 at 09:12

You don't need to loop at all, for the euclidean distance between two arrays just compute the elementwise squares of the differences as:

def euclidean_distance(v1, v2):
    return np.sqrt(np.sum((v1 - v2)**2))

And for the distance matrix, you have sklearn.metrics.pairwise.euclidean_distances:

from sklearn.metrics.pairwise import euclidean_distances

euclidean_distances(a).round(2)

array([[0.  , 2.83, 3.74, 0.  , 2.83, 3.74],
       [2.83, 0.  , 2.83, 2.83, 0.  , 2.83],
       [3.74, 2.83, 0.  , 3.74, 2.83, 0.  ],
       [0.  , 2.83, 3.74, 0.  , 2.83, 3.74],
       [2.83, 0.  , 2.83, 2.83, 0.  , 2.83],
       [3.74, 2.83, 0.  , 3.74, 2.83, 0.  ]])

np.allclose(
    eudis(series[2], series[3]),
    euclidean_distance(series[2], series[3])
)
# True

thank you for the great answer. from the comparison of @Stef this is the fastest for the larger datasets. thank you :) — EmJ, Jun 08 '20 at 13:21

How to efficiently calculate euclidean distance matrix for several timeseries

3 Answers3

Linked