對時間序列進行分類是應用機器和深度學習模型的常見任務之一。本篇文章將涵蓋 8 種類型的時間序列分類方法。這包括從簡單的基于距離或間隔的方法到使用深度神經網絡的方法。這篇文章旨在作為所有時間序列分類算法的參考文章。

時間序列定義

在涵蓋各種類型的時間序列 (TS) 分類方法之前，我們先統一時間序列的概念，TS 可以分為單變量或多變量 TS。

• 單變量 TS 是一組有序的(通常)實數值。
• 多變量 TS 是一組單變量 TS。每個時間戳都是一個向量或實數值數組。

單或多元TS的數據集通常包含一個單或多元TS的有序集。此外，數據集通常包含由一個單一編碼的標簽向量表示，其長度表示不同類的標簽。

TS分類的目標是通過在給定數據集上訓練任何分類模型來定義的，這樣模型就可以學習所提供數據集的概率分布。也就是說當給定TS時，模型應該學會正確地分配類標簽。

基于距離的方法

基于距離或最近鄰的 TS 分類方法使用各種基于距離的度量來對給定數據進行分類。它是一種監督學習技術，其中新 TS 的預測結果取決于與其最相似的已知時間序列的標簽信息。

距離度量是描述兩個或多個時間序列之間距離的函數，它是決定性的。典型的距離度量是：

• p 范數(如曼哈頓距離、歐幾里德距離等)
• 動態時間規整 (DTW)

決定度量后，通常應用 k 最近鄰 (KNN) 算法，該算法測量新 TS 與訓練數據集中所有 TS 之間的距離。計算完所有距離后，選擇最近的 k 個。最后新的 TS 被分配到 k 個最近鄰居中的大多數所屬的類別。

雖然最流行的范數肯定是 p 范數，尤其是歐幾里德距離，但它們有兩個主要缺點，使它們不太適合 TS 分類任務。因為范數僅針對相同長度的兩個 TS 定義，實際上并不總是能夠得到長度相等的序列。范數僅獨立比較每個時間點的兩個 TS 值，但是大多數 TS 值相互關聯。

而DTW 可以解決 p 范數的兩個限制。經典的 DTW 可以最小化時間戳可能不同的兩個時間序列點之間的距離。這意味著輕微偏移或扭曲的 TS 仍然被認為是相似的。下圖可視化了基于 p 范數的度量與 DTW 的工作方式之間的差異。

結合KNN，將DTW作為基準基準算法，用于TS分類的各種基準評估。

KNN也可以有決策樹的方法實現。例如，鄰近森林算法建模了一個決策樹森林，使用距離度量來劃分TS數據。

基于區間和頻率的方法

基于區間的方法通常將TS分割為多個不同的區間。然后使用每個子序列來訓練一個單獨的機器學習(ML)分類器。會生成一個分類器集合，每個分類器都作用于自己的區間。在單獨分類的子序列中計算最常見的類將返回整個時間序列的最終標簽。

時間序列森林

基于區間的模型最著名的代表是時間序列森林(Time Series Forest)。TSF 是建立在初始 TS 的隨機子序列上的決策樹的集合。每棵樹負責將一個類分配給一個區間。

這是通過計算匯總特征(通常是均值、標準差和斜率)來為每個間隔創建特征向量來完成的。之后根據計算出的特征訓練決策樹，并通過所有樹的多數投票獲得預測。投票過程是必需的，因為每棵樹只評估初始 TS 的某個子序列。

除了 TSF 之外，還有其他基于區間的模型。TSF 的變體使用附加特征，例如子序列的中值、四分位數間距、最小值和最大值。與經典的 TSF 算法相比，還存在一種相當復雜的算法，稱為 Random Interval Spectral Ensemble (RISE)算法。

RISE

RISE 算法在兩個方面有別于經典的 TS 森林。

• 每棵樹使用單個 TS 間隔
• 它是通過使用從 TS 中提取的光譜特征來訓練的(而不是使用匯總統計數據作為均值、斜率等)

在 RISE 技術中，每個決策樹都建立在一組不同的傅里葉、自相關、自回歸和部分自相關特征之上。該算法按如下方式工作：

選擇 TS 的第一個隨機區間，并在這些區間上計算上述特征。然后通過組合提取的特征創建一個新的訓練集。在這些基礎上，訓練決策樹分類器。最后使用不同的配置重復這些步驟以創建集成模型，該模型是單個決策樹分類器的隨機森林。

基于字典的方法

基于字典的算法是另一類TS分類器，它基于字典的結構。它們涵蓋了大量不同的分類器，有時可以與上述分類器結合使用。

