Question: Pairwise distance matrix for clustering

[nsankar]

@seanlaw Is it possible to get a pairwise distance matrix using stumpy

I want to try the same procedure using stumpy (dask/coiled) and HDBScan. Kindly provide the steps for the same with the stumpy code snippet. I believe it would require using mstumped API for a multidimensional data ?. Thank you in advance.

[seanlaw]

@nsankar Can you please provide a few details first?

1. How many time series do you have?
2. On average, what is the length of each time series?
3. It sounds like you are already using Google Colab, which means that your time series data is accessible via Google drive. Is this right?

[nsankar]

@seanlaw It is a simulated time series:

import numpy as np
np.random.seed(9999)
data = []
size = 100

random_ts = np.random.uniform(size=size)

for _ in range(5):
data.append(np.copy(random_ts))

data.append(np.arange(100))
data.append(np.arange(100))
data.append(np.arange(100))

[seanlaw]

I guess what I am trying to understand is what is your real world use case and why you need to use Dask. If your use case is truly a fictitious example with five short, randomly generated time series then you don't need Dask. To start, I recommend that you go through this mpdist paper first to understand what distance is being computed first:

https://www.researchgate.net/profile/Shaghayegh_Gharghabi/publication/330028575_Matrix_Profile_XII_MPdist_A_Novel_Time_Series_Distance_Measure_to_Allow_Data_Mining_in_More_Challenging_Scenarios/links/5c37f5f5299bf12be3be34f8/Matrix-Profile-XII-MPdist-A-Novel-Time-Series-Distance-Measure-to-Allow-Data-Mining-in-More-Challenging-Scenarios.pdf?origin=publication_detail

The mpdist is quite different from the multi-dimensional matrix profile produced by mstump, which follows the mSTAMP/mSTOMP paper. mpdist is significantly easier to compute but, to answer your question concretely, I need to know what you are hoping to accomplish with STUMPY beyond a random and somewhat contrived example. Using HDBSCAN on five time series seems like overkill but perhaps it isn't clear to me what the goal is. And I can tell you without performing the computation that clustering five randomly generated time series would/should not produce any relevant clusters and I would recommend not doing it as the results would not be meaningful.

[seanlaw]

In short, it would be relatively straight forward to compute the pairwise distance matrix by creating two nested for loops that iterate over each pair of time series and then computing/storing the mpdist.

[nsankar]

I guess what I am trying to understand is what is your real world use case and why you need to use Dask. If your use case is truly a fictitious example with five short, randomly generated time series then you don't need Dask. To start, I recommend that you go through this mpdist paper first to understand what distance is being computed first:

https://www.researchgate.net/profile/Shaghayegh_Gharghabi/publication/330028575_Matrix_Profile_XII_MPdist_A_Novel_Time_Series_Distance_Measure_to_Allow_Data_Mining_in_More_Challenging_Scenarios/links/5c37f5f5299bf12be3be34f8/Matrix-Profile-XII-MPdist-A-Novel-Time-Series-Distance-Measure-to-Allow-Data-Mining-in-More-Challenging-Scenarios.pdf?origin=publication_detail

The mpdist is quite different from the multi-dimensional matrix profile produced by mstump, which follows the mSTAMP/mSTOMP paper. mpdist is significantly easier to compute but, to answer your question concretely, I need to know what you are hoping to accomplish with STUMPY beyond a random and somewhat contrived example. Using HDBSCAN on five time series seems like overkill but perhaps it isn't clear to me what the goal is. And I can tell you without performing the computation that clustering five randomly generated time series would/should not produce any relevant clusters and I would recommend not doing it as the results would not be meaningful.

@seanlaw What I have is a large multivariate anomaly data which I use for anomaly detection using HDBSCAN clusters. In this case, I was looking at using MPDist which I wanted to compute using dask. But I wanted to first try the simulated timeseries data possibly with stumpy as a first try to check the MPDist working.. That is the scenario..

