Repository navigation
Handling Constant Query Motifs in MASS #600
Description
The distance profile is not calculated reliably for constant motifs. Given the following code, 0, 1 or 2 dips are seen:
import numpy as np
import stumpy
import matplotlib.pyplot as plt
tgtLength = 5000
tgt = np.zeros(tgtLength, dtype = np.float32)
for index in range(tgtLength):
if index < 500:
tgt[index] = np.random.rand(1)[0]
if index >= 500 and index < 1000:
tgt[index] = 3
if index >= 1000:
tgt[index] = np.random.rand(1)[0]
window_size = 500
qry = np.ones(window_size, dtype = np.float32) * 3
plt.plot(tgt)
plt.plot(qry)
plt.show()
plt.close()
distance_proile = stumpy.mass(qry, tgt)
plt.plot(distance_proile)
plt.show()
plt.close()
Is it only on my machine ?
Activity
JaKasb commentedon May 11, 2022
Not a bug.
Each sliding window is normalized by to zero-mean and unit-variance.
If window is constant -> variance is 0 -> Divide by zero
Solution 1:
set parameter normalize to False
Solution 2:
provide a "fixed" version of the sliding variance to MASS()
Solution 3:
Add small noise to data to eliminate contant regions.
Preferably smaller noise magnitude than the quantization stepsize.
seanlaw commentedon May 11, 2022
@AndiBerber Thank you for your question and welcome to the STUMPY community. I wonder if the issue is that the query subsequence is also constant (in addition to a part of your time series being constant). In that case, this may be an undesirable input since, as @JaKasb pointed out, this would cause a "divide by zero" in the z-normalization of your subsequence. In this instance, what would you expect the output to be?
In case it is relevant, you can set
normalize=Falseinstumpy.massas recommended by @JaKasb and you'll get:[-]Bug for const motifs[/-][+]Handling Constant Query Motifs in MASS[/+]AndiBerber commentedon May 12, 2022
Thank you guys @JaKasb and @seanlaw for your friendly and welcoming support. Everything works out as expected when I use
np.float64. The behaviour withnp.float32is weird though, as it is random whether the dips are present. Maybe a warning would be nice if you use it withnp.float32? I would like to implement an efficient MASS algorithm in C++ so I still have a few questions:So by default every sub sequence is z-normalized? As my understanding goes from
https://www.cs.ucr.edu/~eamonn/Matrix_Profile_Tutorial_Part2.pdf, the whole target time series is z-normalized, then it is convolved with the z-normalized motif and divided by the movingStd (of the target´s sub sequences).I know that constant motifs/time series cause issues with z-normalizing and correlation but I wonder how this is handled (or one can handle this) as it still would be nice to detect these occurrences and have a dip in these regions. In the
stumpycase, is it implemented brute force with an euclidian distance meassurement? For me it looks like especially with the results regarding thenormalizeflag. I wonder how to handle constant motifs/time series with theMASS 2.0algorithm.I guess I found what I was looking for with a bunch of if/else savety checks in
core.py/_calculate_squared_distance.Best regards,
Andi
seanlaw commentedon May 12, 2022
@AndiBerber Can you please tell me what version of STUMPY you are using? The latest version is v1.11.1. By default, STUMPY throws an error when the input isn't of type
np.float64. When I do:I get:
This is the same error that I get when I execute your code using the latest version of STUMPY.
Regarding constant regions. There are two key scenarios:
Detecting a constant subsequence is quite straightforward as all you need to do is find the subsequences that have a zero stddev. If it does then the subsequence must be constant. So, after you compute mass using a covolution, you can perform some sort of post-processing step. In case #1, you'd just check if your query subsequence is constant (i.e., stddev == 0.0) and then look for all subsequences in your time series that are constant (i.e., stddev == 0.0) and simply set all of those distances in your distance profile (output pf MASS) to zero. Case #1 is the easy/obvious case. However, in case #2, when only the query OR the subsequence in your time series is constant then it isn't exactly clear what the expected result would/should be. In your example, since your query is constant, you experience both case #1 and case #2 but I have no confidence in how to interpret the distances where time series is NOT constant (i.e., random numbers). Currently, in
stumpy.stump, the distance is set tosqrt(m)(i.e., square-root of the window size) and I can't remember why we did this and if there is a derivation to support this. At the end of the day, a constant subsequence cannot be z-normalized due to "divide-by-zero". There is an on-going discussion in #591 if you have any thoughts you'd like to contribute.AndiBerber commentedon May 12, 2022
@seanlaw : Indeed, my version is
1.9.2. I agree on everything you said. Unfortunately, I´m not sure how to handle case #2 either. Maybe just a brute force z-normalized eucIidean distance measurement? I will have a look at the discussion and the linked paper and contribute if I have some meaningful insights.Thanks again.
seanlaw commentedon May 12, 2022
@AndiBerber If you don't mind, I'd like to move this issue to the Discussion section of our repository