這里是涵蓋的基于字典的方法列表：

• Bag-of-Patterns (BOP)
• Symbolic Fourier Approximation (SFA)
• Individual BOSS
• BOSS Ensemble
• BOSS in Vector Space
• contractable BOSS
• Randomized BOSS
• WEASEL

這類的方法通常首先將 TS 轉換為符號序列，通過滑動窗口從中提取“WORDS”。然后通過確定“WORDS”的分布來進行最終分類，這通常是通過對“WORDS”進行計數和排序來完成的。這種方法背后的理論是時間序列是相似的，這意味著如果它們包含相似的“WORDS”則屬于同一類。基于字典的分類器主要過程通常是相同的。

• 在 TS 上運行特定長度的滑動窗口
• 將每個子序列轉換為一個“WORDS”(具有特定長度和一組固定字母)
• 創建這些直方圖

下面是最流行的基于字典的分類器的列表：

Bag-of-Patterns算法

模式袋(Bag-of-Patterns, BOP)算法的工作原理類似于用于文本數據分類的詞袋算法。這個算法計算一個單詞出現的次數。

從數字(此處為原始 TS)創建單詞的最常見技術稱為符號聚合近似 (SAX)。首先將 TS 劃分為不同的塊，每個塊之后都會標準化，這意味著它的均值為 0，標準差為 1。

通常一個詞的長度比子序列中實數值的數量要長。因此，進一步對每個塊應用分箱。然后計算每個分箱的平均實際值，然后將其映射到一個字母。例如，對于所有低于 -1 的平均值，分配字母“a”，所有大于 -1 和小于 1 的值“b”，所有高于 1 的值“c”。下圖形象化了這個過程。

這里每個段包含 30 個值，這些值被分成 6 個一組，每個組被分配三個可能的字母，構成一個五個字母的單詞。最后匯總每個詞的出現次數，并通過將它們插入最近鄰算法來用于分類。

Symbolic Fourier Approximation

與上述 BOP 算法的思想相反，在 BOP 算法中，原始 TS 被離散化為字母然后是單詞，可以對 TS 的傅里葉系數應用類似的方法。

最著名的算法是Symbolic Fourier Approximation (SFA)，它又可以分為兩部分。

計算 TS 的離散傅立葉變換，同時保留計算系數的子集。

• 監督：單變量特征選擇用于根據統計數據(如 F 統計量或 χ2 統計量)選擇排名較高的系數
• 無監督：通常取第一個系數的子集，代表TS的趨勢

結果矩陣的每一列都被獨立離散化，將 TS 的 TS 子序列轉換為單個單詞。

• 監督：計算分箱邊緣，使得實例熵的雜質標準最小化。
• 無監督：計算分箱邊緣，使其基于傅立葉系數的極值(分箱是統一的)或基于這些的分位數(每個分箱中的系數數量相同)

基于上面的預處理，可以使用各種不同算法，進一步處理信息以獲得 TS 的預測。

BOSS

Bag-of-SFA-Symbols (BOSS) 算法的工作原理如下：

• 通過滑動窗口機制提取 TS 的子序列
• 在每個片段上應用 SFA 轉換，返回一組有序的單詞
• 計算每個單詞的頻率，這會產生 TS 單詞的直方圖
• 通過應用 KNN 等算法結合自定義 BOSS 度量(歐氏距離的微小變化)進行分類。

BOSS算法的變體包含很多變體：

BOSS Ensemble

BOSS Ensemble算法經常用于構建多個單個 BOSS 模型，每個模型在參數方面各不相同：字長、字母表大小和窗口大小。通過這些配置捕捉各種不同長度的圖案。通過對參數進行網格搜索并僅保留最佳分類器來獲得大量模型。

BOSS in Vector Space

BOSS in Vector Space (BOSSVS) 算法是使用向量空間模型的個體 BOSS 方法的變體，該方法為每個類計算一個直方圖，并計算詞頻-逆文檔頻率 (TF-IDF) 矩陣。然后通過找到每個類的TF-IDF向量與TS本身的直方圖之間余弦相似度最高的類，得到分類。

Contractable BOSS

Contractable BOSS(cBOSS) 算法比經典的 BOSS 方法在計算上快得多。

通過不對整個參數空間進行網格搜索而是對從中隨機選擇的樣本進行網格搜索來實現加速的。cBOSS 為每個基本分類器使用數據的子樣本。cBOSS 通過僅考慮固定數量的最佳基分類器而不是高于特定性能閾值的所有分類器來提高內存效率。

Randomized BOSS