[nsankar]

aight forward to comp

@seanlaw Alright. Thanks

[seanlaw]

@nsankar I understand but depending on your real data and the answers to the aforementioned questions:

1. How many time series do you have?
2. On average, what is the length of each time series?
3. It sounds like you are already using Google Colab, which means that your time series data is accessible via Google drive. Is this right?

my response would be drastically different and I don't want to steer you into a direction that is less favorable.

[nsankar]

@nsankar I understand but depending on your real data and the answers to the aforementioned questions:

1. How many time series do you have?
2. On average, what is the length of each time series?
3. It sounds like you are already using Google Colab, which means that your time series data is accessible via Google drive. Is this right?

my response would be drastically different and I don't want to steer you into a direction that is less favorable.

@seanlaw I have 6 dimensions in the time series each representing a metric. , length is 28800 (1 minute sample frequency) - 20 days log, This data is on my local system (private data)

[nsankar]

@seanlaw I am trying using the code given in issue #149 as a reference to compute MPDist on a sample data of 10,000 rows using coiled/dask 10 worker cluster for computing the profile . i.e. mp_ab = stumpy.stump(T_A=tsa, T_B=tsb, m=m, ignore_trivial=False). At the outset it looks like a time consuming method. ..!

[seanlaw]

I have 6 dimensions in the time series each representing a metric. , length is 28800 (1 minute sample frequency) - 20 days log, This data is on my local system (private data)

@nsankar Thank you for the added context. Given that you have 6 x 28,800 time series, I do not recommend using Dask as these time series are pretty short and all of our Dask-supported functions are really targeted for computing matrix profiles for much longer time series lengths (i.e., >100,000 data points in length). Instead, you should be able to compute your pairwise distance using something like this (untested code):

# DO NOT USE, THIS IS UNTESTED CODE!!
# PLEASE VERIFY AND VALIDATE FOR YOURSELF!!
# READ THE ORIGINAL MPDIST PAPER ABOVE!!

import numpy as np
import stumpy
import time

def MPdist(T_A, T_B, m):
    mp_ab = stumpy.stump(T_A=T_A, T_B=T_B, m=m, ignore_trivial=False)
    mp_ba = stumpy.stump(T_A=T_B, T_B=T_A, m=m, ignore_trivial=False)
    mp_abba = np.concatenate((mp_ab[:, 0], mp_ba[:, 0]))
    n = T_A.shape[0] + T_B.shape[0]
    k = int(round(2 * n * 0.05,0))
    mp_dist  = np.sort(mp_abba)[k] 

    return(mp_dist)

# DO NOT USE, THIS IS UNTESTED CODE!!
# PLEASE VERIFY AND VALIDATE FOR YOURSELF!!
# READ THE ORIGINAL MPDIST PAPER ABOVE!!

all_time_series = []
for i in range(6):
    ts = np.random.rand(28800)
    all_time_series.append(ts)

# DO NOT USE, THIS IS UNTESTED CODE!!
# PLEASE VERIFY AND VALIDATE FOR YOURSELF!!
# READ THE ORIGINAL MPDIST PAPER ABOVE!!

n = len(all_time_series)
pairwise_mp_distances = np.full((n, n), np.inf)  # Create an n x n square matrix and fill with np.inf
np.fill_diagonal(pairwise_mp_distances, 0.0)  # Fill the diagonal with zeros
m = 100

# DO NOT USE, THIS IS UNTESTED CODE!!
# PLEASE VERIFY AND VALIDATE FOR YOURSELF!!
# READ THE ORIGINAL MPDIST PAPER ABOVE!!

# Note that we only compute the upper triangular matrix here and fill in the bottom since it is symmetrical
start = time.time()
for i in range(len(all_time_series)):
    T_A = all_time_series[i]
    for j in range(i+1, len(all_time_series)):
        T_B = all_time_series[j]
        distance = MPdist(T_A, T_B, m)
        pairwise_mp_distances[i, j] = distance
        pairwise_mp_distances[j, i] = distance
