原文鏈接：http://tecdat.cn/?p=30169

原文出處：拓端數(shù)據(jù)部落公眾號(hào)

時(shí)間序列分類的動(dòng)態(tài)時(shí)間扭曲

動(dòng)態(tài)時(shí)間扭曲算法何時(shí)、如何以及為什么可以有力地取代常見的歐幾里得距離，以更好地對(duì)時(shí)間序列數(shù)據(jù)進(jìn)行分類

使用機(jī)器學(xué)習(xí)算法對(duì)時(shí)間序列進(jìn)行分類需要一定的熟悉程度。

時(shí)間序列分類（TSC）任務(wù)通常由監(jiān)督算法解決，它旨在創(chuàng)建分類器，將輸入時(shí)間序列映射到描述時(shí)間序列本身的一個(gè)或多個(gè)特征的離散變量（類）中。

可以在語(yǔ)音識(shí)別或手勢(shì)和運(yùn)動(dòng)識(shí)別中找到時(shí)序分類任務(wù)的有趣示例。

圖 — 移動(dòng)識(shí)別示例

用于其他類型的數(shù)據(jù)（例如表格數(shù)據(jù)）的標(biāo)準(zhǔn)分類算法不能直接應(yīng)用，因?yàn)樗鼈儗⒚總€(gè)樣本與其他樣本分開處理。

對(duì)于時(shí)間序列，不能忽略數(shù)據(jù)的時(shí)間順序，因此，不能考慮時(shí)間序列的每個(gè)樣本而考慮其他樣本，但必須保留時(shí)間順序。

出于這個(gè)原因，在文獻(xiàn)中，有幾種類型的時(shí)間序列分類技術(shù)，將在下一段中簡(jiǎn)要解釋。

時(shí)間序列分類方法

作為TSC不同類型方法的簡(jiǎn)要概述。

• 基于區(qū)間的方法：從不同的區(qū)間中提取時(shí)間序列的特征和信息，并將標(biāo)準(zhǔn)分類器應(yīng)用于特征本身。算法的一個(gè)示例是時(shí)序森林分類器。

• 基于字典?的方法：將時(shí)間序列的特征轉(zhuǎn)換為代表類的單詞。標(biāo)準(zhǔn)分類器應(yīng)用于提取單詞的分布。算法的一個(gè)例子是模式袋。

• 基于頻率的方法：在頻譜水平上提取時(shí)間序列的特征，通過(guò)頻率分析和連續(xù)的標(biāo)準(zhǔn)分類器。算法的一個(gè)示例是隨機(jī)間隔頻譜集成。

• 基于形狀的方法：形狀是代表類的時(shí)間序列的子序列。提取時(shí)間序列中k個(gè)最具特征的形狀，然后使用標(biāo)準(zhǔn)分類器。算法的一個(gè)示例是?Shapelet 變換分類器。

• 集成方法：對(duì)于一般問(wèn)題非常有競(jìng)爭(zhēng)力，它們結(jié)合了幾個(gè)估計(jì)器，例如HIVE-COTE算法。

基于距離的方法

在本文中，我們將重點(diǎn)介紹基于距離的方法。

它是一種將距離度量與分類器混合以確定類成員的非參數(shù)方法。分類器通常是?k 最近鄰 （KNN）??算法，用于了解要標(biāo)記的時(shí)間序列是否與訓(xùn)練數(shù)據(jù)集中的某些時(shí)間序列相似。根據(jù)鄰域，最近的類或最近類的聚合與所分析的時(shí)間序列相關(guān)聯(lián)。動(dòng)態(tài)時(shí)間扭曲（DTW）是基于距離的方法的一個(gè)示例。

?圖 — 基于距離的方法

距離指標(biāo)

在時(shí)間序列分類中，我們需要計(jì)算兩個(gè)序列之間的距離，同時(shí)牢記每個(gè)序列內(nèi)樣本之間的時(shí)間關(guān)系和依賴性。選擇正確的指標(biāo)是這種方法的基礎(chǔ)。

歐幾里得距離

讓我們開始考慮常見的歐幾里得距離。

