STUMPY Basics¶

Analyzing Motifs and Anomalies with STUMP¶

This tutorial utilizes the main takeaways from the research papers: Matrix Profile I & Matrix Profile II.

To explore the basic concepts, we'll use the workhorse stump function to find interesting motifs (patterns) or discords (anomalies/novelties) and demonstrate these concepts with two different time series datasets:

1. The Steamgen dataset
2. The NYC taxi passengers dataset

stump is Numba JIT-compiled version of the popular STOMP algorithm that is described in detail in the original Matrix Profile II paper. stump is capable of parallel computation and it performs an ordered search for patterns and outliers within a specified time series and takes advantage of the locality of some calculations to minimize the runtime.

Getting Started¶

Let's import the packages that we'll need to load, analyze, and plot the data.

What is a Motif?¶

Time series motifs are approximately repeated subsequences found within a longer time series. Being able to say that a subsequence is "approximately repeated" requires that you be able to compare subsequences to each other. In the case of STUMPY, all subsequences within a time series can be compared by computing the pairwise z-normalized Euclidean distances and then storing only the index to its nearest neighbor. This nearest neighbor distance vector is referred to as the matrix profile and the index to each nearest neighbor within the time series is referred to as the matrix profile index. Luckily, the stump function takes in any time series (with floating point values) and computes the matrix profile along with the matrix profile indices and, in turn, one can immediately find time series motifs. Let's look at an example:

Loading the Steamgen Dataset¶

This data was generated using fuzzy models applied to mimic a steam generator at the Abbott Power Plant in Champaign, IL. The data feature that we are interested in is the output steam flow telemetry that has units of kg/s and the data is "sampled" every three seconds with a total of 9,600 datapoints.

Visualizing the Steamgen Dataset¶

Take a moment and carefully examine the plot above with your naked eye. If you were told that there was a pattern that was approximately repeated, can you spot it? Even for a computer, this can be very challenging. Here's what you should be looking for:

Manually Finding a Motif¶

The motif (pattern) that we are looking for is highlighted above and yet it is still very hard to be certain that the orange and green subsequences are a match (upper panel), that is, until we zoom in on them and overlay the subsequences on top each other (lower panel). Now, we can clearly see that the motif is very similar! The fundamental value of computing the matrix profile is that it not only allows you to quickly find motifs but it also identifies the nearest neighbor for all subsequences within your time series. Note that we haven't actually done anything special here to locate the motif except that we grab the locations from the original paper and plotted them. Now, let's take our steamgen data and apply the stump function to it:

Find a Motif Using STUMP¶

stump requires two parameters:

1. A time series
2. A window size, m

In this case, based on some domain expertise, we've chosen m = 640, which is roughly equivalent to half-hour windows. And, again, the output of stump is an array that contains all of the matrix profile values (i.e., z-normalized Euclidean distance to your nearest neighbor) and matrix profile indices in the first and second columns, respectively (we'll ignore the third and fourth columns for now). To identify the index location of the motif we'll need to find the index location where the matrix profile, mp[:, 0], has the smallest value:

With this motif_idx information, we can also identify the location of its nearest neighbor by cross-referencing the matrix profile indices, mp[:, 1]:

Now, let's put all of this together and plot the matrix profile next to our raw data:

What we learn is that the global minima (vertical dashed lines) from the matrix profile correspond to the locations of the two subsequences that make up the motif pair! And the exact z-normalized Euclidean distance between these two subsequences is:

So, this distance isn't zero since we saw that the two subsequences aren't an identical match but, relative to the rest of the matrix profile (i.e., compared to either the mean or median matrix profile values), we can understand that this motif is a significantly good match.

Find Potential Anomalies (Discords) using STUMP¶

Conversely, the index location within our matrix profile that has the largest value (computed from stump above) is:

And the nearest neighbor to this discord has a distance that is quite far away:

The subsequence located at this global maximum is also referred to as a discord, novelty, or "potential anomaly":

Now that you've mastered the STUMPY basics and understand how to discover motifs and anomalies from a time series, we'll leave it up to you to investigate other interesting local minima and local maxima in the steamgen dataset.

To further develop/reinforce our growing intuition, let's move on and explore another dataset!

Loading the NYC Taxi Passengers Dataset¶

