時間序列分類@ShapeNet: A Shapelet-Neural Network Approach for Multivariate Time Series Classification

作者：由 daydaymoyu 發表于書法時間：2021-11-26

一篇時間序列分類的論文。

ShapeNet： A Shapelet-Neural Network Approach for Multivariate Time Series Classification

論文連結：

程式碼連結：

Abstract&Introduction

時間序列 shapelet 是相對比較短的判別子序列，它不僅準確，而且可以解釋單變數時間序列（univariate time series UTS）的分類問題。然而，現有的關於 shapelets 選擇的工作不能應用於多元時間序列分類（multivariate time series classification MTSC），因為 MTSC 的候選 shapelets 可能來自不同長度的不同變數，因此無法直接比較。為了應對這一挑戰，本文提出了一種稱為 ShapeNet 的新模型，它將不同長度的 shapelet 候選嵌入到一個用於 shapelet 選擇的統一空間中。該網路使用叢集方式的三元組損失進行訓練，它考慮了錨點（anchor）和多個正（負）樣本之間的距離以及正（負）樣本之間的距離，這對於收斂很重要。文中計算具有代表性和多樣化的最終 shapelet，而不是直接使用所有嵌入進行模型構建，以避免大部分non-discriminative shapelet 候選。文中在 UEA MTS 資料集上使用具有競爭力的最新技術、基準方法以及 ShapeNet 上進行了實驗。結果表明，ShapeNet 的準確性是所有比較方法中最好的。此外，文中透過兩個案例研究說明了 shapelets 的可解釋性。

文中指出基於 shapelet 的 MTSC 方法還處於起步階段。一些典型的挑戰如下

多元時間序列具有多個變數。Shapelet 具有大量（voluminous）且異構（heterogeneous）的候選。對 shapelets 的完整搜尋可能不準確；

不同變數的shapelet候選可以有不同的長度，這樣的shapelet很難比較。對於過多的候選者，不清楚如何選擇對於分類任務有益的判別性的候選shapelet；

大多數現有研究採用黑盒方法。很少有方法提供可解釋的結果。 shapelets 的可解釋性對MTSC至關重要；

因此在本文中，我們為 MTSC 問題提出了一種新的 shapelet 神經網路方法，稱為

ShapeNet

，以解決上述挑戰。ShapeNet 的概述如下圖所示。 ShapeNet 的好處是雙重的，即提高準確性和可解釋的分類結果。

首先，提出 Multi-length-input dilated causal Convolutional Neural Network （Mdc-CNN），它將不同長度和不同變數的shapelet候選嵌入到一個統一的空間中（shapelet embedding）。文中採用擴張卷積（dilated convolution），它在序列中具有指數級的感受野且能夠處理長期依賴關係，同時也不會增加模型複雜性。因果卷積只對當前時間之前的時間進行卷積，確保未來值不會影響當前值。此外，我們提出了一個基於叢集級別的三元組損失函式來訓練 Mdc-CNN，它考慮了叢集內/叢集間度量學習來加速收斂和提高穩定性。我們的 cluster-wise 三元組損失不僅將多個正樣本和多個負樣本作為輸入，還計算它們之間的距離。相比之下，之前的三元組損失僅涉及一個正樣本和一個負樣本。

其次，文中避免直接提供大量的 shapelet 候選來構建分類器。首先對shapelet候選嵌入進行聚類。然後提出了一個utility function來選擇接近大叢集質心且與其他叢集質心不同的前k個候選（top-k candidates），這為提供了具有代表性和多樣化的最終shapelets。

然後文中採用首先被正式定義的多元shapelet變換（multivariate shapelet transformation MST）。具體來說，給定一個多元時間序列，計算它到相同變數的選定 shapelet 的距離以獲得 MST 表示。

總之，ShapeNet 將不同變數的可變長度時間序列子序列學習到統一的嵌入中，其中 ShapeNet 可以捕獲 MTS 中不同變數之間的互動資訊。

Method

Multi-length-input Dilated Causal CNN (Mdc-CNN)

【Design rationale】

ShapeNet 採用一些現有的技術構建各個模組。首先採用擴充套件因果卷積（the dilated causal convolutional neural network Dc-CNN）來學習子序列的新表徵。其次，儘管輸出可以與輸入具有相同的長度，但 Dc-CNN 無法處理不同長度的輸入。因此，文中引入一個全域性最大池化層（global max pooling layer）和一個線性層（linear layer），它們堆疊在最後一個 Dc-CNN 層的頂部，以將所有 shapelet 候選嵌入到統一空間中（由框架圖中的綠色框表示）。我們稱其為多長度輸入擴張因果卷積（Multi-length-input Dilated Causal CNN Mdc-CNN）。

【Mdc-CNN architecture】

Mdc-CNN的結構如下圖所示。可以看出圖（a）編碼器具有

個殘差塊，其中

是擴充套件因子，全域性最大池化層（global max pooling layer）和一個線性層（linear layer）堆疊在最後一個殘差塊的頂部。編碼器的輸入是各種長度和變數的時間序列子序列，輸出是它們的一致性表示。我們稱輸出為 shapelet 候選嵌入。下圖（b）展示了具有兩個相同子塊的殘差塊和一個擴張的因果卷積塊。下圖（c）展示了擴張因子