鑒于時(shí)間序列分類，歐幾里得距離是不合適的，因?yàn)榧词顾Ａ袅藭r(shí)間順序，它也以逐點(diǎn)的方式測(cè)量距離。實(shí)際上，與兩個(gè)時(shí)間序列的歐幾里得距離的相似性是通過(guò)考慮它們的振幅來(lái)計(jì)算的，而與相移、時(shí)移和失真無(wú)關(guān)。

以圖中的示例為例。我們有樹時(shí)間序列：ts1、ts2 和 ts3。我們希望檢測(cè)兩條正弦曲線彼此相似，因?yàn)樗鼈兙哂邢嗤男螤詈蜕舷纶厔?shì)，即使它們的相位和頻率略有不同。但是，如果我們計(jì)算歐幾里得指標(biāo)，直線 ts3 的結(jié)果更接近 ts1。

?圖 — 要比較的時(shí)間序列示例

之所以出現(xiàn)這種現(xiàn)象，是因?yàn)闅W幾里得距離正在比較曲線的振幅，而不允許任何時(shí)間拉伸。

?圖 — 歐幾里得匹配

動(dòng)態(tài)時(shí)間扭曲

引入了動(dòng)態(tài)時(shí)間扭曲以避免歐幾里得距離的問(wèn)題。

從歷史上看，它是為語(yǔ)音識(shí)別而引入的。如圖所示，以不同的速度重復(fù)相同的句子，有必要將時(shí)間序列與相同的單詞相關(guān)聯(lián)，從而管理不同的速度。

?圖 — DTW 的語(yǔ)音識(shí)別應(yīng)用

DTW 允許您通過(guò)確定時(shí)間序列之間的最佳對(duì)齊方式并最大程度地減少時(shí)間失真和偏移的影響來(lái)衡量時(shí)間序列之間的相似性。

不同相的相似形狀，及時(shí)匹配彈性翹曲。

圖 — 動(dòng)態(tài)時(shí)間扭曲匹配

算法

讓我們考慮兩個(gè)時(shí)間序列 X = （x?， x?， ...，?xn）?和?Y = （y?， y?， ...， ym），?在等距時(shí)間點(diǎn)采樣，長(zhǎng)度相等或不同。

我們的目標(biāo)是找到對(duì)齊時(shí)間序列的最小距離。

?圖 — 要對(duì)齊的時(shí)間序列示例

定義局部成本矩陣，該矩陣將被最小化以找到最佳對(duì)齊方式。成本矩陣?C?定義為所有時(shí)間序列點(diǎn)的成對(duì)距離：

圖 — 當(dāng)?shù)爻杀揪仃?C

目的是通過(guò)遵循成本最低的路線，在局部成本矩陣上找到對(duì)齊時(shí)間序列的翹曲路徑。

翹曲路徑?p?是局部成本矩陣上的點(diǎn)序列，因此是兩個(gè)時(shí)間序列上的幾個(gè)點(diǎn)序列：

必須滿足一些條件：

• 邊界條件：

翹曲路徑的起點(diǎn)和終點(diǎn)必須是序列的第一個(gè)和最后一個(gè)點(diǎn)。

• 單調(diào)性條件：

以保留時(shí)間順序。

• 步長(zhǎng)條件：

以限制跳躍和時(shí)間偏移，同時(shí)對(duì)齊序列。

每個(gè)翹曲路徑都有相關(guān)的成本：

• 與翹曲路徑?p?相關(guān)的成本函數(shù)

?圖 — 翹曲路徑示例（非最佳）

目的是找到最佳的翹曲路徑：

DTW 通過(guò)遞歸實(shí)現(xiàn)解決，為此可以找到成本最低的翹曲路徑：

?

?圖 — 最佳翹曲路徑

找到最佳翹曲路徑后，將計(jì)算出相關(guān)的最優(yōu)成本，并將其用作?DTW 距離。

遞歸實(shí)現(xiàn)達(dá)到最優(yōu)，但計(jì)算成本為?O（NM），?其中 N 和 M 是兩個(gè)時(shí)間序列的長(zhǎng)度。

k-最近鄰

回到對(duì)感興趣的時(shí)間序列進(jìn)行分類的原始問(wèn)題，距離度量可以與k-最近鄰（k-nn）算法耦合。這意味著您可以計(jì)算時(shí)間序列到訓(xùn)練數(shù)據(jù)集中所有其他時(shí)間序列的 DTW 距離。然后，如果您正在考慮使用 1-nn 方法，則可以將最近鄰的類與時(shí)間序列相關(guān)聯(lián)，或者，同樣，您可以將 k?最近類中最常用的類與 k-nn?方法相關(guān)聯(lián)。

