Repository navigation
Develop single-dimensional matrix profile for multi-dimensional time series #632
Description
Activity
- changed the title
[-]Developing single-matrix profile in multi-dimensional time series[/-][+]Developing single-dimensional matrix profile for multi-dimensional time series[/+]on Jun 28, 2022 - changed the title
[-]Developing single-dimensional matrix profile for multi-dimensional time series[/-][+]Develop single-dimensional matrix profile for multi-dimensional time series[/+]on Jun 28, 2022 @NimaSarajpoor There's a lot to unpack here but here are a couple of points off of the top of my head:
- You may already be aware of this (so ignore where appropriate) but the multi-dimensional matrix profile already combines dimensions by averaging the distances across a subset of dimensions where the distances are smallest. The details can be found here. However, not that multi-dimensional matrix profiles are not simply summing up distances for the
ksmallest distances and, instead, it is an average. - If your proposal is to simply compute the 1-D matrix profiles for each dimension independently of the others then, IMHO, there's nothing that STUMPY needs to "support" as the computation of 1-D matrix profiles is already optimized and any "combining" can already be done by the user in a post-processing step (outside of STUMPY). An example of this post-processing step might be a nice tutorial?
Maybe you can elaborate on what is currently missing as I may not be understanding your point clearly?
- You may already be aware of this (so ignore where appropriate) but the multi-dimensional matrix profile already combines dimensions by averaging the distances across a subset of dimensions where the distances are smallest. The details can be found here. However, not that multi-dimensional matrix profiles are not simply summing up distances for the
Adding @SaVoAMP @mihailescum to this conversation as they have thought about this a lot and may have some comments to contribute!
Reacted by Nima SarajpoorThere's a lot to unpack here
Agree. I just wanted to share my idea before I forget about it.
- You may already be aware of this (so ignore where appropriate) but the multi-dimensional matrix profile already combines dimensions by averaging the distances across a subset of dimensions where the distances are smallest. The details can be found here. However, not that multi-dimensional matrix profiles are not simply summing up distances for the
ksmallest distances and, instead, it is an average.
Thanks for sharing the link! I took a look and there are some similarities for sure. As provided in here:
ith_matrix_profile = np.full(d, np.inf) ith_indices = np.full(d, -1, dtype=np.int64) for k in range(1, d + 1): smallest_k = np.partition(ith_distance_profile, k, axis=0)[:k] # retrieves the smallest k values in each column averaged_smallest_k = smallest_k.mean(axis=0) # line(*) min_val = averaged_smallest_k.min() if min_val < ith_matrix_profile[k - 1]: ith_matrix_profile[k - 1] = min_val ith_indices[k - 1] = averaged_smallest_k.argmin()IF I UNDERSTAND CORRECTLY:
For instance, sayd=2(two dimensional data T=[T1, T2]), then, in the last iteration wherek=d, theaveraged_smallest_k = smallest_k.mean(axis=0)is distance profile considering all dimensions (here, both two dimensions together). It gets average of each column in 2D distance profile.What I am proposing is to simply keep
min_val(inmin_val = averaged_smallest_k.min()) of the last iterationk=d. So, skip that if-block, and simply returnmin_valas the value for each index in 1D matrix profile. (So, nofor-looporpartition.) something like this:1D_dist_profile = np.mean(ith_2D_distance_profile, axis=0) # exclude trivial idx = np.argmin(1D_dist_profile)Instead of
.mean(), we can combine the values of 2D_distance_profiles (across axis=0) by using the formula provided in my previous comment. We can take advantage of relationship between total_D and Avg_of_Pearsons(across dimensions). In fact, we can enhance current implementation of stump and stumped, and gpu_stump for this! No new module is needed.Maybe I should find some 2D or 3D data to test it out and see if it gives me new/interesting insight about the data! I believe it gives me something new! However, I would like to test it in some real-world data @seanlaw @SaVoAMP @mihailescum do you have any suggestion for 2D or 3D data?
2. If your proposal is to simply compute the 1-D matrix profiles for each dimension independently of the others then,
That is not my proposal. I should have been more clear. Let's say D1 and D2 are two distance profiles of S1 and S2 at an index
i. Then,min( combination of D1 and D2)is different thanmin(D1) + min(D2). The latter is simply the same as adding matrix profile of each dimension in post processing step. My idea is to calculate combined distance profile (similar toline(*)in code snippet above) and then return the minimum of that distance profile as the matrix profile value.Note that we can use this for query matching as well! So, if I have 2D query
Q=[Q1, Q2], I can findS=[S1, S2]close toQconsidering both dimension. Again, this is not adding matrix profile of 1 and 2, but calculating 1D matrix profile by combining distance profile throughout the process. Is this useful? probably. The idea is that I now have a tool to explore and see if I can get new insight from data.
Is this reasonable when we have huge number of dimensions? Probably not. Because, as mentioned in the Eamon's paper, there might be some noise in some dimension of data.
Is it better than multi-dimensional matrix profile? I do not want to use the term "better". It may have its own advantage. I need to use it to see what kind of insight I can get from data that is different than
multi-dimensional matrix profile. Also, I believe it is easier to understand. So, if I have 2 or 3 dimensional data, using this 1D matrix profile might be better in terms of interpretability. And, I think I can do matching in 2D! And, it can be simply(hopefully) implemented in the existing modules.@seanlaw
Please feel free to close this issue or move it to discussion if necessary.- You may already be aware of this (so ignore where appropriate) but the multi-dimensional matrix profile already combines dimensions by averaging the distances across a subset of dimensions where the distances are smallest. The details can be found here. However, not that multi-dimensional matrix profiles are not simply summing up distances for the
Maybe I should find some 2D or 3D data to test it out and see if it gives me new information! I believe it gives me something new! However, I would like to test it in some real-world data @seanlaw @SaVoAMP @mihailescum do you have any suggestion for 2D or 3D data?
I was working with a three-dimensional boxing data set (consisting of acceleration data of 8 different boxers) that is also labeled. I have found here that relatively similar results emerge when examining the data in one, two, or all three dimensions for a punch motif. I could obtain nice results, especially when concatenating all the punches of a boxer of the same type (for example, only frontal punches with the left hand), so that I only had to look for a single motif.
However, even with a 30-dimensional data set for analyzing human motion I could obtain relatively good results with different choices of
k. Maybe this data sets will help to test your considerations.Reacted by Nima Sarajpoor and Sean M. Law@SaVoAMP
Thanks for sharing the data! Much appreciated! I will take a look and see if I can implement my idea and get some preliminary result. I will seek your help in the nearby future if I don't understand the data or the target (i.e, the problem we try to solve by using that data).@NimaSarajpoor I think this is probably better suited for the Discussion section as it isn't quite an issue with the existing code and, instead, is a atypical and yet-to-be-confirmed case.
Reacted by Nima Sarajpoor@seanlaw
Right! It is better to be put in discussion.Reacted by Sean M. Law- locked and limited conversation to collaborators
on Jun 29, 2022
Motivation
I have noticed that there are some interest in using matrix profile in multi-dimensional time series. We can think of it as:
I believe the first one is tackled in Matrix Profile VI, and its tutorial is under progress in PR #557 .
In the paper Matrix Profile VI, we can see the following note:
There are a few things to notice:
So, I think it is worth it to have support for single-dimensional matrix profile for multi-dimensional time series data.
Challenge-(I)
(this is based on what I read about generalizing single-dimensional matrix profile to multi-dimensional time series data. I do not remember the source though. I think it was from Eamonn Keogh.)
One of the main challenges is how to combine m distances across m-dimensional time series data.
Example:
Let's say we have two-dimensional data: T1 (first dimension) and T2 (second dimension). And, let's focus on subsequences at index i and j. Therefore:
But, what is that function
ffor combining the two distancesd1andd2(and gives one single value)? Two common options are:This two are equal only when
p=1. Otherwise, they are different. Both seems reasonable approach. However, we can go with the second approach and provide a module for that instumpy(see section "implementation" below)Challenge-(II)
Another challenge that I remember I read from the same source was how to avoid the domination of one dimension? well, this is probably an issue in non-normalized version. However, like many machine learning problems, it is usually up to the user on how to normalize time series. Maybe they normalize
T1andT2by their maximum. Or, they may standardize the WHOLE dataT1and the WHOLE dataT2. So, I believe this shouldn't be our concern.Implementation$(d^{p} + d '^{p})^{1/p}$ for p-norm non-normalized matrix profile. The challenge might be in using Pearson correlation in normalized version. However, there is a nice solution for that!
I think we can easily do
Note that the factor 2 can be eliminated because if we scale all pairwise distances by the same number, it does not change the result.
Therefore:
$D = \sqrt{2m ( 1 - P)}$ , where P is average of pearsons. So, we can use all those rolling/running variance stuff and simply just take average of pearsons!
Cool!