Matrix Profile: Motifs, chains and discords

Learn how to use one of the most important algorithms in current time series analysis and interpret its results

Introduction

When analyzing time series data, we are often interested in finding recurring and unique patterns. Additionally, we might be interested in how recurring patterns change over time. The Matrix Profile algorithm can answer these questions.

In the context of using the Matrix Profile, recurring patterns are called motifs, evolving motifs are called chains and anomalies are called discords.

API request and response

We can make an example request with a time series with a length of 100 data points to the Matrix Profile endpoint of the Time Door API.

The Time Door API response:

{
  "report": {
    "computation_time": {
      "actual": 392.86,
      "billed": 400
    }
  },
  "result": {
    "reproduction": {},
    "data": {
      "matrix_profile": [
        {
          "t": "2020-01-01T00:00:00Z",
          "distance": 0.9539
        },
        {
          "t": "2020-01-01T00:00:01Z",
          "distance": 0.689
        },
        {
          "t": "2020-01-01T00:00:02Z",
          "distance": 1.028
        },
        {
          "t": "2020-01-01T00:00:03Z",
          "distance": 0.732
        },
        {
          "t": "2020-01-01T00:00:04Z",
          "distance": 0.5966
        },
        {
          "t": "2020-01-01T00:00:05Z",
          "distance": 0.622
        },
        {
          "t": "2020-01-01T00:00:06Z",
          "distance": 0.7389
        },
        {
          "t": "2020-01-01T00:00:07Z",
          "distance": 1.02
        },
        {
          "t": "2020-01-01T00:00:08Z",
          "distance": 1.713
        },
        {
          "t": "2020-01-01T00:00:09Z",
          "distance": 2.306
        },
        {
          "t": "2020-01-01T00:00:10Z",
          "distance": 1.92
        },
        {
          "t": "2020-01-01T00:00:11Z",
          "distance": 1.463
        },
        {
          "t": "2020-01-01T00:00:12Z",
          "distance": 1.278
        },
        {
          "t": "2020-01-01T00:00:13Z",
          "distance": 1.274
        },
        {
          "t": "2020-01-01T00:00:14Z",
          "distance": 1.294
        },
        {
          "t": "2020-01-01T00:00:15Z",
          "distance": 1.213
        },
        {
          "t": "2020-01-01T00:00:16Z",
          "distance": 0.9444
        },
        {
          "t": "2020-01-01T00:00:17Z",
          "distance": 1.1
        },
        {
          "t": "2020-01-01T00:00:18Z",
          "distance": 1.429
        },
        {
          "t": "2020-01-01T00:00:19Z",
          "distance": 1.738
        },
        {
          "t": "2020-01-01T00:00:20Z",
          "distance": 1.791
        },
        {
          "t": "2020-01-01T00:00:21Z",
          "distance": 1.3
        },
        {
          "t": "2020-01-01T00:00:22Z",
          "distance": 0.7819
        },
        {
          "t": "2020-01-01T00:00:23Z",
          "distance": 0.6831
        },
        {
          "t": "2020-01-01T00:00:24Z",
          "distance": 0.8584
        },
        {
          "t": "2020-01-01T00:00:25Z",
          "distance": 1.071
        },
        {
          "t": "2020-01-01T00:00:26Z",
          "distance": 1.667
        },
        {
          "t": "2020-01-01T00:00:27Z",
          "distance": 1.983
        },
        {
          "t": "2020-01-01T00:00:28Z",
          "distance": 2.029
        },
        {
          "t": "2020-01-01T00:00:29Z",
          "distance": 2.266
        },
        {
          "t": "2020-01-01T00:00:30Z",
          "distance": 2.714
        },
        {
          "t": "2020-01-01T00:00:31Z",
          "distance": 3.146
        },
        {
          "t": "2020-01-01T00:00:32Z",
          "distance": 3.216
        },
        {
          "t": "2020-01-01T00:00:33Z",
          "distance": 2.517
        },
        {
          "t": "2020-01-01T00:00:34Z",
          "distance": 2.395
        },
        {
          "t": "2020-01-01T00:00:35Z",
          "distance": 2.073
        },
        {
          "t": "2020-01-01T00:00:36Z",
          "distance": 1.953
        },
        {
          "t": "2020-01-01T00:00:37Z",
          "distance": 1.462
        },
        {
          "t": "2020-01-01T00:00:38Z",
          "distance": 1.387
        },
        {
          "t": "2020-01-01T00:00:39Z",
          "distance": 0.8539
        },
        {
          "t": "2020-01-01T00:00:40Z",
          "distance": 0.7496
        },
        {
          "t": "2020-01-01T00:00:41Z",
          "distance": 0.6341
        },
        {
          "t": "2020-01-01T00:00:42Z",
          "distance": 0.5546
        },
        {
          "t": "2020-01-01T00:00:43Z",
          "distance": 0.6994
        },
        {
          "t": "2020-01-01T00:00:44Z",
          "distance": 0.7522
        },
        {
          "t": "2020-01-01T00:00:45Z",
          "distance": 0.6976
        },
        {
          "t": "2020-01-01T00:00:46Z",
          "distance": 0.7315
        },
        {
          "t": "2020-01-01T00:00:47Z",
          "distance": 0.6498
        },
        {
          "t": "2020-01-01T00:00:48Z",
          "distance": 0.6116
        },
        {
          "t": "2020-01-01T00:00:49Z",
          "distance": 0.5972
        },
        {
          "t": "2020-01-01T00:00:50Z",
          "distance": 0.622
        },
        {
          "t": "2020-01-01T00:00:51Z",
          "distance": 0.7522
        },
        {
          "t": "2020-01-01T00:00:52Z",
          "distance": 0.6976
        },
        {
          "t": "2020-01-01T00:00:53Z",
          "distance": 0.7315
        },
        {
          "t": "2020-01-01T00:00:54Z",
          "distance": 0.6341
        },
        {
          "t": "2020-01-01T00:00:55Z",
          "distance": 0.6116
        },
        {
          "t": "2020-01-01T00:00:56Z",
          "distance": 0.5966
        },
        {
          "t": "2020-01-01T00:00:57Z",
          "distance": 0.7009
        },
        {
          "t": "2020-01-01T00:00:58Z",
          "distance": 0.7979
        },
        {
          "t": "2020-01-01T00:00:59Z",
          "distance": 0.9501
        },
        {
          "t": "2020-01-01T00:01:00Z",
          "distance": 1.897
        },
        {
          "t": "2020-01-01T00:01:01Z",
          "distance": 1.93
        },
        {
          "t": "2020-01-01T00:01:02Z",
          "distance": 1.273
        },
        {
          "t": "2020-01-01T00:01:03Z",
          "distance": 0.9615
        },
        {
          "t": "2020-01-01T00:01:04Z",
          "distance": 0.8961
        },
        {
          "t": "2020-01-01T00:01:05Z",
          "distance": 0.5546
        },
        {
          "t": "2020-01-01T00:01:06Z",
          "distance": 0.7303
        },
        {
          "t": "2020-01-01T00:01:07Z",
          "distance": 0.7979
        },
        {
          "t": "2020-01-01T00:01:08Z",
          "distance": 0.9501
        },
        {
          "t": "2020-01-01T00:01:09Z",
          "distance": 1.713
        },
        {
          "t": "2020-01-01T00:01:10Z",
          "distance": 1.831
        },
        {
          "t": "2020-01-01T00:01:11Z",
          "distance": 1.843
        },
        {
          "t": "2020-01-01T00:01:12Z",
          "distance": 1.316
        },
        {
          "t": "2020-01-01T00:01:13Z",
          "distance": 1.938
        },
        {
          "t": "2020-01-01T00:01:14Z",
          "distance": 0.9539
        },
        {
          "t": "2020-01-01T00:01:15Z",
          "distance": 0.689
        },
        {
          "t": "2020-01-01T00:01:16Z",
          "distance": 1.041
        },
        {
          "t": "2020-01-01T00:01:17Z",
          "distance": 1.31
        },
        {
          "t": "2020-01-01T00:01:18Z",
          "distance": 1.487
        },
        {
          "t": "2020-01-01T00:01:19Z",
          "distance": 1.906
        },
        {
          "t": "2020-01-01T00:01:20Z",
          "distance": 1.831
        },
        {
          "t": "2020-01-01T00:01:21Z",
          "distance": 1.893
        },
        {
          "t": "2020-01-01T00:01:22Z",
          "distance": 1.177
        },
        {
          "t": "2020-01-01T00:01:23Z",
          "distance": 0.9444
        },
        {
          "t": "2020-01-01T00:01:24Z",
          "distance": 1.396
        },
        {
          "t": "2020-01-01T00:01:25Z",
          "distance": 1.505
        },
        {
          "t": "2020-01-01T00:01:26Z",
          "distance": 1.274
        },
        {
          "t": "2020-01-01T00:01:27Z",
          "distance": 1.49
        },
        {
          "t": "2020-01-01T00:01:28Z",
          "distance": 1.43
        },
        {
          "t": "2020-01-01T00:01:29Z",
          "distance": 1.778
        },
        {
          "t": "2020-01-01T00:01:30Z",
          "distance": 1.738
        },
        {
          "t": "2020-01-01T00:01:31Z",
          "distance": null
        },
        {
          "t": "2020-01-01T00:01:32Z",
          "distance": null
        },
        {
          "t": "2020-01-01T00:01:33Z",
          "distance": null
        },
        {
          "t": "2020-01-01T00:01:34Z",
          "distance": null
        },
        {
          "t": "2020-01-01T00:01:35Z",
          "distance": null
        },
        {
          "t": "2020-01-01T00:01:36Z",
          "distance": null
        },
        {
          "t": "2020-01-01T00:01:37Z",
          "distance": null
        },
        {
          "t": "2020-01-01T00:01:38Z",
          "distance": null
        },
        {
          "t": "2020-01-01T00:01:39Z",
          "distance": null
        }
      ],
      "motifs": [
        {
          "t": [
            "2020-01-01T00:00:42Z",
            "2020-01-01T00:01:05Z"
          ],
          "neighbors": [
            "2020-01-01T00:00:55Z",
            "2020-01-01T00:00:49Z",
            "2020-01-01T00:00:03Z",
            "2020-01-01T00:00:22Z",
            "2020-01-01T00:01:16Z"
          ],
          "window_size": 10
        },
        {
          "t": [
            "2020-01-01T00:00:16Z",
            "2020-01-01T00:01:23Z"
          ],
          "neighbors": [
            "2020-01-01T00:01:12Z",
            "2020-01-01T00:01:29Z"
          ],
          "window_size": 10
        }
      ],
      "discords": [
        {
          "t": [
            "2020-01-01T00:00:32Z"
          ],
          "neighbors": [
            "2020-01-01T00:01:29Z",
            "2020-01-01T00:01:13Z",
            "2020-01-01T00:01:22Z"
          ],
          "window_size": 10
        }
      ],
      "chains": {
        "best": [
          "2020-01-01T00:00:42Z",
          "2020-01-01T00:01:05Z",
          "2020-01-01T00:01:16Z"
        ],
        "all": [
          [
            "2020-01-01T00:00:08Z",
            "2020-01-01T00:01:09Z",
            "2020-01-01T00:01:19Z"
          ],
          [
            "2020-01-01T00:00:42Z",
            "2020-01-01T00:01:05Z",
            "2020-01-01T00:01:16Z"
          ]
        ]
      }
    }
  }
}