通過(guò)這種方式，您已經(jīng)達(dá)到了為時(shí)間序列分配類的目標(biāo)，該方法考慮了時(shí)間序列的時(shí)移。

傳統(tǒng) DTW 的替代方法可加快速度

快速 DTW

提出了一種多級(jí)方法來(lái)加快FastDTW算法中的算法速度。

它需要不同的步驟：

• 粗化：?將時(shí)間序列縮小為較粗的時(shí)間序列。這通過(guò)對(duì)相鄰點(diǎn)對(duì)求平均值來(lái)減小時(shí)間序列的大小。

• 投影：?找到最小距離的翹曲路徑，用作更高分辨率翹曲路徑的初始猜測(cè)。

• 優(yōu)雅：?通過(guò)局部調(diào)整將翹曲路徑從較低分辨率細(xì)化到較高分辨率。此步驟在投影路徑的鄰域中查找最佳翹曲路徑，半徑?r?參數(shù)控制鄰域的大小。

?圖 — 快速 DTW

FastDTW允許快速分辨率，復(fù)雜度為O（Nr），?具有良好的次優(yōu)解決方案。

動(dòng)態(tài)時(shí)間規(guī)整（DTW,Dynamic time warping,動(dòng)態(tài)時(shí)間歸整/規(guī)整/彎曲）是一種衡量?jī)蓚€(gè)序列之間最佳排列的算法。線性序列數(shù)據(jù)如時(shí)間序列、音頻、視頻都可以用這種方法進(jìn)行分析。DTW通過(guò)局部拉伸和壓縮，找出兩個(gè)數(shù)字序列數(shù)據(jù)的最佳匹配，同時(shí)也可以計(jì)算這些序列之間的距離。

DTW是干什么的？

動(dòng)態(tài)時(shí)間規(guī)整算法，故名思議，就是把兩個(gè)代表同一個(gè)類型的事物的不同長(zhǎng)度序列進(jìn)行時(shí)間上的“對(duì)齊”。比如DTW最常用的地方，語(yǔ)音識(shí)別中，同一個(gè)字母，由不同人發(fā)音，長(zhǎng)短肯定不一樣，把聲音記錄下來(lái)以后，它的信號(hào)肯定是很相似的，只是在時(shí)間上不太對(duì)整齊而已。所以我們需要用一個(gè)函數(shù)拉長(zhǎng)或者縮短其中一個(gè)信號(hào)，使得它們之間的誤差達(dá)到最小。

DTW怎么計(jì)算？

因此，動(dòng)態(tài)時(shí)間規(guī)整要解決的問(wèn)題就是：找到一條最優(yōu)的規(guī)整路徑?W = {\varpi _1},{\varpi _2}...{\varpi _k}?W=?1,?2...?k，其中?{w_k} = (i,j)?wk=(i,j)，即認(rèn)為時(shí)間序列1的第i個(gè)點(diǎn)和時(shí)間序列2的第j個(gè)點(diǎn)是類似的。全部類似點(diǎn)的距離之和做為規(guī)整路徑距離，用規(guī)整路徑距離來(lái)衡量?jī)蓚€(gè)時(shí)間序列的類似性。規(guī)整路徑距離越小，類似度越高。

下面我們來(lái)總結(jié)一下DTW動(dòng)態(tài)時(shí)間規(guī)整算法的簡(jiǎn)單的步驟：

1. 首先肯定是已知兩個(gè)或者多個(gè)序列，但是都是兩個(gè)兩個(gè)的比較，所以我們假設(shè)有兩個(gè)序列A={a1,a2,a3,...,am} ?B={b1,b2,b3,....,bn}，維度m>n

2. 然后用歐式距離計(jì)算出每序列的每?jī)牲c(diǎn)之間的距離，D(ai,bj) 其中1≤i≤m，1≤j≤n

? ?畫出下表：

