基于Shapelet的时间序列机器学习¶

在本笔记本中，我们的目标是介绍理解用于时间序列机器学习的Shapelets所需的概念。我们介绍了shapelets，并在描述具体分类器之前概述了支撑分类器的算法。在transformers笔记本中有关于特定shapelet转换器的笔记本。

在本笔记本中，我们将长度为$m$且维度为$d$的时间序列表示为向量$X = [\mathbf{x}_1, \ldots, \mathbf{x}_m]$，其中$\mathbf{x}_j \in \mathbb{R}^d$。

在aeon中，我们将一个系列描述为X : (n_channels, n_timepoints)，其中X是一个二维数组，n_channels对应于维度$d$，或特征的数量，n_timepoints对应于$m$，即观测值的数量。请注意，这个定义意味着我们在每个时间点之间有一个固定的时间间隔（即具有固定频率的时间序列）。当$d=1$时，$X$被称为单变量，当$d>1$时，$X$被称为多变量。

当谈论时间序列集合时，我们将使用符号 ${\cal X} = [X_1, \ldots, X_n]$，在代码中对应于形状为 X : (n_samples, n_channels, n_timepoints) 的三维数组，其中 $n$ 对应于 n_samples，即组成数据集 ${\cal X}$ 的时间序列的数量。

例如，我们可以使用GunPoint数据集：

[3]:

from aeon.datasets import load_classification

X_train, y_train = load_classification("GunPoint", split="train")
X_test, y_test = load_classification("GunPoint", split="test")

print(f"shape of the array: {X_train.shape}")
print(f"n_samples = {X_train.shape[0]}")
print(f"n_channels = {X_train.shape[1]}")
print(f"n_timepoints = {X_train.shape[2]}")

shape of the array: (50, 1, 150)
n_samples = 50
n_channels = 1
n_timepoints = 150

我们在aeon中有以下基于shapelet的分类器：

[4]:

from aeon.utils.discovery import all_estimators

all_estimators("classifier", tag_filter={"algorithm_type": "shapelet"})

[4]:

[('LearningShapeletClassifier',
  aeon.classification.shapelet_based._ls.LearningShapeletClassifier),
 ('RDSTClassifier', aeon.classification.shapelet_based._rdst.RDSTClassifier),
 ('RSASTClassifier',
  aeon.classification.shapelet_based._rsast.RSASTClassifier),
 ('SASTClassifier', aeon.classification.shapelet_based._sast.SASTClassifier),
 ('ShapeletTransformClassifier',
  aeon.classification.shapelet_based._stc.ShapeletTransformClassifier)]

为了简单起见，我们在接下来的定义中假设以下假设

我们只考虑单变量时间序列（$d=1$）
我们只考虑等长时间序列（$m_i = m_j, \forall i,j :nbsphinx-math:`in [1,n] `$）

Shapelet的定义¶

