Add support for discords for multivariate time-series

[shfa5275]

While the paper
Yeh, Chin-Chia Michael, et al. (2017) Matrix Profile VI: Meaningful Multidimensional Motif Discovery. ICDM:565-574
only deals with motifs, it will be of great value for those who are interested in detecting outliers in multivariate time-series.

[seanlaw]

@shfa5275 Welcome to our community! Do you happen to have some ideas on how one could accomplish this?

[seanlaw]

@shfa5275 Do you think that all that is needed is to perform a column-wise descending sort (or, similarly, perform the regular ascending sort and then reverse the array)? If so, then this should be pretty straightforward and we can add an argument to mstump/mstumped like discord=True

@mexxexx @robertsd Do either of you have any thoughts about this?

[shfa5275]

@seanlaw, I think so, since discords have high matrix-profile values, they are the opposite of the motifs. But there seems a little problem here. In a $d$ dimensional time-series, there will be $d$ matrix-profiles, and consequently, there will have $d$ discord locations (assuming, for now, that only the location with the highest matrix-profile value is of interest). Of course, visual inspection is an important starting point, nonetheless, it can be overwhelming for a large $d$. Therefore, I am wondering if there is a possibility for you to implement Minimum Description Length (MDL) (as suggested in the aforementioned paper) or a related idea to determine the $k<<d$ most relevant dimensions. And then both motifs and discords can be searched for within those $k$ dimensions.

Besides, any future plans to add search constraints (inclusion, exclusion)?

[seanlaw]

I think so, since discords have high matrix-profile values, they are the opposite of the motifs.

Great, I think I can add the reverse sort and include it in the next release.

But there seems a little problem here. In a $d$ dimensional time-series, there will be $d$ matrix-profiles, and consequently, there will have $d$ discord locations (assuming, for now, that only the location with the highest matrix-profile value is of interest). Of course, visual inspection is an important starting point, nonetheless, it can be overwhelming for a large $d$. Therefore, I am wondering if there is a possibility for you to implement Minimum Description Length (MDL) (as suggested in the aforementioned paper) or a related idea to determine the $k<<d$ most relevant dimensions. And then both motifs and discords can be searched for within those $k$ dimensions.

Since I consider MDL to be a post-processing step, this may possibly be outside of the scope of STUMPY (which is to offer a way for the user to efficiently compute the matrix profile). I am not opposed to it and you should definitely create a separate feature request for MDL. At the moment, there are several other priorities that I would like to get to first but I'll let @mexxexx chime in as he may be convinced to add MDL to some enhancements that he is currently working on. Of course, we would appreciate new contributions and we'd be willing to work with you and support you if you care to submit a PR for MDL!

Besides, any future plans to add search constraints (inclusion, exclusion)?

It's funny that you should ask this. We just added "inclusion" support last week (it is pushed into Master but will likely hit version 1.4.0 in a few weeks) and you can read more about it in issue #180. In short, based on the paper, "exclusion" just requires you to leave those dimensions out of your matrix profile calculation so that is easily handled by the user (by omitting time series rows of the excluded dimensions before calling mstump/mstumped). "inclusion" is only one that requires code modifications at run-time and that is available in Master now (simply add a include=[1, 6, 9] to your mstump/mstumped function call where those are zero-based indices of the dimensions that you want to include in that order). Let me know if that makes sense.

[mihailescum]

Personally, I would like stumpy to include algorithms built on top of the MP, which is why I'm writing a motif discovery module. Of course, like this support of the library is more difficult, but I think it is nice to have a place where common algorithms are shared, so that you don't have to rewrite them from scratch. But, this is not my place to decide, but @seanlaw .

However, MDL and multi dimensional motif/discord search is outside the scope of what I'm writing right now. If anybody wants to build on the 1D case, please feel free.

[seanlaw]

Personally, I would like stumpy to include algorithms built on top of the MP, which is why I'm writing a motif discovery module. Of course, like this support of the library is more difficult, but I think it is nice to have a place where common algorithms are shared, so that you don't have to rewrite them from scratch. But, this is not my place to decide, but @seanlaw .

Thanks @mexxexx! First off, I want to explicitly state that I am open to suggestions and I do not want to be overly dismissive of ideas or increasing the scope. I agree that it would be super helpful to have a central place for algorithms (that build upon MP) to be shared. I was hoping that place would be in the tutorials section of our readthedocs page (in the form of Jupyter notebooks). Maybe it might make sense to have a "User Case Study" or "Useful Concepts" section where we can post user examples. This way, STUMPY doesn't have to support everything immediately and we can iterate, evolve, and migrate useful concepts/algorithms from these case studies over time and incorporate them thoughtfully into the code base as we understand them better.

However, MDL and multi dimensional motif/discord search is outside the scope of what I'm writing right now. If anybody wants to build on the 1D case, please feel free.

Minimally, we should capture these requests, which I've done here:

1. MDL
2. M-dimensional discord/motif search

[seanlaw]

@shfa5275 This feature has been implemented now. Please feel free to re-open this issue if you have any questions on this, add discussions to the other MDL/search issues, or open up a new issue altogether.