1. ?接下來(lái)就是根據(jù)上圖將最短路徑找出來(lái)。從D(a1,a2)沿著某條路徑到達(dá)D(am,bn)。找路徑滿足：假如當(dāng)前節(jié)點(diǎn)是D(ai,bj)，那么下一個(gè)節(jié)點(diǎn)必須是在D(i+1,j)，D(i,j+1)，D(i+1,j+1)之間選擇，并且路徑必須是最短的。計(jì)算的時(shí)候是按照動(dòng)態(tài)規(guī)劃的思想計(jì)算，也就是說(shuō)在計(jì)算到達(dá)第(i,j)個(gè)節(jié)點(diǎn)的最短路徑時(shí)候，考慮的是左上角也即第(i-1,j)、(i-1,j-1)、(i,j-1)這三個(gè)點(diǎn)到(i,j)的最短距離。

2. 接下來(lái)從最終的最短距離往回找到那條最佳的輸出路徑， 從D(a1,b1)到D(am,bn)。他們的總和就是就是所需要的DTW距離

【注】如果不回溯路徑，直接在第3步的時(shí)候?qū)⒆笊辖侨齻€(gè)節(jié)點(diǎn)到下一個(gè)節(jié)點(diǎn)最短的點(diǎn)作為最優(yōu)路徑節(jié)點(diǎn)，就是貪婪算法了。DTW是先計(jì)算起點(diǎn)到終點(diǎn)的最小值，然后從這個(gè)最小值回溯回去看看這個(gè)最小值都經(jīng)過(guò)了哪些節(jié)點(diǎn)。

R語(yǔ)言實(shí)現(xiàn)

在這篇文章中，我們將學(xué)習(xí)如何找到兩個(gè)數(shù)字序列數(shù)據(jù)的排列。

創(chuàng)建序列數(shù)據(jù)

首先，我們生成序列數(shù)據(jù)，并在一個(gè)圖中將其可視化。

plot(a, type = "l") lines(b, col = "blue")

計(jì)算規(guī)整方式

dtw()函數(shù)計(jì)算出一個(gè)最佳規(guī)整方式。

align(a, b)

返回以下項(xiàng)目。你可以參考str()函數(shù)來(lái)了解更多信息。

現(xiàn)在，我們可以繪制組合。

用雙向的方法作圖

動(dòng)態(tài)時(shí)間規(guī)整結(jié)果的繪圖：點(diǎn)比較

顯示查詢和參考時(shí)間序列以及它們的排列方式，進(jìn)行可視化檢查。

Plot(align)

?用密度作圖

顯示疊加了規(guī)整路徑的累積成本密度?。

該圖是基于累積成本矩陣的。它將最優(yōu)路徑顯示為全局成本密度圖中的 "山脊"。

PlotDensity(align)

小結(jié)

總而言之, DTW是一種非常有用的計(jì)算序列最小距離的方法, 不論是在語(yǔ)音序列匹配, 股市交易曲線匹配, 還是DNA堿基序列匹配等等場(chǎng)景, 都有其大展身手的地方. 它的最大特點(diǎn)是在匹配時(shí)允許時(shí)間上的伸縮, 因此可以更好的在一堆序列集合中找到最佳匹配的序列.

1. Eamonn Keogh, Chotirat Ann Ratanamahatana,?Exact indexing of dynamic time warping,?Knowledge and Information Systems, 2005.

最受歡迎的見解

1.在python中使用lstm和pytorch進(jìn)行時(shí)間序列預(yù)測(cè)

2.python中利用長(zhǎng)短期記憶模型lstm進(jìn)行時(shí)間序列預(yù)測(cè)分析

3.使用r語(yǔ)言進(jìn)行時(shí)間序列（arima，指數(shù)平滑）分析

4.r語(yǔ)言多元copula-garch-模型時(shí)間序列預(yù)測(cè)

5.r語(yǔ)言copulas和金融時(shí)間序列案例

6.使用r語(yǔ)言隨機(jī)波動(dòng)模型sv處理時(shí)間序列中的隨機(jī)波動(dòng)

7.r語(yǔ)言時(shí)間序列tar閾值自回歸模型

8.r語(yǔ)言k-shape時(shí)間序列聚類方法對(duì)股票價(jià)格時(shí)間序列聚類

9.python3用arima模型進(jìn)行時(shí)間序列預(yù)測(cè)