BOSS 算法的下一個變體是Randomized BOSS (RBOSS)。該方法在滑動窗口長度的選擇中添加了一個隨機過程，并巧妙地聚合各個 BOSS 分類器的預測。這類似于 cBOSS 變體，減少了計算時間，同時仍保持基準性能。

WEASE

通過在 SFA 轉換中使用不同長度的滑動窗口，TS 分類詞提取 (WEASEL) 算法可以提高標準 BOSS 方法的性能。與其他 BOSS 變體類似，它使用各種長度的窗口大小將 TS 轉換為特征向量，然后由 KNN 分類器對其進行評估。

WEASEL 使用特定的特征推導方法，通過僅使用應用 χ2 檢驗的每個滑動窗口的非重疊子序列進行，過濾掉最相關的特征。

將 WEASEL 與Multivariate Unsupervised Symbols(WEASEL+MUSE)相結合，通過將上下文信息編碼到每個特征中從 TS 中提取和過濾多元特征。

基于 Shapelet 的方法

基于shapelets的方法使用初始時間序列的子序列(即shapelets)的思想。選擇shapelets是為了將它們用作類的代表，這意味著shapelets包含類的主要特征，這些特征可用于區分不同的類。在最優的情況下，它們可以檢測到同一類內TS之間的局部相似性。

下圖給出了一個shapelet的示例。它只是整個TS的子序列。

使用基于shapelets的算法需要確定使用哪個shapelets的問題。可以通過手工制作一組shapelets來選擇，但這可能非常困難。也可以使用各種算法自動選擇shapelets。

基于Shapelet提取的算法

Shapelet Transform是由Lines等人提出的一種基于Shapelet提取的算法，是目前最常用的算法之一。給定n個實值觀測值的TS, shapelet由長度為l的TS的子集定義。

shapelet和整個TS之間的最小距離可以使用歐幾里德距離-或任何其他距離度量- shapelet本身和從TS開始的所有長度為l的shapelets之間的距離。

然后算法選出k個長度屬于一定范圍的最佳shapelets。這一步可以被視為某種單變量特征提取，每個特征都由給定數據集中shapelet與所有TS之間的距離定義。然后根據一些統計數據對shapelets進行排名。這些通常是f統計量或χ2統計量，根據它們區分類的能力對shapelets進行排序。

完成上述步驟后，可以應用任何類型的ML算法對新數據集進行分類。例如基于knn的分類器、支持向量機或隨機森林等等。

尋找理想的shapelets的另一個問題是可怕的時間復雜性，它會隨著訓練樣本的數量成倍增加。

基于 Shapelet學習的算法

基于 Shapelet 學習的算法試圖解決基于 Shapelet 提取的算法的局限性。這個想法是學習一組能夠區分類的 shapelet，而不是直接從給定的數據集中提取它們。

這樣做有兩個主要優點：

• 它可以獲得不包含在訓練集中但對類別具有強烈辨別力的 shapelet。
• 不需要在整個數據集上運行算法，這可以顯著減少訓練時間

但是這種方法也有一些使用可微分最小化函數和選擇的分類器引起的缺點。

要想代替歐幾里德距離，我們必須依賴可微分函數，這樣可以通過梯度下降或反向傳播算法來學習 shapelet。最常見的依賴于 LogSumExp 函數，該函數通過取其參數的指數之和的對數來平滑地逼近最大值。由于 LogSumExp 函數不是嚴格凸函數，因此優化算法可能無法正確收斂，這意味著它可能導致糟糕的局部最小值。

并且由于優化過程本身是算法的主要組成部分，所以還需要添加多個超參數進行調優。

但是該方法在實踐中非常有用，可以對數據產生一些新的見解。

基于核的方法

基于 shapelet 的算法的一個細微變化是基于核的算法。學習和使用隨機卷積核(最常見的計算機視覺算法)，它從給定的 TS 中提取特征。

隨機卷積核變換 (ROCKET) 算法是專門為此目的而設計的。。它使用了大量的內核，這些內核在長度、權重、偏置、膨脹和填充方面都不同，并且是從固定的分布中隨機創建的。

在選擇內核后，還需要一個能夠選擇最相關的特征來區分類的分類器。原始論文中使用嶺回歸(線性回歸的 L2 正則化變體)來執行預測。使用它有兩個好處，首先是它的計算效率，即使對于多類分類問題也是如此，其次是使用交叉驗證微調唯一的正則化超參數的非常的簡單。

使用基于核的算法或 ROCKET 算法的核心優勢之一是使用它們的計算成本相當低。

基于特征的方法

