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

最近我們被客戶要求撰寫關(guān)于動態(tài)時間規(guī)整算法的研究報告，包括一些圖形和統(tǒng)計輸出

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

時間序列分類的動態(tài)時間扭曲

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

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

可以在語音識別或手勢和運動識別中找到時序分類任務(wù)的有趣示例。

圖 — 移動識別示例

用于其他類型的數(shù)據(jù)（例如表格數(shù)據(jù)）的標(biāo)準(zhǔn)分類算法不能直接應(yīng)用，因為它們將每個樣本與其他樣本分開處理。

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

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

時間序列分類方法

作為TSC不同類型方法的簡要概述。

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

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

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

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

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

基于距離的方法

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

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

?圖 ?— 基于距離的方法

距離指標(biāo)

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

歐幾里得距離

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

鑒于時間序列分類，歐幾里得距離是不合適的，因為即使它保留了時間順序，它也以逐點的方式測量距離。實際上，與兩個時間序列的歐幾里得距離的相似性是通過考慮它們的振幅來計算的，而與相移、時移和失真無關(guān)。

以圖中的示例為例。我們有樹時間序列：ts1、ts2 和 ts3。我們希望檢測兩條正弦曲線彼此相似，因為它們具有相同的形狀和上下趨勢，即使它們的相位和頻率略有不同。但是，如果我們計算歐幾里得指標(biāo)，直線 ts3 的結(jié)果更接近 ts1。

?圖 — 要比較的時間序列示例

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

?圖 — 歐幾里得匹配

動態(tài)時間扭曲

引入了動態(tài)時間扭曲以避免歐幾里得距離的問題。

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

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

DTW 允許您通過確定時間序列之間的最佳對齊方式并最大程度地減少時間失真和偏移的影響來衡量時間序列之間的相似性。

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

圖 — 動態(tài)時間扭曲匹配

算法

讓我們考慮兩個時間序列 X = （x?， x?， ...，?xn）?和?Y = （y?， y?， ...， ym），?在等距時間點采樣，長度相等或不同。

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

?圖 — 要對齊的時間序列示例

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

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

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

翹曲路徑?p?是局部成本矩陣上的點序列，因此是兩個時間序列上的幾個點序列：

必須滿足一些條件：

• 邊界條件：

翹曲路徑的起點和終點必須是序列的第一個和最后一個點。

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

以保留時間順序。

• 步長條件：

以限制跳躍和時間偏移，同時對齊序列。

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

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

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

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

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

?

?圖 — 最佳翹曲路徑

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

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

k-最近鄰

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

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

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

快速 DTW

提出了一種多級方法來加快FastDTW算法中的算法速度。

它需要不同的步驟：

• 粗化：?將時間序列縮小為較粗的時間序列。這通過對相鄰點對求平均值來減小時間序列的大小。

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

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

?圖 — 快速 DTW

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

R語言實現(xiàn)

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

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

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

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

點擊標(biāo)題查閱往期內(nèi)容

Python用KShape對時間序列進(jìn)行聚類和肘方法確定最優(yōu)聚類數(shù)k可視化

左右滑動查看更多

01

02

03

04

計算規(guī)整方式

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

align(a,?b)

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

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

用雙向的方法作圖

動態(tài)時間規(guī)整結(jié)果的繪圖：點比較

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

Plot(align)

用密度作圖

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

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

PlotDensity(align)

小結(jié)

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

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

點擊文末?“閱讀原文”

獲取全文完整資料。

本文選自《R語言DTW(Dynamic Time Warping) 動態(tài)時間規(guī)整算法分析序列數(shù)據(jù)和可視化》。

點擊標(biāo)題查閱往期內(nèi)容

ARMA-GARCH-COPULA模型和金融時間序列案例
時間序列分析：ARIMA GARCH模型分析股票價格數(shù)據(jù)
GJR-GARCH和GARCH波動率預(yù)測普爾指數(shù)時間序列和Mincer Zarnowitz回歸、DM檢驗、JB檢驗
【視頻】時間序列分析：ARIMA-ARCH / GARCH模型分析股票價格
時間序列GARCH模型分析股市波動率
PYTHON用GARCH、離散隨機波動率模型DSV模擬估計股票收益時間序列與蒙特卡洛可視化
極值理論 EVT、POT超閾值、GARCH 模型分析股票指數(shù)VaR、條件CVaR：多元化投資組合預(yù)測風(fēng)險測度分析
Garch波動率預(yù)測的區(qū)制轉(zhuǎn)移交易策略
金融時間序列模型ARIMA 和GARCH 在股票市場預(yù)測應(yīng)用
時間序列分析模型：ARIMA-ARCH / GARCH模型分析股票價格
R語言風(fēng)險價值：ARIMA，GARCH，Delta-normal法滾動估計VaR（Value at Risk）和回測分析股票數(shù)據(jù)
R語言GARCH建模常用軟件包比較、擬合標(biāo)準(zhǔn)普爾SP 500指數(shù)波動率時間序列和預(yù)測可視化
Python金融時間序列模型ARIMA 和GARCH 在股票市場預(yù)測應(yīng)用
MATLAB用GARCH模型對股票市場收益率時間序列波動的擬合與預(yù)測R語言GARCH-DCC模型和DCC（MVT）建模估計
Python 用ARIMA、GARCH模型預(yù)測分析股票市場收益率時間序列
R語言中的時間序列分析模型：ARIMA-ARCH / GARCH模型分析股票價格
R語言ARIMA-GARCH波動率模型預(yù)測股票市場蘋果公司日收益率時間序列
Python使用GARCH，EGARCH，GJR-GARCH模型和蒙特卡洛模擬進(jìn)行股價預(yù)測
R語言時間序列GARCH模型分析股市波動率
R語言ARMA-EGARCH模型、集成預(yù)測算法對SPX實際波動率進(jìn)行預(yù)測
matlab實現(xiàn)MCMC的馬爾可夫轉(zhuǎn)換ARMA - GARCH模型估計
Python使用GARCH，EGARCH，GJR-GARCH模型和蒙特卡洛模擬進(jìn)行股價預(yù)測
使用R語言對S＆P500股票指數(shù)進(jìn)行ARIMA + GARCH交易策略
R語言用多元ARMA,GARCH ,EWMA, ETS,隨機波動率SV模型對金融時間序列數(shù)據(jù)建模
R語言股票市場指數(shù)：ARMA-GARCH模型和對數(shù)收益率數(shù)據(jù)探索性分析
R語言多元Copula GARCH 模型時間序列預(yù)測
R語言使用多元AR-GARCH模型衡量市場風(fēng)險
R語言中的時間序列分析模型：ARIMA-ARCH / GARCH模型分析股票價格
R語言用Garch模型和回歸模型對股票價格分析
GARCH（1,1），MA以及歷史模擬法的VaR比較
matlab估計arma garch 條件均值和方差模型R語言POT超閾值模型和極值理論EVT分析