Matrix Profile：针对时间序列挖掘的新型数据结构

原文链接，欢迎评论 ~

背景

在时间序列分析中，比较关注的点包括两方面：「异常」和「趋势」，例如医生查看心电图判断患者是否存在病患，零售业查看历史业绩曲线判断在哪个季节进行销售来提高业绩等。

对于时间序列的异常和趋势分析，其中一种方案是 「相似连接（similarity join）」，其主要思想就是：给定时间序列和窗口长度，计算子序列与时间序列内其它子序列间的距离，得到序列片段与自身进行比较的结果，以此来表征时间序列。

这种方法显而易见的缺点就是计算复杂度非常高，而且随着时间序列长度增大而增大。此时就可以引入 「Matrix Profile（MP）」 来减少计算时间。

注意 Matrix Profile 本身不是一种算法而是表征时间序列的一种数据结构。至于 Matrix profile 有多么强大，此处引入官方的 claim：

❝ The Matrix Profile has the potential to 「revolutionize time series data mining」 because of its generality, versatility, simplicity and scalability. In particular it has implications for time series motif discovery, time series joins, shapelet discovery (classification), density estimation, semantic segmentation, visualization, rule discovery, clustering etc.
❞

从 这段话已经可以看出，在时间序列分析领域 Matrix Profile 几乎已经是改革性的产品了！那么以下主要介绍 MP 的主要思想及其计算方法。

主要参考官方链接地址：

• https://matrixprofile.org/
• https://www.cs.ucr.edu/~eamonn/MatrixProfile.html

Matrix Profile

「Matrix Profile (MP)」 是 2016 年推出的一种相对较新的用于时间序列分析的数据结构，由加利福尼亚河滨大学的 Eamonn Keogh和新墨西哥大学的 Abdullah Mueen 开发。Matrix Profile 包含很多优点：「与领域无关，快速，提供精确（在需要时近似）的解决方案并且仅需要单一超参数」。

Matrix Profile 主要由两部分组成：

• distance profile：最小的标准化欧氏距离；
• profile index：第一个最近邻索引，即最相似子序列位置；

一般通过滑动窗口的方法来计算 Matrix Profile。例如给定窗口大小 m

1. 计算窗口大小的子序列相对于整个时间序列的距离；
2. 设置排除区域 (exclusion zone) 来忽略不重要的匹配；
3. 以最小距离值更新 distance profile；
4. 设置第一个最近邻居索引 profile index；

从以上步骤可以看出需要计算 n-m+1 次，其中 n​​ 代表完整的时间序列长度。排除区域是为了去掉不重要的匹配，例如与子序列非常相似的区域，一般为当前窗口索引的前后 1/2。

上述步骤的计算过程以图的表示形式如下：

Motifs + Discords

Matrix profile 中有两种重要的概念，「motifs」 和 「discords」，如下图所示

• motifs：表示时间序列中重复的模式；
• discords：表示异常；

在计算得到 Matrix profile 后可以很容易得到前 k​​​​ 个 motifs 和 discords。因为 matrix profile 中保存的是子序列间的距离，那么距离最小的表示序列越相似 motifs，而距离最大的表示越异常 discords。

Matrix Profile Algorithms

目前学术界已经提出了很多种算法来优化计算 Matrix Profile，主要方法如下表所示

在相同硬件和参数条件下其运行时间如下图所示

在 Matrix Profile 计算完成之后，有一系列的方法来提取特征，例如 tok-k Motifs、Discords 等。

示例

此部分采用一个简单示例说明 Matrix Profile 的效果，源码请参考：https://github.com/matrix-profile-foundation/article-matrix-profile-intro

原始时间序列如下图所示

从上面这序列看没什么异常的模式，那接着计算不同时间窗口的 matrix profile 如下

不同时间窗口下得到的 matrix profile 明显不同，说明只有选择合适的窗口大小才能得到有意义的 matrix profile。

对于不同时间窗口的 profile 计算 top-K discords，如下

从上面的结果可以看出，不同的 discords 对应不同的异常点，而且具有较好的解释意义。

但是对于周期性异常 matrix profile 计算得到的值并不是非常有意义，如下图所示

Thoughts

• Matrix profile 对于周期性比较强的且检测目标是子序列的任务效果尚可，但是对于周期异常波动效果较差，这也可能是这个方法不太出名的原因吧。
• Matrix profile 对提取序列特征方面效果应该还可以。
• 超参数滑动窗口大小需要根据对数据的先验知识进行判定，所以需要先使用自回归或者傅里叶变换来检测周期。