We can visualize the matrix_profile part of the response.

55.52
19.34
3.216
0.5546
Matrix Profile
2020-01-01 00:00:00
2020-01-01 00:01:39
t

Matrix Profile computed on 100 data points with the Time Door API in 392.86ms.

If we look at the bottom of the response data, we see the following (human-friendly) snippet:

{
  "motifs": [
    {
      "t": [
        "2020-01-01T00:00:42Z",
        "2020-01-01T00:01:05Z"
      ],
      "neighbors": [
        "2020-01-01T00:00:55Z",
        "2020-01-01T00:00:49Z",
        "2020-01-01T00:00:03Z",
        "2020-01-01T00:00:22Z",
        "2020-01-01T00:01:16Z"
      ],
      "window_size": 10
    },
    {
      "t": [
        "2020-01-01T00:00:16Z",
        "2020-01-01T00:01:23Z"
      ],
      "neighbors": [
        "2020-01-01T00:01:12Z",
        "2020-01-01T00:01:29Z"
      ],
      "window_size": 10
    }
  ],
  "discords": [
    {
      "t": [
        "2020-01-01T00:00:32Z"
      ],
      "neighbors": [
        "2020-01-01T00:01:29Z",
        "2020-01-01T00:01:13Z",
        "2020-01-01T00:01:22Z"
      ],
      "window_size": 10
    }
  ],
  "chains": {
    "best": [
      "2020-01-01T00:00:42Z",
      "2020-01-01T00:01:05Z",
      "2020-01-01T00:01:16Z"
    ],
    "all": [
      [
        "2020-01-01T00:00:08Z",
        "2020-01-01T00:01:09Z",
        "2020-01-01T00:01:19Z"
      ],
      [
        "2020-01-01T00:00:42Z",
        "2020-01-01T00:01:05Z",
        "2020-01-01T00:01:16Z"
      ]
    ]
  }
}

Results

We can visualize the motifs, discords, and chains in 2 ways: time-embedded – to show their position in the time series data –, and z-normalized – to quickly compare their similarity.

55.52
19.34
Motif 1/2 (t-embedded)
2020-01-01 00:00:00
2020-01-01 00:01:39
t
55.52
19.34
Motif 2/2 (t-embedded)
2020-01-01 00:00:00
2020-01-01 00:01:39
t
4
-4
Motif 1/2 (z-normalized)
0
9
t
4
-4
Motif 2/2 (z-normalized)
0
9
t
55.52
19.34
Discord 1/1 (t-embedded)
2020-01-01 00:00:00
2020-01-01 00:01:39
t
4
-4
Discord 1/1 (z-normalized)
0
9
t
55.52
19.34
Best Chain (t-embedded)
2020-01-01 00:00:00
2020-01-01 00:01:39
t
55.52
19.34
Chain 2/2 (t-embedded)
2020-01-01 00:00:00
2020-01-01 00:01:39
t

Conclusion

We have outlined some of the core concepts – motifs, chains and discords – of the Matrix Profile, one of the most important algorithms in modern time series analysis.