Detecting Point Anomalies with STUMPY

[notecola]

We have a problem understanding the matrix profile for a very simple case.
The 1D data has 61 points and there clearly is an anomaly.
However, MP plots with various window sizes seem to be not related to the data and to each other.

Example code:

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

from numpy import inf
from matplotlib.patches import Rectangle

df = pd.read_csv('c:/a/data.csv', usecols=['data'])
print(df.describe())
print(df.head())

steps = [3, 4, 6, 12, 24]
fig, axs = plt.subplots(1 + len(steps), sharex=True, gridspec_kw={'hspace': 0})
plt.suptitle('Test', fontsize='30')
axs[0].plot(df['data'].values)
axs[0].set_ylabel('data', fontsize='20')

for i, winsize in enumerate(steps):
    mp = stumpy.stump(df['data'], winsize)

    # same with GPU
    # mp = stumpy.gpu_stump(df['data'], winsize)

    # replace INF
    mp[mp == -inf] = 0
    mp[mp == inf] = 0

    discord_value = mp[:, 0].max()
    discord_index = np.argwhere(mp[:, 0] == mp[:, 0].max()).flatten()[0]
    print("discord max: " + str(discord_value))
    print("discord at: " + str(discord_index))

    rect = Rectangle((discord_index, 0), winsize, discord_value,
                     facecolor='lightgrey')
    axs[1 + i].add_patch(rect)
    axs[1 + i].set_xlabel('Time', fontsize ='20')
    axs[1 + i].set_ylabel('WND: ' + str(winsize), fontsize='20')
    axs[1 + i].plot(mp[:, 0])

plt.show()

CSV zip attached
data.zip

contents are:

,data
1,-301.0
2,144.0
3,378.0
4,632.0
5,-358.0
6,-259.0
7,359.0
8,902.0
9,-177.0
10,431.0
11,162.0
12,1959.0
13,428.0
14,987.0
15,217.0
16,646.0
17,204.0
18,-21.0
19,621.0
20,3255.0
21,-621.0
22,747.0
23,948.0
24,-934.0
25,-1430.0
26,1991.0
27,-167.0
28,460.0
29,-868.0
30,313.0
31,-486.0
32,5021.0
33,-2451.0
34,2172.0
35,-37.0
36,-992.0
37,-1815.0
38,1690.0
39,-6.0
40,51.0
41,174.0
42,-1619.0
43,835.0
44,5365.0
45,-3526.0
46,2351.0
47,-1838.0
48,1679.0
49,7843.0
50,62169.0
51,-57720.0
52,-3004.0
53,1946.0
54,815.0
55,399.0
56,5285.0
57,-9878.0
58,-9921.0
59,-2179.0
60,3723.0
61,1928.0

[seanlaw]

@notecola Thank you for the question. Let me take a look!

[notecola]

Thanks for your time

[seanlaw]