print(time.time() - start)

# DO NOT USE, THIS IS UNTESTED CODE!!
# PLEASE VERIFY AND VALIDATE FOR YOURSELF!!
# READ THE ORIGINAL MPDIST PAPER ABOVE!!

On my 2-core (4 hyperthreads) Macbook Pro, this took around two minutes (102 seconds to be precise) to complete for this small 6 x 28,800 dataset. Note that since we are using Numba, which JIT-compiles STUMPY's Python code into a fast parallelized function, there will be some small overhead spent on compiling stumpy.stump at first use.

Of course, for longer time series lengths, you may play around with replacing the stumpy.stump function calls within MPdist:

mp_ab = stumpy.stump(T_A=T_A, T_B=T_B, m=m, ignore_trivial=False)
mp_ba = stumpy.stump(T_A=T_B, T_B=T_A, m=m, ignore_trivial=False)

with stumpy.stumped

mp_ab = stumpy.stumped(dask_client, T_A=T_A, T_B=T_B, m=m, ignore_trivial=False)
mp_ba = stumpy.stumped(dask_client, T_A=T_B, T_B=T_A, m=m, ignore_trivial=False)

but note that Dask won't help you if you are on your local machine. Dask only helps for longer time series and if you have access to a Dask distributed cluster. And, if you have access to a GPU or are on Google Colab, you may try replacing stumpy.stump (in the MPdist function) with stumpy.gpu_stump.

WARNING: We are currently in the middle of updating our definition of AB-joins (i.e., computing the matrix profile between T_A and T_B so that it matches the published definition). Technically, I don't think this should affect the output from MPdist due to the sorting step, mp_dist = np.sort(mp_abba)[k] but I just wanted you to be aware that this change is coming in STUMPY v1.5.1+!

[nsankar]

@seanlaw Thank you for the excellent guidance. I am going to study , try these and shall revert . Questions : (1) Why do you say Dask only helps for longer time series? I would like to know if there anything beyond making a long time series distributed (divide and conquer stuff..) you are relating to? (2) As to the definition of AB-joins , Is this a new API being added to stumpy or is it getting added to an existing API? Thanks again.

[seanlaw]

Why do you say Dask only helps for longer time series? I would like to know if there anything beyond making a long time series distributed (divide and conquer stuff..) you are relating to?

Well, Dask can be used for a lot of things but, currently in STUMPY, the most time consuming task is computing the matrix profile and the total computational time is O(n^2) where n is the length of your time series. After you compute the matrix profile, everything else that derives from it can be accomplished in a few seconds or less. While Dask is great for analyzing large data sets beyond your available computer memory, time series problems aren't actually that memory intensive and, instead, is heavily compute intensive. For matrix profiles, there is no need to shuffle the time series in and out of memory and, instead, we benefit from the distributed capabilities offered by Dask. Note that all of our parallel compute is actually handled by Numba. We're using Dask to manage the distribution of the jobs but not the actual compute.

As to the definition of AB-joins , Is this a new API being added to stumpy or is it getting added to an existing API? Thanks again.

No, this is not a new API. AB-joins have been in STUMPY since day one (but not well advertised). However, recently, I had noticed that our definition of an AB-join was actually flipped. So, when you did stumpy.stump(T_A, m, T_B), you actually got a BA-join (rather than an AB-join). If you wanted an AB-join, you would've needed to reverse the time series and do stumpy.stump(T_B, m, T_A). This works but is counterintuitive and inconsistent with the published definition. This is fixed in the development version on Github and will be released in the upcoming v1.5.1 as a patch.

[nsankar]

Thanks @seanlaw for enlightening !

[seanlaw]

@nsankar If you don't mind, I'm going to close this for now but feel free to re-open if you have any more questions.