FLUSS - semantic segmentation using the MPI

This PR adds the FLUSS algorithm which provides Fast Low-cost Unipotent Semantic Segmentation. It is defined in pseudo-code in MP paper VIII, which I've added as a source in the Readme as well.

This PR changes the following items:

1. New: matrixprofile/fluss.py defines the fluss function. It returns the Corrected Arc Curve, based on the matrix profile index and the subsequence length.
2. New: tests/test_fluss.py defines a functionality test.
3. Changed: matrixprofile/__init__.py now includes fluss.
4. Changed: docs/examples/Matrix_Profile_Tutorial.ipynb now includes an example (plot) of FLUSS.
5. Changed: README.md now includes a reference to the algorithm and the paper.

A nice future feature would be to implement the anytime version of this algorithm (which does produce slightly different results). For now, I think this is already a useful addition. If there are things that need to be improved, please let me know and I'll have a look at them!

Hi, Very interesting concept thanks for coding it and sharing it. In the readme, you mention:

We can introduce an anomaly to the end of the time series and use STAMPI to detect it And then you conclude The Matrix Profile has spiked in value, highlighting the (potential) presence of a new behavior

I am a bit puzzled by this.. Yes the matrix profile has spiked but so did the data. I do not see in this example the additional value of STAMPI. Overall I am a bit confused about how to interpret the data. Especially if you'd like to do it in an automatic way for an anomaly detection. Here is a picture taking the example with some questions.. The first one, the number seems pretty high, so this mean that the z-norm euclidian distance is high (correct me if I am wrong). However, I could argue that there was just a changepoint and this is the normal "new behavior" (ie. there was an earthquake at the beginning of the data and then it went off). Going into this logic, I would interpret the black square more as outliers than "normal" but in this the MP have values close to 0 which would mean (if I understand correctly) that it should not be seen as outliers. Finally at the end I am unsure why I see an initial spike or the data going back to 0. I am sure this come from my lack of understanding of the MP but it might be nice to add a more detailed description of this chart as well as a function or an heuristic in the readme to automatically detect outliers using MP. Best,

So, I have no idea what the difference between these two packages? They both have pip, but there is no more update in matrixprofile-ts. Strangely, matrixprofile-ts has more stars. Can anyone answer my question?

Hi, thank you for sharing the Matrix Profile code.It is very helpfull

I have a time series sample data with a frequency of one point per hour and it work's perfectly with a period of 24, as you can see in image below.

the code used was this:

df_Sample = pd.read_csv('Sample.csv', sep=',') df_Sample= df_Sample.drop(columns=['Index']) new_df= df_Sample[:1156] a = new_df.values.squeeze() m=24 profile = matrixProfile.stomp(a,m) new_df['profile'] = np.append(profile[0],np.zeros(m-1)+np.nan) new_df['profile_index'] = np.append(profile[1], np.zeros(m - 1) + np.nan) fig, (ax1, ax2) = plt.subplots(2,1,sharex=True,figsize=(15,10)) new_df['Value'].plot(ax=ax1, style='.', title='Sample') new_df['profile'].plot(ax=ax2, c='r', title='Matrix Profile') plt.show()

But when I add additional time series data (that is constant) this happens:

The code is the same but instead of "new_df= df_Sample[:1156]" I defined "new_df= df_Sample".

I was expecting a different result. It seems that the constant values are destroying all the previous analyses. Is this a bug?

Thanks in advance,

David

Sample.zip

Can any one provide definitions of the used parameters. The questions are:

(1) How does one determine the samples to be excluded?

Computes the top k motifs from a matrix profile Parameters ---------- ts: time series to used to calculate mp mp: tuple, (matrix profile numpy array, matrix profile indices) max_motifs: the maximum number of motifs to discover ex_zone: the number of samples to exclude and set to Inf on either side of a found motifs defaults to m/2 Returns tuple (motifs, distances) motifs: a list of lists of indexes representing the motif starting locations. distances: list of minimum distances for each motif """

I tried to use matrix profile to analyse data with missing values, unfortunately I get an empty graph. Is it possible to analyse data with missing values with this implementation? Since in the paper it was stated that matrix profile should result some analysis even with missing data.

I would like to use your algorithm but I have one question. My problem is this: I have a query (pattern of interest) and I would like to find in a time series the patterns that are the closest to the query. Should I use in this case the matrix profile (SCRIMP++) or MASS? Thank you!

Using exactly the Tutorial code under Python 2.7 with miniconda environment, when running the following section, got an error. Is this just me ? can anyone help please? : Calculate the Matrix Profile

m = 32
mp = matrixProfile.stomp(pattern,m)

TypeError                                 Traceback (most recent call last)
<ipython-input-3-d3196b066bd3> in <module>()
      1 m = 32
----> 2 mp = matrixProfile.stomp(pattern,m)

/Users/dev/miniconda2/envs/dsf/lib/python2.7/site-packages/matrixprofile/matrixProfile.pyc in stomp(tsA, m, tsB)
    270     tsB: Time series to compare the query against. Note that, if no value is provided, tsB = tsA by default.
    271     """