@notecola Thanks again for the reproducible example! Hopefully, my response here will come across as "welcoming an open discussion" rather than sounding like an "authoritative voice" (I certainly don't know everything!) so please feel free to challenge me as I will not take offense.

I think that there are a few important points to make here. Firstly, we need to keep in mind that matrix profiles compute z-normalized distances between subsequences and so this means that the magnitude is often lost as a result of normalization. Handwaving-ly, z-normalization of a subsequence essentially removes changes in trend (think de-trending) and compares the shape of one subsequence with another (and not the raw magnitude). This can be a blessing and a curse depending on what problem you are trying to solve but, generally, this means that z-normalized distances are not all well suited for "point anomalies" (i.e., when you have individual points that are, say, two standard deviations away from the full time series mean). Instead, z-normalized distance comparisons are best used for comparing the relative shapes of subsequences (i.e., a contiguous set of neighboring data points). In fact, z-normalized distances are wonderful for finding "shape patterns" or, in the case of discords, the lack of a "shape pattern". See this related issue to get a sense of what I mean as it relates to removing shifts in magnitude (an increasing trend) while still recognizing shape patterns.

Having said that, it is important to note that "discord" is not exactly synonymous with "anomaly". I would consider discords as a great "candidate" for a potentially anomalous shape. So, please keep this in mind. In general, I don't think anybody really "knows" how to define an anomaly...

So, in your toy example, what you have are essentially point anomalies which are not great for z-normalization but, again, this is trivial to detect with simple standard deviation. However, we recently added an (unsupported) implementation that uses unnormalized Euclidean distance (i.e., we don't z-normalize and just compute the straight Euclidean distance) to compute matrix profiles based on this published aamp paper. If you clone the STUMPY repository and install the latest version and try:

from stumpy.aamp import aamp

steps = [3, 4, 6, 12, 24]
fig, axs = plt.subplots(1 + len(steps), sharex=True, gridspec_kw={'hspace': 0})
plt.suptitle('Test', fontsize='30')
axs[0].plot(df['data'].values)
axs[0].set_ylabel('data', fontsize='20')

for i, winsize in enumerate(steps):
    mp = aamp(df['data'], winsize)

    # same with GPU
    # mp = stumpy.gpu_stump(df['data'], winsize)

    # replace INF
    mp[mp == -inf] = 0
    mp[mp == inf] = 0

    discord_value = mp[:, 0].max()
    discord_index = np.argwhere(mp[:, 0] == mp[:, 0].max()).flatten()[0]
    print("discord max: " + str(discord_value))
    print("discord at: " + str(discord_index))

    rect = Rectangle((discord_index, 0), winsize, discord_value,
                     facecolor='lightgrey')
    axs[1 + i].add_patch(rect)
    axs[1 + i].set_xlabel('Time', fontsize ='20')
    axs[1 + i].set_ylabel('WND: ' + str(winsize), fontsize='20')
    axs[1 + i].plot(mp[:, 0])

plt.show()

Then you can clearly see that the
point anomalies can be detected when you don't normalize your Euclidean distances:

Let me know if this helps!

[notecola]

@seanlaw Great answer with a lot of useful information, thank you!

The AAMP is a great addition, wonderful!
Are there any future plans to create a CUDA based AAMP implementation?

Still wondering if it really makes sense trying to interpret the z-normalized matrix profile in case of non periodic time series?

[seanlaw]

@seanlaw Great answer with a lot of useful information, thank you!

Awesome! I'm glad you found it helpful. These discussions also help me think through my understanding as well.

The AAMP is a great addition, wonderful! Are there any future plans to create a CUDA based AAMP implementation?

There are currently no plans but I would recommend that, if you need it, to create a new Github issue requesting this feature. We can't promise anything as we have ton of other priorities that we'd like to get working on but a gpu_aamp might not be too hard to implement and I can see where it might be useful for others too. Though the GPU implementation would have to be done differently than the CPU implementation,

Having said that, we certainly welcome contributions for the community and I would be happy to work with you on it if you would consider contributing! Absolutely no pressure though.

Still wondering if it really makes sense trying to interpret the z-normalized matrix profile in case of non periodic time series?

This is a good question. Ultimately, there is no silver bullet. Each analysis method that you choose will come with trade-offs/assumptions. I think matrix profiles are great for exploratory data analysis as it can tell you whether or not a periodic event has occurred without assuming, a priori, that one exists. Same thing with discords. Additionally, there are a ton of other "nice" features of the matrix profile where, once you've computed it, many other analyses come essentially "for free". At the end of the day, all of these tools should be seen as complimentary and not "the one to rule them all". The great thing is that matrix profiles are fairly inexpensive to run (now) and it doesn't require that you perform any mental gymnastics to interpret.

I'd love to learn more about your use case(s)

[hmcoservit]

@seanlaw

However, we recently added an (unsupported) implementation that uses unnormalized Euclidean distance (i.e., we don't z-normalize and just compute the straight Euclidean distance) to compute matrix profiles based on this published aamp paper. If you clone the STUMPY repository and install the latest version and try:

I have to check this out too!

[JosephTLucas]

Just chiming in to +1 this conversation. I also had this use case and really appreciate the thorough analysis, Sean.

[seanlaw]

The AAMP is a great addition, wonderful! Are there any future plans to create a CUDA based AAMP implementation?

I've added this as a new feature request in issue #232

[seanlaw]

@notecola CUDA based AAMP is now available in the latest STUMPY release version 1.5.0 (along with a ton of new aamp-like functions. I'm going to go ahead and close this for now but feel free to re-open or start a new issue if you have more questions. Thank you!

[seanlaw]

@notecola Just a heads up that starting in STUMPY v1.8.0, you no longer have to call aamp and instead, you can/should use the normalize=False parameter:

stumpy.stump(T, m, normalize=False)

This is equivalent to:

stumpy.aamp(T, m)

In the background, when normalize=False, stumpy.stump just calls stumpy.aamp for you and hands over the relevant data.

[notecola]

@seanlaw Thank you for the update!