First, we'll download historical data that represents the half-hourly average of the number of NYC taxi passengers over 75 days in the Fall of 2014.

We extract that data and insert it into a pandas dataframe, making sure the timestamps are stored as datetime objects and the values are of type float64. Note that we'll do a little more data cleaning than above just so you can see an example where the timestamp is included. But be aware that stump does not actually use or need the timestamp column at all when computing the matrix profile.

Visualizing the Taxi Dataset¶

It seems as if there is a general periodicity between spans of 1-day and 7-days, which can likely be explained by the fact that more people use taxis throughout the day than through the night and that it is reasonable to say most weeks have similar taxi-rider patterns. Also, maybe there is an outlier just to the right of the window starting near the end of October but, other than that, there isn't anything you can conclude from just looking at the raw data.

Generating the Matrix Profile¶

Again, defining the window size, m, usually requires some level of domain knowledge but we'll demonstrate later on that stump is robust to changes in this parameter. Since this data was taken half-hourly, we chose a value m = 48 to represent the span of exactly one day:

Visualizing the Matrix Profile¶

Understanding the Matrix Profile¶

Let's understand what we're looking at.

Lowest Values¶

The lowest values (open triangles) are considered a motif since they represent the pair of nearest neighbor subsequences with the smallest z-normalized Euclidean distance. Interestingly, the two lowest data points are exactly 7 days apart, which suggests that, in this dataset, there may be a periodicity of seven days in addition to the more obvious periodicity of one day.

Highest Values¶

So what about the highest matrix profile values (filled triangles)? The subsequences that have the highest (local) values really emphasizes their uniqueness. We found that the top three peaks happened to correspond exactly with the timing of Columbus Day, Daylight Saving Time, and Thanksgiving, respectively.

Different Window Sizes¶

As we had mentioned above, stump should be robust to the choice of the window size parameter, m. Below, we demonstrate how manipulating the window size can have little impact on your resulting matrix profile by running stump with varying windows sizes.

We purposely chose spans of time that correspond to reasonably intuitive day-lengths that could be chosen by a human.

We can see that even with varying window sizes, our peaks stay prominent. But it looks as if all the non-peak values are converging towards each other. This is why having a knowledge of the data-context is important prior to running stump, as it is helpful to have a window size that may capture a repeating pattern or anomaly within the dataset.

GPU-STUMP - Faster STUMP Using GPUs¶

When you have significantly more than a few thousand data points in your time series, you may need a speed boost to help analyze your data. Luckily, you can try gpu_stump, a super fast GPU-powered alternative to stump that gives speed of a few hundred CPUs and provides the same output as stump:

import stumpy

mp = stumpy.gpu_stump(df['value'], m=m)  # Note that you'll need a properly configured NVIDIA GPU for this

In fact, if you aren't dealing with PII/SII data, then you can try out gpu_stump using the this notebook on Google Colab.

STUMPED - Distributed STUMP¶

Alternatively, if you only have access to a cluster of CPUs and your data needs to stay behind your firewall, then stump and gpu_stump may not be sufficient for your needs. Instead, you can try stumped, a distributed and parallel implementation of stump that depends on Dask distributed:

import stumpy
from dask.distributed import Client

dask_client = Client()

mp = stumpy.stumped(dask_client, df['value'], m=m)  # Note that a dask client is needed

Bonus Section - Understanding the Matrix Profile Columnar Output¶

For any 1-D time series, T, its matrix profile, mp, computed from stumpy.stump(T, m) will contain 4 explicit columns, which we'll describe in a moment. Implicitly, the ith row of the mp array corresponds to the set of (4) nearest neighbor values computed for the specific subsequence T[i : i + m].

The first column of the mp contains the matrix profile (nearest neighbor distance) value, P (note that due to zero-based indexing, the "first column" has a column index value of zero). The second column contains the (zero-based) index location, I, of where the (above) nearest neighbor is located along T (note that any negative index values are "bad" values and indicates that a nearest neighbor could not be found).