的擴張因果卷積示例。圖 2（b）和圖 2（c）的更多細節可以在下面這篇論文中中找到。

An Empirical Evaluation of Generic Convolutional and Recurrent Networks for Sequence Modeling

An elaboration of the Multi-length-input dilated causal Convolutional Neural Network （Mdc-CNN）

Unsupervised Representation Learning

學習/訓練（類似於 word2vec）的目標是確保相似的時間序列獲得相似的表示，反之亦然。然而，word2vec 假設的第二個要求在時間序列的上下文中並不總是成立。例如，Basicmotions 資料集中的步行類的一個變數如下圖所示。我們可以很容易地觀察到波形的一些波峰彼此在時間上相距很遠但distance卻很小。

An example from Basicmotions of the violation of the second requirement of word2vec： subsequences that are far away but have a small distance between them

其次，在一個batch中只包含一個正樣本來訓練網路，這在shapelets的表示學習的上下文中通常是不穩定的。

最後，之前的研究工作沒有考慮負（正）樣本之間的距離。下圖顯示了使用原始三元組損失學習 shapelet 表示的損失。可以注意到，雖然損失略有下降，但它是不穩定的，很難收斂。

A comparison between our cluster-wise triplet loss （multiple positives and multiple negatives， both with intra distances） and original triplet loss （one positive and multiple negatives without intra distance） on ArticularyWordRecognition

【Cluster-wise triplet loss function】

提出一種cluster-wise triplet loss function，該損失以多個正負樣本和正（負）樣本之間的距離作為輸入。為簡單起見，我們採用兩個叢集來演示。具體來說，所有可能的三元組訓練集

$\mathcal{T}$

定義為

其中

是anchor shapelet candidate，

和

表示正樣本和負樣本。三元組

$\mathcal{T}$

在真實資料中是非常多的，使用所有三元組進行訓練在計算上是不現實的且次優的。因此文中採用

三重取樣

。首先將正（負）樣本與錨點的歸一化距離表示為

$\mathcal{D}_{AP}(\mathcal{D}_{AN})$

，得到下式

其中

$\mu$

是在正樣本和負樣本之間強加的margin。假設採用平方歐幾里得距離，則有

其中

$f\left(\cdot \right) \in \mathbb{R}^z$

是透過Mdc-CNN表徵的嵌入。除了anchor和正負樣本之間的距離，正樣本之間的距離應該小，而負樣本之間的距離應該較大，所有正（負）樣本之間的最大距離如下式所示

樣本內損失定義如下：

將上述內容融合在一起，文中提出了叢集方式的三元組損失函式（cluster-wise triplet loss function for the triplets），以無監督的方式下訓練網路，損失函式定義為

Illustration of the effect of training a model using the cluster-wise triplet loss function， positives are closer to each other and the anchor， negatives are closer to each other but farther from the anchor

上圖說明了文中基於叢集方式三元組損失的兩個叢集的一個例子。三元組損失函式最小化錨點與所有正樣本之間的距離，以及所有正（負）樣本之間的距離【

這裡似乎與前文的描述有差異

】，又使錨點（正）與所有負樣本之間的距離最大化。

Multivariate Shapelet Transformation

在得到 shapelet 候選者的統一表徵後，文中建議選擇高質量和多樣化的候選者作為最終的 shapelet。採用 MTS 的 shapelet 變換過程，然後應用經典分類器來解決 MTSC 問題。

【Determining final shapelets】

透過前面的小節，所有的候選shapelet都被嵌入到一個統一的空間中。它允許簡單地採用聚類方法（例如，kmeans）來獲得候選 shapelet 的

個聚類簇。文中提出了一個實用方法來對最接近叢集質心的候選者進行排名，該方法定義為

上式的第一個組成部分是候選叢集的大小。一個大的叢集意味著它代表了許多候選shapelets嵌入。第二個組成部分是候選shapelets嵌入與其他叢集中其他候選shapelets嵌入的距離。文中在

個聚類簇中選擇top-k候選shapelets嵌入，並檢索原始時間序列子序列作為最終的 shapelets。

【Multivariate Shapelet Transformation MST】文中給出了MST的正式定義，這裡直接給出原文的定義。

Definition 1 Multivariate shapelet transformation.

Multivariate shapelet transformation is a method to transform a multivariate time series

$\mathbb{T}_m$

into a new data space

$\left( d_{m,1},d_{m,2},...,d_{m,k} \right)$

by calculating the distances with a set of final shapelets

$\mathcal{S}_k$

， denoted as

$d_{m,j}=\text{dist}\left( T_m^v,S_j \right)$

， where

$\mathcal{S}_i \in \mathcal{S}_k$

，

$T_m^v \in \mathbb{T}_m$

， and the variable of

and

is the same。

一個例子如下圖所示。

Illustration of transforming an MTS instance into the MST representation

上圖顯示了 MST 的一個示例。最左邊的圖展示了一個例項，其中包含來自 Basicmotions 資料集的六個變數。兩個 shapelet，S1 和 S2，位於中間。對於 MST，我們計算具有相同變數的時間序列與子序列之間的距離（例如，第一個變數（頂部的紅色時間序列）與 S1 之間的距離）。因此，時間序列例項的 MST 表示是一個向量，如最右側所示。MST之後，資料集

$\mathbb{D}$