一个Shapelet $S$ 被定义为训练数据中一个时间序列的子序列，它在区分类别时非常有用。它是从训练数据集 ${\cal X}^{\ train}$ 中提取出来的。一个shapelet $S$ 的长度为 $l$，其中 \(l。因此，给定我们的时间序列集合，我们可以为第一个时间序列中的某个通道创建一个从第45个时间戳开始的shapelet候选：我们在 aeon 中有以下基于shapelet的分类器：

[21]:

length = 25  # the length of the shapelet
S = X_train[0, 0, 45 : 45 + length]  # Set the shapelet values
print(S)

[-0.64349171 -0.64265061 -0.6420974  -0.64447929 -0.6488921  -0.65765851
 -0.66120325 -0.64966432 -0.61016844 -0.53743483 -0.46503123 -0.35853483
 -0.28313648 -0.17744604  0.15824648  0.35028455  0.48241039  0.60380734
  0.79710411  0.98755132  1.2037853   1.4065415   1.5962459   1.7128307
  1.7788152 ]

在aeon中，我们提供了一些用于shapelets的可视化类，以帮助创建图表并理解背后的情况。例如，我们可以可视化由shapelet S表示的子序列：（请注意，以下内容在您的系统上首次导入时可能需要很长时间，因为它需要导入aeon中所有基于shapelet的估计器，其中一些由于numba需要一些编译工作）

[22]:

from aeon.visualisation import ShapeletVisualizer

shp_vis = ShapeletVisualizer(S)
fig = shp_vis.plot(figure_options={"figsize": (7, 4)})

../../_images/examples_classification_shapelet_based_7_0.png

历史上，shapelets 最初被提出作为时间序列机器学习的原语 [1]，并被用作时间序列分类决策树中的分割标准。为了实现这一点，定义了 shapelet $S$ 和时间序列 $X$ 之间的距离 $dist$，例如 $dist(S,X) \rightarrow \mathbb{R}$。基于 Shapelet 的分割标准随后基于距离的阈值 $\lambda$，如 $dist(S,X) < \lambda$，以将时间序列 $X$ 引导到左或右子节点，每个节点由另一个 shapelet 定义。

这种计算距离的方法，至今仍在使用，是计算$S$与$X$中所有大小为$l$的子序列之间的欧几里得距离，并返回最小值。更正式地说：

$\displaystyle{dist(S,X) = \min\limits_{i\ :1, \ldots, m-l+1} \sqrt{\sum_{j=0}^{l-1}(\mathbf{s}_j - \mathbf{x}_{i+j})^2}}$

这表示shapelet与时间序列的距离是shapelet与$X$中相同大小的最佳匹配子序列之间的距离。我们可以用以下图像来说明这个公式，其中我们将从值$v$中提取最小值：

drawing

我们可以通过两种方式可视化这个想法，首先，我们可以将shapelet定位在时间序列$X$中最佳匹配的子序列上：

[23]:

fig = shp_vis.plot_on_X(X_test[1], figure_options={"figsize": (7, 4)})

../../_images/examples_classification_shapelet_based_9_0.png

或者我们可以可视化形状$S$与$X$中所有相同大小的子序列之间的距离。我们将其称为$S$和$X$之间的距离向量，其定义为

[24]:

fig = shp_vis.plot_distance_vector(X_test[1], figure_options={"figsize": (7, 4)})

../../_images/examples_classification_shapelet_based_11_0.png

距离向量图展示了shapelet与每个子序列之间的距离，基于shapelet滑动时的起始索引。例如，图中重叠的shapelet和最佳匹配子序列显示，当shapelet从第39个索引开始时，子序列最适合shapelet。这在距离向量图中也得到了展示，其中y在x = 39时达到最小值。

从Shapelet树到Shapelet转换¶

稍后，Shapelet Transform [2] 被引入作为基于shapelet的决策树的替代方案。他们的想法是不将shapelet用作树中的分裂标准，而是用作从时间序列中提取特征的方法，以便能够使用任何类型的表格分类器。在这种方法中，每个时间序列 $X$ 和shapelet $S$ 只提取一个特征：距离 $dist(S,X)$。

给定一组$k$个形状${\cal S} = [S_1, \ldots, S_k]$，这允许创建一个时间序列数据集${\cal X} = [X_1, \ldots, X_n]$的嵌入${\cal X}'$，例如：

$\displaystyle{{\cal X}' = \begin{bmatrix} dist(S_1, X_1) & ... & dist(S_k, X_1) \\ ... & ... & ... \\ dist(S_1, X_n) & ... & dist(S_k, X_n) \end{bmatrix}}$

更通俗地说，Shapelet转换创建了一个表格，其中行是原始时间序列，每列是一个特征，在这种情况下，是shapelet到时间序列的（最短）距离。

这可以用作具有$k$特征的表格数据集，适用于任何表格分类器。在aeon中，每个基于shapelet的转换算法都遵循相同的逻辑，有些算法每个shapelet提取多个特征（例如RDST，它提取3个特征，得到$3k$个特征）。

我们可以通过以下方式列出aeon中所有可用的shapelet转换器：

[25]:

from aeon.utils.discovery import all_estimators

for k, v in all_estimators("transformer", tag_filter={"algorithm_type": "shapelet"}):
    print(f"{k}: {v}")

RSAST: <class 'aeon.transformations.collection.shapelet_based._rsast.RSAST'>
RandomDilatedShapeletTransform: <class 'aeon.transformations.collection.shapelet_based._dilated_shapelet_transform.RandomDilatedShapeletTransform'>
RandomShapeletTransform: <class 'aeon.transformations.collection.shapelet_based._shapelet_transform.RandomShapeletTransform'>
SAST: <class 'aeon.transformations.collection.shapelet_based._sast.SAST'>

例如，让我们选择RandomShapeletTransform转换器，我们可以使用fit和transform函数来获取时间序列嵌入：

[34]:

from aeon.transformations.collection.shapelet_based import RandomShapeletTransform

st = RandomShapeletTransform(max_shapelets=10, n_shapelet_samples=500, random_state=0)
st.fit(X_train, y_train)
st.transform(X_test).shape

[34]:

(150, 10)

按照计划，我们获得了一个大小为 $(n,k)$ 的矩阵。给定任何基于形状的转换的拟合实例，我们可以使用另一个可视化类来绘制提取的形状：

[35]:

from aeon.visualisation import ShapeletTransformerVisualizer

st_vis = ShapeletTransformerVisualizer(st)
id_shapelet = 0  # Identifier of the shapelet

fig = st_vis.plot_on_X(id_shapelet, X_test[1], figure_options={"figsize": (7, 4)})

../../_images/examples_classification_shapelet_based_18_0.png

你也可以使用这个类创建和自定义你自己的shapelet图，例如：

[36]:

from matplotlib import pyplot as plt

fig, ax = plt.subplots(ncols=3, figsize=(15, 5))
st_vis.plot(
    id_shapelet,
    ax=ax[0],
    scatter_options={"c": "purple"},
    line_options={"linestyle": "-."},
)
st_vis.plot_on_X(
    id_shapelet, X_test[1], ax=ax[1], line_options={"linewidth": 3, "alpha": 0.5}
)
ax[1].set_title(f"Best match of shapelet {id_shapelet} on X")
st_vis.plot_distance_vector(
    id_shapelet, X_test[1], ax=ax[2], line_options={"c": "brown"}
)
ax[2].set_title(f"Distance vector of shapelet {id_shapelet} on X")

[36]:

Text(0.5, 1.0, 'Distance vector of shapelet 0 on X')

../../_images/examples_classification_shapelet_based_20_1.png

归一化的形状¶

请注意在上图中，shapelet值（最左边的图）与用于将其定位在时间序列上的值（中间的图）不匹配。这是因为在RandomShapeletTransform中，所有shapelet都使用归一化距离。这使得shapelet具有尺度不变性。这意味着shapelet的最佳匹配集中在子序列的形状上，并且与其尺度无关。这是aeon中大多数shapelet转换估计器的情况。在RandomDilatedShapeletTransform [3]中，您可以调整proba_normalization参数，以修改在fit期间使用归一化距离初始化shapelet的概率。

为了实现这一点，在计算$dist(S,X)$之前，shapelet值和子序列值都进行了z标准化，例如要对$S$进行z标准化，我们首先计算$\mu_S$和$\sigma_S$，分别是$S$的均值和标准差，然后得到其标准化版本$\bar{S}$如下：

$\displaystyle{\bar{S} = \frac{(S - \mu_S)}{\sigma_S}}$

如何从时间序列中提取形状特征？¶

既然我们已经理解了什么是shapelets以及它们是如何使用的，那么还有一个问题没有解答，我们如何提取它们？这个过程隐藏在基于shapelet的转换的fit方法背后。我们可以区分x种shapelet提取过程：

穷举搜索：在这种情况下，我们提取所有可能的shapelet候选（即给定长度的所有子序列），并评估它们的质量以选择最佳的一个。例如，在去除自相似的shapelet之后，我们可以基于$dist(S,X) < \lambda$计算shapelet $S$的信息增益，如[1]中的shapelet-tree所做的那样，或者如[2]中使用固定效应ANOVA的F统计量所做的那样。
基于启发式的搜索：穷举搜索的一个问题是，提取和评估数据集中所有形状候选可能需要很长时间。文献中提出了许多不同的方法，试图在最小化获取形状所需时间的同时，近似穷举搜索的结果。
- 例如，RandomShapeletTransform 不是评估所有可能的候选者，而是使用参数 n_shapelet_samples 从输入中随机提取有限数量的 shapelets。然后，它将质量评估限制在这些随机提取的候选者上，以减少搜索时间。在候选者提取过程中，它还考虑了自相似 shapelets 的概念，以避免采样相似的 shapelets，因为它们将是冗余的。
- 其他方法如SAST[4]仅在训练数据中选择少量“参考”时间序列，其中所有子序列将被视为shapelets，而不评估其质量。这将“特征选择”步骤留给将使用转换的分类器。RSAST[5]使用相同的方法，但也使用一些统计标准来进一步减少从这些参考时间序列中提取的候选数量。
- 在RandomDilatedShapeletTransform中使用的另一种方法是使用半随机提取，该方法通过输入空间的掩码来指导。一旦从时间序列中随机采样了一个shapelet，采样点周围的邻近点将从可用采样点列表中移除。这避免了提取自相似的shapelet，并提高了提取的shapelet集的多样性。此过程影响的邻近点数量由alpha_similarity参数控制。
Shapelet生成: 这最后一种方法从另一个角度看待问题：如果我的数据集中最好的shapelets不在训练数据中怎么办？目标是使用优化方法，如梯度下降或进化算法，来生成shapelet值，而不是从输入中提取它们。第一个shapelet生成方法是Learning Shapelet [6]，由于提取的性质，它仅在aeon内部实现为分类器 LearningShapeletClassifier。

Shapelet “自相似性”¶

我们可以通过以下图像来可视化自相似性的概念。假设我们采样了以绿色高亮的shapelet，在自相似性（这是alpha_similarity的一个特例，其中alpha=1）下，所有以红色堆叠并高亮的相邻子序列不能被考虑为shapelet候选，因为它们会重叠。下一个有效的候选者将是橙色高亮的那些，因为它们不与绿色shapelet重叠。修剪的候选者数量由$\alpha \times l$决定，其中$l$是采样的shapelet（绿色）的长度。

drawing

用于分类的Shapelet转换¶

让我们回顾一下，给定一组从shapelet转换器中提取的$k$个shapelet ${\cal S} = [S_1, \ldots, S_k]$，在fit方法期间，我们使用transform方法创建时间序列数据集${\cal X} = [X_1, \ldots, X_n]$的嵌入${\cal X}'$，以获得：

$\displaystyle{{\cal X}' = \begin{bmatrix} dist(S_1, X_1) & ... & dist(S_k, X_1) \\ ... & ... & ... \\ dist(S_1, X_n) & ... & dist(S_k, X_n) \end{bmatrix}}$

了解了shapelet变换的工作原理后，我们现在可以在转换后的数据上使用分类器来创建分类模型。aeon中的多个估计器为您提供了一个带有fit和predict函数的分类接口。整体shapelet分类框架如下图所示：

drawing

您可以通过以下方式获取可用的shapelet-estimators列表：

例如，使用ShapeletTransformClassifier，fit方法将提取shapelets，执行数据的转换，并默认在转换后的数据上训练一个RotationForestClassifier分类器。您可以选择要使用的分类器，可以通过使用estimator参数，或者自己从RandomShapeletTransform估计器构建一个管道：

[38]:

from sklearn.ensemble import RandomForestClassifier

from aeon.classification.shapelet_based import ShapeletTransformClassifier

stc = ShapeletTransformClassifier(
    estimator=RandomForestClassifier(ccp_alpha=0.01), n_shapelet_samples=100
)
stc.fit(X_train, y_train)
stc.score(X_test, y_test)

[38]:

0.98

类似于可视化变压器，我们也可以可视化基于形状的分类器的单个形状，并在可能的情况下，根据某些估计器的特征重要性标准绘制最佳形状。这些估计器的范围通常仅限于继承自scikit-learn的BaseDecisionTree、BaseForest或LinearClassifierMixin类的那些，因为这些被认为是最可解释的模型之一，其中特征权重直接与输入特征相关。

例如，在aeon的旋转森林中，主成分分析（PCA）的应用使得将特征重要性追溯到单个shapelets变得复杂。由于PCA将原始特征空间转换为一组新的不相关组件，因此很难直接将这些组件与原始shapelet特征关联起来，从而降低了特征重要性方面的可解释性。

[39]:

from aeon.visualisation import ShapeletClassifierVisualizer

stc_vis = ShapeletClassifierVisualizer(stc)
id_class = 0
fig = stc_vis.visualize_shapelets_one_class(
    X_test,
    y_test,
    id_class,
    figure_options={"figsize": (18, 12), "nrows": 2, "ncols": 2},
)

../../_images/examples_classification_shapelet_based_27_0.png

这四个图表都有助于解释基于shapelet的算法的可解释性。在这里，我们取类别0中最具区分性的shapelet，并探索其局部和全局模式。

最小值的箱线图（左上角）：该图通过关注形状的全局质量引入了一个新的视角。它展示了形状与不同类别中每个时间序列之间的最小距离的分布。正如预期的那样，形状与类别0的拟合比其他类别更紧密。
最佳匹配示例（右上角）：此图表通过展示shapelet如何适应每个类别的随机时间序列来扩展最佳匹配的可视化。绿色和橙色曲线分别代表类别1和类别0的样本。Shapelet应该并且确实与类别0的橙色时间序列更紧密地对齐，展示了其根据局部模式区分这两个类别的有效性。
Shapelet 参数（左下角）：此图已经介绍过，优雅地展示了 shapelet 随时间变化的模式。
示例的距离向量（右下角）：此图是距离向量可视化的扩展，提供了从“示例上的最佳匹配”图中，shapelet在每个点上对两个时间序列的拟合程度的比较。这有助于全面了解shapelet在任何点上对时间序列的拟合程度。

扩张的形状¶

扩张形状[3]通过向$S$添加扩张参数$\mathbf{d}$来修改距离函数$dist(S,X)$的公式，其作用类似于卷积核中的扩张。该参数的目标有两个：

通过允许形状特征跨越$l\times \mathbf{d}$个点，同时仅需要$l$个值，来增加形状特征的感受野。
事实上，我们只需要$l$而不是$l\times \mathbf{d}$来计算$dist(S,X)$，并且具有等效的感受野，这也是避免维度诅咒的一个优势（即，在距离中比较的点越多，对于相同输入产生等效结果的可能性越大）。

距离公式，当$\mathbf{d}=1$时，与经典公式等价，如下所示：

$\displaystyle{dist(S,X) = \min\limits_{i\ :1, \ldots, m-(l\times \mathbf{d})} \sqrt{\sum_{j=0}^{l-1}(\mathbf{s}_j - \mathbf{x}_{i+(j\times \mathbf{d})})^2}}$

然后对于 $\mathbf{d}=2$ 可以如下所示：

drawing

请注意，RDST 使用的是曼哈顿距离而不是欧几里得距离。

从距离向量中提取更多特征¶

距离向量 $V = [v_1, \ldots, v_{m-(l\times \mathbf{d})}]$ 其中 $v_i = \sqrt{\sum_{j=0}^{l-1}(\mathbf{s}_j - \mathbf{x}_{i+(j\times \mathbf{d})})^2}$（这里使用欧几里得距离），包含了 $S$ 和 $X$ 中候选子序列之间的所有距离（相同长度的子序列，包括扩张）。虽然 aeon 中大多数基于 shapelet 的转换器和分类器仅从 $V$ 中提取最小值，但在 RandomDilatedShapeletTransform 中，还提取了两个额外的特征：

$\text{argmin} V$ : 最佳匹配的位置，其中位置是shapelet前端的位置
$\sum_i I(v_i < \lambda)$ : 形状出现特征，计算$S$与$X$接近$\lambda$的次数（其中$I$为恒等函数）。

这些功能使我们能够使用shapelets进行区分，并且由于RandomDilatedShapeletTransform也利用了归一化和非归一化的shapelets，我们可以区分以下情况：

drawing

多元情况的泛化¶

多元形状特征的情况是适应距离函数$dist(S,X)$到多元情况的问题。这归结为是否使用通道依赖或通道独立距离的问题。在依赖的情况下，距离考虑多个通道，而在独立的方法中，我们对所有通道应用单变量距离并将每个通道的距离向量相加。这个选择取决于数据的性质和距离函数的性质。

例如，如果我们使用动态时间规整（DTW），这意味着我们要么搜索一个包含所有通道的规整路径，要么为每个通道独立搜索规整路径。但如果我们使用的是平方欧几里得距离（不使用平方根），这两种选择将是等效的。

目前只有RDSTClassifier和ShapeletTransformClassifier（以及它们各自的转换）支持多变量输入。在多变量情况下，另一个可能改变的是，一个shapelet $S$在计算距离时可能只考虑通道的一个子集（这为$S$添加了一个参数，这是一个布尔掩码，用于指示使用哪个通道）。这在RDSTClassifier的原始实现中使用了，但目前尚未在aeon实现中出现。

推广到不等长情况¶

在这种情况下，唯一需要的调整是确保shapelets不超过我们用作输入的任何时间序列的长度。否则，这更多是一个实现问题，因为理论上，使用shapelet和不同大小的时间序列计算距离向量是没有问题的。

在这种情况下，一个需要注意的点是提取的特征。特别是使用RDSTClassifier时，由于argmin和ShapeletOccurence特征都会受到时间序列长度变化的影响，用户需要决定是否应该通过提取它们的时间序列长度来对这些特征进行归一化（例如argmin/m_i，其中$m_i$是时间序列$X_i$的长度）。如果不进行归一化，这些特征可能会编码一些关于时间序列长度的信息，从而在信息不相关时对分类器产生偏差。

SAST 示例¶

SASTClassifier [4] 是一个基于管道形状的分类器，我们可以用于进一步的可视化示例。

[40]:

from sklearn.ensemble import RandomForestClassifier

from aeon.classification.shapelet_based import SASTClassifier

stc = SASTClassifier(classifier=RandomForestClassifier(ccp_alpha=0.01)).fit(
    X_train, y_train
)
from aeon.visualisation import ShapeletClassifierVisualizer

stc_vis = ShapeletClassifierVisualizer(stc)
id_class = 0
fig = stc_vis.visualize_shapelets_one_class(
    X_test,
    y_test,
    id_class,
    n_shp=3,
    figure_options={"figsize": (18, 12), "nrows": 2, "ncols": 2},
)

../../_images/examples_classification_shapelet_based_35_0.png

../../_images/examples_classification_shapelet_based_35_1.png

../../_images/examples_classification_shapelet_based_35_2.png

[41]:

weights = stc._classifier.feature_importances_
fig = stc.plot_most_important_feature_on_ts(X_test[0][0], weights, 3)

../../_images/examples_classification_shapelet_based_36_0.png

UCR单变量数据集上的性能¶

我们当前的shapelet分类器位于目录aeon.classification.shapelet_based中。目前我们只有其中三个的参考结果。

[42]:

all_shapelet_classifiers = [
    "MrSQMClassifier",
    "ShapeletTransformClassifier",
    "RDSTClassifier",
    "SASTClassifier",
    "RSASTClassifier",
    "LearningShapeletClassifier",
]
from aeon.benchmarking.results_loaders import get_estimator_results_as_array
from aeon.datasets.tsc_datasets import univariate

est = ["MrSQMClassifier", "RDSTClassifier", "ShapeletTransformClassifier"]
names = [t.replace("Classifier", "") for t in est]
results, present_names = get_estimator_results_as_array(
    names, univariate, include_missing=False
)
results.shape

[42]:

(112, 3)

[43]:

from aeon.visualisation import plot_boxplot, plot_critical_difference

plot_critical_difference(results, names)

[43]:

(<Figure size 600x220 with 1 Axes>, <Axes: >)

../../_images/examples_classification_shapelet_based_40_1.png

[44]:

plot_boxplot(results, names, relative=True)

[44]:

(<Figure size 1000x600 with 1 Axes>, <Axes: >)

../../_images/examples_classification_shapelet_based_41_1.png

参考文献¶

[1] L. Ye 和 E. Keogh. 时间序列形状：数据挖掘的新原语。在 Proc. 15th ACM SIGKDD, 2009 (https://www.cs.ucr.edu/~eamonn/shaplet.pdf)

[2] J. Lines 等人。用于时间序列分类的 shapelet 变换。在 Proc. 18th ACM SIGKDD, 2012.

[3] Antoine Guillaume 等人。随机扩张形状变换：时间序列形状的新方法。ICPRAI 2021。

[4] Mbouopda, Michael Franklin, 和 Engelbert Mephu Nguifo. 可扩展且准确的时间序列分类子序列变换. 模式识别 147, 2023.

[5] Varela, N. R., Mbouopda, M. F., & Nguifo, E. M. RSAST: 用于时间序列分类的采样形状。2023.

[6] Grabocka, J. 等人。学习时间序列形状。在Pro.e 20th ACM SIGKD, 2014.)。

[ ]:

使用nbsphinx生成。Jupyter笔记本可以在这里找到。