--> 272     return _matrixProfile_stomp(tsA,m,order.linearOrder,distanceProfile.STOMPDistanceProfile,tsB)
    273 
    274 

/Users/dev/miniconda2/envs/dsf/lib/python2.7/site-packages/matrixprofile/matrixProfile.pyc in _matrixProfile_stomp(tsA, m, orderClass, distanceProfileFunction, tsB)
    166 
    167         #Need to pass in the previous sliding dot product for subsequent distance profile calculations
--> 168         (distanceProfile,querySegmentsID),dot_prev = distanceProfileFunction(tsA,idx,m,tsB,dot_first,dp,mean,std)
    169 
    170         if idx == 0:

/Users/dev/miniconda2/envs/dsf/lib/python2.7/site-packages/matrixprofile/distanceProfile.pyc in STOMPDistanceProfile(tsA, idx, m, tsB, dot_first, dp, mean, std)
    116     #Calculate the first distance profile via MASS
    117     if idx == 0:
--> 118         distanceProfile = np.real(np.sqrt(mass(query,tsB).astype(complex)))
    119 
    120         #Currently re-calculating the dot product separately as opposed to updating all of the mass function...

/Users/dev/miniconda2/envs/dsf/lib/python2.7/site-packages/matrixprofile/utils.pyc in mass(query, ts)
    172     q_std = np.std(query)
    173     mean, std = movmeanstd(ts,m)
--> 174     dot = slidingDotProduct(query,ts)
    175 
    176     #res = np.sqrt(2*m*(1-(dot-m*mean*q_mean)/(m*std*q_std)))

/Users/dev/miniconda2/envs/dsf/lib/python2.7/site-packages/matrixprofile/utils.pyc in slidingDotProduct(query, ts)
    122 
    123 
--> 124     query = np.pad(query,(0,n-m+ts_add-q_add),'constant')
    125 
    126     #Determine trim length for dot product. Note that zero-padding of the query has no effect on array length, which is solely determined by the longest vector

/Users/dev/miniconda2/envs/dsf/lib/python2.7/site-packages/numpy/lib/arraypad.pyc in pad(array, pad_width, mode, **kwargs)
   1383                                 pad_width[iaxis],
   1384                                 iaxis,
-> 1385                                 kwargs)
   1386         return newmat
   1387 

/Users/dev/miniconda2/envs/dsf/lib/python2.7/site-packages/numpy/lib/shape_base.pyc in apply_along_axis(func1d, axis, arr, *args, **kwargs)
     89     outshape = asarray(arr.shape).take(indlist)
     90     i.put(indlist, ind)
---> 91     res = func1d(arr[tuple(i.tolist())], *args, **kwargs)
     92     #  if res is a number, then we have a smaller output array
     93     if isscalar(res):

TypeError: 'unicode' object is not callable

We've seen interest in making the library compatible with Python 2. We will explore possible avenues, but if you have any thoughts on the subject please reach out.

Looks like there are both a LICENSE as well as a License.md file in the repo. The LICENSE file is the authoritative full-length Apache license, while the License.md is the short-form version, suitable for top-of-file comment header, for example, but not a substitute for the full license.

It would be good to remove License.md since it's the short-form version, and it's currently keeping the repo from getting the automatic "Apache 2.0" license badge on the overview page courtesy of GitHub's automatic license detector, due to the presence of 2 license files.

Thanks!

I observed different results when calculating the distance profile using the brute force search algorithm and the function matrixprofile.MASS.distance_profile(). Here is a sample of my code:

calculate by brute force

query_ = (query - query.mean()) / query.std(ddof=0) len_m = query.shape[0] dist = [] for index in range(0, serie.shape[0] - len_m + 1): sub = serie[index:index + len_m] sub = (sub - sub.mean()) / sub.std(ddof=0) dist.append(np.sqrt(np.sum(np.power(sub - query_, 2)))) dist = np.array(dist)

This is less of an issue and more me trying to validate the work of a colleague who has already implemented a version of matrix profile. Given it has already been implemented by this group I thought it would be best to open up dialogue. Thanks!

Bumps setuptools from 39.1.0 to 65.5.1.

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

Bumps numpy from 1.16.2 to 1.22.0.

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

Minor, but keeps popping up in tooling we're doing:

In matrixprofile/matrixProfile.py the use of is (instead of ==) to compare n_threads to non-object -1 prompts SyntaxWarning: "is" with a literal.

In:

mp = matrixProfile.stomp(pattern,m) mtfs ,motif_d = motifs.motifs(pattern, mp, max_motifs=10)

self._set_item(key, value) value = self._sanitize_column(key, value) alue = sanitize_index(value, self.index, copy=False)

Any idea how to solve this?

The following code below gives nan and inf values; am I using this incorrectly?

seconds = np.arange(30) traffic_light = np.array([0]*15 + [1]*5 + [2]*10) brake_0 = np.array([0]*15 + [1, 2, 3, 4, 5] + [8, 10, 10, 10, 8, 6, 4, 2, 0, 0])

matrixProfile.stomp(traffic_light, 3) matrixProfile.stomp(brake_0, 3)