首頁  >  文章  >  科技週邊  >  八種時間序列分類法總結

八種時間序列分類法總結

王林
王林轉載
2023-05-06 10:04:061861瀏覽

對時間序列進行分類是應用機器和深度學習模型的常見任務之一。本篇文章將涵蓋 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

#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統計量或χ²統計量,根據它們區域分類的能力對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
  • Scale Deep CNN
  • Time CNN

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

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

八種時間序列分類法總結

它由多個先前饋方式堆疊的初始模組組成,並與殘差連接。最後是全域平均池化和全連結神經網路產生預測結果。

下圖顯示了單一初始模組的工作情況。

八種時間序列分類法總結

總結

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

以上是八種時間序列分類法總結的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:51cto.com。如有侵權,請聯絡admin@php.cn刪除