So, for the ith subsequence T[i : i + m], its nearest neighbor (located somewhere along T) has a starting index location of I = mp[i, 1] and, assuming that I >= 0, this corresponds to the subsequence found at T[I : I + m]. And the matrix profile value for the ith subsequence, P = [i, 0], is the exact (z-normalized Euclidean) distance between T[i : i + m] and T[I : I + m]. Note that the nearest neighbor index location, I, can be positioned ANYWHERE. That is, dependent upon the ith subsequence, its nearest neighbor, I, can be located before/to-the-"left" of i (i.e., I <= i) or come after/to-the-"right" of i (i.e., I >= i). In other words, there is no constraint on where a nearest neighbor is located. However, there may be a time when you might like to only know about a nearest neighbor that either comes before/after i and this is where columns 3 and 4 of mp come into play.

The third column contains the (zero-based) index location, IL, of where the "left" nearest neighbor is located along T. Here, there is a constraint that IL < i or that IL must come before/to-the-left of i. Thus, the "left nearest neighbor" for the ith subsequence would be located at IL = mp[i, 2] and corresponds to T[IL : IL + m]. The fourth column contains the (zero-based) index location, IR, of where the "right" nearest neighbor is located along T. Here, there is a constraint that IR > i or that IR must come after/to-the-right of i. Thus, the "right nearest neighbor" for the ith subsequence would be located at IR = mp[i, 3] and corresponds to T[IR : IR + m].

Again, note that any negative index values are "bad" values and indicates that a nearest neighbor could not be found.

To reinforce this more concretely, let's use the following mp array as an example:

array([[1.626257115121311,  202, -1,  202],
       [1.7138456780667977,  65,  0,   65],
       [1.880293454724256,   66,  0,   66],
       [1.796922109741226,   67,  0,   67],
       [1.4943082939628236,  11,  1,   11],
       [1.4504278114808016,  12,  2,   12],
       [1.6294354134867932,  19,  0,   19],
       [1.5349365731102185, 229,  0,  229],
       [1.3930265554289831, 186,  1,  186],
       [1.5265881687159586, 187,  2,  187],
       [1.8022253384245739,  33,  3,   33],
       [1.4943082939628236,   4,  4,  118],
       [1.4504278114808016,   5,  5,  137],
       [1.680920620705546,  201,  6,  201],
       [1.5625058007723722, 237,  8,  237],
       [1.2860008417613522,  66,  9,   -1]]

Here, the subsequence at i = 0 would correspond to the T[0 : 0 + m] subsequence and the nearest neighbor for this subsequence is located at I = 202 (i.e., mp[0, 1]) and corresponds to the T[202 : 202 + m] subsequence. The z-normalized Euclidean distance between T[0 : 0 + m] and T[202 : 202 + m] is actually P = 1.626257115121311 (i.e., mp[0, 0]). Next, notice that the location of the left nearest neighbor is IL = -1 (i.e., mp[0, 2]) and, since negative indices are "bad", this tells us that the left nearest neighbor could not be found. Hopefully, this makes sense since T[0 : 0 + m] is the first subsequence in T and there are no other subsequences that can possibly exist to the left of T[0 : 0 + m]! Conversely, the location of the right nearest neighbor is IR = 202 (i.e., mp[0, 3]) and corresponds to the T[202 : 202 + m] subsequence.

Additionally, the subsequence at i = 5 would correspond to the T[5 : 5 + m] subsequence and the nearest neighbor for this subsequence is located at I = 12 (i.e., mp[5, 1]) and corresponds to the T[12 : 12 + m] subsequence. The z-normalized Euclidean distance between T[5 : 5 + m] and T[12 : 12 + m] is actually P = 1.4504278114808016 (i.e., mp[5, 0]). Next, the location of the left nearest neighbor is IL = 2 (i.e., mp[5, 2]) and corresponds to T[2 : 2 + m]. Conversely, the location of the right nearest neighbor is IR = 12 (i.e., mp[5, 3]) and corresponds to the T[12 : 12 + m] subsequence.

Similarly, all other subsequences can be evaluated and interpreted using this approach!

Summary¶

And that's it! You have now loaded in a dataset, ran it through stump using our package, and were able to extract multiple conclusions of existing patterns and anomalies within the two different time series. You can now import this package and use it in your own projects. Happy coding!

Resources¶

Matrix Profile I

Matrix Profile II

STUMPY Documentation

STUMPY Matrix Profile Github Code Repository