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

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

動(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

? ?畫(huà)出下表：

3. ?接下來(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)的最短距離。

4. 接下來(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è)圖中將其可視化。

1. 


2. plot(a, type = "l")

3. 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.

最受歡迎的見(jiàn)解

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è)

?