基于特征的方法一般可以涵蓋大多數算法，這些算法對給定的時間序列使用某種特征提取，然后由分類算法執行預測。

關于特征，從簡單的統計特征到更復雜的基于傅里葉的特征。在hctsa(https://github.com/benfulcher/hctsa)中可以找到大量這樣的特性，但是嘗試和比較每個特性可能是一項無法完成的任務，特別是對于較大的數據集。所以提出了典型時間序列特征(catch22)算法被提出了。

catch22算法

該方法旨在推斷一個小的TS特征集，不僅需要強大的分類性能，而且還可以進一步最小化冗余。catch22從hctsa庫中總共選擇了22個特性(該庫提供了4000多個特性)。

該方法的開發人員通過在93個不同的數據集上訓練不同的模型來獲得22個特征，并評估其上表現最好的TS特征，得到了一個仍然保持出色性能的小子集。其上的分類器可以自由選擇，這使得它成為另一個超參數來進行調優。

Matrix Profile Classifier

另一種基于特征的方法是 Matrix Profile (MP) 分類器，它是一種基于 MP 的可解釋 TS 分類器，可以在保持基準性能的同時提供可解釋的結果。

設計人員從基于shapelet的分類器中提取了名為Matrix Profile模型的。該模型表示 TS 的子序列與其最近鄰居之間的所有距離。這樣，MP 就能夠有效地提取 TS 的特征，例如motif和discord，motif 是 TS 的彼此非常相似的子序列，而discords 描述彼此不同的序列。

作為理論上的分類模型，任何模型都可以使用。這種方法的開發者選擇了決策樹分類器。

除了這兩種提到的方法之外，sktime 還提供了一些更基于特征的 TS 分類器。

模型集成

模型集成本身不是一種獨立的算法，而是一種組合各種 TS 分類器以創建更好組合預測的技術。模型集成通過組合多個單獨的模型來減少方差，類似于使用大量決策樹的隨機森林。并且使用各種類型的不同學習算法會導致更廣泛和更多樣化的學習特征集，這反過來會獲得更好的類別辨別力。

最受歡迎的模型集成是 Hierarchical Vote Collective of Transformation-based Ensembles (HIVE-COTE)。它存在許多不同種類的相似版本，但它們的共同點是通過對每個分類器使用加權平均值來組合不同分類器的信息，即預測。

Sktime 使用兩種不同的 HIVE-COTE 算法，其中第一種結合了每個估計器的概率，其中包括一個 shapelet 變換分類器 (STC)、一個 TS 森林、一個 RISE 和一個 cBOSS。第二個由 STC、Diverse Canonical Interval Forest Classifier(DrCIF，TS 森林的變體)、Arsenal(ROCKET 模型的集合)和 TDE(BOSS 算法的變體)的組合定義。

最終的預測是由 CAWPE 算法獲得的，該算法為每個分類器分配權重，這些權重是通過在訓練數據集上找到的分類器的相對估計質量獲得的。

下圖是用于可視化 HIVE-COTE 算法工作結構的常用圖示：

基于深度學習的方法

關于基于深度學習的算法，可以自己寫一篇很長的文章來解釋有關每種架構的所有細節。但是本文只提供一些常用的 TS 分類基準模型和技術。

雖然基于深度學習的算法在計算機視覺和 NLP 等領域非常流行并得到廣泛研究，但它們在 TS 分類領域卻并不常見。Fawaz 等人。在他們關于 TS 分類的深度學習的論文中對當前現有方法的詳盡研究：總結研究了具有六種架構的 60 多個神經網絡 (NN) 模型：

• Multi-Layer Perceptron
• Fully Convolutional NN (CNN)
• Echo-State Networks (based on Recurrent NNs)
• Encoder
• Multi-Scale Deep CNN
• Time CNN

上述大多數模型最初是為不同的用例開發的。所以需要根據不同的用例進行測試。

在2020 年還發布了 InceptionTime 網絡。InceptionTime 是五個深度學習模型進行的集成，其中每個模型都是由 Szegedy 等人首先提出的InceptionTime創建的。這些初始模塊同時將多個不同長度的過濾器應用于 TS，同時從 TS 的較短和較長子序列中提取相關特征和信息。下圖顯示了 InceptionTime 模塊。

它由多個以前饋方式堆疊的初始模塊組成，并與殘差連接。最后是全局平均池化和全連接神經網絡生成預測結果。

下圖顯示了單個初始模塊的工作情況。

總結

本文總結的大量的算法、模型和技術列表不僅能幫助理解時間序列分類方法的廣闊領域，希望對你有所幫助