Distance matrix calculation for time series clustering

[rsangole]

@seanlaw

(Continuing the discussion here from our slack thread...)

Background

I'm trying to develop some time-series clustering for ~3k time-series, each 39 long.

After normalizing each time series using StandardScaler, here's a glimpse of the dataset:

Attempts

Getting inspiration from your link, my attempt to create the full distance matrix is:

SIZE = train_wide.shape[1]
M = 39
PC = 1
result = np.zeros((SIZE,SIZE))
for i in range(SIZE): #train_wide.shape[1]
    for j in range(SIZE):
        if not i == j:            
            result[i,j] = stumpy.mpdist(train_wide.iloc[:,i], 
                                        train_wide.iloc[:,j],
                                        m = M,
                                        percentage = PC,
                                        normalize = False
                                       )

The compute takes (figuratively) forever (10+ hours, before I called it quits on my MB Pro 2.4Ghz 8-core machine).

Questions

1. Am I doing something wrong here, or is this the nature of the beast? Alternatively, any speedier way to get this distance matrix?
2. Is my understand right, that since I want to compare the full time series against each other (and each series is 39 long), it makes sense to set m to 39?

[JaKasb]

Q1

In your definition of distance matrix, the distance matrix contains the pairwise distance between whole sequences.
The shape is 3k x 3k -> 9E06 Elements.
Assume that each mpdist() call takes 1 millisecond (which is unrealistic), then the runtime is 2.5 hours.
https://www.wolframalpha.com/input?i=9E06+milliseconds

Q2

If you want to compare whole sequences, then set m equal to the sequence length.
However for the mpdist-measure, if m=length, then mpdist degenerates to the euclidean distance.

General

Read the papers.
The papers are very helpful and explain a lot of the unexpected corner cases.
The papers also show unexpected use-cases for the algorithms.

There is also a paper about distance matrices:
Matrix Profile XXVI: Mplots: Scaling Time Series Similarity Matrices to Massive Data

[seanlaw]

@rsangole Thank you for your question and welcome to the STUMPY community. I don't know the answer but I'd like to share a few observations and possible answers to your questions:

Am I doing something wrong here, or is this the nature of the beast? Alternatively, any speedier way to get this distance matrix?

Sadly, this is the nature of the beast. As I'm sure you are already aware, any n x n pairwise distance matrix calculation is exceptionally costly (not only for STUMPY). Considering that you've set m to the full length of your time series then this means that you are not benefitting from STUMPY's subsequence-level distance optimizations since you are only computing the Euclidean distance between each train_wide.iloc[:,i] and train_wide.iloc[:,j] pair (and not the shorter subsequences within each time series). Of course, computing the distance between subsequences would only increase the computational time rather than decrease it. Having said that, if you are only interested in the Euclidean distance between the full length time series and with normalize=False then you may be better off doing something much simpler (untested) like:

from scipy.spatial.distance import cdist

results = cdist(train_wide.values.T, train_wide.values.T)

A couple of notes/reminders:

1. You may need to do this in blocks/chunks as cdist may run out of memory if the matrix size is too big (though, this can be manually parallelized using multiple cores as, IIRC, this is single threaded)
2. This only works if you are computing the Euclidean distance at the full time series level (i.e., not between subsequences)
3. This only works for when you set normalize=False (i.e., non-normalized Euclidean distance)

In theory, this would/should be much faster, though, again, it will be costly. Where STUMPY shines is when you want to compare the distance between subsequences and also for longer time series. With m = 39, you are unlikely to benefit much (if any) from STUMPY's internal parallelization due to the small size of the problem.

Is my understand right, that since I want to compare the full time series against each other (and each series is 39 long), it makes sense to set m to 39?

Yes, this is correct. However, if you read the original MPdist paper, they explain that one rarely really wants to compare the full time series. If you look at the recommended MPdist tutorial, this is related to the question of whether or not a phase-shifted time series is the "same" as its unshifted counterpart. Unfortunately, this is a question that can only be answered by the user as it can differ depending on your use case.