Enable stumpy.motifs() to return all the possible motifs

[giacomoguiduzzi]

Greetings,

When trying out the stumpy.motifs() function I tried setting max_motifs=np.inf, but I noticed the code requires it to be a number, so I put a very high number as a workaround. I was wondering: would it be possible to implement a check like this?

if max_motifs is None:
    <don't put a limit on the number of returned motifs>

I have implemented my own way of checking for duplicates or overlapping motifs, I just wouldn't want to skip any. What do you think about this? Is there a reason why this is not implemented?

Thanks in advance!

Best Regards,
Giacomo Guiduzzi

[seanlaw]

@giacomoguiduzzi Thank you for your question.

Frankly, motifs was intended to be a convenience function to help users get started once they computed a matrix profile and it was never meant to cover all possible cases since, as you've discovered, extracting motifs requires making assumptions (e.g., choosing a max_distance or cutoff that is very much time series dependent). Our hope was that more advanced users like you would simply use stumpy.motifs as a jumping off point to build your own custom logic for extracting motifs. Additionally, extracting all motifs can/will result in a giant result set if the wrong parameters are chosen and so we try to discourage the beginner from "shooting themselves in the foot".

so I put a very high number as a workaround

Finally, as you've correctly identified, you can set max_motifs to a large number but, in fact, you can simply set max_motifs = len(P) (or if youre lazy like me, max_motifs = len(T)) because there can NEVER be more motifs than the length of your input, or more precisely, len(T) - m + 1, which should be the same as len(P). I think that this is a reasonable tradeoff to max_motifs = None.

[giacomoguiduzzi]

Hi @seanlaw,

Thank you for your answer, which is clear and concise. Do you think it would be useful to have it written into the function documentation that it's possible to set max_motifs=len(P) if it's for testing purposes or the user knows what he's doing?

Moreover, I want to exploit this question to ask another related one. I noticed that stumpy.motifs() returns two arrays, motifs and matches, but I also noticed that these arrays are 2D. If I have a window size m=5, I would have expected to have a list of sequences of size m, or coordinates like the index on axis 0 and the sequence on axis 1 (e.g., a 10x5 array would mean having found 10 motifs of size 5). I get way bigger sequences though, and I am not really sure of how to interpret these numbers. Can I ask you to explain the data shape here or is it better if I create another discussion?

Thanks in advance for your kindness.

Best Regards,
Giacomo Guiduzzi

[seanlaw]

Do you think it would be useful to have it written into the function documentation that it's possible to set max_motifs=len(P)

I would be open to that. Maybe a comment in max_motifs like:

To consider all valid motifs, you may set max_motifs to be the length of your input matrix profile (i.e., max_motifs=len(P))

To your second question:

I noticed that stumpy.motifs() returns two arrays, motifs and matches

According to the stumpy.motifs documentation, what is returned are the "motif distances" and the "motif indices". Anyhow, let's use this example:

import numpy as np
import stumpy

np.random.seed(0)
T = np.random.rand(100)
m = 5

mp = stumpy.stump(T, m)
motif_distances, motif_indices = stumpy.motifs(
        T,
        mp[:, 0],
        max_distance=np.inf,
        cutoff=np.inf,
        max_motifs=5,
        min_neighbors=1
)

So the motif_distances would be:

[[0.         0.08981511 0.42650516 0.68408535 0.98880333 1.21083773  1.28265441 1.38319011 1.49639677 1.67451732]
 [0.         0.27054555 1.02202283 1.20533935 1.21428651 1.32336783  1.35910497 1.43831474 1.54916232 1.83326773]
 [0.         0.41958675 0.75400348 1.10538592 1.1369166  1.20880986  1.45960704 1.46495518 1.46974129 1.54189829]
 [0.         0.58422162 1.32937922 1.49938887 1.52441222 1.62455208  1.66341761 1.83584812 1.85687152 1.86424029]
 [0.         0.90998442 0.94587034 1.0741843  1.18360818 1.21962711  1.55303998 1.67985013 1.68203287 1.69825012]]

where each row corresponds to the results for a given motif. The motif_indices are:

[[66 76 23 84 89 94  3 70 31 40]
 [20 83 93 10 39  2 88  7 73 65]
 [35 53 59 63 28 17 14 24 47 86]
 [50 11 60 91 72 36 21 25 18 56]
 [79 64 94 48  3 40  9  6 34 87]]

So, to interpret this, you'd look at the first row of motif_indices and see [66, 76, 23, 84, 89, 94, 3, 70, 31, 40]. The 66 is the subsequence index for T[66 : 66 + m] and this is your first motif. Notice that the first row in motif_distances corresponds exactly to this same subsequence. The best matches for T[66 : 66 + m] are subsequences located (from closest to farther) at indices [76, 23, 84, 89, 94, 3, 70, 31, 40]. Thus, the distance between T[66 : 66 + m] and T[76 : 76 + m] is 0.08981511 (i.e., motif_distances[0, 1] and the distance between T[66 : 66 + m] and T[23 : 23 + m] is 0.42650516 (i.e., motif_distance[0, 2]). And so these two pieces of information can tell you everything that you need to know about the identified motifs.

