Handling Constant Query Motifs in MASS

[AndiBerber]

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 ?

[JaKasb]

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]

@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=False in stumpy.mass as recommended by @JaKasb and you'll get:

%matplotlib inline

import numpy as np 
import stumpy
import matplotlib.pyplot as plt

tgtLength = 5000
tgt = np.zeros(tgtLength, dtype = np.float64)
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
distance_proile = stumpy.mass(qry, tgt, normalize=False)
plt.plot(distance_proile)
plt.show()
plt.close()

[AndiBerber]

Thank you guys @JaKasb and @seanlaw for your friendly and welcoming support. Everything works out as expected when I use np.float64. The behaviour with np.float32 is weird though, as it is random whether the dips are present. Maybe a warning would be nice if you use it with np.float32 ? I would like to implement an efficient MASS algorithm in C++ so I still have a few questions:

1. 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).

2. 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 stumpy case, is it implemented brute force with an euclidian distance meassurement? For me it looks like especially with the results regarding the normalize flag. I wonder how to handle constant motifs/time series with the MASS 2.0 algorithm.

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]

The behaviour with np.float32 is weird though, as it is random whether the dips are present. Maybe a warning would be nice if you use it with np.float32 ?

@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:

import numpy as np
import stumpy

Q = np.random.rand(50).astype(np.float32)
T = np.random.rand(1000).astype(np.float32)
stumpy.mass(Q, T)

I get:

TypeError: <class 'numpy.float64'> dtype expected but found float32 in input array
Please change your input `dtype` with `.astype(dtype)`

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:

1. When both subsequences are constant
2. When one subsequence is constant and the second subsequence is not

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 to sqrt(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]

@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]

@AndiBerber I just performed a "proof-by-simulation" and discovered that when only one subsequence is constant (and the other is non-constant) then the distance is always approaching sqrt(m) (where m is the window size).

[seanlaw]

@AndiBerber If you don't mind, I'd like to move this issue to the Discussion section of our repository