How do config stumpy to deal with the twin freak problem

[robroe-tsi]

Hi,

I would like to use stumpy for anomaly detection. Based on the tutorial here https://www.cs.ucr.edu/~eamonn/Matrix_Profile_Tutorial_Part1.pdf page 47 shows the pathological problem when using the MP discords. If two anomalies are close together they can hide each other from having a high MP value. The solution on page 50 could be an option (works by specifying the MP value to the Mth nearest neighbor instead the first NN) but I cant figure out how to do that with the stumpy API. Can you help?

Many thanks and best

[seanlaw]

@robroe-tsi Thank you for your question and welcome to the STUMPY community!

So, after you compute a matrix profile, say, using stumpy.stump, you identify the "discord" as the subsequence with the largest distance to its (non-trivial) nearest neighbor. Then, you can take this discord subsequence and re-compute the "distance profile" (a vector that stores the distance from the discord to EVERY other subsequence including the trivial subsequences), which you can then use to find other nearest neighbors. It would look something like this:

import numpy as np
import stumpy

T = np.random.rand(1000)  # Some fake time series
m = 50
mp = stumpy.stump(T, m)

discord_idx = np.argsort(mp[:, 0])[-1]
discord_subseq = T[discord_idx : discord_idx + m]

distance_profile = stumpy.core.mass(discord_subseq, T)

With this distance_profile (that is specific for your discord subsequence), you can first set the "trivial zone" to np.inf, and then sort the distance_profile to find your top-K nearest neighbors:

trivial_zone = 10  # Adjust this yourself
start_idx = min(0, discord_idx - trivial_zone)
stop_idx = max(len(mp), discord_idx + trivial_zone + 1)
distance_profile[discord_idx - trivial_zone : discord_idx] = np.inf

k = 10
print(np.argsort(distance_profile)[:k])  # print top-K indices that are nearest to the discord index

Unfortunately, there is currently no way to use stumpy.stump compute the second (or third) nearest neighbor. Instead, you need to identify the subsequences of interest (i.e., discords) and then recompute the distance_profile for all of them. However, most of the time, there aren't too many subsequences to try.

[robroe-tsi]

@seanlaw Thanks for the prompt answer and the example.

My concern with your approach is that because of the "twin freak" problem the real anomalies would not stand out with a high distance value - maybe not even in some top N. So if we select the item with the highest distance value we would select the blue point from slide 49 of the tutorial - a normal point.
So essentially I have to use the stumpy.core.mass function all the time - which might not be a problem in the inference phase when testing new "incoming" sequences on the degree of their anomaly.
Then the remaining problem is how to choose the K in the new discord definition from p. 50

The subsequence D that has the maximum distance from its (non-trivial match) K nearest neighbor.

Maybe we use a small K together with subsampling. Will see.

But thanks again for the help and the code example.

[seanlaw]

My concern with your approach is that because of the "twin freak" problem the real anomalies would not stand out with a high distance value - maybe not even in some top N. So if we select the item with the highest distance value we would select the blue point from slide 49 of the tutorial - a normal point.

You are absolutely right. The method that I proposed does not address this issue.

So essentially I have to use the stumpy.core.mass function all the time - which might not be a problem in the inference phase when testing new "incoming" sequences on the degree of their anomaly.
Then the remaining problem is how to choose the K in the new discord definition from p. 50

Yes, stumpy.core.mass is fairly inexpensive if you only have to compute a distance profile occasionally. However, you do not want to compute a full matrix profile this way as it is less efficient. In fact, using mass to compute the full matrix profile is the subject of the first Matrix Profile I paper. stumpy.stump is based on the faster Matrix Profile II paper.

Having said all that, we are certainly open to adding a new feature (PRs are also welcome). Here are some implementation challenges off the top of my head:

1. Depending on the choice of "top-K", we'll have to store more information (i.e., K additional distance and K additional indices)
2. There would be extra processing time to figure out if a new distance falls into the "top-K"

So, the memory increase may be an issue and it may slow down your matrix profile computation altogether unless their were an efficient approach for updating the "top-K" for each subsequence on-the-fly.

[rkans02]

Hey guys,

I am also facing the twin freak problem trying to detect anomalies in a signal strength time series (see in the image). I am currently writing my masters thesis and my goal is to 1. extract the anomalies and 2. classify them. The previous work uses a threshold method to extract the anomalies and k-nearest neighbour classsification. My idea was to use the Matrix profile to combine both steps. However the counting fails with at this twin freak problem. An additional complication is that anomalies have different window sizes.

So currently i am also using the threshold method for counting and the matrix profile for classification ( Fast pattern search ).

I don´t know if any of this is helpful or interesting but as the turorial states on page 50 "If an “anomaly” happens many times, it is probably not an anomaly, and we probably know about it anyway".

I´m very new to the matrix profile but very glad that ive found STUMPY, its really great!

[seanlaw]

@rkans02 Thank you for the note. Regarding:

If an “anomaly” happens many times, it is probably not an anomaly,

I guess the question is how do you quantify "many times" (i.e., what should k be)? As mentioned above, it is certainly possible to return, say, the top 3 nearest neighbors (outside of the exclusion zone) but this will be slower since you have to constantly check/update the top 3 and, minimally, it will require an additional 2 * k * (n - m + 1) amount of space (memory) in order to store additional nearest neighbor information. Again, I'm not saying that it's not doable but, since we actually compute individual distances along diagonals (i.e., we actually don't compute distance profiles), I don't know of a computationally efficient algorithm for checking/updating the nearest neighbor while the matrix profile is being computed. My goal is to provide new features without significantly increasing the complexity of the codebase. I would be curious if you had any suggestions?

[seanlaw]

Additionally, @rkans02, it looks like you are looking for spikes/point anomalies in your data and so it might also be relevant for you to try setting normalize=False when using stumpy.stump (available starting in STUMPY v1.8.0) which turns off z-normalization. This usually makes it better for computing point anomalies or spikes. If you do this, don't forget to set the same parameter later if you use stumpy.core.mass

[seanlaw]

I looked into this a bit more today. There is a reasonably good solution for finding the kth smallest value from a stream (i.e., online) which uses np.partition (available in Numba). The current implementation of stumpy.stump computes and tracks the maximum Pearson correlation but, to keep the codebase clean, I'd recommend spinning off a separate implementation (i.e., function) to handle the twin freak problem.

[rkans02]

Hey Sean, thanks for the fast reply and all your suggestions!
In my case k would be a very large number. I am also searching for different kind of motifs with different lengths and shapes. I am working on an approach were i am manually selecting templates of these not arbitrary motifs and then i am performing the fast pattern search in conjunction with a voting system to count and classify the motifs. But i guess its now not fitting the topic of the discussion anymore.
So I don´t have further suggestions but will look into your suggestions in future work.
Best regards,
Raoul