[giacomoguiduzzi]

Hi @seanlaw,

Thank you very much for explaining it. First, it looks like a visualization bug for the stumpy.stumped documentation in PyCharm, which I used as a reference. In the documentation, as well as in the code, it is written that the function returns two different arrays as you reported. The issue is that with the way the documentation appeared to me it wasn't clear at all:

Returns:
The distances corresponding to a set of subsequence matches for each motif. Note that the first column always corresponds to the distance for the self-match/ trivial-match for each motif.

Together with this, what deceived me is this part of the documentation:

Note that, in the best case scenario, the returned arrays would have shape (max_motifs, max_matches) and contain all finite values.

Now that you cleared it up it makes a lot more sense: the rows are the number of motifs found, and for each motif, the indexes are the starting point of the closest matches found for that motif (first found at index 0 of the array). Thus we could say that what was returned by stumpy.motifs was motif -> list of motifs with the same size found. Nonetheless, I am wondering: was it a casualty that your example has exactly 5 rows, or is it somehow related to the value of m?
Please let me know if I got everything right. Moreover, may I go ahead adding the comment you suggested?

Thanks once again,
Giacomo Guiduzzi

[seanlaw]

Thus we could say that what was returned by stumpy.motifs was motif -> list of motifs with the same size found.

I'm not sure what you mean by "motifs with the same size found". Each motif (row) that is identified may have up to max_matches number of subsequence matches. That means that each motif can have 1 match, 2 matches, 3 matches, ..., but no more than max_matches. When there are not enough matches to reach max_matches, you'll encounter an np.nan value in those places in the array (or the number of columns will be truncated).

Nonetheless, I am wondering: was it a casualty that your example has exactly 5 rows, or is it somehow related to the value of m?

No, there were "5 rows" because the maximum number of motifs, max_motifs was set to 5 and so at most 5 motifs will be returned (maybe less but never more than 5. If you had set max_motifs=3, then you'd get at most 3 motifs (even if more exist):

import numpy as np
import stumpy

np.random.seed(0)
T = np.random.rand(100)
m = 5
mp = stumpy.stump(T, m)
motif_distances, motif_indices = stumpy.motifs(
    T,
    mp[:, 0],
    max_distance=np.inf,
    cutoff=np.inf,
    max_motifs=3,
    min_neighbors=1
)

The outputs would be:

array([[0.        , 0.08981511, 0.42650516, 0.68408535, 0.98880333, 1.21083773, 1.28265441, 1.38319011, 1.49639677, 1.67451732],
       [0.        , 0.27054555, 1.02202283, 1.20533935, 1.21428651, 1.32336783, 1.35910497, 1.43831474, 1.54916232, 1.83326773],
       [0.        , 0.41958675, 0.75400348, 1.10538592, 1.1369166 , 1.20880986, 1.45960704, 1.46495518, 1.46974129, 1.54189829]])

and

array([[66, 76, 23, 84, 89, 94,  3, 70, 31, 40],
       [20, 83, 93, 10, 39,  2, 88,  7, 73, 65],
       [35, 53, 59, 63, 28, 17, 14, 24, 47, 86]])

Note that setting max_motifs=50 only returns 6 "valid" motifs!

Please let me know if I got everything right. Moreover, may I go ahead adding the comment you suggested?

I've gone ahead and added a note to the max_motifs section of the documentation:

https://stumpy.readthedocs.io/en/latest/api.html#motifs

[giacomoguiduzzi]

Hi @seanlaw,

I didn't notice the max_motifs parameter being focused on understanding the data structure, thanks for pointing that out. And thanks for adding the comment, I wanted to help and contribute by doing it myself without taking more of your time, that's why I proposed it. Anyway, what I meant with "motifs with the same size found" I mean that each index / distance relates to a motif of size m found in the time series. Also, thanks for clarifying the NaN values, I was wondering what was happening when debugging my script.
Everything looks crystal clear now. Is there one specific message you'd prefer to mark as the answer to this discussion?

Best,
Giacomo Guiduzzi

[seanlaw]

I wanted to help and contribute by doing it myself without taking more of your time, that's why I proposed it.

No problem! It's important for us to get the documentation "right" and to ensure that things get communicated properly. Your feedback is helpful. Additionally, if you feel inclined to contribute, please take a look at our Github Issues and we can work together.

Is there one specific message you'd prefer to mark as the answer to this discussion?

No, I'll leave it up to you to decide. I think what's more important is the information that is shared across the entire discussion and I hope that it can also help others.